We introduce the transportation problem, consider it’s connection to linear optimization, and show an algorithm that produces a (maybe not optimal) solution.
Exploration6.1.1.
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:
Market 1
Market 2
Market 3
Warehouse 1
$2/ton
$1/ton
$5/ton
70 tons
Warehouse 2
$5/ton
$3/ton
$6/ton
20 tons
Warehouse 3
$1/ton
$2/ton
$8/ton
10 tons
40 tons
40 tons
20 tons
100 tons
We want to ship the goods from the warehouses to the markets in a way that minimizes costs.
(a)
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?
(b)
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{.}\)
(c)
Write an (in)equality for the quantity of goods shipped to Market 2 in terms of the \(x_{ij}\text{.}\)
(d)
Write a (possibly noncanonical) linear minimization problem that minimizes the cost to ship these goods.
Definition6.1.2.
A transportation problem where the total demand and the total supply are the same is a balanced transportation problem.
Activity6.1.3.
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.
(a)
Suppose we had \(n\) warehouses and \(m\) markets with supplies \(w_i\) and demands \(m_j\text{.}\) We have linear equations
Since \(\displaystyle \sum w_i = \sum m_j\text{,}\) what is the maximum number of \(x_{ij}\) that can be non-zero for a basic solution?
Hint.
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?
(b)
We first mark the difference between the lowest two values in each row/column:
\(1\)
\(1\)
\(1\)
\(1\)
\(2\)
\(1\)
\(5\)
\(70 \)
\(2\)
\(5\)
\(3\)
\(6\)
\(20 \)
\(1\)
\(1\)
\(2\)
\(8\)
\(10 \)
\(40 \)
\(40 \)
\(20\)
A table like this is called a transportation tableau.
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?
(c)
We select the row or column with the highest difference and use the smallest entry in said row/column to move as much of the goods as we can:
\(1\)
\(1\)
\(1\)
\(1\)
\(2\)
\(1\)
\(5\)
\(70 \)
\(2\)
\(5\)
\(\ec{3}\)
\(6\)
\(20 \)
\(1\)
\(1\)
\(2\)
\(8\)
\(10 \)
\(40 \)
\(40 \)
\(20\)
\(1\)
\(1\)
\(1\)
\(1\)
\(2\)
\(1\)
\(5\)
\(70 \)
\(2\)
\(5\)
\(\ec{3}^{20}\)
\(6\)
\(0 \)
\(1\)
\(1\)
\(2\)
\(8\)
\(10 \)
\(40 \)
\(20 \)
\(20\)
Would it make sense to move any more goods from warehouse 2? How should we decide how to move goods next?
(d)
Now 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?
\(?\)
\(?\)
\(?\)
\(?\)
\(2\)
\(1\)
\(5\)
\(70 \)
\(\)NA
\(5\)
\(\ec{3}^{20}\)
\(6\)
\(0 \)
\(?\)
\(1\)
\(2\)
\(8\)
\(10 \)
\(40 \)
\(20 \)
\(20\)
(e)
The next highest difference is for Market 3:
\(?\)
\(?\)
\(?\)
\(?\)
\(2\)
\(1\)
\(\ec{5}\)
\(70 \)
\(\)NA
\(5\)
\(\ec{3}^{20}\)
\(6\)
\(0 \)
\(?\)
\(1\)
\(2\)
\(8\)
\(10 \)
\(40 \)
\(20 \)
\(20\)
\(?\)
\(?\)
\(\)NA
\(?\)
\(2\)
\(1\)
\(\ec{5}^{20}\)
\(50 \)
\(\)NA
\(5\)
\(\ec{3}^{20}\)
\(6\)
\(0 \)
\(?\)
\(1\)
\(2\)
\(8\)
\(10 \)
\(40 \)
\(20 \)
\(0\)
Does it make sense to continue to move goods to Market 3?
What should be the next choice of warehouse/market?
(f)
Finish moving the goods from warehouses to markets.
(g)
Consider the final transportation tableau:
\(\)NA
\(\)NA
\(\)NA
\(\)NA
\(\ec{2}^{30}\)
\(\ec{1}^{20}\)
\(\ec{5}^{20}\)
\(0 \)
\(\)NA
\(5\)
\(\ec{3}^{20}\)
\(6\)
\(0 \)
\(\)NA
\(\ec{1}^{10}\)
\(2\)
\(8\)
\(0 \)
\(0 \)
\(0 \)
\(0\)
Verify that this is a feasible solution to the original transportation problem. Do you think it is optimal?
(h)
Out of the nine possible warehouse/market pairs, how many have actual shipments between them? How does that compare to what we found in (a)?
Definition6.1.4.
To summarise the Vogel Advanced-Start Method or VAM method of producing a feasible solution to the transportation problem is outlined as follows.
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{.}\)
For each row and column, we record the difference between the lowest two values.
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.
We ignore any source/sink with 0 supply/demand and repeat 2-4.
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.
Once \(m+n-1\) entries are circled and all supply/demand is exhausted, we terminate. The circled entries are called the basis of the tableau.
