Edexcel International A Level Maths · D1 · Decision Mathematics 1
Linear programming
28 free, high-quality past-paper-style questions on Linear programming for Edexcel IAL Maths, each with a full mark scheme. For when you have finished the past papers, or want to practise one topic at a time.IAL Maths notes and flashcards →Not sure of your level? Diagnostic test →Multiple choice or structured questions, with the mark scheme as a separate PDF.28 new this month · 240 marks · Updated 26 October 2026 · Created by Evan Kotronis with AI assistance · How questions are checked
1IALM-D1-5-B-01D1 · ASEasy6 marks
A florist makes small and large bouquets each day. A small bouquet uses 4 roses and takes 10 minutes to make; a large bouquet uses 10 roses and takes 15 minutes. Each day 200 roses and 6 hours of making time are available. At least 5 large bouquets must be made each day. The profit is £6 on a small bouquet and £11 on a large bouquet. The florist wants to maximise the daily profit.
(a)
Define suitable decision variables.
(1)
(b)
Show that the time constraint can be written as 2x + 3y ≤ 72.
(2)
(c)
Write down the remaining constraints, simplifying where possible.
(2)
(d)
Write down the objective function.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
x = the number of small bouquets and y = the number of large bouquets made each day
B1
Part (b)
6 hours = 360 minutes, so 10x + 15y ≤ 360
M1
dividing by 5: 2x + 3y ≤ 72
A1
Part (c)
roses: 4x + 10y ≤ 200, i.e. 2x + 5y ≤ 100
B1
y ≥ 5 and x ≥ 0
B1
Part (d)
maximise P = 6x + 11y
B1
Model sketch
Figure: model answer: feasible region (shaded) for x small and y large bouquets; not to scale
Exam tip: Convert to one unit before writing a constraint: 6 hours of making time is 360 minutes when the times per bouquet are in minutes.
A café buys x kg of arabica beans and y kg of robusta beans each week. Write each of the following conditions as a linear inequality, simplified so that it has integer coefficients.
(a)
At least 30% of the total mass of beans bought must be robusta.
(2)
(b)
The mass of arabica must be at least twice the mass of robusta.
(1)
(c)
No more than 50 kg of beans in total can be stored.
(1)
(d)
Determine whether buying 30 kg of arabica and 15 kg of robusta satisfies all three conditions.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
y ≥ 0.3(x + y)
M1
10y ≥ 3x + 3y, so 7y ≥ 3x
A1
Part (b)
x ≥ 2y
B1
Part (c)
x + y ≤ 50
B1
Part (d)
7(15) = 105 ≥ 90 = 3(30); 30 ≥ 2(15) = 30; 45 ≤ 50 — all three hold, so yes
B1
Exam tip: Check a ratio inequality with numbers you know should work. 30 kg arabica and 15 kg robusta is exactly twice as much, so it must satisfy x ≥ 2y with equality.
The feasible region R is defined by x + 2y ≤ 18, 3x + 2y ≤ 30, x ≥ 0 and y ≥ 0. The lines x + 2y = 18 and 3x + 2y = 30 meet at the point B.
Figure: the region R (shaded) and the point B; not to scale
(a)
Find the coordinates of B.
(2)
(b)
By comparing gradients, find the point of R at which P = 2x + 3y is maximised, and the maximum value of P.
(2)
(c)
Find the maximum value of Q = x + 3y on R, and where it occurs.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
subtracting the equations: 2x = 12
M1
B is (6, 6)
A1
Part (b)
gradient of objective −2⁄3 lies between −3⁄2 and −1⁄2, so the optimum is at B
M1
P = 30 at (6, 6)
A1
Part (c)
gradient −1⁄3 is shallower than −1⁄2, so the last point touched is the vertex on the y-axis (or compare Q = 27 at (0, 9) with 24 at B)
M1
Q = 27 at (0, 9)
A1
Exam tip: If the objective gradient lies between the gradients of the two edges meeting at a vertex, that vertex is optimal. If it is shallower or steeper than both, move to the next vertex.
Figure 1 shows four straight lines L1, L2, L3 and L4 and the shaded region R, which is the feasible region of a linear programming problem. The y-axis also forms part of the boundary of R.
(a)
Find the equations of L1 and L2.
(2)
(b)
Write down the four inequalities, other than x ≥ 0, that define R.
(2)
(c)
Use the vertex method to find the maximum value of P = 3x + 4y on R, and the point at which it occurs.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
L1 passes through (0, 8) with gradient −½: x + 2y = 16
B1
L2 passes through (0, 2) with gradient 1: y = x + 2
B1
Part (b)
x + 2y ≤ 16 and y ≤ x + 2
B1
x ≤ 10 and y ≥ 1
B1
Part (c)
vertices (0, 1), (10, 1), (10, 3), (4, 6), (0, 2) give P = 4, 34, 42, 36, 8
M1
maximum P = 42 at (10, 3)
A1
Exam tip: Read each line through two points where it crosses gridlines exactly, such as (0, 8) and (4, 6), then find the gradient. Points that only look close to a gridline give wrong equations.
Figure 1 shows the lines x + y = 12, y = 2x and y = 2. Five of the regions into which they divide the first quadrant are labelled A, B, C, D and E. The region R is defined by x + y ≤ 12, y ≤ 2x, y ≥ 2.
(a)
State which labelled region is R, and write down the three inequalities, other than x ≥ 0, that together define region A.
(2)
(b)
Find the coordinates of the vertices of R.
(2)
(c)
Find the maximum and minimum values of P = 2x + 3y on R.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
R is region D (below x + y = 12, below y = 2x, above y = 2)
B1
A: y ≥ 2x, x + y ≤ 12 and y ≥ 2
B1
Part (b)
y = 2 meets y = 2x at (1, 2) and x + y = 12 at (10, 2)
B1
y = 2x in x + y = 12: 3x = 12, (4, 8)
B1
Part (c)
P = 8, 26, 32 at (1, 2), (10, 2), (4, 8)
M1
maximum 32 at (4, 8), minimum 8 at (1, 2)
A1
Exam tip: To decide which side of a line an inequality describes, test a point that is not on the line. For y ≤ 2x, the point (5, 0) gives 0 ≤ 10, so the side below and to the right of y = 2x is included.
A workshop makes pillar candles and jar candles. Figure 1 shows the amount of each resource available per day, the amount of each resource used by one candle and the profit on each candle. The workshop makes x pillar candles and y jar candles each day and wants to maximise its daily profit.
(a)
Use Figure 1 to write down the three resource constraints, simplifying each so that it has integer coefficients.
(3)
(b)
Write down the objective function and the remaining constraints.
(1)
(c)
Find the vertices of the region defined by the moulding and packing constraints together with x ≥ 0 and y ≥ 0.
(1)
(d)
Hence show that the supply of wax never limits production.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
wax: 0.4x + 0.3y ≤ 36, i.e. 4x + 3y ≤ 360
B1
moulding: 12x + 6y ≤ 480 (8 hours = 480 minutes), i.e. 2x + y ≤ 80
B1
packing: 5x + 5y ≤ 300, i.e. x + y ≤ 60
B1
Part (b)
maximise P = 3x + 2y, with x ≥ 0, y ≥ 0
B1
Part (c)
2x + y = 80 and x + y = 60 give x = 20; vertices (0, 0), (40, 0), (20, 40), (0, 60)
B1
Part (d)
4x + 3y = 0, 160, 200, 180 at these vertices
M1
4x + 3y is linear, so its greatest value on the region is 200 at a vertex, and 200 < 360: the wax constraint is satisfied everywhere and is redundant
A1
Common error: Mixing units in one constraint. Moulding times are in minutes, so the 8 hours available must be written as 480 minutes before the inequality is formed.
Figure 1 shows the feasible region R of a linear programming problem. R is bounded by the coordinate axes and the lines 3x + y = 30 and x + 2y = 20. The objective is to maximise P = ax + by, where a and b are positive constants. The dashed line on Figure 1 is the objective line P = 30.
(a)
Use Figure 1 to find the values of a and b.
(2)
(b)
Use the objective line method to find the maximum value of P and the point at which it occurs.
(2)
(c)
State the point of R at which Q = x + 3y is maximised.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
(6, 0) and (0, 5) lie on P = 30: 6a = 30 and 5b = 30
M1
a = 5, b = 6
A1
Part (b)
gradient of objective line −5⁄6 lies between −3 and −½, the gradients of the edges meeting at (8, 6), so the last point reached is (8, 6)
M1
P = 76 at (8, 6)
A1
Part (c)
gradient −1⁄3 is shallower than −½, so (0, 10) (Q = 30)
B1
Exam tip: An objective line is fixed by any two points on it. Where it crosses the axes, ax = P on y = 0 and by = P on x = 0 give the coefficients at once.
A farmer mixes x bags of feed A with y bags of feed B. Each bag of A contains 4 units of protein and 1 unit of fibre; each bag of B contains 1 unit of protein and 3 units of fibre. The mixture must contain at least 16 units of protein and at least 15 units of fibre, and at least 2 bags of B must be used. A bag of A costs £6 and a bag of B costs £4. The farmer wants to minimise the cost.
(a)
Write down the constraints, other than the non-negativity constraints.
(3)
(b)
Find the coordinates of the vertices of the feasible region.
(3)
(c)
Find the minimum cost, and explain why there is no maximum cost.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
protein: 4x + y ≥ 16
B1
fibre: x + 3y ≥ 15
B1
y ≥ 2
B1
Part (b)
4x + y = 16 with x = 0: (0, 16)
B1
4x + y = 16 and x + 3y = 15: 11x = 33, (3, 4)
B1
x + 3y = 15 with y = 2: (9, 2)
B1
Part (c)
C = 6x + 4y = 64, 34, 62 at the three vertices: minimum £34 with 3 bags of A and 4 bags of B
A1
the region is unbounded (it continues without limit away from O), so C can be made as large as we like
B1
Model sketch
Figure: model answer: feasible region R (shaded, unbounded) and its vertices; not to scale
Common error: Treating a minimising problem with “at least” constraints like a maximising one. The feasible region lies on the far side of the lines from O and is unbounded; the minimum is at the vertex nearest O in the direction of the cost line.
A craftsperson makes x tables and y shelves each month. A table uses 3 m² of timber and 4 hours of workshop time; a shelf uses 5 m² of timber and 2 hours. Each month 60 m² of timber and 41 hours of workshop time are available, so 3x + 5y ≤ 60, 4x + 2y ≤ 41, x, y ≥ 0. The profit is £50 on a table and £60 on a shelf. Only whole tables and shelves can be sold.
Figure: the feasible region (shaded) for tables x and shelves y; not to scale
(a)
Explain why the maximum of P = 50x + 60y over the feasible region occurs where 3x + 5y = 60 meets 4x + 2y = 41, and find the exact coordinates of this vertex V.
(3)
(b)
Find the value of P at V.
(1)
(c)
Find the number of tables and shelves that should be made to maximise the profit, justifying your answer.
A garden centre grows trays of herbs and trays of flowers. A tray of herbs needs 2 kg of compost and a tray of flowers needs 3 kg; 120 kg of compost is available. Each tray, of either type, takes up 1 m² of bench space and 50 m² is available. At least 10 trays of herbs must be grown, and the number of trays of flowers must not exceed twice the number of trays of herbs. The profit is £4 on a tray of herbs and £5 on a tray of flowers.
(a)
Formulate this as a linear programming problem, stating your decision variables.
(4)
(b)
Find the coordinates of the vertices of the feasible region.
(3)
(c)
Use the objective line method to find the optimal numbers of trays, and the maximum profit.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
x = number of trays of herbs, y = number of trays of flowers
B1
2x + 3y ≤ 120 and x + y ≤ 50
B1
x ≥ 10, y ≤ 2x, y ≥ 0
B1
maximise P = 4x + 5y
B1
Part (b)
(10, 0) and (50, 0)
B1
x + y = 50 with 2x + 3y = 120: (30, 20)
B1
y = 2x with 2x + 3y = 120: (15, 30); and (10, 20)
B1
Part (c)
gradient −4⁄5 lies between −1 and −2⁄3, so the optimum is where x + y = 50 meets 2x + 3y = 120
M1
30 trays of herbs and 20 trays of flowers, profit £220
A1
Model sketch
Figure: model answer: feasible region (shaded) for x trays of herbs and y trays of flowers; not to scale
Exam tip: “Must not exceed twice” is y ≤ 2x; the boundary y = 2x passes through the origin, so plot it through O and a second point such as (20, 40).
A removal company hires x large vans and y small vans for one day. A large van holds 16 m³ and a small van holds 4 m³, and at least 100 m³ of furniture must be moved. There are 12 drivers, one per van, and only 5 large vans are available. A large van costs £90 a day and a small van £20 a day. The company wants to minimise the cost.
(a)
Write down the constraints, simplifying where possible.
(2)
(b)
Find the coordinates of the vertices of the feasible region.
(3)
(c)
Find the vertex at which the cost is least, ignoring the need for whole numbers.
(1)
(d)
Find the number of each type of van that should be hired, and the cost.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
16x + 4y ≥ 100, so 4x + y ≥ 25
B1
x + y ≤ 12, x ≤ 5, x, y ≥ 0
B1
Part (b)
4x + y = 25 and x = 5: (5, 5)
B1
x + y = 12 and x = 5: (5, 7)
B1
4x + y = 25 and x + y = 12: 3x = 13, (13⁄3, 23⁄3)
B1
Part (c)
C = 90x + 20y: 550, 590 and 1630⁄3 ≈ 543.33, so the least cost is at (13⁄3, 23⁄3)
B1
Part (d)
rounding to (4, 8) fails 4x + y ≥ 25 (24); with x ≤ 4 we need y ≥ 25 − 4x ≥ 9 but y ≤ 12 − x, impossible, so x = 5
M1
x = 5 needs y ≥ 5: 5 large and 5 small vans, £550
A1
Model sketch
Figure: model answer: feasible region (shaded) for x large and y small vans; not to scale
Common error: Rounding a non-integer vertex to the nearest whole numbers without checking: (4, 8) moves only 96 m³, so it is not a feasible plan.
A print shop makes x posters and y banners each day, subject to x + 2y ≤ 40 (ink), 3x + 2y ≤ 60 (machine time), y ≥ 3, x ≥ 0. The profit is £a on a poster and £5 on a banner, so P = ax + 5y.
Figure: the feasible region (shaded) for posters x and banners y; not to scale
(a)
Find the coordinates of the vertices of the feasible region.
(3)
(b)
Given that a = 4, use the vertex method to find the maximum daily profit.
(2)
(c)
Find the range of values of a for which (10, 15) is an optimal point.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
(0, 3) and (0, 20)
B1
3x + 2y = 60 with y = 3: (18, 3)
B1
x + 2y = 40 with 3x + 2y = 60: (10, 15)
B1
Part (b)
P = 4x + 5y = 15, 87, 115, 100 at (0, 3), (18, 3), (10, 15), (0, 20)
M1
maximum £115 at (10, 15)
A1
Part (c)
the objective gradient −a⁄5 must lie between the gradients −3⁄2 and −1⁄2 of the two edges at (10, 15)
M1
1⁄2 ≤ a⁄5 ≤ 3⁄2
M1
2.5 ≤ a ≤ 7.5
A1
Exam tip: At the ends of the range (a = 2.5 or 7.5) the objective line lies along an edge, so the vertex is still optimal but shares the maximum with the neighbouring vertex.
A tea shop packs x boxes of green tea and y boxes of black tea each day, subject to 2x + y ≤ 20, x + y ≤ 14, x + 3y ≤ 36, x, y ≥ 0. The profit is £3 on every box, of either type.
Figure: the feasible region (shaded) for green tea x and black tea y; not to scale
(a)
Find the coordinates of the vertices of the feasible region.
(3)
(b)
Show that the maximum profit is not achieved at a single point, and state the maximum profit.
(2)
(c)
List all the optimal solutions in which whole numbers of boxes are packed.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
(0, 0), (10, 0) and (0, 12)
B1
2x + y = 20 with x + y = 14: (6, 8)
B1
x + y = 14 with x + 3y = 36: (3, 11)
B1
Part (b)
P = 3x + 3y = 3(x + y) is parallel to the edge x + y = 14, so every point of the edge from (6, 8) to (3, 11) is optimal
B1
maximum £42
B1
Part (c)
integer points on x + y = 14 with 3 ≤ x ≤ 6
M1
(3, 11), (4, 10), (5, 9), (6, 8)
A1
Exam tip: When the objective is a multiple of one constraint, the objective line slides on to that whole edge: give the edge, not just one vertex.
A call centre employs x full-time and y part-time staff on a particular day. A full-time member of staff works 8 hours and a part-time member works 4 hours, and at least 160 staff-hours are needed. At least 30 staff must be on duty, and the number of part-time staff must not be more than three times the number of full-time staff. A full-time member of staff is paid £120 for the day and a part-time member £50. The manager wants to minimise the total daily pay. Figure 1 shows the feasible region R.
(a)
Write down the constraints, other than the non-negativity constraints, showing that the staff-hours condition simplifies to 2x + y ≥ 40.
(3)
(b)
Verify by calculation the coordinates of the vertices (8, 24) and (10, 20) shown on Figure 1.
(2)
(c)
Find the minimum total daily pay and the numbers of staff that give it.
(2)
(d)
The daily pay of a part-time member of staff changes to £k, the pay of full-time staff staying at £120. Find the range of values of k for which the plan in (c) remains optimal.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
8x + 4y ≥ 160, so 2x + y ≥ 40
B1
x + y ≥ 30
B1
y ≤ 3x
B1
Part (b)
y = 3x in 2x + y = 40: 5x = 40, giving (8, 24)
B1
subtracting x + y = 30 from 2x + y = 40: x = 10, giving (10, 20)
B1
Part (c)
C = 120x + 50y = 2160, 2200, 3600 at (8, 24), (10, 20), (30, 0)
M1
minimum £2160 with 8 full-time and 24 part-time staff
A1
Part (d)
(8, 24) must cost no more than (10, 20): 960 + 24k ≤ 1200 + 20k
M1
4k ≤ 240, so 0 < k ≤ 60 (moving up along y = 3x always costs more)
A1
Exam tip: In a minimising problem with an unbounded region, slide the cost line towards O. The optimal point is the last point of R it touches, which is always a vertex on the side nearest O.
A boatyard builds x kayaks and y canoes each month. Figure 1 shows the feasible region R, bounded by the coordinate axes and the lines L1 and L2. The dots show the points of R with whole-number coordinates. The profit is £50 on a kayak and £70 on a canoe, and only whole boats can be sold.
(a)
Use Figure 1 to find the equations of L1 and L2, and write down the constraints that they represent.
(2)
(b)
Find the exact coordinates of the point V where L1 and L2 meet.
(2)
(c)
Explain why the maximum of P = 50x + 70y over R occurs at V, and find this maximum value.
(2)
(d)
Find the number of kayaks and canoes that should be built to maximise the profit, and the maximum profit. Justify your answer.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
L1 through (0, 10) and (6, 0): 5x + 3y ≤ 30
B1
L2 through (0, 7) and (4, 5): x + 2y ≤ 14
B1
Part (b)
5x + 3y = 30 and 5x + 10y = 70 give 7y = 40
M1
V = (18⁄7, 40⁄7)
A1
Part (c)
objective gradient −5⁄7 lies between −5⁄3 and −½
B1
P = 3700⁄7 ≈ 528.57
B1
Part (d)
V ≈ (2.57, 5.71); the nearest point (3, 6) is not in R, since 5(3) + 3(6) = 33 > 30
P = 10(5x + 7y) and 5x + 7y ≤ 370⁄7 ≈ 52.9 on R, so a whole-number plan has 5x + 7y ≤ 52 and P ≤ 520, which (2, 6) attains: 2 kayaks and 6 canoes, £520
A1
Common error: Rounding V to the nearest whole numbers. (3, 6) is the nearest grid point but lies outside R; only the dots in Figure 1 are possible plans.
A community garden plants x rows of carrots and y rows of beans. The constraints are x + y ≤ 14 (space), 2x + y ≤ 24 (watering time), x + 2y ≤ 24 (compost), x, y ≥ 0. Figure 1 shows the feasible region R and three proposed plans A, B and C. The profit is £30 on a row of carrots and £20 on a row of beans.
(a)
For each of the plans A, B and C, state whether it is feasible and, if it is not, which constraint it breaks.
(2)
(b)
Find the coordinates of the two vertices of R that do not lie on an axis.
(2)
(c)
Find the maximum profit and the plan that gives it.
(2)
(d)
The profit on a row of beans changes to £b, the profit on carrots staying at £30. Find the range of values of b for which the plan in (c) remains optimal.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
A (7, 8): 7 + 8 = 15 > 14 breaks the space constraint; B (11, 3): 2(11) + 3 = 25 > 24 breaks the watering constraint
B1
C (3, 10): 13 ≤ 14, 16 ≤ 24, 23 ≤ 24, so C is feasible
B1
Part (b)
2x + y = 24 and x + y = 14: (10, 4)
B1
x + 2y = 24 and x + y = 14: (4, 10)
B1
Part (c)
P = 30x + 20y = 360, 380, 320, 240 at (12, 0), (10, 4), (4, 10), (0, 12)
M1
£380: 10 rows of carrots and 4 rows of beans
A1
Part (d)
the edges at (10, 4) have gradients −2 and −1, so −2 ≤ −30⁄b ≤ −1
M1
15 ≤ b ≤ 30
A1
Exam tip: When a plan is tested, substitute it into every constraint, not only the one whose line looks closest. Point A is close to two lines but breaks only one of them.
A hiker plans the food for one day using x sachets of porridge and y energy bars. Figure 1 shows the mass of protein, carbohydrate and fat in one sachet of porridge and in one energy bar. The day's food must provide at least 50 g of protein and at least 180 g of carbohydrate, and no more than 100 g of fat. At most 10 sachets of porridge can be carried. A sachet of porridge has a total mass of 50 g and an energy bar 40 g. The hiker wants to minimise the total mass of this food.
(a)
Use Figure 1 to formulate this as a linear programming problem, simplifying the constraints.
(4)
(b)
Find the coordinates of the vertices of the feasible region.
(3)
(c)
Find the minimum total mass and the food that gives it.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
protein: 10x + 5y ≥ 50, i.e. 2x + y ≥ 10
B1
carbohydrate: 20x + 30y ≥ 180, i.e. 2x + 3y ≥ 18
B1
fat: 5x + 10y ≤ 100, i.e. x + 2y ≤ 20
B1
x ≤ 10, x, y ≥ 0; minimise M = 50x + 40y
B1
Part (b)
2x + y = 10 and 2x + 3y = 18: 2y = 8, (3, 4)
B1
2x + y = 10 meets x + 2y = 20 at (0, 10); 2x + 3y = 18 meets the x-axis at (9, 0)
B1
x = 10 gives (10, 0) and, with x + 2y = 20, (10, 5)
B1
Part (c)
M = 400, 310, 450, 500, 700 at (0, 10), (3, 4), (9, 0), (10, 0), (10, 5)
M1
310 g: 3 sachets of porridge and 4 energy bars
A1
Exam tip: Read each bar against the gridlines and write the nutrient totals in grams before dividing by common factors. The minimum and maximum requirements give inequalities in opposite directions.
Figure 1 shows the feasible region R of a linear programming problem. R is the quadrilateral ABCD, and its vertices lie at grid intersections.
(a)
Find the equation of the line through C and D, and write down the inequality, in the form ax + by ≤ c, given by the side CD of R.
(2)
(b)
Find the maximum and minimum values of Q = 3x − 2y on R, stating where each occurs.
(3)
(c)
Find the greatest value of S = x + y on R, and the greatest value of T = 2y − x, describing fully where each occurs.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
gradient 3⁄6 = ½: y − 5 = ½(x − 1), i.e. 2y − x = 9
B1
R lies below CD (test A: 2 − 2 = 0 ≤ 9): −x + 2y ≤ 9
B1
Part (b)
A(2, 1), B(9, 2), C(7, 8), D(1, 5)
B1
Q = 4, 23, 5, −7 respectively
M1
maximum 23 at B, minimum −7 at D
A1
Part (c)
S = 3, 11, 15, 6: greatest 15 at C
B1
T = 0, −5, 9, 9: greatest 9 at every point of the edge CD, which is parallel to T = 9
B1
Common error: Losing the sign of a negative coefficient. For Q = 3x − 2y the objective lines have a positive gradient, so the largest value is towards the bottom right of R and the smallest towards the top left.
A charity packs x food parcels and y hygiene kits each day. Figure 1 shows the feasible region R for the daily packing plan. R is bounded by the four lines L1, L2, L3 and L4.
(a)
Find the four inequalities that define R.
(3)
(b)
Interpret the inequalities from L1 and L2 in the context of the packing plan.
(2)
(c)
Each food parcel supports 3 people and each hygiene kit supports 2 people. Find the plan that supports the greatest number of people.
(2)
(d)
Packing costs £4 for a food parcel and £3 for a hygiene kit. Find the least daily packing cost for a plan in R with whole numbers of parcels and kits.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
L1 through O and (6, 12): y ≤ 2x
B1
L2 through O and (12, 6): x ≤ 2y
B1
L3: x + y ≤ 18; L4: y ≥ 3
B1
Part (b)
L1: the number of hygiene kits is at most twice the number of food parcels
B1
L2: the number of food parcels is at most twice the number of hygiene kits
the least cost on R is at (1.5, 3), which is not a whole-number plan; y ≥ 3 and x ≥ ½y force x ≥ 2
M1
(2, 3) is in R: least cost £17
A1
Common error: Reversing a ratio constraint. “Kits at most twice parcels” is y ≤ 2x. Check it with a plan you know is allowed, such as 5 parcels and 10 kits.
A factory assembles electric scooters and electric bikes. A scooter needs 5 hours of assembly and 1 hour of testing; a bike needs 4 hours of assembly and 3 hours of testing. Each day 80 hours of assembly and 39 hours of testing are available. At least 4 scooters must be made each day. The profit is £60 on a scooter and £70 on a bike. Only complete scooters and bikes can be sold.
(a)
Formulate this as a linear programming problem, stating your decision variables.
(4)
(b)
Describe how the feasible region R is drawn, and give the coordinates of its vertices.
(3)
(c)
Use the objective line method to find the exact coordinates of the optimal vertex V and the value of P there.
(3)
(d)
Find the optimal integer solution and the maximum daily profit, justifying your answer.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
x = number of scooters, y = number of bikes made each day
B1
5x + 4y ≤ 80
B1
x + 3y ≤ 39, x ≥ 4, y ≥ 0
B1
maximise P = 60x + 70y
B1
Part (b)
lines through (16, 0) and (0, 20); through (39, 0) and (0, 13); and x = 4
B1
R lies below both sloping lines, to the right of x = 4 and above the x-axis
B1
vertices (4, 0), (16, 0), (4, 35⁄3) and the intersection of the sloping lines
B1
Part (c)
objective gradient −6⁄7 lies between −5⁄4 and −1⁄3, so V is where the sloping lines meet
P = 10(6x + 7y) and the only point of R with 6x + 7y = 119 is V, which is not an integer point, so no integer point earns more than £1180
M1
8 scooters and 10 bikes, £1180
A1
Model sketch
Figure: model answer: feasible region R (shaded) for x scooters and y bikes; not to scale
Exam tip: A quick bound helps with integer answers: if every profit is a multiple of £10 and the vertex gives £1190 at a non-integer point, an integer point earning £1180 must be optimal.
A school hires x coaches and y minibuses to take 400 people on a trip. A coach has 48 seats and costs £300; a minibus has 16 seats and costs £120. Only 15 drivers are available, one per vehicle. At least 25% of the vehicles hired must be minibuses. The school wants to minimise the total cost.
(a)
Show that the seating condition gives 3x + y ≥ 25.
(2)
(b)
Write down the other constraints in simplified form.
(2)
(c)
Find the coordinates of the vertices of the feasible region.
(3)
(d)
Find the vertex at which the cost is least, ignoring the need for whole numbers of vehicles.
(2)
(e)
Find the number of coaches and minibuses the school should hire, and the cost.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
48x + 16y ≥ 400
M1
dividing by 16: 3x + y ≥ 25
A1
Part (b)
x + y ≤ 15
B1
y ≥ ¼(x + y) gives x ≤ 3y; and x, y ≥ 0
B1
Part (c)
3x + y = 25 with x = 3y: (7.5, 2.5)
B1
3x + y = 25 with x + y = 15: (5, 10)
B1
x + y = 15 with x = 3y: (11.25, 3.75)
B1
Part (d)
C = 300x + 120y = 2550, 2700, 3825 at the three vertices
M1
least cost at (7.5, 2.5)
A1
Part (e)
test integer points near (7.5, 2.5) against all constraints: (8, 2) fails 8 ≤ 6; (7, 3) seats 24 < 25
Figure: model answer: feasible region (shaded) for x coaches and y minibuses; not to scale
Common error: Writing a percentage condition the wrong way round. “At least 25% are minibuses” compares y with the total x + y: y ≥ 0.25(x + y), which simplifies to x ≤ 3y.
A chocolatier makes boxes of dark and milk chocolates. A box of dark needs 300 g of cocoa and 10 minutes of tempering; a box of milk needs 200 g of cocoa and 20 minutes of tempering. Each day 4.8 kg of cocoa and 4 hours of tempering time are available. At most 14 boxes of dark and at most 10 boxes of milk can be packed each day. The profit is £5 on a box of dark and £6 on a box of milk.
(a)
Taking x and y as the numbers of boxes of dark and milk made each day, formulate this as a linear programming problem, simplifying the constraints.
(4)
(b)
Find the coordinates of all the vertices of the feasible region.
(4)
(c)
Use the vertex method to find the maximum daily profit and how it is achieved.
(2)
(d)
The profit on a box of dark chocolates changes to £p, the profit on milk staying at £6. Find the range of values of p for which the plan in (c) remains optimal.
A farm shop prepares small and large hampers each day. A small hamper takes 20 minutes to prepare and a large hamper 30 minutes; 7 hours of preparation time are available. There are 18 baskets, one per hamper. At least 2 large hampers must be prepared. The profit is £10 on a small hamper and £13 on a large hamper.
(a)
Taking x and y as the numbers of small and large hampers, formulate this as a linear programming problem.
(3)
(b)
Find the coordinates of the vertices of the feasible region.
(3)
(c)
Use the objective line method to find the optimal plan and the maximum profit.
(2)
(d)
The shop decides that at least 8 large hampers must be prepared each day. Find the new optimal plan and the reduction in the maximum daily profit.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
20x + 30y ≤ 420, i.e. 2x + 3y ≤ 42
B1
x + y ≤ 18, y ≥ 2, x ≥ 0
B1
maximise P = 10x + 13y
B1
Part (b)
(0, 2) and (0, 14)
B1
x + y = 18 with y = 2: (16, 2)
B1
2x + 3y = 42 with x + y = 18: (12, 6)
B1
Part (c)
gradient −10⁄13 lies between −1 and −2⁄3, so the optimum is at (12, 6)
M1
12 small and 6 large hampers, £198
A1
Part (d)
(12, 6) is no longer feasible; new vertices (0, 8), (0, 14) and 2x + 3(8) = 42 gives (9, 8) (x + y = 18 with y = 8 gives (10, 8), but 2(10) + 3(8) = 44 > 42, so it is outside the region)
M1
P = 104, 182, 194 at (0, 8), (0, 14), (9, 8)
M1
9 small and 8 large hampers, £194; profit falls by £4
A1
Model sketch
Figure: model answer: feasible region (shaded) for x small and y large hampers; not to scale
Exam tip: When a new constraint is added, check whether the old optimum still satisfies it. If not, redraw the region: the new optimum is at a vertex on the new boundary line.
A bakery bakes x trays of sourdough loaves and y trays of bread rolls each day. A tray of sourdough needs 45 minutes of oven time and 6 kg of flour; a tray of rolls needs 1 hour of oven time and 2 kg of flour. Each day 12 hours of oven time and 60 kg of flour are available, and at least 2 trays of rolls must be baked. The profit is £36 on a tray of sourdough and £40 on a tray of rolls, and only whole trays can be baked. Figure 1 shows the three boundary lines needed for this problem, together with the dashed line y = x, which is used in parts (d) and (e).
(a)
Formulate this as a linear programming problem, showing that the oven-time constraint can be written as 3x + 4y ≤ 48.
(4)
(b)
Describe the feasible region R using the lines on Figure 1, and find the coordinates of its vertices.
(3)
(c)
Use the objective line method to find the optimal plan and the maximum daily profit.
(2)
(d)
The bakery decides that it must bake at least as many trays of rolls as trays of sourdough. Find the exact coordinates of the optimal vertex of the new feasible region, ignoring the need for whole trays, and the value of P there.
(2)
(e)
Find the optimal plan in whole trays under the new condition, and the maximum daily profit. Justify your answer.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
oven time in minutes: 45x + 60y ≤ 720
M1
dividing by 15: 3x + 4y ≤ 48
A1
flour: 6x + 2y ≤ 60, i.e. 3x + y ≤ 30; y ≥ 2, x ≥ 0
B1
maximise P = 36x + 40y
B1
Part (b)
R lies below both 3x + 4y = 48 and 3x + y = 30, on or above y = 2 and on or to the right of the y-axis
B1
(0, 2), (0, 12) and, from 3x + 2 = 30, (28⁄3, 2)
B1
subtracting the sloping lines: 3y = 18, giving (8, 6)
B1
Part (c)
objective gradient −9⁄10 lies between −3 and −3⁄4, so the optimum is at (8, 6)
M1
8 trays of sourdough and 6 trays of rolls, £528
A1
Part (d)
(8, 6) breaks y ≥ x; the optimum moves to where y = x meets 3x + 4y = 48: 7x = 48
M1
(48⁄7, 48⁄7), P = 3648⁄7 ≈ 521.14
A1
Part (e)
for each x, take the largest whole y with 3x + 4y ≤ 48 (3x + y ≤ 30 then also holds); x = 7 would need y ≥ 7 but allows only y ≤ 6, so x ≤ 6
M1
x = 0, 1, 2, 3: y = 12, 11, 10, 9, P = 480, 476, 472, 468; x = 4, 5, 6: y = 9, 8, 7, P = 504, 500, 496
M1
4 trays of sourdough and 9 trays of rolls, £504
A1
Exam tip: When a vertex is not a whole-number point, list the best whole-number y for each whole-number x near the vertex. The best plan, (4, 9), is not next to the vertex (48/7, 48/7), so rounding would miss it.
Figure 1 shows the feasible region R of a linear programming problem. R is the pentagon OABCD, where O is the origin, and its vertices lie at grid intersections. Several different objective functions are to be considered on R.
(a)
Find the three inequalities, other than x ≥ 0 and y ≥ 0, that define R.
(3)
(b)
The maximum value of P = ax + by on R is 72, and this maximum is attained at every point of the edge AB. Find a and b.
(3)
(c)
Find the range of values of the positive constant k for which Q = x + ky attains its maximum on R at C.
(3)
(d)
For k = 4, find every point of R with whole-number coordinates at which Q is maximised.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
AB, through (9, 0) and (8, 4), gradient −4: 4x + y ≤ 36
B1
BC: x + y ≤ 12
B1
CD, through (4, 8) and (0, 9), gradient −¼: x + 4y ≤ 36
B1
Part (b)
the objective line is parallel to AB, so a : b = 4 : 1
M1
at A: 9a = 72
M1
a = 8, b = 2
A1
Part (c)
the edges at C have gradients −1 (BC) and −¼ (CD)
M1
−1 ≤ −1⁄k ≤ −¼
M1
1 ≤ k ≤ 4
A1
Part (d)
Q = x + 4y is parallel to CD, so the maximum, 36, is attained along CD
M1
whole-number points of x + 4y = 36 with 0 ≤ x ≤ 4: (0, 9) and (4, 8)
A1
Exam tip: If the maximum is attained along a whole edge, the objective line is parallel to that edge. That fixes the ratio of the coefficients, and one vertex value then fixes their size.
A workshop hires two machines to make brackets and hinges. In one hour, machine A makes 5 brackets and 4 hinges, and machine B makes 3 brackets and 5 hinges. At least 30 brackets and at least 40 hinges are needed. Machine A is available for at most 8 hours and machine B for at most 10 hours, and each machine is hired for a whole number of hours. Machine A costs £40 per hour and machine B costs £30 per hour. The workshop hires A for x hours and B for y hours and wants to minimise the total cost. Figure 1 shows the feasible region R, with the points of R that have whole-number coordinates shown as dots.
(a)
Formulate this as a linear programming problem.
(3)
(b)
Find the exact coordinates of the vertex V where 5x + 3y = 30 meets 4x + 5y = 40, and explain why the minimum of C over R occurs at V.
(3)
(c)
Find the value of C at V.
(1)
(d)
Find the number of hours for which each machine should be hired, and the minimum cost. Justify your answer.
(4)
Show mark scheme
Answer
Mark
Notes
Part (a)
brackets: 5x + 3y ≥ 30
B1
hinges: 4x + 5y ≥ 40
B1
x ≤ 8, y ≤ 10, x, y ≥ 0; minimise C = 40x + 30y
B1
Part (b)
20x + 12y = 120 and 20x + 25y = 200 give 13y = 80
M1
V = (30⁄13, 80⁄13)
A1
the cost line has gradient −4⁄3, between −5⁄3 and −4⁄5, so moving it towards O it last touches R at V
B1
Part (c)
C = 3600⁄13 ≈ £276.92
B1
Part (d)
V ≈ (2.31, 6.15); the nearest point (2, 6) is not in R: 4(2) + 5(6) = 38 < 40
M1
(2, 7): 31 ≥ 30 and 43 ≥ 40, cost £290; (3, 6): £300; (3, 5) is not in R (37 < 40)
M1
C = 10(4x + 3y) and 4x + 3y ≥ 360⁄13 ≈ 27.7 on R, so 4x + 3y ≥ 28 for whole numbers; the whole-number points with 4x + 3y = 28 are (1, 8), (4, 4), (7, 0), none of which is in R
M1
machine A for 2 hours and machine B for 7 hours, £290
A1
Common error: Rounding both coordinates of V up to (3, 7) to be safe. It is feasible, but it costs £330, and (2, 7) costs only £290. Search the dots close to V.
A company makes x solar lamps and y torches each day. A lamp needs 3 hours of assembly and 1 hour of testing; a torch needs 2 hours of assembly and 2 hours of testing. Each day 36 hours of assembly and 20 hours of testing are available, and at most 10 lamps can be sold. The profit is £5 on a lamp and £4 on a torch, and only whole items are made. Figure 1 shows the feasible region R, together with the dashed line x + 2y = 26, which is used in parts (c) and (d).
(a)
Formulate this as a linear programming problem.
(3)
(b)
Use the vertex method to find the optimal plan and the maximum daily profit.
(2)
(c)
The testing time available is increased to 26 hours. Ignoring the need for whole numbers, find the exact coordinates of the new optimal vertex and the value of P there.
(2)
(d)
With 26 hours of testing time, find the optimal plan in whole numbers and the increase in the maximum daily profit compared with (b). Justify your answer.
(2)
(e)
The testing time is now T hours. Ignoring the need for whole numbers, show that while the optimum is where 3x + 2y = 36 meets x + 2y = T, the maximum profit is 54 + ½T, and find the value of T beyond which extra testing time gives no further increase.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
assembly: 3x + 2y ≤ 36
B1
testing: x + 2y ≤ 20
B1
x ≤ 10, x, y ≥ 0; maximise P = 5x + 4y
B1
Part (b)
P = 0, 50, 62, 64, 40 at (0, 0), (10, 0), (10, 3), (8, 6), (0, 10)
M1
8 lamps and 6 torches, £64
A1
Part (c)
gradient −5⁄4 lies between −3⁄2 and −½, so the optimum is where 3x + 2y = 36 meets x + 2y = 26: 2x = 10
£67 would need 5x + 4y = 67, i.e. (3, 13), (7, 8) or (11, 3), and none is feasible, so 6 lamps and 9 torches, £66, an increase of £2
A1
Part (e)
x = ½(36 − T), y = ¼(3T − 36), so P = 2.5(36 − T) + (3T − 36) = 54 + ½T
M1
this needs x ≥ 0, so T ≤ 36: beyond T = 36 testing time is not limiting
A1
Exam tip: After a constraint is relaxed, the new LP vertex is often not a whole-number point. Check the nearby whole-number plans against every constraint. Here the best one, (6, 9), uses all the assembly time.
We use essential cookies to make this site work. With your permission we'd also use analytics and advertising cookies to understand which resources help students most and how families find us. Nothing optional is set unless you accept. Privacy policy
EssentialNeeded for the site and your cookie choice to work.
Always on
AnalyticsAnonymous visit statistics that help improve the free resources.
MarketingMeasures whether ads reach the right families. Off unless you turn it on.