Big-M / two-phase method (artificial variables)

At a Glance

• Frequency: 5 sub-parts across 5 of 13 years (2018, 2021, 2022, 2023, 2024)
• Priority tier: T2
• Marks (count): 10 (2), 15 (1), 20 (2)
• Average solve time: ~16 min
• Difficulty mix: medium 4, hard 1
• Section: A | Dominant type: computation

Why This Chapter Matters

This atom appears in 5 of the last 13 years and always carries high marks (10–20). The question always involves an LPP with at least one $\ge$ or $=$ constraint, making a starting BFS unavailable without artificial variables. Both methods produce identical optima; the choice between them is stylistic. Three of the five questions use Big-M; two use the two-phase method. Mastering the sign conventions for each method — and knowing when to declare optimality — is what separates full-mark answers from partial credit.

Minimum Theory

Why artificials are needed. The simplex method requires a basic feasible solution (BFS) to start. Slack variables provide a BFS for $\le$ constraints. For $\ge$ or $=$ constraints, no obvious non-negative starting basis exists, so artificial variables $a_i \ge 0$ are appended to create one.

Standard form for a $\ge$ constraint. For $\mathbf{a}_i^T\mathbf{x} \ge b_i$ (with $b_i > 0$): subtract a surplus variable $s_i \ge 0$ and add an artificial $a_i \ge 0$: $\mathbf{a}_i^T\mathbf{x} - s_i + a_i = b_i.$ For an $=$ constraint: add only an artificial (no surplus).

Big-M method. Add large penalty $+M$ per artificial to the objective for minimisation (or $-M$ for maximisation): $\min\; z = \mathbf{c}^T\mathbf{x} + M\sum_i a_i.$ Run the standard simplex. If the optimal solution has any $a_i > 0$, the original problem is infeasible. Once all $a_i = 0$ and all $z_j - c_j \le 0$ (for min), the solution is optimal.

Sign convention for minimisation (Big-M). The entering variable rule: enter the non-basic variable with the largest positive $z_j - c_j$ (or equivalently most negative $c_j - z_j$). Optimality when all $z_j - c_j \le 0$. For a $+M$ artificial in a minimisation problem, the coefficient of $M$ in $z_j - c_j$ is always positive at first, driving artificials to leave.

Two-phase method. Split into two LPs:

Phase I: Minimise $w = \sum_i a_i$ subject to the constraints (original + artificials). If $w_{\min} > 0$, the problem is infeasible. If $w_{\min} = 0$, all artificials are zero; drop the artificial columns.

Phase II: Restore the original objective and run simplex from the Phase I optimal basis (with artificials removed).

Comparison.

Both give the same optimal solution; use whichever is asked.

Uniqueness check. At the optimum, if every non-basic variable has a strictly negative $z_j - c_j$ (for min), the solution is unique. If any non-basic has $z_j - c_j = 0$, an alternative optimum exists along that edge.

Question Archetypes

big-m-method (3 question(s); 2018, 2021, 2023)

Recognition Cues

• “Solve the following LPP by Big-M method.”
• Constraints include at least one $\ge$ or $=$ alongside a $\le$.
• “Show that the problem has a finite optimal solution.”

Solution Template

1. Convert to standard form. For each $\ge$ constraint: subtract surplus $s_i$, add artificial $a_i$. For each $\le$ constraint: add slack $s_j$. For $=$ constraints: add only $a_i$.
2. Penalise artificials. For minimisation: add $+Ma_i$ to the objective. For maximisation: add $-Ma_i$.
3. Initial BFS. Artificials (and any slacks) form the starting basis with $a_i = b_i$.
4. Compute the initial $z_j - c_j$ row. Include the $M$-terms. The most positive entry (for min) or most negative (for max) identifies the entering variable.
5. Ratio test. Divide RHS by the positive entries in the entering column; the row with the smallest ratio identifies the leaving variable.
6. Pivot and repeat until all $z_j - c_j \le 0$ (min) or $\ge 0$ (max).
7. Drop expelled artificials. Once an artificial leaves, do not allow it to re-enter.
8. Report optimality and state whether the original feasible region is bounded (to justify finite optimum).

Worked Example(s)

2018 Paper 2, 2018-P2-Q2b (20 marks)

Minimise $z = 3x_1 + 5x_2$ subject to $x_1 + 2x_2 \ge 8$, $3x_1 + 2x_2 \ge 12$, $5x_1 + 6x_2 \le 60$, $x_1, x_2 \ge 0$.

Standard form: add surpluses $s_1, s_2$, artificials $a_1, a_2$, slack $s_3$: $x_1+2x_2-s_1+a_1=8,\quad 3x_1+2x_2-s_2+a_2=12,\quad 5x_1+6x_2+s_3=60.$

Penalised objective: $\min\; z = 3x_1+5x_2+Ma_1+Ma_2$.

Initial basis $(a_1, a_2, s_3) = (8, 12, 60)$. Initial $z_j - c_j$:

Most positive: $x_1$ ($4M-3 > 4M-5$ for all $M$). Ratio test: $\min(8/1,\,12/3,\,60/5) = 4$ → $a_2$ leaves.

Pivot 1 (enter $x_1$, leave $a_2$, pivot element 3): After row operations, new basis $(a_1, x_1, s_3)$.

Updated: $z_j-c_j$ for $x_2$ still positive ($\sim \tfrac43 M$). Enter $x_2$. Ratio test: $\min(3, 6, 15) = 3$ → $a_1$ leaves.

Pivot 2 (enter $x_2$, leave $a_1$): New basis $(x_2, x_1, s_3) = (3, 2, 32)$. Both artificials expelled.

Optimality check: all remaining $z_j - c_j \le 0$. Optimal: $\boxed{x_1=2,\quad x_2=3,\quad z_{\min}=3(2)+5(3)=21.}$

Finite optimum: the $\le$ constraint $5x_1+6x_2\le60$ bounds the feasible region; combined with both artificials driven to zero, the problem has a finite optimal value.

Constraint check: $x_1+2x_2=8$ ✓ (binding), $3x_1+2x_2=12$ ✓ (binding), $5x_1+6x_2=28\le60$ ✓ (slack 32).

2021 Paper 2, 2021-P2-Q4c (15 marks)

Maximise $Z = 4x_1 + 5x_2 + 2x_3$ subject to $2x_1+x_2+x_3 \ge 10$, $x_1+3x_2+x_3 \le 12$, $x_1+x_2+x_3 = 6$, $x_i \ge 0$.

Key structural observation. The equality constraint $x_1+x_2+x_3=6$ combined with the $\ge$ constraint $2x_1+x_2+x_3\ge10$ gives (subtract): $x_1\ge4$. The objective becomes $Z = 4x_1+5x_2+2x_3 = 2x_1+3x_2+12$ after substituting $x_3=6-x_1-x_2$. To maximise: push $x_1$ and $x_2$ as large as feasible.

Constraint 2: $6 + 2x_2 \le 12 \Rightarrow x_2 \le 3$. Try $x_1=4,\,x_2=2,\,x_3=0$: all constraints satisfied, $Z=16+10+0=26$.

Try $x_1=4,\,x_2=3,\,x_3=?$: forces $x_3=-1<0$, infeasible. The optimum is: $\boxed{x_1=4,\quad x_2=2,\quad x_3=0,\quad Z_{\max}=26.}$

The simplex Big-M tableau confirms this after two pivots expelling the two artificials.

2023 Paper 2, 2023-P2-Q3c (20 marks)

Minimise $Z = 2x_1+3x_2$ subject to $x_1+x_2\ge9$, $x_1+2x_2\ge15$, $2x_1-3x_2\le9$, $x_1,x_2\ge0$. Is the optimal solution unique?

Standard form: surpluses $s_1,s_2$, artificials $a_1,a_2$, slack $s_3$.

Iteration 1: Enter $x_2$ (largest $z_j-c_j = 3M-3$). Ratio test: $\min(9/1, 15/2) = 7.5$ → $a_2$ leaves.

Iteration 2: Enter $x_1$ (next most positive, $0.5M-0.5$). Ratio test: $\min(3, 15, 9) = 3$ → $a_1$ leaves.

Optimal tableau (both artificials expelled): $x_1=3,\,x_2=6,\,s_3=21$.

$\boxed{x_1=3,\quad x_2=6,\quad Z_{\min}=2(3)+3(6)=24.}$

Uniqueness: at the optimum, non-basic variables $s_1$ and $s_2$ both have $z_j-c_j=-1<0$ (strictly negative). No non-basic variable has $z_j-c_j=0$, so the optimum is unique.

Common Traps

• Minimisation entry rule: enter the variable with the most positive $z_j-c_j$ (not most negative). Many students mix up the max/min conventions.
• Expelled artificials cannot re-enter: once $a_i = 0$ and leaves the basis, drop its column. Allowing it back leads to circular pivoting.
• Justify “finite optimum”: state that the feasible region is bounded (quote the $\le$ constraint that bounds it) and that all artificials reached zero (confirming feasibility).
• Uniqueness: check all non-basic $z_j - c_j$ values, not basic ones (basic variables always have $z_j - c_j = 0$ by definition).

two-phase-method (2 question(s); 2022, 2024)

Recognition Cues

• “Use two-phase method to solve …”
• LPP with only $\ge$ constraints (surpluses needed, no slacks).
• Objective is to minimise a sum like $x_1 + x_2$.

Solution Template

Phase I:

1. Add surplus $s_i$ and artificial $a_i$ for each $\ge$ constraint; add artificial only for $=$ constraints.
2. Phase I objective: $\min\; w = \sum_i a_i$ (ignoring the original objective).
3. Compute reduced costs for Phase I: $\bar c_j = -\mathbf{c}_B^T\mathbf{a}_j$ for non-basic columns (where $\mathbf{c}_B$ is the Phase I cost of the basis).
4. Pivot until $w = 0$ (all artificials zero) or confirm infeasibility ($w > 0$ at optimum).
5. Drop all artificial columns; keep the current basis (all non-artificial).

Phase II:

1. Restore the original objective; compute new reduced costs in terms of the Phase I basis.
2. Run simplex until all reduced costs are non-negative (for min) or non-positive (for max).
3. Report the optimal solution.

Worked Example(s)

2022 Paper 2, 2022-P2-Q1e (10 marks)

Use two-phase method: Minimise $Z = x_1 + x_2$ s.t. $2x_1+x_2\ge4$, $x_1+7x_2\ge7$, $x_1,x_2\ge0$.

Standard form: $2x_1+x_2-s_1+a_1=4$, $x_1+7x_2-s_2+a_2=7$.

Phase I: Minimise $w = a_1 + a_2$.

Initial basis $(a_1,a_2)=(4,7)$. Phase I reduced costs: $\bar c_{x_2} = -(1+7) = -8$ (most negative → enter $x_2$). Ratio test: $\min(4/1,\,7/7)=1$ → $a_2$ leaves.

After pivot ($x_2$ enters, $a_2$ leaves): basis $(a_1,x_2)$. Next most negative: $\bar c_{x_1}=-13/7$. Enter $x_1$. Ratio: $3/(13/7)=21/13$ → $a_1$ leaves.

Phase I basis $(x_1,x_2)$; $w=0$. BFS: $x_1=21/13,\,x_2=10/13$.

Phase II: Minimise $Z = x_1 + x_2$.

Reduced costs for $s_1$ and $s_2$: both $>0$ (computed from the Phase I tableau). No entering variable — current solution is optimal.

$\boxed{x_1=\tfrac{21}{13},\quad x_2=\tfrac{10}{13},\quad Z_{\min}=\tfrac{31}{13}\approx2.385.}$

Verification: $2x_1+x_2=\tfrac{42+10}{13}=4$ ✓; $x_1+7x_2=\tfrac{21+70}{13}=7$ ✓ (both binding).

2024 Paper 2, 2024-P2-Q1e (10 marks)

Use two-phase method: Maximise $z = x_1+2x_2$ s.t. $x_1-x_2\ge3$, $2x_1+x_2\le10$, $x_1,x_2\ge0$.

Standard form: $x_1-x_2-s_1+a_1=3$, $2x_1+x_2+s_2=10$.

Phase I: Minimise $w = a_1$.

Initial basis $(a_1,s_2)=(3,10)$. Phase I: enter $x_1$ (coefficient $-1$ in $w=3-x_1+x_2+s_1$, most negative). Ratio test: $\min(3/1,\,10/2)=3$ → $a_1$ leaves. Pivot: $x_1=3,\,s_2=4$; $w=0$.

Phase I complete.

Phase II: Maximise $z = x_1+2x_2$.

Express $z$ in non-basics: from $x_1 = 3+x_2+s_1$, $z = (3+x_2+s_1)+2x_2 = 3+3x_2+s_1$. Coefficient of $x_2$ is $+3>0$ → enter $x_2$.

Ratio test on $s_2$ row (only binding constraint for $x_2$): $s_2 = 4-3x_2-2s_1 \ge 0 \Rightarrow x_2 \le 4/3$. So $x_2=4/3$, $s_2$ leaves.

New basis $(x_1,x_2)$: $x_1=13/3,\,x_2=4/3$. Updated objective: $z = 7 - s_1 - s_2$. Both non-basic coefficients negative — optimal.

$\boxed{x_1=\tfrac{13}{3},\quad x_2=\tfrac{4}{3},\quad z_{\max}=7.}$

Verification: $x_1-x_2=3$ ✓, $2x_1+x_2=10$ ✓ (both binding).

Common Traps

• Phase I objective vs Phase II objective: Phase I minimises $\sum a_i$, not the original $z$. Mixing the two costs marks.
• Check Phase I ends cleanly: if $w_{\min} > 0$, the original problem is infeasible — state this and stop. If $w_{\min} = 0$ but an artificial remains in the basis at value 0 (degeneracy), the Phase I basis is still valid — proceed to Phase II after verifying.
• Drop artificial columns: after Phase I, remove artificial variable columns from the tableau before running Phase II.
• Surplus and artificial for $\ge$: both are needed. Missing the surplus variable (and only adding the artificial) is a common error.

Marks-Aware Writing

10-mark question: show the standard-form conversion (with all variables named), the first pivot calculation in detail (including the $z_j-c_j$ row), and the final answer. A small $2\times 5$ or $3\times 6$ simplex tableau is expected.

15-mark question: two full pivots shown step-by-step with the updated tableau after each pivot. State the entering and leaving variable at each step with the ratio-test computation.

20-mark question: three pivots or more, a thorough optimality-check discussion, and an explicit finite-optimum / uniqueness argument. Show constraint verification at the optimal point.

Practice Set

• 2019-P2-Q3b (15 m) — — Two equalities collapse the feasible region; use Phase I to detect the structural simplification, then note $Z$ is constant on the feasible set.