\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION


 An engineering company manufactures industrial machines
for overseas export.  Demand for the next three months, which must
be satisfied, is shown in the following table.

\begin{center}
\begin{tabular}{lccc}
\hline Month&Aug&Sept&Oct\\ Demand&130&210&220\\ \hline
\end{tabular}
\end{center}

Capacity restrictions limit the production of machines to a
maximum of 200 per month.  However, it is possible to manufacture
machines before they are required.  In this case, there is a cost
of \pounds200 per machine in storage at the end of each month. At
the start of August, there are no machines in storage, and no
machines are required at the end of October.

The machines can be distributed to customers by aeroplane or by
ship. Air transportation costs \pounds1000 per machine; sea
transportation costs \pounds750 per machine. Machines to be
transported by air are dispatched in the month that they are
required. On the other hand, machines to be transported by sea
must be dispatched one month in advance. As a consequence, all
machines that are manufactured to satisfy the demand in August
must be transported by air, and no machines are transported by sea
in October.

Show that the problem of planning the production and the
distribution of machines to customers so that demand is satisfied
at minimum total cost can be formulated as a minimum cost network
flow problem.

Starting with a solution in which the production quantities, the
numbers of machines transported by air and sea, and the end of
month inventories, for each month are specified in the following
table, use the network simplex method to solve the problem.

\begin{center}
\begin{tabular}{lrrr}\\
\hline Month&Aug&Sept&Oct\\ \hline Production&160&200&200\\ Number
transported by air&130&180&200\\ Number transported by
sea&30&20&0\\ End of month inventory&0&0&0\\ \hline
\end{tabular}
\end{center}


ANSWER

Number the months 1,2,3 and define variables

$x_t$= production in month $t$

$y_t$= quantity transported by air in month $t$

$z_t$= quantity transported by sea in month $t$

$s_t$= end of month inventory in month $t$.

The formulation is

\begin{center}
\begin{tabular}{ll}
Minimize&$z=1000(y_1+y_2+y_3)+750(z_1+z_2)+200(s_1+s_2)$\\ subject
to&$x_t\geq0,y_t\geq0\ t=1,2,3$\\ &$z_t\geq0,s_t\geq0\ t=1,2$\\
&$y_1=130$\\ &$y_2+z_1=210$\\ &$y_3+z_2=220$\\
&$x_1-y_x-z_1-s_1=0$\\ &$x_2-y_2-z_2+s_1-s_2=0$\\
&$x_3-y_3-z_3+s_2=0$\\ &$x_1\leq200$\\ &$x_2\leq200$\\
&$x_3\leq200$
\end{tabular}
\end{center}

The last 3 constraints can be written as

\begin{eqnarray*}
-x_1-t_1&=&-200\\ -x_2-t_2&=&-200\\ -x_3-t_3&=&-200
\end{eqnarray*}

for slack variables $t_1,t_2,t_3,t_4$ and a redundant constraint
is $t_1+t_2+t_3=40$.

\setlength{\unitlength}{1.4cm}

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

\put(1,6.8){\vector(0,-1){1.6}}
\put(3,6.8){\vector(-1,-1){1.8}}\put(3,6.8){\vector(0,-1){1.6}}
\put(5,6.8){\vector(-1,-1){1.8}}\put(5,6.8){\vector(0,-1){1.6}}
\put(1,4.8){\vector(0,-1){1.8}}
\put(2.8,5){\vector(-1,0){1.6}}\put(3,4.8){\vector(0,-1){1.6}}
\put(4.8,5){\vector(-1,0){1.6}}\put(5,4.8){\vector(0,-1){1.6}}
\put(2,1.2){\vector(-1,2){.8}}\put(2,1.2){\vector(1,2){.8}}\put(2,1.2){\vector(3,2){2.8}}

\put(1,8.){\vector(0,-1){.5}}\put(3,8.){\vector(0,-1){.5}}\put(5,8){\vector(0,-1){.5}}
\put(1,2.7){\vector(0,-1){.5}}\put(3,2.7){\vector(0,-1){.5}}\put(5,2.7){\vector(0,-1){.5}}

\put(1.2,7.8){130} \put(3.2,7.8){210} \put(5.2,7.8){220}
\put(1,1.8){200}\put(3.2,2.3){200} \put(5,1.8){200}

\put(1.2,6){1000} \put(2,6.5){750} \put(3.2,6){1000}
\put(4,6.5){750} \put(5.2,6){1000} \put(1.2,4){0} \put(3.2,4){0}
\put(5.2,4){0} \put(1.5,4.5){200} \put(3.5,4.5){200}
\put(1.5,2.5){0} \put(2.5,2){0} \put(4,2){0} \put(2.2,.5){40}
\put(2,0){\vector(0,1){.5}}

\end{picture}

The initial tree solution is

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

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

\put(1.,7.3){250} \put(3.,7.3){500} \put(5.,7.3){750}

\put(1.2,6){1000} \put(2,6.5){750} \put(3.2,6){1000}
\put(4,6.5){750} \put(5.2,6){1000} \put(1.2,4){0} \put(3.2,4){0}
\put(5.2,4){0}

\put(0,5){1250} \put(3.4,5){1500} \put(5.2,5){1750}
\put(0,3){1250} \put(3.2,3){1500} \put(5.2,3){1750}
\put(1,1){1250}

\put(.4,6){\framebox(.5,.3)} \put(.4,6){\makebox(.5,0.3){130}}
\put(1.9,5.5){\framebox(.5,.3)}
\put(1.9,5.5){\makebox(.5,0.3){30}} \put(2.4,6){\framebox(.5,.3)}
\put(2.4,6){\makebox(.5,0.3){180}} \put(3.9,5.5){\framebox(.5,.3)}
\put(3.9,5.5){\makebox(.5,0.3){20}} \put(4.4,6){\framebox(.5,.3)}
\put(4.4,6){\makebox(.5,0.3){200}} \put(.4,4){\framebox(.5,.3)}
\put(.4,4){\makebox(.5,0.3){160}} \put(2.4,4){\framebox(.5,.3)}
\put(2.4,4){\makebox(.5,0.3){200}} \put(4.4,4){\framebox(.5,.3)}
\put(4.4,4){\makebox(.5,0.3){200}} \put(1,1.5){\framebox(.5,.3)}
\put(1,1.5){\makebox(.5,0.3){40}}

\end{picture}

\begin{tabular}{cc}
$(i,j)$&$y_i+c_{ij}-y)j$\\ \hline (5,4)&450\\ (6,5)&450\\
(10,8)&$-250$\\ (10,9)&$-500$
\end{tabular}

Entering are (10,9)

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


\put(3,6.8){\vector(-1,-1){1.8}}\put(3,6.8){\vector(0,-1){1.6}}
\put(5,6.8){\vector(-1,-1){1.8}}\put(5,6.8){\vector(0,-1){1.6}}
\put(1,4.8){\vector(0,-1){1.8}} \put(5,4.8){\vector(0,-1){1.6}}
\put(2,1.2){\vector(-1,2){.8}}\put(2,1.2){\vector(3,2){2.8}}

\put(3.5,1.5){$\theta$} \put(5.2,6){$200-\theta$}
\put(5.2,4){$200-\theta$} \put(3.2,5.7){$20+\theta$}
\put(2,5.5){$180-\theta$} \put(1,5.7){$30+\theta$}
\put(0,4){$160+\theta$} \put(.7,2){$40-\theta$}

\end{picture}

$\theta=40$

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

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

\put(1.,7.3){250} \put(3.,7.3){500} \put(5.,7.3){750}

\put(1.2,6){1000} \put(2,6.5){750} \put(3.2,6){1000}
\put(4,6.5){750} \put(5.2,6){1000} \put(1.2,4){0} \put(3.2,4){0}
\put(5.2,4){0}

\put(0,5){1250} \put(3.4,5){1500} \put(5.2,5){1750}
\put(0,3){1250} \put(3.2,3){1500} \put(5.2,3){1750}
\put(1,1){1750}

\put(.4,6){\framebox(.5,.3)} \put(.4,6){\makebox(.5,0.3){130}}
\put(1.9,5.5){\framebox(.5,.3)}
\put(1.9,5.5){\makebox(.5,0.3){70}} \put(2.4,6){\framebox(.5,.3)}
\put(2.4,6){\makebox(.5,0.3){140}} \put(3.9,5.5){\framebox(.5,.3)}
\put(3.9,5.5){\makebox(.5,0.3){60}} \put(4.4,6){\framebox(.5,.3)}
\put(4.4,6){\makebox(.5,0.3){160}} \put(.4,4){\framebox(.5,.3)}
\put(.4,4){\makebox(.5,0.3){200}} \put(2.4,4){\framebox(.5,.3)}
\put(2.4,4){\makebox(.5,0.3){200}} \put(4.4,4){\framebox(.5,.3)}
\put(4.4,4){\makebox(.5,0.3){160}} \put(3.5,1.5){\framebox(.5,.3)}
\put(3.5,1.5){\makebox(.5,0.3){40}}


\end{picture}

\begin{tabular}{cc}
$(i,j)$&$y_i+c_{ij}-y_j$\\ \hline (5,4)&450\\ (6,5)&450\\
(10,7)&500\\ (10,8)&250
\end{tabular}

Optimal solution is

\begin{tabular}{l|ccc}
&Aug&Sept&Oct\\ \hline Production&200&200&160\\ Trans by
air&130&140&160\\ Trans by sea&70&60&0\\ \hline
\end{tabular}

$$z=430\times1000+130\times750=527500$$




\end{document}