\documentclass[11pt]{article}
%\baselineskip 16pt
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}

\setlength{\oddsidemargin}{-0.15in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{9in}
\setlength{\textwidth}{6.5in}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\def\qed{\hfill $\Box$\medskip}

\def\IR{{\mathbb R}}
\def\IC{{\mathbb C}}
\def\IF{{\mathbb F}}
\def\II{{\mathbb I}}
\def\IN{{\mathbb N}}
\def\IQ{{\mathbb Q}}
\def\IZ{{\mathbb Z}}
\def\cB{{\mathcal B}}
\def\cR{{\mathcal R}}
\def\cF{{\mathcal F}}
\def\bC{{\bf C}}
\def\bP{{\bf P}}
\def\bM{{\bf M}}
\def\bd{{\bf d}}\def\({\left (}
\def\){\right )}
\def\logm{{\prec_{\rm log}}\,}
\def\diag{{\rm diag}\,}
\def\tr{{\rm tr}\,}
\def\rank{{\rm rank}\,}
\def\span{{\rm span}\,}
\def\dfrac{\displaystyle\frac}
\def\IR{{\mathbb R}}
%\pagestyle{empty}
\begin{document}
\openup 1\jot

\noindent{\bf
Math 323 Operations Research \qquad Notes on Chapter 7
\rm \hfill C.K. Li

\noindent
{\bf Sample table for transportation problem}

\medskip\noindent
{\bf Example}
Solve the Powerco problem.

\medskip\centerline{ 
\begin{tabular}{|c| c c c c |c|}
\hline 
& C1 & C2 & C3 & C4 & Supply\\
\hline
P1 & \$8 & \$6 & \$10 & \$9 & $\le 35$ \\
P2 & \$9 & \$12 & \$13 & \$7 & $\le 50$ \\
P3 & \$14 & \$9 & \$16 & \$5 & $\le 40$ \\
\hline
Demand & $\ge 45$ & $\ge 20$ & $\ge 30$ & $\ge 30$ & \\
\hline
\end{tabular}\quad ~ 
}

\bigskip
\bigskip
\begin{tabular}{|l|r|r|r|r|r|}
\hline
 & City1  & City2 & City3 & City4 & Supply\cr
\hline Plant1 & 8 & 6 & 10 & 9 & \cr
& & & & & 35\cr
\hline
Plant2 & 9 & 12 & 13 & 7 & \cr
& & & & & 50\cr
\hline
Plant3 & 14 & 9 & 16 & 5 & \cr
& & & & & 40\cr
\hline
Demand & 45 & 20 & 30 & 30 & \cr
\hline
\end{tabular}
\qquad 
\begin{tabular}{ll}
$u_1 =  \qquad$  & $v_1 =  $\cr

\\

$u_2 =  \qquad$  & $v_2 =  $\cr

\\
$u_3 =  \qquad$ & $v_3 =  $\cr

\\
& $v_4 =  $ \cr
\end{tabular}
\qquad $\Delta = $

\bigskip
\bigskip
\begin{tabular}{|l|r|r|r|r|r|}
\hline
 & City1 & City2 & City3 & City4 & Supply\cr
\hline Plant1 & 8 & 6 & 10 & 9 & \cr
& & & & & 35\cr
\hline
Plant2 & 9 & 12 & 13 & 7 & \cr
& & & & & 50\cr
\hline
Plant3 & 14 & 9 & 16 & 5 & \cr
& & & & & 40\cr
\hline
Demand & 45 & 20 & 30 & 30 & \cr
\hline
\end{tabular}
\qquad 
\begin{tabular}{ll}
$u_1 =  \qquad$  & $v_1 =  $\cr

\\

$u_2 =  \qquad$  & $v_2 =  $\cr

\\
$u_3 =  \qquad$ & $v_3 =  $\cr

\\
& $v_4 =  $ \cr
\end{tabular}
\qquad $\Delta = $


\bigskip
\bigskip
\begin{tabular}{|l|r|r|r|r|r|}
\hline
 & City1 & City2 & City3 & City4 & Supply\cr
\hline Plant1 & 8 & 6 & 10 & 9 & \cr
& & & & & 35\cr
\hline
Plant2 & 9 & 12 & 13 & 7 & \cr
& & & & & 50\cr
\hline
Plant3 & 14 & 9 & 16 & 5 & \cr
& & & & & 40\cr
\hline
Demand & 45 & 20 & 30 & 30 & \cr
\hline
\end{tabular}
\qquad 
\begin{tabular}{ll}
$u_1 =  \qquad$  & $v_1 =  $\cr

\\

$u_2 =  \qquad$  & $v_2 =  $\cr

\\
$u_3 =  \qquad$ & $v_3 =  $\cr

\\
& $v_4 =  $ \cr
\end{tabular}
\qquad $\Delta = $

\bigskip
\bigskip
\begin{tabular}{|l|r|r|r|r|r|}
\hline
 & City1 & City2 & City3 & City4 & Supply\cr
\hline Plant1 & 8 & 6 & 10 & 9 & \cr
& & & & & 35\cr
\hline
Plant2 & 9 & 12 & 13 & 7 & \cr
& & & & & 50\cr
\hline
Plant3 & 14 & 9 & 16 & 5 & \cr
& & & & & 40\cr
\hline
Demand & 45 & 20 & 30 & 30 & \cr
\hline
\end{tabular}
\qquad 
\begin{tabular}{ll}
$u_1 =  \qquad$  & $v_1 =  $\cr

\\

$u_2 =  \qquad$  & $v_2 =  $\cr

\\
$u_3 =  \qquad$ & $v_3 =  $\cr

\\
& $v_4 =  $ \cr
\end{tabular}
\qquad $\Delta = $
\end{document}

{\bf 7.4 Sensitivity Analysis}

\begin{itemize}

\item Change $c_{ij}$ to $c_{ij} + \Delta$ for a nonbasic variable. 
Then use the same $u_i, v_j$ and compute the new $c_{ij}-u_i-v_j$ to decide the range for 
$\Delta$ so that
the solution to remain optimal. (For minimum cost, we want $c_{ij} - u_i -v_j \ge 0$.)

\item Change $c_{ij}$ to $c_{ij}+\Delta$
for a basic variable. We need to solve for $u_i, v_j$ again to 
compute $c_{rs}$ for all $c_{rs}$, and determine the range for 
the $\Delta$ so that
the solution to remain optimal.

\item Suppose $u_i, v_j$ are changed by $\Delta$. 

If $x_{ij}$ is a basic variable, change $x_{ij}$ to $x_{ij} + \Delta$ and compute
$Z = \sum_{r,s} c_{rs}x_{rs} c_{ij}\Delta$.

If $x_{ij}$ is a nonbasic variable, find a loop starting with $x_{ij}$
together with other basic variable. Then increase the odd vertex of the loop 
by $\Delta$, and decrease the even vertex of the loop by $\Delta$.

\end{itemize}

\medskip\noindent
{\bf See Examples in p. 390-392.}

\newpage
\includegraphics[height=9in,width=6.8in]{table39.pdf}
\newpage

\bigskip
\noindent
{\bf 7.5 Assignment problems}

Assign $m$ people to $m$ jobs with a cost (salary) matrix.
Basically, we are solving the supply demand problem with $s_i = v_j = 1$ 
for all $i,j = 1, \dots, m$.

We can use the standard transportation simplex method.

We can also use the Hungarian method. 

\begin{enumerate}

\item Subtract the minimum element in each row from entries of the same row for 
all rows to get a reduced cost matrix.

\item Find the minimum number of lines (vertical / horizontal) covering all the zeros
in the matrix. If we need $m$ lines, we are done. Else, go to Step 3.

\item Find the minimum entry not covered by the lines, and subtract it from the
uncovered entries, and add it to entries covered by two lines.  Return to Step 2.
\end{enumerate}   

Explanation of Algorithm. Adding/subtracting constants from a row/columns
does not change the optimal solution.

Steps 1 and 3 are just changing the cost matrix without changing the optimal 
solution. In particular, Step 3 is adding a constant to the covered rows, 
and subtracting a the same constant from the uncovered columns.


\medskip\noindent
{\bf See Example in p. 396-397.}

\newpage
\includegraphics[height=8in,width=6.8in]{table44.pdf}

\newpage
\includegraphics[height=8in,width=6.8in]{table46.pdf}
\newpage
\noindent
{\bf 7.6 Transshipment problems}

\medskip\noindent
{\bf Basic idea} Using the intermediate nodes (transshipment points) in a
transportation network  as as supply and demand points as well.

\medskip\noindent
{\bf Example (pp. 400-402)} Widgetco manufactures widgets at Memphis and Denver
(150 unit and 200 units). Have to ship to Los Angeles and Boston
(130 unites in each demand point). 

Looking at the transportation cost matrix, one would assume that
Memphis, Denver, N.Y. Chicago as supply points,
N.Y. Chicago, L.A., Boston, Dummy as demand points. 

Solving the problem, we see that it is beneficial to send 
product from Memphis to L.A. through N.Y.  


\newpage
\includegraphics[height=9in,width=6.8in]{table59.pdf}
\end{document}
