Formulating linear programsEdexcel A-Level Further Maths: Revision notes

A linear program has three parts. First choose decision variables (for example $x$ tables and $y$ chairs per week), each with a clear meaning and units. Then write the objective function to be maximised (profit) or minimised (cost), which is linear in the variables. Finally write the constraints, linear inequalities from limited resources or requirements, plus non-negativity conditions $x\ge0$, $y\ge0$. Translate words carefully: 'at most', 'no more than' and 'limited to' give $\le$; 'at least', 'no fewer than' and 'minimum of' give $\ge$. 'Exactly' gives $=$. Example: a workshop makes tables ($x$) needing 3 hours of cutting and chairs ($y$) needing 2 hours, with at most 20 hours available: $3x+2y\le20$. If profit is £30 per table and £20 per chair, maximise $P=30x+20y$.

To use the Simplex algorithm every constraint must be an equation. For a $\le$ constraint add a slack variable, the unused amount of the resource: $3x+2y\le20\quad\Rightarrow\quad 3x+2y+s_1=20,\qquad s_1\ge0.$ If $x=4$ and $y=3$ then $s_1=20-12-6=2$: 2 hours of cutting time are unused. If $s_1=0$ the constraint is binding (the resource is fully used). Each $\le$ constraint gets its own slack variable ($s_1$, $s_2$, ...). At the origin ($x=y=0$) every slack variable equals the right-hand side, which gives an obvious starting solution: $x=y=0$ with the slack variables as the basic variables.

For a $\ge$ constraint the left-hand side exceeds the requirement, so subtract a surplus variable, the amount over the minimum: $x+y\ge5\quad\Rightarrow\quad x+y-s_3=5,\qquad s_3\ge0.$ If $x=4$ and $y=3$ then $s_3=7-5=2$: 2 units more than the minimum are supplied. At the origin the equation would give $-s_3=5$, which is impossible because $s_3\ge0$, so a surplus variable alone cannot give a starting solution.

Because a surplus variable cannot supply a starting basic solution, add an artificial variable $t_1\ge0$ to a $\ge$ constraint (and to an $=$ constraint): $x+y-s_3+t_1=5.$ Now $x=y=0$, $s_3=0$, $t_1=5$ is a basic feasible solution, so the algorithm can start. An artificial variable has no meaning in the real problem: it is a device, and a valid final answer must have $t_1=0$. Methods that remove artificial variables (the two-stage and big-M methods) come later. Summary: $\le$ gets a slack variable; $\ge$ gets a surplus and an artificial variable; $=$ gets an artificial variable only.

A company makes $x$ standard and $y$ deluxe boxes. Packing: 4 and 6 minutes, at most 240 minutes. Ribbon: 2 m and 5 m, at most 150 m. At least 10 boxes in total. Profit £3 and £5. Maximise $P=3x+5y$ subject to $2x+3y\le120$, $2x+5y\le150$, $x+y\ge10$, $x,y\ge0$. With extra variables: $2x+3y+s_1=120,\quad 2x+5y+s_2=150,\quad x+y-s_3+t_1=10,\quad P-3x-5y=0.$ Check by substitution: $x=20$, $y=10$ gives $s_1=120-70=50$, $s_2=150-90=60$ and $s_3=30-10=20$ with $t_1=0$.