11.3. THE SIMPLEX ALGORITHM 235
There is no maximum for the above problem. However, I will pretend I don’t know thisand attempt to use the simplex algorithm. You set up the simiplex tableau the same way.Recall it is
0 1 0 73 −1 0 1
313 0 0 2
31 0 0 1
3 0 0 13 − 2
3 0 0 83
0 0 1 −2 1 0 −1 0 0 0 10 0 0 − 1
3 0 0 − 13 − 1
3 1 0 13
0 0 0 113 −1 1 2
3 − 73 0 0 28
30 0 0 2
3 −1 0 − 13 − 1
3 0 1 283
Now to maximize, you try to get rid of the negative entries in the bottom left row. The
most negative entry is the -1 in the fifth column. The pivot is the 1 in the third row of thiscolumn. The new tableau is
0 1 1 13 0 0 − 2
313 0 0 5
31 0 0 1
3 0 0 13 − 2
3 0 0 83
0 0 1 −2 1 0 −1 0 0 0 10 0 0 − 1
3 0 0 − 13 − 1
3 1 0 13
0 0 1 53 0 1 − 1
3 − 73 0 0 31
30 0 1 − 4
3 0 0 − 43 − 1
3 0 1 313
.
Consider the fourth column. The pivot is the top 1/3. The new tableau is
0 3 3 1 0 0 −2 1 0 0 51 −1 −1 0 0 0 1 −1 0 0 10 6 7 0 1 0 −5 2 0 0 110 1 1 0 0 0 −1 0 1 0 20 −5 −4 0 0 1 3 −4 0 0 20 4 5 0 0 0 −4 1 0 1 17
There is still a negative in the bottom, the -4. The pivot in that column is the 3. Thealgorithm yields
0 − 13
13 1 0 2
3 0 − 53 0 0 19
31 2
313 0 0 − 1
3 0 13 0 0 1
30 − 7
313 0 1 5
3 0 − 143 0 0 43
30 − 2
3 − 13 0 0 1
3 0 − 43 1 0 8
30 − 5
3 − 43 0 0 1
3 1 − 43 0 0 2
30 − 8
3 − 13 0 0 4
3 0 − 133 0 1 59
3
Note how z keeps getting larger. Consider the column having the −13/3 in it. The pivot is