D1.5.3 The Simplex algorithm and tableau for maximising and minimising…

Section
D1.5 Linear programming
Level
A level only
Statement
The Simplex algorithm and tableau for maximising and minimising problems with ≤ constraints.
Guidance
Problems will be restricted to those with a maximum of four variables (excluding slack variables) and four constraints, in addition to non-negativity conditions.
Since 2018
27 parts, 93 marks · topic pages: Linear programming: formulation, graphs and the Simplex algorithm, Game theory, Transportation problems

Back to the checklist

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 4D (Decision 2) · Q6(c) 4 marks
A third option, Z, is added to player A’s options. Option Z has the pay-offs shown in the matrix below. Player B Option P Option Q Option R Option X –2 –5 Player A Option Y –1 Option Z –1 Player A now intends to make a random choice between options X, Y and Z, choosing option X with probability x, option Y with probability y and option Z with probability z Player A decides to use the Simplex algorithm to find the optimal values of x, y and z (c) Determine an initial Simplex tableau to solve this 3 x 3 game, making your variables clear. (4)
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 2024 · Paper 4D (Decision 2) · Q7(b) 5 marks
Player A intends to make a random choice between options R, S and T, choosing option R with probability p1, option S with probability p2 and option T with probability p3 Player A wants to find the optimal values of p1, p2 and p3 using the Simplex algorithm. Player A formulates the following objective function for the corresponding linear programme. Maximise P = V where V = the value of the game + 3 (b) Determine an initial Simplex tableau, making your variables and working clear. (5)
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 4D (Decision 2) · Q8(c) 7 marks
Player A intends to make a random choice between options Q, R and S, choosing option Q with probability p1, option R with probability p2 and option S with probability p3 Player A wants to calculate the optimal values of p1, p2 and p3 using the Simplex algorithm. (c) (i) Formulate the game as a linear programming problem for player A. You should write the constraints as equations. (ii) Write down an initial Simplex tableau for this linear programming problem, making your variables clear. (7)
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)
June 2022 · Paper 4D (Decision 2) · Q7(d) 7 marks
Player A intends to make a random choice between options Q, R and S, choosing option Q with probability p1, option R with probability p2 and option S with probability p3 Player A wants to find the optimal values of p1, p2 and p3 using the Simplex algorithm. Given that k > –4, player A formulates the following objective function for the corresponding linear program. Maximise P = V, where V = the value of the original game + 4 (d) (i) Formulate the constraints of the linear programming problem for player A. You should write the constraints as equations. (ii) Write down an initial Simplex tableau, making your variables clear. (7)
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(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)
Oct 2020 · Paper 4D (Decision 2) · Q3(e) 1 mark
(e) Explain why the Simplex algorithm cannot be used to solve transportation linear programming problems such as that formulated in (d). (1)
Oct 2020 · Paper 4D (Decision 2) · Q6(d) 1 mark
(d) Explain why it is necessary to use the constraint p1 + p2 + p3 1 (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 4D (Decision 2) · Q4(c) 3 marks
(c) Write down an initial Simplex tableau for the corrected linear programming problem. (3)

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.