Chapter 6Linear Programming: The Simplex MethodSection 4Maximization and Minimization with Problem ConstraintsIntroduction to the Big M MethodIn this section, we will present a generalized version of the i l th d th t ill l b th i i ti dsimplex method that will solve both maximization and minimization problems with any combination of ≤, ≥, = constraints2ExampleMaximize P = 2x1+ x2subject tox1+ x2< 10–x1+ x2> 203x1, x2> 0To form an equation out of the first inequality, we introduce a slack variable s1, as before, and write x1+ x2+ s1= 10. Example(continued)To form an equation out of the second inequality we introduce a second variablesandsubtractit from the leftintroduce a second variable s2and subtractit from the left side so that we can write–x1+ x2– s2= 2.The variable s2is called a surplus variable, because it is the amount (surplus) by which the left side of the inequality exceeds the right side.4exceeds the right side.Example(continued)We now express the linear programming problem as a system of equations:equations:x1+ x2+ s1= 10–x1+ x2– s2= 2–2x1– x2+ P = 0x1, x2, s1, s2> 051212Example(continued)It can be shown that a basic solution of a system is not feasible if any of the variables (excludingP) are negative Thus a surplusany of the variables (excluding P) are negative. Thus a surplus variable is required to satisfy the nonnegative constraint. An initial basic solution is found by setting the nonbasic variables x1and x2equal to 0. That is, x1= 0, x2,= 0,,s1= 10, s2= -2, P = 0.This solution is not feasible because the surplus variable s2is negative. 6gArtificial VariablesIn order to use the simplex method on problems with mixed constraints, we turn to a device called an artificial variable. This variable has no physical meaning in the original problem and is introduced solely for the purpose of obtaining a basic feasible solution so that we can apply the simplex method. An artificial variable is a variable introduced into each equation that has a surplus variable. To ensure that we 7qpconsider only basic feasible solutions, an artificial variable is required to satisfy the nonnegative constraint. Example(continued)Returning to our example, we introduce an artificial variable a1into th ti i l i th l i blthe equation involving the surplus variable s2: x1+ x2– s2+ a1= 2To prevent an artificial variable from becoming part of an optimal solution to the original problem, a very large “penalty” is introduced into the objective function. This penalty is created by 8choosing a positive constant Mso large that the artificial variable is forced to be 0 in any final optimal solution of the original problem.Example(continued)We then add the term –Ma1to the objective function:P=2x+xMaP= 2x1+ x2–Ma1We now have a new problem, called the modified problem:Maximize P = 2x1+ x2- Ma1subject to x1+ x2+ s1= 10 9x1+ x2–s2+ a1= 2x1, x2, s1, s2, a1> 0Big MMethod:Form the Modified Problem If any problem constraints have negative constants on the right id lti l b th id b1 t bt i t i t ithside, multiply both sides by -1 to obtain a constraint with a nonnegative constant. Remember to reverse the direction of the inequality if the constraint is an inequality. Introduce a slack variable for each constraint of the form ≤. Introduce a surplus variable and an artificial variable in each ≥ constraint. 10 Introduce an artificial variable in each = constraint.  For each artificial variable a, add –Ma to the objective function. Use the same constant M for all artificial variables. Key Steps for Solving a Problem Using the Big M MethodNow that we have learned the steps for finding the modifiedNow that we have learned the steps for finding the modified problem for a linear programming problem, we will turn our attention to the procedure for actually solving such problems. The procedure is called the Big M Method. 11Example(continued)The initial system for the modified problem isx+x+s=10x1+ x2+ s1= 10 –x1+ x2– s2+ a1= 2–2x1– x2 + Ma1+ P = 0x1, x2, s1, s2, a1> 0We next write the augmented coefficient matrix for this system12We next write the augmented coefficient matrix for this system, which we call the preliminary simplex tableau for the modified problem.Example(continued)xxssaPTo start the simplex process we require aninitial simplex11100010110 11022100 10M⎡⎤⎢⎥−−⎢⎥⎢⎥−−⎣⎦x1x2s1s2a1P13To start the simplex process we require an initial simplex tableau, described on the next slide. The preliminary simplex tableau should either meet these requirements, or it needs to be transformed into one that does.Definition: Initial Simplex TableauFor a system tableau to be considered an initial simplex tableau, it must satisfy the following two requirements: 1. The requisite number of basic variables must be selectable. Each basic variable must correspond to a column in the tableau with exactly one nonzero element. Different basic variables must have the nonzero entries in different rows. The remaining variables are then selected as non-basic 14variables.2. The basic solution found by setting the non-basic variables equal to zero is feasible. Example(continued)The preliminary simplex tableau from our example ti fi th fi t i t idPbsatisfies the first requirement, since s1, s2, and Pcan be selected as basic variables according to the criterion stated. However, it does not satisfy the second requirement since the basic solution is not feasible (s2= -2.) To use the simplex method, we must first use row operations to transform the tableau into an equivalent15operations to transform the tableau into an equivalent matrix that satisfies all initial simplex tableau requirements. This transformation is not a pivot operation. Example(continued)⎡⎤x1x2s1s2a1PIf you inspect the preliminary tableau, you realize that the problem is thats2has a negative coefficient in its column.11100010110 11022100 10M⎡⎤⎢⎥−−⎢⎥⎢⎥−−⎣⎦16problem is that s2has a negative coefficient in its column. We need to replace s2as a basic variable by something else with a positive coefficient. We choose a1.We want to use a1as a basic variable instead of s2. We proceed Example(continued)12pto eliminate M from the a1column using row operations: 11100010110 11022100 10M⎡⎤⎢⎥−−⎢⎥⎢⎥−−⎣⎦(-M)R2+ R3->R3x1x2s1s2a1P171 1 1000 101101102210012MMM M⎡⎤⎢⎥−−⎢⎥⎢⎥−−− −⎣⎦Example(continued)From the last matrix