Two-stage Simplex and big-M methodsEdexcel A-Level Further Maths: Revision notes

For a $\le$ constraint the slack variable gives a ready-made starting solution. A $\ge$ or $=$ constraint does not: for $x+2y\ge6$ the equation $x+2y-s_2=6$ at $x=y=0$ gives $s_2=-6$, which is not allowed. So we add an artificial variable $t$: $x+2y-s_2+t=6$, which starts with $t=6$. But $t$ has no meaning in the real problem. A genuine solution must have $t=0$. The big-M and two-stage methods are two ways of forcing artificial variables out of the solution. Summary: $\le$ gives a slack variable; $\ge$ gives a surplus and an artificial variable; $=$ gives an artificial variable.

Use one objective that penalises artificial variables. For a maximising problem subtract $Mt$, where $M$ is a very large positive number: $P=3x+4y-Mt,\quad\text{i.e.}\quad P-3x-4y+Mt=0.$ Since $t$ is basic, its column must be a unit column, so eliminate $t$ from the $P$ row: subtract $M\times$ the $t$ row. For $x+y+s_1=12$ and $x+2y-s_2+t=6$: $P\text{ row: }-3-M,\ -4-2M,\ 0,\ M,\ 0\mid-6M.$ Choose the pivot column by comparing the coefficients of $M$ first (the most negative for large $M$): here $y$. Ratios: $\frac{12}{1}=12$ and $\frac62=3$, so the $t$ row is the pivot row.

After the first pivot ($t$ row, $y$ column) the $y$ row is $\frac12,1,0,-\frac12,\frac12\mid3$ and the $P$ row is $-1,0,0,-2,2+M\mid12$. Now $t$ has left the basis and $M$ appears only in the $t$ column. The most negative entry is $-2$ (the $s_2$ column). Only the $s_1$ row has a positive entry ($\frac12$, ratio 18), so it is the pivot row. The result is the $P$ row $1,0,4,0,M\mid48$, with no negatives. So $x=0$, $y=12$, $P=48$ (check: $x+y=12$, $x+2y=24\ge6$). If the final tableau still has $t>0$, the problem has no feasible solution.

Stage 1 ignores profit and just finds a feasible start. Define $I=t$ (the sum of the artificial variables) and minimise it, i.e. maximise $Q=-t$. Eliminate $t$ to get the $Q$ row. For $x+y+s_1=10$ and $3x+y-s_2+t=6$: $Q-3x-y+s_2=-6$. Carry the $P$ row (written as usual) through stage 1 so it stays correct.

• If the minimum of $I$ is 0: a basic feasible solution exists, so go to stage 2.
• If the minimum of $I$ is positive: no feasible solution. Stage 2: delete the $Q$ row and the artificial column(s), and continue Simplex on the original $P$ row until no negatives remain.

Maximise $P=2x+5y$ subject to $x+y\le10$ and $3x+y\ge6$. Stage 1: pivot on the 3 in the $t$ row ($x$ column; ratios 10 and 2), giving $x=2$ and $Q=0$. The $P$ row becomes $0,-\frac{13}{3},0,-\frac23\mid4$. Stage 2: $y$ enters (ratios 6 and 12, so the $x$ row leaves), then $s_2$ enters (the $s_1$ row leaves). Final $P$ row $3,0,5,0\mid50$: $x=0$, $y=10$, $P=50$. Minimising: maximise $P=-C$. For minimise $C=2x+3y$ with $x+y\ge4$ and $x+3y\le12$, use $P=-2x-3y-Mt$ (big-M) or $Q=-t$ then $P=-C$ (two-stage). The result is $x=4$, $y=0$ and $C=8$.