What is a Transportation problem ? Give a general mathematical model of a transportation problem.
5 marks · directive: Explain
The core of a good answer
A transportation problem is a special linear programme that finds how many units xᵢⱼ to ship from each of m sources (supply aᵢ) to each of n destinations (demand bⱼ) so as to minimise total cost ΣΣ cᵢⱼxᵢⱼ subject to Σⱼ xᵢⱼ = aᵢ, Σᵢ xᵢⱼ = bⱼ and xᵢⱼ ≥ 0, with Σaᵢ = Σbⱼ for a balanced problem.
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
Definition plus the model: decision variables, objective, supply and demand constraints, non-negativity, the balance condition, and key properties (m + n − 1 basic variables, integrality). Brief, 5 marks.
Answer outline
Introduction
The problem is credited to F. L. Hitchcock (1941) and is also called the Hitchcock-Koopmans transportation problem; its constraint matrix has a special structure that allows simple solution methods.
Model
- Minimise Z = Σᵢ₌₁ᵐ Σⱼ₌₁ⁿ cᵢⱼ xᵢⱼ
- Subject to Σⱼ₌₁ⁿ xᵢⱼ = aᵢ, i = 1, ..., m (supply)
- Σᵢ₌₁ᵐ xᵢⱼ = bⱼ, j = 1, ..., n (demand)
- xᵢⱼ ≥ 0 for all i, j
- Balanced if Σaᵢ = Σbⱼ; otherwise add a dummy source or destination with zero cost.
Properties
- A feasible solution always exists when the problem is balanced (for example xᵢⱼ = aᵢbⱼ/Σaᵢ).
- Only m + n − 1 constraints are independent, so a basic feasible solution has m + n − 1 basic cells; fewer means degeneracy.
- The constraint matrix is totally unimodular, so integer supplies and demands give integer optimal shipments.
- Initial solutions: North-West corner, least cost, Vogel's approximation; optimality: MODI (u-v) or stepping-stone method.
Conclusion
The transportation problem is an LPP with m × n variables and m + n equality constraints whose structure makes it solvable by tabular methods.
Examples and data to cite
- Shipping goods from plants (sources with supplies) to depots or markets (sinks with demands) at minimum cost is the standard application.
- The assignment problem is the special case with m = n and all aᵢ = bⱼ = 1.
Facts to remember
- Balanced condition Σaᵢ = Σbⱼ.
- Number of basic variables = m + n − 1.
- Total unimodularity gives integer solutions.
- Dummy rows or columns handle unbalanced problems.