The simplex algorithmAQA A-Level Further Maths: Revision notes

The simplex algorithm solves linear programming problems algebraically, so it works when there are too many variables to draw. First write every constraint as an equation by adding a slack variable: $2x+y\leq10$ becomes $2x+y+r=10$ with $r\geq0$. The slack is the unused part of the resource. Write the objective as $P-4x-3y=0$ for $P=4x+3y$. The initial tableau lists these equations, one row per constraint plus the objective row. The variables that are non-zero (here $r$ and $s$) are the basic variables; the others are non-basic and equal 0. At the start, $x=y=0$, the slack variables take the right-hand sides and $P=0$.

1. Pivot column: in the objective row choose the most negative entry. If there are none, stop. 2. Pivot row: for each row where the pivot-column entry is positive, calculate the ratio $\frac{\text{right-hand side}}{\text{entry}}$ and choose the smallest. 3. Pivot: divide the pivot row by the pivot entry so it becomes 1, then add or subtract multiples of this row from the others (including the objective row) to make every other entry in the pivot column 0. The new tableau gives a better value of $P$. Repeat. Example: with $P-4x-3y=0$, $2x+y+r=10$, $x+y+s=8$ the pivot column is $x$, the ratios are $\frac{10}{2}=5$ and $\frac81=8$, so the pivot is the 2 in the $r$ row.

Maximise $P=3x+2y$ subject to $2x+y\leq14$ and $x+2y\leq10$. Initial: $2x+y+r=14$, $x+2y+s=10$, $P-3x-2y=0$. Pivot column $x$; ratios $7$ and $10$, so pivot on the 2. After iteration 1: $x+\frac12y+\frac12r=7$, $\frac32y-\frac12r+s=3$, $P-\frac12y+\frac32r=21$. The objective row still has $-\frac12$. Pivot column $y$; ratios $14$ and $2$, so pivot on the $\frac32$. After iteration 2: $x+\frac23r-\frac13s=6$, $y-\frac13r+\frac23s=2$, $P+\frac43r+\frac13s=22$. No negative coefficients remain, so the solution is optimal: $x=6$, $y=2$, $P=22$. This agrees with the graphical method, where the optimum is the vertex $(6,2)$.

Read the current solution from the tableau: basic variables take the right-hand side of their row, non-basic variables are 0, and $P$ is the right-hand side of the objective row. A solution is optimal when every coefficient in the objective row is non-negative. A slack of 0 means that constraint is binding (that resource is fully used); a positive slack is the amount unused. Example: if the final tableau has $r=0$, $s=0$ and $t=8$, the first two resources are fully used and 8 units of the third are spare. If a negative coefficient is still in the objective row, the current solution is not optimal and another iteration is needed.

The simplex algorithm as set out maximises. To minimise $Q$, maximise $P=-Q$ instead, then the minimum of $Q$ is $-P$. Example: minimise $Q=x-2y$ subject to $2x+y\leq12$ and $x+y\leq7$. Maximise $P=-x+2y$, with objective row $P+x-2y=0$. The pivot column is $y$ and the ratios are $12$ and $7$, so the pivot is the 1 in the second row. After one iteration the objective row is $P+3x+2s=14$, with no negative entries, so $y=7$, $x=0$ and $P=14$. The minimum value of $Q$ is $-14$.