Maths › Decision Mathematics 2 › Transportation problems
Transportation problems
Several warehouses, several shops, and a cost for every route between them. The first job is any feasible plan at all, and the north-west corner method supplies one without looking at the costs.
Builds on Linear programming: formulation and Algorithms, sorting and bin packing.
IN THIS TOPIC
- Balance a problem with a dummy source or destination.
- Find an initial solution by the north-west corner method.
- Count the cells used and recognise degeneracy.
WHAT YOU PROBABLY THINK
The north-west corner method gives a good starting solution because it fills the cheapest cells first.
A plan that ignores the costs
A transportation problem has supplies at several sources, demands at several destinations, and a cost per unit for each route. The total supply and total demand must match before anything else happens: if they do not, add a dummy destination or source taking the surplus at zero cost, which balances the problem without changing any real decision.
The north-west corner method then fills the top-left cell as far as the supply and demand allow, crosses off whichever runs out, and repeats on the reduced table. It never looks at a single cost, which is exactly why it is quick and why the answer is usually poor: the opening claim credits it with a cleverness it does not have. Its only job is to get a feasible plan on paper so that the improvement machinery has something to work on.
WORKED EXAMPLE
The first solution
Supplies A 30, B 40, C 20; demands X 25, Y 35, Z 30. Costs are AX 5, AY 7, AZ 9, BX 6, BY 4, BZ 8, CX 3, CY 5, CZ 7. Find the north-west corner solution and its cost.
AX takes min(30, 25) = 25, using up X. AY then takes the remaining 5 of A, using up A.
BY takes 30 of the 35 Y needs, then BZ takes B's remaining 10, and CZ takes the last 20.
Cost = 25(5) + 5(7) + 30(4) + 10(8) + 20(7) = 500.
Counting the cells
A solution to an m by n problem should use exactly m + n − 1 cells. That is the number the improvement method needs: enough to determine the shadow costs, and no more than a spanning structure allows. Here 3 + 3 − 1 = 5, and the north-west corner solution uses five, so all is well.
When fewer cells are used the solution is degenerate, which happens when a supply and a demand run out together. The fix is to record a zero allocation in one adjacent cell, which restores the count without moving any goods. It looks like a piece of bookkeeping, and it is, but without it the shadow costs cannot all be found.
YOUR TURN
Balancing and counting
Supplies are 30, 40 and 20; demands are 25, 35 and 20. Explain what has to be done before starting, and how many cells the solution should use.
Show the working
Total supply is 90 and total demand is 80, so the problem is unbalanced.
Add a dummy destination with demand 10 and a cost of zero from every source.
The table is now 3 by 4, so a solution should use 3 + 4 − 1 = 6 cells.
Whichever source ends up supplying the dummy is the one whose goods are not sent anywhere, at no cost.
THE EXAM BIT
- Check that supply equals demand first, and add a dummy with zero costs if it does not.
- Work strictly from the top left; the method has no discretion in it.
- State the cost of your initial solution, and say that it is only a starting point.
- Count the cells against m + n − 1 and add a zero allocation if the solution is degenerate.
CHECK YOURSELF
A transportation problem has 4 sources and 3 destinations. How many cells should a solution use, and what does it mean if it uses five?
Show a hint
m + n − 1.
Show the answer
4
+
3
−
1
=
6
c
e
l
l
s
.
U
s
i
n
g
o
n
l
y
f
i
v
e
m
e
a
n
s
t
h
e
s
o
l
u
t
i
o
n
i
s
d
e
g
e
n
e
r
a
t
e
,
s
o
a
z
e
r
o
a
l
l
o
c
a
t
i
o
n
m
u
s
t
b
e
e
n
t
e
r
e
d
i
n
a
s
u
i
t
a
b
l
e
c
e
l
l
b
e
f
o
r
e
t
h
e
i
m
p
r
o
v
e
m
e
n
t
m
e
t
h
o
d
c
a
n
b
e
a
p
p
l
i
e
d
.
Balance the problem with a zero-cost dummy first, then fill from the north-west corner without looking at any cost.
A solution to an m by n problem uses m + n − 1 cells; fewer means degeneracy, fixed by recording a zero allocation.
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.
- Balance a problem with a dummy source or destination.
- Find an initial solution by the north-west corner method.
- Count the cells used and recognise degeneracy.
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.