Practise › Questions › The stepping-stone method
The stepping-stone method questions
Shadow costs say what each route ought to cost, improvement indices say which unused route improves on that, and the stepping-stone route moves goods onto it without breaking the totals.
6 original questions · 29 marks · the the stepping-stone method notes · Decision Mathematics 2
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.
Explain what the improvement index of an unused cell measures, and what a positive index tells you.
Worked answer
The index is the cell's cost minus its row shadow cost and its column shadow cost. It is the change in the total cost per unit sent along that route, once the rest of the plan has been adjusted to keep the supplies and demands satisfied. A positive index means using that route would raise the total, so the cell should stay empty. B1 for cost minus the two shadow costs, B1 for what the index measures, B1 for the positive case.A solution has R values A 0, B 3 and K values X 6, Y 4. The unused cell BX costs 8. Find its improvement index and say whether it is a candidate to enter.
Worked answer
Index = 8 − 3 − 6 = −1. It is negative, so the route is cheaper than the shadow costs predict and the cell is a candidate. M1 for cost minus the shadow costs, A1 for −1, B1 for the conclusion. Whether it actually enters depends on whether any other unused cell has a more negative index.Costs are AX 8, AY 5, AZ 6, BX 4, BY 9, BZ 7, CX 3, CY 6, CZ 5. The north-west corner solution is AX 35, AY 5, BY 30, CY 10, CZ 40, costing 835. Find the shadow costs and all four improvement indices.
Worked answer
Set R(A) = 0 and work outwards through the cells that are in use, since each of those satisfies R + K = cost. AX gives K(X) = 8 and AY gives K(Y) = 5. BY gives R(B) = 9 − 5 = 4, CY gives R(C) = 6 − 5 = 1, and CZ gives K(Z) = 5 − 1 = 4.
Each unused cell then has index cost − R − K. AZ = 6 − 0 − 4 = 2. BX = 4 − 4 − 8 = −8. BZ = 7 − 4 − 4 = −1. CX = 3 − 1 − 8 = −6.
M1 for setting R(A) = 0 and working outwards, A1 A1 for the R and K values, M1 for cost − R − K, A1 A1 for the four indices.
Write the R values down the side of the table and the K values along the top. The shadow costs are worth marks in their own right, so they must appear even if only the indices are asked for.Carry out the improvement. Name the entering cell, give the stepping-stone loop, state the value moved and the exiting cell, and give the new cost two ways.
Worked answer
The most negative index is −8, so BX enters. The loop turns only at cells that are in use, alternating signs: BX plus, BY minus, AY plus, AX minus, back to BX.
The minus cells hold BY 30 and AX 35, so the value moved is 30 and BY exits.
New allocations: AX 5, AY 35, BX 30, CY 10, CZ 40. Cost = 835 + 30(−8) = 595, and directly 5(8) + 35(5) + 30(4) + 10(6) + 40(5) = 40 + 175 + 120 + 60 + 200 = 595.
B1 for BX entering, M1 for the stepping-stone loop, A1 for the alternating signs, A1 for moving 30, A1 for BY exiting, A1 for 595.In that first table the cell CX had the lowest cost of all nine at 3, yet BX entered. Explain why, without recalculating the indices.
Worked answer
The entering cell is chosen by improvement index, not by cost. The index already accounts for what the rest of the plan must give up to accommodate the new route, which the raw cost ignores. Here CX scored −6 against BX's −8, so a unit sent along BX saves more than one sent along CX even though CX looks cheaper on the table. B1 for the index rather than the cost deciding, B1 for what the index allows for, B1 for the comparison of −8 with −6.Continue from the solution costing 595. A second round of indices gives CX = −6 as the only negative one. Complete the problem and justify that your answer is optimal.
Worked answer
CX enters. The loop is CX plus, AX minus, AY plus, CY minus, back to CX. The minus cells hold AX 5 and CY 10, so the value moved is 5 and AX exits.
New allocations: AY 40, BX 30, CX 5, CY 5, CZ 40. Cost = 595 + 5(−6) = 565, and directly 200 + 120 + 15 + 30 + 200 = 565.
A third round of shadow costs gives R(A) 0, R(B) 2, R(C) 1, K(X) 2, K(Y) 5 and K(Z) 4, so the four remaining indices are AX 6, AZ 2, BY 2 and BZ 1. All are positive, so no unused route would reduce the total and 565 is optimal. B1 for CX entering, M1 for the loop, A1 for moving 5, A1 for AX exiting, A1 for the new allocations, A1 for 565, M1 for the third round of indices, B1 for the optimality statement. Stopping at 595 because the improvement looked small would have left 30 on the table.
The same practice on paper: the printable workbook for this topic, questions and a worked answer book.
Practise the stepping-stone method 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.