Two Phase Simplex Method (Worked Example): Phase 1 (Find Feasibility) + Phase 2 (Optimize) with Fully Solved Tableaus
Two-phase simplex is the standard way to start simplex when you donβt have an obvious initial basic feasible solution
(common with = or β₯ constraints). This page includes multiple fully solved worked examples, including an infeasible LP.
If youβre new to LPs, start with Linear Programming (LP) β Beginner Guide. To verify any final answer quickly, use the Linear Programming calculator.
On this page
- Quick takeaway
- When do you need two-phase simplex?
- Step 0: Convert to standard form (slack, surplus, artificial)
- Phase 1: Build and solve the auxiliary problem
- Phase 2: Restore the original objective and optimize
- Two-phase vs BigβM (whatβs different)
- Questions people ask (two-phase simplex)
- Worked examples (fully solved)
- Check your answer (calculator + next guides)
- Common mistakes (fast debug list)
- Glossary
Quick takeaway: Two-phase simplex is simplex with a disciplined start.
Phase 1 adds artificial variables and minimizes
w = Ξ£ artificial to find feasibility.
If Phase 1 ends with w* = 0, the original LP is feasible; then Phase 2 drops artificials
and optimizes the original objective.
If Phase 1 ends with w* > 0, the original LP is infeasible
(see also Unbounded vs Infeasible LP (Fix Checklist)).
When do you need two-phase simplex?
Rule of thumb
Use two-phase when you canβt read off an initial basic feasible solution
Standard simplex needs a starting basis that looks like an identity matrix and gives nonnegative basic values.
You usually get this immediately when all constraints are β€ with b β₯ 0 (slack variables form the basis).
You typically need two-phase when you have:
- Equality constraints (
=) - βGreater-thanβ constraints (
β₯) - Mixed constraint types where slack variables alone canβt create a valid basis
Step 0: Convert to standard form (slack, surplus, artificial)
Setup
How each constraint type is standardized
| Original constraint | Convert to equality | What variables appear? | Why artificial may be needed |
|---|---|---|---|
aα΅x β€ b |
aα΅x + s = b |
Slack s β₯ 0 |
Slack can be a starting basic variable |
aα΅x β₯ b |
aα΅x β s + a = b |
Surplus s β₯ 0 and artificial a β₯ 0 |
Surplus has coefficient -1, so you add an artificial to start |
aα΅x = b |
aα΅x + a = b |
Artificial a β₯ 0 |
No slack/surplus exists, so you add artificial to start |
After standardization, the only remaining question is: do you have a valid starting basis? If not, Phase 1 creates one.
Phase 1: Build and solve the auxiliary problem
Phase 1
Objective: drive artificial variables to zero
Let A be the set of artificial variables. Phase 1 solves:
minimize w = Ξ£_{a β A} a
subject to (standard-form constraints)
all variables β₯ 0
Interpretation:
- If the minimum is
w* = 0, the original LP is feasible. - If the minimum is
w* > 0, the original LP is infeasible.
Phase 2: Restore the original objective and optimize
Phase 2
Drop artificials, keep feasibility, then run simplex normally
- Confirm
w* = 0at the end of Phase 1. - Remove artificial-variable columns (theyβre not part of the original LP).
- Restore the original objective and canonicalize it w.r.t. the current basis.
- Run simplex until the optimality condition holds.
If youβre comparing methods: Dual Simplex Method is another simplex variant, but it serves a different purpose (useful when the tableau is optimal but infeasible).
Two-phase vs BigβM (whatβs different)
Comparison
Same idea; different numerical behavior
- BigβM method: keeps artificials in the original objective with a large penalty
M. Itβs compact but can be numerically delicate. - Two-phase: separates feasibility (Phase 1) from optimization (Phase 2), avoiding the need to choose
M.
If you want the penalty approach, see Big M Method Explained.
Questions people ask about the two-phase simplex method (PAA)
People ask
What is the two-phase simplex method?
The two-phase simplex method is a simplex start-up procedure used when there is no obvious initial basic feasible solution. It uses Phase 1 to find feasibility by minimizing the sum of artificial variables, then runs Phase 2 to optimize the original LP objective.
People ask
When do you use the two-phase simplex method instead of the simplex method?
You use two-phase when your constraints include = or β₯ (or other forms that prevent slack variables from forming an identity basis).
If your model is a clean β€ system with b β₯ 0, the standard simplex start is usually enough.
People ask
How do you form the Phase 1 objective function?
Add artificial variables where needed, then set the auxiliary objective to minimize
w = a1 + a2 + .... In tableau form, you must also canonicalize the Phase 1 objective row
by eliminating the artificial basic-variable coefficients using row operations.
People ask
What if the Phase 1 optimal value is not zero?
If w* > 0, the original LP has no feasible solution.
Use Unbounded vs Infeasible LP (Fix Checklist) to debug (bounds, sign mistakes, inconsistent requirements).
People ask
What is the difference between the two-phase method and the BigβM method?
Both introduce artificial variables. The BigβM method penalizes artificials directly in the original objective using a large M.
Two-phase separates feasibility from optimization, avoiding βchoose a huge M,β which is one reason itβs cleaner for hand calculations.
People ask
How do you check your final simplex answer quickly?
Solve the same model in the Linear Programming calculator. If itβs a 2-variable model, also confirm with the Graphical Method for LP (2 Variables).
Worked examples (fully solved)
Worked examples
Expand only the example you need
Each example below is collapsible (collapsed by default) to keep the page scannable while remaining fully indexable by search engines.
Example 1 β Two phase simplex method example (feasible LP with = and β₯ constraints)
Original LP (maximize):
maximize z = 3x1 + 2x2
subject to x1 + x2 = 4
x1 + 2x2 β₯ 6
x1, x2 β₯ 0
Step 1: Convert to standard form
Equality constraint needs an artificial variable a1.
The β₯ constraint needs a surplus variable s2 and an artificial variable a2.
(If you want the βwhyβ explained: Slack / Surplus / Artificial Variables.)
(1) x1 + x2 + a1 = 4
(2) x1 + 2x2 β s2 + a2 = 6
x1, x2, s2, a1, a2 β₯ 0
Step 2: Phase 1 objective (feasibility)
Phase 1 minimizes w = a1 + a2. For a simplex maximization tableau, itβs convenient to maximize P = βw.
Using the two constraints to eliminate a1 and a2 from w:
a1 = 4 β x1 β x2 a2 = 6 β x1 β 2x2 + s2 w = a1 + a2 = 10 β 2x1 β 3x2 + s2 P = βw = β10 + 2x1 + 3x2 β s2
So in canonical row form:
P β 2x1 β 3x2 + s2 = β10
Phase 1 β Initial tableau (already canonicalized)
| Basis | x1 | x2 | s2 | a1 | a2 | RHS |
|---|---|---|---|---|---|---|
| a1 | 1 | 1 | 0 | 1 | 0 | 4 |
| a2 | 1 | 2 | -1 | 0 | 1 | 6 |
| P = -w | -2 | -3 | 1 | 0 | 0 | -10 |
Phase 1 β Pivot 1 (enter x2, leave a2)
Entering variable: x2 (most negative in P row is -3).
Ratio test among positive x2 coefficients:
Row a1: 4 / 1 = 4 Row a2: 6 / 2 = 3 β smallest, so a2 leaves
| Basis | x1 | x2 | s2 | a1 | a2 | RHS |
|---|---|---|---|---|---|---|
| a1 | 0.5 | 0 | 0.5 | 1 | -0.5 | 1 |
| x2 | 0.5 | 1 | -0.5 | 0 | 0.5 | 3 |
| P = -w | -0.5 | 0 | -0.5 | 0 | 1.5 | -1 |
Conceptually: a real variable (x2) entered the basis and an artificial moved out, pushing toward feasibility.
Phase 1 β Pivot 2 (enter x1, leave a1)
Entering variable: x1 (negative coefficient -0.5).
Ratio test on x1:
Row a1: 1 / 0.5 = 2 β smallest, so a1 leaves Row x2: 3 / 0.5 = 6
| Basis | x1 | x2 | s2 | a1 | a2 | RHS |
|---|---|---|---|---|---|---|
| x1 | 1 | 0 | 1 | 2 | -1 | 2 |
| x2 | 0 | 1 | -1 | -1 | 1 | 2 |
| P = -w | 0 | 0 | 0 | 1 | 1 | 0 |
Phase 1 optimum is P* = 0 which implies w* = 0.
Therefore the original LP is feasible.
Phase 2 β Restore the original objective and optimize
Drop artificial columns a1 and a2. With nonbasic s2 = 0, the basic solution is:
x1 = 2 x2 = 2
Objective value:
z = 3x1 + 2x2 = 3(2) + 2(2) = 10
From the Phase 2 equations (after dropping artificials), you can express:
x1 + s2 = 2 β x1 = 2 β s2 x2 β s2 = 2 β x2 = 2 + s2 z = 3(2 β s2) + 2(2 + s2) = 10 β s2
Since s2 β₯ 0, the maximum occurs at s2 = 0.
Optimal solution (Example 1): x1 = 2, x2 = 2, z* = 10.
Example 2 β Two phase simplex method example (infeasible LP; Phase 1 returns w* > 0)
Original LP:
maximize z = x1 + x2
subject to x1 + x2 = 1
x1 + x2 β₯ 3
x1, x2 β₯ 0
The constraints contradict each other. Two-phase simplex detects this in Phase 1 because it cannot drive all artificials to zero.
Step 1: Standard form
(1) x1 + x2 + a1 = 1
(2) x1 + x2 β s2 + a2 = 3
x1, x2, s2, a1, a2 β₯ 0
Step 2: Phase 1 objective
minimize w = a1 + a2
Step 3: Solve Phase 1 (a clean certificate that w* > 0)
Subtract constraint (1) from constraint (2):
(2) β (1): (x1+x2 β s2 + a2) β (x1+x2 + a1) = 3 β 1
βs2 + a2 β a1 = 2
So: a2 = 2 + s2 + a1 β₯ 2 (because s2 β₯ 0 and a1 β₯ 0)
Therefore:
w = a1 + a2 β₯ a1 + 2 + s2 + a1 = 2 + s2 + 2a1 β₯ 2
This lower bound is achievable (e.g., choose a1=0, s2=0, a2=2 and any (x1,x2) with x1+x2=1).
Hence w* = 2.
Phase 1 result (Example 2): w* = 2 > 0 β the original LP is infeasible.
Use Unbounded vs Infeasible LP (Fix Checklist) to diagnose modeling/data causes.
Example 3 β Two phase simplex method example (minimization with β₯ constraints)
Original LP (minimize):
minimize z = 2x1 + x2
subject to x1 + x2 β₯ 2
x1 + 2x2 β₯ 3
x1, x2 β₯ 0
Step 1: Standard form (surplus + artificial variables)
(1) x1 + x2 β s1 + a1 = 2
(2) x1 + 2x2 β s2 + a2 = 3
x1, x2, s1, s2, a1, a2 β₯ 0
Step 2: Phase 1 objective
minimize w = a1 + a2 (equivalently maximize P = βw)
Canonical Phase 1 objective (eliminate artificials using the constraints):
a1 = 2 β x1 β x2 + s1 a2 = 3 β x1 β 2x2 + s2 w = 5 β 2x1 β 3x2 + s1 + s2 P = βw = β5 + 2x1 + 3x2 β s1 β s2 So: P β 2x1 β 3x2 + s1 + s2 = β5
Phase 1 β Initial tableau (canonicalized)
| Basis | x1 | x2 | s1 | s2 | a1 | a2 | RHS |
|---|---|---|---|---|---|---|---|
| a1 | 1 | 1 | -1 | 0 | 1 | 0 | 2 |
| a2 | 1 | 2 | 0 | -1 | 0 | 1 | 3 |
| P = -w | -2 | -3 | 1 | 1 | 0 | 0 | -5 |
Phase 1 β Pivot 1 (enter x2, leave a2)
Enter x2 (most negative is -3). Ratio test:
Row a1: 2/1 = 2 Row a2: 3/2 = 1.5 β smallest, so a2 leaves
| Basis | x1 | x2 | s1 | s2 | a1 | a2 | RHS |
|---|---|---|---|---|---|---|---|
| a1 | 0.5 | 0 | -1 | 0.5 | 1 | -0.5 | 0.5 |
| x2 | 0.5 | 1 | 0 | -0.5 | 0 | 0.5 | 1.5 |
| P = -w | -0.5 | 0 | 1 | -0.5 | 0 | 1.5 | -0.5 |
Phase 1 β Pivot 2 (enter x1, leave a1)
Enter x1 (negative coefficient -0.5). Ratio test:
Row a1: 0.5 / 0.5 = 1 β smallest, so a1 leaves Row x2: 1.5 / 0.5 = 3
| Basis | x1 | x2 | s1 | s2 | a1 | a2 | RHS |
|---|---|---|---|---|---|---|---|
| x1 | 1 | 0 | -2 | 1 | 2 | -1 | 1 |
| x2 | 0 | 1 | 1 | -1 | -1 | 1 | 1 |
| P = -w | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
Phase 1 ends with w* = 0 β the LP is feasible.
Now drop artificial variables and optimize the original objective.
Phase 2 β Optimize the original objective (minimize z = 2x1 + x2)
To keep the same βmaximize tableauβ convention, maximize Q = βz.
After removing a1 and a2, the basis is {x1, x2}.
Phase 2 starting tableau (columns shown: x1, x2, s1, s2):
| Basis | x1 | x2 | s1 | s2 | RHS |
|---|---|---|---|---|---|
| x1 | 1 | 0 | -2 | 1 | 1 |
| x2 | 0 | 1 | 1 | -1 | 1 |
| Q = -z (canonical) | 0 | 0 | 3 | -1 | -3 |
The objective row has a negative coefficient at s2 (-1), so s2 enters.
Ratio test uses rows with positive s2 coefficients:
Row x1: RHS / s2 = 1 / 1 = 1 β x1 leaves Row x2: s2 coefficient is -1 (not eligible)
Phase 2 β Pivot (enter s2, leave x1)
| Basis | x1 | x2 | s1 | s2 | RHS |
|---|---|---|---|---|---|
| s2 | 1 | 0 | -2 | 1 | 1 |
| x2 | 1 | 1 | -1 | 0 | 2 |
| Q = -z | 1 | 0 | 1 | 0 | -2 |
Now there are no negative coefficients in the objective row, so the current solution is optimal for maximizing Q = -z,
hence optimal for minimizing z.
Set nonbasic variables to 0: x1 = 0, s1 = 0. Then from the basic rows:
From row x2: x2 = 2 From row s2: s2 = 1
Optimal solution (Example 3): x1 = 0, x2 = 2, and z* = 2.
Check your answer (calculator + next guides)
Tooling + learning path
Fast verification + what to read next
To verify any worked example quickly, solve it in the Linear Programming calculator. For 2-variable problems, you can also confirm visually using Graphical Method for LP (2 Variables).
If your solution reports more than one optimum, see Multiple Optimal Solutions in LP. For primalβdual intuition, see PrimalβDual Relationship in LP. For implementations: Linear Programming in Excel Solver and Linear Programming in Python (PuLP/OR Tools).
x must be integers/binaries), simplex is not enough:
use Integer Linear Programming (ILP/MILP) and expect
branch-and-bound (and sometimes
cutting planes).
Common mistakes (fast debug list)
Troubleshooting
If Phase 1 βdoesnβt work,β itβs usually one of these
| Symptom | Likely mistake | Fix |
|---|---|---|
| Phase 1 objective row still depends on artificial basic variables | Objective row not canonicalized | Eliminate artificial columns from Phase 1 objective row using row operations before pivoting |
| Surplus/slack sign confusion | Used +s for a β₯ constraint |
For β₯, use βs (surplus) then add artificial if needed |
Phase 1 ends with w* > 0, but you expected feasibility |
Model is genuinely infeasible or data inconsistent | Use Unbounded vs Infeasible LP (Fix Checklist) |
| Phase 2 behaves oddly after dropping artificials | Dropped an artificial while it was still in the basis | Pivot it out first (or handle the redundancy/zero-row case carefully) |
Glossary
Glossary
- Basic feasible solution (BFS): feasible solution obtained by setting nonbasic variables to 0 and solving for basic variables.
- Slack variable: converts
β€into equality via+s. - Surplus variable: converts
β₯into equality viaβs. - Artificial variable: temporary variable used to create an initial basis when slack/surplus cannot.
- Phase 1 objective (w): feasibility measure via sum of artificials.
- Canonical objective row: objective row with 0 coefficients under basic-variable columns.
Disclaimer
This article and the associated calculators are provided for educational and informational purposes only. Optimization outcomes depend on modeling assumptions and input data and may not reflect real-world constraints unless you encode them correctly. This is not legal, financial, operational, or safety advice. For high-stakes decisions, validate results against domain requirements and consult a qualified professional. For details, read our full disclaimer.