11.3. THE SIMPLEX ALGORITHM 233

0 7

535

145 −1 1

5 0 0 0 175

1 35

25

15 0 − 1

5 0 0 0 85

0 75

85

45 0 1

5 −1 0 0 225

0 − 15

15

35 0 2

5 0 −1 0 195

0 25

35

45 0 1

5 0 0 −1 125

Now go to the second column. The pivot in this column is the 7/5. This is in a differentrow than the pivot in the first column so I will use it to zero out everything below it. Thiswill get rid of the zeros in the fifth column and introduce zeros in the second. This yields

0 1 37 2 − 5

717 0 0 0 17

71 0 1

7 −1 37 − 2

7 0 0 0 17

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

7 1 − 17

37 0 −1 0 30

70 0 3

7 0 27

17 0 0 −1 10

7

Now consider another column, this time the fourth. I will pick this one because it hassome negative numbers in it so there are fewer entries to check in looking for a pivot.Unfortunately, the pivot is the top 2 and I don’t want to pivot on this because it woulddestroy the zeros in the second column. Consider the fifth column. It is also not a goodchoice because the pivot is the second element from the top and this would destroy thezeros in the first column. Consider the sixth column. I can use either of the two bottomentries as the pivot. The matrix is

0 1 0 2 −1 0 0 0 1 11 0 1 −1 1 0 0 0 −2 30 0 1 −2 1 0 −1 0 0 10 0 −1 1 −1 0 0 −1 3 00 0 3 0 2 1 0 0 −7 10

Next consider the third column. The pivot is the 1 in the third row. This yields

0 1 0 2 −1 0 0 0 1 11 0 0 1 0 0 1 0 −2 20 0 1 −2 1 0 −1 0 0 10 0 0 −1 0 0 −1 −1 3 10 0 0 6 −1 1 3 0 −7 7

 .

There are still 5 columns which consist entirely of zeros except for one entry. Four of themhave that entry equal to 1 but one still has a -1 in it, the -1 being in the fourth column. Ineed to do the row operations on a nonsimple column which has the pivot in the fourth row.