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.

2 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, the corresponding system of constraint equations si $ ..1amnxn 1sm5bma21x11a22x21..1a2nxn 1s2 5b2a11x11a12x21..1a1nxn1s1 5b1bi $ $ 0am1x11am2x2 1..1amnxn # bma21x11a22x21..1a2nxn # b2a11x11a12x21.

3 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

4 FormIn the tableau, it is customary to omit the coefficient of z. 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.

5 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. 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.

6 (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.

7 (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.

8 So we choose as the departing Departing1101027s22500190s30000 EnteringNote that the pivot is the entry in the first row and second column. 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.

9 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.

10 (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.