\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

\begin{description}

\item[(a)]
Describe how  artificial arcs are used in the network simplex
method.   Suppose that artificial arcs remain in the tree solution
at the end of phase~1 of the two-phase network simplex method.
State the conditions under which phase 2 should be performed, and
describe what happens to these artificial arcs in phase~2.

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

\begin{tabular}{ll}
Minimize&$z = 5x_1 + 8x_2 + 11x_3 + 10x_4$\\&$+ 4x_5 + 9x_6 + 6x_7
+ 8x_8 + 7x_9 $\\subject to&$x_1,\ldots,x_{9} \geq 0$\\&$x_1 + x_2
= 15$\\&$x_2 + x_3 +x_4= 20$\\&$x_4 + x_5 = 12$\\&$x_6 + x_7 +
x_{8}= 27$\\&$x_8 + x_{9} = 14$\\&$x_3 + x_{7} \le 18$.
\end{tabular}

Starting with a solution in which $x_1$, $x_2$, $x_4$, $x_7$ and
$x_{8}$ take positive values, and the constraint $x_3+x_7 \le 18$
is satisfied as a strict inequality, use the network simplex
method to solve the problem.

\end{description}

ANSWER


\begin{description}

\item[(a)]
Select any node $w$ of the network. for each source node $i\
(i\neq w)$, if there is no arc from $i$ to $w$, add an artificial
arc with cost $c_{iw}'=1$. For each non-source node $j\ (j\neq
w)$, if there is no arc from $w$ to $j$, add an artificial arc
with cost $c'_{wj}-1$. All original arcs $(k,l)$ are assigned a
cost $c_{kl}'=0$. The first phase of the nethod minimizes $z'=\sum
c_{kl}x_{kl}$ (where $x_{kl}$ is the flow in arc $(k,l)$). The
initial tree solution is

\begin{eqnarray*}
x_{iw}&=&a_i\textrm{ for source nodes with supply }a_i\\
x_{wj}&=&b_j\textrm{ for intermediate and sink nodes with demand
}b_j
\end{eqnarray*}

\begin{itemize}

\item
If, at the end of phase 1, $z'>0$, the problem is infeasible.

\item
If $z'=0$ and the feasible tree solution contains no artificial
arc, the second phase of finding the minimum cost flow starts.

\item
If $z'=0$ but there is some artificial arc $(u,v)$ in the feasible
tree solution with $x_{uv}=0$, consider the dual variables $y_i$
for this solution. The satisfy $y_i+c_{ij}'\geq y_j$ for all arcs
$(i,j)$ with equality holding for arcs of the tree solution.
Partition the nodes into two sets $S$ and $T$, where
$S=\{k|y_k\leq y_u\}$ and $T=\{k|y_K>y_u\}$. The problem
decomposes into subproblems involving nodes of $S$, and nodes of
$T$, and arcs between $S$ and $T$ are removed.

\end{itemize}

\item[(b)]
Multiplying some of the constraints by $-1$ and introducing slack
variables, we obtain

\begin{eqnarray*}
x_1+x_2&=&15\\ -x_2-x_3-x_4&=&-20\\ x_4+x_5&=&12\\
-x_6-x_7-x_8&=&-27\\ x_8+x_9&=&14\\ x_3+x_7+s&=&18\\
-x_1-x_5+x_6-x_9-s&=&-12
\end{eqnarray*}

where the last constraint is obtained by summing the others.

\setlength{\unitlength}{1cm}

\begin{picture}(8,10)

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

\put(3.2,9){\vector(2,-1){3.8}}\put(5,8.5){8}
\put(2.8,8.8){\vector(-1,-3){1.8}}\put(1.5,6.5){5}
\put(4.2,7){\vector(1,0){2.6}}\put(5,6.5){10}
\put(3.8,6.8){\vector(-3,-4){2.6}}\put(2.5,5.5){4}
\put(4,4.8){\vector(-1,-2){.8}}\put(3.5,3.5){8}
\put(3.8,5){\vector(-3,-2){2.6}}\put(2.5,3.8){7}
\put(5,1.2){\vector(1,3){1.8}}\put(6.4,4){11}
\put(4.8,1){\vector(-1,1){1.8}}\put(4.,2){6}
\put(4.8,1){\vector(-2,1){3.6}}\put(2.5,1.7){0}
\put(1.2,3){\vector(1,0){1.6}}\put(2.3,2.5){9}

\put(2.5,9.7){\vector(1,-2){.3}}\put(2.5,9.7){15}
\put(7.2,7.2){\vector(2,1){.5}}\put(6.8,7.5){20}
\put(3.4,7.6){\vector(1,-1){.4}}\put(3.2,7.7){12}
\put(3,2.8){\vector(0,-1){.4}}\put(3.2,2.5){27}
\put(4.6,5.6){\vector(-3,-2){.5}}\put(4.5,5.2){14}
\put(5.4,.2){\vector(-1,3){.2}}\put(5.5,.5){18}
\put(.8,2.8){\vector(-2,-1){.5}}\put(.5,2.4){12}

\end{picture}

The initial tree solution is


\setlength{\unitlength}{1cm}

\begin{picture}(8,10)

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

\put(3.2,9){\vector(2,-1){3.8}}\put(5,8.5){8}
\put(2.8,8.8){\vector(-1,-3){1.8}}\put(1.5,6.5){5}
\put(4.2,7){\vector(1,0){2.6}}\put(5,6.5){10}

\put(4,4.8){\vector(-1,-2){.8}}\put(3.5,3.5){8}


\put(4.8,1){\vector(-1,1){1.8}}\put(4.,2){6}
\put(4.8,1){\vector(-2,1){3.6}}\put(2.5,1.7){0}

\put(5.5,6.5){\framebox(.5,.4)}\put(5.5,6.5){\makebox(.5,.4){12}}
\put(5.3,8){\framebox(.5,.4)}\put(5.3,8){\makebox(.5,.4){8}}
\put(1.3,6.){\framebox(.5,.4)}\put(1.3,6.){\makebox(.5,.4){7}}
\put(2.5,1.3){\framebox(.5,.4)}\put(2.5,1.3){\makebox(.5,.4){5}}
\put(4.2,1.7){\framebox(.5,.4)}\put(4.2,1.7){\makebox(.5,.4){13}}
\put(3.,4){\framebox(.5,.4)}\put(3.,4){\makebox(.5,.4){14}}

\put(2.5,9.7){\vector(1,-2){.3}}\put(2.5,9.7){15}
\put(7.2,7.2){\vector(2,1){.5}}\put(6.8,7.5){20}
\put(3.4,7.6){\vector(1,-1){.4}}\put(3.2,7.7){12}
\put(3,2.8){\vector(0,-1){.4}}\put(3.2,2.5){27}
\put(4.6,5.6){\vector(-3,-2){.5}}\put(4.5,5.2){14}
\put(5.4,.2){\vector(-1,3){.2}}\put(5.5,.5){18}
\put(.8,2.8){\vector(-2,-1){.5}}\put(.5,2.4){12}

\put(4.2,6.5){$-2$} \put(6.5,6.5){8} \put(3.2,9.2){0}
\put(.7,3.2){5} \put(4.5,.5){5} \put(2.5,3.2){11} \put(3.5,5.2){3}

\end{picture}

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

Entering arc is (3,7)

\setlength{\unitlength}{1cm}

\begin{picture}(6,6)

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

\put(3.2,4.8){\vector(1,-1){1.6}} \put(3.2,2.2){\vector(2,1){1.6}}
\put(2.8,1.8){\vector(-2,-1){1.6}}
\put(2.8,4.8){\vector(-1,-2){1.8}}

\put(4.2,4.2){$8+\theta$} \put(4,2){$12-\theta$}
\put(2,1){$\theta$} \put(1,3){$7-\theta$}

\end{picture}

$\theta=7$

Leaving arc is (1,7).


\setlength{\unitlength}{1cm}

\begin{picture}(8,10)

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

\put(3.2,9){\vector(2,-1){3.8}}\put(5,8.5){8}

\put(4.2,7){\vector(1,0){2.6}}\put(5,6.5){10}
\put(3.8,6.8){\vector(-3,-4){2.6}}\put(2.5,5.5){4}
\put(4,4.8){\vector(-1,-2){.8}}\put(3.5,3.5){8}

\put(4.8,1){\vector(-1,1){1.8}}\put(4.,2){6}
\put(4.8,1){\vector(-2,1){3.6}}\put(2.5,1.7){0}

\put(4.2,6.5){$-2$} \put(6.5,6.5){8} \put(3.2,9.2){0}
\put(.7,3.2){5} \put(4.5,.5){5} \put(2.5,3.2){11} \put(3.5,5.2){3}


\put(5.5,6.5){\framebox(.5,.4)}\put(5.5,6.5){\makebox(.5,.4){5}}
\put(5.3,8){\framebox(.5,.4)}\put(5.3,8){\makebox(.5,.4){15}}
\put(2.5,6,){\framebox(.5,.4)}\put(2.5,6.){\makebox(.5,.4){7}}
\put(2.5,1.3){\framebox(.5,.4)}\put(2.5,1.3){\makebox(.5,.4){5}}
\put(4.2,1.7){\framebox(.5,.4)}\put(4.2,1.7){\makebox(.5,.4){13}}
\put(3.,4){\framebox(.5,.4)}\put(3.,4){\makebox(.5,.4){14}}

\end{picture}

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

Thus, we have an optimal solution

$$x_1=0\ x_2=15\ x_3=0\ x_4=5\ x_5=7\ x_6=0\ x_7=13\ x_8=14\
x_9=0$$

$$z=8\times15+10\times5+4\times7+6\times13+8\times14=388$$

\end{description}




\end{document}