9.4 THE SIMPLEX METHOD: MINIMIZATION

1 SECTION SIMPLEX METHOD: MINIMIZATION50932. The accounting firm in Exercise 31 raises its charge for anaudit to $2500. What number of audits and tax returns willbring in a maximum revenue?In the SIMPLEX method, it may happen that in selecting the departingvariable all the calculated ratios are negative. This indicates an un-bounded solution. Demonstrate this in Exercises 33 and (Maximize)34.(Maximize)Objective function:Objective function:Constraints:Constraints:If the SIMPLEX method terminates and one or more variables not inthe final basishave bottom-row entries of zero, bringing these variables into the basis will determine other optimal this in Exercises 35 and , x2 $ 50x1, x2 $ 022x11x2 # 502x112x2 # 4 2x11x2 # 202x123x2 # 1z5x113x2z5x112x235.

2 (Maximize)36.(Maximize)Objective function:Objective function:Constraints: a computer to maximize the objective functionsubject to the a computer to maximize the objective functionsubject to the same set of constraints given in Exercise , x2, x3, x4 $ # # # 65z52x117x216x314x4x1, x2 $ 30x1, x2 $ 102x113x2 # 355x112x2 # 102x113x2 # 203x115x2 # THE SIMPLEX METHOD: MINIMIZATIONIn Section , we applied the SIMPLEX method only to linear programming problems instandard form where the objective function was to be maximized. In this section, we extendthis procedure to linear programming problems in which the objective function is to be MINIMIZATION problem is in standard formif the objective function is to be minimized, subject to the constraintswhere The basic procedure used to solve such a problem is to convert itto a maximization problemin standard form, and then apply the SIMPLEX method as dis-cussed in Section Example 5 in Section , we used geometric methods to solve the following MINIMIZATION $ 0 and bi $ 0.

3 Am1x11am2x21..1amnxn $ a21x11a22x21..1a2nxn $ b2 a11x11a12x21..1a1nxn $ b11..1cnxnc1x11c2x2w5 CCMinimization problem : Find the minimum value ofObjective functionsubject to the following constraintsConstraintswhere The first step in converting this problem to a maximization prob-lem is to form the augmented matrix for this system of inequalities. To this augmentedmatrix we add a last row that represents the coefficients of the objective function, as , we form the transposeof this matrix by interchanging its rows and that the rows of this matrix are the columns of the first matrix, and vice versa. Finally,we interpret the new matrix as a maximizationproblem as follows. (To do this, we intro-duce new variables, y1, y2, and y3.)

4 We call this corresponding maximization problem thedual of the original MINIMIZATION Maximization problem :Find the maximum value ofDual objective functionsubject to the constraintswhere As it turns out, the solution of the original MINIMIZATION problem can be found by applying the SIMPLEX method to the new dual problem , as $ 0, y2 $ 0, and y3 $ # # ..300126..361030..04601210..3003690..0x1 $ 0 and x2 $ $ 39012x1166x2 $ 33660x1160x2 $ 9 LINEAR PROGRAMMING}}Dual 0 EnteringBasicy1y2y3s1s2bVariables10y10 620 11s2 Departing024 4050 EnteringBasicy1y2y3s1s2bVariables10y101y 3012 0 32 x1x2 Thus, the solution of the dual maximization problem is This is the samevalue we obtained in the MINIMIZATION problem given in Example 5, in Section The x-values corresponding to this optimal solution are obtained from the entries in the bottomrow corresponding to slack variable columns.

5 In other words, the optimal solution occurswhen The fact that a dual maximization problem has the same solution as its original MINIMIZATION problem is stated formally in a result called the von Neumann DualityPrinciple, after the American mathematician John von Neumann (1903 1957).Solving a MINIMIZATION ProblemWe summarize the steps used to solve a MINIMIZATION problem as and SIMPLEX METHOD: MINIMIZATION511 Theorem von NeumannDuality PrincipleThe objective value wof a MINIMIZATION problem in standard form has a minimum valueif and only if the objective value zof the dual maximization problem has a maximumvalue. Moreover, the minimum value of wis equal to the maximum value of 9 LINEAR PROGRAMMINGS olving a MinimizationProblemA MINIMIZATION problem is in standard form if the objective function is to be minimized, subject to the constraintswhere To solve this problem we use the following Form the augmented matrixfor the given system of inequalities, and add a bottomrow consisting of the coefficients of the objective Form the transposeof this Form the dual maximization problemcorresponding to this transposed matrix.

6 Thatis, find the maximum of the objective function given by subject to the constraintswhere 4. Apply the SIMPLEX methodto the dual maximization problem . The maximum valueof zwill be the minimum value of w. Moreover, the values of x1, x2, .. , and xnwilloccur in the bottom row of the final SIMPLEX tableau, in the columns correspondingto the slack $ 0, y2 $ 0, .. , and ym $ y21..1amnym # y21..1am2 ym # c2a11y11a21y21..1am1ym # c11bmymz5b1y11b2y21..a11a12a1n..b1a21a22 a2n..b2..am1am2amn..0a11a21am1..c1a12a22 am2..c2..a1na2namn..0xi $ 0 and bi $ ..1amnxn $ ..1a2nxn $ b2a11x11a12x21..1a1nxn $ b11..1cnxnw5c1x11c2x2We illustrate the steps used to solve a MINIMIZATION problem in Examples 1 and 1 Solving a MINIMIZATION ProblemFind the minimum value ofObjective functionsubject to the constraintswhere SolutionThe augmented matrix corresponding to this MINIMIZATION problem isThus, the matrix corresponding to the dual maximization problem is given by the follow-ing implies that the dual maximization problem is as Maximization problem : Find the maximum value ofDual objective functionsubject to the constraintswhere We now apply the SIMPLEX method to the dual problem as Departing11012s2000 Entering2426y1 $ 0 and y2 $ # 22y11y2 # 3z56y114y2321.

7 611..311.. $ 0 and x2 $ $ 42x11x2 $ 6w53x112x2 SECTION SIMPLEX METHOD: MINIMIZATION513}Constraints}Dual constraintsBasicy1y2s1s2bVariables10y101 s2 Departing0309 EnteringBasicy1y2s1s2bVariables10 11y1012 1y200 2210 x1x2 From this final SIMPLEX tableau, we see that the maximum value of zis 10. Therefore, thesolution of the original MINIMIZATION problem isMinimum Valueand this occurs whenBoth the MINIMIZATION and the maximization linear programming problems in Example1 could have been solved with a graphical method, as indicated in Figure Note inFigure (a) that the maximum value of z56y124y2is the same as the minimum valueof as shown in Figure (b). (See page 515.)EXAMPLE 2 Solving a MINIMIZATION ProblemFind the minimum value ofObjective functionsubject to the constraintsConstraintswhere x1 $ 0, x2 $ 0, and x3 $ $ 42x112x212x3 $ 82x112x212x3 $ 6w52x1110x218x3w53x112x2,x152 and 9 LINEAR PROGRAMMING}SolutionThe augmented matrix corresponding to this MINIMIZATION problem isThus, the matrix corresponding to the dual maximization problem is given by the follow-ing implies that the dual maximization problem is as Maximization problem .

8 Find the maximum value ofDual objective functionsubject to the constraintsDual constraintswhere We now apply the SIMPLEX method to the dual problem as 2s111201010s2122001 8s3 Departing000 0 EnteringBasicy1y2y3s1s2s3bVariables10100 2s1 Departing01 0 16s211 0 04y204 0 0 432 Entering221212212122124282621y1 $ 0, y2 $ 0, and y3 $ # 18y112y212y3 # 10y112x222y3 # 12z56y118y214y3111..6012..82122..0 1021..2112..10122..0 .SECTION SIMPLEX METHOD: MINIMIZATION515 Figure y1y2 Maximum:z= 6y1+ 4y2= 10(1, 1)(0, 2)(0, 0), 0322331(((a)x1x2 Minimum:w= 3x1+ 2x2= 10(0, 6)(2, 2)(4, 0)1123562456(b)}Basicy1y2y3s1s2s3bVariab les10100 2y10015s20103y200220436 x1x2x3 From this final SIMPLEX tableau, we see that the maximum value of zis 36.))

9 Therefore, thesolution of the original MINIMIZATION problem isMinimum Valueand this occurs whenApplicationsEXAMPLE 3A Business Application: Minimum CostA small petroleum company owns two refineries. Refinery 1 costs $20,000 per day to operate, and it can produce 400 barrels of high-grade oil, 300 barrels of medium-grade oil,and 200 barrels of low-grade oil each day. Refinery 2 is newer and more modern. It costs$25,000 per day to operate, and it can produce 300 barrels of high-grade oil, 400 barrels ofmedium-grade oil, and 500 barrels of low-grade oil each company has orders totaling 25,000 barrels of high-grade oil, 27,000 barrels ofmedium-grade oil, and 30,000 barrels of low-grade oil. How many days should it run eachrefinery to minimize its costs and still refine enough oil to meet its orders?

10 SolutionTo begin, we let and represent the number of days the two refineries are the total cost is given byObjective functionThe constraints are given by(High-grade)(Medium-grade)Constraints( Low-grade)where The augmented matrix corresponding to this MINIMIZATION problem isx1 $ 0 and x2 $ $ 30,000300x11400x2 $ 27,000400x11300x2 $ 25,000C520,000x1125, , x250, and 9 LINEAR PROGRAMMING}The matrix corresponding to the dual maximization problem isWe now apply the SIMPLEX method to the dual problem as ,000s13004005000125,000s2 Departing000 EnteringBasicy1y2y3s1s2bVariables2801400 110,000s1 Departing1050y300601,500,000 EnteringBasicy1y2y3s1s2bVariables10y101y 30500025501,750,000 x1x2 From the third SIMPLEX tableau, we see that the solution to the original MINIMIZATION problem is200713502314001225072170012801223,0002 7,00015004535225230,000227,000225,000340 0300.