Simplex method (basic)

At a Glance

• Frequency: 9 sub-parts across 8 of 13 years (2013, 2014, 2015, 2016, 2017, 2019, 2020, 2022)
• Priority tier: T1
• Marks (count): 10 (1), 15 (3), 20 (5)
• Average solve time: ~17 min
• Difficulty mix: medium 6, hard 3
• Section: A | Dominant type: computation

Why This Chapter Matters

The simplex method appears in 8 of the last 10 years and almost always carries 15 or 20 marks — the second-highest average mark of any T1 Paper 2 atom. More importantly, the algorithm is completely mechanical: every question follows the same four-step sequence (standard form → tableau → pivot until optimal → read the answer). The hard parts are handling special cases — equality constraints, lower-bound shifts, resonance with alternative optima, and reading the dual from the optimal tableau — but each has a fixed rule. Learning those rules is sufficient to score full marks.

Minimum Theory

Standard form and initial basis. A linear programming problem with all $\le$ constraints and non-negative RHS is converted to standard form by adding non-negative slack variables $s_i$. The slacks form the initial basis with $z=0$. If a constraint is $=$, add a (non-negative) artificial variable $a_i$ and use Big-M or Phase-I to drive it to zero. If a variable has a non-zero lower bound $x_i\ge k$, substitute $y_i=x_i-k\ge0$ before running the simplex.

Pivot rules. At each iteration: the entering variable is the one with the largest positive $c_j-z_j$ (for maximisation); for minimisation use the largest positive $z_j-c_j$. The leaving variable is found by the minimum-ratio test: compute $\min\{\text{RHS}_i/a_{ij}:a_{ij}>0\}$; the row achieving the minimum exits the basis. Pivot by row-reducing to make the entering column a unit vector.

Termination and special cases. The tableau is optimal when all $c_j-z_j\le0$ (max). If a non-basic variable has $c_j-z_j=0$ at the optimal tableau, alternative optima exist; do one more pivot on that variable to find the second extreme optimal vertex, then the complete optimal set is their convex combination. The dual optimum $y_i^*$ is read directly from the optimal tableau: it equals the $c_j-z_j$ entry in the column of the $i$-th slack variable.

Question Archetypes

Three patterns cover every simplex question in the corpus.

simplex-method (5 question(s); 2013×2, 2017, 2019, 2020)

Recognition Cues

• “Solve by the simplex method” with $\le$ constraints (sometimes one equality or lower-bound constraint).
• May ask to minimise — convert by negating objective, or equivalently enter the variable with the largest positive $z_j-c_j$.
• A non-standard constraint (equality, $\ge$, or $x_i\ge k>0$) signals a pre-processing step before the main simplex run.

Solution Template

1. Pre-process. For $\ge$ constraints: subtract a surplus variable and add an artificial. For equality constraints: add an artificial. For lower bounds $x_i\ge k$: substitute $y_i=x_i-k$.
2. Standard form. For $\le$ constraints add slacks $s_i\ge0$. Write the initial tableau with $(s_1,\ldots,s_m)$ as the basis.
3. Compute $c_j-z_j$. For the initial tableau (with all-slack basis) $c_j-z_j=-c_j$ (max) or $+c_j$ (min).
4. Pivot. Enter: largest positive $c_j-z_j$. Leave: min-ratio test (skip non-positive column entries). Update the tableau by row operations.
5. Repeat until no positive $c_j-z_j$ remains.
6. Read the solution. Basic variables = RHS values; non-basic = 0. Compute objective.

Worked Example(s)

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

Maximize $z=2x_1+3x_2-5x_3$ s.t. $x_1+x_2+x_3=7$, $2x_1-5x_2+x_3\ge10$, $x_i\ge0$.

Pre-process. The equality $x_1+x_2+x_3=7$ eliminates $x_3=7-x_1-x_2$. The $\ge$ constraint becomes $x_1-6x_2\ge3$, and $x_3\ge0$ gives $x_1+x_2\le7$. Substituting into the objective yields $z'=7x_1+8x_2-35$.

Maximise $z'$. Both constraints $x_1+x_2\le7$ and $x_1\ge3+6x_2$ fix $x_2\le4/7$; optimum at $x_2=4/7$, $x_1=7-4/7=45/7$, $x_3=0$: $\boxed{\;z_{\max}=\frac{102}{7}\approx14.57\quad\text{at}\quad(x_1,x_2,x_3)=\!\left(\tfrac{45}{7},\tfrac{4}{7},0\right).\;}$

2013 Paper 2, 2013-P2-Q4c (20 marks)

Minimize $z=5x_1-4x_2+6x_3-8x_4$ s.t. $x_1+2x_2-2x_3+4x_4\le40$, $2x_1-x_2+x_3+2x_4\le8$, $4x_1-2x_2+x_3-x_4\le10$, $x_i\ge0$.

Standard form. Add slacks $s_1,s_2,s_3$. For minimisation enter the variable with the largest positive $z_j-c_j=-c_j$ (initial): $x_4$ has $z_j-c_j=8$.

Iteration 1. $x_4$ enters, min-ratio $8/2=4$ at $s_2$. Pivot.

Iteration 2. $x_2$ enters (next largest $z_j-c_j$), min-ratio $24/4=6$ at $s_1$. Pivot.

Check. All $z_j-c_j\le0$: optimal. Note $z_{s_2}-c_{s_2}=0$ (alternative optima along the $s_2$ edge).

$\boxed{\;x_2=6,\;x_4=7,\;z_{\min}=-80.\;}$

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

Maximize $z=3x_1+5x_2+4x_3$ s.t. $2x_1+3x_2\le8$, $2x_2+5x_3\le10$, $3x_1+2x_2+4x_3\le15$, $x\ge0$.

Three iterations. Enter $x_2$ (coeff 5) → $s_1$ leaves ($8/3$ min-ratio). Enter $x_3$ → $s_2$ leaves ($14/15$). Enter $x_1$ → $s_3$ leaves ($89/41$). All three structural constraints become binding at the optimum.

$\boxed{\;x_1=\tfrac{89}{41},\;x_2=\tfrac{50}{41},\;x_3=\tfrac{62}{41},\;z_{\max}=\tfrac{765}{41}\approx18.66.\;}$

Keep exact fractions. The denominator 41 arises from the pivot on $41/15$ in iteration 2 — the most error-prone step.

2019 Paper 2, 2019-P2-Q3b (15 marks)

Minimize $Z=x_1+2x_2-3x_3-2x_4$ s.t. $x_1+2x_2-3x_3+x_4=4$, $x_1+2x_2+x_3+2x_4=4$, $x_i\ge0$.

Key observation. Subtract the two equations: $4x_3+x_4=0$. Since $x_3,x_4\ge0$, this forces $x_3=x_4=0$. The feasible set reduces to $x_1+2x_2=4$ where $Z=x_1+2x_2=4$ (constant). The minimum is $4$, achieved at every feasible point, e.g. $(0,2,0,0)$.

$\boxed{\;Z_{\min}=4,\;\text{e.g. at }(0,2,0,0).\;}$

Do not be lured by the negative cost coefficients $-3x_3,-2x_4$ — those variables are pinned at zero.

2020 Paper 2, 2020-P2-Q3b (15 marks)

Minimize $z=-6x_1-2x_2-5x_3$ s.t. $2x_1-3x_2+x_3\le14$, $-4x_1+4x_2+10x_3\le46$, $2x_1+2x_2-4x_3\le37$, $x_1\ge2$, $x_2\ge1$, $x_3\ge3$.

Shift. $y_i=x_i-k_i$: $y_1=x_1-2$, $y_2=x_2-1$, $y_3=x_3-3$. New constraints: $2y_1-3y_2+y_3\le10$, $-4y_1+4y_2+10y_3\le20$, $2y_1+2y_2-4y_3\le43$. New objective: maximize $z'=6y_1+2y_2+5y_3$ (constant $-29$ absorbed).

Three simplex iterations drive all slacks to zero. Solve the $3\times3$ binding system: $y_1=\tfrac{1011}{50},\;y_2=\tfrac{298}{25},\;y_3=\tfrac{133}{25}.$

Back-substitute: $\boxed{\;x_1=\tfrac{1111}{50}\approx22.22,\;x_2=\tfrac{323}{25}\approx12.92,\;x_3=\tfrac{208}{25}\approx8.32,\;z_{\min}=-\tfrac{5019}{25}\approx-200.76.\;}$

Common Traps

• Min-ratio test: skip rows where the entering column entry is $\le0$ — those rows do not bound the increase of the entering variable.
• Minimisation sign: for minimisation, enter the variable with the largest positive $z_j-c_j$ (equivalently, enter the most-negative reduced cost); don’t accidentally use the max convention.
• Equality constraints force artificials — the negative cost terms from equality constraints are not exploitable if the feasible region pinning forces those variables to zero (2019).
• Non-zero lower bounds must be shifted before running the simplex (2020); the optimal tableau values are for the shifted variables $y_i$, not the original $x_i$.
• Keep exact fractions throughout — the denominator-41 type fractions (2017) are correct; rounding mid-computation causes cascading errors.

simplex-alternative-optima (2 question(s); 2014, 2016)

Recognition Cues

• “Find all optimal solutions” — a deliberate cue that there is more than one.
• “Is the optimal solution unique? Justify.”
• The optimal tableau has a non-basic variable with $c_j-z_j=0$.

Solution Template

1. Run the simplex to the first optimal tableau.
2. Check non-basic reduced costs. If any non-basic variable has $c_j-z_j=0$, alternative optima exist; state this.
3. Find the second vertex: pivot that non-basic variable into the basis (using the min-ratio test on its column).
4. Report the segment: all optimal solutions are the convex combination $(1-t)\mathbf x^{(1)}+t\mathbf x^{(2)}$ for $t\in[0,1]$.
5. Uniqueness: if all non-basic reduced costs are strictly negative at optimality, the solution is unique.

Worked Example(s)

2014 Paper 2, 2014-P2-Q4c (20 marks)

Maximize $Z=30x_1+24x_2$ s.t. $5x_1+4x_2\le200$, $x_1\le32$, $x_2\le40$, $x_1,x_2\ge0$. Find all optimal solutions.

Iteration 1 ($x_1$ enters, $s_2$ leaves): basis $\{s_1,x_1,s_3\}$, $Z=960$.

Iteration 2 ($x_2$ enters, $s_1$ leaves): basis $\{x_2,x_1,s_3\}$, $Z=1200$.

Optimal tableau reduced costs. $s_1: -6<0$; $s_2: 0$ ← alternative optima!

Pivot $s_2$ in. Min-ratio on $s_2$ column: $s_3$ leaves. New vertex: $(x_1,x_2)=(8,40)$, $Z=1200$ ✓.

$\boxed{\;\text{All optimal solutions: }(32-24t,\;10+30t)\text{ for }t\in[0,1];\;Z_{\max}=1200.\;}$

The entire edge joining $(32,10)$ and $(8,40)$ is optimal because the objective gradient $(30,24)=6(5,4)$ is parallel to the binding constraint $5x_1+4x_2=200$.

2016 Paper 2, 2016-P2-Q2c (20 marks)

Maximize $z=2x_1+3x_2+6x_3$ s.t. $2x_1+x_2+x_3\le5$, $3x_2+2x_3\le6$, $x\ge0$. Is the solution unique?

Iteration 1 ($x_3$ enters, $s_2$ leaves). Iteration 2 ($x_1$ enters, $s_1$ leaves).

Optimal. $(x_1,x_2,x_3)=(1,0,3)$, $z=20$. Non-basic reduced costs: $c_{x_2}-z_{x_2}=-5.5$, $c_{s_1}-z_{s_1}=-1$, $c_{s_2}-z_{s_2}=-2.5$ — all strictly negative.

$\boxed{\;\text{The optimal solution is }\textbf{unique}:\;x_1=1,\;x_3=3,\;z_{\max}=20.\;}$

Common Traps

• Alternative-optima signal is $c_j-z_j=0$ for a non-basic variable. Basic variables trivially have $c_j-z_j=0$ — that is not the signal.
• Must check all non-basic reduced costs (structural variables AND slacks) for the uniqueness test.
• When finding the second vertex, the pivot on the zero-reduced-cost variable uses the standard min-ratio test — the objective does not change but the basis changes.

simplex-with-dual (2 question(s); 2015, 2022)

Recognition Cues

• “Write the dual of the given problem.”
• “Read the dual optimum from the optimal table.”
• The question has both a primal simplex run AND a dual reading.

Solution Template

1. Solve the primal by simplex to optimality.
2. Write the dual. For a primal $\max\;c^Tx$ s.t. $Ax\le b$, $x\ge0$: dual is $\min\;b^Ty$ s.t. $A^Ty\ge c$, $y\ge0$.
3. Read dual optimum. In the optimal primal tableau, $y_i^*=$ entry in the $c_j-z_j$ row at the column of slack $s_i$.
4. Verify strong duality: $Z_{\max}=W_{\min}$.
5. Verify dual feasibility: substitute $y^*$ into each dual constraint.

Worked Example(s)

2015 Paper 2, 2015-P2-Q4c (20 marks)

Max $Z=2x_1-4x_2+5x_3$ s.t. $x_1+4x_2-2x_3\le2$, $-x_1+2x_2+3x_3\le1$; write dual; read dual optimum.

Simplex (two iterations: $x_3$ enters then $x_1$ enters):

$\boxed{\;Z_{\max}=31\text{ at }x_1=8,\;x_3=3,\;x_2=0.\;}$

Dual. Min $W=2y_1+y_2$ s.t. $y_1-y_2\ge2$, $4y_1+2y_2\ge-4$, $-2y_1+3y_2\ge5$, $y_1,y_2\ge0$.

Dual optimum from $c_j-z_j$ row at slack columns. $y_1^*=11$ (at $s_1$), $y_2^*=9$ (at $s_2$). $W=2(11)+9=31=Z_{\max}$ ✓.

2022 Paper 2, 2022-P2-Q3c (15 marks)

Max $Z=x_1+x_2+x_3$ s.t. $2x_1+x_2+x_3\le2$, $4x_1+2x_2+x_3\le2$, $x\ge0$; write dual; read dual optimum.

Simplex (three degenerate pivots ending with $x_3=2$ basic):

$\boxed{\;Z_{\max}=2\text{ at }x_3=2,\;x_1=x_2=0.\;}$

Dual. Min $W=2y_1+2y_2$ s.t. $2y_1+4y_2\ge1$, $y_1+2y_2\ge1$, $y_1+y_2\ge1$, $y\ge0$.

Dual optimum. From optimal $c_j-z_j$ row: $y_1^*=1$, $y_2^*=0$. $W=2(1)+2(0)=2=Z_{\max}$ ✓.

Common Traps

• The dual optimum is in the $c_j-z_j$ (or $z_j-c_j$) row at the slack variable columns, not the structural variable columns.
• Strong duality check ($Z_{\max}=W_{\min}$) is the fastest verification of the dual reading.
• Complementary slackness: a binding dual constraint corresponds to a non-zero primal variable, and vice versa — use this to cross-check.
• With degeneracy (tied ratios in the min-ratio test), the simplex may take extra iterations but still reaches the correct optimum; the dual reading procedure is unchanged.

Marks-Aware Writing

10-mark questions (2013-Q1e): One to two sentences of strategy, then eliminate the equality and solve the 2-variable LPP. Box the answer and verify all constraints.

15-mark questions (2019, 2020, 2022): Full tableau with three iterations shown. Each iteration: entering variable (with justification), min-ratio test (table), pivot result. Final answer in a box. One verification row.

20-mark questions (2013-Q4c, 2014, 2015, 2016, 2017): Show every pivot in a labelled tableau. For the dual: write the dual formulation explicitly (objective + all constraints), then read $y_i^*$ and state the strong-duality verification. For alternative optima: find both vertices, state the segment.

Practice Set