Questions on the Simplex algorithm

Question 1

State the stopping condition for the Simplex algorithm, and why it is the right one.

Accepted 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.

Question 2

The Simplex tableau maximises an objective. State how it is used to minimise one instead, and state what has to be done to the final value.

Accepted Answer

Maximise the negative of the objective: to minimise C, set P = −C, write the tableau for P and run the algorithm unchanged. B1.
The tableau then reports the greatest value of −C, so the minimum of C is the negative of the value standing in the corner. B1.
The values of the variables themselves need no adjustment: the point that maximises −C is the point that minimises C, and only the sign of the objective has been changed.

Question 3

Set up the initial Simplex tableau for maximising P = 3x + 5y + 4z subject to 2x + 3y + z ≤ 18 and x + y + 2z ≤ 12.

Accepted Answer

Add a slack variable to each constraint: 2x + 3y + z + s₁ = 18 and x + y + 2z + s₂ = 12, with s₁ ≥ 0 and s₂ ≥ 0. B1.
Write the objective with its signs reversed: P − 3x − 5y − 4z = 0. B1.
With columns P, x, y, z, s₁, s₂ and the value, the tableau reads
P: 1, −3, −5, −4, 0, 0 | 0
s₁: 0, 2, 3, 1, 1, 0 | 18
s₂: 0, 1, 1, 2, 0, 1 | 12
B1 for the two constraint rows.
Each slack variable has a column of its own, carrying a 1 in its own row and zeros elsewhere, which is what makes the slacks the starting basic variables. The solution the initial tableau describes is x = y = z = 0 with P = 0, the origin, which is feasible here because both constraints are ≤ with non-negative right-hand sides.

Question 4

Set up the initial tableau for maximising P = 4x + 5y subject to x + y ≤ 10 and 2x + 3y ≤ 24.

Accepted Answer

Add slack variables: x + y + s₁ = 10 and 2x + 3y + s₂ = 24, with the objective as P − 4x − 5y = 0. The tableau rows are P: 1, −4, −5, 0, 0 | 0; s₁: 0, 1, 1, 1, 0 | 10; s₂: 0, 2, 3, 0, 1 | 24. B1 for the slack variables, B1 for the objective row, B1 B1 for the two constraint rows.

Question 5

Carry out the first iteration, naming the pivot column, the pivot row and the row operations.

Accepted Answer

The most negative entry in the objective row is −5, so the pivot column is y. B1.
Ratio test on the y column: 18 ÷ 3 = 6 and 12 ÷ 1 = 12. M1. The smaller is 6, so the pivot row is the s₁ row and the pivot element is 3. A1.
Divide the pivot row by 3 for the new y row 0, 2/3, 1, 1/3, 1/3, 0 | 6. Subtract it once from the s₂ row for 0, 1/3, 0, 5/3, −1/3, 1 | 6. Add five times it to the objective row for 1, 1/3, 0, −7/3, 5/3, 0 | 30. M1 for the row operations, A1 for the three new rows.
So P = 30 with y = 6, x = 0, z = 0 and s₂ = 6. The objective row still holds −7/3 in the z column, so a further iteration is needed. B1 for that decision, with the negative entry as its reason.
Write each row operation beside the row it produced, in the form 'row 2 minus row 1', so that the tableau can be followed. Keep the entries as exact fractions: the decimals here recur, and rounding them corrupts the next ratio test.

Question 6

A final tableau has objective row P + 2s₁ + s₂ = 44, with rows giving x = 6 and y = 4. State the solution and justify that it is optimal.

Accepted 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 s₁ = s₂ = 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.

Question 7

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.

Accepted 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.

Question 8

Carry out the first iteration of the Simplex algorithm on the tableau with objective row 1, −3, −5, −4, 0, 0 | 0; s₁ row 0, 2, 3, 1, 1, 0 | 18; and s₂ row 0, 1, 1, 2, 0, 1 | 12, the columns being P, x, y, z, s₁, s₂ and the value. Name the pivot column, the pivot row and the row operations, and say whether a further iteration is needed.

Accepted Answer

The most negative entry in the objective row is −5, so the pivot column is y. B1.
Ratio test on the y column: 18 ÷ 3 = 6 and 12 ÷ 1 = 12. M1. The smaller is 6, so the pivot row is the s₁ row and the pivot element is 3. A1.
Divide the pivot row by 3 for the new y row 0, 2/3, 1, 1/3, 1/3, 0 | 6. Subtract it once from the s₂ row for 0, 1/3, 0, 5/3, −1/3, 1 | 6. Add five times it to the objective row for 1, 1/3, 0, −7/3, 5/3, 0 | 30. M1 for the row operations, A1 for the three new rows.
So P = 30 with y = 6, x = 0, z = 0 and s₂ = 6. The objective row still holds −7/3 in the z column, so a further iteration is needed. B1 for that decision, with the negative entry as its reason.
Write each row operation beside the row it produced, in the form 'row 2 minus row 1', so that the tableau can be followed. Keep the entries as exact fractions: the decimals here recur, and rounding them corrupts the next ratio test.

Question 9

Continue from the tableau with objective row 1, 1/3, 0, −7/3, 5/3, 0 | 30; y row 0, 2/3, 1, 1/3, 1/3, 0 | 6; and s₂ row 0, 1/3, 0, 5/3, −1/3, 1 | 6, the columns being P, x, y, z, s₁, s₂ and the value. Carry out the next iteration and state the solution.

Accepted Answer

The only negative entry in the objective row is −7/3, so the pivot column is z. B1.
Ratio test on the z column: 6 ÷ (1/3) = 18 and 6 ÷ (5/3) = 18/5, which is 3.6. M1. The smaller is 3.6, so the pivot row is the s₂ row and the pivot element is 5/3. A1.
Multiply the pivot row by 3/5 for the new z row 0, 1/5, 0, 1, −1/5, 3/5 | 18/5. Subtract a third of it from the y row for 0, 3/5, 1, 0, 2/5, −1/5 | 24/5. Add seven thirds of it to the objective row for 1, 4/5, 0, 0, 6/5, 7/5 | 192/5. M1 for the row operations.
No negative entries remain, so the tableau is optimal: x = 0, y = 4.8, z = 3.6 with s₁ = s₂ = 0 and P = 38.4. A1.
Check against the problem the tableau came from, which maximises 3x + 5y + 4z: 3(0) + 5(4.8) + 4(3.6) = 24 + 14.4 = 38.4, and both constraints come out exactly at 18 and 12, matching the two zero slacks. The variable x stays out of the solution altogether, which is what the 4/5 in its column records.

Question 10

A final Simplex tableau for maximising P = 3x + 5y + 4z subject to 2x + 3y + z ≤ 18 and x + y + 2z ≤ 12 has objective row P + (4/5)x + (6/5)s₁ + (7/5)s₂ = 192/5, where s₁ and s₂ are the slack variables of the two constraints. Write down the value of P, state what one further unit of each resource is worth, and say what the entry in the x column means.

Accepted Answer

Every non-basic variable is zero, so P = 192/5 = 38.4. B1.
The coefficient of a slack variable in the final objective row is what one more unit of that resource would add to P. One more unit of the first resource is worth 6/5 = 1.2. B1. One more unit of the second is worth 7/5 = 1.4. B1.
The 4/5 in the x column says that bringing x into the solution would reduce P by 0.8 for every unit of x brought in, which is why x stays out. B1.
Both slacks are zero here, so both constraints are tight and both are worth something. A constraint with slack left over at the optimum shows a zero in its column, because more of a resource already in surplus changes nothing. Neither figure holds indefinitely: add enough units and the basis changes, after which the next unit is worth something else.

Question 11

Minimise C = 2x − 3y + 4z subject to x + y + z ≤ 10, 2x + y ≤ 8 and x, y, z ≥ 0. Set up a Simplex tableau, carry out one iteration, and state the minimum value of C.

Accepted Answer

The tableau maximises, so minimise C by maximising P = −C = −2x + 3y − 4z and read the answer back at the end. B1.
Adding slacks: x + y + z + s₁ = 10 and 2x + y + s₂ = 8, with the objective as P + 2x − 3y + 4z = 0. With columns P, x, y, z, s₁, s₂ and the value, the rows are P: 1, 2, −3, 4, 0, 0 | 0; s₁: 0, 1, 1, 1, 1, 0 | 10; s₂: 0, 2, 1, 0, 0, 1 | 8. B1.
The only negative entry is −3, so the pivot column is y. Ratios: 10 ÷ 1 = 10 and 8 ÷ 1 = 8, so the pivot row is the s₂ row and the pivot element is 1. That row is unchanged as the new y row 0, 2, 1, 0, 0, 1 | 8; subtracting it from the s₁ row gives 0, −1, 0, 1, 1, −1 | 2; adding three times it to the objective row gives 1, 8, 0, 4, 0, 3 | 24. M1 for the ratio test and the row operations.
No negative entries remain, so P = 24 at x = 0, y = 8, z = 0, and the minimum is C = −24. A1.
The −1 left in the s₁ row is ordinary and is simply skipped by any later ratio test.

Question 12

Continue from the tableau after the first iteration, with objective row 1, −2/3, 0, 0, 5/3 | 40, s₁ 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.

Accepted 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 s₁ 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, s₁ = s₂ = 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.

Question 13

Explain why a problem with a ≥ constraint cannot be started in the ordinary way, and describe the two methods that fix it.

Accepted 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.

Question 14

Maximise P = 3x + 2y subject to x + y ≤ 8, x + 3y ≥ 6 and x, y ≥ 0. Write the constraints as equations, set up the first stage of the two-stage Simplex method, carry that stage out, and state the feasible point it reaches.

Accepted Answer

The ≤ constraint gains a slack: x + y + s₁ = 8. The ≥ constraint loses a surplus and gains an artificial variable: x + 3y − s₂ + t₁ = 6. B1 for both equations with all three extra variables named.
Stage one minimises I = t₁, the sum of the artificial variables. From the second equation t₁ = 6 − x − 3y + s₂, so the stage-one row is I + x + 3y − s₂ = 6. B1 for stage one minimising the artificial variable.
With columns I, x, y, s₁, s₂, t₁ and the value, the tableau is I: 1, 1, 3, 0, −1, 0 | 6; s₁: 0, 1, 1, 1, 0, 0 | 8; t₁: 0, 1, 3, 0, −1, 1 | 6.
Since I is being minimised, pivot on the largest positive entry in its row, which is 3 in the y column. M1.
Ratio test: 8 ÷ 1 = 8 and 6 ÷ 3 = 2, so the pivot row is the t₁ row and the pivot element is 3. M1 for the ratio test, A1 for the pivot row.
Divide that row by 3 for the new y row 0, 1/3, 1, 0, −1/3, 1/3 | 2. Subtract it from the s₁ row for 0, 2/3, 0, 1, 1/3, −1/3 | 6. Subtract three times it from the stage-one row for 1, 0, 0, 0, 0, −1 | 0. A1 for the tableau after the pivot.
The stage-one row now reads I = 0, so the artificial variable has been driven out and stage one is finished. The point reached is x = 0, y = 2, with s₁ = 6 and s₂ = 0. A1.
Check it: 0 + 2 = 2 ≤ 8 and 0 + 3(2) = 6 ≥ 6, so it satisfies both original constraints and is a genuine corner of the feasible region. Stage two now starts from here on the real objective P = 3x + 2y, with the t₁ column deleted. The origin could not have been used: 0 + 0 = 0 is not ≥ 6.

Question 15

In a Simplex tableau being maximised, the entries of the pivot column in the constraint rows are −2, 0 and −5. Explain what this shows about the problem. In a second tableau the ratio test gives the same smallest ratio in two different rows; explain what happens next and what it means.

Accepted Answer

The ratio test uses only the positive entries of the pivot column, because a row limits how far the entering variable can rise only when increasing that variable drives the row's value down. M1.
Here no entry is positive: −2 and −5 make their rows' values grow as the entering variable grows, and 0 leaves its row untouched. No row limits the increase, so the entering variable may be raised for ever and the objective with it. A1.
The problem is therefore unbounded: the feasible region runs away in the direction the objective grows, and there is no optimal solution to report. B1. On a well-posed resource problem this points to a missing constraint rather than to an arithmetic error.
A tie in the ratio test means two basic variables reach zero together. Either row may be taken as the pivot row, and the algorithm continues. M1.
Whichever is chosen, the other basic variable is left at zero in the next tableau, so the solution is degenerate: a vertex where more constraint lines meet than the number of variables requires. A1.
The next iteration may then move to a new basis while the value in the corner does not change at all, so an unchanged objective after a pivot is not by itself a sign that something has gone wrong. B1.