Transportation Problem

306. Transportation Problem

A classical LP: ship supply from $𝑚$ sources to $𝑛$ destinations at minimum cost.

306.1. Formulation

Decision variable $𝑥_{𝑖 𝑗}$ = units shipped from source $𝑖$ to destination $𝑗$ .

min \sum_{𝑖 = 1}^{𝑚} \sum_{𝑗 = 1}^{𝑛} 𝑐_{𝑖 𝑗} 𝑥_{𝑖 𝑗}

subject to:

\sum_{𝑗} 𝑥_{𝑖 𝑗} = 𝑠_{𝑖}, 𝑖 = 1, \dots, 𝑚 (supply at source 𝑖 = 𝑠_{𝑖})

\sum_{𝑖} 𝑥_{𝑖 𝑗} = 𝑑_{𝑗}, 𝑗 = 1, \dots, 𝑛 (demand at destination 𝑗 = 𝑑_{𝑗})

𝑥_{𝑖 𝑗} \geq 0

Balanced: $\sum 𝑠_{𝑖} = \sum 𝑑_{𝑗}$ . If unbalanced, add a dummy source / sink.

306.2. Structure

$𝑚 𝑛$ decision variables, $𝑚 + 𝑛$ equality constraints (one redundant) → $𝑚 + 𝑛 - 1$ 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

306.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; $𝑂 ({(𝑚 + 𝑛)}^{2})$ per pivot vs $𝑂 ({(𝑚 𝑛)}^{2})$ for general

For large instances: just use network simplex.

306.4. Special cases

Assignment problem — $𝑚 = 𝑛$ , all $𝑠_{𝑖} = 𝑑_{𝑗} = 1$ , $𝑥 \in {0, 1}$
Transshipment — allow intermediate nodes
MCNF — generalization with arc capacities (here)

306.5. See also