11.5. DUALITY 243
whose augmented matrix is1 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