Transportation Problem: Formulation and Solution Methods

The transportation problem is a special type of linear programming: ship goods from several sources (factories) to several destinations (warehouses) at minimum cost. Each source has a fixed supply, each destination has a fixed demand, and each route has a unit shipping cost.

It matters because distribution is a huge cost in every supply chain. Companies that ship thousands of tonnes daily use transportation models to decide exactly how much each factory sends to each warehouse, saving large sums of money.

Key Concepts

• Supply: amount available at each source aᵢ; demand: amount needed at each destination bⱼ.
• Unit cost cᵢⱼ: cost of shipping one unit from source i to destination j.
• Balanced problem: total supply equals total demand; unbalanced problems add a dummy source or destination with zero cost.
• Basic feasible solution: needs exactly m + n − 1 occupied cells (for m sources, n destinations).
• Degeneracy: fewer than m + n − 1 positive allocations; handled by adding a tiny ε allocation.

Formulas

Minimise Z = ΣᵢΣⱼ cᵢⱼxᵢⱼ subject to Σⱼxᵢⱼ = aᵢ, Σᵢxᵢⱼ = bⱼ, xᵢⱼ ≥ 0.

• Northwest corner rule: a simple starting method — fill from the top-left cell, exhausting supplies and demands in order.
• Vogel's approximation (VAM): penalises not using the cheapest routes; gives near-optimal starts.
• MODI (u-v) method: computes cell evaluations dᵢⱼ = cᵢⱼ − (uᵢ + vⱼ) on occupied cells; if all ≥ 0 the solution is optimal (minimisation).

Assumptions: costs are linear per unit, supply and demand are known constants, and the problem is balanced.

Worked Example

Two factories supply A = 50, B = 50; two warehouses need X = 30, Y = 70. Costs: A→X = 4, A→Y = 6, B→X = 5, B→Y = 3.

1. Northwest corner: A→X = 30 (X demand met, A has 20 left); A→Y = 20 (A supply met, Y has 50 left); B→Y = 50. Cost = 30·4 + 20·6 + 50·3 = 120 + 120 + 150 = 390.
2. MODI check: occupied cells give u₁ = 0, v₁ = 4, v₂ = 6, u₂ = −3. Empty cell B→X: d = 5 − (−3 + 4) = 4 ≥ 0 → optimal.
3. Check supplies: A ships 30 + 20 = 50 ✓; B ships 50 ✓; X receives 30 ✓; Y receives 70 ✓.

Minimum cost is 390 with this allocation.

Common Misconceptions

• "Cheapest route first is always optimal." Greedy cheapest-first can be suboptimal; VAM's penalty logic does better.
• "Supply must equal demand exactly." Dummy sources/destinations with zero cost handle imbalances.
• "A starting solution is the final answer." Northwest corner is rarely optimal; MODI improvement steps are needed.

Real-World Applications

• Cement and grain companies route bulk shipments from plants to depots daily.
• Disaster relief agencies allocate supplies from depots to affected areas at minimum cost.
• Airlines assign crew bases to flight legs as transportation-type problems.

The transportation problem models one of the most common decisions in business — who ships what to whom. Its special structure allows fast dedicated methods like VAM and MODI instead of full simplex tableaux.