Linear Programming Simplex Method Graphical Solution Appendix: Row Operations

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.