The Transportation Problem (TP) determines the cheapest way to ship a single
homogeneous commodity from \(m\) sources (factories, warehouses) to \(n\) destinations (markets,
customers), given supply at each source, demand at each destination and the unit shipping cost
between every (source, destination) pair.
It is a special class of linear programming, but its structure makes it solvable much faster
than the general simplex method.
Real-Life Examples
Distribution of cement bags from 3 cement plants to 5 cities.
Allocation of crude oil from 4 refineries to 7 petrol depots.
Posting of milk-cans from dairies to retail outlets.
Routing of containers from ports to inland warehouses.
2. Mathematical Formulation
Let:
\(m\) = number of sources; \(a_i\) = supply at source \(i\) (\(i = 1, \ldots, m\)).
\(n\) = number of destinations; \(b_j\) = demand at destination \(j\) (\(j = 1, \ldots, n\)).
\(c_{ij}\) = unit transportation cost from source \(i\) to destination \(j\).
\(x_{ij}\) = quantity shipped from source \(i\) to destination \(j\) (decision variable).
LP Form
\[
\text{Minimise } Z \;=\; \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij}\, x_{ij}
\]
Subject to:
\[
\sum_{j=1}^{n} x_{ij} \;=\; a_i, \quad i = 1, 2, \ldots, m \quad \text{(supply constraints)},
\]
\[
\sum_{i=1}^{m} x_{ij} \;=\; b_j, \quad j = 1, 2, \ldots, n \quad \text{(demand constraints)},
\]
\[
x_{ij} \ge 0 \quad \forall\, i, j.
\]
Balanced TP Condition
A TP is balanced if total supply equals total demand:
If unbalanced, add a dummy row or column with zero costs (Section 7).
Number of Basic Variables
A basic feasible solution to a balanced TP has exactly (m + n − 1) non-zero allocations (because one of the (m + n) constraints is redundant). Fewer non-zeros ⇒ degeneracy.
Find the cell with the least cost \(c_{ij}\) in the entire table (break ties arbitrarily).
Allocate \(x_{ij} = \min(a_i, b_j)\).
Cross out the exhausted row or column.
Repeat in the remaining (smaller) table.
Merits: uses cost information — usually a better starting solution than NWCM. Demerits: still ignores the relative badness of next-cheapest option (which VAM does capture).
EXAMPLE 1
For the same TP as Example 1 (NWCM):
Min cost is 1 at (S₁, D₂). Allocate min(300, 350) = 300. Row 1 exhausted.
In remaining table (S₂, S₃ × D₁..D₄), min cost is 2 at (S₂, D₁) and (S₃, D₄). Pick (S₂, D₁): allocate min(400, 250) = 250. Col 1 exhausted.
Min cost in remaining is 2 at (S₃, D₄). Allocate min(500, 200) = 200. Col 4 exhausted.
Min cost is 3 at (S₃, D₂) and (S₃, D₃). Pick (S₃, D₂): D₂ has 50 left. Allocate 50.
For a 3×3 problem with min-cost at (S₂, D₁) = 1, allocate the corresponding minimum; repeat in the reduced table. Process continues for at most (m + n − 1) steps.
6. IBFS — Vogel's Approximation Method (VAM)
Algorithm
For each row, compute row penalty = difference between the two smallest costs in that row.
For each column, similarly compute column penalty.
Identify the row or column with the largest penalty (ties broken arbitrarily).
In that row/column, allocate as much as possible to the least-cost cell.
Cross out the satisfied row/column; recompute penalties for the reduced table.
Repeat until all allocations are made.
Rationale: the penalty quantifies the regret if the cheapest cell is not used; allocating to the cell with the largest such regret is the "best bang for the buck".
Merits: usually produces a very close-to-optimal initial solution; often the optimum itself. Demerits: more arithmetic per step than NWCM or LCEM.
EXAMPLE 1
Same TP. Initial penalties:
D₁
D₂
D₃
D₄
Supply
Penalty
S₁
3
1
7
4
300
3−1 = 2
S₂
2
6
5
9
400
5−2 = 3
S₃
8
3
3
2
500
3−2 = 1
Demand
250
350
400
200
1200
Penalty
3−2=1
3−1=2
5−3=2
4−2=2
Largest penalty = 3 in row S₂. Min cost in S₂ is 2 at (S₂, D₁). Allocate min(400, 250) = 250. D₁ exhausted.
Continue with the reduced table; recalculate penalties; allocate; and so on. Final VAM solution typically gives cost ≈ 2700, close to optimal.
EXAMPLE 2
For a 2×3 TP with costs (4, 6, 8 / 8, 7, 5) and supplies (20, 30), demand (10, 25, 15):
Largest = 4 (col D₁). Min cost in D₁ = 4 at (S₁, D₁). Allocate min(20, 10) = 10. D₁ exhausted.
Continue: recompute penalties on remaining 2×2 table.
7. Optimality Test — MODI (Modified Distribution) Method
After obtaining an IBFS (by NWCM / LCEM / VAM), MODI tests whether it is optimum and, if not, gives an improved solution.
Algorithm
Compute u_i, v_j: For each occupied (basic) cell, write the dual equation
\(u_i + v_j = c_{ij}\). Set \(u_1 = 0\) (or any one of them) and solve for the rest. There
are exactly (m + n − 1) basic cells, matching the (m + n − 1) unknown \(u_i, v_j\) values.
Compute opportunity costs \(d_{ij} = c_{ij} - (u_i + v_j)\) for every non-basic cell.
Optimality criterion: if all \(d_{ij} \ge 0\), the solution is optimum. Stop.
If some \(d_{ij} < 0\), select the cell with the most negative \(d_{ij}\) (entering cell).
Form a closed loop starting and ending at the entering cell, using only basic cells at the turning points; alternately mark "+" and "−" starting with "+" at the entering cell.
Find θ = minimum allocation among the "−" cells.
Update: add θ to "+" cells, subtract θ from "−" cells. The "−" cell with allocation θ leaves the basis.
Repeat from step 1 until all \(d_{ij} \ge 0\).
EXAMPLE 1 — One iteration of MODI
Suppose the IBFS has basic cells (S₁,D₁)=20, (S₁,D₂)=30, (S₂,D₂)=10, (S₂,D₃)=40 with costs 4, 6, 5, 7.
Set \(u_1 = 0\). From (S₁,D₁): \(v_1 = 4\). From (S₁,D₂): \(v_2 = 6\). From (S₂,D₂): \(u_2 = -1\). From (S₂,D₃): \(v_3 = 8\).
If a non-basic cell has \(d_{ij} = -2\), forming the closed loop and adjusting by θ reduces the total cost by \(2\theta\). Continue until no negative \(d_{ij}\) remains.
8. Degeneracy in TP
DEFINITION
A TP solution is degenerate if the number of basic (non-zero) allocations is fewer than \(m + n − 1\). Degeneracy makes MODI fail because we don't have enough equations to solve for all \(u_i, v_j\).
How does degeneracy arise?
During IBFS — when a row and a column are exhausted simultaneously (tied min).
During MODI iterations — when more than one cell has the minimum allocation θ.
Resolution
Allocate an infinitesimally small quantity ε > 0 to a chosen empty (non-basic) cell so that the total number of allocations becomes \(m + n − 1\). The cell chosen should preserve the rim conditions (allow the dual equations to be solved). At the end of the algorithm, set ε = 0.
9. Unbalanced TP
If total supply ≠ total demand, the basic LP has no feasible solution. Two cases:
9.1 Supply > Demand
Add a dummy destination with demand = (supply − demand) and zero cost in every row.
Any allocations to the dummy column represent goods that remain unshipped.
9.2 Supply < Demand
Add a dummy source with supply = (demand − supply) and zero cost in every column.
Allocations to the dummy row represent unsatisfied demand.
After balancing, solve as a regular TP.
EXAMPLE 1
Supply = 100, 150; Demand = 80, 100, 90. Total supply = 250, demand = 270. Add dummy source with supply 20 and zero costs.
EXAMPLE 2
Supply = 60, 80; Demand = 50, 60. Total supply 140 > demand 110. Add dummy destination with demand 30 and zero costs.
10. Maximization Transportation Problem
Sometimes \(c_{ij}\) represents profit rather than cost, and we want to maximise \(Z\).
Conversion to Minimisation
Find the largest profit \(M = \max c_{ij}\).
Replace each \(c_{ij}\) by \(M - c_{ij}\). The new matrix has all non-negative entries with the largest profit becoming 0.
Solve as a minimization TP.
The optimum allocation from the converted TP is also the optimum for the original; total profit = \(\sum c_{ij}^{\text{original}} \cdot x_{ij}\).
EXAMPLE
Profit matrix:
D₁
D₂
D₃
S₁
40
25
22
S₂
44
35
30
M = 44. Conversion: 44 − each.
D₁
D₂
D₃
S₁
4
19
22
S₂
0
9
14
Solve this min-cost TP normally; the resulting allocation maximises original profit.
Summary Workflow
Check balance; add dummy if needed.
For maximization, convert (M − cᵢⱼ).
Find IBFS (NWCM / LCEM / VAM). VAM is usually best.
Apply MODI to test optimality and improve.
Resolve degeneracy with ε if it arises.
Report final allocations and cost (or profit).
Key Take-aways
TP is a special LP with structure → faster methods than simplex.
(m+n−1) basic variables in any non-degenerate BFS.
NWCM is simplest; LCEM uses costs; VAM uses penalties — accuracy ordering is NWCM < LCEM < VAM.