Graphical solution of linear programsEdexcel International A Level Maths: Revision notes

With two variables, a linear program can be solved on a graph. For each constraint, draw the boundary line (replace the inequality sign with $=$), then decide which side satisfies it, by testing a point such as the origin (if the line does not pass through it). Shade out (or label) the unwanted side for each inequality, so that the feasible region $R$ is left clear. The region where all constraints hold is bounded by the axes (from $x,y\ge0$) and the lines. The corner points of the region are its vertices. Their coordinates are found by reading the graph, or exactly by solving the two boundary equations simultaneously. For $x+y=10$ and $3x+y=18$: subtracting gives $2x=8$, so the vertex is $(4,6)$. Always check that a vertex satisfies every other constraint.

An optimal solution of a linear program always occurs at a vertex of the feasible region (or along an edge between two vertices which gives the same value). So:

1. Find the coordinates of every vertex of the feasible region.
2. Evaluate the objective function at each vertex.
3. Choose the largest value (to maximise) or the smallest (to minimise). Example: maximise $P=5x+4y$ with vertices $(0,0)$, $(6,0)$, $(4,6)$, $(0,10)$. The values are $0$, $30$, $44$, $40$. The maximum is $P=44$ at $(4,6)$. State the values of both the variables and the objective at the end.

The objective function $P=ax+by$ is a family of parallel lines, one for each value of $P$. Each has gradient $-\frac{a}{b}$. To use the ruler method:

1. Draw one objective line, such as $5x+4y=20$, choosing a value of $P$ that gives a convenient line inside the graph.
2. Place a ruler along it and slide it parallel to the line.
3. For maximising, move away from the origin: the optimum is the last point of the feasible region the ruler touches. For minimising, start on the origin side and move away from the origin: the optimum is the first point of the region touched.
4. Read off the vertex, then find its coordinates exactly by solving the two boundary equations, and calculate $P$. The line has a negative gradient when $a$ and $b$ are positive, so check your line slopes down to the right.

Minimisation problems usually have constraints of the form $\ge$ (requirements such as energy or protein) and the feasible region is on the far side of the lines from the origin. The optimum is then the point that makes the objective as small as possible: with the ruler, it is the first point of the region touched when the line moves away from the origin. Example: minimise $C=4x+3y$ subject to $2x+y\ge12$, $x+2y\ge9$, $x+y\le10$. The vertices are $(2,8)$, $(5,2)$, $(9,0)$ and $(10,0)$, with $C=32$, $26$, $36$, $40$. The minimum is $C=26$ at $(5,2)$. The point $(5,2)$ is found by solving $2x+y=12$ and $x+2y=9$.

If $x$ and $y$ must be whole numbers (tables, parcels), the optimal vertex may be fractional. The solution is then the best integer point inside the feasible region. Do not just round: a rounded point may lie outside the region or not be the best. Method: find the optimal vertex, then test integer points near it, checking every constraint. Or use the ruler method: move the objective line back from the optimal vertex, parallel to itself, until it first passes through a feasible integer point; that point is the optimum. Example: maximise $P=5x+4y$ subject to $2x+3y\le14$ and $4x+y\le15$. The vertex $(3.1,\,2.6)$ gives $P=25.9$. The point $(3,3)$ is infeasible ($15>14$), and $(3,2)$ is feasible with $P=23$. The other points are worse ($(2,3)$ gives 22, $(1,4)$ gives 21), so the optimum is $(3,2)$ with $P=23$. The integer optimum is never better than the non-integer optimum.