\pdfpagewidth=8.5truein  \pdfpageheight=11truein
\hsize=5.5truein  \vsize=9truein
\pdfhorigin=1.5truein  \pdfvorigin=1truein

% MetaPost stuff
\input supp-pdf
\def\fig#1{\convertMPtoPDF{#1}{1}{1}}
\def\midfig#1{{%
	\setbox0=\hbox{\fig{#1}}%
	\dimen0=0.5\ht0%
	\advance\dimen0 by-0.3\ht\strutbox
	\lower\dimen0\box0%
}}

\edef\restoreinterlineskip{\noexpand\baselineskip=\the\baselineskip\relax\noexpand\lineskiplimit=\the\lineskiplimit\relax\noexpand\lineskip=\the\lineskip}

\long\def\boxed#1{\vbox{\offinterlineskip
	\hrule
	\hbox to \hsize{%
	\hss\vrule\hskip1em%
	\vbox{\advance\hsize by-2em \advance\hsize by-0.8pt
	\restoreinterlineskip
	\vskip1ex
	\noindent#1\par
	\vskip1ex
	}\hskip1em\vrule\hss}%
	\hrule}}

\long\def\bboxed#1{\vbox{\offinterlineskip
	\hrule
	\hbox to \hsize{%
	\hss\vrule\hskip1ex%
	\vbox{\advance\hsize by-2ex \advance\hsize by-0.8pt
	\restoreinterlineskip
	\vskip1ex
	\boxed{#1}\par
	\vskip1ex
	}\hskip1ex\vrule\hss}%
	\hrule}}

\input weirdtable  % Will's macros for my transportation tableaux

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\bf Transportation problem example, in detail}

\bigskip

\noindent Warehouses A,~B, and~C have 18,~25, and~12 units of a certain
commodity, respectively. Customers V,~W, X, Y, and~Z have respective demands of
14,~6, 8, 10, and~17 units of this commodity. The costs per unit to ship this
commodity from each warehouse to each customer are given in the table below:
$$\vbox{\offinterlineskip
\halign{\strut\enspace\hfil#\hfil\enspace&\vrule#&&\strut\enspace\hfil#\hfil\enspace\cr
&&V&W&X&Y&Z\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
A&&\$20&\$12&\$15&\$10&\$16\cr
B&&\$15&\$18&\$16&\$13&\$10\cr
C&&\$17&\$14&\$19&\$14&\$12\cr
}}$$
How can all of these demands be met from these warehouses at minimum total
cost?

\bigskip\hrule\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent We will represent a solution in the form of a $3\times5$ grid (or
{\it tableau\/}), as shown below.
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaublankrow left=\hbox{A} right= rest= , , , , .
	\tableaublankrow left=\hbox{B} right= rest= , , , , .
	\tableaublankrow left=\hbox{C} right= rest= , , , , .
\endtableau$$
The three rows of this grid correspond to the warehouses A,~B, and~C, and the
five columns correspond to the customers V,~W, X, Y, and~Z. We will write a
bold number in the lower left corner of a square (or {\it cell\/}) in this grid
to represent the number of units shipped from the corresponding warehouse to
the corresponding customer; we might call such a quantity a {\it flow}. (We
will also write other numbers in other locations in the square.)

We begin by finding an {\it initial basic feasible solution}. The purpose of
this initial basic feasible solution is to give us a starting point---just one
possible way of satisfying the demands from the warehouses. It will not be
optimal; in fact, we will not even consider the shipping costs at this point.

\medbreak

\boxed{The {\bf method to find an initial basic feasible solution} is
straightforward:

\medskip

\item{$\bullet$} Satisfy each demand one by one, from left to right.

\smallskip

\item{$\bullet$} For each demand, take units from each supply, top to bottom,
until the demand is met; but once a supply has been exhausted, it cannot be
used to satisfy later demands.

\smallskip

\item{$\bullet$} [Note: There is a special case that arises when a demand is
satisfied {\it and\/} a supply is exhausted simultaneously. See the note and
example on page~17 for details.]

}% end \boxed

\medbreak

\noindent For this problem, we form an initial basic feasible solution as
follows:

\medskip

\item{0.} For convenience, let's write the amount of each supply (i.e., each
warehouse) next to the row labels, and the amount of each demand (i.e., each
customer) next to the column labels.
$$\begintableau
	\tableauheader{\hbox{V: 14},\hbox{W: 6},\hbox{X: 8},\hbox{Y: 10},\hbox{Z: 17}}
	\tableaublankrow left=\phantom{00}\llap{\hbox{A: 18}} right= rest= , , , , .
	\tableaublankrow left=\phantom{00}\llap{\hbox{B: 25}} right= rest= , , , , .
	\tableaublankrow left=\phantom{00}\llap{\hbox{C: 12}} right= rest= , , , , .
\endtableau$$

\smallbreak

\item{1.} The first demand is~V, which demands 14~units. This demand can be
satisfied by taking 14~units from the first supply,~A. So we will do that.
$$\begintableau
	\tableauheader{\hbox{V: 14},\hbox{W: 6},\hbox{X: 8},\hbox{Y: 10},\hbox{Z: 17}}
	\tableaublankrow left=\phantom{00}\llap{\hbox{A: 18}} right= rest=14, , , , .
	\tableaublankrow left=\phantom{00}\llap{\hbox{B: 25}} right= rest= , , , , .
	\tableaublankrow left=\phantom{00}\llap{\hbox{C: 12}} right= rest= , , , , .
\endtableau$$

\smallbreak

\item{2.} The next demand is~W, which demands 6~units. Warehouse~A has 4~units
remaining (because 14 of its 18~units were previously used to satisfy the
demand of~V), so W will take those remaining 4~units from~A; this exhausts the
supply of~A. The remaining 2~units of W's demand can be satisfied by taking
2~units from the next supply,~B.
$$\begintableau
	\tableauheader{\hbox{V: 14},\hbox{W: 6},\hbox{X: 8},\hbox{Y: 10},\hbox{Z: 17}}
	\tableaublankrow left=\phantom{00}\llap{\hbox{A: 18}} right= rest=14,4, , , .
	\tableaublankrow left=\phantom{00}\llap{\hbox{B: 25}} right= rest= ,2, , , .
	\tableaublankrow left=\phantom{00}\llap{\hbox{C: 12}} right= rest= , , , , .
\endtableau$$

\smallbreak

\item{3.} The third demand is~X, which demands 8~units. Warehouse~B has
23~units remaining (after W took 2~units), so we can satisfy the demand of~X
by taking 8~units from~B.
$$\begintableau
	\tableauheader{\hbox{V: 14},\hbox{W: 6},\hbox{X: 8},\hbox{Y: 10},\hbox{Z: 17}}
	\tableaublankrow left=\phantom{00}\llap{\hbox{A: 18}} right= rest=14,4, , , .
	\tableaublankrow left=\phantom{00}\llap{\hbox{B: 25}} right= rest= ,2,8, , .
	\tableaublankrow left=\phantom{00}\llap{\hbox{C: 12}} right= rest= , , , , .
\endtableau$$

\smallbreak

\item{4.} The fourth demand,~Y, is for 10~units. We can satisfy this demand
by taking 10~units from~B.
$$\begintableau
	\tableauheader{\hbox{V: 14},\hbox{W: 6},\hbox{X: 8},\hbox{Y: 10},\hbox{Z: 17}}
	\tableaublankrow left=\phantom{00}\llap{\hbox{A: 18}} right= rest=14,4, , , .
	\tableaublankrow left=\phantom{00}\llap{\hbox{B: 25}} right= rest= ,2,8,10, .
	\tableaublankrow left=\phantom{00}\llap{\hbox{C: 12}} right= rest= , , , , .
\endtableau$$

\smallbreak

\item{5.} The last demand is~Z, which demands 17~units. The second supply,~B,
has 5~units remaining (after W took~2, X~took~8, and Y took~10), so Z~will
take those remaining 5~units from~B (after which B is exhausted), and then we
will satisfy the remaining 12~units of Z's demand by taking all 12~units from
the last supply,~C.
$$\begintableau
	\tableauheader{\hbox{V: 14},\hbox{W: 6},\hbox{X: 8},\hbox{Y: 10},\hbox{Z: 17}}
	\tableaublankrow left=\phantom{00}\llap{\hbox{A: 18}} right= rest=14,4, , , .
	\tableaublankrow left=\phantom{00}\llap{\hbox{B: 25}} right= rest= ,2,8,10,5.
	\tableaublankrow left=\phantom{00}\llap{\hbox{C: 12}} right= rest= , , , ,12.
\endtableau$$

\smallbreak

\noindent This process gives us an initial basic feasible solution. The squares
containing bold numbers here are called {\it basic\/} squares; they correspond
to basic variables in the linear programming formulation of this problem (the
LP formulation has 15~variables, one for each square). The squares not
containing bold numbers are {\it nonbasic}. Note that the basic squares form a
``stair-step'' pattern from the upper left square of the grid to the lower
right square; this should always be the case. (See the note and example on
page~17 for a discussion about a special case that occasionally arises.)

This initial solution is {\it feasible\/} because all of the demands are met,
and all of the supplies are exhausted. (Notice that the total supply is equal
to the total demand in this problem. If this is not the case, then you will
need to add a fictitious supply or a fictitious demand to make the totals
equal.) The initial solution is {\it basic\/} because the number of basic
squares is equal to the number of rows plus the number of columns minus~1
(which is $3+5-1=7$ for this problem); that is the rank of the coefficient
matrix of the LP for this problem.

\medskip

\boxed{{\bf Important:} Every solution that we get during the solution process
must be basic. In other words, the number of basic squares must always be equal
to the number of rows plus the number of columns minus~1.

\medskip

\noindent(In this problem, with a $3\times5$ grid, that means we must always
have $3+5-1=7$ basic squares. We achieved this result with our initial basic
feasible solution, but we will see where it is important to take this rule into
consideration a little later in this example---see page~15.)}

\medbreak

\noindent But there is no reason that the initial basic feasible solution
should be {\it optimal}, because we didn't consider the costs at all. The
initial basic feasible solution just gives us a starting point. It's probably a
terribly inefficient solution to the problem; it probably costs much more than
the optimal solution does. The rest of the algorithm for solving this
transportation problem consists of repeatedly {\it improving\/} the current
solution (lowering its cost) until it cannot be improved further, at which
point the solution is optimal.

\looseness=-1
A key step in this improvement process is identifying the values of the dual
variables. There are 15~variables in the primal LP, corresponding to the
squares in the grid, and representing the number of units to be shipped from
the corresponding warehouse to the corresponding customer. The primal~LP has
eight constraints: three to ensure that each supply is exhausted (these
correspond to the rows of the grid), and five to ensure that each demand is met
(these correspond to the columns of the grid). So the dual LP will have eight
variables: one for each row and one for each column. Let's call the ``row
variables'' $v_1$,~$v_2$, and~$v_3$, and let's call the ``column variables''
$w_1$~through~$w_5$. We can use complementary slackness to determine the values
of the dual variables from the values of the primal variables, which we have in
the grid. From complementary slackness, if the primal solution is optimal, then
basic primal variables should correspond to tight dual constraints, which gives
us the following:

\medskip

\boxed{{\bf Rule from complementary slackness:} For each {\bf basic} square in
the grid, the sum of the corresponding row variable and the corresponding
column variable must equal the corresponding cost.}

\medbreak

\noindent Now, in this problem we have eight dual variables (three row
variables and five column variables), but only seven basic squares, which means
that complementary slackness gives us only seven equations for these eight
unknowns. That means that we have one {\it free variable\/}; we can choose one
of the dual variables to be any value that we like, and then solve for the
remaining dual variables using the rule above. (It will always be true that
there is one more dual variable than basic squares, so there will always be one
free variable.) In practice, for simplicity, we choose the value of the first
row variable,~$v_1$, to be~0, and go from there.

Let's see how we can find the values of the dual variables for our initial
basic feasible solution. To assist us in this process, we will copy the costs
from the table given in the problem into the grid. We'll put the costs in
little postage-stamp boxes in the upper right corners of each square, like
this:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right= rest=l;14;20 l;4;12 r;;15 r;;10 r;;16.
	\tableaurow left=\hbox{B} right= rest=r;;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right= rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
\endtableau$$
We'll write the row variables on the right-hand side of each row, and we'll
write the column variables at the bottom of each column:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1 rest=l;14;20 l;4;12 r;;15 r;;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2 rest=r;;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1,w_2,w_3,w_4,w_5}
\endtableau$$

\noindent The first step in the process of finding the values of the dual
variables is to set $v_1=0$, as our free variable:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;14;20 l;4;12 r;;15 r;;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2 rest=r;;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1,w_2,w_3,w_4,w_5}
\endtableau$$

\noindent Now, consider the AV~square in this grid (that~is, the square at the
intersection of the A~row and the V~column). This is a basic square, so the
result of complementary slackness says that the sum of the corresponding row
variable~$v_1$ and the corresponding column variable~$w_1$ must equal the
corresponding cost, which is~20; so we have $v_1+w_1=20$. Since $v_1=0$, that
means that $w_1$ must be~20:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;14;20 l;4;12 r;;15 r;;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2 rest=r;;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1=20,w_2,w_3,w_4,w_5}
\endtableau$$

\noindent Next, consider the AW~square, which is also basic. Complementary
slackness, when applied to this square, says that $v_1+w_2=12$. Since $v_1=0$,
that means that $w_2=12$:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;14;20 l;4;12 r;;15 r;;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2 rest=r;;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1=20,w_2=12,w_3,w_4,w_5}
\endtableau$$

\noindent Then we can consider the BW~square. This is a basic square, so
complementary slackness gives $v_2+w_2=18$. Since we now know that $w_2=12$,
this means that $v_2=6$:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;14;20 l;4;12 r;;15 r;;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2=6 rest=r;;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1=20,w_2=12,w_3,w_4,w_5}
\endtableau$$

\noindent Next, consider the BX~square. Because this square is basic, we get
the equation $v_2+w_3=16$. Since $v_2=6$, we see that $w_3=10$:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;14;20 l;4;12 r;;15 r;;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2=6 rest=r;;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1=20,w_2=12,w_3=10,w_4,w_5}
\endtableau$$

\noindent From the BY~square, which is basic, we get $v_2+w_4=13$; since
$v_2=6$, we get $w_4=7$:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;14;20 l;4;12 r;;15 r;;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2=6 rest=r;;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1=20,w_2=12,w_3=10,w_4=7,w_5}
\endtableau$$

\noindent From the BZ~square, which is basic, we get $v_2+w_5=10$; since
$v_2=6$, we get $w_5=4$:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;14;20 l;4;12 r;;15 r;;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2=6 rest=r;;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1=20,w_2=12,w_3=10,w_4=7,w_5=4}
\endtableau$$

\noindent Lastly, from the final basic square,~CZ, we get $v_3+w_5=12$; since
$w_5=4$, we get $v_3=8$:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;14;20 l;4;12 r;;15 r;;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2=6 rest=r;;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3=8 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1=20,w_2=12,w_3=10,w_4=7,w_5=4}
\endtableau$$

\goodbreak

Once we have all of the values of the dual variables, we compute {\it test
values\/} for all of the {\it nonbasic\/} squares in the grid.

\medskip

\boxed{{\bf Computing test values:} A test value (for a {\bf nonbasic} square
only) is equal to the cost of that square, minus the value of the corresponding
row variable, minus the value of the corresponding column variable.}

\medbreak

\noindent The meaning of a test value is as follows: A nonbasic square is a
link from a supply to a demand that the current solution is not using. If the
test value of that square is {\it negative}, then we can improve our current
solution (to get a solution of lower cost) by using that link.

We will write test values in the lower right corners of nonbasic squares, and
to further distinguish them from the values in the basic squares we will color
them red. Note that test values have very different meanings from the values in
basic squares! The values in basic squares (written in the lower left corner)
represent {\it flows\/} from supplies to demands; they are quantities that are
being shipped from the corresponding supply to the corresponding demand. The
values in nonbasic squares (written in the lower right corner) are test values
that tell us whether it would be advantageous to change our solution to use the
corresponding link from a supply to a demand.

Let's compute the test values for the nonbasic squares in this example. The
test values can be computed in any order; let's begin in the A~row and work
down. The first nonbasic square is the AX~square. The test value for the
AX~square is the cost minus the row variable minus the column variable, which
is $15-0-10=5$:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;14;20 l;4;12 r;5;15 r;;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2=6 rest=r;;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3=8 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1=20,w_2=12,w_3=10,w_4=7,w_5=4}
\endtableau$$

\noindent The test value for the next nonbasic square, the AY~square, is
$10-0-7=3$:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;14;20 l;4;12 r;5;15 r;3;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2=6 rest=r;;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3=8 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1=20,w_2=12,w_3=10,w_4=7,w_5=4}
\endtableau$$

\noindent The test value for the AZ~square is $16-0-4=12$:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;14;20 l;4;12 r;5;15 r;3;10 r;12;16.
	\tableaurow left=\hbox{B} right=v_2=6 rest=r;;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3=8 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1=20,w_2=12,w_3=10,w_4=7,w_5=4}
\endtableau$$

\noindent Starting the next row, the test value for the BV~square is
$15-6-20=-11$:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;14;20 l;4;12 r;5;15 r;3;10 r;12;16.
	\tableaurow left=\hbox{B} right=v_2=6 rest=r;-11;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3=8 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1=20,w_2=12,w_3=10,w_4=7,w_5=4}
\endtableau$$

\noindent That was the only nonbasic square in the B~row, so we'll continue to
the C~row. The test value for the CV~square is $17-8-20=-11$:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;14;20 l;4;12 r;5;15 r;3;10 r;12;16.
	\tableaurow left=\hbox{B} right=v_2=6 rest=r;-11;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3=8 rest=r;-11;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1=20,w_2=12,w_3=10,w_4=7,w_5=4}
\endtableau$$

\noindent The test value for the CW~square is $14-8-12=-6$:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;14;20 l;4;12 r;5;15 r;3;10 r;12;16.
	\tableaurow left=\hbox{B} right=v_2=6 rest=r;-11;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3=8 rest=r;-11;17 r;-6;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1=20,w_2=12,w_3=10,w_4=7,w_5=4}
\endtableau$$

\noindent The test value for the CX~square is $19-8-10=1$:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;14;20 l;4;12 r;5;15 r;3;10 r;12;16.
	\tableaurow left=\hbox{B} right=v_2=6 rest=r;-11;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3=8 rest=r;-11;17 r;-6;14 r;1;19 r;;14 l;12;12.
	\tableaufooter{w_1=20,w_2=12,w_3=10,w_4=7,w_5=4}
\endtableau$$

\noindent And, finally, the test value for the CY~square is $14-8-7=-1$:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;14;20 l;4;12 r;5;15 r;3;10 r;12;16.
	\tableaurow left=\hbox{B} right=v_2=6 rest=r;-11;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3=8 rest=r;-11;17 r;-6;14 r;1;19 r;-1;14 l;12;12.
	\tableaufooter{w_1=20,w_2=12,w_3=10,w_4=7,w_5=4}
\endtableau$$

\goodbreak

Since there are negative test values, we know that this solution is not optimal
(which is not surprising, because we wrote down this solution without even
considering the costs). We can improve the solution by shifting the flows in
order to use one of the links that has a negative test value. As a rule of
thumb, we will choose a link that has the {\it most\/} negative test value.
Here, two nonbasic squares (BV~and~CV) tie for the most negative test value, so
we can pick one of those squares arbitrarily. Let's pick the BV~square. We will
change our solution to use that link by changing the flows in the grid; this
operation is called {\it pivoting\/} (it is equivalent to pivoting in the
simplex algorithm).

\medskip

\boxed{{\bf Choosing a pivot:} If there is a negative test value in the grid,
then the solution is not optimal. In this case, choose the most negative test
value as the pivot location. If there is a tie, break the tie arbitrarily.}

\medskip

\noindent We want to change our solution to use the BV~link (i.e., to ship some
units from the supply~B to the demand~V). We don't know yet how many units we
should send along this link, so let's call that unknown quantity~$t$.
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaublankrow left=\hbox{A} right= rest= , , , , .
	\tableaublankrow left=\hbox{B} right= rest=t, , , , .
	\tableaublankrow left=\hbox{C} right= rest= , , , , .
\endtableau$$

\noindent Now, consider the V~column. The total demand of~V is~14, which means
that the total of the flows in that column should be~14. The current
solution satisfies that demand by shipping 14~units from A to~V. But now we are
going to ship $t$~units from B to~V, so in order to maintain the same column
sum we must {\it subtract\/} $t$~units from the flow in the AV~square, giving
us a flow of $14-t$ there:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaublankrow left=\hbox{A} right= rest=14-t, , , , .
	\tableaublankrow left=\hbox{B} right= rest=t, , , , .
	\tableaublankrow left=\hbox{C} right= rest= , , , , .
\endtableau$$

\noindent Next, consider the A~row. The total supply of~A is~18, which means
that the total of the flows in that row should be~18. The current solution
exhausts that supply by shipping 14~units from A to~V and 4~units from A to~W.
But now we are reducing the flow in the AV~square by $t$~units, so we need to
{\it increase\/} the flow in the AW~square by $t$~units in order to maintain
the same row sum:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaublankrow left=\hbox{A} right= rest=14-t,4+t, , , .
	\tableaublankrow left=\hbox{B} right= rest=t, , , , .
	\tableaublankrow left=\hbox{C} right= rest= , , , , .
\endtableau$$

\noindent And now consider the W~column. The total demand of~W is~6, which
means that the total of the flows in that column should be~6. The current
solution satisfies that demand by shipping 4~units from A to~W and 2~units from
B to~W. But now we are going to increase the flow in the AW~square by
$t$~units, so we need to {\it subtract\/} $t$~units from the BW~square in order
to maintain the same column sum:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaublankrow left=\hbox{A} right= rest=14-t,4+t, , , .
	\tableaublankrow left=\hbox{B} right= rest=t,2-t, , , .
	\tableaublankrow left=\hbox{C} right= rest= , , , , .
\endtableau$$

\noindent Note that this last adjustment also fixed the discrepancy in the
B~row, so that the row sum in that row will remain the same: we are increasing
the flow in the BV~square by~$t$ and also reducing the flow in the BW~square
by~$t$, so the net change is zero. After these adjustments, all of the row sums
and all of the column sums remain the same as they were before, which means
that all of the demands will be satisfied and all of the supplies will be
exhausted, so we will get another feasible solution. The other flows in the
basic squares that were not adjusted will remain the same:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaublankrow left=\hbox{A} right= rest=14-t,4+t, , , .
	\tableaublankrow left=\hbox{B} right= rest=t,2-t,8,10,5.
	\tableaublankrow left=\hbox{C} right= rest= , , , ,12.
\endtableau$$

\noindent A useful way of viewing this series of adjustments is to view it as a
{\it circuit\/} in the grid representing the previous solution. The circuit
begins in the nonbasic square where we are pivoting (i.e., the BV~square), and
then travels alternately vertically and horizontally, ``landing'' only in basic
squares (AV,~AW, and~BW) and then returning to the pivot square~(BV). This
circuit is shown below, superimposed on the grid representing the previous
solution:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right= rest=l;14;20 l;4;12 r;5;15 r;3;10 r;12;16.
	\tableaurow left=\hbox{B} right= rest=r;-11;15 l;2;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right= rest=r;-11;17 r;-6;14 r;1;19 r;-1;14 l;12;12.
\endtableau
\llap{\raise0.45cm\hbox{\fig{transportation-example-1.mps}}\hskip1.55cm}$$
We can perform the necessary adjustments by identifying such a circuit (there
will be exactly one such circuit in the grid) and then alternately adding and
subtracting~$t$ from the flows in the squares going around the circuit, in
either direction, starting at the pivot square.

These adjustments give us the following tentative new grid:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaublankrow left=\hbox{A} right= rest=14-t,4+t, , , .
	\tableaublankrow left=\hbox{B} right= rest=t,2-t,8,10,5.
	\tableaublankrow left=\hbox{C} right= rest= , , , ,12.
\endtableau$$
We would like to make the value of~$t$ as large as possible, because using the
BV~link saves us money (that's what the negative test value tells us). However,
we can't make $t$ too large, because none of the flows can become negative (we
can't ship a negative number of units from a supply to a demand). So we need to
choose $t=2$ here, because one of the squares in the tentative new grid,
the BW~square, has a flow of $2-t$. When we choose $t=2$, the flow in the
BW~square becomes zero, so that square becomes nonbasic. We gain a new basic
square~(BV) and lose an old basic square~(BW), so the number of basic squares
remains the same; this is important, because the number of basic squares in
this problem should always be~7. The result is the following basic feasible
solution:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaublankrow left=\hbox{A} right= rest=12,6, , , .
	\tableaublankrow left=\hbox{B} right= rest=2, ,8,10,5.
	\tableaublankrow left=\hbox{C} right= rest= , , , ,12.
\endtableau$$
Note that the ``stair-step'' structure is gone. That's okay; that was only a
requirement for the {\it initial\/} basic feasible solution.

\goodbreak

The steps of pivoting are summarized below:

\medskip

\boxed{{\bf Pivoting:} After choosing the pivot location in the grid, perform
the following steps to pivot there.

\medskip

\item{1.} Find a {\it circuit\/} in the grid, starting at the pivot square. The
circuit must have the following properties:

\smallskip

\itemitem{--} It must begin and end at the pivot square.

\smallskip

\itemitem{--} From the pivot square, the circuit must go vertically to a basic
square, then horizontally to another basic square, then vertically to another
basic square, and so on, alternating vertical and horizontal steps, until it
returns to the pivot square. These vertical and horizontal steps can (and
usually will) jump over some squares in the grid.

\smallskip

\itemitem{--} Except for the pivot square, the vertical and horizontal steps of
the circuit must always land in basic squares.

\smallskip

\itemitem{--} The circuit cannot land in the same square more than once, except
the pivot square at the beginning and end of the circuit.

\smallskip

\item{} There will be exactly one such circuit in the grid that begins and
ends at the pivot square. There are no hard and fast rules for finding the
circuit; you will have to do some searching (and perhaps some trial-and-error)
to find it.

\smallskip

\item{2.} Form a tentative new grid by adding~$t$ to the flow of the pivot
square (which was previously zero), and then alternately subtracting and
adding~$t$ to the basic squares going around the circuit (in either direction)
to preserve all of the row sums and column sums.

\smallskip

\item{3.} Choose the largest value of~$t$ that does not make any flow negative.
Then determine the new flows by using this value of~$t$. A flow that becomes
zero will become a nonbasic square.

\smallskip

\itemitem{--} However, if more than one flow becomes zero, only one of them
will become nonbasic, in order to preserve the correct number of basic squares.
The others will become basic squares that happen to have zero flow (this is a
degenerate solution). Choose any one of the zero-flow squares to become
nonbasic, and leave the rest as basic squares with zero flow.

}

\medbreak

\noindent So now we have a new basic feasible solution. We will continue this
process (finding the values of the dual variables, computing the test values,
identifying a pivot location, and pivoting there) until we reach a point where
all of the test values are nonnegative; this means that the solution is
optimal, and we can stop. Therefore, the whole process of solving a
transportation problem goes like this:

\medskip

\bboxed{{\bf Steps for solving a transportation problem:}

\medskip

\item{1.} Form an initial basic feasible solution. See the box on page~1.

\smallskip

\item{2.} Write the costs in the grid, and set the first row variable,~$v_1$,
to~0.

\smallskip

\item{3.} Use the {\bf basic} squares and the rule from complementary slackness
to find the values of all the other dual variables (i.e., the row and column
variables). See the box on page~3.

\smallskip

\item{4.} Compute the test values for all of the {\bf nonbasic} squares. See
the box on page~6.

\smallskip

\item{5.} If all of the test values are nonnegative, then the current solution
is optimal. Stop.

\smallskip

\item{6.} Otherwise, choose the most negative test value and pivot there (by
finding a circuit and adding and subtracting~$t$). See the box on page~10.

\smallskip

\item{7.} Return to step~2 for the new solution obtained in step~6.

}

\medbreak

\noindent Let's continue with our example. We continue by adding the costs to
the upper right corners of the squares and setting $v_1=0$:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;12;20 l;6;12 r;;15 r;;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2 rest=l;2;15 r;;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1,w_2,w_3,w_4,w_5}
\endtableau$$

\noindent Now we use the rule from complementary slackness to find the values
of the remaining dual variables.

\medskip

\item{1.} The AV~square is basic, so $v_1+w_1=20$. We know $v_1=0$, so
$w_1=20$.

\smallskip

\item{2.} The AW~square is basic, so $v_1+w_2=12$. We know $v_1=0$, so
$w_2=12$.

\smallskip

\item{3.} The BV~square is basic, so $v_2+w_1=15$. We know $w_1=20$, so
$v_2=-5$.

\smallskip

\item{4.} The BX~square is basic, so $v_2+w_3=16$. We know $v_2=-5$, so
$w_3=21$.

\smallskip

\item{5.} The BY~square is basic, so $v_2+w_4=13$. We know $v_2=-5$, so
$w_4=18$.

\smallskip

\item{6.} The BZ~square is basic, so $v_2+w_5=10$. We know $v_2=-5$, so
$w_5=15$.

\smallskip

\item{7.} The CZ~square is basic, so $v_3+w_5=12$. We know $w_5=15$, so
$v_3=-3$.

\medskip

\noindent Therefore, the values of the dual variables are as follows:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;12;20 l;6;12 r;;15 r;;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2=-5 rest=l;2;15 r;;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3=-3 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1=20,w_2=12,w_3=21,w_4=18,w_5=15}
\endtableau$$

\goodbreak

\noindent Next we compute the test values for all of the nonbasic squares.
Remember, the test value for a nonbasic square is the cost minus the row
variable minus the column variable. We get the following test values:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;12;20 l;6;12 r;-6;15 r;-8;10 r;1;16.
	\tableaurow left=\hbox{B} right=v_2=-5 rest=l;2;15 r;11;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3=-3 rest=r;0;17 r;5;14 r;1;19 r;-1;14 l;12;12.
	\tableaufooter{w_1=20,w_2=12,w_3=21,w_4=18,w_5=15}
\endtableau$$

\goodbreak

\noindent We have negative test values, so this solution is not optimal. We
choose the most negative test value, which is the $-8$ in the AY~square, as our
pivot location. Now we need to find a circuit in this grid that starts in the
AY~square, goes vertically to a basic square (which must be the BY~square, as
there are no other basic squares in the Y~column), then goes horizontally to
another basic square, then goes vertically to another basic square, and so on,
until it returns to the AY~square. After a little bit of searching, we find the
following circuit in the grid, which goes AY--BY--BV--AV--AY:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right= rest=l;12;20 l;6;12 r;-6;15 r;-8;10 r;1;16.
	\tableaurow left=\hbox{B} right= rest=l;2;15 r;11;18 l;8;16 l;10;13 l;5;10.
	\tableaurow left=\hbox{C} right= rest=r;0;17 r;5;14 r;1;19 r;-1;14 l;12;12.
\endtableau
\llap{\raise0.45cm\hbox{\fig{transportation-example-2.mps}}\hskip1.55cm}$$

\noindent We form a tentative new solution by assigning a flow of~$t$ to the
AY~square, and then alternately subtracting and adding~$t$ to the flows in the
basic squares around the circuit, leaving the other basic squares unchanged:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaublankrow left=\hbox{A} right= rest=12-t,6, ,t, .
	\tableaublankrow left=\hbox{B} right= rest=2+t, ,8,10-t,5.
	\tableaublankrow left=\hbox{C} right= rest= , , , ,12.
\endtableau$$

\noindent We want to choose the largest value of~$t$ that does not cause any
flow to become negative. So we choose $t=10$ here, which gives us the new
basic feasible solution below:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaublankrow left=\hbox{A} right= rest=2,6, ,10, .
	\tableaublankrow left=\hbox{B} right= rest=12, ,8, ,5.
	\tableaublankrow left=\hbox{C} right= rest= , , , ,12.
\endtableau$$

\noindent Now we do the whole thing again! Write the costs in the grid, and
set $v_1=0$:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;2;20 l;6;12 r;;15 l;10;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2 rest=l;12;15 r;;18 l;8;16 r;;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1,w_2,w_3,w_4,w_5}
\endtableau$$

\noindent Use the basic squares to find the values of the other dual variables:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;2;20 l;6;12 r;;15 l;10;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2=-5 rest=l;12;15 r;;18 l;8;16 r;;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3=-3 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1=20,w_2=12,w_3=21,w_4=10,w_5=15}
\endtableau$$

\noindent Compute the test values for the nonbasic squares:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=l;2;20 l;6;12 r;-6;15 l;10;10 r;1;16.
	\tableaurow left=\hbox{B} right=v_2=-5 rest=l;12;15 r;11;18 l;8;16 r;8;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3=-3 rest=r;0;17 r;5;14 r;1;19 r;7;14 l;12;12.
	\tableaufooter{w_1=20,w_2=12,w_3=21,w_4=10,w_5=15}
\endtableau$$

\noindent We have a negative test value (in~AX), so this solution is not
optimal. The AX~square must be the pivot location. Search for a circuit, and
find AX--BX--BV--AV--AX:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right= rest=l;2;20 l;6;12 r;-6;15 l;10;10 r;1;16.
	\tableaurow left=\hbox{B} right= rest=l;12;15 r;11;18 l;8;16 r;8;13 l;5;10.
	\tableaurow left=\hbox{C} right= rest=r;0;17 r;5;14 r;1;19 r;7;14 l;12;12.
\endtableau
\llap{\raise0.45cm\hbox{\fig{transportation-example-3.mps}}\hskip1.55cm}$$

\noindent Assign a flow of~$t$ to the AX~square, and then alternately subtract
and add~$t$ to the flows around the circuit:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaublankrow left=\hbox{A} right= rest=2-t,6,t,10, .
	\tableaublankrow left=\hbox{B} right= rest=12+t, ,8-t, ,5.
	\tableaublankrow left=\hbox{C} right= rest= , , , ,12.
\endtableau$$

\noindent Choose $t=2$, which is the largest value that does not produce a
negative flow in any square:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaublankrow left=\hbox{A} right= rest= ,6,2,10, .
	\tableaublankrow left=\hbox{B} right= rest=14, ,6, ,5.
	\tableaublankrow left=\hbox{C} right= rest= , , , ,12.
\endtableau$$

\noindent Continue! Write the costs in the grid, and set $v_1=0$:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=r;;20 l;6;12 l;2;15 l;10;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2 rest=l;14;15 r;;18 l;6;16 r;;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1,w_2,w_3,w_4,w_5}
\endtableau$$

\noindent Find the values of the other dual variables:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=r;;20 l;6;12 l;2;15 l;10;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2=1 rest=l;14;15 r;;18 l;6;16 r;;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3=3 rest=r;;17 r;;14 r;;19 r;;14 l;12;12.
	\tableaufooter{w_1=14,w_2=12,w_3=15,w_4=10,w_5=9}
\endtableau$$

\noindent Compute the test values:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=r;6;20 l;6;12 l;2;15 l;10;10 r;7;16.
	\tableaurow left=\hbox{B} right=v_2=1 rest=l;14;15 r;5;18 l;6;16 r;2;13 l;5;10.
	\tableaurow left=\hbox{C} right=v_3=3 rest=r;0;17 r;-1;14 r;1;19 r;1;14 l;12;12.
	\tableaufooter{w_1=14,w_2=12,w_3=15,w_4=10,w_5=9}
\endtableau$$

\noindent The CW~square has a negative test value, so this solution is not
optimal. Use the CW~square as the pivot location, and find a circuit that
starts and ends at~CW. This circuit is a little trickier to find than the
previous ones, because it isn't just a rectangle: it goes
CW--AW--AX--BX--BZ--CZ--CW:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right= rest=r;6;20 l;6;12 l;2;15 l;10;10 r;7;16.
	\tableaurow left=\hbox{B} right= rest=l;14;15 r;5;18 l;6;16 r;2;13 l;5;10.
	\tableaurow left=\hbox{C} right= rest=r;0;17 r;-1;14 r;1;19 r;1;14 l;12;12.
\endtableau
\llap{\raise0.3cm\hbox{\fig{transportation-example-4.mps}}\hskip1.55cm}$$

\noindent Assign a flow of~$t$ to the CW~square, and then alternately subtract
and add~$t$ to the flows around the circuit:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaublankrow left=\hbox{A} right= rest= ,6-t,2+t,10, .
	\tableaublankrow left=\hbox{B} right= rest=14, ,6-t, ,5+t.
	\tableaublankrow left=\hbox{C} right= rest= ,t, , ,12-t.
\endtableau$$

\noindent Choose $t=6$, which is the largest value of~$t$ that does not make
any flow negative:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaublankrow left=\hbox{A} right= rest= , ,8,10, .
	\tableaublankrow left=\hbox{B} right= rest=14, , , ,{11}.
	\tableaublankrow left=\hbox{C} right= rest= ,6, , ,6.
\endtableau$$
But now we need to be careful! Look at what happened here. We gained one new
basic square~(CW), but we lost {\it two\/} basic squares (AW~and~BX), because
both of their flows became zero. This means that the number of basic squares
has dropped to~6. Remember that the number of basic squares should always be~7
in this problem. To fix this problem, {\it only one\/} of the two squares
AW~and~BX whose flow became zero should be made nonbasic; the other one should
be kept as a basic square whose flow happens to be zero. (This is a degenerate
solution.) Let's choose to keep AW as the basic square. This gives us the
following basic feasible solution:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaublankrow left=\hbox{A} right= rest= ,0,8,10, .
	\tableaublankrow left=\hbox{B} right= rest=14, , , ,{11}.
	\tableaublankrow left=\hbox{C} right= rest= ,6, , ,6.
\endtableau$$

\boxed{{\bf Special case when pivoting:} If the flow of more than one basic
square becomes zero when a pivot is performed, {\it only one\/} of those
squares should become nonbasic; the others should be kept as basic squares with
flows of zero. This is necessary in order to keep the correct number of basic
squares.}

\medbreak

\noindent Okay, now we can continue. Write the costs in the grid, and set
$v_1=0$:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=r;;20 l;0;12 l;8;15 l;10;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2 rest=l;14;15 r;;18 r;;16 r;;13 l;11;10.
	\tableaurow left=\hbox{C} right=v_3 rest=r;;17 l;6;14 r;;19 r;;14 l;6;12.
	\tableaufooter{w_1,w_2,w_3,w_4,w_5}
\endtableau$$

\noindent Find the values of the other dual variables:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=r;;20 l;0;12 l;8;15 l;10;10 r;;16.
	\tableaurow left=\hbox{B} right=v_2=0 rest=l;14;15 r;;18 r;;16 r;;13 l;11;10.
	\tableaurow left=\hbox{C} right=v_3=2 rest=r;;17 l;6;14 r;;19 r;;14 l;6;12.
	\tableaufooter{w_1=15,w_2=12,w_3=15,w_4=10,w_5=10}
\endtableau$$

\noindent Compute the test values:
$$\begintableau
	\tableauheader{\hbox{V},\hbox{W},\hbox{X},\hbox{Y},\hbox{Z}}
	\tableaurow left=\hbox{A} right=v_1=0 rest=r;5;20 l;0;12 l;8;15 l;10;10 r;6;16.
	\tableaurow left=\hbox{B} right=v_2=0 rest=l;14;15 r;6;18 r;1;16 r;3;13 l;11;10.
	\tableaurow left=\hbox{C} right=v_3=2 rest=r;0;17 l;6;14 r;2;19 r;2;14 l;6;12.
	\tableaufooter{w_1=15,w_2=12,w_3=15,w_4=10,w_5=10}
\endtableau$$

\noindent Hurray! All of the test values are nonnegative. That means that this
solution is optimal. So an optimal solution to this transportation problem is
as follows:

\medskip

\item{$\bullet$} Ship 8~units from A to~X.

\smallskip

\item{$\bullet$} Ship 10~units from A to~Y.

\smallskip

\item{$\bullet$} Ship 14~units from B to~V.

\smallskip

\item{$\bullet$} Ship 11~units from B to~Z.

\smallskip

\item{$\bullet$} Ship 6~units from C to~W.

\smallskip

\item{$\bullet$} Ship 6~units from C to~Z.

\medbreak

\noindent The total cost of this shipment plan is
$$8(\$15)+10(\$10)+14(\$15)+11(\$10)+6(\$14)+6(\$12)=\$696,$$
which is the minimum possible cost to satisfy all five demands and exhaust all
five supplies.

One other detail deserves mention: the case of a nonunique optimal solution.

\medskip

\boxed{{\bf Nonuniqueness:} If a test value in the optimal grid is zero, then
the optimal solution is not unique, and another optimal solution can be
obtained by pivoting on that square.}

\medskip

\noindent In this case, the test value of~0 in the CV~square in the final grid
tells us that this optimal solution is not unique---if we like, we can get
another optimal solution by pivoting on the CV~square. Try it!

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\bf A special case when forming the initial basic feasible solution:}
Occasionally, when you are forming the initial basic feasible solution, you
will simultaneously satisfy a demand {\it and\/} exhaust a supply (before the
bottom right square). When this happens, you need to be careful that you have
the right number of basic squares.

Here is an example. Suppose there are four warehouses (A,~B, C, and~D) with
respective supplies of 5,~9, 6, and~4 units, and six customers (U,~V, W, X, Y,
and~Z) with respective demands of 3,~7, 4, 2, 3, and~5 units. When we form the
initial basic feasible solution, we get the following:
$$\begintableau
	\sixtableauheader{\hbox{U: 3},\hbox{V: 7},\hbox{W: 4},\hbox{X: 2},\hbox{Y: 3},\hbox{Z: 5}}
	\sixtableaublankrow left=\phantom{00}\llap{\hbox{A: 5}} right= rest=3,2, , , , .
	\sixtableaublankrow left=\phantom{00}\llap{\hbox{B: 9}} right= rest= ,5,4, , , .
	\sixtableaublankrow left=\phantom{00}\llap{\hbox{C: 6}} right= rest= , , ,2,3,1.
	\sixtableaublankrow left=\phantom{00}\llap{\hbox{D: 4}} right= rest= , , , , ,4.
\endtableau$$
Notice what happened when we satisfied the demand of~W: we simultaneously
exhausted the supply of~B. This led to a diagonal step in the basic squares,
from BW to~CX. This disrupts the ``stair-step'' pattern, and more importantly
it gives us too few basic squares. Remember that the number of basic squares
should always equal the number of rows plus the number of columns minus~1,
which in this case is $4+6-1=9$; but we have only eight basic squares in this
solution.

We need to fix this deficiency, and at the same time we need to restore the
necessary ``stair-step'' pattern for the initial basic feasible solution. So
we need to add a basic square with a flow of zero. This basic square should be
either the CW~square or the BX~square (but not both!)\ in order to restore the
``stair-step'' pattern. Suppose that we choose the CW~square; then our initial
basic feasible solution will be as follows:
$$\begintableau
	\sixtableauheader{\hbox{U: 3},\hbox{V: 7},\hbox{W: 4},\hbox{X: 2},\hbox{Y: 3},\hbox{Z: 5}}
	\sixtableaublankrow left=\phantom{00}\llap{\hbox{A: 5}} right= rest=3,2, , , , .
	\sixtableaublankrow left=\phantom{00}\llap{\hbox{B: 9}} right= rest= ,5,4, , , .
	\sixtableaublankrow left=\phantom{00}\llap{\hbox{C: 6}} right= rest= , ,0,2,3,1.
	\sixtableaublankrow left=\phantom{00}\llap{\hbox{D: 4}} right= rest= , , , , ,4.
\endtableau$$

\boxed{{\bf Special case for the initial basic feasible solution:} If a demand
is satisfied and a supply is exhausted simultaneously when forming the initial
basic feasible solution, then add a basic square with zero flow to restore the
``stair-step'' pattern and give the right number of basic variables.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye
