236 CHAPTER 11. LINEAR PROGRAMMING

the single positive entry, 1/3. The next tableau is

5 3 2 1 0 −1 0 0 0 0 83 2 1 0 0 −1 0 1 0 0 114 7 5 0 1 −3 0 0 0 0 194 2 1 0 0 −1 0 0 1 0 44 1 0 0 0 −1 1 0 0 0 213 6 4 0 0 −3 0 0 0 1 24

.

There is a column consisting of all negative entries. There is therefore, no maximum. Notealso how there is no way to pick the pivot in that column.

Example 11.3.4 Minimize z = x1−3x2 + x3 subject to x1 + x2 + x3 ≤ 10,x1 + x2 + x3 ≥ 2,x1 + x2 +3x3 ≤ 8 and x1 +2x2 + x3 ≤ 7 with all variables nonnegative.

There exists an answer because the region defined by the constraints is closed andbounded. Adding in slack variables you get the following augmented matrix correspondingto the constraints. 

1 1 1 1 0 0 0 101 1 1 0 −1 0 0 21 1 3 0 0 1 0 81 2 1 0 0 0 1 7

Of course there is a problem with the obvious solution obtained by setting to zero all vari-ables corresponding to a nonsimple column because of the simple column which has the−1 in it. Therefore, I will use the simplex algorithm to make this column non simple. Thethird column has the 1 in the second row as the pivot so I will use this column. This yields

0 0 0 1 1 0 0 81 1 1 0 −1 0 0 2−2 −2 0 0 3 1 0 20 1 0 0 1 0 1 5

 (11.17)

and the obvious solution is feasible. Now it is time to assemble the simplex tableau. Firstadd in the bottom row and second to last column corresponding to the equation for z. Thisyields 

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 5−1 3 −1 0 0 0 0 1 0

Next you need to zero out the entries in the bottom row which are below one of the simple