303. Transportation Problem
A classical LP: ship supply from sources to destinations at minimum cost.
303.1. Formulation
Decision variable = units shipped from source to destination .
subject to:
Balanced: . If unbalanced, add a dummy source / sink.
303.2. Structure
- decision variables, equality constraints (one redundant) → basic variables in any BFS
- Constraint matrix is totally unimodular — LP relaxation always has integer optimum (with integer supply/demand)
- Special structure → much faster than general simplex
303.3. Solution algorithms
- Northwest-corner rule — initial BFS by greedy fill from upper-left
- Vogel’s approximation method (VAM) — better initial BFS using opportunity costs
- MODI / stepping stone — improvement iterations on a BFS to optimality
- Transportation simplex — specialized simplex exploiting structure; per pivot vs for general
For large instances: just use network simplex.
303.4. Special cases
- Assignment problem — , all ,
- Transshipment — allow intermediate nodes
- MCNF — generalization with arc capacities (here)