[Math] Simplex Method row operations help

linear programming

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

Best Answer

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.

Related Question