We introduce the transportation problem, consider its connection to linear optimization, and show an algorithm that produces a (maybe not optimal) solution.
Suppose we have a company moving goods (lets say widgets) from 3 different warehouses to 3 different markets. The cost of shipping from warehouses to markets is listed below, along with the demand from each market and the supply available at each warehouse:
Just eyeballing this, can you come up with a heuristic guess as to an optimal, or at least “good” shipping schedule? How did you come up with this and what did you have to consider?
Let \(x_{ij}\) denote the the tons of goods shipped from warehouse \(i\) to market \(j\text{.}\) Write an (in)equality for the quantity of goods shipped from Warehouse 1 in terms of the \(x_{ij}\text{.}\)
While we could solve this transportation by the Simplex Algorithm, it would be painfully tedious to do. We develop an algorithm to simplify this process.
We now generalize to a balanced transportation problem with \(n\) warehouses and \(m\) markets with supplies \(w_i\) and demands \(m_j\text{.}\) Note that we have linear equations
Imagine an augmented matrix with the coefficients of the \(x_{ij}\) on one side and the supplies/demand of the other. What is an upper bound of the rank of this matrix? Then consider that \(\displaystyle \sum w_i = \sum m_j\text{.}\) What does this say about the (in)dependence of the rows? What then must the rank be? What happened in part \(\textbf{(a)}\text{?}\)
Ideally we would always want to move everything with the cheapest available option. It’s not hard to see that in most cases, like this one, this isn’t actually possible. What do these numbers we computed measure? How can they help us decide how to move goods?
Note that Warehouse 2 has all their supply exhausted, and shipping from there is no longer an option. What are the differences between the lowest costs and second lowest costs in each row/column?
We begin with \(m\) sources and \(n\) sinks, each with a supply or demand respectively. We associate each row of the transportation tableau with a source, each column with a sink, and each entry \(c_{ij}\) with the cost of shipping from source \(i\) to sink \(j\text{.}\)
We pick the row/column with the largest difference (so long as the associated supply/demand is positive), and the smallest entry in the row/column, \(c_{ij}\text{.}\) By convention we circle this entry.
We “ship” quantity from source \(i\) to sink \(j\text{,}\) recording this quantity as a superscript in the numerator and adjusting the supply for source \(i\) and demand for sink \(j\) appropriately.
If all source/sinks are exhausted and we have not yet circled \(m+n-1\) entries, we circle any entries in the last row/column we’ve examined, noting that the quantities “shipped” for these entries is zero.