226 CHAPTER 11. LINEAR PROGRAMMING

to finally obtain 1 0 0 1

212 0 5

0 1 0 0 1 0 80 0 1 3

2 − 12 0 1

0 0 0 − 32 − 1

2 1 −5

and this is a simplex tableau. The variables are x2,x4,x5,x1,x3,z.

It isn’t as hard as it may appear from the above. Lets not permute the variables andsimply find an acceptable simplex tableau as described above.

Example 11.2.3 Consider z = x1−x2 subject to the constraints, x1 +2x2 ≤ 10,x1 +2x2 ≥2, and 2x1 + x2 ≤ 6,xi ≥ 0. Find a simplex tableau.

Adding in slack variables, an augmented matrix which is descriptive of the constraintsis  1 2 1 0 0 10

1 2 0 −1 0 62 1 0 0 1 6

The obvious solution is not feasible because of that -1 in the fourth column. When you letx1,x2 = 0, you end up having x4 =−6 which is negative. Consider the second column andselect the 2 as a pivot to zero out that which is above and below the 2. 0 0 1 1 0 4

12 1 0 − 1

2 0 332 0 0 1

2 1 3

This one is good. When you let x1 = x4 = 0, you find that x2 = 3,x3 = 4,x5 = 3. Theobvious solution is now feasible. You can now assemble the simplex tableau. The first stepis to include a column and row for z. This yields

0 0 1 1 0 0 412 1 0 − 1

2 0 0 332 0 0 1

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

Now you need to get zeros in the right places so the simple columns will be preserved assimple columns in this larger matrix. This means you need to zero out the 1 in the thirdcolumn on the bottom. A simplex tableau is now

0 0 1 1 0 0 412 1 0 − 1

2 0 0 332 0 0 1

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

 .

Note it is not the same one obtained earlier. There is no reason a simplex tableau shouldbe unique. In fact, it follows from the above general description that you have one for eachbasic feasible point of the region determined by the constraints.