7.1 The transportation problem
There are \(m\) sources with supplies \(s_i\), \(n\) destinations with demands \(d_j\), and a cost \(c_{ij}\) per unit shipped from \(i\) to \(j\). With \(x_{ij}\) the amount shipped, \begin {gather*} \text {minimise } \sum _{i,j}c_{ij}x_{ij} \\ \text {subject to}\quad \sum _jx_{ij} = s_i \ (i = 1, \ldots , m), \quad \sum _ix_{ij} = d_j \ (j = 1, \ldots , n), \quad x \geq 0 . \end {gather*} The problem is balanced if \(\sum s_i = \sum d_j\), which is necessary for feasibility with equalities and also sufficient (ship \(x_{ij} = s_id_j/\sum d\)). An unbalanced problem is balanced by a dummy destination (or source) absorbing the excess at zero cost, or at the cost of unmet demand.
Proposition 7.1.1. The \(m + n\) equality constraints of a balanced transportation problem have rank \(m + n - 1\). Hence every BFS has at most \(m + n - 1\) positive entries, and a set of \(m + n - 1\) cells is a basis if and only if it contains no cycle, that is, it forms a spanning tree of the bipartite graph of sources and destinations.
Proof. The sum of the row constraints minus the sum of the column constraints is \(0 = \sum s_i - \sum d_j\), so the rows are dependent and the rank is at most \(m + n - 1\). Deleting the last column constraint leaves rows that are independent: the columns for cells \((i, n)\), \(i \leq m\), and \((1, j)\), \(j < n\), form an identity-like triangular submatrix. A cycle of cells \((i_1, j_1), (i_1, j_2), (i_2, j_2), \ldots \) gives a dependence among their columns, with alternating signs; conversely \(m + n - 1\) cells without a cycle form a tree, which can be solved leaf by leaf, so its columns are independent. □
Example 7.1.2. Three sources with supplies \(7\), \(9\), \(18\) serve four destinations with demands \(5\), \(8\), \(7\), \(14\); the costs are
| \(D_1\) | \(D_2\) | \(D_3\) | \(D_4\) | supply | |
| \(S_1\) | \(19\) | \(30\) | \(50\) | \(10\) | \(7\) |
| \(S_2\) | \(70\) | \(30\) | \(40\) | \(60\) | \(9\) |
| \(S_3\) | \(40\) | \(8\) | \(70\) | \(20\) | \(18\) |
| demand | \(5\) | \(8\) | \(7\) | \(14\) | \(34\) |
It is balanced, and a BFS has at most \(3 + 4 - 1 = 6\) positive cells. The optimal plan (Software 7.6.1, Figure 6) costs \(743\).
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.