| Statement | What it asks |
|---|---|
| CG6 | Express real situations in terms of linear inequalities |
| CG7 | Use graphs of linear inequalities to solve 2-dimensional maximisation and minimisation problems |
| CG8 | Know the definition of objective function and be able to find it in 2-dimensional cases |
Objective function: the quantity you want to maximise or minimise
- Define your two variables clearly, with units.
- Write the objective function — the thing to be maximised or minimised.
- Write one inequality for each limited resource.
- Add the non-negativity constraints $x \geqslant 0$, $y \geqslant 0$.
- Simplify each inequality by dividing out common factors.
A workshop makes bookcases and desks. A bookcase needs $3$ hours of assembly and $2$ hours of finishing, and sells for a profit of £$40$. A desk needs $5$ hours of assembly and $2$ hours of finishing, for a profit of £$60$. There are $60$ assembly hours and $32$ finishing hours available. Set the problem up.
- Draw each boundary line using its two axis intercepts.
- Test the origin in each inequality to find the correct side.
- Shade to leave the feasible region clear, and label it $R$.
- Find each vertex algebraically, by solving pairs of boundary lines.
2. Evaluate the objective function at each one
3. Pick the largest (or smallest) value
Maximise $P = 40x + 60y$ subject to $3x + 5y \leqslant 60$, $x + y \leqslant 16$, $x \geqslant 0$, $y \geqslant 0$.
| Vertex | $P = 40x + 60y$ |
|---|---|
| $(0, 0)$ | $0$ |
| $(16, 0)$ | $640$ |
| $(10, 6)$ | $400 + 360 = 760$ |
| $(0, 12)$ | $720$ |
A farmer must supply at least $24$ units of nitrogen and at least $16$ units of phosphate. Feed A gives $2$ nitrogen and $2$ phosphate per sack at £$3$; feed B gives $6$ nitrogen and $2$ phosphate per sack at £$5$. Minimise the cost.
| Vertex | $C = 3x + 5y$ |
|---|---|
| $(12, 0)$ | $36$ |
| $(6, 2)$ | $18 + 10 = 28$ |
| $(0, 8)$ | $40$ |
- Find the exact vertex as usual.
- If it has whole-number coordinates, you are finished.
- If not, test the nearby whole-number points — checking each one still satisfies every constraint.
- Choose the best of the valid ones.
Maximise $P = 5x + 4y$ subject to $2x + 3y \leqslant 13$, $x + y \leqslant 5$, $x, y \geqslant 0$, with $x$ and $y$ whole numbers.
Objective function
The quantity being optimised.
Constraints
One inequality per limited resource.
Don't forget
$x \geqslant 0$, $y \geqslant 0$.
Simplify
Divide out common factors before plotting.
Feasible region
The overlap of all the constraints.
The key fact
The optimum is at a vertex.
Vertices
Solve boundary lines in pairs — never read them off.
Method
Tabulate the objective at every vertex.
Minimisation
"At least" constraints give an unbounded region.
Whole numbers
Test nearby integer points; recheck all constraints.
Define "objective function".
▶ Show solution
The objective function is the expression, in the problem's variables, for the quantity being maximised or minimised — for example the profit $P = 40x + 60y$ or the cost $C = 3x + 5y$.
A chair needs $2$ m of timber and a table needs $5$ m. There is $40$ m available. Write the constraint.
▶ Show solution
With $x$ chairs and $y$ tables: $2x + 5y \leqslant 40$.
Evaluate $P = 3x + 7y$ at the vertices $(0,0)$, $(4,0)$, $(2,3)$ and $(0,4)$, and state the maximum.
▶ Show solution
$(0,0)$: $0$
$(4,0)$: $12$
$(2,3)$: $6 + 21 = 27$
$(0,4)$: $28$
Maximum $P = 28$ at $(0, 4)$.
Find the vertex where $2x + y = 10$ meets $x + 2y = 11$.
▶ Show solution
Double the first: $4x + 2y = 20$.
Subtract the second: $3x = 9$, so $x = 3$.
Then $y = 10 - 6 = 4$. The vertex is $(3, 4)$.
Simplify the constraint $15x + 25y \leqslant 300$.
▶ Show solution
Divide by $5$: $3x + 5y \leqslant 60$.
Maximise $P = x + y$ subject to $x + 2y \leqslant 8$, $3x + y \leqslant 9$, $x, y \geqslant 0$.
▶ Show solution
Axis vertices: $(3, 0)$ from $3x \leqslant 9$; $(0, 4)$ from $2y \leqslant 8$.
Slanted lines meet: $x + 2y = 8$ and $3x + y = 9$. From the second, $y = 9 - 3x$:
$x + 18 - 6x = 8$, so $-5x = -10$ and $x = 2$, $y = 3$.
$(0,0)$: $0$; $(3,0)$: $3$; $(2,3)$: $5$; $(0,4)$: $4$
Maximum $P = 5$ at $(2, 3)$.
Minimise $C = 2x + 3y$ subject to $x + y \geqslant 6$, $2x + y \geqslant 8$, $x, y \geqslant 0$.
▶ Show solution
Axis vertices: $(0, 8)$ from $y \geqslant 8$ — check $x+y = 8 \geqslant 6$ ✓; and $(6, 0)$ from $x \geqslant 6$ — check $2x = 12 \geqslant 8$ ✓
Lines meet: subtracting $x+y=6$ from $2x+y=8$ gives $x = 2$, so $y = 4$.
$(0,8)$: $24$; $(2,4)$: $4 + 12 = 16$; $(6,0)$: $12$
Minimum $C = 12$ at $(6, 0)$.
Explain why the optimum of a linear objective function cannot occur strictly inside the feasible region.
▶ Show solution
From any interior point you can move a small distance in the direction that increases the objective function, and still remain inside the region.
So an interior point can always be improved upon, and therefore cannot be optimal.
Moving in that direction repeatedly, you must eventually reach a boundary, and then slide along it to a corner. Hence the optimum lies at a vertex (or along a whole edge, if the objective line happens to be parallel to that edge).
A vertex is found at $\left(\tfrac{7}{2}, \tfrac{9}{2}\right)$, but $x$ and $y$ must be whole numbers. Describe carefully how you would proceed.
▶ Show solution
Test the whole-number points near the vertex: $(3,4)$, $(3,5)$, $(4,4)$ and $(4,5)$.
For each, first check it satisfies every constraint — some will lie outside the region, because the vertex is a corner and at least one constraint is tight there.
Then evaluate the objective function at the surviving points and take the best.
You should not simply round the vertex to the nearest integers, because the rounded point may be infeasible.
A bakery makes loaves and rolls. Each loaf needs $500$ g of flour and $10$ minutes of oven time; each roll needs $100$ g of flour and $4$ minutes of oven time. There is $30$ kg of flour and $8$ hours of oven time each day. Loaves sell at a profit of £$1.20$, rolls at £$0.30$.
(a) Write down the objective function and the constraints. (b) Find all the vertices of the feasible region. (c) Find the production plan that maximises profit. (d) The bakery is offered extra flour. Explain whether this would increase the maximum profit.
▶ Show solution
Let $x$ = loaves and $y$ = rolls.
(a) Maximise $P = 1.2x + 0.3y$.
Flour (in grams): $500x + 100y \leqslant 30\,000$, which simplifies to $5x + y \leqslant 300$.
Oven (in minutes): $10x + 4y \leqslant 480$, which simplifies to $5x + 2y \leqslant 240$.
And $x \geqslant 0$, $y \geqslant 0$.
(b) On the $x$-axis: flour gives $x \leqslant 60$, oven gives $x \leqslant 48$. The binding one is $48$, so $(48, 0)$.
On the $y$-axis: flour gives $y \leqslant 300$, oven gives $y \leqslant 120$. The binding one is $120$, so $(0, 120)$.
Where the slanted lines meet: subtracting $5x + y = 300$ from $5x + 2y = 240$ gives $y = -60$.
A negative $y$ means the lines cross outside the first quadrant, so this is not a vertex of the feasible region.
Vertices: $(0,0)$, $(48, 0)$, $(0, 120)$.
(c) $(0,0)$: $P = 0$
$(48, 0)$: $P = 1.2 \times 48 = £57.60$
$(0, 120)$: $P = 0.3 \times 120 = £36.00$
The maximum profit is £$57.60$, from $48$ loaves and no rolls.
Check: flour used $= 48 \times 500 = 24$ kg $\leqslant 30$ kg ✓; oven $= 480$ min $= 8$ h ✓
(d) No. At the optimum only $24$ kg of the $30$ kg of flour is used — there is already $6$ kg spare.
The binding constraint is oven time, which is fully used. Extra flour cannot be baked, so it would not raise the profit at all. To increase profit the bakery needs more oven capacity, not more flour.