Transportation problems
Studying this course? Keep your progress in one place.
Key facts
- A transportation problem sends a product from sources to destinations at least total cost.
- It must be balanced: add a dummy with all costs 0 if supply and demand differ.
- The north-west corner method gives a start; a basic solution has occupied cells.
- Find shadow costs from , then improvement indices . Optimal when none is negative.
- The stepping-stone method moves , the smallest quantity in a cell, round a loop.
The transportation problem
Move a single product from sources to destinations at unit cost to minimise total cost. Balance it first.
A transportation problem moves one product from sources (supplies) to destinations (demands). A transportation tableau has one row per source, one column per destination, and each cell shows the cost and the quantity sent.
The problem is balanced when total supply equals total demand. Cells carrying a quantity are occupied; the others are unoccupied. A non-degenerate basic solution has exactly occupied cells.
Check totals first and balance the problem before anything else.
- 1
Balance
add a dummy if supply and demand differ
- 2
Initial solution
north-west corner method
- 3
Shadow costs
solve R + K = C on occupied cells
- 4
Improvement indices
I = C - R - K on unoccupied cells
- 5
Stepping-stone
move θ round a loop through the entering cell
- 6
Repeat
stop when no index is negative
A problem has total supply 80 and total demand 75. What do you add to balance it?
The north-west corner method
Start at the top-left cell and send as much as possible. Cross out the used-up row or column and move on. Costs are ignored.
The north-west corner method gives an initial basic feasible solution without looking at costs.
Start at the top-left cell and send the smaller of the supply and the demand. Cross out the row or column that is used up and move to the next cell (right if the row has stock left, down if the column still needs stock). Repeat until everything is allocated.
Check each row and column total, and count the occupied cells.
- 1
Start top-left
cell W1S1
- 2
Send the smaller
of the row's supply and the column's demand
- 3
Cross out
the row or column that is used up
- 4
Move on
right if the row has stock, down if the column needs stock
- 5
Repeat
until all supply is allocated
| S1 | S2 | S3 | |
|---|---|---|---|
| W1 | 15 | 5 | – |
| W2 | – | 30 | – |
| W3 | – | – | 25 |
S1
- W1:
- 15
- W2:
- –
- W3:
- –
S2
- W1:
- 5
- W2:
- 30
- W3:
- –
S3
- W1:
- –
- W2:
- –
- W3:
- 25
Worked example
Sources W1, W2, W3 have supplies 20, 30, 25 and destinations S1, S2, S3 have demands 15, 35, 25. The costs of the occupied cells are 4, 6, 3 and 2 in order of allocation. Find the cost.
- 1
W1S1 . Column 1 is used up; W1 has 5 left.
- 2
W1S2 . Row 1 is used up; S2 still needs 30.
- 3
W2S2 . Both W2 and S2 are used up at once.
- 4
W3S3 .
- 5
Cost .
In the north-west corner method, which cell do you fill first?
Degeneracy and dummies
Fewer than occupied cells is degenerate. Unbalanced problems need a dummy source or destination with all costs 0.
Degeneracy: a solution with fewer than occupied cells is degenerate, as when W2 and S2 ran out at the same time. Place a quantity 0 (sometimes ) in an unoccupied cell, chosen so there is no closed loop of occupied cells, until there are .
Dummy locations: if supply exceeds demand add a dummy destination; if demand exceeds supply add a dummy source. All costs to or from a dummy are 0.
A quantity sent to or from a dummy is not real: it is unused stock or unmet demand.
- 1
Balance
add a dummy destination or source, all costs 0
- 2
Count cells
occupied cells must equal
- 3
Add a zero
put 0 in an unoccupied cell with no closed loop
- 4
Continue
as normal
| Supply exceeds demand | Demand exceeds supply | |
|---|---|---|
| Add | dummy destination | dummy source |
| All costs | 0 | 0 |
| Quantity means | unused stock | unmet demand |
Supply exceeds demand
- Add:
- dummy destination
- All costs:
- 0
- Quantity means:
- unused stock
Demand exceeds supply
- Add:
- dummy source
- All costs:
- 0
- Quantity means:
- unmet demand
A 3 by 4 problem has a basic solution with 5 occupied cells. Is it degenerate?
Shadow costs and indices
Find shadow costs with on occupied cells, then on the rest. Any negative index can be improved.
Find shadow costs (one per source) and (one per destination) so that for every occupied cell , with . Fill them in order along the occupied cells.
The improvement index of each unoccupied cell is : the change in total cost per unit if that cell is brought in.
If every the solution is optimal. Otherwise the most negative cell is the entering cell.
- 1
Set
then use on occupied cells
- 2
Find all and
working along occupied cells
- 3
Improvement indices
on unoccupied cells
- 4
Any negative?
most negative enters; if none, optimal
- Occupied cells
- Unoccupied cells
Worked example
Occupied costs are S1D1 4, S1D2 3, S2D2 5, S2D3 6 and S3D3 4. Find the shadow costs and the improvement index of S2D1 (cost 5).
- 1
Set .
- 2
S1D1: . S1D2: .
- 3
S2D2: , so . S2D3: , so .
- 4
S3D3: , so .
- 5
.
An unoccupied cell has , and . What should you do?
The stepping-stone method
Trace a closed loop through the entering cell with alternating signs, and move the smallest quantity in a cell round it.
Trace a closed loop that starts and ends at the entering cell and turns only at occupied cells, with alternating and signs starting with at the entering cell.
Let be the smallest quantity in a cell. Add it to the cells and subtract it from the cells. A cell that falls to 0 is the exiting cell.
Recalculate shadow costs and indices. Repeat until no index is negative. Each row and column total stays unchanged.
Worked example
The entering cell CX has . The loop is as drawn. The minus cells hold 30, 35 and 20. The cost is £540. Find the new cost.
- 1
.
- 2
Add 20 to the cells and subtract 20 from the cells. AX falls to 0, so AX is the exiting cell.
- 3
The cost falls by .
The minus cells in a loop hold 12, 8 and 15. What is ?
As a linear program
Let be the amount sent from source to destination : minimise cost subject to row sums equal supply and column sums equal demand.
Let be the amount sent from source to destination . For a balanced problem:
- Objective: minimise .
- Supply: for each source, .
- Demand: for each destination, .
Dummy cells carry zero cost, so they vanish from the objective but stay in the constraints.
There are variables and constraints, but only are independent, which is why a basic solution has occupied cells.
- 1
Variables
, amount from source to destination
- 2
Objective
minimise
- 3
Supply constraints
row sums equal
- 4
Demand constraints
column sums equal
- Supply (rows)
- Demand (columns)
- Objectiveminimise
A balanced problem has 3 sources and 4 destinations. How many variables and constraints does its LP have?
Try an exam question
Two depots and hold 40 and 35 units. Three shops , , need 20, 25 and 25 units. Balance the problem and use the north-west corner method to find an initial solution.
[4 marks]
- [1]Total supply 75 exceeds total demand 70, so add a dummy destination with demand 5.
- [1]All costs to the dummy are 0.
- [1] and .
- [1], and : 5 occupied cells, which is .
That's the notes covered.
Carry on to the next subtopic.
Try a question
Using the north-west corner method, how many units are sent from W1 to S2?
1 mark, marked against the mark scheme
Using the north-west corner method, how many units are sent from W1 to S2?
1 mark, marked against the mark scheme