The Two-Phase Method in Linear Programming (Step-by-step guide)
Learn how to solve linear programming problems with artificial variables using the Two-Phase Simplex Method, a robust alternative to the Big-M method.
Why the Two-Phase Method Exists
The standard Simplex algorithm requires an initial basic feasible solution (BFS) to start iterating. For problems that contain only ≤ constraints, this is trivial: adding a slack variable to each constraint instantly gives an identity basis, and the origin (all decision variables = 0) is feasible.
However, when a model includes ≥ or = constraints, the origin is no longer feasible, and no obvious initial basis exists. Two strategies address this:
- Big-M Method: Penalise artificial variables heavily in the original objective. Simple to set up, but the presence of an arbitrarily large constant M can cause floating-point precision errors in software implementations.
- Two-Phase Method: Replace the original objective function entirely in a first pass, driving artificial variables out of the basis before the real optimisation begins. Numerically cleaner and preferred in most professional solvers.
Problem Setup: Standard Form
Consider the following linear program (LP):
Maximise Z = 2x&sub1; + 3x&sub2;
Subject to:
x&sub1; + x&sub2; ≤ 4 (constraint 1)
x&sub1; + 2x&sub2; ≥ 6 (constraint 2)
x&sub1;, x&sub2; ≥ 0
To put it in standard form:
- Constraint 1 (≤): add slack variable s&sub1; → x&sub1; + x&sub2; + s&sub1; = 4
- Constraint 2 (≥): subtract surplus variable s&sub2; and add artificial variable a&sub1; → x&sub1; + 2x&sub2; − s&sub2; + a&sub1; = 6
Variables: x&sub1;, x&sub2;, s&sub1;, s&sub2;, a&sub1; ≥ 0. The initial basic variables are s&sub1; and a&sub1; (they form an identity in the constraint matrix).
Phase I: Finding an Initial Basic Feasible Solution
Forget the original objective Z for now. Construct an auxiliary objective:
Minimise W = a&sub1;
If we can drive W to zero, we have removed every artificial variable from the basis, meaning we have a genuine BFS for the original problem.
Step 1 — Build the Phase I Tableau
Because a&sub1; is currently in the basis at value 6, the W-row cannot simply read the column of a&sub1; as zero. We must perform a preliminary row operation to zero out the objective row's coefficient for the basic variable a&sub1;:
W-row = W-row − (constraint 2)
⇒ W = −x&sub1; − 2x&sub2; + s&sub2; − a&sub1; + a&sub1; = −6 ... after cancellation:
W + x&sub1; + 2x&sub2; − s&sub2; = 6
Initial Phase I tableau (W-row at top; RHS column last):
| BV | x&sub1; | x&sub2; | s&sub1; | s&sub2; | a&sub1; | RHS |
|---|---|---|---|---|---|---|
| W | 1 | 2 | 0 | −1 | 0 | 6 |
| s&sub1; | 1 | 1 | 1 | 0 | 0 | 4 |
| a&sub1; | 1 | 2 | 0 | −1 | 1 | 6 |
Step 2 — Iteration 1
- Entering variable: Most negative in W-row (here, minimising, so most positive reduced cost). Column x&sub2; (coefficient 2) enters.
- Minimum ratio test: Row s&sub1;: 4/1 = 4; Row a&sub1;: 6/2 = 3 ← minimum. a&sub1; leaves.
- Pivot: Divide pivot row (a&sub1;) by 2, then eliminate x&sub2; from all other rows.
Tableau after pivot:
| BV | x&sub1; | x&sub2; | s&sub1; | s&sub2; | a&sub1; | RHS |
|---|---|---|---|---|---|---|
| W | 0 | 0 | 0 | 0 | −1 | 0 |
| s&sub1; | 1/2 | 0 | 1 | 1/2 | −1/2 | 1 |
| x&sub2; | 1/2 | 1 | 0 | −1/2 | 1/2 | 3 |
W = 0. All artificial variables are zero and out of the basis. Phase I is complete. The BFS at this point is: x&sub1; = 0, x&sub2; = 3, s&sub1; = 1, s&sub2; = 0.
Phase II: Optimising the Original Objective
Now that we have a genuine BFS, we switch to the original objective Z = 2x&sub1; + 3x&sub2;. Drop the a&sub1; column entirely and replace the W-row with the original Z-row, re-expressed in terms of the current non-basic variables.
Step 3 — Set Up the Phase II Tableau
Current basis: {s&sub1;, x&sub2;}. The original objective in terms of non-basics requires updating the Z-row:
Z = 2x&sub1; + 3x&sub2;
= 2x&sub1; + 3(3 − x&sub1;/2 + s&sub2;/2) [substituting the x&sub2;-row]
= 9 + x&sub1;/2 + 3s&sub2;/2
Phase II tableau:
| BV | x&sub1; | x&sub2; | s&sub1; | s&sub2; | RHS |
|---|---|---|---|---|---|
| Z | −1/2 | 0 | 0 | −3/2 | −9 |
| s&sub1; | 1/2 | 0 | 1 | 1/2 | 1 |
| x&sub2; | 1/2 | 1 | 0 | −1/2 | 3 |
(Z-row uses the standard convention: Z − cTx = 0, so negative coefficients indicate improving directions.)
Step 4 — Iteration 2
- Entering variable: Most negative Z-row coefficient is −3/2 in column s&sub2;. s&sub2; enters.
- Minimum ratio test: Row s&sub1;: 1 ÷ (1/2) = 2; Row x&sub2;: 3 ÷ 0 = ∞ (negative, ignored). s&sub1; leaves.
- Pivot: Divide pivot row (s&sub1;) by 1/2 → multiply by 2, then eliminate s&sub2; from other rows.
Final Phase II tableau:
| BV | x&sub1; | x&sub2; | s&sub1; | s&sub2; | RHS |
|---|---|---|---|---|---|
| Z | 2 | 0 | 3 | 0 | −12 |
| s&sub2; | 1 | 0 | 2 | 1 | 2 |
| x&sub2; | 1 | 1 | 1 | 0 | 4 |
All Z-row coefficients are non-negative → optimal solution reached.
- x&sub1; = 0, x&sub2; = 4, Z = 12
- s&sub2; = 2 (constraint 2 has 2 units of surplus)
What If Phase I Ends with W > 0?
If after all Simplex iterations on the Phase I problem the minimum value of W is strictly greater than zero, at least one artificial variable remains in the basis with a positive value. This means no point in the original feasible region exists — the problem is infeasible. Stop immediately; there is no point proceeding to Phase II.
Two-Phase vs. Big-M: A Comparison
| Property | Two-Phase Method | Big-M Method |
|---|---|---|
| Numerical stability | High (no large constants) | Lower (M can cause precision loss) |
| Ease of setup | Moderate (two separate LPs) | Simple (one LP, single pass) |
| Infeasibility detection | W > 0 at end of Phase I | Artificial variable in final basis |
| Software preference | Preferred by most solvers | Common in manual textbook examples |
Conclusion
The Two-Phase Method is the gold standard for handling ≥ and = constraints in linear programming. By cleanly separating feasibility detection (Phase I) from true optimisation (Phase II), it avoids the numerical pitfalls of an arbitrary large penalty and provides a clear, unambiguous signal when a problem has no feasible solution.