11.5. DUALITY 243

whose augmented matrix is1 5 1 2 1 1 0 0 0 22 3 2 1 1 0 1 0 0 31 2 2 1 1 0 0 1 0 23 1 1 1 1 0 0 0 1 3

Now the obvious solution is feasible so there is no hunting for an initial obvious feasiblesolution required. Now add in the row and column for w. This yields

1 5 1 2 1 1 0 0 0 0 22 3 2 1 1 0 1 0 0 0 31 2 2 1 1 0 0 1 0 0 23 1 1 1 1 0 0 0 1 0 3−5 −8 −6 −7 −4 0 0 0 0 1 0

 .

It is a maximization problem so you want to eliminate the negatives in the bottom left row.Pick the column having the one which is most negative, the −8. The pivot is the top 5.Then apply the simplex algorithm to obtain

15 1 1

525

15

15 0 0 0 0 2

575 0 7

5 − 15

25 − 3

5 1 0 0 0 95

35 0 8

515

35 − 2

5 0 1 0 0 65

145 0 4

535

45 − 1

5 0 0 1 0 135

− 175 0 − 22

5 − 195 − 12

585 0 0 0 1 16

5

 .

There are still negative entries in the bottom left row. Do the simplex algorithm to thecolumn which has the − 22

5 . The pivot is the 85 . This yields

18 1 0 3

818

14 0 − 1

8 0 0 14

78 0 0 − 3

8 − 18 − 1

4 1 − 78 0 0 3

438 0 1 1

838 − 1

4 0 58 0 0 3

452 0 0 1

212 0 0 − 1

2 1 0 2− 7

4 0 0 − 134 − 3

412 0 11

4 0 1 132

and there are still negative numbers. Pick the column which has the −13/4. The pivot isthe 3/8 in the top. This yields

13

83 0 1 1

323 0 − 1

3 0 0 23

1 1 0 0 0 0 1 −1 0 0 113 − 1

3 1 0 13 − 1

3 0 23 0 0 2

373 − 4

3 0 0 13 − 1

3 0 − 13 1 0 5

3− 2

3263 0 0 1

383 0 5

3 0 1 263

which has only one negative entry on the bottom left. The pivot for this first column is the