teach me 2 phase method In the M-method, the use of the penalty, M, can result in computer roundoff error. The
two-phase method eliminates the use of the constant M altogether. As the name suggests, the method solves the LP in two phases: Phase I attempts to find a starting basic
feasible solution, and, if one is found, Phase II is invoked to solve the original problem.
summary of the two-Phase method
phase I. Put the problem in equation form, and add the necessary artificial variables to the constraints (exactly as in the M-method) to secure a starting basic solution. Next, find a basic solution of the resulting equations
that always minimizes the sum of the artificial variables, regardless of
whether the LP is maximization or minimization. If the minimum value
of the sum is positive, the LP problem has no feasible solution. Otherwise,
proceed to Phase II.
phase II. Use the feasible solution from Phase I as a starting basic feasible
solution for the original problem.
example 3.4-2
We use the same problem in Example 3.4-1.
Phase I
Minimize r = R1 + R2
subject to
3x1 + x2 + R1 = 3
4x1 + 3x2 - x3 + R2 = 6
x1 + 2x2 + x4 = 4
x1, x2, x3, x4, R1, R2 Ú 0
The associated tableau is
Basic x1 x2 x3 R1 R2 x4 Solution
r 0 0 0 -1 -1 0 0
R1 3 1 0 1 0 0 3
R2 4 3 -1 0 1 0 6
x4 1 2 0 0 0 1 4
116 Chapter 3 The Simplex Method and Sensitivity Analysis
As in the M-method, R1 and R2 are substituted out in the r-row by using the following row
operations:
New r@row = Old r@row + 11 * R1@row + 1 * R2@row2
The new r-row is used to solve Phase I of the problem, which yields the following optimum tableau (verify with TORA’s Iterations 1 Two@phase Method ):
Basic x1 x2 x3 R1 R2 x4 Solution
r 0 0 0 -1 -1 0 0
x1 1 0 1
5
3
5 -1
5 0 3
5
x2 0 1 -3
5 -4
5
3
5 0 6
5
x4 0 0 1 1 -1 1 1
Because minimum r = 0, Phase I produces the basic feasible solution x1 = 3
5, x2 = 6
5, and
x4 = 1. At this point, the artificial variables have completed their mission, and we can eliminate
their columns altogether from the tableau and move on to Phase II.
Phase II
After deleting the artificial columns, we write the original problem as
Minimize z = 4x1 + x2
subject to
x1 + 1
5 x3 = 3
5
x2 - 3
5 x3 = 6
5
x3 + x4 = 1
x1, x2, x3, x4 Ú 0
Essentially, Phase I has transformed the original constraint equations in a manner that provides
a starting basic feasible solution for the problem, if one exists. The tableau associated with Phase
II problem is thus given as
Again, because the basic variables x1 and x2 have nonzero coefficients in the z-row, they
must be substituted out, using the following operations.
New z@row = Old z@row + 14 * x1@row + 1 * x2@row2
Basic x1 x2 x3 x4 Solution
z -4 -1 0 0 0
x1 1 0 1
5 0 3
5
x2 0 1 -3
5 0 6
5
x4 0 0 1 1 1
3.5 Special Cases in the Simplex Method 117
Basic x1 x2 x3 x4 Solution
z 0 0 1
5 0 18
5
x1 1 0 1
5 0 3
5
x2 0 1 -3
5 0 6
5
x4 0 0 1 1 1
The initial tableau of Phase II is thus given as
Because we are minimizing, x3 must enter the solution. Application of the simplex method will
produce the optimum in one iteration (verify with TORA).
remarks. The removal of the artificial variables and their columns at the end of
Phase I can take place only when they are all nonbasic (as Example 3.4-2 illustrates). If
one or more artificial variables are basic (at zero level) at the end of Phase I, then their
removal requires the following additional steps:
Step 1. Select a zero artificial variable to leave the basic solution and designate its row
as the pivot row. The entering variable can be any nonbasic nonartificial variable with a nonzero (positive or negative) coefficient in the pivot row. Perform
the associated simplex iteration.
Step 2. Remove the column of the (just-leaving) artificial variable from the tableau. If
all the zero artificial variables have been removed, go to Phase II. Otherwise,
go back to Step 1.
The logic behind step 1 is that the feasibility of the remaining basic variables will
not be affected when a zero artificial variable is made nonbasic regardless of whether
the pivot element is positive or negative. Problems 3-47 and 3-48 illustrate this situation. Problem 3-49 provides an additional detail about Phase I calculations.
3.5 sPeciAL cAses in tHe simPLex metHOd
This section considers four special cases that arise in the use of the simplex method.
1. Degeneracy
2. Alternative optima
3. Unbounded solutions
4. Nonexisting (or infeasible) solutions
The remainder of this section presents a theoretical explanation of these situations. It also provides an interpretation of what these special results mean in a real-life
problem.
118 Chapter 3 The Simplex Method and Sensitivity Analysis
3.5.1 degeneracy
In the application of the feasibility condition of the simplex method, a tie for the minimum ratio may occur and can be broken arbitrarily. When this happens, at least one basic
variable will be zero in the next iteration, and the new solution is said to be degenerate.
Degeneracy can cause the simplex iterations to cycle indefinitely, thus never terminating the algorithm. The condition also reveals the possibility of at least one redundant
constraint.
The following example explains the practical and theoretical impacts of degeneracy.