Linear programming
D1 Topic 5, spec point by spec point (Linear programming). Each spec point has the method, worked examples written the way the mark scheme wants them, how the marks go and the mistakes that cost the most marks.
Spec5.1Formulating a linear program
Formulation of problems as linear programs.
The three parts
- Decision variables: say exactly what each letter stands for, with units ("\(x\) = the number of tables made per week").
- Objective: "maximise" or "minimise" an expression (\(P = 30x + 20y\)).
- Constraints: inequalities, including non-negativity (\(x, y \geqslant 0\)).
Translating the wording
| Words | Inequality |
|---|---|
| at most 10 items | \(x + y \leqslant 10\) |
| at least 40 in total | \(x + y + z \geqslant 40\) |
| at least twice as many \(x\) as \(y\) | \(x \geqslant 2y\) |
| no more than three times as many \(y\) as \(x\) | \(y \leqslant 3x\) |
| at least 30% of the items are \(y\) | \(y \geqslant 0.3(x + y)\), i.e. \(7y \geqslant 3x\) |
| at most 60% of the containers are small | \(x \leqslant 0.6(x + y + z)\), i.e. \(2x \leqslant 3y + 3z\) |
| each \(x\) uses 3 units, each \(y\) 5, with 1000 available | \(3x + 5y \leqslant 1000\) |
Check "twice as many": test numbers. If \(x = 10\) and \(y = 5\), there are twice as many \(x\), and \(x \geqslant 2y\) holds.
Simplify constraints to integer coefficients where you can; the scheme often asks for that.
formulation
A carpenter makes \(x\) tables and \(y\) chairs per week. At most 10 items in total. Finishing takes 1 hour per table and 3 per chair, with 18 hours available. At most 8 tables. Profit is £30 per table and £20 per chair.
Maximise \(P = 30x + 20y\)
subject to \(x + y \leqslant 10\), \(x + 3y \leqslant 18\), \(x \leqslant 8\), \(x, y \geqslant 0\).
- B1 cao for a constraint like \(3x + 5y \leqslant 1000\) (WDM11A Jan 2026 Q5a).
- Three-variable formulation: B1 for "minimise \(9x + 12y + 16z\)" (write "minimise", not "min"), B1s for simple constraints, M1 A1 for each percentage constraint simplified (WDM11 Jan 2022 Q14a).
- Reading constraints off a graph: B1 for two correct, B1 for all; using strict inequalities throughout loses a mark (WDM11 Jun 2025 Q8a).
Often asked as: very common (34 questions). Write constraints from words; define variables; read inequalities from a given feasible region.
Reversing "at least twice as many": writing \(2x \geqslant y\) instead of \(x \geqslant 2y\).
Leaving out non-negativity, or not defining the variables.
Spec5.2Graphical solution: ruler and vertex methods
Graphical solution of two-variable problems using the ruler (objective line) and vertex methods.
Drawing the feasible region
- Draw each constraint's boundary line (find two points, e.g. the intercepts).
- Shade the side you don't want (the Edexcel convention), leaving the feasible region \(R\) unshaded, and label it \(R\).
Vertex method
The optimum of a linear objective is always at a vertex of the feasible region.
- Find the coordinates of every vertex (solve the simultaneous equations of the two lines meeting there).
- Evaluate the objective at each.
- Choose the largest (maximise) or smallest (minimise).
Ruler (objective line) method
- Draw a line \(P = k\) for a convenient \(k\) (it has the gradient of the objective).
- Slide it parallel, away from the origin to maximise (or towards it to minimise).
- The last point of \(R\) it touches is optimal. Then find that vertex's exact coordinates by solving equations.
the carpenter (from 5.1)
Vertices of \(R\): \((0, 0)\), \((8, 0)\), \((8, 2)\) (from \(x = 8\) and \(x + y = 10\)), \((6, 4)\) (from \(x + y = 10\) and \(x + 3y = 18\)), \((0, 6)\).
| Vertex | \((0,0)\) | \((8,0)\) | \((8,2)\) | \((6,4)\) | \((0,6)\) |
|---|---|---|---|---|---|
| \(P = 30x + 20y\) | 0 | 240 | 280 | 260 | 120 |
Make 8 tables and 2 chairs for a profit of £280.
Ruler check: the objective line has gradient \(-\frac32\), steeper than \(x + y = 10\) (gradient \(-1\)), so sliding it out it leaves \(R\) at the corner where \(x = 8\) meets \(x + y = 10\).
- B1 for each line drawn accurately (within half a small square) and long enough to define \(R\), with \(R\) labelled (WDM11A Jan 2026 Q5b).
- Lines, objective, vertex: M1 A1 A1 for lines, then an objective line or vertex testing, then the exact optimum and its value, in context (WDM11 Jun 2025 Q5).
- Leftover resources: substitute the optimal values back into the constraints, with units (WDM11 Jan 2023 Q12e).
Often asked as: very common (42 questions). Draw constraints and find \(R\); find the optimum by either method; interpret in context; how much of a resource is left over.
Reading vertex coordinates from the graph when they should be calculated exactly.
Shading the feasible region instead of leaving it clear (follow the question's instruction).
Spec5.3Integer solutions
Consideration of problems where solutions must have integer values.
The idea
If the variables are counts (tables, people), the optimal vertex may not have whole-number coordinates. You can't just round it, because the rounded point may be outside \(R\) or not the best.
Method
- Find the exact optimal vertex.
- List the integer points near it (all the combinations of rounding each coordinate up and down, and others nearby along the boundary).
- Check each in every constraint and discard the infeasible ones.
- Evaluate the objective at the feasible ones and choose the best.
rounding fails
Maximise \(P = 3x + 4y\) subject to \(5x + 3y \leqslant 150\), \(x \geqslant 2y\), \(x, y \geqslant 0\), with \(x, y\) integers.
Optimal vertex: \(x = 2y\) meets \(5x + 3y = 150\) at \(13y = 150\): \((23.08, 11.54)\), \(P = 115.4\).
Test: \((23, 12)\) fails \(x \geqslant 2y\). \((24, 11)\) fails: \(5(24) + 3(11) = 153\). \((24, 12)\) fails: 156. \((23, 11)\): \(148 \leqslant 150\) and \(23 \geqslant 22\), feasible, \(P = 113\).
Nearby \((24, 10)\): feasible, \(P = 112\). So the integer optimum is \((23, 11)\) with \(P = 113\).
- dM1 for testing integer points near the optimum in the right inequalities (at least two or three points), A1 for identifying the optimal point with the infeasible ones shown to fail, and the objective value (WDM11A Jun 2026 Q8d, WDM11 Jan 2026 Q8c).
- B1 cao for the integer solution (WDM11 Jan 2025 Q8c).
Often asked as: the last part of an LP question.
Rounding the vertex to the nearest integers without checking the constraints.
Checking feasibility in only one constraint.