Graphical solution of linear programsEdexcel A-Level Further Maths: Revision notes

With two variables each constraint is a half-plane bounded by a straight line. Draw the line (for example $2x+y=12$ passes through $(6,0)$ and $(0,12)$), decide which side satisfies the inequality by testing a point such as $(0,0)$, and shade out the unwanted side. What is left, inside all constraints and in the first quadrant ($x,y\ge0$), is the feasible region. Its corners are vertices, found as intersections of boundary lines. Solve two equations simultaneously: for $2x+y=12$ and $x+2y=10$ the vertex is $\left(\frac{14}{3},\frac83\right)$. Axis-vertices come from setting $x=0$ or $y=0$.

For $P=5x+4y$ the objective line $5x+4y=k$ has gradient $-\frac54$ and all points on it give the same $P=k$. Draw one such line (choose $k$ to make the intercepts easy, for example $k=20$) and slide it parallel across the feasible region.

• To maximise, move the line away from the origin; the optimum is the last vertex it touches.
• To minimise, move it towards the origin; the optimum is the first vertex it touches (when the region lies away from the origin). Read off the vertex, then substitute to find the optimal value. In the cleaning-company example the optimum is $\left(\frac{14}{3},\frac83\right)$ with $P=\frac{70}{3}+\frac{32}{3}=34$.

The optimum of a linear objective over a feasible region always occurs at a vertex. Find the coordinates of every vertex, evaluate the objective at each, and pick the largest (maximise) or smallest (minimise). Example: vertices $(0,0)$, $(6,0)$, $\left(\frac{14}{3},\frac83\right)$, $(0,5)$ give $P=0,30,34,20$, so the maximum is 34. If the objective line is parallel to a boundary edge, two vertices tie and every point on that edge is optimal (maximise $2x+y$ with vertices $(5,0)$ and $(3,4)$ both giving 10).

Sometimes the variables must be whole numbers (vehicles, boxes). The optimal vertex is often not whole, and rounding is unsafe: the rounded point may be infeasible or not optimal. Method: find the non-integer optimum first, then list whole-number feasible points close to it, calculate the objective at each, and compare. If the objective has whole-number coefficients, a whole-number point gives a whole-number value, which gives a neat bound. Example: maximise $P=3x+2y$ subject to $4x+3y\le26$, $x+2y\le10$. The optimum is $(6.5,0)$ with $P=19.5$. $(7,0)$ is infeasible and $(6,0)$ gives only 18. But $(5,2)$ is feasible with $P=19$, and as $P\le19.5$ is a whole number, 19 is the maximum.

To minimise cost $C=3x+4y$ with $x+y\ge8$ and $2x+5y\ge30$: the vertices are $(0,8)$, $\left(\frac{10}{3},\frac{14}{3}\right)$ and $(15,0)$, with $C=32$, $\frac{86}{3}\approx28.67$ and $45$. The minimum is at $\left(\frac{10}{3},\frac{14}{3}\right)$. With whole kilograms, $C$ is a whole number $\ge28.67$, so $C\ge29$. The point $(3,5)$ is feasible ($8\ge8$ and $31\ge30$) and gives $C=29$, so it is optimal.