234 CHAPTER 11. LINEAR PROGRAMMING

Such a column is the second to the last. The pivot is the 3. The new matrix is0 1 0 7

3 −1 0 13

13 0 2

31 0 0 1

3 0 0 13 − 2

3 0 83

0 0 1 −2 1 0 −1 0 0 10 0 0 − 1

3 0 0 − 13 − 1

3 1 13

0 0 0 113 −1 1 2

3 − 73 0 28

3

 . (11.15)

Now the obvious basic solution is feasible. You let x4 = 0= x5 = x7 = x8 and x1 = 8/3,x2 =2/3,x3 = 1, and x6 = 28/3. You don’t need to worry too much about this. It is the abovematrix which is desired. Now you can assemble the simplex tableau and begin the algo-rithm. Remember C≡ 2x1+3x2+2x3+3x4. First add the row and column which deal withC. This yields

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

3−2 −3 −2 −3 0 0 0 0 0 1 0

(11.16)

Now you do row operations to keep the simple columns of 11.15 simple in 11.16. Of courseyou could permute the columns if you wanted but this is not necessary.

This yields the following for a simplex tableau. Now it is a matter of getting rid of thepositive entries in the bottom row because you are trying to minimize.

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

The most positive of them is the 2/3 and so I will apply the algorithm to this one first. Thepivot is the 7/3. After doing the row operation the next tableau is

0 37 0 1 − 3

7 0 17

17 0 0 2

71 − 1

7 0 0 17 0 2

7 − 57 0 0 18

70 6

7 1 0 17 0 − 5

727 0 0 11

70 1

7 0 0 − 17 0 − 2

7 − 27 1 0 3

70 − 11

7 0 0 47 1 1

7 − 207 0 0 58

70 − 2

7 0 0 − 57 0 − 3

7 − 37 0 1 64

7

and you see that all the entries are negative and so the minimum is 64/7 and it occurs whenx1 = 18/7,x2 = 0,x3 = 11/7,x4 = 2/7.