Transportation problem

Why it matters

Moving raw material from suppliers to plants, and finished goods from plants to warehouses, is a recurring cost that a good allocation can cut by 10–30 %. The transportation problem is a special LP whose structure allows a fast hand method: get a starting allocation, then improve it with MODI until no route can lower the cost. The same machinery also handles production scheduling over time periods and is the parent of the assignment problem.

Key ideas

Model. m sources with supplies sᵢ, n destinations with demands dⱼ, a unit cost cᵢⱼ on each route; choose shipments xᵢⱼ ≥ 0 to minimise total cost while each source ships exactly its supply and each destination receives exactly its demand.

Balanced vs unbalanced. The method needs Σsᵢ = Σdⱼ.

• Supply > demand: add a dummy destination that absorbs the excess (cost 0, or a storage cost if given).
• Demand > supply: add a dummy source for the shortfall (cost 0, or a shortage penalty if given).
• A prohibited route gets a very large cost M.

Basic solution size. Of the m + n equations only m + n − 1 are independent, so a basic feasible solution has exactly m + n − 1 occupied cells that contain no closed loop.

Initial basic feasible solution.

• North-West Corner (NWC): start top-left, allocate min(supply, demand), move right if the column is satisfied or down if the row is exhausted. Ignores cost — quick but usually poor.
• Least Cost Method (LCM): allocate as much as possible to the cheapest remaining cell, strike out the satisfied row or column, repeat.
• Vogel's Approximation Method (VAM): for each row and column compute a penalty = difference between its two lowest remaining costs; in the row or column with the largest penalty, allocate to its cheapest cell. VAM usually starts at or very near the optimum.

Optimality — MODI (u-v) method.

1. For every occupied cell, uᵢ + vⱼ = cᵢⱼ; set one u (usually u₁) = 0 and solve.
2. For every empty cell, opportunity cost dᵢⱼ = cᵢⱼ − (uᵢ + vⱼ).
3. If all dᵢⱼ ≥ 0, the solution is optimal (a zero dᵢⱼ means alternative optima).
4. Otherwise enter the most negative cell, trace a closed loop of horizontal and vertical moves through occupied cells, mark corners + and − alternately, shift θ = the smallest allocation on a − corner, and repeat. uᵢ and vⱼ are the dual variables of the supply and demand constraints, so MODI is simplex written in table form.

Degeneracy. If fewer than m + n − 1 cells are occupied (it happens when a row and a column are satisfied at the same time), the u, v values cannot all be found. Put a tiny allocation ε in an independent empty cell (one that does not form a loop) and treat it as occupied; let ε → 0 at the end.

Formulas

• Objective: Min Z = Σᵢ Σⱼ cᵢⱼ · xᵢⱼ
• Supply: Σⱼ xᵢⱼ = sᵢ; demand: Σᵢ xᵢⱼ = dⱼ; xᵢⱼ ≥ 0
• Balance: Σ sᵢ = Σ dⱼ
• Number of basic cells: m + n − 1
• MODI: uᵢ + vⱼ = cᵢⱼ (occupied), dᵢⱼ = cᵢⱼ − (uᵢ + vⱼ) (empty)
• Cost change per loop: ΔZ = θ · dᵢⱼ

Symbols: cᵢⱼ = cost per unit on route i→j (₹/unit); xᵢⱼ = units shipped; sᵢ, dⱼ = supply and demand (units); uᵢ, vⱼ = row and column potentials (₹/unit); θ = quantity shifted around the loop (units).

Worked examples

Example 1 (three starting methods). Costs (₹/unit): F1 → [19, 30, 50, 10], F2 → [70, 30, 40, 60], F3 → [40, 8, 70, 20] to W1…W4. Supplies 7, 9, 18; demands 5, 8, 7, 14 (total 34 = 34, balanced).

1. NWC: x₁₁ = 5, x₁₂ = 2, x₂₂ = 6, x₂₃ = 3, x₃₃ = 4, x₃₄ = 14. Z = 95 + 60 + 180 + 120 + 280 + 280 = ₹1015.
2. LCM: cheapest 8 → x₃₂ = 8; 10 → x₁₄ = 7; 20 → x₃₄ = 7; 40 → x₂₃ = 7; 40 → x₃₁ = 3; finally x₂₁ = 2. Z = 64 + 70 + 140 + 280 + 120 + 140 = ₹814.
3. VAM: x₁₁ = 5, x₁₄ = 2, x₂₃ = 7, x₂₄ = 2, x₃₂ = 8, x₃₄ = 10. Z = 95 + 20 + 280 + 120 + 64 + 200 = ₹779. Each uses 6 = 3 + 4 − 1 cells.

Example 2 (GATE-type, MODI on the VAM solution).

1. With u₁ = 0: v₁ = 19, v₄ = 10; from (2,4): u₂ = 60 − 10 = 50; from (2,3): v₃ = 40 − 50 = −10; from (3,4): u₃ = 20 − 10 = 10; from (3,2): v₂ = 8 − 10 = −2.
2. Opportunity costs: d₁₂ = 30 − (0 − 2) = 32; d₁₃ = 50 − (0 − 10) = 60; d₂₁ = 70 − 69 = 1; d₂₂ = 30 − (50 − 2) = −18; d₃₁ = 40 − 29 = 11; d₃₃ = 70 − 0 = 70.
3. Only d₂₂ < 0, so (2,2) enters. Loop: (2,2)+ → (3,2)− → (3,4)+ → (2,4)−. θ = min(8, 2) = 2.
4. New allocation: x₂₂ = 2, x₃₂ = 6, x₃₄ = 12, x₂₄ = 0 (leaves). ΔZ = θ · d₂₂ = 2 × (−18) = −36, so Z = 779 − 36 = 743.
5. Re-run MODI: u = (0, 32, 10), v = (19, −2, 8, 10); all dᵢⱼ = 32, 42, 19, 18, 11, 52 are positive.
6. Optimal cost ₹743, unique (no zero dᵢⱼ): x₁₁ = 5, x₁₄ = 2, x₂₂ = 2, x₂₃ = 7, x₃₂ = 6, x₃₄ = 12.

Common mistakes

• Solving an unbalanced problem without first adding a dummy row or column.
• Computing the VAM penalty as largest minus smallest instead of the difference of the two smallest costs.
• Counting occupied cells wrong and missing degeneracy; then the u, v system cannot be solved.
• Placing ε in a cell that forms a closed loop with occupied cells.
• Choosing θ from a + corner, or forgetting that the loop turns only at occupied cells.
• In a maximisation (profit) table, applying the min rules directly — convert by subtracting every entry from the largest, or use negative profits.

For GATE PI

• Starting cost by NWC, LCM or VAM for a 3×3 or 3×4 table (NAT).
• Number of basic variables, recognising degeneracy, balancing with dummies.
• One MODI step: find uᵢ, vⱼ, the entering cell, θ and the new cost.
• Practise VAM penalties carefully — ties and simultaneous row/column exhaustion are where marks are lost.

Quick check

1. How many occupied cells must a basic solution of a 4 × 5 transportation problem have?
2. Supply 250, demand 300. What do you add?
3. In MODI, an empty cell has d = 0 at optimality. What does it mean?
4. Which starting method ignores costs?

Answers: 1. 4 + 5 − 1 = 8. 2. A dummy source of 50 units. 3. An alternative optimal solution exists. 4. North-West Corner.