Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

before programming an algorithm which implements the simplex method, I thought I'd solve an issue before the actual programming work begins.

For some reason, I can NEVER get the correct answer. I've understood the method, but the problem is with the row operations - where you try to get a column to have all 0 values except for the pivot element which has a value of '1'.

To do this, I play around with the rows by doing R1-R2, R2+5R1, etc. I always manage to get the pivot column to be 1 and the rest 0's, however my answers never match the correct ones. Ive narrowed it down to a problem with the row operations - are there any rules related to this, or can I just play around with the rows as much as I like? Also, can I mix between older tableaux and the current one?

Thanks

share|improve this question
1  
If you want, feel free to post a sample table and I'll be more specific about what went wrong. Let me know if you want to know a "always do this row operation" rule. I assume you've learned them, and are just curious why being creative messes things up. –  Jack Schmidt May 16 '11 at 0:18
    
Unfortunately I haven't come across any specific row operation rules - which is why I'm searching for guidelines :) What I usually do is play around with a mixture of rows from the same table and previous tables, and add/subtract them to get the required column completely with 0's except for the pivot - which works, however answers never match the supposed correct ones. Therefore, I'm definitely doing something wrong with the row operations. –  simplex May 16 '11 at 0:46
    
Cool. I think you'll get it if you remember the rule: The first row you mention is the one you want to change. The second row you mention has to be the new pivot row. Choose the multiplier so it cancels. If both rows are the same (you are trying to fix the pivot row), the only thing you do is divide the pivot row by whatever number is in the pivot position, so you get a 1. –  Jack Schmidt May 16 '11 at 1:02
    
In linear systems you have more flexibility, especially at the start. Row swaps, random row ops, etc. can make a problem easier. Towards the end of it (after REF and on the way to RREF), things get more tightly controlled. The simplex algorithm is the most restrictive because you are already in RREF, and one wrong move can break the RREF pivots. –  Jack Schmidt May 16 '11 at 1:03
    
Ah I see. So for example to change R1 and the pivot row is R2, I would use R1+5R2. And for R3, I'd use R3-4R2? And if I use this system, would it be guaranteed to work all the time? Thanks for all the help so far :) –  simplex May 16 '11 at 8:01

1 Answer 1

I'll assume you are using a nice full table that includes a P column and P row, where P is the objective function.

The critical thing is that to read a final answer from your tableau, you must always:

  • Ensure the tableau describes the system in a (pivoted) RREF
  • Ensure the right hand sides are all non-negative
  • Ensure the bottom row (the objective row) is all non-negative
  • Ensure that P is a basic variable

This means that at the end your table describes a linear system in which some of the variables are free and some (including P) are solved in terms of those. The first • ensures you can read the answers off easily. The second ensures that you can set the free variables to 0 without breaking the law. The third ensures that doing this is good for the objective, since those variables were just costing you profit anyways. The fourth is very important: you don't want to set profit = 0!


Here are some common mistakes I see:

Deciding which element becomes a pivot has some small amount of freedom in it, but you can choose a "wrong" pivot. This will break the second • point, or best case scenario, fail to make progress on the third • point.

Make sure that you only use the chosen pivot as your second row in the row operations. Otherwise you are likely to break the first • point (look in your tables and see if you still have the same number of 0-0-1-0 type columns after your row op shenanigans as before).

Technically you could use previous tableaux rows to alter things, but I think this is very likely to break the first • point.

One somewhat rare mistake I see with very creative row ops (that are legal in solving linear systems) is that people manage to swap P out of the basis. Sometimes this means they have a "2" as the pivot for P, and so the last row means 3x + 5y + 2P = 26. x and y are free and hurt profit, so set x=y=0, but then you have 2P=26 instead of P=26, and so maybe P=13 is the right answer (or maybe something is horribly wrong). Sometimes people end up with P a free variable. Then you are forced to set P=0! That is very rarely the most profitable move.


For example: Consider a simple company with two products and two resources. Both products make them a dollar each. The first product uses 1 resource of each type. The second product uses 2 of the first resource and none of the second. The company decides to make X units of the first product and Y units of the second. It has 100 units of both resources.

  • The profit is P = X + Y, or written linear style, (-1)X + (-1)Y + 0U + 1P = 0.
  • The first resource constraint is 1X + 2Y + U = 100, where U is the unused portion of the first resource.
  • The second resource constraint is 1X + 0Y + V = 100, where V is the unused portion of the second resource.
  • To be feasible, we must have X ≥ 0, Y ≥ 0, U ≥ 0, and V ≥ 0
  • To be optimal, we want P to be a maximum

The initial tableau is:

 X  Y  U  V  P  RHS
 1  2  1  0  0  100
 1  0  0  1  0  100
-1 -1  0  0  1    0

Currently our "basic" solution is feasible but not optimal: X=Y=0 are free, and U=100, V=100, and P=0 have pivots. Each row is a linear equation.

Both X and Y are profitable, so we can choose either to pivot (into the basis). Let's choose X since it is first alphabetically. We can choose either row as the pivot row, so let's choose the first as it is "owned" by U and U is first alphabetically. So we want R1 column 1 to be a "1", R2 column 1 to be a "0", R3 column 1 to be a "0".

Let's do it wrong(ly). For my first row operation, I will choose R3 + R2, instead of the correct R3+R1. I guess I'll also do the correct R2−R1, and the oh-so-easy "leave R1 alone".

Our next tableau is:

 X  Y  U  V  P  RHS
 1  2  1  0  0  100
 0 -2 -1  1  0    0    (wrong)
 0 -1  0  1  1    0

First column looks good. What's the big deal? Look at the V column. It used to be a nice RREF looking 0-1-0. Now it is all messy, 0-1-1. Is V a free variable now? If so who are the pivots? X has a pivot. P has a pivot. Nobody else. Uh oh. First • is broken.

Ok, so backtrack:

 X  Y  U  V  P  RHS
 1  2  1  0  0  100
 1  0  0  1  0  100
-1 -1  0  0  1    0

Now do the right row ops: R1 stays the same. R2 becomes R2−R1. R3 becomes R3+R1. We get:

 X  Y  U  V  P  RHS
 1  2  1  0  0  100
 0 -2 -1  1  0    0
 0  1  1  0  1  100

Now what do we see? Let's look at the basic solution: X, V, P have pivots, so we can solve for them X=100, V=0, P=100. Y,U are free, so we set them to 0. How much unused resources? U=0 of the first resource, and V=0 of the second. So efficient. How much do we produce? X=100 of the first product, and Y=0 of the second. So easy. How much money do we make? P=100. Sounds good.

Can we do better? No. Y+U+P=100. The bigger we make Y, the less room we have for profit. The bigger we make U, the less room we have for profit. The only reasonable thing is to set Y=U=0. Yay.

share|improve this answer
    
Thanks for the reply.. I think this might be the problem: "Make sure that you only use the chosen pivot as your second row in the row operations. Otherwise you are likely to break the first • point (look in your tables and see if you still have the same number of 0-0-1-0 type columns after your row op shenanigans as before)." Could you please elaborate on this? –  simplex May 16 '11 at 0:31
    
No problem. I worked out a silly example. Feel free to skip most of the text and just look at the tables. By using R2 instead of R1 to do the zero-ing, I managed to mess up V. –  Jack Schmidt May 16 '11 at 1:00
    
Thanks a lot for your help - greatly appreciated :) –  simplex May 16 '11 at 17:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.