X hits on this document

378 views

0 shares

0 downloads

0 comments

14 / 63

A-14

Module A

The Simplex Solution Method

TIME OUT for George B. Dantzig

After developing the simplex method for solving linear pro- gramming problems, George Dantzig needed a good problem to test it on. The problem he selected was the “diet problem” formulated in 1945 by Nobel economist George Stigler. This problem was to determine an adequate nutritional diet at min- imum cost (which was an important military and civilian issue during World War II). Formulated as a linear programming

model, the diet problem consisted of 77 unknowns and 9 equa- tions. It took 9 clerks using hand-operated (mechanical) desk calculators 120 man-days to obtain the optimal simplex solu- tion: a diet consisting primarily of wheat flour, cabbage, and dried navy beans that cost $39.69 per year (in 1939 prices). The solution developed by Stigler using his own numerical method was only 24 cents more than the optimal solution.

Column Quantity

z = (50)(20) + (0)(60) = 1000

j

x x s s

1 2 1 2

z = (50)(1>2) + (0)(5>2) = 25 z = (50)(1) + (0)(0) = 50 z = (50)(1>2) + (0)(-3>2) = 25 z = (50)(0) + (0)(1) = 0

1 2 3 4

T h e r o w v a l u e s a n d t h e r o w v a l u e s a r e a d d e d t o t h e t a b l e a u t o g i v e t h e c o m - p l e t e d s e c o n d s i m p l e x t a b l e a u s h o w n i n T a b l e A - 1 3 . T h e v a l u e o f 1 , 0 0 0 i n t h e r o w i s t h e z j c j - value of the objective function (profit) for this basic feasible solution. z j z j

50 0

x s2

2

20 60

1/2 5/2

1 0

1/2 -3/2

0 1

z

j

1,000

25

50

25

0

c j - z j

15

0

  • -

    25

0

Basic

40

50

0

0

Variables

Quantity

x1

x2

s1

s2

Table A-13

The Completed Second Simplex Tableau

c j

Each tableau is the same as performing row operations for a set of simultaneous equations.

The computational steps that we followed to derive the second tableau in effect accom- plish the same thing as row operations in the solution of simultaneous equations. These same steps are used to derive each subsequent tableau, called iterations.

The Optimal Simplex Tableau The steps that we followed to derive the second simplex tableau are repeated to develop the third tableau. First, the pivot column or entering basic variable is determined. Because 15 i n t h e r o w r e p r e s e n t s t h e g r e a t e s t p o s i t i v e n e t i n c r e a s e i n p r o f i t , b e c o m e s t h e x 1 c j - entering nonbasic variable. Dividing the pivot column values into the values in the quantity column indicates that s2 is the leaving basic variable and corresponds to the pivot row. The pivot row, pivot column, and pivot number are indicated in Table A-14. z j

At this point you might be wondering why the net increase in profit per bowl (x1) is $15 rather than the original profit of $40. It is because the production of bowls (x1) will require some of the resources previously used to produce mugs (x2) only. Producing some bowls means not producing as many mugs; thus, we are giving up some of the profit gained from producing mugs to gain even more by producing bowls. This difference is the net increase of $15.

Document info
Document views378
Page views378
Page last viewedMon Dec 05 13:36:39 UTC 2016
Pages63
Paragraphs3770
Words30893

Comments