The Simplex Algorithm

The graphical method is elegant but trapped in two dimensions — three products, four resources, or any realistic problem cannot be drawn. The Simplex algorithm, devised by George Dantzig in 1947, is the algebraic engine that breaks free. It encodes the linear programme as a tableau of numbers and then "walks" from one vertex of the feasible region to a neighbouring vertex that is at least as good, repeating until no improving move remains. Geometrically it is a tour of the corners of a high-dimensional polytope; arithmetically it is disciplined Gaussian elimination steered by a profit row. This lesson builds the method from slack variables to the optimality test, with two fully worked tableau traces.

---

1. Where this sits in AQA 7367

This is the algebraic climax of the linear-programming strand of the Paper 3 Discrete option (7367/3D) (Paper 3: 2 h, 100 marks, 33⅓%; AO1 40% / AO2 25% / AO3 35%). Carrying out the pivot procedure accurately is AO1; interpreting a tableau as a basic feasible solution, recognising the optimality condition, and reading off the answer are AO2. AQA typically asks for the setup and one or two iterations, so accuracy in a single pivot is worth securing completely.

---

2. Core theory: standard form and slack variables

The Simplex algorithm requires the LP in standard form:

$$\begin{aligned} \text{maximise } & P = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n \\ \text{subject to } & a_{i1}x_1 + \cdots + a_{in}x_n \le b_i \quad (b_i \ge 0) \\ & x_j \ge 0 \ \text{for all } j. \end{aligned}$$maximise subject to ​P=c1​x1​+c2​x2​+⋯+cn​xn​ai1​x1​+⋯+ain​xn​≤bi​(bi​≥0)xj​≥0 for all j.​

Each "$\le$≤" inequality becomes an equation by adding a non-negative slack variable $s_i$si​ that absorbs the unused capacity:

$a_{i1}x_1 + \cdots + a_{in}x_n + s_i = b_i, \qquad s_i \ge 0.$ai1​x1​+⋯+ain​xn​+si​=bi​,si​≥0.

If $s_i > 0$si​>0 the $i$ith resource is not fully used; if $s_i = 0$si​=0 the constraint is binding (active). The objective is written with everything on the left, $P - c_1 x_1 - \cdots - c_n x_n = 0$P−c1​x1​−⋯−cn​xn​=0, which is why its tableau row holds the negatives $-c_j$−cj​.

A basic feasible solution (BFS) sets the $n$n non-basic variables to $0$0 and reads the basic ones from the right-hand column — this is exactly a vertex of the feasible region. The Simplex algorithm hops from BFS to BFS, i.e. vertex to vertex.

It helps to see why the slack trick works. With $m$m constraints and $n$n decision variables we now have $n + m$n+m variables but only $m$m equations, so the system is underdetermined — there are infinitely many solutions, one for each choice of which variables are "free". Setting $n$n of the variables to zero leaves a square $m \times m$m×m system that pins down the remaining $m$m (the basic variables) uniquely; if those values are all $\ge 0$≥0 the point is feasible, and it is a corner of the region precisely because $n$n constraints (the zeroed variables, or original inequalities turned binding) are active at once. Each Simplex pivot swaps one variable into the basis and one out, which geometrically slides you along an edge from one corner to the next. So the bookkeeping of "entering" and "leaving" variables is not arbitrary ritual — it is the algebra of moving between adjacent vertices.

---

3. The tableau and the iteration (with M1/A1 mark scheme)

Lay the system out as a tableau, one row per constraint plus the objective ($P$P) row:

basis	$x_1$x1​	$x_2$x2​	$s_1$s1​	$s_2$s2​	RHS
$s_1$s1​	$a_{11}$a11​	$a_{12}$a12​	1	0	$b_1$b1​
$s_2$s2​	$a_{21}$a21​	$a_{22}$a22​	0	1	$b_2$b2​
$P$P	$-c_1$−c1​	$-c_2$−c2​	0	0	0

The starting BFS is $x_1 = x_2 = 0$x1​=x2​=0, $s_1 = b_1$s1​=b1​, $s_2 = b_2$s2​=b2​, $P = 0$P=0 — the origin.

One iteration:

1. Pivot column — the column with the most negative $P$P-row entry (the variable whose increase raises $P$P fastest). If no $P$P-row entry is negative, STOP — the tableau is optimal.
2. Pivot row — the ratio test: divide each constraint's RHS by its (positive) entry in the pivot column; the smallest non-negative ratio chooses the row (this is the variable that hits zero first as the entering variable grows). Ignore zero or negative pivot-column entries.
3. Pivot — divide the pivot row by the pivot element (making it $1$1), then add multiples of the new pivot row to every other row so the rest of the pivot column becomes $0$0.
4. Repeat from step 1.

Exam tip. The pivot column is chosen from the $P$P row (most negative); the pivot row from the ratio test (smallest ratio). Mixing these up is the single most common structural error. Show your ratios explicitly — they carry method marks.

---

4. Worked Example 4.1 — a two-variable trace

Maximise $P = 5x + 4y$P=5x+4y subject to $6x + 4y \le 24$6x+4y≤24, $x + 2y \le 6$x+2y≤6, $x, y \ge 0$x,y≥0.

Add slacks: $6x + 4y + s_1 = 24$6x+4y+s1​=24, $x + 2y + s_2 = 6$x+2y+s2​=6.

Initial tableau.

basis	$x$x	$y$y	$s_1$s1​	$s_2$s2​	RHS
$s_1$s1​	6	4	1	0	24
$s_2$s2​	1	2	0	1	6
$P$P	$-5$−5	$-4$−4	0	0	0

Iteration 1. Most negative $P$P-entry: $-5$−5 (column $x$x). Ratios $24/6 = 4$24/6=4 and $6/1 = 6$6/1=6; smallest is $4$4 (row $s_1$s1​), so pivot on the $6$6. (M1 for the correct pivot via most-negative + ratio test.)

$$\begin{aligned} R_1 &\to \tfrac{1}{6}R_1 = [\,1,\ \tfrac23,\ \tfrac16,\ 0\ |\ 4\,], \\ R_2 &\to R_2 - R_1^{\text{new}} = [\,0,\ \tfrac43,\ -\tfrac16,\ 1\ |\ 2\,], \\ P &\to P + 5R_1^{\text{new}} = [\,0,\ -\tfrac23,\ \tfrac56,\ 0\ |\ 20\,]. \end{aligned}$$R1​R2​P​→61​R1​=[1, 32​, 61​, 0 ∣ 4],→R2​−R1new​=[0, 34​, −61​, 1 ∣ 2],→P+5R1new​=[0, −32​, 65​, 0 ∣ 20].​

basis	$x$x	$y$y	$s_1$s1​	$s_2$s2​	RHS
$x$x	1	$\tfrac23$32​	$\tfrac16$61​	0	4
$s_2$s2​	0	$\tfrac43$34​	$-\tfrac16$−61​	1	2
$P$P	0	$-\tfrac23$−32​	$\tfrac56$65​	0	20

(A1 for a correct tableau after iteration 1; the BFS here is $x = 4,\ y = 0,\ P = 20$x=4, y=0, P=20.)

Iteration 2. Most negative: $-\tfrac23$−32​ (column $y$y). Ratios $4 \div \tfrac23 = 6$4÷32​=6 and $2 \div \tfrac43 = \tfrac32$2÷34​=23​; smallest is $\tfrac32$23​ (row $s_2$s2​), pivot on $\tfrac43$34​.

$$\begin{aligned} R_2 &\to \tfrac{3}{4}R_2 = [\,0,\ 1,\ -\tfrac18,\ \tfrac34\ |\ \tfrac32\,], \\ R_1 &\to R_1 - \tfrac23 R_2^{\text{new}} = [\,1,\ 0,\ \tfrac14,\ -\tfrac12\ |\ 3\,], \\ P &\to P + \tfrac23 R_2^{\text{new}} = [\,0,\ 0,\ \tfrac34,\ \tfrac12\ |\ 21\,]. \end{aligned}$$R2​R1​P​→43​R2​=[0, 1, −81​, 43​ ∣ 23​],→R1​−32​R2new​=[1, 0, 41​, −21​ ∣ 3],→P+32​R2new​=[0, 0, 43​, 21​ ∣ 21].​

basis	$x$x	$y$y	$s_1$s1​	$s_2$s2​	RHS
$x$x	1	0	$\tfrac14$41​	$-\tfrac12$−21​	3
$y$y	0	1	$-\tfrac18$−81​	$\tfrac34$43​	$\tfrac32$23​
$P$P	0	0	$\tfrac34$43​	$\tfrac12$21​	21

No negative $P$P-row entries, so this is optimal: $x = 3,\ y = \tfrac32,\ P = 21$x=3, y=23​, P=21. (A1.) Check: $6(3) + 4(\tfrac32) = 24$6(3)+4(23​)=24 ✓ and $3 + 2(\tfrac32) = 6$3+2(23​)=6 ✓ — both constraints binding, and $P = 15 + 6 = 21$P=15+6=21. (A1 for verifying against the original constraints.)

Track the vertices the algorithm visited: it started at the origin $(0,0)$(0,0) with $P = 0$P=0, stepped to $(4,0)$(4,0) with $P = 20$P=20, and finished at $(3, \tfrac32)$(3,23​) with $P = 21$P=21 — three corners of the feasible quadrilateral, each better than the last. That is the Simplex idea made visible: an uphill walk along the edges of the polygon.

---

5. Worked Example 5.1 — why Simplex earns its keep: three variables

The graphical method cannot touch this — there is no two-dimensional picture of a three-variable region.

Maximise $P = 5x_1 + 4x_2 + 3x_3$P=5x1​+4x2​+3x3​ subject to $2x_1 + 3x_2 + x_3 \le 5, \quad 4x_1 + x_2 + 2x_3 \le 11, \quad 3x_1 + 4x_2 + 2x_3 \le 8, \quad x_j \ge 0.$2x1​+3x2​+x3​≤5,4x1​+x2​+2x3​≤11,3x1​+4x2​+2x3​≤8,xj​≥0.

Add slacks $w_1, w_2, w_3$w1​,w2​,w3​.

basis	$x_1$x1​	$x_2$x2​	$x_3$x3​	$w_1$w1​	$w_2$w2​	$w_3$w3​	RHS
$w_1$w1​	2	3	1	1	0	0	5
$w_2$w2​	4	1	2	0	1	0	11
$w_3$w3​	3	4	2	0	0	1	8
$P$P	$-5$−5	$-4$−4	$-3$−3	0	0	0	0

Iteration 1. Most negative: $-5$−5 ($x_1$x1​). Ratios $5/2 = 2.5$5/2=2.5, $11/4 = 2.75$11/4=2.75, $8/3 \approx 2.67$8/3≈2.67; smallest is $2.5$2.5, pivot on the $2$2 in row $w_1$w1​.

$$\begin{aligned} R_1 &\to \tfrac12 R_1 = [\,1,\ \tfrac32,\ \tfrac12,\ \tfrac12,\ 0,\ 0\ |\ \tfrac52\,], \\ R_2 &\to R_2 - 4R_1^{\text{new}} = [\,0,\ -5,\ 0,\ -2,\ 1,\ 0\ |\ 1\,], \\ R_3 &\to R_3 - 3R_1^{\text{new}} = [\,0,\ -\tfrac12,\ \tfrac12,\ -\tfrac32,\ 0,\ 1\ |\ \tfrac12\,], \\ P &\to P + 5R_1^{\text{new}} = [\,0,\ \tfrac72,\ -\tfrac12,\ \tfrac52,\ 0,\ 0\ |\ \tfrac{25}{2}\,]. \end{aligned}$$R1​R2​R3​P​→21​R1​=[1, 23​, 21​, 21​, 0, 0 ∣ 25​],→R2​−4R1new​=[0, −5, 0, −2, 1, 0 ∣ 1],→R3​−3R1new​=[0, −21​, 21​, −23​, 0, 1 ∣ 21​],→P+5R1new​=[0, 27​, −21​, 25​, 0, 0 ∣ 225​].​

Iteration 2. The only negative $P$P-entry is $-\tfrac12$−21​ ($x_3$x3​). Ratios use positive $x_3$x3​-entries: row $x_1$x1​ gives $\tfrac52 \div \tfrac12 = 5$25​÷21​=5; row $w_2$w2​ has entry $0$0 (skip); row $w_3$w3​ gives $\tfrac12 \div \tfrac12 = 1$21​÷21​=1. Smallest is $1$1, pivot on the $\tfrac12$21​ in row $w_3$w3​.

$$\begin{aligned} R_3 &\to 2R_3 = [\,0,\ -1,\ 1,\ -3,\ 0,\ 2\ |\ 1\,], \\ R_1 &\to R_1 - \tfrac12 R_3^{\text{new}} = [\,1,\ 2,\ 0,\ 2,\ 0,\ -1\ |\ 2\,], \\ P &\to P + \tfrac12 R_3^{\text{new}} = [\,0,\ 3,\ 0,\ 1,\ 0,\ 1\ |\ 13\,]. \end{aligned}$$R3​R1​P​→2R3​=[0, −1, 1, −3, 0, 2 ∣ 1],→R1​−21​R3new​=[1, 2, 0, 2, 0, −1 ∣ 2],→P+21​R3new​=[0, 3, 0, 1, 0, 1 ∣ 13].​

($R_2$R2​ is unchanged since its $x_3$x3​-entry was $0$0.) The $P$P row is now $[0, 3, 0, 1, 0, 1\,|\,13]$[0,3,0,1,0,1∣13] — all non-negative, so optimal: $x_1 = 2,\ x_2 = 0,\ x_3 = 1,\ P = 13$x1​=2, x2​=0, x3​=1, P=13. Check: $2(2)+3(0)+1 = 5$2(2)+3(0)+1=5 ✓, $4(2)+0+2 = 10 \le 11$4(2)+0+2=10≤11, $3(2)+0+2 = 8$3(2)+0+2=8 ✓; $P = 10 + 0 + 3 = 13$P=10+0+3=13 ✓.

---

6. Reading and interpreting the final tableau

A finished tableau carries more than the optimum:

• Basic variables (a column that is all $0$0 except a single $1$1) take the RHS value of their row; non-basic variables are $0$0.
• A slack $s_i = 0$si​=0 means resource $i$i is fully used (its constraint binds); a positive slack is leftover capacity.
• The $P$P-row entries under the slack columns at optimality are the shadow prices — the extra profit per additional unit of each resource. In Example 4.1 the final $P$P-row is $[0,0,\tfrac34,\tfrac12\,|\,21]$[0,0,43​,21​∣21]: one more unit of the first resource would add $\tfrac34$43​ to $P$P, and of the second $\tfrac12$21​. This links straight to LP duality (§13).

Ties, degeneracy and non-standard problems