D1.5.1 Formulation of problems as linear programs including the meaning…

Section
D1.5 Linear programming
Level
Partly A level only
Statement
Formulation of problems as linear programs including the meaning and use of slack, surplus and artificial variables.
Guidance
For example, 3x + 2y ≤ 20 ⇒ 3x + 2y + s₁ = 20; 2x + 5y ≤ 35 ⇒ 2x + 5y + s₂ = 35; x + y ≥ 5 ⇒ x + y − s₃ + t₁ = 5; where s₁, s₂ are slack variables, s₃ is a surplus variable and t₁ is an artificial variable.
Since 2018
26 parts, 112 marks · topic pages: Linear programming: formulation, graphs and the Simplex algorithm

Back to the checklist

June 2025 · AS Paper 2 (Decision 1) · Q4(a) 1 mark
4 y x Figure 3 George is a baker who bakes x sponge cakes and y fruit cakes every day. One of George’s constraints is shown on Figure 3. (a) Write down this constraint as a simplified inequality with integer coefficients. (1)
June 2025 · AS Paper 2 (Decision 1) · Q4(b) 5 marks
Three further constraints are • George must bake at least four fruit cakes every day • for every two sponge cakes George bakes, he must bake at most three fruit cakes • George needs 200 g of butter for each sponge cake and 100 g for each fruit cake and has 2.8 kg of butter available each day (b) (i) Write down the three inequalities which model these constraints. Give your answers in simplified form with integer coefficients. (ii) Add lines and shading to Diagram 1 in the answer book to represent these three constraints. Hence determine the feasible region and label it R. (5)
June 2025 · Paper 3D (Decision 1) · Q5(b) 3 marks
(b) Use the substitutions x X , y Y , z O 3 Z and P Q 1 10 to reformulate the linear programming problem into a form in which the Simplex algorithm can be used to solve the problem. You should write the constraints as simplified inequalities with integer coefficients. (3)
June 2025 · Paper 3D (Decision 1) · Q7(a) 7 marks
7. y 3x + 4y = 20 R x x = 1 3x + y = 8 2x + 3y = 6 Figure 5 Figure 5 shows the constraints of a linear programming problem in x and y, where R is the feasible region. The objective is to maximise P x ky , where k is a positive constant. The optimal value of P is to be found using the big-M method. (a) Set up an initial tableau for solving this linear programming problem using the big-M method. You should use exactly 2 slack variables, 2 surplus variables and 2 artificial variables. (7)
June 2024 · AS Paper 2 (Decision 1) · Q4(a) 3 marks
4. y x –5 Figure 4 Figure 4 shows three of the six constraints for a linear programming problem in x and y The unshaded region and its boundaries satisfy these three constraints. (a) State these three constraints as simplified inequalities with integer coefficients. (3)
June 2024 · AS Paper 2 (Decision 1) · Q4(b) 2 marks
The variables x and y represent the number of orange fish and the number of blue fish, respectively, that are to be kept in an aquarium. The number of fish in the aquarium is subject to these three further constraints • there must be at least one blue fish • the orange fish must not outnumber the blue fish by more than ten • there must be no more than five blue fish for every orange fish (b) Write each of these three constraints as a simplified inequality with integer coefficients. (2)
June 2024 · Paper 3D (Decision 1) · Q5(a) 6 marks
5. Two friends, Anaira and Tommi, play a game involving two positive numbers x and y Anaira gives Tommi the following clues to see if he can correctly determine the value of x and the value of y • x is greater than y and the difference between the two is at least 100 • x is at most 5 times as large as y • the sum of 2x and 3y is at least 350 • the sum of x and y is as small as possible Tommi decides to solve this problem by using the big-M method. (a) Set up an initial tableau for solving this problem using the big-M method. As part of your solution, you must show • how the constraints were made into equations using one slack variable, exactly two surplus variables and exactly two artificial variables • how the objective function was formed (6)
June 2024 · Paper 3D (Decision 1) · Q7(b) 5 marks
(b) By considering the equations represented in the above tableau, formulate the linear programming problem in x, y and z only. State the objective and list the constraints as inequalities with integer coefficients. (5)
June 2023 · AS Paper 2 (Decision 1) · Q4(a) 2 marks
4. y x = 8 3y = 4x + 5 R 4x + 15y = 120 objective line x 3x + 8y = 32 Figure 3 Figure 3 shows the constraints of a linear programming problem in x and y. The unshaded area, including its boundaries, forms the feasible region, R. An objective line has been drawn and labelled on the graph. (a) State the inequalities that define the feasible region. (2)
June 2023 · Paper 3D (Decision 1) · Q7(a) 5 marks
7. A publisher plans to produce three versions of the same book: a paperback, a hardcover, and a deluxe edition. • Each paperback takes 4 minutes to print and 1 minute to bind • Each hardcover takes 8 minutes to print and 5 minutes to bind • Each deluxe edition takes 15 minutes to print and 12 minutes to bind The printing machine is available for at most 150 hours and the binding machine must be used for at least 60 hours. The publisher decides to produce • at least 1600 books in total • at least three times as many paperbacks as hardcovers The profit on each paperback sold is £8, the profit on each hardcover sold is £20 and the profit on each deluxe edition sold is £40 Let x, y and z represent the number of paperbacks, hardcovers and deluxe editions produced. (a) Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. (5)
June 2023 · Paper 3D (Decision 1) · Q7(b) 6 marks
The publisher decides to solve this linear programming problem by using the two-stage simplex method. (b) Set up an initial tableau for solving this problem using the two-stage simplex method. As part of your solution, you must show how • the constraints have been made into equations by using slack variables, exactly two surplus variables and exactly two artificial variables • the rows for the two objective functions are formed (6)
June 2023 · Paper 3D (Decision 1) · Q7(e) 1 mark
(e) Give a reason why the publisher may not earn the profit stated in (d)(i). (1)
June 2022 · AS Paper 2 (Decision 1) · Q4(a) 3 marks
4. y 14 12 10 R Objective line x Figure 3 Figure 3 shows the constraints of a maximisation linear programming problem in x and y, where x 0 and y 0 . The unshaded area, including its boundaries, forms the feasible region, R. An objective line has been drawn and labelled on the graph. (a) List the constraints as simplified inequalities with integer coefficients. (3)
June 2022 · Paper 3D (Decision 1) · Q4(a) 4 marks
4. A linear programming problem in x, y and z is to be solved using the big‑M method. The initial tableau is shown below. b.v. x y z s1 s2 s3 a1 a2 Value s1 a1 –2 –1 a2 –4 –1 P 2 – 4M –3 + 2M –1 + 2M M M –20M (a) Using the information in the above tableau, formulate the linear programming problem. You should • list each of the constraints as an inequality • state the two possible objectives (4)
June 2022 · Paper 3D (Decision 1) · Q7(a) 5 marks
7. y y = 2x + 1 R x x + 2y = 12 7x + 2y = 46 x + y = 8 Figure 5 Figure 5 shows the constraints of a linear programming problem in x and y where R is the feasible region. The objective is to maximise P = x + ky, where k is a positive constant. The optimal vertex of R is to be found using the Simplex algorithm. (a) Set up an initial tableau for solving this linear programming problem using the Simplex algorithm. (5)
Nov 2021 · Paper 3D (Decision 1) · Q8(a) 5 marks
8. Susie is preparing for a triathlon event that is taking place next month. A triathlon involves three activities: swimming, cycling and running. Susie decides that in her training next week she should • maximise the total time spent cycling and running • train for at most 39 hours • spend at least 40% of her time swimming • spend a total of at least 28 hours of her time swimming and running Susie needs to determine how long she should spend next week training for each activity. Let • x represent the number of hours swimming • y represent the number of hours cycling • z represent the number of hours running (a) Formulate the information above as a linear programming problem. State the objective and list the constraints as simplified inequalities with integer coefficients. (5)
Nov 2021 · Paper 3D (Decision 1) · Q8(b) 6 marks
Susie decides to solve this linear programming problem by using the two-stage Simplex method. (b) Set up an initial tableau for solving this problem using the two-stage Simplex method. As part of your solution you must show how • the constraints have been made into equations using slack variables, exactly one surplus variable and exactly one artificial variable • the rows for the two objective functions are formed (6)
Oct 2020 · AS Paper 2 (Decision 1) · Q4 9 marks
4. y R objective line V x –2 Figure 3 Figure 3 shows the constraints of a linear programming problem in x and y, where R is the feasible region. Figure 3 also shows an objective line for the problem and the optimal vertex, which is labelled as V. The value of the objective at V is 556 Express the linear programming problem in algebraic form. List the constraints as simplified inequalities with integer coefficients and determine the objective. (9)
Oct 2020 · Paper 3D (Decision 1) · Q7(a) 4 marks
7. A maximisation linear programming problem in x, y and z is to be solved using the two-stage simplex method. The partially completed initial tableau is shown below. Basic x y z s1 s2 s3 a1 a2 Value variable s1 a1 –1 a2 –1 –1 P –2 –1 –3 A (a) Using the information in the above tableau, formulate the linear programming problem. State the objective and list the constraints as inequalities. (4)
June 2019 · AS Paper 2 (Decision 1) · Q5(a) 7 marks
5. Ben is a wedding planner. He needs to order flowers for the weddings that are taking place next month. The three types of flower he needs to order are roses, hydrangeas and peonies. Based on his experience, Ben forms the following constraints on the number of each type of flower he will need to order. Ɣ At least three-fifths of all the flowers must be roses. Ɣ For every 2 hydrangeas there must be at most 3 peonies. Ɣ The total number of flowers must be exactly 1000 The cost of each rose is £1, the cost of each hydrangea is £5 and the cost of each peony is £4 Ben wants to minimise the cost of the flowers. Let x represent the number of roses, let y represent the number of hydrangeas and let z represent the number of peonies that he will order. (a) Formulate this as a linear programming problem in x and y only, stating the objective function and listing the constraints as simplified inequalities with integer coefficients. (7)
June 2019 · AS Paper 2 (Decision 1) · Q5(b) 3 marks
Ben decides to order the minimum number of roses that satisfy his constraints. (b) (i) Calculate the number of each type of flower that he will order to minimise the cost of the flowers. (ii) Calculate the corresponding total cost of this order. (3)
June 2019 · Paper 3D (Decision 1) · Q6(b) 7 marks
(b) Set up the initial tableau for solving this linear programming problem using the big-M method. (7)
June 2019 · Paper 3D (Decision 1) · Q7(a) 2 marks
7. A shop sells two types of watch, analogue watches and digital watches. The shop manager knows that, each month, she should order at least 60 watches in total. In addition, at most 80% of the watches she orders must be digital. Let x be the number of analogue watches ordered and let y be the number of digital watches ordered. (a) Write down inequalities, in terms of x and y, to model these constraints. (2)
June 2018 · AS Paper 2 (Decision 1) · Q4(a) 1 mark
4. The manager of a factory is planning the production schedule for the next three weeks for a range of cabinets. The following constraints apply to the production schedule. ¢ The total number of cabinets produced in week 3 cannot be fewer than the total number produced in weeks | and 2 ¢ At most twice as many cabinets must be produced in week 3 as in week 2 ¢ The number of cabinets produced in weeks 2 and 3 must, in total, be at most 125 The production cost for each cabinet produced in weeks 1, 2 and 3 is £250, £275 and £200 respectively. The factory manager decides to formulate a linear programming problem to find a production schedule that minimises the total cost of production. The objective is to minimise 250x + 275y + 200z (a) Explain what the variables x, y and z represent. (1)
June 2018 · AS Paper 2 (Decision 1) · Q4(b) 2 marks
(b) Write down the constraints of the linear programming problem in terms of x, y and z. (2)
June 2018 · AS Paper 2 (Decision 1) · Q4(c) 8 marks
Due to demand, exactly 150 cabinets must be produced during these three weeks. This reduces the constraints to x+y <75 x + 3y > 150 x > 25 y20 which are shown in Diagram| in the answer book. Given that the manager does not want any cabinets left unfinished at the end of a week, (c) (i) use a graphical approach to solve the linear programming problem and hence determine the production schedule which minimises the cost of production. You should make your method and working clear. (ii) Find the minimum total cost of the production schedule. (8)

Find an Edexcel Further Maths tutor

Stuck on this? Book a trial lesson with our Further Maths tutor.

Prefer email? Send an enquiry

If you are under 18, please include a parent's contact details. Enquiries go to enquiries@alevelfurthermathstutor.com and are deleted once handled.