\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

\begin{description}

\item[(a)]
Describe briefly some features of a computer implementation of the
network simplex method that would improve the efficiency of a
standard version of the algorithm.

\item[(b)]
Show that the following linear programming problem can be
formulated as a minimum cost network flow problem.

\begin{tabular}{ll}
Minimize&$z = 8x_1 + 7x_2 + 2x_3 + 6x_4 + 2x_5 + 6x_6$\\&$+ 5x_7 +
8x_8 + 7x_9 +9x_{10} + 8x_{11}$\\subject to&$x_1,\ldots,x_{11}
\geq 0$\\&$x_1 + x_2 + x_3 = 20$\\& $x_3 + x_4 = 16$\\&$x_4 + x_5
= 25$\\&$x_6 + x_7 + x_8 = 10$\\&$x_8 + x_9+ x_{10} =
30$\\&$x_{10} + x_{11} =32$\\&$x_1 + x_{6} \leq 23$
\end{tabular}

Starting with a solution in which $x_2$, $x_4$, $x_5$, $x_7$,
$x_9$ and $x_{11}$ take positive values, and the last constraint
is satisfied as a strict inequality, use the network simplex
method to solve the problem.

\end{description}

ANSWER

\begin{description}

\item[(a)]
The main points are:

\begin{itemize}

\item
compute dual variables by updating their values from the previous
iteration, rather than performing a complete recalculation

\item
compute reduced costs for a subset of arcs, and if there are
negative reduced costs, then choose the entering arc from this
subset.

\end{itemize}

\item[(b)]
The constraints can be written as

\begin{eqnarray*}
x_1+x_2+x_3&=&20\\ -x_3-x_4&=&-16\\ x_4+x_5&=&25\\
x_6+x_7+x_8&=&10\\ -x_8-x_9+x_{10}&=&-30\\ x_{10}+x_{11}&=&32\\
-x_1-x_6-s&=&-23\\ -x_2-x_5-x_7+x_9-x_{11}+s&=&-18
\end{eqnarray*}

where $s$ is a slack variable, and the last redundant constraint
is deduced from the others.

\setlength{\unitlength}{1cm}

\begin{picture}(6,9)

\put(8,8){Initial tree solution}

\put(1,5){\circle{.3}}\put(1,5){\makebox(0,0){1}}
\put(1,3){\circle{.3}}\put(1,3){\makebox(0,0){2}}
\put(2,1){\circle{.3}}\put(2,1){\makebox(0,0){3}}
\put(5,5){\circle{.3}}\put(5,5){\makebox(0,0){4}}
\put(5,3){\circle{.3}}\put(5,3){\makebox(0,0){5}}
\put(4,1){\circle{.3}}\put(4,1){\makebox(0,0){6}}
\put(3,7){\circle{.3}}\put(3,7){\makebox(0,0){7}}
\put(3,4){\circle{.3}}\put(3,4){\makebox(0,0){8}}

\put(1.2,5){\vector(2,-1){1.6}}\put(1,4.8){\vector(0,-1){1.6}}\put(1.2,5){\vector(1,1){1.8}}
\put(2,1.2){\vector(-1,2){.8}}\put(2,1.2){\vector(1,3){.8}}
\put(5,4.8){\vector(0,-1){1.6}}\put(4.8,5){\vector(-2,-1){1.6}}\put(4.8,5){\vector(-1,1){1.8}}
\put(4,1.2){\vector(1,2){.8}}\put(4,1.2){\vector(-1,3){.8}}
\put(3,4.2){\vector(0,1){2.6}}\put(3.2,4){\vector(2,-1){1.6}}

\put(.2,5.3){\vector(2,-1){.5}}\put(.8,2.8){\vector(-2,-1){.5}}
\put(1.7,.2){\vector(1,2){.3}}\put(5.7,5.4){\vector(-2,-1){.5}}
\put(5.2,2.8){\vector(2,-1){.5}}\put(4.4,.2){\vector(-1,2){.3}}
\put(3,7.2){\vector(0,1){.5}}\put(2.8,3.8){\vector(-2,-1){.5}}

\put(.3,5.3){20} \put(.3,2.2){16} \put(1.2,0){25} \put(5.5,5){10}
\put(5.5,3){30} \put(4.5,0){32} \put(3.2,7.5){23}


%second diagram
\put(1.5,6){8} \put(4.2,6){6} \put(3.2,5){0} \put(2.2,4.5){7}
\put(4,4.2){5} \put(.5,3.8){2} \put(4.2,3.5){7} \put(5.2,4){8}
\put(2,2.5){2} \put(3.8,2.5){8} \put(1.2,1.5){6} \put(4.6,1.5){9}



\put(8,5){\circle{.3}}\put(8,5){\makebox(0,0){1}}
\put(8,3){\circle{.3}}\put(8,3){\makebox(0,0){2}}
\put(9,1){\circle{.3}}\put(9,1){\makebox(0,0){3}}
\put(12,5){\circle{.3}}\put(12,5){\makebox(0,0){4}}
\put(12,3){\circle{.3}}\put(12,3){\makebox(0,0){5}}
\put(11,1){\circle{.3}}\put(11,1){\makebox(0,0){6}}
\put(10,7){\circle{.3}}\put(10,7){\makebox(0,0){7}}
\put(10,4){\circle{.3}}\put(10,4){\makebox(0,0){8}}

\put(8.2,5){\vector(2,-1){1.6}}
\put(9,1.2){\vector(-1,2){.8}}\put(9,1.2){\vector(1,3){.8}}
\put(11.8,5){\vector(-2,-1){1.6}} \put(11,1.2){\vector(-1,3){.8}}
\put(10,4.2){\vector(0,1){2.6}}\put(10.2,4){\vector(2,-1){1.8}}

 \put(10.2,5){0} \put(9.2,4.5){7} \put(11,4.2){5}
 \put(11.2,3.5){7} \put(9,2.5){2}
\put(10.8,2.5){8} \put(8.2,1.5){6}

\begin{small}
\put(9.4,5){\framebox(.4,.3)}\put(9.4,5){\makebox(.4,.3){23}}
\put(10.8,4.7){\framebox(.4,.3)}\put(10.8,4.7){\makebox(.4,.3){10}}
\put(8.2,4.2){\framebox(.4,.3)}\put(8.2,4.2){\makebox(.4,.3){20}}
\put(11.4,3.4){\framebox(.4,.3)}\put(11.4,3.4){\makebox(.4,.3){30}}
\put(8.5,2.3){\framebox(.4,.3)}\put(8.5,2.3){\makebox(.4,.3){16}}
\put(11.,1.8){\framebox(.4,.3)}\put(11.,1.8){\makebox(.4,.3){9}}
\put(9.5,1.5){\framebox(.4,.3)}\put(9.5,1.5){\makebox(.4,.3){32}}
\end{small}

\put(7.5,5.2){0} \put(7.5,3.2){11} \put(9.3,1){5} \put(12.3,5){2}
\put(12.2,3){14} \put(11.3,1){$-1$} \put(10.2,7){7}
\put(10.2,4.2){7}

\end{picture}

\begin{tabular}{ccl}
Non basic&$y_i+c_{ij}-y_j$\\ \hline (1,2)&$-9$&(Entering arc
(1,2))\\ (1,7)&1\\ (4,5)&1\\ (4,7)&$-4$\\ (6,5)&$-6$
\end{tabular}

\setlength{\unitlength}{1.cm}

\begin{picture}(6,6)

\put(1,5){\circle{.3}}\put(1,5){\makebox(0,0){1}}
\put(1,1){\circle{.3}}\put(1,1){\makebox(0,0){2}}
\put(5,1){\circle{.3}}\put(5,1){\makebox(0,0){3}}
\put(5,5){\circle{.3}}\put(5,5){\makebox(0,0){8}}

\put(0.5,3){$\theta$} \put(2.5,.5){$16-\theta$}
\put(5.2,3){$9+\theta$} \put(2.5,5.5){$20-\theta$}

\put(1,4.8){\vector(0,-1){3.6}} \put(4.8,1){\vector(-1,0){3.6}}
\put(5,1.2){\vector(0,1){3.6}} \put(4.8,5){\vector(-1,0){3.6}}


\end{picture}

$\theta=16$ leaving arc (3,2)

 \setlength{\unitlength}{1cm}

\begin{picture}(6,8)

\put(1,5){\circle{.3}}\put(1,5){\makebox(0,0){1}}
\put(1,3){\circle{.3}}\put(1,3){\makebox(0,0){2}}
\put(2,1){\circle{.3}}\put(2,1){\makebox(0,0){3}}
\put(5,5){\circle{.3}}\put(5,5){\makebox(0,0){4}}
\put(5,3){\circle{.3}}\put(5,3){\makebox(0,0){5}}
\put(4,1){\circle{.3}}\put(4,1){\makebox(0,0){6}}
\put(3,7){\circle{.3}}\put(3,7){\makebox(0,0){7}}
\put(3,4){\circle{.3}}\put(3,4){\makebox(0,0){8}}

\put(1.2,5){\vector(2,-1){1.6}}\put(1,4.8){\vector(0,-1){1.6}}
\put(2,1.2){\vector(1,3){.8}} \put(4.8,5){\vector(-2,-1){1.6}}
\put(4,1.2){\vector(-1,3){.8}}
\put(3,4.2){\vector(0,1){2.6}}\put(3.2,4){\vector(2,-1){1.8}}

\put(3.2,5){0} \put(2.2,4.5){7} \put(4,4.2){5} \put(4.2,3.5){7}
 \put(2,2.5){2} \put(3.8,2.5){8}

\begin{small}
\put(2.4,5){\framebox(.4,.3)}\put(2.4,5){\makebox(.4,.3){23}}
\put(3.8,4.7){\framebox(.4,.3)}\put(3.8,4.7){\makebox(.4,.3){10}}
\put(1.6,4.2){\framebox(.4,.3)}\put(1.6,4.2){\makebox(.4,.3){4}}
\put(4.4,3.4){\framebox(.4,.3)}\put(4.4,3.4){\makebox(.4,.3){30}}
\put(.4,4.5){\framebox(.4,.3)}\put(.4,4.5){\makebox(.4,.3){16}}
\put(.5,4){2}
\put(4.,1.8){\framebox(.4,.3)}\put(4.,1.8){\makebox(.4,.3){25}}
\put(2.5,1.5){\framebox(.4,.3)}\put(2.5,1.5){\makebox(.4,.3){32}}
\end{small}

\put(.5,5.2){0} \put(.5,3.2){11} \put(2.3,1){5} \put(5.3,5){2}
\put(5.2,3){14} \put(4.3,1){$-1$} \put(3.2,7){7} \put(3.2,4.2){7}

\end{picture}

\begin{tabular}{cc}
Non-basic&$y_i+c_{ij}-y_j$\\ \hline (1,7)&1\\ (3,2)&9\\
(4,5)&$-4$\\ (4,7)&1\\ (6,5)&$-6$
\end{tabular}

Entering arc (6,5)

\setlength{\unitlength}{1cm}

\begin{picture}(6,6)

\put(1,5){\circle{.3}}\put(1,5){\makebox(0,0){8}}
\put(1,1){\circle{.3}}\put(1,1){\makebox(0,0){6}}
\put(5,3){\circle{.3}}\put(5,3){\makebox(0,0){5}}

\put(1,1.2){\vector(0,1){3.6}}\put(1.2,1){\vector(2,1){3.8}}\put(1.2,5){\vector(2,-1){3.8}}

\put(1.2,3){$32-\theta$} \put(3,4.2){$30-\theta$}
\put(3,1.5){$\theta$}
\end{picture}

Leaving arc (8,5)

\setlength{\unitlength}{1cm}

\begin{picture}(6,8)

\put(1,5){\circle{.3}}\put(1,5){\makebox(0,0){1}}
\put(1,3){\circle{.3}}\put(1,3){\makebox(0,0){2}}
\put(2,1){\circle{.3}}\put(2,1){\makebox(0,0){3}}
\put(5,5){\circle{.3}}\put(5,5){\makebox(0,0){4}}
\put(5,3){\circle{.3}}\put(5,3){\makebox(0,0){5}}
\put(4,1){\circle{.3}}\put(4,1){\makebox(0,0){6}}
\put(3,7){\circle{.3}}\put(3,7){\makebox(0,0){7}}
\put(3,4){\circle{.3}}\put(3,4){\makebox(0,0){8}}

\put(1.2,5){\vector(2,-1){1.6}}\put(1,4.8){\vector(0,-1){1.6}}
\put(2,1.2){\vector(1,3){.8}} \put(4.8,5){\vector(-2,-1){1.6}}
\put(4,1.2){\vector(1,2){.8}}\put(4,1.2){\vector(-1,3){.8}}
\put(3,4.2){\vector(0,1){2.6}}

 \put(3.2,5){0} \put(2.2,4.5){7} \put(4,4.2){5}
\put(.5,3.8){2} \put(2,2.5){2} \put(3.8,2.5){8} \put(4.6,1.5){9}

\begin{small}
\put(2.4,5){\framebox(.4,.3)}\put(2.4,5){\makebox(.4,.3){23}}
\put(3.8,4.7){\framebox(.4,.3)}\put(3.8,4.7){\makebox(.4,.3){10}}
\put(.4,4.5){\framebox(.4,.3)}\put(.4,4.5){\makebox(.4,.3){16}}
\put(4.4,3.4){\framebox(.4,.3)}\put(4.4,3.4){\makebox(.4,.3){30}}
\put(1.5,2.3){\framebox(.4,.3)}\put(1.5,2.3){\makebox(.4,.3){16}}
\put(1.6,4.2){\framebox(.4,.3)}\put(1.6,4.2){\makebox(.4,.3){4}}
\put(4.,1.8){\framebox(.4,.3)}\put(4.,1.8){\makebox(.4,.3){25}}
\put(2.5,1.5){\framebox(.4,.3)}\put(2.5,1.5){\makebox(.4,.3){2}}
\put(4.6,2){\framebox(.4,.3)}\put(4.6,2){\makebox(.4,.3){30}}
\end{small}

\put(.5,5.2){0} \put(.5,3.2){11} \put(2.3,1){5} \put(5.3,5){2}
\put(5.2,3){14} \put(4.3,1){$-1$} \put(3.2,7){7} \put(3.2,4.2){7}

\end{picture}

\begin{tabular}{cc}
Non-basic&$y_i+c_{ij}-y)j$\\ (1,7)&1\\ (3,2)&9\\ (4,5)&2\\
(4,7)&1\\ (8,5)&6
\end{tabular}

Thus we have an optimal solution.

$x_3=16\ x_2=4\ x_5=25\ x_{11}=2\ x_{10}=30\ x_7=10\
x_1=x_4=x_6=x_8=x_9=0\ z=446$

\end{description}




\end{document}