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.


Return to EMAT 6690

 

.