Maths › Decision Mathematics 2 › The stepping-stone method
The stepping-stone method
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.
Builds on Transportation problems and The Simplex algorithm.
IN THIS TOPIC
- Find shadow costs from the cells in use.
- Compute improvement indices and identify the entering cell.
- Trace the stepping-stone route, find the exiting cell, and state the new cost.
- Formulate a transportation problem as a linear program.
COMMON MISCONCEPTION
The entering cell is the unused cell with the lowest cost in the table.
Shadow costs and indices
Give each row a number R and each column a number K, chosen so that R + K equals the cost of every cell currently in use. Setting the first R to zero fixes all the rest, and the m + n − 1 cells in use are exactly enough to determine them.
The formulae booklet carries nothing at all for Decision Maths, so every definition and every algorithm in this unit has to come from memory. A negative index means that route is cheaper than the shadow costs predict, so sending goods along it would reduce the total. The most negative index gives the entering cell. It need not be the cheapest unused cell in the table, because a raw cost says nothing about everything else in the plan that would have to shift to accommodate it, and shifting is what the shadow costs measure.
WORKED EXAMPLE
Which cell enters
For the north-west corner solution, find the shadow costs and the improvement indices.
Setting RA = 0: AX in use gives KX = 5, AY gives KY = 7, BY gives RB = −3, BZ gives KZ = 11, and CZ gives RC = −4.
Indices: AZ = 9 − 0 − 11 = −2; BX = 6 + 3 − 5 = 4; CX = 3 + 4 − 5 = 2; CY = 5 + 4 − 7 = 2.
Only AZ is negative, so AZ enters. Note that CX has the lowest cost in the whole table at 3, yet its index is positive.
Moving goods round the loop
From the entering cell, trace a closed route through cells already in use, alternately adding and subtracting. Each row and column must gain as much as it loses, which is what keeps the supplies and demands satisfied. Mark the entering cell with a plus and alternate round the loop.
The quantity moved, θ, is the smallest allocation sitting in a minus cell, since anything larger would drive that cell negative. That cell empties and becomes the exiting cell. The new cost is the old one plus θ times the improvement index, and it is worth checking that against a direct recalculation of the whole table.
GUIDED PRACTICE
One improvement
Carry out the improvement on the entering cell AZ, and state the new cost.
Show the working
The loop is AZ plus, AY minus, BY plus, BZ minus, back to AZ.
The minus cells hold AY 5 and BZ 10, so θ = 5 and AY exits.
New allocations: AX 25, AZ 5, BY 35, BZ 5, CZ 20.
New cost = 500 + 5(−2) = 490, and recalculating directly gives 125 + 45 + 140 + 40 + 140 = 490. A further round of indices shows none negative, so 490 is optimal.
The same problem as a linear program
Write xij for the number of units sent from source i to destination j. Minimise the total cost Σ cijxij, subject to one equation per source saying its shipments add to its supply, one equation per destination saying its receipts add to its demand, and xij ≥ 0 throughout.
A 3 by 3 problem therefore has nine variables and six constraints, one of which is redundant once the problem is balanced. Simplex would solve it, slowly. The transportation method is that same algorithm specialised to this shape, and that kinship is why shadow costs behave so much like the objective row of a tableau.
ASSESSMENT FOCUS
- Set the first shadow cost to zero and say that you have done so.
- Compute an index for every unused cell, not only the ones you expect to be negative.
- Draw the stepping-stone loop on the table with the plus and minus signs marked.
- State θ, name the exiting cell, and check the new cost two ways.
- Stop when no index is negative, and say that is why you have stopped.
CHECK YOURSELF
An unused cell has cost 12, its row shadow cost is 4 and its column shadow cost is 9. Find the improvement index and say what it means.
Show a hint
Cost minus the two shadow costs.
Show the answer
12 − 4 − 9 = −1. The index is negative, so using this route would reduce the total cost by 1 for every unit sent along it, and the cell is a candidate to enter.
Shadow costs satisfy R + K = cost for every cell in use, and the improvement index of an unused cell is cost − R − K.
The most negative index enters; θ is the smallest minus-cell allocation, that cell exits, and the cost falls by θ times the index.
As a linear program it is minimise Σ c x subject to one equation per source and one per destination.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
Or read them with their worked answers on the the stepping-stone method questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Find shadow costs from the cells in use.
- Compute improvement indices and identify the entering cell.
- Trace the stepping-stone route, find the exiting cell, and state the new cost.
- Formulate a transportation problem as a linear program.
Open the full revision checklist to see every objective in the course in one place.