Robinson Tuition
AS Decision Mathematics 1 · Edexcel 8FM0 · free Further Maths worksheet

Linear programming

Formulating a problem with decision variables, an objective function and constraints, drawing the feasible region, the objective line and vertex methods, integer solutions, maximising and minimising.

12 original questions, 77 marks. Type your answers below for an instant mark and a score (algebra in any equivalent form, e.g. 2sqrt(3) or 2√3), or print the worksheet, mark it with the answers sheet, and use the solutions to see every step written out by hand.

Worksheet PDFWorked solutions PDFAnswers PDF

The questions

1

The diagram shows the feasible region, R, of a linear programming problem in x and y.

Write down the inequalities that define R.

0123456789101101234567891011xyRy = 1x + y = 10y = 2xx = 7
3 marks
Show answer
y ≥ 1, x + y ≤ 10, y ≤ 2x, x ≤ 7
2

A bakery in Cardiff makes x loaves of bread and y cakes each day.

  • Each loaf uses 500 g of flour and each cake uses 200 g of flour. There is 20 kg of flour available.
  • Each loaf needs 30 minutes of oven time and each cake needs 20 minutes. The oven is available for 15 hours.
  • At least 10 cakes must be made.
  • The number of loaves must be at least half the number of cakes.

Write down four inequalities, other than x ≥ 0, to model these constraints. Simplify each inequality so that it has integer coefficients that are as small as possible.

4 marks
Show answer
5x + 2y ≤ 200, 3x + 2y ≤ 90, y ≥ 10, 2x ≥ y
3

The diagram shows the feasible region, R, for a linear programming problem. R is defined by x + 2y ≤ 16, 3x + y ≤ 18, y ≥ 2 and x ≥ 0

The objective is to maximise P = 2x + 3y

  1. Find the exact coordinates of each vertex of R.
  2. Use the vertex method to find the optimal vertex and the maximum value of P.
0123456789012345678910xyRx + 2y = 163x + y = 18y = 2
5 marks
Show answer
a) (0, 2), (163, 2), (4, 6), (0, 8) b) P = 26 at (4, 6)
4

A linear programming problem has the constraints

2x + y ≤ 12,   x + 3y ≤ 15,   x − y ≤ 3,   x ≥ 0,   y ≥ 0

  1. On the grid, draw lines to represent the constraints. Label the feasible region R.
  2. Find the exact coordinates of every vertex of R.
012345678910012345678910111213xy
7 marks
Show answer
a) Lines drawn and R labelled (region below 2x + y = 12 and x + 3y = 15, above x - y = 3, in the first quadrant) b) (0, 0), (3, 0), (5, 2), (215, 185), (0, 5)
5

A garden centre in Kent makes hanging baskets and window boxes to sell in spring.

  • A hanging basket uses 3 litres of compost and a window box uses 5 litres. There are 150 litres of compost available.
  • A hanging basket takes 20 minutes to plant and a window box takes 10 minutes. There are 8 hours of planting time available.
  • At least 5 window boxes must be made.
  • The number of hanging baskets must be no more than three times the number of window boxes.

The profit is £6 on each hanging basket and £4 on each window box. The garden centre wants to maximise its profit.

Formulate this as a linear programming problem. You should define your decision variables, state the objective and list the constraints as simplified inequalities.

5 marks
Show answer
Let x = number of hanging baskets, y = number of window boxes. Maximise P = 6x + 4y subject to 3x + 5y ≤ 150, 2x + y ≤ 48, y ≥ 5, x ≤ 3y, x ≥ 0
6

The diagram shows the feasible region, R, of a linear programming problem, defined by x + y ≥ 8, 3x + y ≥ 12, x + 3y ≥ 12, x ≥ 0 and y ≥ 0. R is unbounded.

The objective is to minimise C = 4x + 5y

  1. Draw an objective line on the diagram and use it to identify the optimal vertex.
  2. Find the coordinates of the optimal vertex and the minimum value of C.
  3. Explain why the problem would have no solution if the objective were to maximise C.
0123456789101112131401234567891011121314xyRx + y = 83x + y = 12x + 3y = 12
6 marks
Show answer
a) Objective line 4x + 5y = 20 (gradient -4/5), slid parallel away from O: the first point of R it reaches is the vertex where x + y = 8 meets x + 3y = 12 b) (6, 2); C = 34 c) R is unbounded, so x and y can be as large as we like and C has no maximum.
7

A secondary school in Leeds is buying x laptops and y tablets.

  • At least 40 devices must be bought in total.
  • At most 70% of the devices may be tablets.
  • At least a quarter of the devices must be laptops.
  • A laptop costs £400 and a tablet costs £250. The budget is £18 000

Write down inequalities to model these constraints. Each must be simplified so that it has integer coefficients as small as possible.

5 marks
Show answer
x + y ≥ 40, 3y ≤ 7x, 3x ≥ y, 8x + 5y ≤ 360
8

A craft business makes x wooden toys and y jigsaws each week. The constraints are 3x + 2y ≤ 21, x + 3y ≤ 15, x ≥ 0 and y ≥ 0, and the feasible region R is shown. The profit, in pounds, is P = 5x + 4y, to be maximised.

  1. Find the exact coordinates of the vertex V and the value of P at V.
  2. Show that V gives the maximum value of P over R.
  3. Given that x and y must be integers, find the optimal number of toys and jigsaws and the maximum weekly profit.
012345678012345678xyR3x + 2y = 21x + 3y = 15V
7 marks
Show answer
a) (337, 247); P = 2617 b) P(0, 0) = 0, P(7, 0) = 35, P(0, 5) = 20, all less than 261/7 = 37.3 c) x = 5, y = 3; £37
9

The feasible region R is defined by x + y ≤ 10, 2x + y ≤ 16, x + 3y ≤ 24, x ≥ 0 and y ≥ 0, as shown.

  1. Find the value of P = 3x + 2y at each vertex of R, and hence state the optimal vertex when P is maximised.

The objective is changed to maximise Q = x + ky, where k is a positive constant. The vertex V(6, 4) is still optimal.

  1. Find the range of possible values of k
01234567890123456789xyRx + y = 102x + y = 16x + 3y = 24V(6, 4)
7 marks
Show answer
a) (0, 0): 0, (8, 0): 24, (6, 4): 26, (3, 7): 23, (0, 8): 16; optimal vertex (6, 4) b) 12 ≤ k ≤ 1
10

A furniture workshop in High Wycombe makes chairs and tables.

  • A chair uses 2 m of timber and a table uses 5 m. There are 60 m of timber available each week.
  • A chair takes 2 hours to make and a table takes 3 hours. There are 48 hours of labour available each week.
  • At least 4 tables must be made each week.
  • The number of chairs must be no more than three times the number of tables.

The profit is £30 on a chair and £55 on a table. Let x be the number of chairs and y the number of tables made each week.

  1. Formulate the problem as a linear programming problem.
  2. On the grid, draw the constraints and label the feasible region R.
  3. Use the vertex method to find the number of chairs and tables that maximises the profit, and the maximum profit.
01234567891011121314151617181920212201234567891011121314xy
10 marks
Show answer
a) Maximise P = 30x + 55y subject to 2x + 5y ≤ 60, 2x + 3y ≤ 48, y ≥ 4, x ≤ 3y, x ≥ 0 b) R drawn: vertices (0, 4), (12, 4), (16, 163), (15, 6), (0, 12) c) 15 chairs, 6 tables; £780
11

A farmer in Lincolnshire mixes two feeds, A and B, for her sheep. She uses x kg of feed A and y kg of feed B each day. The mix must provide enough protein, fibre and minerals, which gives the constraints

2x + y ≥ 16,   x + y ≥ 11,   x + 3y ≥ 18,   x ≥ 0,   y ≥ 0

The feasible region R is shown. Feed A costs £3 per kg and feed B costs £2 per kg.

  1. Find the exact coordinates of the vertices of R.
  2. Find the amounts of each feed that minimise the daily cost, and the minimum cost.
  3. The price of feed A rises to £5 per kg. Find the new minimum cost and the amounts of each feed.
012345678910111213141516171819200123456789101112131415161718xyR2x + y = 16x + y = 11x + 3y = 18
8 marks
Show answer
a) (0, 16), (5, 6), (152, 72), (18, 0) b) 5 kg of A, 6 kg of B; £27 c) 0 kg of A, 16 kg of B; £32
12

A sixth-form college in Bath is taking 300 students to a careers fair. It can hire minibuses, which seat 16 students and cost £120 each, and coaches, which seat 50 students and cost £400 each.

  • There must be enough seats for all 300 students.
  • Only 12 drivers are available, one for each vehicle.
  • The college insists on at least as many minibuses as coaches.

Let x be the number of minibuses and y the number of coaches.

  1. Formulate the problem as a linear programming problem, simplifying your constraints.
  2. On the grid, draw the constraints and label the feasible region R.
  3. Find the vertices of R and the cost at each.
  4. Find the number of minibuses and coaches that the college should hire, and the minimum cost.
01234567891011121314012345678xy
10 marks
Show answer
a) Minimise C = 120x + 400y subject to 8x + 25y ≥ 150, x + y ≤ 12, x ≥ y, y ≥ 0 b) R drawn: the triangle above 8x + 25y = 150, below x + y = 12 and below y = x c) (5011, 5011): £2363.64; (15017, 5417): £2329.41; (6, 6): £3120 d) 7 minibuses, 4 coaches; £2440

Your score

Answer the questions above and your score appears here.

Every question here is original and written by Robinson Tuition. It follows the Edexcel AS Further Mathematics specification and suits AQA and OCR Further Maths too; this is not an exam-board paper.

All AS Decision Mathematics 1 topics