9.3 THE SIMPLEX METHOD: MAXIMIZATION

1 THE SIMPLEX METHOD: MAXIMIZATIONFor linear programming problems involving two variables, the graphical solution methodintroduced in Section is convenient. However, for problems involving more than twovariables or problems involving a large number of constraints, it is better to use solutionmethods that are adaptable to computers. One such method is called the SIMPLEX method,developed by George Dantzig in 1946. It provides us with a systematic way of examiningthe vertices of the feasible region to determine the optimal value of the objective introduce this method with an we want to find the maximum value of where and subject to the following the left-hand side of each inequalityis less than or equal to the right-hand side, theremust exist nonnegative numbers and that can be added to the left side of each equa-tion to produce the following system of linear numbers and are called slack variablesbecause they take up the slack ineach , s22x115x21s11s21s35902x115x21s11s21s3527 2x115x21s11s21s3511s3s1, s22x115x2 # 902x115x2 # 272x115x2 # 11x2$0,x1 $ 0z54x116x2,494 CHAPTER 9 LINEAR PROGRAMMINGS tandard Form of a Linear ProgrammingProblemA linear programming problem is in standard formif it seeks to maximize the objec-tive function subject to the and After adding slack variables.

2 The corresponding system of constraint equations si $ ..1amnxn 1sm5bma21x11a22x21..1a2nxn 1s2 5b2a11x11a12x21..1a1nxn1s1 5b1bi $ $ 0am1x11am2x2 1..1amnxn # bma21x11a22x21..1a2nxn # b2a11x11a12x21..1a1nxn # b1z5c1x11c2x21..1cnxnREMARK: Note that for a linear programming problem in standard form, the objectivefunction is to be maximized, not minimized. (Minimization problems will be discussed inSections and )Abasic solutionof a linear programming problem in standard form is a solutionof the constraint equations in which at most mvariables arenonzero the variables that are nonzero are called basic basic solution forwhich all variables are nonnegative is called a basic feasible SIMPLEX TableauThe SIMPLEX method is carried out by performing elementary row operations on a matrixthat we call the SIMPLEX tableau consists of the augmented matrix corre-sponding to the constraint equations together with the coefficients of the objective functionwritten in the formIn the tableau, it is customary to omit the coefficient of z.

3 For instance, the SIMPLEX tableaufor the linear programming problemObjective functionis as Current z valueFor this initial SIMPLEX tableau,the basic variables are and and the nonbasicvariables (which have a value of zero) are and . Hence, from the two columns that arefarthest to the right, we see that the current solution isandThis solution is a basic feasible solution and is often written assx1, x2, s1, s2, s3d5s0, 0, 11, 27, , x250, s1511, s2527,x2x1s3,s1, s2,2624212x115x21s11s21s35902x115x21s11s 21s35272x115x21s11s21s3511z54x116x22c1x1 2c2x2 2..2cnxn1s0ds11s0ds21.. , x2, .. , xn, s1, s2, .. , smdSECTION SIMPLEX METHOD: MAXIMIZATION495} ConstraintsThe entry in the lower right corner of the SIMPLEX tableau is the current value of z. Notethat the bottom row entries underandare the negatives of the coefficients ofandin the objective functionTo perform an optimality checkfor a solution represented by a SIMPLEX tableau, we lookat the entries in the bottom row of the tableau.

4 If any of these entries are negative (asabove), then the current solution is not we have set up the initial SIMPLEX tableau for a linear programming problem , the sim-plex method consists of checking for optimality and then, if the current solution is not op-timal, improving the current solution. (An improved solution is one that has a larger z-valuethan the current solution.) To improve the current solution, we bring a new basic variableinto the solution we call this variable the entering implies that one of thecurrent basic variables must leave, otherwise we would have too many variables for a basicsolution we call this variable the departing choose the entering and departing variables as The entering variable corresponds to the smallest (the most negative) entry in thebottom row of the The departing variable corresponds to the smallest nonnegative ratio of , in thecolumn determined by the entering The entry in the SIMPLEX tableau in the entering variable s column and the departingvariable s row is called the , to form the improved solution, we apply Gauss-Jordan elimination to the columnthat contains the pivot, as illustrated in the following example.

5 (This process is called pivoting.)EXAMPLE 1 Pivoting to Find an Improved SolutionUse the SIMPLEX method to find an improved solution for the linear programming problemrepresented by the following objective function for this problem is 9 LINEAR PROGRAMMINGS olutionNote that the current solution corresponds toa z value of 0. To improve this solution, we determine that is the entering variable, because is the smallest entry in the bottom EnteringTo see whywe choose as the entering variable, remember that Hence, itappears that a unit change in produces a change of 6 in z, whereas a unit change in produces a change of only 4 in find the departing variable, we locate the s that have corresponding positive elementsin the entering variables column and form the following the smallest positive ratio is 11, so we choose as the departing Departing1101027s22500190s30000 EnteringNote that the pivot is the entry in the first row and second column.

6 Now, we use Gauss-Jordan elimination to obtain the following improved PivotingAfter PivotingThe new tableau now appears as , 271527, , x250, s1511, s2527, s3590dSECTION SIMPLEX METHOD: MAXIMIZATION497 Basicx1x2s1s2s3bVariables110011x2201016s 2700135s3060066 Note that has replaced in the basis column and the improved solutionhas a z-value ofIn Example 1 the improved solution is not yet optimal since the bottom row still has anegative entry. Thus, we can apply another iteration of the SIMPLEX method to further im-prove our solution as follows. We choose as the entering variable. Moreover, the small-est nonnegative ratio of andis 5, so is the departing variable. Gauss-Jordan elimination produces the , the new SIMPLEX tableau is as this tableau, there is still a negative entry in the bottom row. Thus, we choose as theentering variable and as the departing variable, as shown in the following , 16y258, , x2, s1, s2, s3d5s0, 11, 0, 16, 35ds1x2210252121498 CHAPTER 9 LINEAR PROGRAMMINGB asicx1x2s1s2s3bVariables01016x20016s2 Departing1005x1000116 EnteringBy performing one more iteration of the SIMPLEX method, we obtain the following tableau.

7 (Try checking this.)Basicx1x2s1s2s3bVariables01012x200 114s110015x1000132 Maximum z-valueIn this tableau, there are no negative elements in the bottom row. We have therefore deter-mined the optimal solution to bewithREMARK: Ties may occur in choosing entering and/or departing variables. Should thishappen, any choice among the tied variables may be the linear programming problem in Example 1 involved only two decision vari-ables, we could have used a graphical solution technique, as we did in Example 2, Notice in Figure that each iteration in the SIMPLEX method corresponds to movingfrom a given vertex to an adjacent vertex with an improved SIMPLEX MethodWe summarize the steps involved in the SIMPLEX method as , 12ds5, 16ds0, 11ds0, , x2, s1, s2, s3d5s15, 12, 14, 0, 0d23832135322373132231072871725722737172 7 SECTION SIMPLEX METHOD: MAXIMIZATION499 Figure (0, 0)(0, 11)(5, 16)(15, 12)(27, 0)Note that the basic feasible solution of an initial SIMPLEX tableau is This solution is basic because at most m variables are nonzero (namely the slack variables).

8 It is feasible because each variable is the next two examples, we illustrate the use of the SIMPLEX method to solve a problem involving three decision 2 The SIMPLEX Method with Three Decision VariablesUse the SIMPLEX method to find the maximum value ofObjective functionsubject to the constraintswhereand SolutionUsing the basic feasible solutionthe initial SIMPLEX tableau for this problem is as follows. (Try checking these computations,and note the tie that occurs when choosing the first entering variable.)sx1, x2, x3, s1, s2, s3d5s0, 0, 0, 10, 20, 5dx3 $ $ 0, x2 $ 0, 2x112x212x3 # 252x112x222x3 # 202x112x222x3 # 10z52x12x212x3sx1, x2, .. , xn, s1, s2, .. , smd5s0, 0, .. , 0, b1, b2, .. , 9 LINEAR PROGRAMMINGThe SIMPLEX Method(Standard Form)To solve a linear programming problem in standard form, use the following Convert each inequality in the set of constraints to an equation by adding slack Create the initial SIMPLEX Locate the most negative entry in the bottom row.

9 The column for this entry is calledthe entering column.(If ties occur, any of the tied entries can be used to determinethe entering column.)4. Form the ratios of the entries in the b-column with their corresponding positive entries in the entering column. The departing rowcorresponds to the smallest non-negative ratio (If all entries in the entering column are 0 or negative, then thereis no maximum solution. For ties, choose either entry.) The entry in the departing rowand the entering column is called the Use elementary row operations so that the pivot is 1, and all other entries in the entering column are 0. This process is called If all entries in the bottom row are zero or positive, this is the final tableau. If not, goback to Step If you obtain a final tableau, then the linear programming problem has a maximumsolution, which is given by the entry in the lower-right corner of the.

10 Basicx1x2x3s1s2s3bVariables21010010s1120 1020s201200 15s3 Departing10000 EnteringBasicx1x2x3s1s2s3bVariables21010 010s1 Departing13001125s20100x3200015 EnteringBasicx1x2x3s1s2s3bVariables10005 x1001120s20100x303010115 This implies that the optimal solution isand the maximum value of zis , the constraints in a linear programming problem will include an such cases, we still add a slack variable called an artificial variableto form the ini-tial SIMPLEX tableau. Technically, this new variable is not a slack variable (because there isno slack to be taken). Once you have determined an optimal solution in such a problem ,you should check to see that any equations given in the original constraints are 3 illustrates such a 3 The SIMPLEX Method with Three Decision VariablesUse the SIMPLEX method to find the maximum value ofObjective functionz53x112x21x3sx1, x2, x3, s1, s2, s3d5s5, 0, 52, 0, 20, 0d52121221252121222521212222222 SECTION SIMPLEX METHOD: MAXIMIZATION501subject to the constraintswhereand SolutionUsing the basic feasible solutionthe initial SIMPLEX tableau for this problem is as follows.