Practise › Questions › The Simplex algorithm
The Simplex algorithm questions
Graphs run out at two variables. Simplex walks from corner to corner algebraically instead, improving at every step, and stops when no move can improve the objective any further.
7 original questions · 31 marks · the the simplex algorithm notes · Decision Mathematics 1
Every question here is written for this library rather than taken from a past paper. Write your answer out before opening the worked one: the answers award marks point by point, and the marks are easier to see when you have something of your own to compare against.
State the stopping condition for the Simplex algorithm, and why it is the right one.
Worked answer
Stop when no negative entries remain in the objective row. A negative entry means increasing that variable would still improve the objective, so while one remains the solution can be bettered. Once none remain, no variable can be increased without reducing the objective, and the current vertex is optimal. B1 for the stopping condition, B1 for the reason.Set up the initial tableau for maximising P = 4x + 5y subject to x + y ≤ 10 and 2x + 3y ≤ 24.
Worked answer
Add slack variables: x + y + s1 = 10 and 2x + 3y + s2 = 24, with the objective as P − 4x − 5y = 0. The tableau rows are P: 1, −4, −5, 0, 0 | 0; s1: 0, 1, 1, 1, 0 | 10; s2: 0, 2, 3, 0, 1 | 24. B1 for the slack variables, B1 for the objective row, B1 B1 for the two constraint rows.Carry out the first iteration, naming the pivot column, the pivot row and the row operations.
Worked answer
The most negative entry in the objective row is −5, so the pivot column is y. The ratio test gives 10 ÷ 1 = 10 and 24 ÷ 3 = 8, so the pivot row is the s2 row and the pivot element is 3.
Divide that row by 3 to give the new y row 0, 2/3, 1, 0, 1/3 | 8. Subtract it from the s1 row for 0, 1/3, 0, 1, −1/3 | 2, and add five times it to the objective row for 1, −2/3, 0, 0, 5/3 | 40.
So P = 40 with y = 8, x = 0 and s1 = 2. B1 for the pivot column, M1 for the ratio test, A1 for the pivot row, M1 for the row operations, A1 for the new y row, A1 for the objective row. The objective row still has −2/3 in the x column, so a second iteration is needed. Name the row operations as R − R(y) and R + 5R(y) beside the tableau, since a mark goes on them.A final tableau has objective row P + 2s1 + s2 = 44, with rows giving x = 6 and y = 4. State the solution and justify that it is optimal.
Worked answer
No entry in the objective row is negative, so no variable can be increased to improve P: the tableau is optimal. The basic variables are x = 6 and y = 4, the non-basic slacks are s1 = s2 = 0, and P = 44. B1 for the optimality statement, B1 for x = 6, B1 for y = 4, B1 for P = 44. Both slacks being zero means both constraints are tight, matching the graphical answer.In a tableau the pivot column entries are 2, −1 and 4, with values 12, 8 and 20. Identify the pivot row and explain the entry you ignored.
Worked answer
Ratios: 12 ÷ 2 = 6 and 20 ÷ 4 = 5. The −1 is skipped entirely: increasing the entering variable would make that row's value grow rather than shrink, so it places no limit. The smallest ratio is 5, so the third row is the pivot row. M1 for the ratio test, A1 for the third row, B1 for ignoring the negative entry.Continue from the tableau after the first iteration, with objective row 1, −2/3, 0, 0, 5/3 | 40, s1 row 0, 1/3, 0, 1, −1/3 | 2 and y row 0, 2/3, 1, 0, 1/3 | 8. Carry out the second iteration and state the solution.
Worked answer
The only negative entry left is −2/3, so the pivot column is x. The ratio test gives 2 ÷ 1/3 = 6 and 8 ÷ 2/3 = 12, so the pivot row is the s1 row and the pivot element is 1/3.
Multiply that row by 3 to give the new x row 0, 1, 0, 3, −1 | 6. Subtract two thirds of it from the y row for 0, 0, 1, −2, 1 | 4, and add two thirds of it to the objective row for 1, 0, 0, 2, 1 | 44.
No negative entries remain, so the tableau is optimal: x = 6, y = 4, s1 = s2 = 0 and P = 44.
B1 for the pivot column, M1 for the ratio test, A1 for the pivot row, M1 for the row operations, A1 for the new x row, A1 for the other two rows, A1 for the solution.
Negative entries away from the objective row are perfectly normal and are ignored by the ratio test. Only the pivot column entries matter there, and only the positive ones.Explain why a problem with a ≥ constraint cannot be started in the ordinary way, and describe the two methods that fix it.
Worked answer
With only ≤ constraints and non-negative right-hand sides, the origin is feasible and the slack variables form a valid starting solution. A ≥ constraint with a positive right-hand side makes the origin infeasible, and subtracting a surplus variable does not replace what the slacks provided: setting the real variables to zero would need a negative surplus, so there is no obvious starting basis to read off. An artificial variable is added to each such row to supply one, and must then be driven out. The two-stage method first minimises the sum of the artificial variables, driving them to zero and so reaching a feasible corner, then runs ordinary Simplex from there. The big-M method instead subtracts a large multiple M of each artificial variable from the objective, making them so expensive that the algorithm eliminates them on its own. B1 B1 for why the ordinary start fails, B1 for the two-stage method, B1 for the big-M method, B1 for how the artificial variables are driven out.
The same practice on paper: the printable workbook for this topic, questions and a worked answer book.
Practise the simplex algorithm one question at a time
The player marks nothing for you. It shows one question, waits, then shows the worked answer so you can mark yourself, and brings a question back sooner when it went badly.