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 the
row,
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 the
entry
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
the
row,
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 the
entry
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 the
row
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 the
entry
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 the
row
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
.