# Transportation problem

Jump to: navigation, search

Find a flow of least cost that ships from supply sources to consumer destinations. This is a bipartite network, $LaTeX: N = [S*T, A]$, where $LaTeX: S$ is the set of sources, $LaTeX: T$ is the set of destinations, and $LaTeX: A$ is the set of arcs. In the standard form, $LaTeX: N$ is bi-complete (A contains all arcs from $LaTeX: S$ to $LaTeX: T$), but in practice networks tend to be sparsely linked. Let $LaTeX: c(i, j)$ be the unit cost of flow from $LaTeX: i \in S$ to $LaTeX: j \in T,$ $LaTeX: s(i)$ = supply at i-th source, and $LaTeX: d(j)$ = demand at j-th destination. Then, the problem is the linear program:

$LaTeX: \begin{array}{rrcl} \min & \multicolumn{3}{l}{\sum\limits_{(i,j) \in S \times T} c_{i,j} x_{i,j}} \\ \\

& \sum\limits_{j \in T} x_{i,j} & \le & s_i \mbox{ for all } i \in S, \\ & \sum\limits_{i \in S} x_{i,j} & \ge & d_j \mbox{ for all } j \in T, \\ & x & \ge & 0.

\end{array}$

The decision variables $LaTeX: (x)$ are called flows, and the two classes of constraints are called supply limits and demand requirements, resp. (Some authors use equality constraints, rather than than the inequalities shown.) An extension is the capacitated transportation problem, where the flows have bounds: $LaTeX: \textstyle x \le U.$