\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

Show that the following linear programming problem can be
formulated as a minimum cost network flow problem.

\begin{tabular}{ll}
Minimize&$z = 5x_1 + 3x_2 + 2x_3 + 4x_4 + 7x_5$\\&$+ 5x_6 + 5x_7 +
3x_8 + 6x_9 +5x_{10}$\\subject to&$x_1,\ldots,x_{10} \geq
0$\\&$x_1 + x_2  = 12$\\&$x_2 + x_3 + x_4 = 10$\\&$ x_4 + x_5 =
13$\\&$x_5 + x_6 = 16$\\&$x_7 + x_8 = 6$\\&$x_8 + x_9 \leq
9$\\&$x_9 + x_{10} \geq 8$\\&$x_3 + x_7  + x_{10} = 20$.
\end{tabular}

Starting with a solution in which $x_1$, $x_2$, $x_5$, $x_6$,
$x_8$ and $x_{10}$ take positive values, and the constraints
$x_8+x_9  \leq 9$ and $x_9+x_{10} \geq 8$ are satisfied as strict
inequalities, use the network simplex method to solve the problem.




ANSWER

Adding slack variables and multiplying some constraints by $-1$,
the formulation is

\begin{tabular}{cll}
&Minimize&$z=5x_1+3x_2+2x_3+4x_4+7x_5+5x_6+5x_7+3x_8+6x_9+5x_{10}$\\
&subject to&$x_i\geq0\ i=1,\ldots,10$\\ (1)&&$x_1+x_2=12$\\
(2)&&$-x_2-x_3-x_4=-10$\\(3)&&$x_4+x_5=13$\\ (4)&&$-x_5-x_6=-16$\\
(5)&&$-x_7-x_8=-6$\\ (6)&&$x_8+x_9+s_1$\\
(7)&&$-x_9-x_{10}+s_2=-8$\\ (8)&&$x_3+x_9+x_10=10$\\
(9)&&$-x_1+x_6-s_1-s_2=-14$
\end{tabular}

(where the last redundant constraint is obtained by summing the
others).

The network is

\setlength{\unitlength}{1cm}

\begin{picture}(11,8)

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

\put(3.2,7){\vector(1,0){4.6}}\put(5.5,7.2){3}
\put(2.8,6.8){\vector(-2,-3){1.6}}\put(1.6,5.6){5}
\put(8,1.8){7}\put(9.8,3.8){\vector(-3,-2){4.1}}
\put(9.5,5.5){4}\put(10,4.2){\vector(-2,3){1.8}}
\put(3.7,4){6}\put(4,3.2){\vector(0,1){1.6}}
\put(5.5,2.5){3}\put(4.2,3){\vector(1,0){2.6}}
\put(3,3){0}\put(3.8,3){\vector(-3,1){2.6}}
\put(3.8,5){\vector(-3,-1){2.6}}\put(7.2,5.8){2}
\put(7.2,5.2){\vector(1,2){.8}}\put(7.2,3.8){5}
\put(7,4.8){\vector(0,-1){1.6}}\put(5.5,5.2){5}
\put(6.8,5){\vector(-1,0){2.6}}\put(2.8,4.7){0}
\put(1.2,3.8){\vector(3,-2){4.1}}\put(3,1.8){5}

\put(2.7,7.7){\vector(1,-2){.2}}\put(8.2,7.2){\vector(1,2){.3}}
\put(11,4){\vector(-1,0){.5}}\put(5.5,.8){\vector(0,-1){.5}}
\put(7,2.8){\vector(-1,-2){.3}}\put(4.5,2.2){\vector(-1,2){.3}}
\put(4,5.2){\vector(-1,2){.3}}\put(7.8,5){\vector(-1,0){.5}}
\put(.8,4){\vector(-1,0){.5}}

\put(2.8,7.5){12} \put(8.5,7.3){10} \put(10.5,3.5){13}
\put(5.7,.3){16} \put(7,2.5){6} \put(4.5,2.5){9} \put(4,5.5){8}
\put(7.5,4.5){20} \put(.5,3.5){14}

\end{picture}

The initial tree solution is

\setlength{\unitlength}{1cm}

\begin{picture}(11,8)

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

\put(3.2,7){\vector(1,0){4.6}}\put(5.5,7.2){3}
\put(2.8,6.8){\vector(-2,-3){1.6}}\put(1.6,5.6){5}
\put(8,1.8){7}\put(9.8,3.8){\vector(-3,-2){4.1}}
\put(5.5,2.5){3}\put(4.2,3){\vector(1,0){2.6}}
\put(3,3){0}\put(3.8,3){\vector(-3,1){2.6}}
\put(3.8,5){\vector(-3,-1){2.6}}\put(5.5,5.2){5}
\put(6.8,5){\vector(-1,0){2.6}}\put(2.8,4.7){0}
\put(1.2,3.8){\vector(3,-2){4.1}}\put(3,1.8){5}

\put(2.7,7.7){\vector(1,-2){.2}}\put(8.2,7.2){\vector(1,2){.3}}
\put(11,4){\vector(-1,0){.5}}\put(5.5,.8){\vector(0,-1){.5}}
\put(7,2.8){\vector(-1,-2){.3}}\put(4.5,2.2){\vector(-1,2){.3}}
\put(4,5.2){\vector(-1,2){.3}}\put(7.8,5){\vector(-1,0){.5}}
\put(.8,4){\vector(-1,0){.5}}

\put(2.8,7.5){12} \put(8.5,7.3){10} \put(10.5,3.5){13}
\put(5.7,.3){16} \put(7,2.5){6} \put(4.5,2.5){9} \put(4,5.5){8}
\put(7.5,4.5){20} \put(.5,3.5){14}

\put(3.2,7.2){0} \put(8.7,6.7){3} \put(10,3.3){3} \put(4.7,.7){10}
\put(7.3,3){8} \put(3.7,2.5){0} \put(4.3,5.2){5} \put(6.7,5.5){0}
\put(4.3,5.2){5}

\put(7,7.2){\framebox(.5,.4)}\put(7,7.2){\makebox(.5,.4){10}}
\put(1.7,6){\framebox(.5,.4)}\put(1.7,6){\makebox(.5,.4){2}}
\put(6.,5.2){\framebox(.5,.4)}\put(6.,5.2){\makebox(.5,.4){20}}
\put(3,4){\framebox(.5,.4)}\put(3,4){\makebox(.5,.4){12}}
\put(4.8,3.2){\framebox(.5,.4)}\put(4.8,3.2){\makebox(.5,.4){6}}
\put(3.5,3.3){\framebox(.5,.4)}\put(3.5,3.3){\makebox(.5,.4){3}}
\put(7.2,1.2){\framebox(.5,.4)}\put(7.2,1.2){\makebox(.5,.4){13}}
\put(2.3,2){\framebox(.5,.4)}\put(2.3,2){\makebox(.5,.4){3}}

\end{picture}

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

Entering arc is (8,5)

\setlength{\unitlength}{1cm}

\begin{picture}(6,4)

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

\put(4.8,3){\vector(-1,0){1.6}} \put(5,2.8){\vector(0,-1){1.6}}
\put(3.2,1){\vector(1,0){1.6}}\put(2.8,1.2){\vector(-2,1){1.6}}
\put(2.8,2.8){\vector(-2,-1){1.6}}

\put(3.5,3.2){$20-\theta$} \put(5.2,2){$\theta$}
\put(3.5,.5){$6-\theta$} \put(1,1){$3+\theta$}
\put(1,3){$12-\theta$}

\end{picture}

$\theta=6$

Leaving arc is (6,5)

\setlength{\unitlength}{1cm}

\begin{picture}(11,8)

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

\put(3.2,7){\vector(1,0){4.6}}\put(5.5,7.2){3}
\put(2.8,6.8){\vector(-2,-3){1.6}}\put(1.6,5.6){5}
\put(8,1.8){7}\put(9.8,3.8){\vector(-3,-2){4.1}}
\put(3,3){0}\put(3.8,3){\vector(-3,1){2.6}}
\put(3.8,5){\vector(-3,-1){2.6}}\put(7.2,3.7){5}
\put(7,4.8){\vector(0,-1){1.6}}\put(5.5,5.2){5}
\put(6.8,5){\vector(-1,0){2.6}}\put(2.8,4.7){0}
\put(1.2,3.8){\vector(3,-2){4.1}}\put(3,1.8){5}

\put(3.2,7.2){0} \put(8.7,6.7){3} \put(10,3.3){3} \put(4.7,.7){10}
\put(7.3,3){8} \put(3.7,2.5){0} \put(4.3,5.2){5} \put(6.7,5.5){0}
\put(4.3,5.2){5}

\put(7,7.2){\framebox(.5,.4)}\put(7,7.2){\makebox(.5,.4){10}}
\put(1.7,6){\framebox(.5,.4)}\put(1.7,6){\makebox(.5,.4){2}}
\put(6.,5.2){\framebox(.5,.4)}\put(6.,5.2){\makebox(.5,.4){14}}
\put(3,4){\framebox(.5,.4)}\put(3,4){\makebox(.5,.4){6}}
\put(7.2,4.2){\framebox(.5,.4)}\put(7.2,4.2){\makebox(.5,.4){6}}
\put(3.5,3.3){\framebox(.5,.4)}\put(3.5,3.3){\makebox(.5,.4){9}}
\put(7.2,1.2){\framebox(.5,.4)}\put(7.2,1.2){\makebox(.5,.4){13}}
\put(2.3,2){\framebox(.5,.4)}\put(2.3,2){\makebox(.5,.4){3}}

\end{picture}

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

Entering arc is (8,2)

\begin{picture}(6,4)

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

\put(4.8,3){\vector(-1,0){1.6}} \put(5,2.8){\vector(0,-1){1.6}}
\put(3.2,1){\vector(1,0){1.6}}\put(2.8,1.2){\vector(-2,1){1.6}}
\put(2.8,2.8){\vector(-2,-1){1.6}}

\put(3.5,3.2){$10-\theta$} \put(5.2,2){$\theta$}
\put(3.5,.5){$14-\theta$} \put(1,1){$6+\theta$}
\put(1,3){$2+\theta$}

\end{picture}

Leaving arc is (9,7)

\setlength{\unitlength}{1cm}

\begin{picture}(11,8)

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

\put(3.2,7){\vector(1,0){4.6}}\put(5.5,7.2){3}
\put(2.8,6.8){\vector(-2,-3){1.6}}\put(1.6,5.6){5}
\put(8,1.8){7}\put(9.8,3.8){\vector(-3,-2){4.1}}

\put(3,3){0}\put(3.8,3){\vector(-3,1){2.6}}

\put(7.2,5.2){\vector(1,2){.8}}\put(7.2,3.8){5}
\put(7,4.8){\vector(0,-1){1.6}}\put(5.5,5.2){5}
\put(6.8,5){\vector(-1,0){2.6}}\put(2.8,4.7){0}
\put(1.2,3.8){\vector(3,-2){4.1}}\put(3,1.8){5}


\put(3.2,7.2){0} \put(8.7,6.7){3} \put(10,3.3){3} \put(4.7,.7){10}
\put(7.3,3){8} \put(3.7,2.5){0} \put(4.3,5.2){5} \put(6.7,5.5){0}
\put(4.3,5.2){5}

\put(7,7.2){\framebox(.5,.4)}\put(7,7.2){\makebox(.5,.4){4}}
\put(1.7,6){\framebox(.5,.4)}\put(1.7,6){\makebox(.5,.4){8}}
\put(6.,5.2){\framebox(.5,.4)}\put(6.,5.2){\makebox(.5,.4){8}}
\put(7.2,6){\framebox(.5,.4)}\put(7.2,6){\makebox(.5,.4){6}}
\put(7.2,4.2){\framebox(.5,.4)}\put(7.2,4.2){\makebox(.5,.4){6}}
\put(3.5,3.3){\framebox(.5,.4)}\put(3.5,3.3){\makebox(.5,.4){9}}
\put(7.2,1.2){\framebox(.5,.4)}\put(7.2,1.2){\makebox(.5,.4){13}}
\put(2.3,2){\framebox(.5,.4)}\put(2.3,2){\makebox(.5,.4){3}}


\end{picture}

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

Thus, we have an optimal solution

$$x_1=8\ x_2=4\ x_3=6\ x_4=0\ x_5=13\ x_6=3\ x_7=6\ x_8=0\ x_9=0\
x_{10}=8\ z=240$$





\end{document}