Revision Library

revisionlibrary.co.uk

HIGHER

IG.M3 Linear Programming

EDEXCEL 4MA1 · Calculator allowed · about 75 minutes

Total Marks

Name: _______________________________ Date: ____ / ____ / ______

Answer ALL questions. Show all your working.

A cafe orders x cakes and y pastries for the week. It must order at least 5 cakes. It must order at least twice as many pastries as cakes. The total number of items ordered must not exceed 30. Write down three inequalities that represent these conditions.

(Total for Question 1 is 3 marks)

Using the three inequalities from Question 1 (x ≥ 5, y ≥ 2x, x + y ≤ 30), show, with working, that the point (8, 20) satisfies all three inequalities.

(Total for Question 2 is 3 marks)

Using the same three inequalities (x ≥ 5, y ≥ 2x, x + y ≤ 30), explain why the point (3, 25) does NOT lie in the feasible region.

(Total for Question 3 is 2 marks)

Give an example of a point (x, y), where x and y are both positive integers, that satisfies x ≥ 5 and x + y ≤ 30, but does NOT satisfy y ≥ 2x.

(Total for Question 4 is 1 mark)

A region is bounded by a solid straight line passing through the points (0, 6) and (6, 0). The origin, (0, 0), lies inside the shaded region. Write down the inequality that defines the shaded region.

Figure (to be drawn): A coordinate grid showing a solid straight line from (0, 6) to (6, 0). The region containing the origin (below/left of the line) is shaded.

(Total for Question 5 is 2 marks)

Does the point (5, 10) satisfy the inequality 2x + y ≤ 25? Show your working.

(Total for Question 6 is 2 marks)

The vertices of a feasible region are (0, 0), (0, 5), (4, 3) and (6, 0). The objective function is P = 20x + 30y. Evaluate P at each vertex, and state the maximum value of P and the vertex at which it occurs.

Figure (to be drawn): A coordinate grid showing a shaded quadrilateral feasible region with vertices marked and labelled at (0, 0), (0, 5), (4, 3) and (6, 0).

(Total for Question 7 is 3 marks)

A small workshop makes x standard garden benches and y deluxe garden benches each day (x and y are non-negative integers). Each bench, standard or deluxe, takes 1 hour to build, and the workshop operates for at most 8 hours a day, so x + y ≤ 8. Each standard bench uses 2 units of timber and each deluxe bench uses 1 unit of timber; only 14 units of timber are available each day, so 2x + y ≤ 14. The workshop makes a profit of 50 pounds per standard bench and 40 pounds per deluxe bench. Let P = 50x + 40y be the total daily profit, in pounds.

Figure (to be drawn): A coordinate grid (x from 0 to 8, y from 0 to 10) with the lines x + y = 8 and 2x + y = 14 drawn, and the feasible region (the quadrilateral with vertices (0,0), (0,8), (6,2) and (7,0)) shaded.

(a)State the two further inequalities that must hold because x and y cannot be negative.(1)

(b)The feasible region is bounded by the lines x + y = 8 and 2x + y = 14 (as well as the axes). Find the coordinates of the point where these two lines intersect.(3)

(c)The other two vertices of the feasible region lie where each constraint line meets an axis (choosing, at each axis, whichever line is more restrictive). State the coordinates of these two vertices.(2)

(d)Evaluate P = 50x + 40y at each of the four vertices (0, 0), (0, 8), (6, 2) and (7, 0), and hence find the maximum possible daily profit and the number of each type of bench that achieves it.(4)

(e)State, in the context of the problem, what the workshop should make to maximise its daily profit, and state this maximum profit.(1)

(Total for Question 8 is 11 marks)

A farmer needs to provide her animals with at least 8 units of nutrient A and at least 10 units of nutrient B each day, by buying x bags of feed P and y bags of feed Q (x and y are non-negative integers). Each bag of feed P provides 2 units of nutrient A and 1 unit of nutrient B. Each bag of feed Q provides 1 unit of nutrient A and 2 units of nutrient B. This gives the constraints 2x + y ≥ 8 and x + 2y ≥ 10. Each bag of feed P costs 3 pounds and each bag of feed Q costs 5 pounds, so the total daily cost is C = 3x + 5y pounds, which the farmer wants to minimise.

Figure (to be drawn): A coordinate grid with the lines 2x + y = 8 and x + 2y = 10 drawn. The feasible region (satisfying both 'greater than or equal to' constraints, together with x ≥ 0 and y ≥ 0) is the unbounded region above and to the right of both lines, with corner vertices at (0, 8), (2, 4) and (10, 0).

(a)Explain, in the context of this problem, why x ≥ 0 and y ≥ 0 must also hold.(1)

(b)Find the coordinates of the point where the lines 2x + y = 8 and x + 2y = 10 intersect.(3)

(c)The feasible region (the region satisfying both 'at least' constraints) also has vertices at (0, 8) and (10, 0), where each line meets an axis. Verify that both of these points satisfy the OTHER inequality (the one not used to find them).(2)

(d)Evaluate C = 3x + 5y at each of the three vertices (0, 8), (2, 4) and (10, 0), and hence find the minimum possible daily cost and the number of bags of each feed that achieve it.(3)

(Total for Question 9 is 9 marks)

A youth club is transporting people on a trip using x minibuses and y coaches (x and y are non-negative integers). Each minibus holds 15 people and each coach holds 50 people. At least 200 people need transport, so 15x + 50y ≥ 200. Find the minimum possible total number of vehicles (x + y), and give the numbers of minibuses and coaches that achieve this minimum.

(Total for Question 10 is 4 marks)

Mark scheme · IG.M3 Linear Programming

Question 1

B1 x ≥ 5
B1 y ≥ 2x
B1 x + y ≤ 30
Answer: x ≥ 5, y ≥ 2x, x + y ≤ 30

Question 2

M1 checks x = 8 ≥ 5, true, and checks y = 20 ≥ 2(8) = 16, true
M1 checks x + y = 8 + 20 = 28 ≤ 30, true
A1 correctly concludes all three inequalities are satisfied, so (8, 20) is in the feasible region, cso
Answer: (8, 20) satisfies all three inequalities

Question 3

M1 identifies that x = 3 fails the condition x ≥ 5 (correctly checks the other two inequalities are satisfied: y = 25 ≥ 2(3) = 6 true, x + y = 28 ≤ 30 true)
A1 correct conclusion: since x = 3 < 5, the inequality x ≥ 5 is not satisfied, so (3, 25) is not in the feasible region
Answer: (3, 25) fails x ≥ 5, since 3 < 5

Question 4

B1 any valid point with x ≥ 5, x + y ≤ 30 and y < 2x, e.g. (5, 5): 5 ≥ 5 true, 5 + 5 = 10 ≤ 30 true, but 5 < 2(5) = 10, so y ≥ 2x fails; accept any other correct example, e.g. (10, 1)
Answer: e.g. (5, 5)

Question 5

M1 finds the equation of the boundary line as x + y = 6, e.g. from gradient -1 and intercept 6
A1 x + y ≤ 6 cao (correct direction, confirmed by the origin satisfying it: 0 + 0 = 0 ≤ 6)
Answer: x + y ≤ 6

Question 6

M1 substitutes x = 5, y = 10 into 2x + y, e.g. 2(5) + 10
A1 correct conclusion: 2(5) + 10 = 20, and 20 ≤ 25 is true, so yes, (5, 10) satisfies the inequality
Answer: Yes: 2(5) + 10 = 20 ≤ 25

Question 7

M1 attempts P at each of the four vertices
A1 all four values correct: P(0,0) = 0, P(0,5) = 150, P(4,3) = 170, P(6,0) = 120
A1 correct conclusion: maximum P = 170, occurring at (4, 3)
Answer: Maximum P = 170 at (4, 3)

Question 8

(a) B1 x ≥ 0 and y ≥ 0 (both stated)
(a) Answer: x ≥ 0, y ≥ 0
(b) M1 sets up the simultaneous equations and eliminates one variable correctly, e.g. subtracts x + y = 8 from 2x + y = 14 to get x = 6
(b) M1 substitutes back to find the other variable, e.g. y = 8 - 6
(b) A1 (6, 2) cao (both coordinates correct)
(b) Answer: (6, 2)
(c) B1 (0, 8): where x + y = 8 meets the y-axis (this is more restrictive there than 2x + y = 14, which would allow (0, 14))
(c) B1 (7, 0): where 2x + y = 14 meets the x-axis (this is more restrictive there than x + y = 8, which would allow (8, 0))
(c) Answer: (0, 8) and (7, 0)
(d) M1 attempts P at all four vertices
(d) A1 all four values correct: P(0,0) = 0, P(0,8) = 320, P(6,2) = 380, P(7,0) = 350
(d) A1 correctly identifies the maximum as P = 380
(d) A1 states this occurs at x = 6, y = 2 (6 standard benches and 2 deluxe benches), ft from their vertex values
(d) Answer: Maximum profit = 380 pounds, with 6 standard benches and 2 deluxe benches
(e) B1 6 standard benches and 2 deluxe benches each day, giving a maximum daily profit of 380 pounds, ft from part (d)
(e) Answer: 6 standard benches and 2 deluxe benches per day, for a maximum profit of 380 pounds

Question 9

(a) B1 the farmer cannot buy a negative number of bags of feed, oe
(a) Answer: The farmer cannot buy a negative number of bags
(b) M1 rearranges one equation, e.g. y = 8 - 2x from the first equation
(b) M1 substitutes correctly into the other equation and solves, e.g. x + 2(8 - 2x) = 10 leading to -3x = -6
(b) A1 (2, 4) cao (both coordinates correct)
(b) Answer: (2, 4)
(c) B1 (0, 8) is on the line 2x + y = 8, and checking x + 2y = 0 + 16 = 16, which is ≥ 10, so it satisfies the other constraint
(c) B1 (10, 0) is on the line x + 2y = 10, and checking 2x + y = 20 + 0 = 20, which is ≥ 8, so it satisfies the other constraint
(c) Answer: Both points satisfy the other inequality
(d) M1 attempts C at all three vertices
(d) A1 all three values correct: C(0,8) = 40, C(2,4) = 26, C(10,0) = 30
(d) A1 correctly identifies the minimum as C = 26, at x = 2, y = 4 (2 bags of feed P and 4 bags of feed Q)
(d) Answer: Minimum cost = 26 pounds, with 2 bags of feed P and 4 bags of feed Q

Question 10

M1 shows that a total of 3 vehicles is not enough, e.g. the largest possible capacity with 3 vehicles is achieved by using all coaches, 3 x 50 = 150, which is less than 200
M1 shows that a total of 4 vehicles can work, e.g. x = 0, y = 4 gives capacity 15(0) + 50(4) = 200, which meets the requirement exactly
A1 minimum total number of vehicles = 4 cao
B1 correctly states this is achieved with x = 0 minibuses and y = 4 coaches (any mix of 4 vehicles including at least one minibus gives capacity below 200, e.g. 1 minibus and 3 coaches gives 15 + 150 = 165 < 200)
Answer: Minimum 4 vehicles: 0 minibuses and 4 coaches

Linear Programming - Worksheets, Questions and Revision