The Two-Phase Method
A clean way out of the Big M headache
Prerequisites: you're already comfortable with the standard Simplex algorithm and the Big M method for
handling ≥ and = constraints. This tutorial builds directly on that.
● What you'll walk away with
Why Big M gets annoying — the procedure for Phase 1 and Phase 2, in plain steps — one complete
worked example, solved by hand, tableau by tableau — and a field guide for reading the final tableau:
unique solution, multiple solutions, infeasible, unbounded, or degenerate.
1. Why do we even need this?
Quick recap first. Plain Simplex needs a free starting point: a basic feasible solution (BFS) that's obvious to
read off the tableau. When every constraint is ≤ with a non-negative RHS, slack variables hand you that
starting point for free — set all real variables to 0, let the slacks equal the RHS, done.
The trouble starts with ≥ or = constraints. There's no slack variable sitting there ready to be a basic variable,
so you can't just read off a starting corner. The Big M method patches this: add an artificial variable to
every such constraint, and slap a huge penalty M on it in the objective function, so the simplex algorithm is
desperate to push it out of the solution as fast as possible.
1.1 So what's actually wrong with Big M?
It works — but it drags three annoyances along with it:
1. M isn't a real number. Textbooks say “let M be sufficiently large,” but that's not something you can
compute with. Pick M too small relative to the other coefficients, and the algorithm can end its run with an
artificial variable still sitting in the basis at a positive value — a solution that looks optimal but is actually
garbage.
2. Symbolic arithmetic by hand is painful. Every entry in the Zj − Cj row becomes an expression like (5
− 3M), and deciding which of two such expressions is “more negative” means comparing the M-terms
first, then the constants — easy to slip up on, especially across several iterations.
3. Numerically it's fragile. If you actually plug in a large number for M on a computer, floating-point
rounding lets that huge number swallow the small, meaningful differences elsewhere in the tableau,
quietly corrupting the arithmetic.
● The Two-Phase fix
Two-Phase throws M away entirely. Instead of one messy problem with a penalty term, you solve two
clean, ordinary simplex problems back to back — both with plain numbers, no symbols, no guessing
how big is “big enough.”
2. The core idea
Think of artificial variables as scaffolding on a building. You need them to get a foothold at the start, but they
have no business being part of the finished structure.
Two-Phase simply separates “get rid of the scaffolding” from “actually build the thing” into two sequential
stages:
PHASE 1
➔ PHASE 2
Ignore the real objective. Drop the artificials.
Minimize the sum of the Bring back the real
artificial variables. objective function.
Goal: reach any feasible Goal: optimize for real,
corner of the real problem. starting from that corner.
If Phase 1 can drive every artificial variable down to zero, you've landed on solid ground — a genuine
feasible corner — and Phase 2 continues the climb from exactly that corner. If it can't, the original problem
was never feasible in the first place, and you stop right there.
3. Setting up (same as Big M)
Nothing new here — this is identical to how you already set up Big M:
Constraint type What you add Starting basic variable
≤ (less-or-equal) + slack S S
≥ (greater-or-equal) − surplus S + artificial A A
= (equality) + artificial A A
Slack and surplus variables always carry a coefficient of 0 in the real objective — they don't cost or earn
anything. Artificial variables are the only ones that get special treatment, and that treatment is the whole
subject of Phase 1.
4. Phase 1 — step by step
1. Write every constraint in standard equality form, adding slack / surplus / artificial variables per the
table above. Make sure every RHS is ≥ 0 (multiply a row by −1 first if it isn't).
2. Build the Phase-1 objective: minimize r = (sum of all artificial variables). Every real variable, slack,
and surplus gets coefficient 0 — only the artificials count. (In max-tableau form: maximize W = −r.)
3. The starting basis is just the artificials and any natural slacks — an immediate, obvious BFS for this
auxiliary problem, since every RHS is ≥ 0.
4. Run ordinary Simplex on this auxiliary problem. Nothing special — the same entering/leaving rules
you already use.
5. Read the result:
All artificials are zero — you've found a genuine BFS of the original problem. Proceed
min r = 0
to Phase 2.
Some artificial refuses to leave, no matter how you pivot. The constraints contradict
min r > 0
each other. Stop — infeasible.
5. Phase 2 — step by step
1. Start from the final Phase-1 tableau — the one where r = 0.
2. Delete every artificial-variable column. They've done their job and don't belong in the real problem.
Exception: if an artificial is still sitting in the basis but at value 0 (a degenerate leftover), pivot it out using
any nonzero entry in its row under a real/slack column — or, if its whole row is zeros, that constraint was
redundant, so just delete the row.
3. Bring back the real objective function — replace the Cj row with the original coefficients for the x's
(slacks/surplus stay at 0).
4. Recompute the Z and Z − C rows for the current basis — these numbers change because the
j j j
objective changed.
5. Continue Simplex iterations exactly as normal until you hit optimality, or detect an unbounded
direction.
● Key thing to notice
Phase 2 does not start over from scratch. It reuses the exact corner point Phase 1 handed you — you're
simply now climbing toward the real objective instead of the artificial one.
6. Worked example, start to finish
Minimize Z = 4x1 + x2
subject to:
3x1 + x2 = 3
4x1 + 3x2 ≥ 6
x1 + 2x2 ≤ 4
x1, x2 ≥ 0
A good mix on purpose: one =, one ≥, one ≤ — so we need one artificial for row 1, a surplus + artificial for
row 2, and a plain slack for row 3.
Row Standard-form equation Basic variable
1 (=) 3x1 + x2 + A1 = 3 A1
2 (≥) 4x1 + 3x2 − S1 + A2 = 6 A2
3 (≤) x1 + 2x2 + S2 = 4 S2
6.1 Phase 1
Auxiliary objective: Maximize W = −A1 − A2 (equivalently, minimize r = A1 + A2). Starting basis: A1, A2, S2.
Iteration 0 (starting tableau)
Basis x1 x2 S1 A1 A2 S2 RHS
A1 3 1 0 1 0 0 3
A2 4 3 -1 0 1 0 6
S2 1 2 0 0 0 1 4
Zj -7 -4 1 -1 -1 0
Zj-Cj -7 -4 1 0 0 0
Most negative Zj−Cj is −7 under x1 → x1 enters. Ratio test (RHS/pivot-col, positive entries only): 3/3=1, 6/4=1.5, 4/1=4 →
row A1 wins → A1 leaves. Pivot = 3.
Iteration 1
Basis x1 x2 S1 A1 A2 S2 RHS
x1 1 1/3 0 1/3 0 0 1
A2 0 5/3 -1 -4/3 1 0 2
S2 0 5/3 0 -1/3 0 1 3
Zj 0 -5/3 1 4/3 -1 0
Zj-Cj 0 -5/3 1 7/3 0 0
Most negative is −5/3 under x2 → x2 enters. Ratios: 1÷(1/3)=3, 2÷(5/3)=1.2, 3÷(5/3)=1.8 → row A2 wins → A2 leaves. Pivot
= 5/3.
Iteration 2 (final)
Basis x1 x2 S1 A1 A2 S2 RHS
x1 1 0 1/5 3/5 -1/5 0 3/5
x2 0 1 -3/5 -4/5 3/5 0 6/5
S2 0 0 1 1 -1 1 1
Zj 0 0 0 0 0 0
Zj-Cj 0 0 0 1 1 0
Every Zj−Cj ≥ 0 → optimal for Phase 1. Both artificials are non-basic (value 0), so min r = 0. The problem is feasible — on to
Phase 2.
● Phase 1 verdict: FEASIBLE
x1 = 3/5, x2 = 6/5, S2 = 1, A1 = A2 = 0. Check it against the original constraints: 3(3/5)+6/5 = 3 ✓,
4(3/5)+3(6/5) = 6 ✓, 3/5+2(6/5)+1 = 4 ✓.
6.2 Phase 2
Drop the A1 and A2 columns entirely. Restore the real objective: Maximize −Z = −4x1 − x2 (C : x1=−4,
j
x2=−1, S1=0, S2=0). We keep the exact same basis Phase 1 ended with — x1, x2, S2 — and just recompute
the Zj row against the new objective.
Iteration 0 (carried over from Phase 1, new objective row)
Basis x1 x2 S1 S2 RHS
x1 1 0 1/5 0 3/5
x2 0 1 -3/5 0 6/5
S2 0 0 1 1 1
Zj -4 -1 -1/5 0
Zj-Cj 0 0 -1/5 0
Only S1 has a negative Zj−Cj (−1/5) → S1 enters. Ratios: (3/5)÷(1/5)=3, (6/5)÷(−3/5) skipped (negative), 1÷1=1 → row S2
wins → S2 leaves. Pivot = 1.
Iteration 1 (final)
Basis x1 x2 S1 S2 RHS
x1 1 0 0 -1/5 2/5
x2 0 1 0 3/5 9/5
S1 0 0 1 1 1
Zj -4 -1 0 1/5
Zj-Cj 0 0 0 1/5
Every Zj−Cj ≥ 0 → optimal. The only non-basic variable, S2, has a strictly positive evaluation (1/5) — so this optimum is
unique (more in §7).
● Final answer
x1 = 2/5, x2 = 9/5, S1 = 1, S2 = 0 → Zmin = 4(2/5) + 1(9/5) = 17/5 = 3.4
7. Reading the final tableau: the five cases
This is the part people usually want a cheat sheet for. Here's what each ending looks like on the tableau, and
what it tells you about the problem.
A — INFEASIBLE
Trigger: Phase 1 reaches optimality with min r > 0 — at least one artificial variable is stuck in the basis at a
positive value, and no pivot can remove it.
What it means: The constraints contradict each other — no point satisfies all of them at once (e.g. x1+x2≤2
together with x1+x2≥5 can never both hold). Stop here; don't run Phase 2 at all.
B — UNIQUE OPTIMAL SOLUTION
Trigger: Phase 2 reaches optimality (all Z −C ≥ 0) and every non-basic variable has a strictly positive Z −C
j j j j
(none equal to 0).
What it means: There is exactly one best corner point. This is what happened in the worked example
above: the only non-basic variable, S2, evaluated to 1/5 — not zero — so that optimum is one-of-a-kind.
C — MULTIPLE (ALTERNATE) OPTIMAL SOLUTIONS
Trigger: Phase 2 reaches optimality, but at least one non-basic variable has Zj−Cj = 0 exactly.
What it means: That variable could be pivoted into the basis without changing the objective value at all —
so there's an entire edge (or face) of equally-good solutions, not just one point.
Tip: pivot that zero-evaluation variable in and see where you land — same Z, different x's; any point on the
segment between the two corners is also optimal.
D — UNBOUNDED SOLUTION
Trigger: During Phase 2, an entering variable is identified (its Z −C < 0, i.e. it would improve the objective),
j j
but every entry in that column is ≤ 0 — the ratio test has no valid candidate row.
What it means: That variable can be pushed to infinity and the objective keeps improving forever without
ever leaving the feasible region. In practice this usually means the real-world model is missing a constraint.
Note: this can't happen in Phase 1 — r is always bounded below by 0, so Phase 1 itself never comes back
unbounded.
E — DEGENERATE SOLUTION
Trigger: In the minimum-ratio test (either phase), two or more rows tie for the smallest ratio.
What it means: Whichever row you choose to leave, some basic variable ends up at value 0 in the very
next tableau — a “squeezed” corner point. Not an error, just a flag.
Usually harmless. In rare pathological cases repeated degeneracy can make the simplex algorithm cycle
(revisit the same tableaus forever). If you ever suspect that, switch to Bland's rule (always break ties by
smallest variable index) to guarantee it terminates.
8. Big M vs. Two-Phase, side by side
Big M Two-Phase
LPs solved 1, with a symbolic penalty M 2, both with plain numbers
Choosing a value Yes — awkward, no exact rule Never needed
Arithmetic style Symbolic (terms carry M around) Ordinary numbers throughout
M too small → wrong answer;
Main risk None of that — just two clean runs
M huge → floating-point trouble
Detecting Artificial stays positive and
Direct: Phase 1 ends with min r > 0
infeasibility M-terms don't cancel out
8.1 Common slip-ups
• Forgetting to flip a row's sign to make its RHS ≥ 0 before adding the artificial variable.
• Leaving the artificial-variable columns in the tableau going into Phase 2 — drop them, or the algorithm
can (meaninglessly) bring one back into the basis.
• Forgetting to recompute the Z and Z −C rows after swapping in the real objective — the Phase-1
j j j
numbers no longer apply once Cj has changed.
9. One-page cheat sheet
1. Convert all constraints to standard equality form; add slack / surplus+artificial / artificial as needed;
ensure RHS ≥ 0.
2. Phase 1: minimize (sum of artificials) using ordinary Simplex.
3. min r = 0 → feasible, go to Phase 2. min r > 0 → STOP, infeasible.
4. Phase 2: drop artificial columns, restore the real objective, recompute Zj / Zj−Cj, keep pivoting.
5. At the final tableau, check the non-basic Zj−Cj values:
Ending Reading
All non-basic Zj−Cj strictly > 0 Unique optimal solution
Some non-basic Zj−Cj = 0 Multiple optimal solutions
Phase 1 ends with min r > 0 Infeasible
Entering column has no positive entries Unbounded
Tie in the minimum-ratio test Degenerate (watch for cycling)
End of tutorial — the worked example in §6 followed exactly this checklist, top to bottom.