Maths › Decision Mathematics 2 › Transportation problems and the north-west corner method
Transportation problems and the north-west corner method
A transportation problem distributes goods from several sources to several destinations at the least total cost. The first step is finding 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.
COMMON MISCONCEPTION
The north-west corner method gives a good starting solution because it fills the cheapest cells first.
The north-west corner method never looks at a single cost. It fills the top-left cell as far as the supply and demand allow, crosses off whichever of the two runs out, and repeats on the reduced table, which is what makes it quick. What it delivers is a feasible starting solution, and the improvement stage that follows is where the costs enter and the total comes down.
A feasible starting solution
A transportation problem has supplies at several sources, demands at several destinations, and a cost per unit for each route. Total supply and total demand must match before anything else happens. If they do not, add a dummy destination or source to take 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 of the two runs out, and repeats on the reduced table. It never looks at a single cost, which is what makes it quick. It provides a feasible starting solution with no claim to be optimal, and the improvement stage that follows is what reduces the cost.
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 pin down every shadow cost and no more than a spanning structure allows. Here 3 + 3 − 1 = 5, and the north-west corner solution uses five, as required.
Use fewer and 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, restoring the count without moving any goods. It is only bookkeeping, but without it the shadow costs cannot all be found.
GUIDED PRACTICE
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.
Goods allocated to the dummy are not sent anywhere, and cost nothing.
ASSESSMENT FOCUS
- 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 cells. Using only five means the solution is degenerate, so a zero allocation must be entered in a suitable cell before the improvement method can be applied.
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.
Or read them with their worked answers on the transportation problems and the north-west corner 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.
- 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.