11.3. THE SIMPLEX ALGORITHM 231

Recall this is the same as maximizing z = x1− x2 subject to

 1 2 1 0 01 2 0 −1 02 1 0 0 1



x1

x2

x3

x4

x5

=

 1026

 ,x≥ 0,

the variables, x3,x4,x5 being slack variables. Recall the simplex tableau was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

with the variables ordered as x2,x4,x5,x1,x3 and so xB = (x2,x4,x5) and

xF = (x1,x3) .

Apply the simplex algorithm to the fourth column because − 32 < 0 and this is the most

negative entry in the bottom row. The pivot is 3/2 because 1/(3/2) = 2/3 < 5/(1/2) .Dividing this row by 3/2 and then using this to zero out the other elements in that column,the new simplex tableau is

1 0 − 13 0 2

3 0 143

0 1 0 0 1 0 80 0 2

3 1 − 13 0 2

30 0 1 0 −1 1 −4

 .

Now there is still a negative number in the bottom left row. Therefore, the process shouldbe continued. This time the pivot is the 2/3 in the top of the column. Dividing the top rowby 2/3 and then using this to zero out the entries below it,

32 0 − 1

2 0 1 0 7− 3

2 1 12 0 0 0 1

12 0 1

2 1 0 0 332 0 1

2 0 0 1 3

 .

Now all the numbers on the bottom left row are nonnegative so the process stops. Nowrecall the variables and columns were ordered as x2,x4,x5,x1,x3. The solution in terms ofx1 and x2 is x2 = 0 and x1 = 3 and z = 3. Note that in the above, I did not worry aboutpermuting the columns to keep those which go with the basic variables on the left.

Here is a bucolic example.

Example 11.3.3 Consider the following table.