Formulating Transportation Problems as LPs

A transportation problem is a special LP for shipping a single commodity from $m$ supply sources to $n$ demand destinations at minimum total cost. The data are:

• $s_i$ = supply available at source $i$, for $i=1,\ldots,m$
• $d_j$ = demand at destination $j$, for $j=1,\ldots,n$
• $c_{ij}$ = cost per unit shipped from source $i$ to destination $j$

We introduce one decision variable for each (source, destination) pair:

$$x_{ij}=\text{units shipped from source }i\text{ to destination }j.$$

A problem with $m$ sources and $n$ destinations therefore has $mn$ decision variables.

The objective is to minimize total shipping cost across every route:

$$\min\;\sum_{i=1}^m\sum_{j=1}^n c_{ij}\,x_{ij}.$$

For a small problem with $m=2$ sources and $n=3$ destinations, the objective expands to

$$\min\;c_{11}x_{11}+c_{12}x_{12}+c_{13}x_{13}+c_{21}x_{21}+c_{22}x_{22}+c_{23}x_{23}.$$