Linear programming: formulation, graphs and the Simplex algorithm Decision 1

Papers
A level Paper 3D; AS Paper 2 (option 27)
Level
AS and A level
Spec
D1.5.1, D1.5.2, D1.5.3, D1.5.4
Booklet
Nothing is given.
Since 2018
63 question parts, 225 marks

Notes, worked examples and practice for this topic are being written by our tutors. The past-paper questions below are ready now: work each one on paper, then open the mark scheme and the examiner's comment.

Past-paper questions

Print this topic as a pack questions first, then the mark schemes

Tap a question to zoom it. Mark scheme and examiner's comment open under each question.
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 · AS Paper 2 (Decision 1) · Q4(c) 5 marks
George makes £8 profit from each sponge cake he sells and £5 profit from each fruit cake he sells. Given that he wishes to maximise his profit, (c) use the vertex method to determine the number of sponge cakes and the number of fruit cakes George should bake each day. You must make your method and working clear. (5)
June 2025 · Paper 3D (Decision 1) · Q5(a) 1 mark
5. Consider the following linear programming problem in x, y and z. Maximise P x y z subject to 2 x + y + z x - y - z z x y x y z (a) Explain why the Simplex algorithm cannot be used to solve this linear programming problem in its current form. (1)
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) · Q5(c) 1 mark
After a second iteration of the Simplex algorithm, a possible tableau T is s1 s2 s3 b.v. X Y Z Value -3 -1 X s2 -1 Y -5 Q (c) Write down the profit equation given by T. (1)
June 2025 · Paper 3D (Decision 1) · Q5(d) 1 mark
(d) Using your answer to (c), explain why T is not optimal. (1)
June 2025 · Paper 3D (Decision 1) · Q5(e) 6 marks
(e) (i) Perform the third iteration of the Simplex algorithm. You should state the row operations you use. (ii) Hence determine the maximum value of P, and the corresponding values of x, y and z. (6)
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 2025 · Paper 3D (Decision 1) · Q7(b) 5 marks
After a third iteration of the big-M method, a possible tableau is s1 s2 s3 s4 a1 a2 x y b.v. Value s1 - - x - y - - s2 -1 - P k k M M k k 7 - 7 - - + 7 + (b) Given that the third iteration gives the optimal value for P, determine this value. (5)
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 · AS Paper 2 (Decision 1) · Q4(c) 3 marks
P75677A (c) Represent these three constraints by adding lines and shading to Diagram 1 in the answer book, labelling the feasible region, R (3)
June 2024 · AS Paper 2 (Decision 1) · Q4(d) 4 marks
The total value (in pounds) of the fish in the aquarium is given by the objective function Maximise P = 3x + 5y (d) (i) Use the objective line method to determine the optimal point of the feasible region, giving its coordinates as exact fractions. (ii) Hence find the maximum total value of the fish in the aquarium, stating the optimal number of orange fish and the optimal number of blue fish. (4)
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) · Q5(b) 3 marks
The big-M method is applied until the tableau containing the optimal solution to the problem is found. One row of this final tableau is as follows. b.v. x y s1 s2 s3 a1 a2 Value x -3 -1 (b) (i) State the value of x (ii) Hence deduce the value of y, making your reasoning clear. (3)
June 2024 · Paper 3D (Decision 1) · Q7(a) 2 marks
7. A maximisation linear programming problem in x, y and z is to be solved using the Simplex method. The tableau after the 1st iteration is shown below. b.v. x y z s1 s2 s3 Value s1 -1 -1 x -1 s3 P -1 -11 (a) State the column that contains the pivot value for the 1st iteration. You must give a reason for your answer. (2)
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 2024 · Paper 3D (Decision 1) · Q7(c) 4 marks
(c) Taking the most negative number in the profit row to indicate the pivot column, perform the 2nd iteration of the Simplex algorithm, to obtain a new tableau, T. Make your method clear by stating the row operations you use. (4)
June 2024 · Paper 3D (Decision 1) · Q7(d) 2 marks
(d) (i) Explain, using T, how you know that an optimal solution to the original linear programming problem has not been found after the 2nd iteration. (ii) State the values of the basic variables after the 2nd iteration. (2)
June 2024 · Paper 3D (Decision 1) · Q7(e) 1 mark
A student attempts the 3rd iteration of the Simplex algorithm and obtains the tableau below. b.v. x y z s1 s2 s3 Value -1 z -1 x -1 y P (e) Explain how you know that the student’s attempt at the 3rd iteration is not correct. (1)
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 · AS Paper 2 (Decision 1) · Q4(b) 5 marks
The maximum value of the objective function is 160 The minimum value of the objective function is 883 (b) Determine the objective function, showing your working clearly. (5)
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(c) 5 marks
The following tableau is obtained after two iterations of the first stage of the two-stage simplex method. b.v. x y z s1 s2 s3 s4 a1 a2 Value s1 –1 –3 -1 -1 2000 z -12 -1 15600 x -1 -12 15600 s4 -4 -32 -56 204800 P I (c) Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the second stage of the two-stage simplex method to obtain a new tableau. Make your method clear by stating the row operations you use. (5)
June 2023 · Paper 3D (Decision 1) · Q7(d) 2 marks
After three iterations of the second stage of the two-stage simplex method, the following tableau is obtained. b.v. x y z s1 s2 s3 s4 Value s2 -1 z -3 -9 -7 x 1125 -1 -3 y P 20500 Given that the publisher produces the optimal number of each version of the book, (d) (i) state the maximum profit the publisher can earn, (ii) find the number of hours the binding machine will be used. (2)
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 · AS Paper 2 (Decision 1) · Q4(b) 5 marks
The optimal value of the objective function is 216 (b) (i) Calculate the exact coordinates of the optimal vertex. (ii) Hence derive the objective function. (5)
June 2022 · AS Paper 2 (Decision 1) · Q4(c) 1 mark
Given that x represents the number of small flower pots and y represents the number of large flower pots supplied to a customer, (c) deduce the optimal solution to the problem. (1)
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) · Q4(b) 2 marks
(b) Obtain the most efficient pivot for a first iteration of the big‑M method. You must give reasons for your answer. (2)
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)
June 2022 · Paper 3D (Decision 1) · Q7(b) 1 mark
After two iterations of the Simplex algorithm a possible tableau T is b.v. x y s1 s2 s3 s4 Value -3 s1 -2 x -11 s3 y + k 5 k P - + 5k + 2 (b) State the value of each variable after the second iteration. (1)
June 2022 · Paper 3D (Decision 1) · Q7(c) 9 marks
It is given that T does not give an optimal solution to the linear programming problem. After a third iteration of the Simplex algorithm the resulting tableau does give an optimal solution to the problem. (c) Perform the third iteration of the Simplex algorithm and hence determine the range of possible values for P. You should state the row operations you use and make your method and working clear. (9)
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)
Nov 2021 · Paper 3D (Decision 1) · Q8(c) 2 marks
The following tableau T is obtained after one iteration of the second stage of the two‑stage Simplex method. b.v. x y z s1 s2 s3 Value y s2 -2 -5 x -1 P -1 (c) Obtain a suitable pivot for a second iteration. You must give reasons for your answer. (2)
Nov 2021 · Paper 3D (Decision 1) · Q8(d) 5 marks
(d) Starting from tableau T, solve the linear programming problem by performing one further iteration of the second stage of the two-stage Simplex method. You should make your method clear by stating the row operations you use. (5)
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) · Q4(a) 2 marks
4. y 2y = 5x 7 – y = x + 1 6 – 5 – 4 – R 3 – 2 – 1 – – – – – – – – x 6x + 5y = 30 Figure 3 Figure 3 shows the constraints of a linear programming problem in x and y, where R is the feasible region. (a) Write down the inequalities that define R. (2)
Oct 2020 · Paper 3D (Decision 1) · Q4(b) 4 marks
The objective is to maximise P, where P = 3x + y (b) Obtain the exact value of P at each of the three vertices of R and hence find the optimal vertex, V. (4)
Oct 2020 · Paper 3D (Decision 1) · Q4(c) 4 marks
The objective is changed to maximise Q, where Q = 3x + ay. Given that a is a constant and the optimal vertex is still V, (c) find the range of possible values of a. (4)
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)
Oct 2020 · Paper 3D (Decision 1) · Q7(b) 2 marks
(b) Complete the bottom row of Table 1 in the answer book. You should make your method and working clear. (2)
Oct 2020 · Paper 3D (Decision 1) · Q7(c) 3 marks
The following tableau is obtained after two iterations of the first stage of the two-stage simplex method. Basic x y z s1 s2 s3 a1 a2 Value variable -7 -3 s1 -1 x -1 -1 z -11 -3 P A (c) (i) Explain how the above tableau shows that a basic feasible solution has been found for the original linear programming problem. (ii) Write down the basic feasible solution for the second stage. (3)
Oct 2020 · Paper 3D (Decision 1) · Q7(d) 5 marks
(d) Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the second stage of the two-stage simplex method, to obtain a new tableau, T. Make your method clear by stating the row operations you use. (5)
Oct 2020 · Paper 3D (Decision 1) · Q7(e) 3 marks
(e) (i) Explain, using T, whether or not an optimal solution to the original linear programming problem has been found. (ii) Write down the value of the objective function. (iii) State the values of the basic variables. (3)
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(a) 1 mark
6. A linear programming problem in x, y and z is described as follows. Maximise P = 2x + 2y í z 3x + y + 2z - 30 subject to x í y + z . 8 4y + 2z . 15 x, y, z . 0 (a) Explain why the Simplex algorithm cannot be used to solve this linear programming problem. (1)
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) · Q6(c) 1 mark
After a first iteration of the big-M method, the tableau is b.v. x y z s1 s2 s3 a1 a2 Value s1 1.5 0.25 í0.25 26.25 a1 1.5 í1 í0.25 0.25 11.75 y 0.5 í0.25 0.25 3.75 P í(2 + M) 2 í 1.5M M í0.5 + 0.25M 0.5 + 0.75M 7.5 í 11.75M (c) State the value of each variable after the first iteration. (1)
June 2019 · Paper 3D (Decision 1) · Q6(d) 1 mark
(d) Explain why the solution given by the first iteration is not feasible. (1)
June 2019 · Paper 3D (Decision 1) · Q6(e) 2 marks
Taking the most negative entry in the profit row to indicate the pivot column, (e) obtain the most efficient pivot for a second iteration. You must give reasons for your answer. (2)
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 2019 · Paper 3D (Decision 1) · Q7(b) 4 marks
Two further constraints are y + 3x . 140 4y + x . 80 (b) Represent all these constraints on Diagram 1 in the answer book. Hence determine, and label, the feasible region, R. (4)
June 2019 · Paper 3D (Decision 1) · Q7(c) 3 marks
The cost to the shop of ordering an analogue watch is five times the cost of ordering a digital watch. The shop manager wishes to minimise the total cost. (c) Determine the number of each type of watch the shop manager should order. You must make your method clear. (3)
June 2019 · Paper 3D (Decision 1) · Q7(d) 3 marks
Given that the minimum total cost of ordering the watches is £4455 (d) determine the cost of ordering one analogue watch and the cost of ordering one digital watch. You must make your method clear. (3)
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.