11.3. THE SIMPLEX ALGORITHM 237

columns in 11.17. This yields the simplex tableau0 0 0 1 1 0 0 0 81 1 1 0 −1 0 0 0 2−2 −2 0 0 3 1 0 0 20 1 0 0 1 0 1 0 50 4 0 0 −1 0 0 1 2

 .

The desire is to minimize this so you need to get rid of the positive entries in the left bottomrow. There is only one such entry, the 4. In that column the pivot is the 1 in the second rowof this column. Thus the next tableau is

0 0 0 1 1 0 0 0 81 1 1 0 −1 0 0 0 20 0 2 0 1 1 0 0 6−1 0 −1 0 2 0 1 0 3−4 0 −4 0 3 0 0 1 −6

There is still a positive number there, the 3. The pivot in this column is the 2. Apply thealgorithm again. This yields

12 0 1

2 1 0 0 − 12 0 13

212 1 1

2 0 0 0 12 0 7

212 0 5

2 0 0 1 − 12 0 9

2− 1

2 0 − 12 0 1 0 1

2 0 32

− 52 0 − 5

2 0 0 0 − 32 1 − 21

2

 .

Now all the entries in the left bottom row are nonpositive so the process has stopped. Theminimum is −21/2. It occurs when x1 = 0, x2 = 7/2,x3 = 0.

Now consider the same problem but change the word, minimize to the word, maximize.

Example 11.3.5 Maximize z = x1 − 3x2 + x3 subject to the constraints x1 + x2 + x3 ≤10,x1 + x2 + x3 ≥ 2, x1 + x2 + 3x3 ≤ 8 and x1 + 2x2 + x3 ≤ 7 with all variables nonneg-ative.

The first part of it is the same. You wind up with the same simplex tableau,0 0 0 1 1 0 0 0 81 1 1 0 −1 0 0 0 2−2 −2 0 0 3 1 0 0 20 1 0 0 1 0 1 0 50 4 0 0 −1 0 0 1 2

but this time, you apply the algorithm to get rid of the negative entries in the left bottom