Return to the
List of Activities This activity is designed to help you understand the process of solving linear programming problems which do not contain an Identity submatrix in the initial tableau. We show how artificial variables can be introduced and the objective function changed so that the Simplex Method will force the artificial variables out of the basis and replace them with problem variables. The two-phase procedure completes the study of the simplex solution method and allows us to solve any LP problem to find its optimal solution or discover whether it is unbounded or infeasible.
| 1. Put in Standard Form | Add slack or subtract surplus variables to put the problem in the form: Minimize CTX subject to AX = b, X >= 0. |
| 2. Add Artificial Variables | Add a new variable to the left side of each constraint which originally was >= or = the constant term. |
| 3. Change Objective Function | Set up a new objective function equal to the sum of the artificial variables. |
| 4. Perform Phase I | Set up the simplex tableau and pivot to reach a solution where bottom row <= 0. |
| 5. Check for Feasibility | If solution to step 4 is not 0, the problem is infeasible. If it is 0, remove rest of artificial variables. |
| 6. Insert old Objective Function | Replace bottom row of the final tableau in phase I with the negative of original standard form objective function. |
| 7. Perform Phase II | Continue pivoting until an optimal solution is reached or the problem becomes unbounded. |
Standard form:
minimize -x1 + x2 minimize -x1 + x2
subj to: 6x1 - x2 <= 10 subj 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 >= 0 xi >= 0 for all i
We need one artificial variable x6 in constraint 2. Constraint 1 already has a slack variable and constraint 3 has x3 with a coefficient 1 and x3 does not appear in any other constraint. Thus the column corresponding to x3 already has a pivot and so will be part of the required Identity submatrix.
The new objective function for phase 1 will be z' = x6.
Initial Phase I simplex tableau:
| 6 -1 0 1 0 0 | 10 | | 1 5 0 0 -1 1 | 4 | | 1 5 1 0 0 0 | 5 | |-----------------------| | 0 0 0 0 0 -1 | 0 |
Note that we have omitted the z column since it is never used.
| 6 -1 0 1 0 0 | | 1 0 0 | | 1 0 0 | | 6 -1 0 |
A = | 1 5 0 0 -1 1 |, B= | 0 1 0 |, B-1 = | 0 1 0 |, D = | 1 5 -1 |
| 1 5 1 0 0 0 | | 0 0 1 | | 0 0 1 | | 1 5 0 |,
b = [10 4 5]'
Setup for simplex process: make all bottom row entries under the basis columns 3, 4 and 6 zero by pivoting. The simplex tableau becomes:
| 6 -1 0 1 0 0 | 10 | | 1 5 0 0 -1 1 | 4 | | 1 5 1 0 0 0 | 5 | |-----------------------| | 1 5 0 0 -1 0 | 4 |
Now, we can start the simplex process: x2 should replace x6 (min ratio 4/5); The new tableau is
| 6.2 0 0 1 -0.2 0.2 | 10.8 |
| 0.2 1 0 0 -0.2 0.2 | 0.8 |
| 0 0 1 0 1 -1 | 1 |
|-------------------------------|
| 0 0 0 0 0 -1 | 0 |
| 1 -1 0 | | 1 0.2 0 |
B = | 0 5 0 |, B-1 = | 0 0.2 0 |
| 0 5 1 | | 0 -1 1 |
The solution to step 4 is z' = 0. The artificial variable x6 is no longer in the basis so we can drop it.
The initial Phase II tableau as follows:
| 6.2 0 0 1 -0.2 | 10.8 | | 0.2 1 0 0 -0.2 | 0.8 | | 0 0 1 0 1 | 1 | |--------------------------| | 1 -1 0 0 0 | 0 | CB = [0 0 1]', CD = [-1 0 0]'
We pivot on a22 to get zero under basic columns. The pivot yields
| 6.2 0 0 1 -0.2 | 10.8 | | 0.2 1 0 0 -0.2 | 0.8 | | 0 0 1 0 1 | 1 | |--------------------------| | 1.2 0 0 0 -0.2 | 0.8 |
We need to bring in x1 in place of x4 since min ratio is 10.8/6.2.
Final tableau is:
| 1 0 0 0.16 -0.03 | 1.74 | | 0 1 0 -0.03 -0.19 | 0.45 | | 0 0 1 0 1 | 1 | |----------------------------| | 0 0 0 -0.19 -0.16 |-1.29 |
Optimal solution [1.74 0.45 1 0 0]
| 6 -1 0 | | 0.16 0 0 || 1 0.2 0 | | 0.16 0.032 0 |
B = | 1 5 0 |, B-1 = |-0.03 1 0 || 0 0.2 0 | = |-0.03 0.194 0 |
| 1 5 1 | | 0 0 1 || 0 -1 1 | | 0 -1 1 |
Why?
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.
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 do not contribute pivot columns to the coefficient matrix. This ensures an initial basic feasible solution. We then do pivot operations to force the artificial variables out of the basis and obtain a basic feasible solution which is an extreme point of the problem in standard form.
We need to set up a new objective function equal to the sum of the artificial variables. 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. Thus the optimal solution with objective function z' will be z' = 0.
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.
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. 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 for details.
We are ready to start solving the original problem, since Phase I has produced an Identity submatrix in the simplex tableau. We insert the negative of the coefficients of the original objective function in standard form in the bottom row of the tableau.
Again, the first set of pivots is focused on getting zeros under the basic columns. Once this is done, we proceed with the usual simplex method to reach an optimal solution or discover that the problem in unbounded. At each step we should write out the matrices B and B-1 and the vectors CB' and CD' as this 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 from Phase I to the final tableau from Phase II.
These will be provided in class.
minimize 3x1 - x2 + x3
subject to: x1 + x2 = 3
2x1 + 4x2 - x3 >= 2
x1 >= 0, x2 >= 0, x3 >= 0
Return to the
List of Activities