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.
z = (50)(20) + (0)(60) = 1000
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
c j - z j
The Completed Second Simplex Tableau
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.