Skip to content

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:

  1. Formulate a transportation problem and recognise its special structure.
  2. Balance an unbalanced problem using dummy rows or columns.
  3. Construct an initial BFS by the North-West Corner Method (NWCM).
  4. Construct an initial BFS by the Least Cost Method (LCM).
  5. 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.

\[ \begin{aligned} \min\ & Z = \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij}x_{ij}\\ \text{s.t. } & \sum_{j=1}^{n} x_{ij} = a_i && i = 1,\ldots,m && \text{(supply)}\\ & \sum_{i=1}^{m} x_{ij} = b_j && j = 1,\ldots,n && \text{(demand)}\\ & x_{ij} \ge 0 \end{aligned} \]

The four special properties

(1) Feasibility condition. A solution exists iff the problem is balanced:

\[ \sum_{i=1}^{m}a_i \ =\ \sum_{j=1}^{n}b_j \]

(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\).

\[ \boxed{\ \textbf{A basic feasible solution has exactly } m+n-1 \textbf{ basic cells.}\ } \]

(3) Total unimodularity. Every entry of \(A\) is \(0\) or \(1\), and each variable appears in exactly two constraints. Hence:

\[ \boxed{\ \textbf{Integer supplies and demands} \ \Longrightarrow\ \textbf{integer optimal solution, automatically.}\ } \]

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.
\[ \boxed{\ \textbf{Setting the dummy costs thoughtfully is where the modelling judgement lies.}\ } \]

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.

\[ \boxed{\ \textbf{VAM typically lands within 5–10 \% of the optimum, and often ON it.}\ } \]

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.

\[ Z = 5(19) + 2(30) + 6(30) + 3(40) + 4(70) + 14(20) \]
\[ = 95 + 60 + 180 + 120 + 280 + 280 = \mathbf{1015} \]

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.

\[ Z = 7(10) + 2(70) + 7(40) + 3(40) + 8(8) + 7(20) \]
\[ = 70 + 140 + 280 + 120 + 64 + 140 = \mathbf{814} \]

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.

\[ Z = 5(19) + 2(10) + 7(40) + 2(60) + 8(8) + 10(20) \]
\[ = 95 + 20 + 280 + 120 + 64 + 200 = \mathbf{779} \]

Comparison

Method Cost Excess over optimum (743)
NWCM 1015 +36.6 %
LCM 814 +9.6 %
VAM 779 +4.8 %
Optimum (L09) 743 —
\[ \boxed{\ \textbf{VAM starts 4.8 \% from optimal; NWCM starts 36.6 \% away. Always use VAM.}\ } \]

(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.

\[ \sum a = 300+400+500 = \mathbf{1200}, \qquad \sum b = 250+350+400+100 = \mathbf{1100} \]
\[ \text{Supply exceeds demand by } 1200 - 1100 = \mathbf{100} . \]

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.

\[ Z = 15(8) + 5(6) + 20(12) + 10(13) + 25(16) \]
\[ = 120 + 30 + 240 + 130 + 400 = \mathbf{920} \]

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.

\[ Z = 20(10) + 15(9) + 15(13) + 25(9) = 200 + 135 + 195 + 225 = \mathbf{755} \]

Comparison with NWCM.

\[ \text{NWCM} = 920, \qquad \text{VAM} = 755, \qquad \text{saving} = 165 \ (\mathbf{17.9\%}) \]

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.

\[ \boxed{\ \textbf{Fix: place a zero allocation ($\epsilon$) in a suitable empty cell to restore 5 basic cells.}\ } \]

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.

\[ \boxed{\ \textbf{The best method is the best one you can actually complete.}\ } \]

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.

\[ \sum a = 150+200 = \mathbf{350}, \qquad \sum b = 100+120+80 = \mathbf{300} \]

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.

\[ Z = 100(12) + 50(0) + 120(10) + 80(14) = 1200 + 0 + 1200 + 1120 = \mathbf{₹3{,}520} \]

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

  1. Balance: supplies \((50,80)\), demands \((30,40,20)\). [Ans: demand 90 < supply 130; dummy destination with demand 40]
  2. Apply NWCM to supplies \((10,20)\), demands \((15,15)\) and give the basic-cell count. [Ans: 3 cells]
  3. Compute the VAM penalties for the first round of the §4 example and confirm 22 in \(D_2\).
  4. Why does a transportation BFS have \(m+n-1\) rather than \(m+n\) basic cells?
  5. A \(4\times6\) problem: how many basic cells? [Ans: 9]
  6. State the cost to place in a dummy destination when surplus stock incurs ₹5/unit holding cost. [Ans: 5, not 0]
  7. 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.