A Transportation problem and VAM

Exploration 6.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.

Definition 6.1.2.

A transportation problem where the total demand and the total supply are the same is a balanced transportation problem.

Activity 6.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)

Consider the transportation Problem described in Exploration 6.1.1, and consider the linear equations

\begin{equation*} \sum x_{i\ell} = w_i, \sum x_{kj} = m_j. \end{equation*}

Set up an augmented matrix representing this system and solve it. What is the rank of this matrix? Describe the set of solutions to this system?

(b)

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

\begin{equation*} \sum x_{i\ell} = w_i, \sum x_{kj} = m_j. \end{equation*}

Since $\displaystyle \sum w_i = \sum m_j\text{,}$ how many of the $x_{ij}$ are needed to 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? What happened in part (a)?

(c)

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?

(d)

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?

(e)

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$

(f)

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?

(g)

Finish moving the goods from warehouses to markets.

(h)

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?

(i)

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)?

Definition 6.1.4.

To summarize 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.

	\(1\)	\(1\)	\(1\)
\(1\)	\(2\)	\(1\)	\(5\)	\(70 \)
\(2\)	\(5\)	\(3\)	\(6\)	\(20 \)
\(1\)	\(1\)	\(2\)	\(8\)	\(10 \)
	\(40 \)	\(40 \)	\(20\)

	\(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\)

	\(?\)	\(?\)	\(?\)
\(?\)	\(2\)	\(1\)	\(5\)	\(70 \)
\(\)NA	\(5\)	\(\ec{3}^{20}\)	\(6\)	\(0 \)
\(?\)	\(1\)	\(2\)	\(8\)	\(10 \)
	\(40 \)	\(20 \)	\(20\)

	\(?\)	\(?\)	\(?\)
\(?\)	\(2\)	\(1\)	\(\ec{5}\)	\(70 \)
\(\)NA	\(5\)	\(\ec{3}^{20}\)	\(6\)	\(0 \)
\(?\)	\(1\)	\(2\)	\(8\)	\(10 \)
	\(40 \)	\(20 \)	\(20\)

Linear Optimization: A Geometric Inquiry Course

Section 6.1 A Transportation problem and VAM