Linear Programming (Graphical Method)

A factory wants the most profitable mix of products; a diet must meet nutritional minimums at least cost; an airline must crew its flights within legal limits. Each is an optimisation under constraints: maximise (or minimise) a quantity while respecting a list of restrictions. When both the objective and the constraints are linear, the problem is a linear programme (LP), and with just two decision variables it can be solved by a beautiful picture — plot the constraints, shade the region of allowed points, and the best solution always sits at a corner. This lesson builds the graphical method rigorously, proves why the optimum is at a vertex, and prepares the ground for the Simplex algorithm (next lesson) that handles three variables or more.

---

1. Where this sits in AQA 7367

This is a core optimisation topic of the Paper 3 Discrete option (7367/3D) (Paper 3: 2 h, 100 marks, 33⅓%; AO1 40% / AO2 25% / AO3 35%). Formulating a worded scenario into variables, an objective and constraints is AO3 (modelling in context); plotting, finding vertices and evaluating is AO1; the objective-line argument and interpreting integer-feasibility are AO2. Formulation marks are among the most reliably available — and most often dropped through careless inequalities. The graphical method also feeds directly into the Simplex algorithm of the next lesson, so a secure understanding of why the optimum sits at a vertex here pays off when the picture disappears in three or more variables.

---

2. Core theory: anatomy of a linear programme

Every LP has three ingredients:

Component	Meaning
Decision variables	the quantities to choose, e.g. $x, y \ge 0$x,y≥0
Objective function	the linear quantity to optimise, e.g. $P = 30x + 50y$P=30x+50y
Constraints	linear inequalities limiting the variables

By convention the variables are non-negative: $x \ge 0,\ y \ge 0$x≥0, y≥0 (you cannot make $-3$−3 chairs). A point $(x,y)$(x,y) satisfying all constraints is feasible; the set of all feasible points is the feasible region, and it is always a convex polygon (possibly unbounded). The optimum is the feasible point giving the best objective value.

Convexity is the structural fact that makes the whole method work, and it is worth seeing why. Each single inequality $ax + by \le c$ax+by≤c defines a half-plane — everything on one side of a line — which is a convex set (the segment joining any two of its points stays inside). The feasible region is the intersection of all these half-planes (one per constraint, plus the two axes), and an intersection of convex sets is itself convex. Geometrically the region is therefore a polygon with straight edges and no "dents"; its corners are the vertices, formed where two constraint lines cross. Because the objective $ax + by$ax+by is linear, its value changes at a constant rate as you move in any fixed direction, so it can never have a maximum in the flat interior of an edge or face — it is always pushed to a corner. That single observation, made precise in §10, is the Fundamental Theorem of Linear Programming, and it is why the entire graphical method reduces to "find the vertices and test them".

Worked Example 2.1 — formulation (with M1/A1 mark scheme)

A workshop makes chairs ($x$x) and tables ($y$y). Each chair uses $2$2 h carpentry and $1$1 h finishing; each table uses $1$1 h carpentry and $2$2 h finishing. There are $100$100 h of carpentry and $80$80 h of finishing available. Profit is £30 a chair and £50 a table. Formulate the LP.

$$\begin{aligned} \text{Maximise } & P = 30x + 50y \\ \text{subject to } & 2x + y \le 100 \quad (\text{carpentry}) \\ & x + 2y \le 80 \quad (\text{finishing}) \\ & x \ge 0,\ y \ge 0. \end{aligned}$$Maximise subject to ​P=30x+50y2x+y≤100(carpentry)x+2y≤80(finishing)x≥0, y≥0.​

(M1 for a correct objective with the right coefficients; A1 for both resource constraints with the correct inequality direction and non-negativity.)

Exam tip. Resource limits give "$\le$≤" constraints; nutritional or demand minimums give "$\ge$≥". Always state $x,y \ge 0$x,y≥0 explicitly — it is a free mark candidates routinely forget.

---

3. The graphical method (with M1/A1 mark scheme)

1. Draw each constraint as a line (replace $\le/\ge$≤/≥ by $=$=); use the two intercepts.
2. Shade the feasible region — for "$\le$≤" the allowed side is towards the origin (test $(0,0)$(0,0)); for "$\ge$≥" it is away from it.
3. Find the vertices of the region by solving the relevant pairs of lines simultaneously.
4. Evaluate the objective at every vertex and pick the best.

Worked Example 3.1 — solving the workshop LP

Lines. $2x + y = 100$2x+y=100: intercepts $(50,0)$(50,0) and $(0,100)$(0,100). $x + 2y = 80$x+2y=80: intercepts $(80,0)$(80,0) and $(0,40)$(0,40).

Intersection of the two constraints. From $2x + y = 100$2x+y=100, $y = 100 - 2x$y=100−2x; substitute into $x + 2y = 80$x+2y=80: $x + 2(100 - 2x) = 80 \;\implies\; x + 200 - 4x = 80 \;\implies\; -3x = -120 \;\implies\; x = 40,\ y = 20.$x+2(100−2x)=80⟹x+200−4x=80⟹−3x=−120⟹x=40, y=20. (M1 for a correct simultaneous solution; A1 for the vertex $(40, 20)$(40,20).)

Vertices of the feasible region (check each is feasible):

• $O(0,0)$O(0,0) — trivially feasible.
• $(50, 0)$(50,0) — on carpentry; finishing $50 + 0 = 50 \le 80$50+0=50≤80 ✓.
• $(40, 20)$(40,20) — both constraints binding ✓.
• $(0, 40)$(0,40) — on finishing; carpentry $0 + 40 = 40 \le 100$0+40=40≤100 ✓.

(The intercepts $(80,0)$(80,0) and $(0,100)$(0,100) are infeasible — they violate the other constraint — so they are not vertices of the region.)

$$\begin{array}{c|c} \text{Vertex} & P = 30x + 50y \\ \hline (0,0) & 0 \\ (50,0) & 1500 \\ (40,20) & 1200 + 1000 = 2200 \\ (0,40) & 2000 \end{array}$$Vertex(0,0)(50,0)(40,20)(0,40)​P=30x+50y015001200+1000=22002000​​

The maximum is $P = 2200$P=2200 at $(40, 20)$(40,20) — make $40$40 chairs and $20$20 tables. (A1 for evaluating all vertices; A1 for the correct optimum and interpretation.)

Here is the feasible region (shaded), the two constraint lines, and the optimum vertex $(40,20)$(40,20):

Exam tip. The optimum always lies at a vertex of the feasible region (a theorem — see §10). Evaluate the objective at every vertex; do not eyeball it. Marks are awarded for the table of vertex values, not just the final answer.

---

4. The objective-line (iso-profit) method

Instead of testing every vertex, draw a line of constant objective value:

$30x + 50y = c \quad\Longleftrightarrow\quad y = -\tfrac{3}{5}x + \tfrac{c}{50}.$30x+50y=c⟺y=−53​x+50c​.

All such lines are parallel (gradient $-\tfrac{3}{5}$−53​); increasing $c$c slides the line away from the origin. Push it as far as possible while it still touches the feasible region — the last vertex it meets is optimal. For the workshop, the objective gradient $-\tfrac{3}{5} = -0.6$−53​=−0.6 lies between the two constraint gradients ($2x+y$2x+y has gradient $-2$−2; $x+2y$x+2y has gradient $-\tfrac12$−21​), which is exactly why the optimum is the intersection vertex $(40,20)$(40,20) rather than an axis vertex.

This gradient comparison is a powerful shortcut: if the objective line is steeper than every constraint it will leave the region at a vertex on one axis; if shallower than every constraint, at the other; if its gradient lies between two binding constraints, the optimum is their intersection. It also explains the special case of multiple optima: if the objective line is parallel to a binding constraint, every point on that edge is optimal.

Reading a region from a graph

AQA frequently reverses the task: a region is drawn and you must write down the inequalities that define it, or you are given inequalities and asked to shade the region. The technique is the same in either direction. To read off an inequality from a boundary line, first find the line's equation from two points on it (its intercepts are easiest), then decide the direction by testing a point you can see is inside the region — usually the origin. If $(0,0)$(0,0) satisfies the trial equation with "$\le$≤", the region is the "$\le$≤" side; otherwise it is "$\ge$≥". For example, a boundary through $(6,0)$(6,0) and $(0,4)$(0,4) has equation $\tfrac{x}{6} + \tfrac{y}{4} = 1$6x​+4y​=1, i.e. $2x + 3y = 12$2x+3y=12; if the shaded region contains the origin, the inequality is $2x + 3y \le 12$2x+3y≤12. When several lines bound a region, repeat for each, then add $x \ge 0$x≥0 and $y \ge 0$y≥0 if the region sits in the first quadrant. A common convention in exams is to shade the unwanted side of each line (so the feasible region is left clear); always read the rubric to see which convention the paper uses, because shading the wrong side is a frequent and avoidable loss of marks.

---

5. A second walkthrough: a minimisation

Minimise $C = 3x + 2y$C=3x+2y subject to $x + y \ge 10$x+y≥10, $2x + y \ge 14$2x+y≥14, $x, y \ge 0$x,y≥0.

Lines. $x + y = 10$x+y=10: $(10,0),(0,10)$(10,0),(0,10). $2x + y = 14$2x+y=14: $(7,0),(0,14)$(7,0),(0,14). For "$\ge$≥" the feasible region lies away from the origin, so it is unbounded above-right; its corner points are where the boundary turns.

Intersection. Subtracting $x + y = 10$x+y=10 from $2x + y = 14$2x+y=14 gives $x = 4$x=4, then $y = 6$y=6: the vertex $(4,6)$(4,6).

Corner points of the boundary: $(0,14)$(0,14) (on $2x+y=14$2x+y=14; $0+14 \ge 10$0+14≥10 ✓), $(4,6)$(4,6), and $(10,0)$(10,0) (on $x+y=10$x+y=10; $20 \ge 14$20≥14 ✓).

$$\begin{array}{c|c} \text{Vertex} & C = 3x + 2y \\ \hline (0,14) & 28 \\ (4,6) & 12 + 12 = 24 \\ (10,0) & 30 \end{array}$$Vertex(0,14)(4,6)(10,0)​C=3x+2y2812+12=2430​​

The minimum is $C = 24$C=24 at $(4,6)$(4,6). (Because the region is unbounded, a minimisation still has a finite optimum at a vertex, but the maximum would be unbounded — a crucial distinction.) The objective gradient $-\tfrac{3}{2}$−23​ lies between the constraint gradients $-1$−1 and $-2$−2, confirming the intersection vertex is optimal.

---

6. Integer programming and special cases