Ken Montgomery
EMAT 6690
MATHEMATICS
APPLIED IN INDUSTRY
Linear Programming: The Simplex Method of Optimization
Appendix: Row Operations
|
|
|
|
|
B |
|
2 |
4 |
1 |
0 |
0 |
36 |
|
3 |
1 |
0 |
1 |
0 |
36 |
|
5 |
2 |
0 |
0 |
1 |
30 |
|
-30 |
-20 |
0 |
0 |
0 |
0 |
|
Tableau 1
Beginning with Tableau 1, we identify the entering
column
as,
the departing row as
and the pivot
as 5. We then multiply the departing row by
to make the pivot
equal to 1, yielding Tableau 2.
|
|
|
|
|
b |
|
2 |
4 |
1 |
0 |
0 |
36 |
|
3 |
1 |
0 |
1 |
0 |
36 |
|
1 |
2/5 |
0 |
0 |
1/5 |
6 |
|
-30 |
-20 |
0 |
0 |
0 |
0 |
|
Tableau 2
We then multiply the departing row
by –2 and
add the departing row to therow,
which gives Tableau 3.
|
|
|
|
|
b |
|
0 |
16/5 |
1 |
0 |
-2/5 |
24 |
|
3 |
1 |
0 |
1 |
0 |
36 |
|
-2 |
-4/5 |
0 |
0 |
-2/5 |
-12 |
|
-30 |
-20 |
0 |
0 |
0 |
0 |
|
Tableau 3
We return the pivot to 1, by multiplying
the departing
row by in Tableau 4.
|
|
|
|
|
b |
|
0 |
16/5 |
1 |
0 |
-2/5 |
24 |
|
3 |
1 |
0 |
1 |
0 |
36 |
|
1 |
2/5 |
0 |
0 |
1/5 |
6 |
|
-30 |
-20 |
0 |
0 |
0 |
0 |
|
Tableau 4
We wish to have a zero in theentry
of the entering column, so we multiply
the departing row by –3 obtaining Tableau 5.
|
|
|
|
|
b |
|
0 |
16/5 |
1 |
0 |
-2/5 |
24 |
|
3 |
1 |
0 |
1 |
0 |
36 |
|
-3 |
-6/5 |
0 |
0 |
-3/5 |
-18 |
|
-30 |
-20 |
0 |
0 |
0 |
0 |
|
Tableau 5
Next, we add the departing row to
therow,
and then multiply the departing row by
yielding Tableau 6.
|
|
|
|
|
b |
|
0 |
16/5 |
1 |
0 |
-2/5 |
24 |
|
0 |
-1/5 |
0 |
1 |
-3/5 |
18 |
|
1 |
2/5 |
0 |
0 |
1/5 |
6 |
|
-30 |
-20 |
0 |
0 |
0 |
0 |
|
Tableau 6
We expect the z-value (the last row entry of the b-column) to increase as we change the –30 into 0. We accomplish this by multiplying the departing row by 30 and adding the departing row to the bottom row and thus obtain Tableau 7.
|
|
|
|
|
b |
|
0 |
16/5 |
1 |
0 |
-2/5 |
24 |
|
0 |
-1/5 |
0 |
1 |
-3/5 |
18 |
|
30 |
12 |
0 |
0 |
6 |
180 |
|
0 |
-8 |
0 |
0 |
6 |
180 |
|
Tableau 7
We then multiply the departing row
by to return the pivot
to 1 and we have a preliminary solution given by Tableau 8.
|
|
|
|
|
b |
|
0 |
16/5 |
1 |
0 |
-2/5 |
24 |
|
0 |
-1/5 |
0 |
1 |
-3/5 |
18 |
|
1 |
2/5 |
0 |
0 |
1/5 |
6 |
|
0 |
-8 |
0 |
0 |
6 |
180 |
|
Tableau 8
We next conduct another optimality check
and
determine the new entering column to be .
We calculate ratios of b to
for each row and determine the new pivot to be
.
Multiplying the new departing row by
changes our pivot
to 1 and yields Tableau 9.
|
|
|
|
|
b |
|
0 |
1 |
5/16 |
0 |
-1/8 |
15/2 |
|
0 |
-1/5 |
0 |
1 |
-3/5 |
18 |
|
1 |
2/5 |
0 |
0 |
1/5 |
6 |
|
0 |
-8 |
0 |
0 |
6 |
180 |
|
Tableau 9
We wish to change theentry
of the entering column to 0, so we multiply the departing
row by
obtaining
Tableau 10.
|
|
|
|
|
b |
|
0 |
1/5 |
1/16 |
0 |
-1/40 |
3/2 |
|
0 |
-1/5 |
0 |
1 |
-3/5 |
18 |
|
1 |
2/5 |
0 |
0 |
1/5 |
6 |
|
0 |
-8 |
0 |
0 |
6 |
180 |
|
Tableau 10
Further, we add the departing row
to therow
and then multiply the departing row by 5,
to return the pivot to 1, which gives Tableau 11.
|
|
|
|
|
b |
|
0 |
1 |
5/16 |
0 |
-1/8 |
15/2 |
|
0 |
0 |
1/16 |
1 |
-5/8 |
39/2 |
|
1 |
2/5 |
0 |
0 |
1/5 |
6 |
|
0 |
-8 |
0 |
0 |
6 |
180 |
|
Tableau 11
To change theentry
of the entering column to 0, we first
multiply the departing row by
which
yields Tableau 12.
|
|
|
|
|
b |
|
0 |
-2/5 |
-1/8 |
0 |
-1/20 |
-3 |
|
0 |
0 |
1/16 |
1 |
-5/8 |
39/2 |
|
1 |
2/5 |
0 |
0 |
1/5 |
6 |
|
0 |
-8 |
0 |
0 |
6 |
180 |
|
Tableau 12
By adding the departing row to therow
and then multiplying the departing row by
,
we obtain Tableau 13.
|
|
|
|
|
b |
|
0 |
1 |
5/16 |
0 |
-1/8 |
15/2 |
|
0 |
0 |
1/16 |
1 |
-5/8 |
39/2 |
|
1 |
0 |
-1/8 |
0 |
3/20 |
3 |
|
0 |
-8 |
0 |
0 |
6 |
180 |
|
Tableau 13
We prepare to change the bottom-row entry of the entering column (-8) to 0, by first multiplying the departing row by 8, yielding Tableau 14.
|
|
|
|
|
b |
|
0 |
8 |
5/2 |
0 |
-1 |
60 |
|
0 |
0 |
1/16 |
1 |
-5/8 |
39/2 |
|
1 |
0 |
-1/8 |
0 |
3/20 |
3 |
|
0 |
-8 |
0 |
0 |
6 |
180 |
|
Tableau 14
By adding the departing row to the
bottom row
and then multiplying the departing row by,
we obtain a better solution for z, given in Tableau
15.
|
|
|
|
|
b |
|
0 |
1 |
5/16 |
0 |
-1/8 |
15/2 |
|
0 |
0 |
1/16 |
1 |
-5/8 |
39/2 |
|
1 |
0 |
-1/8 |
0 |
3/20 |
3 |
|
0 |
0 |
5/2 |
0 |
5 |
240 |
|
Tableau 15
A final optimality check ensures that all of the entries on the bottom row are non-negative. The optimal solution is given by the below equation.
Substitution into the objective function verifies the optimal z-value.
Interestingly however, we also solve this problem graphically.
Return to EMAT 6690
.