Math438 ACTIVITY 15:Artificial Variables and the Two-phase Simplex Method
WHY:There are LP problems in which standard form does not produce an identity matrix in the original tableau; they include equality constraints that aren't "nice", or have ≥ constraints (that give surplus variables - coefficient
-1, rather than 1, in the constraint). We handle this situation by creating artificial variables that are not part of the original problem; they give us an initial basic feasible solution to a modified problem – the values of the artificial variables measure how far we are from feasibility for the original problem, so we must drive them out of the basis (make them 0) to get a genuine basic feasible solution. If they cannot be driven out of the basis, we are dealing with an infeasible problem - there are no feasible solutions at all. [This is the other way - besides being unbounded - that a linear programming problem can fail to have an optimal solution]
VOCABULARY:
Artificial Variable
An Artificial Variable is a nonnegative quantity added to the left side of a constraint of an LP problem in standard form. Enough artificial variables are added to the constraints so that the resulting coefficient matrix contains an mxm Identity submatrix, giving an initial feasible solution to a related problem (whose objective function –to be reduced to 0 – measures the extent to which we are violating the original constraints). Although they are initially basic variables when we apply the simplex method, artificial variables must be driven out of the basis so that their values are zero in the final solution. If this is not possible, then the problem is infeasible (i.e. its feasible region is null).
Two-Phase Simplex Method
This extended form of the Simplex Method first {Phase I] drives the artificial variables out of the basis and then [Phase II] solves the original problem [starting from th ebasic feasible solution found in Phase I]. See Procedure 3.4.1 on p.114 of Strategic Mathematics and the methodology below.
LEARNING OBJECTIVES:
1.Discover when and how to introduce artificial variables in a linear programming problem.
2.Discover how to solve a two-phase problem or else tell when it is unbounded or infeasible using the Simplex Method.
3.Take time to review group expectations.
CRITERIA:
1.Quality of the answers to the Critical Thinking Questions.
2.Success in applying the methodology to homework and quiz problems.
METHODOLOGY:
1. Put in Standard FormAdd slack or surplus variables to put a problem in the form: Min CTX where AX = b, X ≥ 0.
2. Add Artificial VariablesAdd a new variable to the left side of each constraint which does not contribute a pivot (1 with 0's above & below) to the coefficient matrix. [usually from ≥ or = constraints].
3. Change Objective FunctionSet up a new objective function equal to the sum of the artificial variables.
4. Perform Phase ISet up the simplex tableau [for this problem] and pivot to reach a solution where bottom row ≤ 0.
5. Check for FeasibilityIf the value of the objective function in step 4 is not 0, the problem is infeasible. If it is 0, remove the [columns for the] artificial variables from the tableau.
6. Insert original Obj. FunctionReplace the bottom row of the final tableau in phase 1 with the negative of original objective function [usual bottom row]. It will probably be necessary to perform some preliminary pivots (as in Act 14) to obtain the correct form for starting the simplex algorithm
7. Perform Phase IIContinue pivoting until you obtain an optimal solution or evidence that the problem is unbounded.
RESOURCES:
1.Section 3.4: Strategic Mathematics, especially examples 3.4.2 -- 3.4.4.
2.30 minutes
PLAN:
1.Work through the models given here, and the discussion of the methodology
2.Answer the Critical Thinking Questions
3.Complete the Exercise below
MODEL 1:
1. Put in Standard FormAdd slack or surplus variables to put a problem in the form: Min CTX where AX = b, X ≥ 0.
Original ProblemStandard form:
minimize -x1 + x2minimize-x1 + x2
subj to: 6x1 - x2 ≤ 10subj to:6x1 - x2 + x4 = 10
x1 + 5x2 ≥ 4 x1 + 5x2 - x5= 4
x1 + 5x2 + x3 = 5 x1 + 5x2 + x3 = 5
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0xi ≥ 0 for all i
2. Add Artificial VariablesAdd a new variable to the left side of each constraint which does not contribute a pivot to the coefficient matrix [usually from ≥ or = constraints].
Constraint 1 already has a slack variable. Constraint 3 has x3 with a coefficient 1 and x3 does not appear in any other constraint, so this 1 will serve as a pivot. Constraint 2 will not provide a pivot, so we need one artificial variable x6 in constraint 2.
3. Change Objective FunctionSet up a new objective function equal to the sum of the artificial variables.
The new objective function for phase 1 will be z' = x6.
4. Perform Phase ISet up the simplex tableau and pivot to reach a solution where bottom row ≤ 0.
Initial Phase I simplex tableau: [Identity in columns 4, 6, 3] [notice the –1 (the negative of the coefficient) in the bottom row of the x6 column]
Note that we have omitted the z column since it is has no effect on our calculations
Setup for simplex process: make all bottom row entries under the basis columns 3, 4 and 6 zero by pivoting. The simplex tableau becomes:
Now, we can start the simplex process: x2 should enter ( 5 in bottom row of column 2) , the pivot is in row 2 ( ratio 4/5) so x6 will be driven out; The new tableau is and we have our minimal solution for Phase 1.
For phase I, B = , B-1 = [Note that B-1 for this phase consists of is columns 4, 6, and 3 of the final tableau - the columns that contained the identity matrix in the original tableau]
5. Check for FeasibilityIf the value of the objective function in step 4 is not 0, the problem is infeasible. If it is 0, remove the [columns for the] artificial variables from the tableau.
The value in the solution to step 4 is z' = 0. The artificial variable x6 is no longer in the basis and has no meaning in the final solution, so remove the x6 column from the tableau .
6. Insert original Objective Function: Replace bottom row of the final tableau in phase 1 with the negative of original obj. function.
The initial Phase II tableau is:
Starting basis is x4, x3, x2 - but there is a -1 at the bottom of the x2 column so we pivot on a22 to get zero under this basis column. The pivot yields [Our initial basic feasible solution gives value .8 - not 0, because two of the basic variables are decision variables - not slack or surplus]
7. Perform Phase IIContinue pivoting until an optimal solution is reached or the problem becomes unbounded.
We need to bring in x1 (bottom row value 1.2). Minimum ratio is 10.8/6.2, so we pivot on a11 (driving x4 out of the basis - row 1 is the x4 row).
Final tableau is: Optimal solution [1.74 .45 1 0 0]
The phase II B is and the Phase II B-1 is (again - the columns in the final tableau that contained the identity in the initial tableau for this phase).
For the problem as a whole,
B = , B-1 = BII-1BI-1 = (product of the two separate B-1 matrices for the two phases - notice the order) , Why?
DISCUSSION:
Step 1. Put in Standard Form
In order to solve a problem using the simplex method we must replace the constraint inequalities by equalities. This is what is done by converting the problem to standard form. Doing this increases the dimension of the feasible region, but there is a 1-1 correspondence between the extreme points of the original feasible region and those of the new feasible region. Thus, solutions to the problem in standard form yields solutions to the original problem.
Step 2.Add Artificial Variables
In order to start the simplex method we need an Identity submatrix in the simplex tableau. If the original constraints were ≤, we added a slack variable which gave rise to a pivot column in the coefficient matrix. Otherwise, we subtracted a surplus variable (in the ≥ case) or did nothing (in the = case). To force an Identity submatrix, we add variables, called artificial variables, to the constraints which did not contribute pivot columns to the coefficient matrix. [This gives a different problem in which we have an initial basic feasible solution. In steps 3 and 4 we force out the artificial variables so our solutions are in the original feasible region].
Step 3. Change Objective Function
We need to set up a new objective function equal to the sum of the artificial variables [This measures how far away we are from having a feasible solution of our original problem]. Since the artificial variables are nonnegative, the objective function value will always be nonnegative. We want to force the artificial variables to become 0 in order to drive them out of the basis (so we can work on our original problem). Thus the optimal solution with objective function z' will be z' = 0.
Step 4. Perform Phase I
To obtain an optimal solution z' = 0 for the problem with artificial variables and the objective function constructed in Step 3, we construct a simplex tableau and pivot using the minimum ratio rule until the artificial variables have been driven from the basis. This process is called Phase I. The first set of pivots is always focused on getting zeros under the basic columns in the tableau. After this is accomplished, we choose columns with positive last row entries to come into the basis if their minimum ratio will be in a row containing a pivot in an artificial variable column.
Step 5. Check for Feasibility
If the optimal solution from the Phase I simplex method has a positive objective function value then the problem we are working on has no points in its feasible region, and hence is infeasible [The smallest possible “distance from feasible solutions” is positive – we can never reach a feasible solution for the original problem.]. If z' = 0, we can continue pivoting (without changing the objective function value) until all the artificial variable columns have been dropped from the simplex tableau. See the algorithm on page 125 of Strategic Mathematics for details.
Step 6.Insert Old Objective Function
We are ready to start solving the original problem, since Phase I has produced an Identity submatrix in the simplex tableau [has identified a basic feasible solution]. We insert the negative of the coefficients of the original objective function in standard form in the bottom row of the tableau. We usually need to perform a set of pivots to get zeros under all the basic columns [value of the objective function at this solution is not usually 0]
Step 7.Perform Phase II
Again, the first set of pivots is focused on getting zeros under the basic columns. Once we have zeros under all the basic columns, , we proceed with the usual simplex method to reach an optimal solution or discover that the problem in unbounded. At each step we could write out the matrices B and B-1 and the vectors CBT and CDT [Doing so for each Phase and for the final solution – but not for every pivot step - will be helpful when we do post-optimality analysis.] Premultiplying by the product of B-1 from Phase II and B-1 from Phase I will convert the original tableau [all but the bottom row] for the problem to the final tableau from Phase II.
MODEL 2:
See examples 3.4.2 – 3.4.4 on pages 111-114.
CRITICAL THINKING QUESTIONS:
1.Why do we need only one artificial variable in Model 1?
2.If Phase I ends with a positive objective function value, why is the problem infeasible? What does this mean about the feasible region?
3.What is the first move in executing the simplex method in both Phase I and Phase II?
4.Why is the last sentence in the discussion of step 7 true?
5.Which was the most difficult step in the methodology to understand? Can you reword it and its discussion to make it clearer?
EXERCISE:
Work with the following problem:
minimize3x1 - x2 + x3
subject to: x1 + x2= 3
2x1 + 4x2 - x3 ≥ 2
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
1.Put the problem in standard form, add artificial variables if necessary, and set up the initial simplex tableau:
2.Complete phase I (solve the artificial variables problem to obtain an initial feasible solution). You may use Maple to compute the tableaus (The worksheet from Activity 14 - Activity14.mw - contains the necessary commands -- but does not contain the matrices for this problem) or do the computations by hand. Identify A, b, D, B, B-1 for this phase
3.Finish solving the problem. Write out the final [optimal] basic feasible solution as well as B, B-1, D, and
CBT B-1D - CDT for the problem as a whole