Use Vogel’s approximation method to solve the following transportation problem :
Distribution Centre
Plant | D₁ | D₂ | D₃ | D₄ | Capacity
P₁ | 2 | 3 | 11 | 7 | 6
P₂ | 1 | 0 | 6 | 1 | 1
P₃ | 5 | 8 | 15 | 9 | 10
Demand | 7 | 5 | 3 | 2
10 marks · directive: Solve
The core of a good answer
The problem is balanced (supply 17 = demand 17); Vogel's method gives the initial solution P₁D₁ = 1, P₁D₂ = 5, P₂D₄ = 1, P₃D₁ = 6, P₃D₃ = 3, P₃D₄ = 1 with cost 102, and two MODI improvements lead to the optimum P₁D₂ = 5, P₁D₃ = 1, P₂D₃ = 1, P₃D₁ = 7, P₃D₃ = 1, P₃D₄ = 2 with minimum cost 100.
An outline written by upsc.help, not an official UPSC answer; every fact checked by a separate review. How we work
What the question asks
Find the initial basic feasible solution by VAM (penalties = difference of the two smallest costs in each row and column; allocate in the least-cost cell of the line with the largest penalty), then test it by MODI and improve to the optimum. Show the penalty steps and the final table.
Answer outline
Introduction
Supplies 6 + 1 + 10 = 17; demands 7 + 5 + 3 + 2 = 17: balanced, so m + n − 1 = 6 basic cells are needed.
Step 1: VAM allocations
- Penalties rows (1, 1, 3), columns (1, 3, 5, 6): largest 6 in D₄; least cost P₂D₄ = 1; allocate 1. P₂ exhausted.
- Rows P₁ 1, P₃ 3; columns D₁ 3, D₂ 5, D₃ 4, D₄ 2: largest 5 in D₂; least cost P₁D₂ = 3; allocate 5. D₂ satisfied, P₁ has 1 left.
- Rows P₁ 5 (costs 2, 11, 7), P₃ 4; columns D₁ 3, D₃ 4, D₄ 2: largest 5 in P₁; least cost P₁D₁ = 2; allocate 1. P₁ exhausted.
- Only P₃ remains: P₃D₁ = 6, P₃D₃ = 3, P₃D₄ = 1.
- Cost = 2(1) + 3(5) + 1(1) + 5(6) + 15(3) + 9(1) = 2 + 15 + 1 + 30 + 45 + 9 = 102. Six occupied cells = m + n − 1, non-degenerate.
Step 2: MODI test of the VAM solution
- With u₃ = 0: v₁ = 5, v₃ = 15, v₄ = 9; u₁ = −3, v₂ = 6; u₂ = −8.
- Δᵢⱼ = cᵢⱼ − uᵢ − vⱼ for empty cells: P₁D₃ = −1, P₁D₄ = 1, P₂D₁ = 4, P₂D₂ = 2, P₂D₃ = −1, P₃D₂ = 2.
- Negative Δ: not optimal.
Step 3: First improvement
- Enter P₂D₃; loop P₂D₃(+) P₂D₄(−) P₃D₄(+) P₃D₃(−); θ = min(1, 3) = 1.
- New solution P₁D₁ 1, P₁D₂ 5, P₂D₃ 1, P₃D₁ 6, P₃D₃ 2, P₃D₄ 2; cost 101.
- Recompute: u₃ = 0, u₁ = −3, u₂ = −9; Δ(P₁D₃) = −1, still negative.
Step 4: Second improvement
- Enter P₁D₃; loop P₁D₃(+) P₁D₁(−) P₃D₁(+) P₃D₃(−); θ = min(1, 2) = 1.
- Solution: P₁D₂ = 5, P₁D₃ = 1, P₂D₃ = 1, P₃D₁ = 7, P₃D₃ = 1, P₃D₄ = 2.
- Cost = 3(5) + 11(1) + 6(1) + 5(7) + 15(1) + 9(2) = 15 + 11 + 6 + 35 + 15 + 18 = 100.
- MODI: u₃ = 0, u₁ = −4, u₂ = −9, v = (5, 7, 15, 9); all Δ > 0 (P₁D₁ 1, P₁D₄ 2, P₂D₁ 5, P₂D₂ 2, P₂D₄ 1, P₃D₂ 1): optimal and unique.
Conclusion
VAM gives a starting cost of 102, within 2% of the optimum; the optimal shipping plan costs 100. All steps were recomputed in Python and the optimum confirmed by a linear programming solver.
Examples and data to cite
- Here VAM's starting cost (102) is within 2% of the optimum (100), as computed in Python.
- The MODI method uses the dual variables uᵢ, vⱼ of the transportation LP.
Facts to remember
- VAM penalty = difference between the two lowest costs in a row or column.
- Allocate in the cheapest cell of the line with the highest penalty.
- MODI: uᵢ + vⱼ = cᵢⱼ for basic cells; optimal when all cᵢⱼ − uᵢ − vⱼ ≥ 0.
- A basic feasible solution needs m + n − 1 occupied cells.