Lesson 8: The Transportation Problem: Formulation and Initial Solutions¶
8.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Formulate a transportation problem and recognise its special structure.
- Balance an unbalanced problem using dummy rows or columns.
- Construct an initial BFS by the North-West Corner Method (NWCM).
- Construct an initial BFS by the Least Cost Method (LCM).
- Construct an initial BFS by Vogel's Approximation Method (VAM) and explain why it is superior.
8.2 The Transportation Problem¶
Statement. \(m\) sources with supplies \(a_1,\ldots,a_m\) ship a homogeneous product to \(n\) destinations with demands \(b_1,\ldots,b_n\). Shipping one unit from source \(i\) to destination \(j\) costs \(c_{ij}\). Minimise total shipping cost.
Model.
The four special properties¶
(1) Feasibility condition. A solution exists iff the problem is balanced:
(2) One redundant constraint. Summing all supply equations and all demand equations gives the same total, so the \(m+n\) equations have rank \(m+n-1\).
(3) Total unimodularity. Every entry of \(A\) is \(0\) or \(1\), and each variable appears in exactly two constraints. Hence:
No integer programming is needed — a remarkable and practically important fact.
(4) A specialised algorithm exists. Because the structure is so regular, the problem is solved on a small tableau rather than a full simplex tableau, at a fraction of the effort.
The transportation tableau¶
| \(D_1\) | \(D_2\) | \(\cdots\) | \(D_n\) | Supply | |
|---|---|---|---|---|---|
| \(S_1\) | \(c_{11}\) | \(c_{12}\) | \(c_{1n}\) | \(a_1\) | |
| \(S_2\) | \(c_{21}\) | \(c_{22}\) | \(c_{2n}\) | \(a_2\) | |
| \(\vdots\) | |||||
| \(S_m\) | \(c_{m1}\) | \(c_{m2}\) | \(c_{mn}\) | \(a_m\) | |
| Demand | \(b_1\) | \(b_2\) | \(b_n\) | \(\sum a = \sum b\) |
Allocations \(x_{ij}\) are written inside the cells, next to the costs.
8.3 Balancing an Unbalanced Problem¶
| Situation | Fix |
|---|---|
| Supply > Demand (\(\sum a > \sum b\)) | add a dummy destination with demand \(\sum a - \sum b\) and zero costs |
| Demand > Supply (\(\sum b > \sum a\)) | add a dummy source with supply \(\sum b - \sum a\) and zero costs |
Interpretation.
- Units shipped to a dummy destination are never shipped — they remain in the warehouse. Cost 0 is correct if there is no holding charge; use the holding cost per unit if there is one.
- Units shipped from a dummy source represent unmet demand. Cost 0 means no penalty; use the shortage/penalty cost if lost sales matter.
Prohibited routes. If a route is impossible (no road, embargo, incompatible product), set \(c_{ij} = M\) (a very large number). The optimiser will avoid it automatically.
8.4 Three Methods for an Initial BFS¶
All three produce a BFS with \(m+n-1\) basic cells; they differ in quality and effort.
North-West Corner Method (NWCM)¶
1. Start at the top-left (north-west) cell
2. Allocate the maximum possible: x = min(remaining supply, remaining demand)
3. Cross out the exhausted row or column
4. Move to the new north-west corner of the remaining table
5. Repeat until all supply and demand are met
Property. Ignores cost entirely — fastest to apply, worst starting solution.
Least Cost Method (LCM / Matrix Minima)¶
1. Find the cell with the LOWEST cost in the whole table
2. Allocate the maximum possible there
3. Cross out the exhausted row or column
4. Repeat on the reduced table (ties broken arbitrarily)
Property. Greedy on cost — usually much better than NWCM, but can be short-sighted.
Vogel's Approximation Method (VAM)¶
1. For each row and column, compute the PENALTY
= (second smallest cost) - (smallest cost) among available cells
2. Select the row or column with the LARGEST penalty
3. In that row/column, allocate as much as possible to its LOWEST-cost cell
4. Cross out the exhausted row or column and RECOMPUTE all penalties
5. Repeat
The idea behind the penalty. The penalty is the regret — the extra cost incurred if you are forced to use the second-best cell in that line instead of the best. Attend first to the line with the most to lose.
Comparison¶
| Method | Effort | Solution quality | Use when |
|---|---|---|---|
| NWCM | lowest | poor | teaching the mechanics only |
| LCM | medium | good | quick manual work |
| VAM | highest | best | always, in practice |
8.5 Worked Example — All Three Methods¶
The problem (a classic instance).
| \(D_1\) | \(D_2\) | \(D_3\) | \(D_4\) | Supply | |
|---|---|---|---|---|---|
| \(S_1\) | 19 | 30 | 50 | 10 | 7 |
| \(S_2\) | 70 | 30 | 40 | 60 | 9 |
| \(S_3\) | 40 | 8 | 70 | 20 | 18 |
| Demand | 5 | 8 | 7 | 14 | 34 / 34 |
Balanced: \(7+9+18 = 34 = 5+8+7+14\) ✓. Basic cells required: \(m+n-1 = 3+4-1 = \mathbf{6}\).
NWCM¶
| Step | Cell | \(\min(\text{supply},\text{demand})\) | Allocate | Exhausted |
|---|---|---|---|---|
| 1 | \((1,1)\) | \(\min(7,5)\) | 5 | \(D_1\) |
| 2 | \((1,2)\) | \(\min(2,8)\) | 2 | \(S_1\) |
| 3 | \((2,2)\) | \(\min(9,6)\) | 6 | \(D_2\) |
| 4 | \((2,3)\) | \(\min(3,7)\) | 3 | \(S_2\) |
| 5 | \((3,3)\) | \(\min(18,4)\) | 4 | \(D_3\) |
| 6 | \((3,4)\) | \(\min(14,14)\) | 14 | both |
Allocation.
| \(D_1\) | \(D_2\) | \(D_3\) | \(D_4\) | |
|---|---|---|---|---|
| \(S_1\) | 5 | 2 | – | – |
| \(S_2\) | – | 6 | 3 | – |
| \(S_3\) | – | – | 4 | 14 |
Cost.
6 basic cells ✓.
LCM¶
| Step | Lowest available cost | Cell | Allocate | Exhausted |
|---|---|---|---|---|
| 1 | 8 | \((3,2)\) | \(\min(18,8) = 8\) | \(D_2\) |
| 2 | 10 | \((1,4)\) | \(\min(7,14) = 7\) | \(S_1\) |
| 3 | 20 | \((3,4)\) | \(\min(10,7) = 7\) | \(D_4\) |
| 4 | 40 | \((2,1)\) or \((3,1)\); take \((3,1)\) | \(\min(3,5) = 3\) | \(S_3\) |
| 5 | 70 | \((2,1)\) | \(\min(9,2) = 2\) | \(D_1\) |
| 6 | 40 | \((2,3)\) | \(\min(7,7) = 7\) | both |
Allocation.
| \(D_1\) | \(D_2\) | \(D_3\) | \(D_4\) | |
|---|---|---|---|---|
| \(S_1\) | – | – | – | 7 |
| \(S_2\) | 2 | – | 7 | – |
| \(S_3\) | 3 | 8 | – | 7 |
Cost.
Better than NWCM by \(1015 - 814 = 201\) (19.8 %).
VAM¶
Step 1 — initial penalties.
| Line | Costs | Two smallest | Penalty |
|---|---|---|---|
| \(S_1\) | 19, 30, 50, 10 | 10, 19 | 9 |
| \(S_2\) | 70, 30, 40, 60 | 30, 40 | 10 |
| \(S_3\) | 40, 8, 70, 20 | 8, 20 | 12 |
| \(D_1\) | 19, 70, 40 | 19, 40 | 21 |
| \(D_2\) | 30, 30, 8 | 8, 30 | 22 ← |
| \(D_3\) | 50, 40, 70 | 40, 50 | 10 |
| \(D_4\) | 10, 60, 20 | 10, 20 | 10 |
Largest penalty 22 in \(D_2\). Its cheapest cell is \((3,2)\) with cost 8. Allocate \(\min(18, 8) = 8\). \(D_2\) is exhausted; \(S_3\) has 10 left.
Step 2 — recompute penalties (columns \(D_1, D_3, D_4\) remain).
| Line | Costs | Penalty |
|---|---|---|
| \(S_1\) | 19, 50, 10 | \(19-10 = 9\) |
| \(S_2\) | 70, 40, 60 | \(60-40 = 20\) |
| \(S_3\) | 40, 70, 20 | \(40-20 = 20\) |
| \(D_1\) | 19, 70, 40 | 21 ← |
| \(D_3\) | 50, 40, 70 | 10 |
| \(D_4\) | 10, 60, 20 | 10 |
\(D_1\) wins with 21. Cheapest cell \((1,1)\), cost 19. Allocate \(\min(7,5) = 5\). \(D_1\) exhausted; \(S_1\) has 2 left.
Step 3. Remaining columns \(D_3, D_4\); rows \(S_1(2), S_2(9), S_3(10)\).
| Line | Costs | Penalty |
|---|---|---|
| \(S_1\) | 50, 10 | 40 |
| \(S_2\) | 40, 60 | 20 |
| \(S_3\) | 70, 20 | 50 ← |
| \(D_3\) | 50, 40, 70 | 10 |
| \(D_4\) | 10, 60, 20 | 10 |
\(S_3\) wins with 50. Cheapest cell \((3,4)\), cost 20. Allocate \(\min(10,14) = 10\). \(S_3\) exhausted; \(D_4\) has 4 left.
Step 4. Rows \(S_1(2), S_2(9)\); columns \(D_3(7), D_4(4)\).
| Line | Costs | Penalty |
|---|---|---|
| \(S_1\) | 50, 10 | 40 |
| \(S_2\) | 40, 60 | 20 |
| \(D_3\) | 50, 40 | 10 |
| \(D_4\) | 10, 60 | 50 ← |
\(D_4\) wins. Cheapest cell \((1,4)\), cost 10. Allocate \(\min(2,4) = 2\). \(S_1\) exhausted; \(D_4\) has 2 left.
Step 5. Only \(S_2(9)\) remains, with \(D_3(7)\) and \(D_4(2)\). Allocate \((2,4) = 2\) and \((2,3) = 7\).
Final VAM allocation.
| \(D_1\) | \(D_2\) | \(D_3\) | \(D_4\) | |
|---|---|---|---|---|
| \(S_1\) | 5 | – | – | 2 |
| \(S_2\) | – | – | 7 | 2 |
| \(S_3\) | – | 8 | – | 10 |
Cost.
Comparison¶
| Method | Cost | Excess over optimum (743) |
|---|---|---|
| NWCM | 1015 | +36.6 % |
| LCM | 814 | +9.6 % |
| VAM | 779 | +4.8 % |
| Optimum (L09) | 743 | — |
(In this instance VAM is not exactly optimal — L09's MODI method closes the remaining gap in one iteration. VAM is often exactly optimal on smaller or more structured problems.)
8.6 Solved Problems¶
Problem 1 — Balancing an unbalanced problem¶
Three plants supply 300, 400 and 500 units to four warehouses needing 250, 350, 400 and 100 units. Balance the problem and interpret the dummy.
Solution.
Add a dummy destination \(D_5\) with demand 100 and zero costs.
| \(D_1\) | \(D_2\) | \(D_3\) | \(D_4\) | \(D_5\) (dummy) | Supply | |
|---|---|---|---|---|---|---|
| \(P_1\) | \(c_{11}\) | \(c_{12}\) | \(c_{13}\) | \(c_{14}\) | 0 | 300 |
| \(P_2\) | \(c_{21}\) | \(c_{22}\) | \(c_{23}\) | \(c_{24}\) | 0 | 400 |
| \(P_3\) | \(c_{31}\) | \(c_{32}\) | \(c_{33}\) | \(c_{34}\) | 0 | 500 |
| Demand | 250 | 350 | 400 | 100 | 100 | 1200/1200 |
Interpretation. \(x_{i5}\) is the quantity left unshipped at plant \(i\). Since the model minimises cost and all dummy costs are 0, the optimiser will leave the surplus at whichever plant is most expensive to ship from — which is exactly right.
Basic cells now required: \(m+n-1 = 3+5-1 = \mathbf{7}\) (not 6).
Refining the dummy costs. Zero is correct only if surplus stock is free to hold. If plant \(i\) charges \(h_i\) per unit per period for storage, set \(c_{i5} = h_i\) and the model will decide where to hold stock and how much to ship, in one optimisation. This small change often makes the model genuinely useful rather than merely balanced.
(Similarly, if demand exceeded supply, a dummy source would represent unmet demand, and its costs should be the per-unit shortage penalties — lost margin plus goodwill — not zero.)
Problem 2 — Full NWCM with a degenerate step¶
Apply NWCM to supplies \((20, 30, 25)\) and demands \((15, 25, 35)\), with costs
| \(D_1\) | \(D_2\) | \(D_3\) | |
|---|---|---|---|
| \(S_1\) | 8 | 6 | 10 |
| \(S_2\) | 9 | 12 | 13 |
| \(S_3\) | 14 | 9 | 16 |
Solution.
Balance check. \(20+30+25 = 75 = 15+25+35\) ✓. Basic cells needed: \(3+3-1 = 5\).
| Step | Cell | Supply left | Demand left | Allocate | Exhausted |
|---|---|---|---|---|---|
| 1 | \((1,1)\) | 20 | 15 | 15 | \(D_1\) |
| 2 | \((1,2)\) | 5 | 25 | 5 | \(S_1\) |
| 3 | \((2,2)\) | 30 | 20 | 20 | \(D_2\) |
| 4 | \((2,3)\) | 10 | 35 | 10 | \(S_2\) |
| 5 | \((3,3)\) | 25 | 25 | 25 | both |
Allocation.
| \(D_1\) | \(D_2\) | \(D_3\) | |
|---|---|---|---|
| \(S_1\) | 15 | 5 | – |
| \(S_2\) | – | 20 | 10 |
| \(S_3\) | – | – | 25 |
Cost.
Basic cells: 5 ✓ — a proper BFS.
Note the "staircase" pattern. NWCM always produces this shape, because it works strictly left-to-right and top-to-bottom. Since it never looks at costs, it happens here to load the most expensive cell \((3,3)\) at cost 16 with the largest allocation of 25 — a clear symptom of the method's blindness.
(For comparison, VAM on this data gives \(Z = 755\) — and that happens to be the exact optimum. See Problem 3.)
Problem 3 — VAM with a tie in penalties¶
Apply VAM to the data of Problem 2 and compare with NWCM.
Solution.
Step 1 — penalties.
| Line | Costs | Two smallest | Penalty |
|---|---|---|---|
| \(S_1\) | 8, 6, 10 | 6, 8 | 2 |
| \(S_2\) | 9, 12, 13 | 9, 12 | 3 |
| \(S_3\) | 14, 9, 16 | 9, 14 | 5 ← |
| \(D_1\) | 8, 9, 14 | 8, 9 | 1 |
| \(D_2\) | 6, 12, 9 | 6, 9 | 3 |
| \(D_3\) | 10, 13, 16 | 10, 13 | 3 |
\(S_3\) has the largest penalty (5). Its cheapest cell is \((3,2)\), cost 9. Allocate \(\min(25, 25) = 25\). Both \(S_3\) and \(D_2\) are exhausted — cross out one (say \(D_2\)) and leave \(S_3\) with 0 to preserve the basic-cell count.
Step 2. Remaining: rows \(S_1(20), S_2(30)\); columns \(D_1(15), D_3(35)\).
| Line | Costs | Penalty |
|---|---|---|
| \(S_1\) | 8, 10 | 2 |
| \(S_2\) | 9, 13 | 4 |
| \(D_1\) | 8, 9 | 1 |
| \(D_3\) | 10, 13 | 3 |
\(S_2\) wins (4). Cheapest cell \((2,1)\), cost 9. Allocate \(\min(30,15) = 15\). \(D_1\) exhausted; \(S_2\) has 15 left.
Step 3. Only \(D_3\) remains, needing 35. Rows \(S_1(20)\), \(S_2(15)\). Allocate \((1,3) = 20\) and \((2,3) = 15\).
Allocation.
| \(D_1\) | \(D_2\) | \(D_3\) | |
|---|---|---|---|
| \(S_1\) | – | – | 20 |
| \(S_2\) | 15 | – | 15 |
| \(S_3\) | – | 25 | – |
Cost.
Comparison with NWCM.
And in this instance VAM is exactly optimal — MODI (L09) will confirm that no improvement is possible. This is common on small, well-structured problems, though not guaranteed (the §4 example left a 4.8 % gap).
A degeneracy warning. VAM used only 4 basic cells, but a BFS needs \(m+n-1 = 5\). This happened at Step 1 when a row and a column were exhausted simultaneously.
Choose a cell that does not create a closed loop with the existing basic cells — for example \((3,3)\) with allocation 0. This costs nothing but is essential for the MODI method of L09, which needs exactly \(m+n-1\) basic cells to compute the \(u_i\) and \(v_j\) multipliers.
Problem 4 — Choosing the method under time pressure¶
A logistics manager must solve a \(10\times15\) transportation problem by hand before a meeting in 20 minutes. Which method, and why? Estimate the effort.
Solution.
Problem size. \(m = 10\), \(n = 15\), so \(mn = 150\) cells and \(m+n-1 = 24\) basic cells.
Effort estimate.
| Method | Operations | Estimated time | Expected quality |
|---|---|---|---|
| NWCM | 24 allocations, no comparisons | ~3 min | 30–40 % above optimum |
| LCM | 24 allocations, each scanning up to 150 cells ≈ 1800 comparisons | ~12 min | 8–12 % above |
| VAM | 24 allocations, each recomputing 25 penalties ≈ 600 penalty computations, each needing 2 minima | ~25 min | 3–7 % above |
| MODI to optimality | VAM + several iterations, each needing 24 multipliers and 126 opportunity costs | ~60+ min | optimal |
Recommendation: LCM.
The reasoning. VAM would give a better answer but would not finish in time, and an unfinished VAM is worth nothing. LCM completes comfortably in 12 minutes and lands within about 10 % of optimum, leaving 8 minutes to sanity-check the arithmetic.
What the manager should say in the meeting. "This plan costs ₹X. It was produced by a cost-greedy heuristic and is likely within 10 % of optimal. I will run the exact optimisation this afternoon and expect to save a further 5–10 %."
The real answer, of course. A \(10\times15\) transportation problem is solved exactly, in milliseconds by any spreadsheet solver or a three-line Python script. Hand methods are taught to build understanding of the structure — the \(m+n-1\) basis, the loop, the multipliers — not because anyone should solve real problems this way.
Problem 5 — Modelling with prohibited routes and a dummy¶
A company has plants A (150) and B (200) and markets X (100), Y (120), Z (80). Route A→Z is impossible (no rail link). Shipping costs are:
| X | Y | Z | |
|---|---|---|---|
| A | 12 | 18 | — |
| B | 15 | 10 | 14 |
Formulate the balanced tableau and find an initial solution by VAM.
Solution.
Step 1 — check balance.
Supply exceeds demand by 50 ⟹ add a dummy market \(W\) with demand 50 and zero costs.
Step 2 — handle the prohibited route. Set \(c_{AZ} = M\) (a very large number, say 1000).
The balanced tableau.
| X | Y | Z | W (dummy) | Supply | |
|---|---|---|---|---|---|
| A | 12 | 18 | \(M\) | 0 | 150 |
| B | 15 | 10 | 14 | 0 | 200 |
| Demand | 100 | 120 | 80 | 50 | 350/350 |
Basic cells needed: \(2+4-1 = \mathbf{5}\).
Step 3 — VAM.
Penalties (round 1).
| Line | Costs | Penalty |
|---|---|---|
| A | 12, 18, \(M\), 0 | \(12 - 0 = 12\) |
| B | 15, 10, 14, 0 | \(10 - 0 = 10\) |
| X | 12, 15 | 3 |
| Y | 18, 10 | 8 |
| Z | \(M\), 14 | \(M - 14\) ← huge |
| W | 0, 0 | 0 |
Column Z has an enormous penalty — the prohibited route makes the alternative essential. Cheapest cell in Z is \((B, Z)\) at 14. Allocate \(\min(200, 80) = 80\). Z exhausted; B has 120 left.
Penalties (round 2), columns X, Y, W:
| Line | Costs | Penalty |
|---|---|---|
| A | 12, 18, 0 | 12 |
| B | 15, 10, 0 | 10 |
| X | 12, 15 | 3 |
| Y | 18, 10 | 8 |
| W | 0, 0 | 0 |
Row A wins (12). Cheapest cell is \((A, W)\) at 0. Allocate \(\min(150, 50) = 50\). W exhausted; A has 100 left.
Penalties (round 3), columns X, Y:
| Line | Costs | Penalty |
|---|---|---|
| A | 12, 18 | 6 |
| B | 15, 10 | 5 |
| X | 12, 15 | 3 |
| Y | 18, 10 | 8 ← |
Column Y wins. Cheapest cell \((B, Y)\) at 10. Allocate \(\min(120, 120) = 120\). Both B and Y are exhausted.
Remaining: A has 100, X needs 100. Allocate \((A, X) = 100\).
Final allocation.
| X | Y | Z | W | |
|---|---|---|---|---|
| A | 100 | – | – | 50 |
| B | – | 120 | 80 | – |
Cost.
Basic cells: 4, but \(m+n-1 = 5\) ⟹ degenerate. Add a zero allocation at, say, \((B, W)\) to restore the count for L09's MODI method.
Reading the answer for management.
- Plant A ships its entire usable output (100 units) to market X.
- 50 units of A's capacity are unused (the dummy) — A is the plant with excess capacity.
- Plant B serves Y and Z entirely.
- The prohibited route A→Z was avoided automatically — no allocation appears there ✓, confirming the \(M\)-cost trick worked.
A management insight from the dummy. The 50 idle units sit at plant A. If A has higher fixed costs than B, this is the evidence needed to consider consolidating production at B — an insight the transportation model surfaces for free.
8.7 Practice Problems¶
- Balance: supplies \((50,80)\), demands \((30,40,20)\). [Ans: demand 90 < supply 130; dummy destination with demand 40]
- Apply NWCM to supplies \((10,20)\), demands \((15,15)\) and give the basic-cell count. [Ans: 3 cells]
- Compute the VAM penalties for the first round of the §4 example and confirm 22 in \(D_2\).
- Why does a transportation BFS have \(m+n-1\) rather than \(m+n\) basic cells?
- A \(4\times6\) problem: how many basic cells? [Ans: 9]
- State the cost to place in a dummy destination when surplus stock incurs ₹5/unit holding cost. [Ans: 5, not 0]
- Explain why integer supplies guarantee an integer optimum.
8.8 Summary¶
- The transportation problem ships from \(m\) sources to \(n\) destinations at minimum cost; it is an LP with a very special structure.
- Feasible iff balanced (\(\sum a = \sum b\)); unbalance is fixed by a dummy row or column, whose costs should be the true holding or shortage costs, not reflexively zero.
- One constraint is redundant, so a BFS has exactly \(m+n-1\) basic cells. Fewer ⟹ degenerate; insert a zero allocation that creates no loop.
- Total unimodularity ⟹ integer supplies give an integer optimum automatically — no integer programming needed.
- Prohibited routes are handled by setting \(c_{ij} = M\).
- Three starting methods: NWCM (ignores cost — worst), LCM (greedy on cost), VAM (largest regret first — best, typically within 5–10 % of optimum). On the worked example: 1015 / 814 / 779 against an optimum of 743.
Next lesson: L09 — Optimality by the MODI (u–v) method.
Practise now: unit1-lp-lab.html → Transportation Lab: enter any cost table and run NWCM, LCM
and VAM side by side, with penalties shown at every step.