The Transportation Algorithm

Section 6.2 The Transportation Algorithm

We show how we can take a feasible transportation solution (say from Section 6.1), and from there produce an optimal solution.

Exploration 6.2.1.

Consider a transportation tableau:


$\ec{5}^{20}$	$\ec{5}^{30}$	0
$\ec{8}^{10}$	$\eb{5}^{0}$	0
0	0

The box here denotes that the bottom right 5 isn’t currently being used but likely should be.

(a)

It is clear that we should shift some of warehouse 2’s shipments to market 2 to reduce costs. Why isn’t this a valid transportation tableau?


	$\ec{5}^{20}$	$\ec{5}^{30}$
	$\ec{8}^{0}$	$\eb{5}^{10}$

(b)

How should we adjust these values to have a valid tableau?


	$\ec{5}^{?}$	$\ec{5}^{?}$
	$\ec{8}^{0}$	$\eb{5}^{10}$

(c)

How about this one?


$\ec{*}^{13}$	$\ec{*}^{15}$	?	?	0
$\ec{*}^{7}$	?	$\ec{*}^{12}$	?	0
?	$\ec{*}^{5}$	?	$\eb{*}^0$	0
?	?	?	?	0
?	?	$\ec{*}^9$	$\ec{*}^6 $	0
0	0	0	0

Activity 6.2.2.

Recall the transportation tableau obtained in Activity 6.1.3:

	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$

Note that this tableau corresponds to a basic feasible solution for the original minimization problem.

(a)

If this solution is not optimal, what should the next step be?

Pick a variable to exit the basis which increases the objective function and make the smallest change.
Pick a variable to exit the basis which decreases the objective function and make the smallest change.
Pick a variable to exit the basis which increases the objective function and make the biggest change.
Pick a variable to exit the basis which decreases the objective function and make the biggest change.

(b)

Select row values $a_i$ and column values $b_j$ so that each circled value $c_{ij}$ is the sum of row and column values $a_i+b_j\text{.}$

(We can think of these as analogous to the shadow costs associated with the warehouse/market bounds)

	$b_1$	$b_2$	$b_3$
$a_1$	$\ec{2}^{30}$	$\ec{1}^{20}$	$\ec{5}^{20}$
$a_2$	$5$	$\ec{3}^{20}$	$6$
$a_3$	$\ec{1}^{10}$	$2$	$8$

(c)

Replace each entry of the tableau $c_{ij}$ with $c_{ij}-a_i-b_j\text{.}$ What does this measure? What does it mean if each entry is non-negative?

(d)

Pick a $c_{ij}\lt 0$

	$b_1$	$b_2$	$b_3$
$a_1$	$\ec{0}^{30}$	$\ec{0}^{20}$	$\ec{0}^{20}$
$a_2$	$?$	$\ec{0}^{20}$	$\eb{-?}$
$a_3$	$\ec{?}^{10}$	$?$	$?$

(e)

Pick circled entries $c_{k \ell}$ so that they with the boxed $c_{ij}$ form a cycle, that is each of these entries shares a row with exactly one another of the entries, and a column with another of the entries.

(f)

Based on the discussion in (a), which entry should transfer their shipments to $c_{23}\text{?}$

$c_{11}\text{.}$
$c_{12}\text{.}$
$c_{13}\text{.}$
$c_{22}\text{.}$
$c_{31}\text{.}$

How do the other entries in the cycle adjust? (There may be more than one valid choice.)

(g)

Remove the basis entry which is no longer being used, and recompute the $a_i, b_j$ with the new basis.

	$b_1$	$b_2$	$b_3$
$a_1$	$?$	$?$	$?$
$a_2$	$?$	$?$	$?$
$a_3$	$?$	$?$	$?$

(h)

Verify that none of the entries are non negative. Why do we now terminate?

We then replace the entries with the original entries

	$b_1$	$b_2$	$b_3$
$a_1$	$2^{30}$	$1^{40}$	$5^0$
$a_2$	$5^0$	$3^0$	$6^{20}$
$a_3$	$1^{10}$	$2^0$	$8^0$

(i)

Use Sage to confirm the solution:

Definition 6.2.3.

To summarize, the Transportation Algorithm is as follows:

We begin with a feasible transportation tableau, probably via VAM Definition 6.1.4.

We then associate with each row an unknown $a_i$ and each column a $b_j\text{.}$
We (by convention) let $b_1=0$ and select values $a_i, b_j$ so that for each basis entry $c_{ij}$ we have that $c_{ij} = a_i+b_j\text{.}$
Replace every entry $c_{ij}$ with $c_{ij}-a_i-b_j\text{.}$
If there is a negative entry $c_{k\ell}$ box this entry and select basis entries so that they, along with the boxed entry, form a cycle.

If each entry is non-negative, GOTO 6.
Shift shipments appropriately along the cycle so that $c_{k\ell}$ has a non-negative shipping quantity, and one of the selected basis entries has a zero shipping quantity.

Then GOTO 2.
Replace each cost entry with the costs from step 1 and terminate.

Activity 6.2.4.

Consider the Transportation Algorithm Definition 6.2.3. Recall that the objective function for the transportation problem is $f(\x)=\displaystyle \sum x_{ij}c_{ij}\text{,}$ and that the entries of the tableau produced in Step 3 are $c_{ij}-a_i-b_j\text{.}$

(a)

Show that in step 5 the newly produced solution has a strictly lower objective value.

(b)

If instead of step 4, we selected an entry with a zero value, what would be true about the resulting new solution?

The new solution has smaller objective value.
The new solution has greater objective value.
The new solution has the same objective value.
The relation of the value of the new solution to the original cannot be determined in general.

Subsection 6.2.1 Unbalanced Transportation Problems

Activity 6.2.5.

We now consider the case of unbalanced transportation problems, where the demand and supply are unequal.

(a)

Suppose we had the following transportation problem:

	Market 1	Market 2	Market 3
Warehouse 1	$5/ton	$3/ton	$1/ton	35 tons
Warehouse 2	$6/ton	$2/ton	$5/ton	45 tons
Warehouse 3	$4/ton	$2/ton	$1/ton	15 tons
	30 tons	20 tons	40 tons

Suppose we satisfy all the demand in a way that minimizes costs. What would be the remaining result?

(b)

Suppose we “ship” the excess supply to a phatom market:

	Market 1	Market 2	Market 3	“Market”
Warehouse 1	$5/ton	$3/ton	$1/ton	?	35 tons
Warehouse 2	$6/ton	$2/ton	$5/ton	?	45 tons
Warehouse 3	$4/ton	$2/ton	$1/ton	?	15 tons
	30 tons	20 tons	40 tons	?

How much is shipped to the “Market”? How much does it cost to “ship” from each warehouse to “Market”?

(c)

Suppose we had the following transportation problem:

	Market 1	Market 2	Market 3
Warehouse 1	$5/ton	$3/ton	$1/ton	35 tons
Warehouse 2	$6/ton	$2/ton	$5/ton	45 tons
Warehouse 3	$4/ton	$2/ton	$1/ton	15 tons
	30 tons	50 tons	40 tons

Suppose we exhaust all the supply in a way that minimizes costs. What would be the remaining result?

(d)

Suppose we have a phantom “Warehouse” that “filled” the outstanding demand.

	Market 1	Market 2	Market 3
Warehouse 1	$5/ton	$3/ton	$1/ton	35 tons
Warehouse 2	$6/ton	$2/ton	$5/ton	45 tons
Warehouse 3	$4/ton	$2/ton	$1/ton	15 tons
“Warehouse”	?	?	?	?
	30 tons	50 tons	40 tons

How much additional “supply” is needed? How much would it cost to ship this “supply” from “Warehouse” to the markets?

(e)

Describe a general procedure for solving unbalanced transportation problems.

Prev Top Next


\(\ec{5}^{20}\)	\(\ec{5}^{30}\)	0
\(\ec{8}^{10}\)	\(\eb{5}^{0}\)	0
0	0


	\(\ec{5}^{20}\)	\(\ec{5}^{30}\)
	\(\ec{8}^{0}\)	\(\eb{5}^{10}\)


	\(\ec{5}^{?}\)	\(\ec{5}^{?}\)
	\(\ec{8}^{0}\)	\(\eb{5}^{10}\)


\(\ec{*}^{13}\)	\(\ec{*}^{15}\)	?	?	0
\(\ec{*}^{7}\)	?	\(\ec{*}^{12}\)	?	0
?	\(\ec{*}^{5}\)	?	\(\eb{*}^0\)	0
?	?	?	?	0
?	?	\(\ec{*}^9\)	\(\ec{*}^6 \)	0
0	0	0	0

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

	\(b_1\)	\(b_2\)	\(b_3\)
\(a_1\)	\(\ec{2}^{30}\)	\(\ec{1}^{20}\)	\(\ec{5}^{20}\)
\(a_2\)	\(5\)	\(\ec{3}^{20}\)	\(6\)
\(a_3\)	\(\ec{1}^{10}\)	\(2\)	\(8\)

	\(b_1\)	\(b_2\)	\(b_3\)
\(a_1\)	\(\ec{0}^{30}\)	\(\ec{0}^{20}\)	\(\ec{0}^{20}\)
\(a_2\)	\(?\)	\(\ec{0}^{20}\)	\(\eb{-?}\)
\(a_3\)	\(\ec{?}^{10}\)	\(?\)	\(?\)

	\(b_1\)	\(b_2\)	\(b_3\)
\(a_1\)	\(?\)	\(?\)	\(?\)
\(a_2\)	\(?\)	\(?\)	\(?\)
\(a_3\)	\(?\)	\(?\)	\(?\)

	\(b_1\)	\(b_2\)	\(b_3\)
\(a_1\)	\(2^{30}\)	\(1^{40}\)	\(5^0\)
\(a_2\)	\(5^0\)	\(3^0\)	\(6^{20}\)
\(a_3\)	\(1^{10}\)	\(2^0\)	\(8^0\)