D1.5.4 The two-stage Simplex and big-M methods for maximising and…

Section
D1.5 Linear programming
Level
A level only
Statement
The two-stage Simplex and big-M methods for maximising and minimising problems which may include both ≤ and ≥ constraints.
Guidance
Problems will be restricted to those with a maximum of four variables (excluding slack, surplus and artificial variables) and four constraints, in addition to any non-negativity conditions.
Since 2018
20 parts, 76 marks · topic pages: Linear programming: formulation, graphs and the Simplex algorithm

Back to the checklist

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 · 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 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 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)
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 · 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 · 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)

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.