Formulating and graphical solution of LPsAQA A-Level Further Maths: Revision notes

Linear programming finds the best value of a linear objective function subject to linear constraints. To formulate a problem: (1) define the decision variables, e.g. $x$ tables and $y$ chairs; (2) write the objective function to be maximised (profit) or minimised (cost), e.g. $P=50x+30y$; (3) write each constraint as an inequality using the same units on both sides, e.g. $4x+2y\leq40$ for 40 hours of carpentry when a table takes 4 hours and a chair takes 2; (4) include non-negativity constraints $x\geq0$, $y\geq0$. Phrases translate as follows: 'at most' is $\leq$, 'at least' is $\geq$, 'at least twice as many chairs as tables' is $y\geq2x$.

For each constraint, draw its boundary line: find two points, often the axis intercepts, by setting $x=0$ then $y=0$. For $2x+y\leq14$ the intercepts are $(7,0)$ and $(0,14)$. Test a point such as the origin to see which side satisfies the inequality, and shade the unwanted side so the feasible region is left clear. The feasible region is the set of points satisfying every constraint. Its corners are called vertices. A vertex is found either as an axis intercept or by solving two boundary equations simultaneously, for example $2x+y=14$ and $x+2y=10$ meet where $x=6$ and $y=2$.

Write the objective as $ax+by=k$. It is a line of gradient $-\frac ab$, and different values of $k$ give parallel lines. Draw one such line through the feasible region, then slide it parallel to itself. For a maximum, move it away from the origin until the last point of the feasible region it touches, which is an optimal vertex. For a minimum, move it towards the origin until the first point it touches. Example: $P=3x+2y$ has gradient $-\frac32$. It lies between the gradients $-2$ of $2x+y=14$ and $-\frac12$ of $x+2y=10$, so the optimum is where those two lines meet, $(6,2)$, giving $P=22$.

The optimal value of a linear objective over a feasible region always occurs at a vertex. So an alternative to the ruler method is to list every vertex, evaluate the objective function at each, and choose the greatest (maximise) or least (minimise). Example: for $P=3x+2y$ the vertices $(0,0)$, $(7,0)$, $(6,2)$, $(0,5)$ give $0$, $21$, $22$, $10$, so the maximum is 22. For a minimum cost over $(6,3)$, $(4,6)$, $(8,2)$ with $C=3x+4y$, the values are $30$, $36$, $32$, so the minimum is 30 at $(6,3)$. This method is reliable, and it also shows near-optimal vertices.

Give the answer in the language of the problem, with units: say how many of each item to make, and the maximum profit or minimum cost. Adding or changing a constraint can move the optimum. Example: in a school shop with $3x+2y\leq120$, $x+y\leq50$, $y\geq15$ and profit $4x+3y$, the optimum is $(20,30)$ with profit £170. Adding $x\geq y$ makes $(20,30)$ infeasible, and the new optimum is $(24,24)$ with profit £168. To check a point is feasible, substitute it into every constraint. A point such as $(5,4)$ in a feed problem requiring protein $3x+2y\geq24$ gives $23$, so it fails.