Lesson 6: Big-M, Two-Phase Methods and Special Cases¶
6.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Explain why \(\ge\) and \(=\) constraints need artificial variables.
- Apply the Big-M method and interpret its tableaus.
- Apply the two-phase method and know when to prefer it.
- Detect infeasibility, unboundedness, alternate optima and degeneracy from a tableau.
- Diagnose and repair a failing model.
6.2 Why Artificial Variables Are Needed¶
Simplex requires a starting basic feasible solution. When every constraint is \(\le\) with \(b_i \ge 0\), the slacks provide one immediately: set all real variables to zero and read \(s_i = b_i \ge 0\). The origin is feasible.
With a \(\ge\) constraint this fails. Consider \(3x_1 + x_2 \ge 6\). In standard form,
Setting \(x_1 = x_2 = 0\) gives \(s_1 = -6 < 0\) — not feasible. The surplus variable enters with coefficient \(-1\), so it cannot be a starting basic variable.
Similarly for \(=\): \(3x_1+x_2 = 3\) has no slack at all, so no basic variable exists in that row.
The fix. Add an artificial variable \(A_i \ge 0\) with coefficient \(+1\):
Now \(A_1 = 6\) and \(A_2 = 3\) give a starting basis. But this solves a different problem — the artificials must be driven to zero before the answer means anything.
6.3 The Big-M Method¶
Idea. Attach a huge penalty \(M\) to each artificial variable so that the optimiser expels them automatically.
with \(M\) larger than any number that could otherwise arise.
The three outcomes.
| At optimality | Conclusion |
|---|---|
| All \(A_i = 0\) | the solution is optimal for the original problem ✓ |
| Some \(A_i > 0\) | the original problem is INFEASIBLE |
| \(Z\) unbounded with all \(A_i = 0\) | the original problem is UNBOUNDED |
Handling M in the tableau¶
Entries in the \(z_j - c_j\) row become expressions like \(-6996\) or, symbolically, \(-7M + 4\). Two equivalent conventions:
- Symbolic: keep \(M\) as a symbol and compare coefficients of \(M\) first, then the constants.
- Numeric: set \(M\) to a large number (say 1000, safely above any coefficient in the problem).
This lesson uses \(M = 1000\) for readability; the symbolic form is given alongside.
6.4 Worked Big-M Example¶
Standard form. Convert to maximisation of \(Z' = -4x_1 - x_2\):
Iteration 0¶
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_2\) | \(A_1\) | \(A_2\) | \(s_3\) | RHS | Ratio |
|---|---|---|---|---|---|---|---|---|---|
| \(A_1\) | \(-M\) | 3 | 1 | 0 | 1 | 0 | 0 | 3 | \(1\) ← |
| \(A_2\) | \(-M\) | 4 | 3 | −1 | 0 | 1 | 0 | 6 | \(3/2\) |
| \(s_3\) | 0 | 1 | 2 | 0 | 0 | 0 | 1 | 4 | \(4\) |
| \(z_j-c_j\) | \(-7M{+}4\) | \(-4M{+}1\) | \(M\) | 0 | 0 | 0 | \(-9M\) |
With \(M = 1000\): \(z_j-c_j = (-6996,\ -3999,\ 1000,\ 0,\ 0,\ 0)\), \(Z' = -9000\).
Entering \(x_1\) (most negative). Ratios \(\{1,\ 3/2,\ 4\}\) ⟹ leaving \(A_1\). Pivot 3.
Iteration 1¶
Row 1 ÷ 3; then eliminate.
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_2\) | \(A_1\) | \(A_2\) | \(s_3\) | RHS | Ratio |
|---|---|---|---|---|---|---|---|---|---|
| \(x_1\) | −4 | 1 | \(1/3\) | 0 | \(1/3\) | 0 | 0 | 1 | \(3\) |
| \(A_2\) | \(-M\) | 0 | \(5/3\) | −1 | \(-4/3\) | 1 | 0 | 2 | \(6/5\) ← |
| \(s_3\) | 0 | 0 | \(5/3\) | 0 | \(-1/3\) | 0 | 1 | 3 | \(9/5\) |
| \(z_j-c_j\) | 0 | \(-1667\) | \(1000\) | \(2332\) | 0 | 0 | \(-2004\) |
(Symbolically \(z_2-c_2 = -\frac53M + \frac13\).)
\(A_1\) has left the basis ✓ — one down, one to go. Entering \(x_2\), leaving \(A_2\), pivot \(5/3\).
Iteration 2¶
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_2\) | \(A_1\) | \(A_2\) | \(s_3\) | RHS | Ratio |
|---|---|---|---|---|---|---|---|---|---|
| \(x_1\) | −4 | 1 | 0 | \(1/5\) | \(3/5\) | \(-1/5\) | 0 | \(3/5\) | \(3\) |
| \(x_2\) | −1 | 0 | 1 | \(-3/5\) | \(-4/5\) | \(3/5\) | 0 | \(6/5\) | — |
| \(s_3\) | 0 | 0 | 0 | 1 | 1 | −1 | 1 | 1 | \(1\) ← |
| \(z_j-c_j\) | 0 | 0 | \(-1/5\) | \(4992/5\) | \(5001/5\) | 0 | \(-18/5\) |
Both artificials are now out of the basis ✓, and \(Z' = -\frac{18}{5}\), i.e. \(Z = 3.6\).
But not yet optimal: \(z_{s_2} - c_{s_2} = -\frac15 < 0\). Entering \(s_2\), leaving \(s_3\), pivot 1.
Iteration 3¶
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_2\) | \(A_1\) | \(A_2\) | \(s_3\) | RHS |
|---|---|---|---|---|---|---|---|---|
| \(x_1\) | −4 | 1 | 0 | 0 | \(2/5\) | 0 | \(-1/5\) | 2/5 |
| \(x_2\) | −1 | 0 | 1 | 0 | \(-1/5\) | 0 | \(3/5\) | 9/5 |
| \(s_2\) | 0 | 0 | 0 | 1 | 1 | −1 | 1 | 1 |
| \(z_j-c_j\) | 0 | 0 | 0 | \(4993/5\) | \(1000\) | \(1/5\) | \(-17/5\) |
All \(z_j-c_j \ge 0\) ⟹ OPTIMAL.
Verification against the original problem.
Both artificials are zero, so the answer is valid for the original problem.
Note the near-miss at iteration 2. Both artificials had left, yet the solution \((0.6,\ 1.2)\) with \(Z = 3.6\) was not optimal. Expelling the artificials makes the solution feasible, not optimal — the algorithm must continue until the \(z_j-c_j\) test passes.
6.5 The Two-Phase Method¶
Idea. Split the work into two clean stages instead of juggling \(M\).
Phase I — find feasibility. Replace the objective by
subject to the same constraints.
- If \(W^{*} > 0\) ⟹ the original problem is INFEASIBLE. Stop.
- If \(W^{*} = 0\) ⟹ a BFS of the original problem has been found. Proceed.
Phase II — find optimality. Drop the artificial columns, restore the original objective, recompute the \(z_j - c_j\) row, and continue simplex from the Phase I final tableau.
Big-M versus two-phase¶
| Big-M | Two-phase | |
|---|---|---|
| Number of tableaus | fewer | more |
| Arithmetic | mixes \(M\) with ordinary numbers | clean numbers throughout |
| Numerical stability | poor — huge \(M\) swamps small coefficients in floating point | good |
| Infeasibility detection | at the end | at the end of Phase I — earlier |
| Hand calculation | fine | fine |
| Computer implementation | avoided | used in practice |
Why Big-M fails numerically. With \(M = 10^{6}\) and a genuine coefficient of \(10^{-3}\), double precision (≈16 significant digits) cannot represent their sum accurately. Round-off then corrupts the \(z_j-c_j\) signs and the algorithm terminates at a wrong basis.
Phase I on the same example¶
Iteration 0. \(c_B = (-1,-1,0)\), \(W = 3+6 = 9\). The \(z_j-c_j\) row is obtained by summing the artificial rows and negating the real-variable entries:
Entering \(x_1\), leaving \(A_1\) — the same pivots as Big-M, because the \(M\)-terms dominated there and the \(M\)-terms are the Phase I objective.
Phase I terminates at iteration 2 with \(W^{*} = 0\) and the BFS \((x_1, x_2) = (0.6, 1.2)\).
Phase II restores \(\max\ Z' = -4x_1 - x_2\), recomputes \(z_j-c_j\), finds \(z_{s_2}-c_{s_2} = -\frac15\), performs the one remaining pivot, and reaches the same optimum.
6.6 The Four Special Cases in the Tableau¶
| Case | Tableau signature | Action |
|---|---|---|
| Infeasible | some \(A_i > 0\) at optimality (or \(W^{*}>0\) in Phase I) | relax a constraint |
| Unbounded | entering column has no positive entry | add the missing constraint |
| Alternate optima | a non-basic variable has \(z_j - c_j = 0\) | pivot to find the second optimum |
| Degenerate | a basic variable equals 0 | continue; watch for stalling |
6.7 Solved Problems¶
Problem 1 — Detecting infeasibility with Big-M¶
Solve \(\max\ Z = 3x_1+2x_2\) s.t. \(x_1+x_2 \le 4\), \(x_1+x_2\ge 8\), \(x_1,x_2\ge0\).
Solution.
Standard form.
Iteration 0. Basis \(\{s_1, A_1\}\), \(Z = -8M\).
Entering \(x_1\); ratios \(\frac41 = 4\) and \(\frac81 = 8\) ⟹ leaving \(s_1\), pivot 1.
Iteration 1.
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(A_1\) | RHS |
|---|---|---|---|---|---|---|---|
| \(x_1\) | 3 | 1 | 1 | 1 | 0 | 0 | 4 |
| \(A_1\) | \(-M\) | 0 | 0 | −1 | −1 | 1 | 4 |
| \(z_j-c_j\) | 0 | 1 | \(M+3\) | \(M\) | 0 | \(12-4M\) |
All \(z_j - c_j \ge 0\) (since \(M\) is large) ⟹ the algorithm STOPS.
But \(A_1 = 4 > 0\).
Why, obviously. The constraints demand \(x_1+x_2 \le 4\) and \(x_1+x_2\ge8\) simultaneously — impossible since \(4 < 8\).
What the tableau tells us more precisely. The final \(Z = 12 - 4M\) contains the term \(-4M\): the "cost" of the infeasibility is 4 units of violation. Modern solvers report exactly this — the minimum total constraint violation — which points the modeller straight at the problem.
Practical response. Either the capacity 4 is wrong, or the requirement 8 is wrong. The infeasibility of 4 units tells management exactly how much extra capacity (or how much demand reduction) would be needed.
Problem 2 — Two-phase method, complete¶
Solve by two-phase: \(\min\ Z = 2x_1+3x_2\) s.t. \(x_1+x_2\ge5\), \(x_1+2x_2\ge6\), \(x_1,x_2\ge0\).
Solution.
Standard form.
PHASE I: min W = A₁+A₂, i.e. max -A₁-A₂¶
Iteration 0. Basis \(\{A_1,A_2\}\), \(W = 5+6 = 11\).
| Basis | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(A_1\) | \(A_2\) | RHS | Ratio |
|---|---|---|---|---|---|---|---|---|
| \(A_1\) | 1 | 1 | −1 | 0 | 1 | 0 | 5 | 5 |
| \(A_2\) | 1 | 2 | 0 | −1 | 0 | 1 | 6 | 3 ← |
| \(z_j-c_j\) | −2 | −3 | 1 | 1 | 0 | 0 | \(W=11\) |
Entering \(x_2\); leaving \(A_2\); pivot 2.
Iteration 1. Row 2 ÷ 2: \((\frac12,\ 1,\ 0,\ -\frac12,\ 0,\ \frac12\ |\ 3)\). Row 1 ← row 1 − (new row 2): \((\frac12,\ 0,\ -1,\ \frac12,\ 1,\ -\frac12\ |\ 2)\).
| Basis | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(A_1\) | RHS | Ratio |
|---|---|---|---|---|---|---|---|
| \(A_1\) | \(1/2\) | 0 | −1 | \(1/2\) | 1 | 2 | 4 ← |
| \(x_2\) | \(1/2\) | 1 | 0 | \(-1/2\) | 0 | 3 | 6 |
| \(z_j-c_j\) | \(-1/2\) | 0 | 1 | \(-1/2\) | 0 | \(W=2\) |
Entering \(x_1\); leaving \(A_1\); pivot \(\frac12\).
Iteration 2. Row 1 ÷ \(\frac12\): \((1,\ 0,\ -2,\ 1\ |\ 4)\). Row 2 ← row 2 − \(\frac12\)(new row 1): \((0,\ 1,\ 1,\ -1\ |\ 1)\).
| Basis | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | RHS |
|---|---|---|---|---|---|
| \(x_1\) | 1 | 0 | −2 | 1 | 4 |
| \(x_2\) | 0 | 1 | 1 | −1 | 1 |
| \(z_j-c_j\) | 0 | 0 | 0 | 0 | \(W = \mathbf{0}\) |
Both artificials have left the basis, and \((x_1, x_2) = (4, 1)\) is a BFS of the original problem.
PHASE II: min Z = 2x₁ + 3x₂¶
Drop the artificial columns and restore the true objective. With \(c_B = (2, 3)\):
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | RHS |
|---|---|---|---|---|---|---|
| \(x_1\) | 2 | 1 | 0 | −2 | 1 | 4 |
| \(x_2\) | 3 | 0 | 1 | 1 | −1 | 1 |
| \(z_j-c_j\) | 0 | 0 | −1 | −1 | \(Z = 11\) |
For a MINIMISATION in this form, optimality requires \(z_j - c_j \le 0\). Both are \(-1 \le 0\) ✓.
Verification.
Graphical cross-check. The corners of the feasible region are \((6,0)\) with \(Z = 12\), \((4,1)\) with \(Z = 11\), and \((0,5)\) with \(Z = 15\). Minimum is \((4,1)\), \(Z = 11\) ✓.
Problem 3 — Detecting unboundedness¶
Solve \(\max\ Z = 2x_1 + x_2\) s.t. \(x_1 - x_2 \le 10\), \(2x_1 - x_2 \le 40\), \(x_1,x_2\ge0\).
Solution.
Iteration 0. Basis \(\{s_1, s_2\}\).
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | RHS | Ratio |
|---|---|---|---|---|---|---|---|
| \(s_1\) | 0 | 1 | −1 | 1 | 0 | 10 | 10 ← |
| \(s_2\) | 0 | 2 | −1 | 0 | 1 | 40 | 20 |
| \(z_j-c_j\) | −2 | −1 | 0 | 0 | 0 |
Entering \(x_1\); ratios \(\{10, 20\}\); leaving \(s_1\); pivot 1.
Iteration 1. Row 2 ← row 2 − 2(row 1).
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | RHS |
|---|---|---|---|---|---|---|
| \(x_1\) | 2 | 1 | −1 | 1 | 0 | 10 |
| \(s_2\) | 0 | 0 | 1 | −2 | 1 | 20 |
| \(z_j-c_j\) | 0 | −3 | 2 | 0 | 20 |
Entering \(x_2\) (\(-3\)). Column entries: \((-1,\ 1)^T\). Ratio for row 2: \(20/1 = 20\). Leaving \(s_2\).
Iteration 2.
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | RHS |
|---|---|---|---|---|---|---|
| \(x_1\) | 2 | 1 | 0 | −1 | 1 | 30 |
| \(x_2\) | 1 | 0 | 1 | −2 | 1 | 20 |
| \(z_j-c_j\) | 0 | 0 | −4 | 3 | 80 |
Entering \(s_1\) (\(-4\)). Column entries \((-1, -2)^T\) — BOTH NEGATIVE.
The direction of unboundedness. Increasing \(s_1\) by \(t\) gives
Check feasibility along the ray. At \(x_1 = 30+t\), \(x_2 = 20+2t\):
Both constraints remain satisfied for every \(t \ge 0\) ✓ — genuinely unbounded.
Why it happened. Both constraints have the form (something) \(-x_2 \le\) (constant). Increasing \(x_2\) loosens both. Nothing in the model limits \(x_2\), yet \(x_2\) contributes positively to profit.
The modelling lesson. Every LP claiming unbounded profit has a missing constraint — here, no limit on the resource consumed by \(x_2\). The unbounded ray names the culprit precisely.
Problem 4 — Alternate optima found by pivoting¶
A final tableau for \(\max\ Z = 2x_1+4x_2\) is shown. Identify alternate optima and find the second optimal solution.
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | RHS |
|---|---|---|---|---|---|---|
| \(x_2\) | 4 | \(1/2\) | 1 | \(1/2\) | 0 | 4 |
| \(s_2\) | 0 | \(3/2\) | 0 | \(-1/2\) | 1 | 2 |
| \(z_j-c_j\) | 0 | 0 | 2 | 0 | 16 |
Solution.
Diagnosis. \(x_1\) is non-basic (it is not a basis label) yet \(z_1 - c_1 = 0\).
Current optimum. \(x_1 = 0\), \(x_2 = 4\), \(Z = 4(4) = 16\) ✓.
Find the second. Bring \(x_1\) into the basis. Column \(x_1 = (\frac12,\ \frac32)^T\); ratios
Leaving \(s_2\); pivot \(\frac32\).
Row 2 ÷ \(\frac32\): \((1,\ 0,\ -\frac13,\ \frac23\ |\ \frac43)\). Row 1 ← row 1 − \(\frac12\)(new row 2): \((0,\ 1,\ \frac12+\frac16,\ -\frac13\ |\ 4-\frac23)\) \(= (0,\ 1,\ \frac23,\ -\frac13\ |\ \frac{10}{3})\).
| Basis | \(c_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | RHS |
|---|---|---|---|---|---|---|
| \(x_2\) | 4 | 0 | 1 | \(2/3\) | \(-1/3\) | \(10/3\) |
| \(x_1\) | 2 | 1 | 0 | \(-1/3\) | \(2/3\) | \(4/3\) |
| \(z_j-c_j\) | 0 | 0 | 2 | 0 | 16 |
Check. \(Z = 2(\frac43)+4(\frac{10}{3}) = \frac83+\frac{40}{3} = \frac{48}{3} = 16\) ✓ — identical, as required.
The complete optimal set.
At \(\lambda = \frac12\): \(\vec x = (\frac23,\ \frac{11}{3})\), giving \(Z = \frac43 + \frac{44}{3} = \frac{48}{3} = 16\) ✓.
Note that \(s_2\) also has \(z_j-c_j = 0\) but is BASIC in the first tableau — that is not a signal of alternate optima. Only non-basic zeros count.
Problem 5 — Diagnosing and repairing a failing model¶
A production LP returns "infeasible". The model is: produce \(x_1, x_2\) with \(2x_1+3x_2 \le 100\) (machine hours), \(x_1 \ge 30\) (contract), \(x_2 \ge 25\) (contract). Diagnose and propose three repairs, quantifying each.
Solution.
Diagnosis. The two contracts consume, at minimum,
but only 100 are available.
How the simplex method reports this. Phase I terminates with \(W^{*} = 35/1 = 35\) (in units of the violated constraint), or in Big-M form an artificial variable remains at a positive value. Commercial solvers additionally report the Irreducible Infeasible Subsystem — here, exactly these three constraints, since removing any one restores feasibility.
Repair 1 — buy capacity. Increase machine hours to at least 135.
If overtime costs ₹200/hour, the cost is ₹7 000. Feasible if the contract penalties exceed ₹7 000.
Repair 2 — renegotiate a contract. Suppose \(x_2 \ge 25\) is relaxed to \(x_2 \ge q\). Feasibility requires
So product 2's commitment must fall from 25 to at most 13 units — a 48 % reduction.
Alternatively relax \(x_1 \ge 30\) to \(x_1 \ge p\):
— a 60 % reduction. Relaxing product 2 is the cheaper repair in units of commitment.
Repair 3 — soften the constraints (goal programming). Convert the hard contracts to soft targets with penalties, using the technique of L02 Problem 3:
where \(p_1, p_2\) are the per-unit penalties for missing each contract. This model is always feasible and tells you the least-cost way to break the promises — which is exactly the decision management actually faces.
Worked example of Repair 3. With penalties \(p_1 = ₹500\) and \(p_2 = ₹300\) per unit short:
Since product 1 costs 2 hours/unit and product 2 costs 3 hours/unit, the shortfall penalty per machine hour saved is
Cut product 2 — it is cheaper per hour saved. Need to save 35 hours:
Compare the three repairs.
| Repair | Cost | Notes |
|---|---|---|
| Buy 35 overtime hours | ₹7 000 | keeps both contracts intact |
| Goal programming (cut product 2) | ₹3 500 | cheapest — breaks the cheaper promise |
| Cut product 1 instead | \(\frac{35}{2}\times500 = ₹8{,}750\) | worst option |
The general lesson. "Infeasible" is not a failure of the algorithm — it is information. It says the requirements as stated cannot all be met, and the Phase I objective quantifies by exactly how much. The right response is to model the trade-off explicitly, which is what goal programming does.
6.8 Practice Problems¶
- Set up the Big-M tableau for \(\min\ 3x_1+5x_2\) s.t. \(x_1+x_2\ge4\), \(2x_1+x_2 = 6\).
- Solve Problem 2 of §6 by Big-M and confirm the same answer.
- A Phase I ends with \(W^{*} = 3\). What do you conclude?
- Column entries in the pivot column are \((0, -2, -5)^T\). Diagnose. [Ans: unbounded]
- Why is Big-M numerically dangerous on a computer?
- In a minimisation tableau, state the optimality condition.
- A final tableau has a basic variable equal to 0 and all \(z_j-c_j > 0\). Is it optimal? [Ans: yes — optimal and degenerate]
6.9 Summary¶
- \(\ge\) and \(=\) constraints leave no starting basic feasible solution, so artificial variables are added — they buy a starting point and must then be expelled.
- Big-M: penalise artificials with a huge \(M\). At optimality, all \(A_i = 0\) ⟹ valid; any \(A_i > 0\) ⟹ INFEASIBLE.
- Expelling the artificials gives feasibility, not optimality — continue until the \(z_j-c_j\) test passes.
- Two-phase: Phase I minimises \(\sum A_i\) (if \(W^{*}>0\), infeasible); Phase II restores the real objective. Numerically far safer, and what real solvers use.
- Tableau signatures: infeasible (\(A_i > 0\) / \(W^{*}>0\)), unbounded (no positive entry in the pivot column), alternate optima (a non-basic variable with \(z_j-c_j = 0\)), degenerate (a basic variable equal to 0).
- Infeasibility is information. The Phase I objective measures the total violation, and goal programming converts hard constraints into penalised targets — always feasible, and it prices the trade-off management actually faces.
Next lesson: L07 — Duality and sensitivity analysis.
Practise now: unit1-lp-lab.html → Simplex Stepper: switch on artificial variables and watch
Big-M and two-phase run side by side on the same problem.