\documentstyle{slides}
\pagestyle{plain}
\begin{document}
\blackandwhite{example}
\begin{slide}{}
\begin{center}
{\Large\bf NETWORK SIMPLEX METHOD}
\end{center}
\begin{center}
{\Large\bf for the}
\end{center}
\begin{center}
{\Large\bf TRANSSHIPMENT PROBLEM}
\end{center}
\begin{center}
{\bf C\&O 370}~~~~ {\bf WINTER 1995}
\end{center}

The transshipment problem on the digraph $G=(V(G),E(G))$ is the linear
program
\[ (TP) ~~~\min z=cx ~\mbox{s.t.}~Ax=b, x\geq 0.
\]
In (TP), $A=\left\{ a_{ve} : (v,e) \in V(G) \times E(G) \right\}$ is
the {\em incidence matrix of $G$}, defined by
\[
a_{ve}=  \left\{
\begin{array}{ccl}
-1  &  \mbox{if}  & v=t(e)\\
1  &  \mbox{if}  & v=h(e)\\
0  &  otherwise.
\end{array}
  \right.
\]

\end{slide}
\begin{slide}{}

$c=\left\{ c_e : e \in E(G) \right\}$ is a given real {\em cost} vector,
and $b=\left\{ b_v : v \in V(G) \right\}$ is a given real {\em demand}
vector.

A tree solution of (TP) is a vector $x^0 = \left\{x^0_j : j \in E(G)
\right\}$ which is the (unique) solution of the equality constraints of
(TP) together with $x_j=0, j \in E \backslash T,$ where %T% is the
edge-set of some spanning tree of $G$. (Henceforth, we abbreviate {\em
edge-set of a spanning tree of $G$} to {\em tree of $G$}).


\end{slide}
\begin{slide}{}

If a tree solution $x^0$ of (TP) is also nonnegative, then $x^0$ is a
\underline{feasible tree solution}. Any tree determining a feasible tree
solution is a \underline{feasible tree}. Given such a tree $T$ and edge
set $e \in E \backslash T,$ let $C(T,e)$ be the unique circuit of $G$
satisfying:
\begin{enumerate}
\item
every edge of $C(T,e)$ is in $T \cup \{e\}$
\item
$e$ is a forward edge of $C(T,e).$
\end{enumerate}

The \underline{cost} (with respect to $c$) of $C(T,e)$ is defined to be
\[ \begin{array}{c}
  \sum \{ c_j : j ~\mbox{is a forward edge of}~C(T,e) \} \\
  ~~~-~~\sum \{ c_j : j ~\mbox{is a reverse edge of}~C(T,e) \} 
\end{array}
\]
(The cost of a path is defined analogously.)

For $e \in E,$  we have $c_e(T)$ is the cost of $C(T,e)$ if $e \in E
\backslash T$ and is 0 if $e \in T$.


\end{slide}
\begin{slide}{}

{\large \bf NETWORK SIMPLEX METHOD}
\begin{enumerate}
\item[Step 0]~\\
Find a feasible tree $T$ with associated solution $x^0$, or show that no
feasible tree exists.
\item[Step 1]~\\
If $c_j(T) \geq 0,$ for all $j \in E \backslash T,$ then STOP; $x^0$ is
an optimal solution. Otherwise, choose $e \in E \backslash T$ with
$c_e(T) < 0.$
\item[Step 2]~\\
If $C(T,e)$ has no reverse edge, the STOP; (TP) is unbounded.
\end{enumerate}

\end{slide}
\begin{slide}{}

\begin{enumerate}
\item[Step 3]~\\
Let
\[
\theta = \min 
  \{ x^0_j : j ~\mbox{is a reverse edge of}~C(T,e) \}.
\]
Let
\[
F = 
  \{ j : j ~\mbox{is a reverse edge of}~C(T,e)  \& x_j^0 = 0\}.
\]
Define $x^1 =  \{ x_j^1 : j \in e \}$ by 
\[
x_j^1=  \left\{
\begin{array}{ccl}
x_j^0 + \theta &  \mbox{if}~ j ~\mbox{forward in}~ C(T,e)\\
x_j^0 - \theta &  \mbox{if}~ j ~\mbox{reverse in}~ C(T,e)\\
x_j^0  &  otherwise.
\end{array}
  \right.
\]
Choose $f \in F,$ and let $T^1=\{T \cup \{e\}\} \backslash \{f\}.$
Replace $T$ by $T^1$ and $x^0$ by $x^1$ and go to Step 1.
\end{enumerate}


\end{slide}
\begin{slide}{}

\underline{Comments}
\begin{enumerate}
\item
Step 0 requires a {\em Phase 1} subroutine.
\item
The numbers $c_j(T)$ of Step 1 can be evaluated by maintaining the
vector $y(T) = \{y_v(T): v \in V\},$ where relative to a designated root
node $r$, $y_v(T)$ is the cost of the $rv$-path in $T$. Then, it can be
shown that
\[
c_j(T) = c_j + y_{t(j)}(T) - y_{h(e)}(T) , \forall j \in E.
\]
\item
The termination criterion of Step 1 is valid. This can be demonstrated
by showing that $y(T)$ is dual feasible and satisfies complementary
slackness with $x^0.$

\item
The termination criterion of Step 2 is valid, since $x^1$ defined in
step 3 is feasible for $\theta$ arbitrarily large and has $cx^1 = cx^0 +
\theta c_e(T).$
\item
The following refinement due to R. Bland does not admit cycling:
~~\\
~~\\
Let $e_1, e_2, \ldots, e_n$ be an arbitrary, fixed ordering of $E
(=E(G)).$ Then, 
\begin{enumerate}
\item
choose $e$ in step 1 to have the least index possible
\item
choose $f$ in step 3 to have the least index possible.
\end{enumerate}
\end{enumerate}

\end{slide}{}
\end{document}
