Transportation problem

From Glossary

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:

\min & \multicolumn{3}{l}{\sum\limits_{(i,j) \in S \times T} c_{i,j} x_{i,j}} \\ \\
<pre>& \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.

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.

Personal tools