CHAP EER 3 The Simplex Method and Sensitivity Analysis Chapter Guide. This chapter details the simplex method for solving the general LP problem. It also explains how simplex-based sensitivity analysis is used to provide important economic interpretations about the optimum solution, including the dual prices and the reduced cost. The simplex method computations are particularly tedious, repetitive, and, above all, boring. As you do these computations, you should not lose track of the big picture; namely, the simplex method attempts to move from one corner point of the solution space to a better corner point until the optimum is found. To assist you in this regard, TORA’s interactive user-guided module (with instant feedback) allows you to decide how the computations should proceed while relieving you of the burden of the tedious computations. In this manner, you get to understand the concepts without being overwhelmed by the computational details. Rest assured that once you have learned how the simplex method works (and itis important that you do understand the concepts), computers will carry out the tedious work and you will never again need to solve an LP manually. Throughout my teaching experience, I have noticed that while students can easily carry out the tedious simplex method computations, in the end, some cannot tell why they are doing them or what the solution is. To assist in overcoming this potential difficulty, the material in the chapter stresses the interpretation of each iteration in terms of the solution to the original problem. ‘When you complete the material in this chapter, you will be in a position to read and interpret the output reports provided by commercial software. The last section describes how these reports are generated in AMPL, Excel Solver, and TORA. This chapter includes a summary of | real-life application, 11 solved examples, 1 AMPL model, 1 Solver model, 1 TORA model, 87 end-of-section problems, and 3 cases. The cases are in Appendix E on the CD. The AMPL/Excel/Solver/TORA programs are in folder ch3Files. Real Life Application—Optimization of Heart Valve Production Biological heart valves in different sizes are bioprostheses manufactured from porcine hearts for human implantation. On the supply side, porcine hearts cannot be “produced” to specific sizes COURSE MATERIAL FOR RESTRICTED CIRCULATION ONLY 675 Operations Research: An Introduction oreover, the exact size of amanufactured valve cannot be determined until the biological component { pigheart has been processed. Asa result, some sizes may be overstocked and others understocked. \ linear programming model was developed to reduce overstocked sizes and increase understocked zes. The resulting savings exceeded $1,476,000 in 1981, the year the study was made. The details of is study are presented in Case 2, Chapter 24 on the CD. 1 LP MODEL IN EQUATION FORM he development of the simplex method computations is facilitated by imposing two requirements 1 the constraints of the problem: 1. All the constraints (with the exception of the nonnegativity of the variables) are equations with nonnegative right-hand side. 2. Alll the variables are nonnegative. . These two requirements are imposed here primarily to standardize and streamline the simplex method calculations, It is important to know that all commercial packages (and TORA) directly accept inequality constraints, nonnegative right-hand side, and unrestricted variables. Any necessary pre- conditioning of the model is done internally in the software before the simplex method solves the problem. 3.1.1 Converting Inequalities into Equations with Nonnegative Right-Hand Side {n (<) constraints, the right-hand side can be thought of as representing the limit on the availability of a resource, in which case the left-hand side would represent the usage of this limited resource by the activities (variables) of the model. The difference between the right-hand side and the left-hand side of the (<) constraint thus yields the unused or slack amount of the resource. ‘To convert a (<)-inequality to an equation, a nonnegative slack variable is added to the left-hand side of the constraint. For example, in the Reddy Mikks model (Example 2.1-1), the constraint associated with the use of raw material M1 is given as 6m + 4x <4 Defining s1 as the slack or unused amount of M1, the constraint can be converted to the following equation: 6x +4x2 +51 = 24,51 20 Next, a (2)-constraint sets a lower limit on the activities of the LP model, so that the amount by which the left-hand side exceeds the minimum limit represents a surplus. The conversion from (©) to (=) is achieved by subtracting a nonnegative surplus variable from the left-hand side of the inequality. For example, in the diet model (Example 2.2-2), the constraint representing the minimum feed requirements is x +22 > 800 Defining 5; as the surplus variable, the constraint can be converted to the following equation x1 +42 = $, = 800, 51 20 COURSE ?ATERIAL FOR RESTRICTED CIRCULATION ONLY Tr Th ne: PRThe Simplex Method and Sensitivity Analysis 69 The only remaining requirement is for the right-hand side of the resulting equation to be nonnegative. The condition can always be satisfied by multiplying both sides of the resulting equation by —1, where necessary. For example, the constraint —utm<-3 is equivalent to the equation -m tm ts =-3.9120 Now, multiplying both sides by —1 will render a nonnegative right-hand side, as desired—that is, 1-9 =3 PROBLEM SET 3.18, *1. In the Reddy Mikks model (Example 2.2-1), consider the feasible solution x; = 3 and x2 = 1 Determine the value of the associated slacks for raw materials M1 and M2. 2. In the diet model (Example 2.2-2), determine the surplus amount of feed consisting of 500 Ib of corn and 600 Ib of soybean meal. 3. Consider the following inequality 10xy — 31 = -5 Show that multiplying both sides of the inequality by ~1 and then converting the resulting inequality into aan equation is the same as converting it first to an equation and then multiplying both sides by ~1. 4, Write the standard form of the LP, ‘Maximize z bey + 2x7 subject to, 2xy+ x2 52 3xy +4xp > 12 a4. 20. 5. Show how the following objective function can be presented in equation form: Minimize 2 = max(|xy — x2 +33), |— x1 +3x2— 31) 4.42.43 20 (Hint: |a| < bis equivalent toa < banda > -b,) 6. Show that the m equations: aijxj = bit Deus m +1 inequalities: are equivalent to the follow Says) shi = r= | FOR RESTRICTED CIRCULATION ONLY70 Operations Research: An Introduction 3.1.2 Dealing with Unrestricted Variables In Example 2.3-6 we presented a multiperiod production smoothing model in which the workforce at the start of each period is adjusted up or down depending on the demand for that period. Specifically, if x; (= 0) is the workforce size in period i, then x;+1 (= 0) the workforce size in period i + 1 can be expressed as ma = ai + Yet The variable y;1 must be unrestricted in sign to allow x;41 to increase or decrease relative to 1) depending on whether workers are hired or fired, respectively. "Aswe will see shortly, the simplex method computations require all the variables be nonnegative. ‘We can always account for this requirement by using the substitution Jie Vijay Where y;,, 20 and vi 20 To show how this substitution works, suppose that in period 1 the workforce is +1 = 20 workers and that the workforce in period 2 will be increased by 5 to reach 25 workers. In terms of the variables y, and y},, this will be equivalent to yz = 5 and yf =0or y2 =5—0=5. Similarly, if the workforce in period 2 is reduced to 16, then we have yy =O and yf =4, or yp = 0-4 = —4. The substitution also allows for the possibility of no change in the workforce by letting both variables assume a zero value. ‘Youprobably are wondering about the possibility that both y,_ and y} may assume positive values simultaneously. Intuitively, as we explained in Example 2.3-6, this cannot happen, because it means that we can hire and fire a worker at the same time. This intuition is also supported by a mathematical proof that shows that, in any simplex method solution, itis impossible that both variables will assume positive values simultaneously. PROBLEM SET 3.1B 1. Express the following linear programming problem in the standard form, Maximize z = 3x1 +219 + 5x3 subject to, 2x - 3x2 <3 xy +21 + 3x3 <5 3x +213 <2 20,2720. 2, Express the following LPP in the standard form, Minimize z = x1 — 2x2 +23 subject to, Day + 3x2 +433 2-4 3x +517 +243 27 COURSE ).ATERIAL | FOR RESTRICTED CIRCULATION ONLY x1.) 2 Oand x5 is unrestricted 3.2 Th of nn ho an: to sol cor x= ani sol 1 itiThe Simplex Method and Sensitivity Analysis 71 *3. JoShop manufactures three products whose unit profits are $2, $5, and $3, respectively. The company has budgeted 80 hours of labor time and 65 hours of machine time for the production of three products, The labor requirements per unit of products 1, 2, and 3 are 2, 1, and 2 hours, respectively. The corresponding ‘machine time requirements per unit are 1, 1 and 2hours. JoShop regards the budgeted labor and machine hours as goals that may be exceeded, if necessary, but at the additional cost of $15 per labor hour and $10 per machine hour, Formulate the problem as an LP, and determine its optimum solution using TORA, Solver, or AMPL. 4, In an LP in which there are several unrestricted variables, a transformation of the type xj = j xf. 27 4} > Owill double the corresponding number of nonnegative variables. We can, instead, replace k unrestricted variables with exactly k+1 nonnegative variables by usingthe substitution xj = x)—w,., w > 0. Use TORA, Solver, or AMPL to show that the two methods produce the same solution for the following LP: Maximize z= -2x1 +322 ~ 23 subject to 4x —2 — 5x 2xy +312 + 2x x 2 0,29,.23 unrestricted 3.2, TRANSITION FROM GRAPHICAL TO ALGEBRAIC SOLUTION The ideas conveyed by the graphical LP solution in Section 2.2 lay the foundation for the development of the algebraic simplex method. Figure 3.1 draws a parallel between the two methods. In the graphical method, the solution space is delineated by the half-spaces representing the constraints, and in the simplex method the solution space is represented by m simultaneous linear equations and n nonnegative variables. ‘We can see visually why the graphical solution space has an infinite number of solution points, but how can we draw a similar conclusion from the algebraic representation of the solution space? The answer is that in the algebraic representation the number of equations m is always less than or equal to the number of variables n.' If m = n, and the equations are consistent, the system has only one solution; but if m < n (which represents the majority of LPs), then the system of equations, again if consistent, will yield an infinite number of solutions. To provide a simple illustration, the equation x =2has m =n = 1, and the solution is obviously unique, But, the equation x + y = 1 has m = 1 and = 2, and it yields an infinite number of solutions (any point on the straight line x + y = lisa solution). Having shown how the LP solution space is represented algebraically, the candidates for the optimum (ie, corner points) are determined from the simultaneous linear equations in the following manner: Algebraic Determination of Corner Points. 7 Ina set of m x n equations (m < n), if we set n — m variables equal to zero and then solve the m equations for the remaining m variables, the resulting solution, if unique, is called a basic solution ‘the number of equations m is larger than the number of variables, then atleast m — n equations must be redundant. : COURSE MATERIAL | FOR RESTRICTED CIRCULATION ONLY72 Operations Research: An Introduction Graphical Method Algebraic Method ‘Graph all constraints, including nonnegativity | | {Represent the solution space by m equations restrictions in m variables and restrict all variables to nonnegative values, m 4 at x t4x3 = 10 sag 20 xy unrestricted Conversion to the equation form involves using the substitution x2 = xy ~ x}. Show that a basic solution cannot include both x> and x} simultaneously. 5. Consider the following LP: Maximize 2 = x1 + 3x2 subject to ata <2 -ntns4 es x1 unrestricted COURSE iW@ATERIAL 20 | FOR RESTRICTED CIRCULATION ONLY (a) Determine all the basic feasible solutions of the problem. (b) Use direct substitution in the objective function to determine the best basic solution, (©) Solve the problem graphically, and verify that the solution obtained in (c) is the optimum.76 Operations Research: An Introduction 3.3. THE SIMPLEX METHOD Rather than enumerating all the basic solutions (corner points) of the LP problem (as we did in Section 3.2), the simplex method investigates only a “select few” of thcse solutions. Section 3.3.1 describes the iterative nature of the method, and Section 3.3.2 provides the computational details of the simplex algorithm. 3.3.1 Iterative Nature of the Simplex Method Figure 33 provides the solution space of the LP of Example 3.2-1. Norm lly, the simplex method starts at the origin (point A) where x1 = x) = 0. At this starting point, the valuc » the objective function, z, iszero, and the logical question is whether an increase in nonbasic x; and/or x2 above their current zero values can improve (increase) the value of z, We answer this question by investigating the objective function: Maximize z = 2x1 + 3x2 The function shows that an increase in either x1 or x2 (or both) above their current zero values will improve the value of z. The design of the simplex method calls for increasing one variable at a time, with the selected variable being the one with the largest rate of improvement in z. In the present example, the value of z will increase by 2 for each unit increase in x, and by 3 for each unit increase in x). This means that the rate of improvement in the value of z is 2 for x; and 3 for x2. We thus elect to increase x9, the variable with the largest rate of improvement, Figure 3.4 shows that the value of FIGURE 2.3, Iterative process of the simplex method. COURS TERIAL | FOR RESTRICTED CiCULATTON ONLYThe Simplex Method and Sensitivity Analysis 77 x2 must be increased until corner point B is reached (recall that stopping short of reaching corner point B is not optimal because a candidate for the optimum must be a comer point). At point B. the simplex method will then increase the value of x; to reach the improved corner point C, which is the optimum. The path of the simplex algorithm is thusdefined as A > B + C. Each comer point along the path is associated with an iteration. It is important to note that the simplex method moves alongside the edges of the solution space, which means that the method cannot cut across the solution space, going from A to C directly. We need to make the transition from the graphical solution to the algebraic solution by showing how the points 4, B, and C are represented by their basic and nonbasie variables. The following table summarizes these representations: Corner point Basic variables ~Nonbasic (zero) variables A 5192 AAD B S22 182 a Este) S182 Notice the change pattern in the basic and nonbasic variables as the solution moves along the path A BC. From A to B, nonbasic x2 at A becomes basic at B and basic s> at A becomes nonbasic at B. In the terminology of the simplex method, we say that x2 is the entering variable (because it enters the basic solution) and s> is the leaving variable (because it leaves the basic solution). In a similar manner, at point B, x; enters (the basic solution) and sy leaves, thus leading to point C. PROBLEM SET 3.34, 1, In Figure 3.3, suppose that the objective function is changed to Maximize z= 8x +42 Identify the path of the simplex method and the basic and nonbasic variables that define this path. 2. Consider the graphical solution of the Reddy Mikks model given in Figure 2.2, Identify the path of the simplex method and the basic and nonbasic variables that define this path. *3. Consider the three-dimensional LP solution space in Figure 3.4, whose feasible extreme points are A, B, and J, % COURSE MATERIAL f zon, | FoR RESTRICTED CIRCULATION ONLY c E — C(0,1,0) D-(0.6.1 cure 3 ” Solution space of Problem 3, Set 3.2b78 Oper This section provides the computatis mining the entering and leaving varial solution has been reached. The vehicle of explanation is a numerical example. ieee COURSE MATERIAL FOR RESTRICTED CIRCULATION ONLY jions Research: An Introduction (a) Which ofthe following pairs of corner points cannot represent successive simplex iterations: (A,B), (B, D), (E, H), and (A, 1)? Explain the reason. (b) Suppose that the simplex iterations start at A and that the optimum oceurs at H- Indicate whether any of the following paths are no legitimate forthe simplex algorithm, and state the reason. @ A+B >G>H. (i) ADE SIH. (ii) A+ C+ E> B>A>D>G>H. 4, For the solution space in Figure 3.4, all the constraints are. of the type < and all the variables x,x2, and x3 are nonnegative. Suppose thats, 5,3, and sg (= 0) are the slacks associated with cons \srepresented by the planes CEUF, BEIHG, DFIHG, and LJH, respectively. Identify the basic ané sonbasie variables associated with each feasible extreme point of the solution space. Consider the solution space in Figure 34, where the simplex algorithm starts at point 4. Determine the entering variable in the first iteration together with its value and the improvement in = for each of the following objective functions: (a), Maximize 2 = xy — 2x2 +333 (b) Maximize 2 = 5x1 +212 +433 (©) Maximize z = —2x1 +72 +233 (@) Maximize 2 = 11 +22 +33 3.3.2 Computational Details of the Simplex Algorithm ‘onal details of a simplex iteration, including the rules for deter- ‘bles as well as for stopping the computations when the optimum Example 3.3-1 We use the Reddy Mikks model (Example 2.1-1) to explain the details o expressed in equation form as Maximize z= 5x1 + 4x2 + Osy +052 + O53 + Os the simplex method. The problem is subject to 6x, +4 +51 =24 (Raw material My) mt2n +9 6 (Raw material Mz) —y tx +53 1 (Market limit) x” 454 = 2 (Demand limit) 142,514 521 53154 20 ‘The variables 51,5, 53, and sy are the slacks associated with the respective constraints. Next, we write the objective equation as z-Sy— 42 =0 In this manner, the starting simplex tableau can be represented as follows: on of: any val bat the by en the ath un as ur (x ne a th soThe Simplex Method and Sensitivity Analysis 79 ‘The design of the tableau specifies the set of basic and nonbasic variables as well as provides the solution associated with the starting iteration. As explained in Section 3.3.1, the simplex iterations start at the origin (1,22) = (0, 0) whose associated set of nonbasic and basic variables are defined as Nonbasic (zero) variables: Basic variables:(sy, 52,53, 54) 162) Substituting the nonbasic variables (x1, x2) = (0,0) and noting the special 0-1 arrangement of the coefficients of z and the basic variables (5, sp, 53,54) in the tableau, the following solution is immediately available (without any calculations): z=0 a4 = 6 sal a2 This information is shown in the tableau by listing the basic variables in the leftmost Basic column and their values in the rightmost Solution column. In effect, the tableau defines the current corner point by specifying its basic variables and their values, as well as the corresponding value of the objective function, z. Remember that the nonbasic variables (those not listed in the Basic column) always equal zero. Isthe starting solution optimal? The objective function z = 5x1 +4r2 shows that the solution can be improved by increasing xj or x2. Using the argument in Section 3.3.1, 1 with the most positive coefficient is selected as the centering variable. Equivalently, because the simplex tableau expresses the objective function as :~Sx1 —4x) = the entering variable will correspond to the variable with the most negative coefficient in the objective equation. This rule is referred to as the optimality condition. ‘The mechanics of determining the leaving variable from the simplex tableau calls for computing the nonneg- ative ratios of the right-hand side of the equations (Solution column) to the corresponding constraint coefficients under the entering variable, x1, as the following table shows. Entering Ratio a Solution ome Basic 1 y= Ap =-1 ignore) 2 m=Feo0li 1 = § =00 (ignore) Conclusion: xj enters and sy leaves ‘The minimum nonnegative ratio automatically identifies the current basic variable sy as the leaving variable and assigns the entering variable x, the new value of 4. How do the computed ratios determine the leaving variable and the value of the entering variable? Fig- ture 3.5 shows that the computed ratios are actually the intercepts of the constraints with the entering variable (x1) axis, We can see that the value of x; must be increased to 4 at corner point B, which is the smallest non- negative intercept with the x-axis. An increase beyond B is infeasible. At point B, the current basic variable 51 associated with constraint 1 assumes a zero value and becomes the leaving variable. The rule associated with the ratio computations is referred to as the feasibility condition because it guarantees the feasibility of the new solution, i COURSE MATERIAL | FOR RESTRICTED CIRCULATION ONLY80 Operations Research: An Introduction Maxinize z= 5, + 4 sujet to: Gq +4 +5,=%8 O ntdgtns 6@ -ytntg=1@ HK nian 2@ 4 © im a |} -s ———4 FIGURE 3.5 Graphical interpretation of the simplex method ratios in the Reddy Mikks model ‘The new solution point B is determined by “swapping” the entering variable x, and the leaving variable sy in the simplex tableau to produce the following sets of nonbasic and basic variables: Nonbasic (zero) variables atB : (51,*2) Basic variables atB : (x1, $2, 53,54) “The swapping process is based on the Gauss-Jordan row operations. It identifies the entering variable column asthe pivot column and the leaving variable row as the pivot row. The intersection of the pivot column and the pivot row is called the pivot element. The following tableau is a restatement ofthe starting tableau with its pivot row and column highlighted. “The Gauss-Jordan computations needed to produce the new basic solution include two types. 1. Pivotrow ‘a. Replace the leaving variable in the Basic column with the entering variable. b. New pivot row = Current pivot row + Pivot element Enter Basic z x st 8354 _ Solution 0 0 Pivot row 2 0 PEO wee ena, 6 si 0 aD eee 1 (0 Pou 0 2 Pivot column ¥ COURSE MATERIAL FOR RESTRICTED CIRCULATION ONLYThe Simplex Method and Sensitivity Analysis 81 2. All other rows, including z New Row = (Current row) — (Its pivot column coefficient) x (New pivot row) These computations are applied to the preceding tableau in the following manner: 1, Replace sin the Basic column with x1: New x1-row = Current s1-row +6 = }064100024) 1320004) 2, New z-row = Current z-tow ~ (~5) x New x-row = (1 -5 -400000)~(-5)x 013 $0004) 0-3 $00020) 3. New sp-row = Current sg-row ~ (1) x New x1-row =(01201006)~ (1) x01} £0004) (00$ -£1002) 4, New sg-row = Current ss-row — (~1) x New x1-row = (0 -1100101)~(-1) x 01 $0004) = (003 $0105) 5. New sq-row = Current sq-row — (0) x New xy-row = (00100012) ~(0)(01 3 $0004) = (00100012) ‘The new basic solution is (x, 2,3, 4) and the new tableau becomes Basic zo 1 354 Solution zi o go 0 o 2% Observe that the new tableau has the same properties as the starting tableau. When we set the new nonbasic variables x2 and s; to zero, the Solution column automatically yields the new basic solution (x1 = 4, s2 = 2,53 5,54 = 2). This “conditioning” of the tableau is the result ofthe application of the Gauss-Jordan row operations. ‘The corresponding new objective value is z = 20, which is consistent with New z= Oldz +New x-value x its objective coefficient =0+4x5=20 In the last tableau, the optimality condition shows that x is the entering variable. The feasibility condition produces the following COURSE MATERIAL {FOR RESTRICTED CIRCULATION ONLY82 Operations Research: An Introduction Entering Basic oy Solution 3 4 3 2 3 5 1 2 Thus, sy leaves the basic solution and new value of x) is 1.5. The corresponding increase in zis 3x9 = 3 x15 which yields new z = 20 +1 =21 Replacing 5 in the Basic column with entering xp, the following Gauss-Jordan row operations are ap- plied: 1. New pivot x7-row = Current s)-row 2, New z-row = Current z-row ~(~ 3)x New x7-1ow 3, New xy-row = Current xy-row ~(3) x New x)-row 4, New s3-row = Current s3-row ~(3) x New x2-10W. 8, New sq-row = Current sj-row ~(1)x New x-row ‘These computations produce the following tableau: Basic z x, ¥2 5) 52 83 54 Solution n 3 cy 3 I 3 54 $ Based on the optimality condition, none of the z-row coefficients associated with the nonbasic variables, s and sp, are negative. Hence, the last tableau is optimal. ‘The optimum solution can be read from the simplex tableau in the following manner. The optimal val- ues of the variables in the Basic column are given in the right-hand-side Solution column and can be inter- preted as Decision variable Optimum value Recommendation a 3 Produce 3 tons of exterior paint daily * 3 Produce 1.5 tons of interior paint daily z 2 Daily profit is $21,000 ‘You can verify that the values s, = s = 0,53 = 3,55 = } are consistent with the given values of x; and x2 by substituting out the values of x1 and x9 in the constraints. == eee ‘ | COURSE MATERIAL | FOR RESTRICTED CIRCULATION ONLY Se ™ lez im op of cal oo ger ite the gre 33 So cal. coe bec var— The Simplex Method and Sensitivity Analysis 83, ‘The solution also gives the status of the resources. A resource is designated as scarce ifthe activities (vari ables) of the model use the resource completely. Otherwise, the resource is abundant. ‘This information is secured from the optimum tableau by checking the value of the slack variable associated with the constraint representing the resource. If the slack value is zero, the resource is used completely and, hence, is classified as scarce. Otherwise, a positive slack indicates that the resource is abundant. The following table classifies the constraints of the model: Resource Slack value Status Raw material, M1 5) =0 Scarce Raw material, M2 5 Scarce Market limit % Abundant Demand lit 4 Abundant, Remarks. The simplex tableau offers a wealth of additional information that includes: L. Sensitivity analysis, which deals with determining the conditions that will keep the current solution un- changed. 2. Post-optimal analysis, which deals with finding a new optimal solution when the data of the model are changed. Section 3.6 deals with sensitivity analysis. The more involved topic of post-optimal analysisiscoveredin Chapter 4, TORA Moment. ‘The Gauss-Jordan computations are tedious, voluminous, and, above all, boring. Yet, they are the Jeast important, because in practice these computations are carried out by the computer. What is important is that you understand how the simplex method works. TORA’s interactive user-guided option (with instant feedback) can be of help in this regard because it allows you to decide the course of the computations in the simplex method without the burden of carrying out the Gauss-Jordan calculations. To use TORA with the Reddy Mikks problem, enter the model and then, from the |SOLVE/MODIFY) menu, select Solve’ > |Algebilid! = [Tieration ESiack. (The All-Slack DIFY Ss ba selection indicates that the starting basic solution consists of slack variables only. ‘The remaining options will be presented in Sections 3.4, 4.3, and 7.4.2.) Next, click Go er generate one or all iterations by clicking Next Iteration or All Iterations. If you opt to generate the iterations one at a time, you can interactively specify the entering and leaving variables by clicking the headings of their corresponding column and row. If your selections are correct, the column turns green and the row turns red. Else, an error message will be posted, 3.3.3 Summary of the Simplex Method So far we have dealt with the maximization case. In minimization problems, the optimality condition calls for selecting the entering variable as the nonbasic variable with the most positive objective coefficient in the objective equation, the exact opposite rule of the maximization case. This follows because max z is equivalent to min (—z). As for the feasibility condition for selecting the leaving variable, the rule remains unchanged, : COURSE MATERIAL | FOR RESTRICTED CIRCULATION ONLY84 Operations Research: An Introduction Optimality condition, The entering variable in a maximization (minimization) problem is the nonbasic variable having the most negative (positive) coefficient in the z-row. Ties are broken ar- bitrarily. The optimum is reached at the iteration where all the z-row coefficients of the nonbasic variables are nonnegative (nonpositive). Feasibility condition, For both the maximization and the minimization problems, the leaving vatiable is the basic variable associated with the smallest nonnegative ratio (with striciy positive denominator). Ties are broken arbitrarily. Gauss-Jordan row operations. 1. Pivot row a, Replace the leaving variable in the Basic column with the entering variable b. New pivot row = Current pivot row + Pivot element 2, All other rows, including z New row = (Current row) — (pivot column coefficient) x (New pivot row) The steps of the simplex method are Step 1. Determine a starting basic feasible solution. Step 2. Select an entering variable using the optimality condition. Stop if there is no entering variable; the last solution is optimal. Else, go to step 3. Step 3. Select a Jeaving variable using the feasibility condition. Step 4. Determine the new basic solution by using the appropriate Gauss-Jordan computations. Go tostep 2. PROBLEM SET 3.3B 1 ‘This problem is designed to reinforce your understanding of the simplex feasibility condition, In the first tableau in Example 33-1, we used the minimum (nonnegative) ratio test to determine the leaving variable. Such a condition guarantees that none of the new values of the basic variables will become negative (as stipulated by the definition of the LP). To demonstrate ths point, force sp, instead of sy, toleave the basic solution. Now, look at the resulting simplex tableau, and you will note that s; assumes a negative value (© 12), meaning that the new solution is infeasible. This situation will never occur if we employ the minimum-ratio feasibility condition. 2. Consider the following set of constraints: ay + 2a +215 +414 < 40 Qy- yt ut24s8 4-22 + 19-14 10 apa. ag 4 20 Solve the problem for each of the following objective functions. (a) Maximize < = 2x1 + x2 ~ 3x3 + 5x4. (b) Maximize z = 8x1 + 6x2 + 3x3 — 2a -Seaies COURSE MAT STRICTED CIRCULATION ONLYThe Simplex Method and Sensitivity Analysis 85 (©) Maximize (@) Minimize 3. A manufacturer is engaged in producing 2 products x and y, the contribution margin being Rs. 15 and Rs. 45 respectively. A unit of product x requires 1 unit of facility A and 0.5 unit of facility B. A unit of product y requires 1.6 units of facility A, 2.0 units of facility B and 1 unit of raw material C. The availability of total facility A and B, and raw material C during a particular time period are 240, 162, and 50 units respectively. Find out the product mix which will maximize the contribution margin by simplex method. 4, Consider the following LP: =3ry ay + 3x3 + 4uy. xy — Ay + 6x3 — Bra, Maximize 2 = x, subject to Say +x =4 6x 45 =8 3x try =3 1) 72) %3,%4 20 (a) Solve the problem by inspection (do not use the Gauss-Jordan row operations), and justify the answer in terms of the basic solutions of the simplex method. (b) Repeat (a) assuming that the objective function calls for minimizing z = 5. Solve the following LPP: Maximize z = 15xy + 6x9 + 9x3 +24 subject to the constraints 2ay + 49 + 5x3 +0.6r4 < 10 3x +17 +313 + 0.2514 < 12 Ta +44 <35 Os has an unbounded solution. 6. Show by simplex method that the following LPP has infinite number of non-basic feasible optimal solutions Maximize z = 4xy + 10x, subject to 2+ 2 <10 2x +54 < 20 2x + 3x7 < 18 xa 20 7. Consider the two-dimensional solution space in Figure 36. COURSE MATERIAL (a) Suppose that the objective function is given as D C/RCULATTON ONLY CTED CiRCULAT Maximize z = 3x1 + 6x2 If the simplex iterations start at point A, identify the path to the optimum point E.86 Operations Research: An Introduction FIGURE 3.6 Solution space for Problem 7, Set 3.3b (b) Determine the entering variable, the corresponding ratios ofthe feasibility condition, ané the change in the value of z, assuming that the starting iteration occurs at point A and that the objective function is given as Maximize z = 4xy +22 (©) Repeat (b), assuming that the objective function is Maximize z = xy + 4x 8, Three grades ofcoal A, B and C contain phosphorus and ash as impurities. In a particular industrial process, fuel up to 100 ton (maximum) is required, which should contain ash not more than 3% and phosphorus not more than 0.03%. It is desired to maximize the profit while satisfying these conditions. There is an unlimited supply of each grade, The percentage of impurities and the profits of grades are given below: fisteea eS ON Coa Phosphorus. Ash Profits in rupees % % per ton eee A 0.02 20 12.00 B 0.04 30 15.00 G 0.03 50 14.00 ScCiieo seis Ge ee Find the proportions in which the three grades be used. 9, What do you mean by an optimal basi feasible solution to linear programming problem? Is the solution 9 = 4, x3 = a4 = x5 = 0,a basie solution of the equations: a= atin tay tay =2 xy + xy + $23 +45 = 2? 410, A boat company makes three different kinds of boats, All can be made profitably inthis company, but the ‘company’s monthly production is constrained by the limited amount of labour, wood and screws available each month. The director will choose the combination of boats that maximizes his revenue in view of the information given in the following table: COURSE MATERIAL FOR RESTRICTED CIRCULATION ONLYThe Simplex Method and Sensitivity Analysis 87 Input Row Boat Canoe Keyak Monthly Available Labour (Hours) 2 1 9 1,260 hours Wood (Board feet) 2 18 16 __ 19,008 board feet Screws (Kg) 2 4 3 396 Kg Selling price (in Rs.) 4,000 2,000 5,000 Formulate the above as LPP and solve it by simplex method. From the optimal table of the solved LPP, find: a) How many boats of each type will be produced and what will be the resulting revenue? b) Which, if any, of the resources are not fully utilized? Ifso, how much of spare capacity is left? ©) How much wood will be used to make all of the boats given in the optimal solution? UL. For a company engaged in the manufacture of three products A, B and C, the available data are given below. Product A. BAC ‘Minimum Sales requirement per month 10 20 30 Profit (Rs.)/unit 10 15 8 Operations required processing Times and Capacity Operations 1 er eee A Des Tope tl 3 Bre Total available hours/month 200 220 180 Find out the product-mix to maximize the profit. 3.4 ARTIFICIAL STARTING SOLUTION As demonstrated in Example 3.3-1, LPs in which all the constraints are (=) with nonnegative right- hand sides offer a convenient all-slack starting basic feasible solution. Models involving (=) and/or (=) constraints do not. ‘The procedure for starting “ill-behaved” LPs with (=) and (>) constraints is to use artificial vari- ables that play the role of slacks at the first iteration, and then dispose of them legitimately at a later iteration. Two closely related methods are introduced here: the M-method and the two-phase method. 3.4.1 M-Method The M-method starts with the LP in equation form (Section 3.1). If equation i does not have a slack (or a variable that can play the role of a slack), an artificial variable, Ri, is added to form a starting solution similar to the convenient all-slack basic solution. However, because the artificial variables are not part of the original LP model, they are assigned a very high penalty in the objective function, thus forcing them (eventually) to equal zero in the optimum solution. This will always be the case if COURSE MATERIAL | FoR RESTRICTED CIRCULATION ONLY[course \FoR RESTRICTE!