11.3. THE SIMPLEX ALGORITHM 229

Obviously the obvious solution is not feasible. It results in x3 < 0. We need to exchangebasic variables. Lets just try something. 1 1 −1 0 0 1

0 −1 2 1 0 40 1 1 0 1 5

Now this one is all right because the obvious solution is feasible. Letting x2 = x3 = 0,it follows that the obvious solution is feasible. Now we add in the objective function asdescribed above. 

1 1 −1 0 0 0 10 −1 2 1 0 0 40 1 1 0 1 0 5−2 −3 0 0 0 1 0

Then do row operations to leave the simple columns the same. Then

1 1 −1 0 0 0 10 −1 2 1 0 0 40 1 1 0 1 0 50 −1 −2 0 0 1 2

Now there are negative numbers on the bottom row to the left of the 1. Lets pick the first.(It would be more sensible to pick the second.) The ratios to look at are 5/1,1/1 so pick forthe pivot the 1 in the second column and first row. This will leave the right column abovethe lower right corner nonnegative. Thus the next tableau is

1 1 −1 0 0 0 11 0 1 1 0 0 5−1 0 2 0 1 0 41 0 −3 0 0 1 3

There is still a negative number there to the left of the 1 in the bottom row. The new ratiosare 4/2,5/1 so the new pivot is the 2 in the third column. Thus the next tableau is

12 1 0 0 1

2 0 332 0 0 1 − 1

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

2 0 0 0 32 1 9

Still, there is a negative number in the bottom row to the left of the 1 so the process doesnot stop yet. The ratios are 3/(3/2) and 3/(1/2) and so the new pivot is that 3/2 in thefirst column. Thus the new tableau is

0 1 0 − 13

23 0 2

32 0 0 1 − 1

2 0 30 0 2 2

323 0 6

0 0 0 13

43 1 10

