Section 6.4 Summary of Chapter 6
We introduce the Transportion Problem: given \(n\) “warehouses” and \(m\) “markets”, each with \(W_i\) supply and \(M_j\) demand respectively, then given \(c_{ij}\text{,}\) the cost to ship from warehouse \(i\) to market \(j\text{,}\) to find the shipping quantities \(x_{ij}\) which satisfy all the warehouse and market constraints. When \(\displaystyle \sum_{i=1}^n W_i=\sum_{j=1}^m M_j\text{,}\) we call this problem balanced.
This can be captured with a transportation tableau:
| \(c_{11}\) | \(c_{12}\) | \(\cdots\) | \(c_{1m}\) | \(W_1 \) | |
| \(c_{21}\) | \(c_{22}\) | \(\cdots\) | \(c_{2m}\) | \(W_2 \) | |
| \(\vdots\) | \(\vdots\) | \(\ddots\) | \(\cdots\) | \(\cdots \) | |
| \(c_{n1}\) | \(c_{n2}\) | \(\cdots\) | \(c_{nm}\) | \(W_n \) | |
| \(M_1 \) | \(M_2 \) | \(\cdots \) | \(M_m\) | \(\displaystyle \sum_{i=1}^n W_i = \sum_{j=1}^m M_j\) |
Note that if we we to consider the inherent system of equations:
\begin{align*}
\sum_{j=1}^m x_{ij} \amp = W_i \\
\sum_{i=1}^n x_{ij} \amp = M_j
\end{align*}
and the fact that \(\displaystyle \sum_{i=1}^n W_i=\sum_{j=1}^m M_j\text{,}\) that the associated augmented matrix would have rank \(n+m-1\) and thus at most \(n+m-1\) of the \(x_{ij}\) need be non-zero for a feasible or optimal solution. A selection of these variables will be considered the basis of a solution, and is equivalent to the basis variables from Chapter 2.
We then introduce the Vogel Advanced Start Method (VAM) Definition 6.1.4 to heuristically pick a “good” feasible solution. The essential premise is that,we take each warehouse and market, and consider the difference between the cheapest and second cheapest options for that row/column. Since we want to minimize cost, we prioritize warehouses/markets where making the second best choice would incur a larger cost penalty than the best choice, and choose the cheapest option for those row/columns. We then readjust and repeat until we obtain a feasible solution.
We then proceed with the Transportation Algorithm Definition 6.2.3. The general idea is that we assign an \(a_i\) to each row and \(b_j\) for each column so that \(c_{ij}=a_i+b_j\) for each \(x_{ij}\) in the basis. Then, we reduce each \(c_{ij}\) by \(a_i+b_j\text{.}\) We then see if any entries are negative.
Note that for the current basis, the cost of shipping is \(\displaystyle \sum_{i=1}^n\sum_{j=1}^m c_{ij}x_{ij}\text{,}\) but since \(c_{ij}=0\) for \(x_{ij}\) not in the basis, and since \(\displaystyle \sum_{j=1}^m x_{ij}=W_i, \sum_{i=1}^n x_{ij}=M_j\text{,}\) we have that \(\displaystyle \sum_{i=1}^n\sum_{j=1}^m c_{ij}x_{ij} = \sum_{i=1}^n a_iW_i+\sum_{j=1}^m b_jM_j\text{,}\) so shifting the shipping to an entry where \(c_{ij}< a_i+b_j\) would lower the total shipping cost. We then outline a cycle consisting of new basis elements and shifting the shipping around to preserve the warehouse and market constraints, addting the negative entry to the basis and removing an entry with no shipping from the basis. Note that it is possible for this shift to be zero, yet changing the basis, equivalent to a degenerate piviot from Section 2.3. We repeat this process until there are no longer negative entries.
Finally, we consider the Assignment Problem and the Hungarian Algorithm Definition 6.3.5. The assignment problem can be thought of as a transportation problem where each warehouse and market have supply and demand 1. But since this is greatly simplified, we should expect a simpler algorithm. We note that we may add and subtract \(k\) from any row or column without changing the optimal assignment, since this is equivalent to picking originally and then giving/taking \(k\) back afterwards. We may also multiply all entries by the same value and preserve the optimal assignment by a similar argument. So we may adjust the tableau to only have non-negative integer entries, and then subtract the smallest value from each row, then each column.
If there is a permutation set of zeroes, a collection of \(n\) zeroes no two of which share a row or column, then these clearly represent an optimal assignment. If non exist, we may rearrange the tableau by drawing a minimum number of lines through each zero. We then take the smallest uncovered entry and subtract that from each uncovered row and add it to each covered column. Equivalently we subtract this value from each uncovered entry and add it to each intersection. We then repeat until we find a permutation set of zeroes.
