The Simplex algorithmEdexcel A-Level Further Maths: Revision notes

The Simplex algorithm solves a linear program by moving from vertex to vertex of the feasible region, improving the objective each time, without drawing anything. It works for problems in any number of variables (here up to four variables and four constraints). For a maximising problem with $\le$ constraints, add a slack variable to each constraint. The objective $P=2x+3y$ becomes $P-2x-3y=0$. The initial tableau lists each equation as a row:

• $x+y+r=10$ gives row $r$: $1,1,1,0\mid10$
• $x+2y+s=16$ gives row $s$: $1,2,0,1\mid16$
• $P-2x-3y=0$ gives row $P$: $-2,-3,0,0\mid0$ The starting solution has the slack variables as the basic variables ($r=10$, $s=16$) and $x=y=0$, with $P=0$.

1. Pivot column: the column with the most negative entry in the $P$ row (here $y$, with $-3$). This variable enters the basis.
2. Pivot row: do the ratio test: for each row with a positive entry in the pivot column, calculate $\frac{\text{value}}{\text{entry}}$. The smallest ratio gives the pivot row ($\frac{10}{1}=10$, $\frac{16}{2}=8$, so row $s$). This variable leaves.
3. The pivot element is where they meet (the 2 in row $s$, column $y$). Ignore zero and negative entries in the ratio test: they would give an infeasible next solution. Choosing the smallest ratio keeps every value non-negative.

After choosing the pivot:

1. Divide the pivot row by the pivot element so the pivot becomes 1: row $s$ becomes $\frac12,1,0,\frac12\mid8$ (now row $y$).
2. For every other row (including $P$), subtract a multiple of the new pivot row so that the pivot column becomes 0. Row $r$ minus row $y$: $\frac12,0,1,-\frac12\mid2$. Row $P$ plus $3\times$ row $y$: $-\frac12,0,0,\frac32\mid24$. The pivot column is now a unit column, so $y$ is basic. The solution is $y=8$, $r=2$, $x=s=0$ and $P=24$, better than 0.

Repeat iterations until the $P$ row has no negative entries. Then the tableau is optimal. Continuing the example, $x$ (with $-\frac12$) enters. Ratios: $\frac{2}{1/2}=4$ and $\frac{8}{1/2}=16$, so row $r$ is the pivot row. The result is $x$ row: $1,0,2,-1\mid4$; $y$ row: $0,1,-1,1\mid6$; $P$ row: $0,0,1,1\mid26$. Reading the answer: basic variables take the value in their row, non-basic variables are 0. So $x=4$, $y=6$, $r=s=0$ and $P=26$. Check: $4+6=10$ and $4+12=16$, both constraints binding, and $2(4)+3(6)=26$.

The Simplex algorithm as set out maximises. To minimise $C$, maximise $P=-C$ instead, then give the minimum as $C=-P$. Example: minimise $C=2x-3y-4z$ subject to $x+y+z\le12$, $2x+y+3z\le18$. Maximise $P=-2x+3y+4z$, i.e. $P+2x-3y-4z=0$. After two iterations the optimum is $x=0$, $y=9$, $z=3$ with $P=39$, so the minimum of $C$ is $-39$. With three or four variables the process is the same: just more columns. Keep fractions exact and check each row operation.