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 beats 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.
WHAT YOU PROBABLY THINK
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 the rest, and the m + n − 1 cells in use are exactly enough to determine them all.
A negative index means that route is cheaper than the shadow costs predict, so using it would reduce the total. The most negative index gives the entering cell. It is not the cheapest unused cell in the table: the opening claim ignores what the rest of the plan would have to change to accommodate it, which 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 in use, alternately adding and subtracting. Each row and column must gain as much as it loses, so the supplies and demands stay satisfied. Mark the entering cell with a plus and alternate round the loop.
The quantity moved, θ, is the smallest allocation in a minus cell, since any more would make it negative. That cell empties and becomes the exiting cell. The new cost is the old one plus θ times the improvement index, which is worth checking against a direct recalculation.
The whole problem can also be written as a linear program: minimise the total cost subject to one equation per source and one per destination. Simplex would then solve it, and the transportation method is really Simplex specialised to that shape.
YOUR TURN
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 EXAM BIT
- 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.
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
1
2
−
4
−
9
=
−
1
.
T
h
e
i
n
d
e
x
i
s
n
e
g
a
t
i
v
e
,
s
o
u
s
i
n
g
t
h
i
s
r
o
u
t
e
w
o
u
l
d
r
e
d
u
c
e
t
h
e
t
o
t
a
l
c
o
s
t
b
y
1
f
o
r
e
v
e
r
y
u
n
i
t
s
e
n
t
a
l
o
n
g
i
t
,
a
n
d
t
h
e
c
e
l
l
i
s
a
c
a
n
d
i
d
a
t
e
t
o
e
n
t
e
r
.
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.
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.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- 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.
Open the full revision checklist to see every objective in the course in one place.
No animated video for this topic yet; these notes stand alone.