%  Problem set 4: solutions
%  Combinatorial Optimization, SUAMI, summer 2015
%  Brian Kell <bkell@cmu.edu>

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.5truein \vsize=9truein
\pdfhorigin=1.5truein \pdfvorigin=1truein

% MetaPost stuff
\input supp-pdf
\def\fig#1{\convertMPtoPDF{#1}{1}{1}}
\def\midfig#1{{%
	\setbox0=\hbox{\fig{#1}}%
	\dimen0=0.5\ht0%
	\advance\dimen0 by-0.3\ht\strutbox
	\lower\dimen0\box0%
}}

% AMSFonts
\input amssym.tex

\font\titlefont=cmbx12  \font\smfont=cmr8  \font\transposefont=cmss8 at6pt

\newcount\pno \pno=0
\def\problem{\global\advance\pno by1%
	\medbreak\noindent{\llap{\bf\the\pno.\enspace}}\ignorespaces}
\def\solution{\medskip\noindent\llap{$\triangleright$\bf\phantom.\enspace}{\bf Solution.}\enspace\ignorespaces}

% Pilfered from an example on page 106 of the TeXbook
\def\qed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\hbox{\vrule\vbox to6pt{\hrule\hbox to5.2pt{\hss}\vfil\hrule}\vrule}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}
\def\subqed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\raise2pt\hbox{\vrule height4pt width4pt depth0pt}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}

\newdimen\pivotwidth  \newdimen\pivotdepth
\def\pivot#1{%
	\setbox0=\hbox{\vphantom/$#1$}
	\pivotdepth=\dp0
	\setbox0=\hbox{\vbox{\vskip1pt\hbox{\hskip2pt\box0\hskip2pt}\vskip1pt}}%
	\pivotwidth=\wd0  \advance\pivotwidth by0.8pt
	\lower\pivotdepth\hbox{\vbox{%
		\vskip-1.4pt
		\hrule width\pivotwidth height0.4pt depth0.0pt
		\hbox{%
			\vrule height\ht0 depth\dp0 width0.4pt
			\copy0
			\vrule height\ht0 depth\dp0 width0.4pt
		}%
		\hrule width\pivotwidth height0.4pt depth0.0pt
		\vskip-1.4pt
	}\hskip-2.4pt}%
}

\def\frac#1#2{{\textstyle{{#1}\over{#2}}}}
\def\R{{\mathord{\Bbb R}}}
\def\transpose{{\raise0.5pt\hbox{\transposefont T}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Problem set~4: solutions}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Consider a project consisting of the following nine activities.
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut#\hfil\quad&&\hfil\strut#\hfil\quad\cr
&Immediate&Usual time&Crash time&Cost per day\cr
Activity&prerequisites&(days)&(days)&to speed up\cr
\noalign{\vskip2pt\hrule\vskip2pt}
A&---&2&---&---\cr
B&---&6&3&\$180\cr
C&A&4&2&\$150\cr
D&B&2&1&\$200\cr
E&B&4&1&\$\phantom075\cr
F&C, D&3&1&\$250\cr
G&D&1&---&---\cr
H&F&3&2&\$100\cr
I&E, F, G&4&1&\$140\cr}}$$

\item{(a)} Draw a CPM network for this project.

\smallskip

\item{(b)} Using the {\it usual times\/}:

\smallskip

\itemitem{(i)} Determine the earliest and latest times for each node.

\smallskip

\itemitem{(ii)} Determine the float for each activity.

\smallskip

\itemitem{(iii)} Determine the critical path.

\smallskip

\item{(c)} Formulate a linear program to determine the least expensive way to
reduce the length of the project by 4~days. Solve your linear program (with
Maple or otherwise) and interpret your results.

\smallskip

\item{(d)} Formulate a linear program to determine the shortest possible
completion time that can be achieved with a budget of \$900. Solve your linear
program and interpret your results.

\solution

\medskip

\item{(a)} A CPM network for this project is shown below. Solid arrows
represent activities. The edge label for an activity that cannot be sped up
gives the duration of the activity; the label for an activity that can be sped
up gives the interval of possible durations (from the crash time to the usual
time) and the per-day speedup cost. This drawing also incorporates the
information from part~(b): the earliest time for each node (using the usual
times) is shown in green above the node, the latest time for each node is shown
in red below the node, the float for each activity is shown in blue below the
corresponding arrow, and the critical path is highlighted in yellow.
$$\fig{pset04-solns-1.mps}$$

\goodbreak

\item{(b)} Let $u_i$ denote the usual time of activity~$i$. Let $e_j$~and~$l_j$
denote the earliest time and latest time of node~$j$, respectively, using the
usual times.

\smallskip

\itemitem{(i)} The earliest time of node~0 is~0. For $j\not=0$ the earliest
time of node~$j$ is found as follows: for each incoming edge (including dummy
edges), add the earliest time of the edge's start node to the duration (i.e.,
the usual time) of the corresponding activity; and then take the maximum of all
of these sums. Note that the duration of a dummy edge is zero.
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut#\hfil\quad&\vrule#&\quad\strut$#$\hfil\quad\cr
Node&&\omit\quad\strut Earliest time\hfil\quad\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
\phantom00&&0\cr
\phantom01&&e_0+u_{\rm A}=0+2=2\cr
\phantom02&&e_0+u_{\rm B}=0+6=6\cr
\phantom03&&e_1+u_{\rm C}=2+4=6\cr
\phantom04&&e_2+u_{\rm D}=6+2=8\cr
\phantom05&&e_2+u_{\rm E}=6+4=10\cr
\phantom06&&\max\{e_3+0,e_4+0\}=\max\{6,8\}=8\cr
\phantom07&&e_6+u_{\rm F}=8+3=11\cr
\phantom08&&e_4+u_{\rm G}=8+1=9\cr
\phantom09&&e_7+u_{\rm H}=11+3=14\cr
10&&\max\{e_5+0,e_7+0,e_8+0\}=\max\{10,11,9\}=11\cr
11&&e_{10}+u_{\rm I}=11+4=15\cr
12&&\max\{e_9+0,e_{11}+0\}=\max\{14,15\}=15\cr
}}$$

\goodbreak

\itemitem{} The latest time of the last node is equal to its earliest time.
For each other node, the latest time is found as follows: for each outgoing
edge (including dummy edges), subtract the duration of the corresponding
activity from the latest time of the edge's end node; and then take the
minimum of all of these differences.
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut#\hfil\quad&\vrule#&\quad\strut$#$\hfil\quad\cr
Node&&\omit\quad\strut Latest time\hfil\quad\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
12&&e_{12}=15\cr
11&&l_{12}-0=15\cr
10&&l_{11}-u_{\rm I}=15-4=11\cr
\phantom09&&l_{12}-0=15\cr
\phantom08&&l_{10}-0=11\cr
\phantom07&&\min\{l_9-u_{\rm H},l_{10}-0\}=\min\{15-3,11\}=11\cr
\phantom06&&l_{11}-u_{\rm F}=11-3=8\cr
\phantom05&&l_{10}-0=11\cr
\phantom04&&\min\{l_6-0,l_8-u_{\rm G}\}=\min\{8,11-1\}=8\cr
\phantom03&&l_6-0=8\cr
\phantom02&&\min\{l_4-u_{\rm D},l_5-u_{\rm E}\}=\min\{8-2,11-4\}=6\cr
\phantom01&&l_3-u_{\rm C}=8-4=4\cr
\phantom00&&\min\{l_1-u_{\rm A},l_2-u_{\rm B}\}=\min\{4-2,6-6\}=0\cr
}}$$

\goodbreak

\itemitem{(ii)} The float of an activity is equal to the latest time of its
end node, minus the earliest time of its start node, minus its duration.
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut#\hfil\quad&\vrule#&\quad\strut$#$\hfil\quad\cr
Activity&&\omit\quad\strut Float\hfil\quad\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
A&&l_1-e_0-u_{\rm A}=4-0-2=2\cr
B&&l_2-e_0-u_{\rm B}=6-0-6=0\cr
C&&l_3-e_1-u_{\rm C}=8-2-4=2\cr
D&&l_4-e_2-u_{\rm D}=8-6-2=0\cr
E&&l_5-e_2-u_{\rm E}=11-6-4=1\cr
F&&l_7-e_6-u_{\rm F}=11-8-3=0\cr
G&&l_8-e_4-u_{\rm G}=11-8-1=2\cr
H&&l_9-e_7-u_{\rm H}=15-11-3=1\cr
I&&l_{11}-e_{10}-u_{\rm I}=15-11-4=0\cr
}}$$

\goodbreak

\itemitem{} For completeness, we can also compute the floats for the dummy
activities, even though they do not represent actual activities in the project:
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut#\hfil\quad&\vrule#&\quad\strut$#$\hfil\quad\cr
Dummy activity&&\omit\quad\strut Float\hfil\quad\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
$3\to6$&&l_6-e_3-0=8-6-0=2\cr
$4\to6$&&l_6-e_4-0=8-8-0=0\cr
$\phantom05\to10$&&l_{10}-e_5-0=11-10-0=1\cr
$\phantom07\to10$&&l_{10}-e_7-0=11-11-0=0\cr
$\phantom08\to10$&&l_{10}-e_8-0=11-9-0=2\cr
$\phantom09\to12$&&l_{12}-e_9-0=15-14-0=1\cr
$11\to12$&&l_{12}-e_{11}-0=15-15-0=0\cr
}}$$

\itemitem{(iii)} A critical path is a path from the beginning of the project
(node~0) to the completion of the project (node~12) consisting entirely of
critical activities. There is a unique critical path in this project,
consisting of the activities B---D---F---I.

\medbreak

\item{(c,\thinspace d)} First we define the variables and their domains. For
$i\in\{\rm B,C,D,E,F,H,I\}$, let $d_i$ denote the duration of activity~$i$
(possibly sped up from its usual time). For $0\le j\le12$, let $t_j$ denote the
time at which node~$j$ occurs. All of these variables are nonnegative.

\item{} \hskip\parindent Next we list the network constraints, because we will
need the network constrains in any linear program for this project, and these
constraints come from the CPM network we drew in part~(a). Each activity gives
us a sequence constraint:
$$\eqalign{
	t_1-t_0&\ge2\cr
	t_2-t_0&\ge d_{\rm B}\cr
	t_3-t_1&\ge d_{\rm C}\cr
}\qquad\qquad\eqalign{
	t_4-t_2&\ge d_{\rm D}\cr
	t_5-t_2&\ge d_{\rm E}\cr
	t_7-t_6&\ge d_{\rm F}\cr
}\qquad\qquad\eqalign{
	t_8-t_4&\ge1\cr
	t_9-t_7&\ge d_{\rm H}\cr
	t_{11}-t_{10}&\ge d_{\rm I}\cr
}$$
Each dummy edge gives us a dummy constraint:
$$\eqalign{
	t_6-t_3&\ge0\cr
	t_6-t_4&\ge0\cr
	\cr
}\qquad\qquad\eqalign{
	t_{10}-t_5&\ge0\cr
	t_{10}-t_7&\ge0\cr
	t_{10}-t_8&\ge0\cr
}\qquad\qquad\eqalign{
	t_{12}-t_9&\ge0\cr
	t_{12}-t_{11}&\ge0\cr
	\cr
}$$
Each activity that can be sped up gives us a pair of duration constraints:
$$\openup1\jot\vbox{%
	\hbox{\strut$3\le d_{\rm B}\le 6$}%
	\hbox{\strut$2\le d_{\rm C}\le 4$}%
	\hbox{\strut$1\le d_{\rm D}\le 2$}%
}\qquad\qquad\vbox{%
	\hbox{\strut$1\le d_{\rm E}\le 4$}%
	\hbox{\strut$1\le d_{\rm F}\le 3$}%
	\hbox{\strut}%
}\qquad\qquad\vbox{%
	\hbox{\strut$2\le d_{\rm H}\le 3$}%
	\hbox{\strut$1\le d_{\rm I}\le 4$}%
	\hbox{\strut}%
}$$

\goodbreak

\item{} Now, our objective in part~(c) is to minimize the total speedup cost,
which is
$$180(6-d_{\rm B})+150(4-d_{\rm C})+200(2-d_{\rm D})+75(4-d_{\rm E})
	+250(3-d_{\rm F})+100(3-d_{\rm H})+140(4-d_{\rm I}).$$
The usual project completion time is 15~days, so reducing the length of the
project by 4~days means completing it in 11~days, which gives us the deadline
constraint $t_{12}\le11$. Therefore our linear program for part~(c) is
$$\eqalign{
	{\rm minimize}\quad&\hbox{[total speedup cost]}\cr
	{\rm subject\ to}\quad&\hbox{[all network constraints]}\cr
	&t_{12}\le11\cr
	&\hbox{all variables nonnegative.}\cr
}$$

\goodbreak

\item{} Our objective in part~(d) is to minimize the project completion time,
which is~$t_{12}$, subject to the budget constraint
$\hbox{[total speedup cost]}\le900$. So our linear program for part~(d) is
$$\eqalign{
	{\rm minimize}\quad&t_{12}\cr
	{\rm subject\ to}\quad&\hbox{[all network constraints]}\cr
	&\hbox{[total speedup cost]}\le900\cr
	&\hbox{all variables nonnegative.}\cr
}$$

\goodbreak

\item{} The following Maple worksheet solves both of these linear programs. (It
is convenient to solve them together because they share almost all of their
constraints.)

{\smallskip
\raggedright \advance\hsize by-\parindent \hangindent=2\parindent
		\hangafter=0  \noindent\tt
> restart;\hfil\break
> with(Optimization);
$$\displaylines{
	[\it ImportMPS,Interactive,LPSolve,LSSolve,Maximize,Minimize,NLPSolve,\hfill\cr
	\qquad\it QPSolve]\hfill\cr
}$$
> sequence:=[t1-t0>=2,t2-t0>=dB,t3-t1>=dC,t4-t2>=dD,t5-t2>=dE,\hfil\break
	\strut\qquad t7-t6>=dF,t8-t4>=1,t9-t7>=dH,t11-t10>=dI];
$$\displaylines{
	\it sequence:=[{\rm2}\le t1-t0,dB\le t2-t0,dC\le t3-t1,dD\le t4-t2,\hfill\cr
	\qquad\it dE\le t5-t2,dF\le t7-t6,{\rm1}\le t8-t4,dH\le t9-t7,dI\le t11-t10]\hfill\cr
}$$
> dummy:=[t6-t3>=0,t6-t4>=0,t10-t5>=0,t10-t7>=0,t10-t8>=0,\hfil\break
	\strut\qquad t12-t9>=0,t12-t11>=0];
$$\displaylines{
	\it dummy:=[{\rm0}\le t6-t3,{\rm0}\le t6-t4,{\rm0}\le t10-t5,{\rm0}\le t10-t7,
		{\rm0}\le t10-t8,\hfill\cr
	\qquad0\le\it t12-t9,{\rm0}\le t12-t11]\hfill\cr
}$$
> duration:=[3<=dB,dB<=6,2<=dC,dC<=4,1<=dD,dD<=2,1<=dE,dE<=4,\hfil\break
	\strut\qquad1<=dF,dF<=3,2<=dH,dH<=3,1<=dI,dI<=4];
$$\displaylines{
	{\it duration}:=[3\le{\it dB,dB}\le6,2\le{\it dC,dC}\le4,1\le{\it dD,dD}\le2,
		1\le{\it dE},\hfill\cr
	\qquad{\it dE}\le4,1\le{\it dF,dF}\le3,2\le{\it dH,dH}\le3,1\le{\it dI,dI}\le4]\hfill\cr
}$$
> network:=[op(sequence),op(dummy),op(duration)];
$$\displaylines{
	\it network:=[{\rm2}\le t1-t0,dB\le t2-t0,dC\le t3-t1,dD\le t4-t2,dE\le t5-t2,\hfill\cr
	\qquad\it dF\le t7-t6,{\rm1}\le t8-t4,dH\le t9-t7,dI\le t11-t10,{\rm0}\le t6-t3,\hfill\cr
	\qquad0\le\it t6-t4,{\rm0}\le t10-t5,{\rm0}\le t10-t7,{\rm0}\le t10-t8,{\rm0}\le\it t12-t9,\hfill\cr
	\qquad0\le{\it t12-t11},3\le{\it dB,dB}\le6,2\le{\it dC,dC}\le4,1\le{\it dD,dD}\le2,\hfill\cr
	\qquad1\le{\it dE,dE}\le4,1\le{\it dF,dF}\le3,2\le{\it dH,dH}\le3,1\le{\it dI,dI}\le4]\hfill\cr
}$$
> cost:=(dB,dC,dD,dE,dF,dH,dI)->180*(6-dB)+150*(4-dC)\hfil\break
	\strut\qquad+200*(2-dD)+75*(4-dE)+250*(3-dF)+100*(3-dH)+140*(4-dI);
$$\displaylines{
	{\it cost}:=({\it dB,dC,dD,dE,dF,dH,dI})\to3990-180\,{\it dB}-150\,{\it dC}-200\,{\it dD}\hfill\cr
	\qquad{}-75\,{\it dE}-250\,{\it dF}-100\,{\it dH}-140\,{\it dI}\hfill\cr
}$$
> constraintsC:=[op(network),t12<=11];
$$\displaylines{
	\it constraintsC:=[{\rm2}\le t1-t0,dB\le t2-t0,dC\le t3-t1,dD\le t4-t2,\hfill\cr
	\qquad\it dE\le t5-t2,dF\le t7-t6,{\rm1}\le t8-t4,dH\le t9-t7,dI\le t11-t10,\hfill\cr
	\qquad0\le t6-t3,{\rm0}\le\it t6-t4,{\rm0}\le t10-t5,{\rm0}\le t10-t7,{\rm0}\le t10-t8,\hfill\cr
	\qquad0\le\it t12-t9,{\rm0}\le{\it t12-t11},3\le{\it dB,dB}\le6,2\le{\it dC,dC}\le4,1\le{\it dD},\hfill\cr
	\qquad{\it dD}\le2,1\le{\it dE,dE}\le4,1\le{\it dF,dF}\le3,2\le{\it dH,dH}\le3,1\le{\it dI},\hfill\cr
	\qquad{\it dI}\le4,{\it t12}\le11]\hfill\cr
}$$
> LPSolve(cost(dB,dC,dD,dE,dF,dH,dI),constraintsC,\hfil\break
	\strut\qquad assume=nonnegative);
$$\displaylines{
	\bigl[739.99999883316,[{\it dB}=4.00000000068840,{\it dC}=4.,\hfill\cr
	\qquad{\it dD}=2.00000000034420,{\it dE}=4.,{\it dF}=3.,{\it dH}=2.00000000275359,\hfill\cr
	\qquad{\it dI}=2.00000000499089,{\it t0}=0.,{\it t1}=2.,{\it t10}=8.99999999535331,\hfill\cr
	\qquad{\it t11}=11.0000000003442,{\it t12}=11.,{\it t2}=3.99999999965580,\hfill\cr
	\qquad{\it t3}=5.99999999896740,{\it t4}=5.99999999896740,{\it t5}=8.99999999569751,\hfill\cr
	\qquad{\it t6}=5.99999999862320,{\it t7}=8.99999999759060,{\it t8}=6.99999999896740,\hfill\cr
	\qquad{\it t9}=11.]\bigr]\hfill\cr
}$$
> constraintsD:=[op(network),cost(dB,dC,dD,dE,dF,dH,dI)<=900];
$$\displaylines{
	\it constraintsD:=[{\rm2}\le t1-t0,dB\le t2-t0,dC\le t3-t1,dD\le t4-t2,\hfill\cr
	\qquad\it dE\le t5-t2,dF\le t7-t6,{\rm1}\le t8-t4,dH\le t9-t7,dI\le t11-t10,\hfill\cr
	\qquad0\le t6-t3,{\rm0}\le\it t6-t4,{\rm0}\le t10-t5,{\rm0}\le t10-t7,{\rm0}\le t10-t8,\hfill\cr
	\qquad0\le\it t12-t9,{\rm0}\le{\it t12-t11},3\le{\it dB,dB}\le6,2\le{\it dC,dC}\le4,1\le{\it dD},\hfill\cr
	\qquad{\it dD}\hss\le\hss2,1\hss\le\hss{\it dE,dE}\hss\le\hss4,1\hss\le\hss{\it dF,dF}\hss\le\hss3,2\hss\le\hss{\it dH,dH}\hss\le\hss3,1\hss\le\hss{\it dI},{\it dI}\hss\le\hss4,\hfill\cr
	\qquad-180{\it dB}-150{\it dC}-200{\it dD}-75{\it dE}-250{\it dF}-100{\it dH}-140{\it dI}\le-3090]\hfill\cr
}$$
> LPSolve(t12,constraintsD,assume=nonnegative);
$$\displaylines{
	\bigl[10.3599999956080,[{\it dB}=4.00000000034420,{\it dC}=4.,\hfill\cr
	\qquad{\it dD}=2.00000000000000,{\it dE}=4.,{\it dF}=2.35999999801741,{\it dH}=2.,\hfill\cr
	\qquad{\it dI}=2.00000000309779,{\it t0}=0.,{\it t1}=2.,{\it t10}=8.35999999560802,\hfill\cr
	\qquad{\it t11}=10.3599999956080,{\it t12}=10.3599999956080,{\it t2}=4.,\hfill\cr
	\qquad{\it t3}=5.99999999965580,{\it t4}=5.99999999965580,{\it t5}=7.99999999965580,\hfill\cr
	\qquad{\it t6}=5.99999999965580,{\it t7}=8.35999999664062,{\it t8}=6.99999999965580,\hfill\cr
	\qquad{\it t9}=10.3599999966406]\bigr]\hfill\cr
}$$

}

\item{} \hskip\parindent The optimal activity durations in part~(c) are
$d_{\rm B}=4$, $d_{\rm C}=4$, $d_{\rm D}=2$, $d_{\rm E}=4$, $d_{\rm F}=3$,
$d_{\rm H}=2$, and $d_{\rm I}=2$. This means that the least expensive way to
reduce the length of the project by 4~days is to speed up activity~B by 2~days
from its usual time, activity~H by 1~day from its usual time, and activity~I by
2~days from its usual time. The optimal objective value (i.e., the minimum
total speedup cost) is \$740.

\item{} \hskip\parindent The optimal activity durations in part~(d) are
$d_{\rm B}=4$, $d_{\rm C}=4$, $d_{\rm D}=2$, $d_{\rm E}=4$, $d_{\rm F}=2.36$,
$d_{\rm H}=2$, and $d_{\rm I}=2$, with an optimal objective value of
10.36~days. This means that the best way to apply the budget of \$900 in order
to reduce the project completion time is to speed up activity~B by 2~days from
its usual time, activity~F by 0.64~day from its usual time, activity~H by 1~day
from its usual time, and activity~I by 2~days from its usual time. \qed

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Rural Residence, Inc.\ (RRI) manufactures and builds prefab log homes.
The logs are cut at their plant and delivered to the site. All other materials,
such as roofing, doors, windows, etc., are purchased from other companies. The
tasks involved in building one of their homes are shown in the table below.
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut#&\enspace\strut#\hfil&\hfil\strut#\hfil\quad
	&&\hfil\strut#\hfil\quad\cr
&&Immediate&Usual time&Crash time&Cost per day\cr
\multispan2\hfil\strut Activity\hfil&prerequisites&(days)&(days)&to speed up\cr
\noalign{\vskip2pt\hrule\vskip2pt}
A.&Prepare site&---&2&---&---\cr
B.&Adjust design to site&A&2&1&\$300\cr
C.&Cut logs for house&A&3&2&\$250\cr
D.&Obtain other materials&B&7&---&---\cr
E.&Excavate basement&B&2&1&\$700\cr
F.&Pour foundation&E&3&2&\$350\cr
G.&Ship logs&C&5&3&\$125\cr
H.&Assemble logs&F, G&8&5&\$150\cr
I.&Complete roof, doors, etc.&D, H&5&4&\$250\cr
J.&Prepare for utilities&D, H&5&3&\$300\cr
K.&Connect utilities&J&2&---&---\cr
L.&Finish interior&J&7&4&\$200\cr
M.&Landscape lot&I, K&2&---&---\cr}}$$
In addition to the tasks above, RRI must maintain a trailer and security guard
at the job site from the time that the excavation of the basement begins until
the interior is finished, at a cost of \$210 per day.

Determine a project schedule that will minimize the total cost of the project.

\solution A CPM network for this project is shown below. Note that we can reuse
node~10 as the start node for both activities I~and~J, because they have the
same prerequisites. The excavation of the basement (activity~E) begins at
node~2, and the finishing of the interior (activity~L) ends at node~14, so the
trailer and security guard must be maintained between the two times represented
by those nodes. $$\fig{pset04-solns-2.mps}$$

We will formulate a linear program for this problem, based on the CPM network.
For $i\in\{\rm B,C,E,F,G,H,I,J,L\}$, let $d_i$ denote the duration of
activity~$i$ (possibly sped up from its usual time). For $0\le j\le17$, let
$t_j$ denote the time at which node~$j$ occurs. All of these variables are
nonnegative.

The network constraints come from the CPM network. Each activity gives us a
sequence constraint:
$$\eqalign{
	t_1-t_0&\ge2\cr
	t_2-t_1&\ge d_{\rm B}\cr
	t_3-t_1&\ge d_{\rm C}\cr
	t_4-t_2&\ge7\cr
	t_5-t_2&\ge d_{\rm E}\cr
}\qquad\qquad\eqalign{
	t_6-t_5&\ge d_{\rm F}\cr
	t_7-t_3&\ge d_{\rm G}\cr
	t_9-t_8&\ge d_{\rm H}\cr
	t_{11}-t_{10}&\ge d_{\rm I}\cr
	\cr
}\qquad\qquad\eqalign{
	t_{12}-t_{10}&\ge d_{\rm J}\cr
	t_{13}-t_{12}&\ge2\cr
	t_{14}-t_{12}&\ge d_{\rm L}\cr
	t_{16}-t_{15}&\ge2\cr
	\cr
}$$
Each dummy edge gives us a dummy constraint:
$$\eqalign{
	t_8-t_6&\ge0\cr
	t_8-t_7&\ge0\cr
	t_{10}-t_4&\ge0\cr
}\qquad\qquad\eqalign{
	t_{10}-t_9&\ge0\cr
	t_{15}-t_{11}&\ge0\cr
	t_{15}-t_{13}&\ge0\cr
}\qquad\qquad\eqalign{
	t_{17}-t_{14}&\ge0\cr
	t_{17}-t_{16}&\ge0\cr
	\cr
}$$
Each activity that can be sped up gives us a pair of duration constraints:
$$\openup1\jot\vbox{%
	\hbox{\strut$1\le d_{\rm B}\le 2$}%
	\hbox{\strut$2\le d_{\rm C}\le 3$}%
	\hbox{\strut$1\le d_{\rm E}\le 2$}%
}\qquad\qquad\vbox{%
	\hbox{\strut$2\le d_{\rm F}\le 3$}%
	\hbox{\strut$3\le d_{\rm G}\le 5$}%
	\hbox{\strut$5\le d_{\rm H}\le 8$}%
}\qquad\qquad\vbox{%
	\hbox{\strut$4\le d_{\rm I}\le 5$}%
	\hbox{\strut$3\le d_{\rm J}\le 5$}%
	\hbox{\strut$4\le d_{\rm L}\le 7$}%
}$$

\noindent Our objective is to minimize the total project cost. The portion of
the project cost under our control is the speedup cost, plus the cost of
maintaining the trailer and security guard from the time of node~2 until the
time of node~14 at \$210 per day. Therefore, the quantity we aim to minimize is
$$\displaylines{
	\quad300(2-d_{\rm B})+250(3-d_{\rm C})+700(2-d_{\rm E})+350(3-d_{\rm F})
		+125(5-d_{\rm G})\quad\hfill\cr
	\hfill\quad{}+150(8-d_{\rm H})+250(5-d_{\rm I})+300(5-d_{\rm J})
		+200(7-d_{\rm L})+210(t_{14}-t_2).\quad\cr
}$$
Our linear program is
$$\eqalign{
	{\rm minimize}\quad&\hbox{[cost]}\cr
	{\rm subject\ to}\quad&\hbox{[all network constraints]}\cr
	&\hbox{all variables nonnegative.}\cr
}$$

\noindent The following Maple worksheet solves this linear program.

{\smallskip
\raggedright \advance\hsize by-\parindent \hangindent=\parindent
		\hangafter=0  \noindent\tt
> restart;\hfil\break
> with(Optimization);
$$\displaylines{
	[\it ImportMPS,Interactive,LPSolve,LSSolve,Maximize,Minimize,NLPSolve,\hfill\cr
	\qquad\it QPSolve]\hfill\cr
}$$
> sequence:=[t1-t0>=2,t2-t1>=dB,t3-t1>=dC,t4-t2>=7,t5-t2>=dE,\hfil\break
	\strut\qquad t6-t5>=dF,t7-t3>=dG,t9-t8>=dH,t11-t10>=dI,t12-t10>=dJ,\hfil\break
	\strut\qquad t13-t12>=2,t14-t12>=dL,t16-t15>=2];
$$\displaylines{
	\it sequence:=[{\rm2}\le t1-t0,dB\le t2-t1,dC\le t3-t1,{\rm7}\le t4-t2,dE\le t5-t2,\hfill\cr
	\qquad\it dF\le t6-t5,dG\le t7-t3,dH\le t9-t8,dI\le t11,t10,dJ\le t12-t10,\hfill\cr
	\qquad2\le\it t13-t12,dL\le t14-t12,{\rm2}\le t16-t15]\hfill\cr
}$$
> dummy:=[t8-t6>=0,t8-t7>=0,t10-t4>=0,t10-t9>=0,t15-t11>=0,\hfil\break
	\strut\qquad t15-t13>=0,t17-t14>=0,t17-t16>=0];
$$\displaylines{
	\it dummy:=[{\rm0}\le t8-t6,{\rm0}\le t8-t7,{\rm0}\le t10-t4,{\rm0}\le t10-t9,{\rm0}\le t15-t11,\hfill\cr
	\qquad0\le\it t15-t13,{\rm0}\le t17-t14,{\rm0}\le t17-t16]\hfill\cr
}$$
> duration:=[1<=dB,dB<=2,2<=dC,dC<=3,1<=dE,dE<=2,2<=dF,dF<=3,3<=dG,\hfil\break
	\strut\qquad dG<=5,5<=dH,dH<=8,4<=dI,dI<=5,3<=dJ,dJ<=5,4<=dL,dL<=7];
$$\displaylines{
	{\it duration}:=[1\le{\it dB,dB}\le2,2\le{\it dC,dC}\le3,1\le{\it dE,dE}\le2,2\le{\it dF,dF}\le3,\hfill\cr
	\qquad3\le{\it dG,dG}\le5,5\le{\it dH,dH}\le8,4\le{\it dI,dI}\le5,3\le{\it dJ,dJ}\le5,4\le{\it dL},\hfill\cr
	\qquad{\it dL}\le7]\hfill\cr
}$$
> network:=[op(sequence),op(dummy),op(duration)];
$$\displaylines{
	\it network:=[{\rm2}\le t1-t0,dB\le t2-t1,dC\le t3-t1,{\rm7}\le t4-t2,dE\le t5-t2,\hfill\cr
	\qquad\it dF\le t6-t5,dG\le t7-t3,dH\le t9-t8,dI\le t11,t10,dJ\le t12-t10,\hfill\cr
	\qquad2\le\it t13-t12,dL\le t14-t12,{\rm2}\le t16-t15,{\rm0}\le t8-t6,{\rm0}\le t8-t7,\hfill\cr
	\qquad0\le\it t10-t4,{\rm0}\le t10-t9,{\rm0}\le t15-t11,0\le\it t15-t13,{\rm0}\le t17-t14,\hfill\cr
	\qquad0\le\it t17-t16,\rm1\le{\it dB,dB}\le2,2\le{\it dC,dC}\le3,1\le{\it dE,dE}\le2,2\le{\it dF},\hfill\cr
	\qquad{\it dF}\le3,3\le{\it dG,dG}\le5,5\le{\it dH,dH}\le8,4\le{\it dI,dI}\le5,3\le{\it dJ,dJ}\le5,\hfill\cr
	\qquad4\le{\it dL},{\it dL}\le7]\hfill\cr
}$$
> cost:=(dB,dC,dE,dF,dG,dH,dI,dJ,dL,t2,t14)->300*(2-dB)+250*(3-dC)\hfil\break
	\strut\qquad+700*(2-dE)+350*(3-dF)+125*(5-dG)+150*(8-dH)+250*(5-dI)\hfil\break
	\strut\qquad+300*(5-dJ)+200*(7-dL)+210*(t14-t2);
$$\displaylines{
	{\it cost}:=({\it dB,dC,dE,dF,dG,dH,dI,dJ,dL,t2,t14})\to9775-300\,{\it dB}-250\,{\it dC}\hfill\cr
	\qquad{}-700\,{\it dE}-350\,{\it dF}-125\,{\it dG}-150\,{\it dH}-250\,{\it dI}-300\,{\it dJ}-200\,{\it dL}+210\,{\it t14}-210\,{\it t2}\hfill\cr
}$$
> LPSolve(cost(dB,dC,dE,dF,dG,dH,dI,dJ,dL,t2,t14),network,\hfil\break
	\strut\qquad assume=nonnegative);
$$\displaylines{
	\bigl[5039.99999877809,[{\it dB}=2.00000000137680,{\it dC}=3.00000000034420,{\it dE}=2.,\hfill\cr
	\qquad{\it dF}=3.,{\it dG}=5.,{\it dH}=5.,{\it dI}=5.,{\it dJ}=5.,{\it dL}=4.,{\it t0}=0.,{\it t1}=2.,\hfill\cr
	\qquad{\it t10}=14.9999999977627,{\it t11}=21.9999999974185,{\it t12}=19.9999999974185,\hfill\cr
	\qquad{\it t13}=21.9999999974185,{\it t14}=23.9999999970743,{\it t15}=21.9999999970743,\hfill\cr
	\qquad{\it t16}=23.9999999970743,{\it t17}=23.9999999967301,{\it t2}=5.00000000051630,\hfill\cr
	\qquad{\it t3}=4.99999999931160,{\it t4}=14.9999999981069,{\it t5}=6.99999999948370,\hfill\cr
	\qquad{\it t6}=9.99999999845110,{\it t7}=9.99999999827900,{\it t8}=9.99999999810690,\hfill\cr
	\qquad{\it t9}=14.9999999977627]\bigr]\hfill\cr
}$$

}

The optimal activity durations are $d_{\rm B}=2$, $d_{\rm C}=3$, $d_{\rm E}=2$,
$d_{\rm F}=3$, $d_{\rm G}=5$, $d_{\rm H}=5$, $d_{\rm I}=5$, $d_{\rm J}=5$, and
$d_{\rm L}=4$. This means that the way to minimize the total cost of the
project is to speed up each of activities H~and~L by 3~days from their usual
times. The optimal objective value (i.e., the minimum total speedup cost and
maintenance cost for the trailer and security guard) is \$5040. The project
will be completed in 24~days under this schedule. \qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem The ABC~Co.\ manufactures its product in two plants, A~and~B, and
sells its product in four markets, W,~X, Y, and~Z. The capacity in Plant~A is
300~units, and in Plant~B it is 350~units. The demands and per-unit shipping
costs for the four markets are shown below.
$$\vbox{\offinterlineskip
\halign{\hfil\strut#\enspace&&\enspace\hfil\strut#\hfil\enspace\cr
&\multispan4\hfil\strut Markets\hfil\cr
&W&X&Y&Z\cr
\omit&\omit\leaders\hrule\hfil&\omit\leaders\hrule\hfil&\omit\leaders\hrule\hfil&\omit\leaders\hrule\hfil\cr
\noalign{\vskip2pt}
Demand:&155&230&225&160\cr
Per-unit shipping cost from~A:&\$10&\$20&\$15&\$25\cr
Per-unit shipping cost from~B:&\$\phantom05&\$15&\$10&\$20\cr}}$$
The usual per-unit labor cost is \$95 in either plant. The other costs per unit
are \$50 in Plant~A and \$70 in Plant~B\null. Overtime labor can be hired only
at Plant~A at a per-unit cost of~\$140. If the capacity is not adequate to meet
demand, additional items can be manufactured at Plant~A using overtime labor.

\smallskip

\item{(a)} Formulate a linear program to determine how ABC should schedule its
production to meet all demand while minimizing its total costs. Solve your LP
(with Maple or otherwise) and interpret the results.

\smallskip

\item{(b)} Solve this problem using the specialized transportation algorithm
described in class. Compare this result to your result from part~(a).

\solution We can view this as an instance of the transportation problem. We
have three origins: usual production in Plant~A, usual production in Plant~B,
and overtime production in Plant~A. We shall label these origins A,~B, and~O,
respectively. We have four destinations: the markets W,~X, Y, and~Z.

The total demand is $155+230+225+160=770$ units, but the total supply at
origins A~and~B (that~is, the total capacity of both plants) is only 650~units.
Therefore, we will need to produce 120~units using overtime labor, so the
supply at origin~O is~120.

The total per-unit production costs at each origin are \$145 at~A, \$165 at~B,
and \$190 at~O. Combining these with the shipping costs, we get the per-unit
costs from each source to each destination shown in the following table.
$$\vbox{\offinterlineskip
\halign{\enspace\hfil\strut#\hfil\enspace&\vrule#&&\enspace\hfil\strut#\hfil\enspace\cr
&&W&X&Y&Z\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
A&&\$155&\$165&\$160&\$170\cr
B&&\$170&\$180&\$175&\$185\cr
O&&\$200&\$210&\$205&\$215\cr
}}$$

\item{(a)} For $i\in\{\rm A,B,O\}$ and $j\in\{\rm W,X,Y,Z\}$, let $x_{ij}$
denote the number of units to be produced at origin~$i$ and shipped to
market~$j$. All of these variables are nonnegative.

\item{} \hskip\parindent Our objective is to minimize total cost, subject to
the constraints that the supply at each origin is exhausted and the demand at
each destination is satisfied. Thus we have the following linear program.
$$\def\\#1#2{\setbox0=\hbox{$x_{\rm OW}$}\hbox to\wd0{$x_{\rm #1#2}$\hfil}}
\eqalign{
	{\rm maximize}\quad\phantom{{}+{}}155\\AW+165\\AX+160\\AY+170\\AZ&\cr
	{}+170\\BW+180\\BX+175\\BY+185\\BZ&\cr
	{}+200\\OW+210\\OX+205\\OY+215\\OZ&\cr
	{\rm subject\ to}\quad\phantom{{}+000\\xx+000\\xx+000\\xx+000\\xx}
		\llap{$\\AW+\\AX+\\AY+\\AZ$}&=300\cr
	\\BW+\\BX+\\BY+\\BZ&=350\cr
	\\OW+\\OX+\\OY+\\OZ&=120\cr
	\\AW+\\BW+\\OW&=155\cr
	\\AX+\\BX+\\OX&=230\cr
	\\AY+\\BY+\\OY&=225\cr
	\\AZ+\\BZ+\\OZ&=160\cr
	&\phantom{{}=000}\llap{all variables nonnegative}.\cr
}$$

\item{} The following Maple worksheet solves this linear program.

{\smallskip
\raggedright \advance\hsize by-2\parindent \hangindent=\parindent
		\hangafter=0  \noindent\tt
> restart;\hfil\break
> with(Optimization);
$$\displaylines{
	[\it ImportMPS,Interactive,LPSolve,LSSolve,Maximize,Minimize,NLPSolve,\hfill\cr
	\qquad\it QPSolve]\hfill\cr
}$$
> cost:=(AW,AX,AY,AZ,BW,BX,BY,BZ,OW,OX,OY,OZ)->155*AW+165*AX\hfil\break
	\strut\qquad+160*AY+170*AZ+170*BW+180*BX+175*BY+185*BZ+200*OW+210*OX\hfil\break
	\strut\qquad+205*OY+215*OZ;
$$\displaylines{
	\it cost:=(AW,AX,AY,AZ,BW,BX,BY,BZ,OW,OX,OY,OZ)\to\hfill\cr
	\qquad155\,{\it AW}+165\,{\it AX}+160\,{\it AY}+170\,{\it AZ}+170\,{\it BW}+180\,{\it BX}+175\,{\it BY}\hfill\cr
	\qquad{}+185\,{\it BZ}+200\,{\it OW}+210\,{\it OX}+205\,{\it OY}+215\,{\it OZ}\hfill\cr
}$$
> supply:=[AW+AX+AY+AZ=300,BW+BX+BY+BZ=350,OW+OX+OY+OZ=120];
$$\displaylines{
	\it supply:=[AW+AX+AY+AZ={\rm300},BW+BX+BY+BZ={\rm350},\hfill\cr
	\qquad\it OW+OX+OY+OZ={\rm120}]\hfill\cr
}$$
> demand:=[AW+BW+OW=155,AX+BX+OX=230,AY+BY+OY=225,AZ+BZ+OZ=160];
$$\displaylines{
	\it demand:=[AW+BW+OW={\rm155},AX+BX+OX={\rm230},\hfill\cr
	\qquad\it AY+BY+OY={\rm225},AZ+BZ+OZ={\rm160}]\hfill\cr
}$$
> constraints:=[op(supply),op(demand)];
$$\displaylines{
	\it constraints:=[AW+AX+AY+AZ={\rm300},BW+BX+BY+BZ={\rm350},\hfill\cr
	\qquad\it OW+OX+OY+OZ={\rm120},AW+BW+OW={\rm155},\hfill\cr
	\qquad\it AX+BX+OX={\rm230},AY+BY+OY={\rm225},AZ+BZ+OZ={\rm160}]\hfill\cr
}$$
> LPSolve(cost(AW,AX,AY,AZ,BW,BX,BY,BZ,OW,OX,OY,OZ),constraints,\hfil\break
	\strut\qquad assume=nonnegative);
$$\displaylines{
	\bigl[1.35825\;10^5,[{\it AW}=0.,{\it AX}=110.000000000000,{\it AY}=30.0000000000000,\hfill\cr
	\qquad{\it AZ}=160.000000000000,{\it BW}=155.000000000000,{\it BX}=0.,\hfill\cr
	\qquad{\it BY}=195.,{\it BZ}=0.,{\it OW}=0.,{\it OX}=120.,{\it OY}=0.,{\it OZ}=0.]\bigr]\hfill\cr
}$$

}

\item{} So an optimal production and shipping plan is as shown in the table
below:
$$\vbox{\offinterlineskip
\halign{\enspace\hfil\strut#\hfil\enspace&\vrule#&&\enspace\hfil\strut#\hfil\enspace\cr
&&W&X&Y&Z\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
A&&&110&30&160\cr
B&&155&&195&\cr
O&&&120&&\cr
}}$$
The objective value of this solution (i.e., the total cost of production and
shipping) is \$135,825.

\medbreak

\item{(b)} Shown below is the initial transportation tableau, with the initial
basic feasible solution constructed using the method described in the lecture:
satisfy demands one by one, left to right, using the supplies top to bottom.
The values of the basic squares are shown in bold in the lower left corners.
Then the values of the dual variables are calculated, starting with $v_1=0$
arbitrarily, and these dual values are used to compute the test values for the
nonbasic squares (shown in red in the lower right corners).
$$% to do: someday maybe it would be nice not to have to kludge these things together
\def\row#1{\smash{\lower6pt\hbox{\strut#1}}}
\def\red#1{\pdfliteral{1 0 0 rg 1 0 0 RG}#1\pdfliteral{0 0 0 rg 0 0 0 RG}}
\vbox{\offinterlineskip
\halign{\hfil#\ &&\vrule#&\ \bf#\hfil\ &\vrule#&\ \hfil\strut#\ \cr
&\omit&\multispan3\hfil\strut W: 155\hfil&\omit&\multispan3\hfil\strut X: 230\hfil
	&\omit&\multispan3\hfil\strut Y: 225\hfil&\omit&\multispan3\hfil\strut Z: 160\hfil\cr
\omit&\multispan{17}\hrulefill\cr
\row{A: 300}&&   &     &  155&&   &     &  165&&   &     &  160&&   &     &  170&&\row{$v_1=0$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
            &&155&\omit&     &&145&\omit&     &&   &\omit&\red0&&   &\omit&\red0&\cr
\omit&\multispan{17}\hrulefill\cr
\row{B: 350}&&   &     &  170&&   &     &  180&&   &     &  175&&   &     &  185&&\row{$v_2=15$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
            &&   &\omit&\red0&& 85&\omit&     &&225&\omit&     && 40&\omit&     &\cr
\omit&\multispan{17}\hrulefill\cr
\row{O: 120}&&   &     &  200&&   &     &  210&&   &     &  205&&   &     &  215&&\row{$v_3=45$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
            &&   &\omit&\red0&&   &\omit&\red0&&   &\omit&\red0&&120&\omit&     &\cr
\omit&\multispan{17}\hrulefill\cr
\noalign{\vskip2pt}
&\omit&\multispan3\hfil\strut$w_1=155$\hfil&\omit&\multispan3\hfil\strut$w_2=165$\hfil
	&\omit&\multispan3\hfil\strut$w_3=160$\hfil&\omit&\multispan3\hfil\strut$w_4=170$\hfil\cr
}}$$
Since all the test values are nonnegative, this solution is already optimal. So
we have another optimal production and shipping plan:
$$\vbox{\offinterlineskip
\halign{\enspace\hfil\strut#\hfil\enspace&\vrule#&&\enspace\hfil\strut#\hfil\enspace\cr
&&W&X&Y&Z\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
A&&155&145&&\cr
B&&&85&225&40\cr
O&&&&&120\cr
}}$$
The objective value of this solution is
$155(\$155)+145(\$165)+85(\$180)+225(\$175)+40(\$185)+120(\$215)=\$135{,}825$,
which matches the objective value of the optimal solution found by Maple. (In
fact, as it turns out, {\it all\/} feasible solutions are optimal for this
particular instance.) \qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem A manufacturer can ordinarily produce 300~units of a certain product
each month and needs to schedule production for a three-month period in which
the orders exceed this capacity. Inventory at the beginning of the first month
is 120~units, and the demands for the successive three months are 420,~360,
and 450~units. Monthly production capacity can be increased by up to 100~units
at an additional cost of \$8~per unit. Holding costs to manufacture in one
month and ship during a later month are \$2~per unit per month.

Determine a production schedule that will minimize the total cost of exceeding
the usual monthly capacity and holding costs.

\solution We can formulate this as an instance of the transportation problem.
There are seven origins: with labels and their supplies, they are the starting
inventory (I,~120), first month usual production (A,~300), first month
increased production (AA,~100), second month usual production (B,~300), second
month increased production (BB,~100), third month usual production (C,~300),
and third month increased production (CC,~100). Three destinations are
explicitly stated in the problem: with labels and their demands, they are the
first month (X,~420), second month (Y,~360), and third month (Z,~450). However,
the total supply is $120+300+100+300+100+300+100=1320$, while the total demand
is only $420+360+450=1230$, so we will add a fictitious fourth destination,
``unused'' (U,~90), to make total supply and total demand equal.

The per-unit costs from each origin to each destination are shown in the
following table.
$$\vbox{\offinterlineskip
\halign{\enspace\hfil\strut#\hfil\enspace&\vrule#&&\enspace\hfil\strut#\hfil\enspace\cr
&&X&Y&Z&U\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
I&&\$0&\$2&\$4&\$6\cr
A&&\$0&\$2&\$4&\$0\cr
AA&&\$8&\$10&\$12&\$0\cr
B&&$\infty$&\$0&\$2&\$0\cr
BB&&$\infty$&\$8&\$10&\$0\cr
C&&$\infty$&$\infty$&\$0&\$0\cr
CC&&$\infty$&$\infty$&\$8&\$0\cr
}}$$

Some of the costs in this table are given as~$\infty$, because they represent
impossible origin-destination combinations. For example, it is impossible to
use ordinary production in the third month~(C) to satisfy demand in the first
month~(X). Because our objective is to minimize total cost, setting the costs
of these impossible combinations to~$\infty$ will make them prohibitively
expensive to use in an optimal solution. (If $\infty$ causes implementation
difficulties because arithmetic with~$\infty$ is not well defined, then a very
large finite cost, such as \$10,000, could be used instead; it would achieve
the same result.)

Most of the entries in the U~column of this cost table are zero, because they
represent origin-destination combinations for which items would not be produced
in the first place. For example, if a solution calls for 10~units to be
``shipped'' from origin~AA to destination~U, then the meaning is that 10~units
that {\it could\/} be produced using increased production in the first month
will go unused---they will not be used to satisfy demand. In that case, there
is no need to produce them at all, so only 90~units will be produced from~AA,
and those 10~units that are never produced will incur no cost. However, the
IU~entry in the cost table is~\$6, because the items from origin~I (the
starting inventory) have already been produced, and not using them to satisfy
one of the demands will incur three months of holding costs.

\filbreak

\noindent The initial transportation tableau appears below.
$$\def\row#1{\smash{\lower6pt\hbox{\strut#1}}}
\def\red#1{\pdfliteral{1 0 0 rg 1 0 0 RG}#1\pdfliteral{0 0 0 rg 0 0 0 RG}}
\vbox{\offinterlineskip
\halign{\hfil#\ &&\vrule#&\ \bf#\hfil\ &\vrule#&\ \hfil\strut#\ \cr
&\omit&\multispan3\hfil\strut X: 420\hfil&\omit&\multispan3\hfil\strut Y: 360\hfil
	&\omit&\multispan3\hfil\strut Z: 450\hfil&\omit&\multispan3\hfil\strut U: 90\hfil\cr
\omit&\multispan{17}\hrulefill\cr
%              --------- X ----------  --------- Y ----------  ------ Z ------  -------- U --------
 \row{I: 120}&&   &     &           0&&   &     &           2&&   &     &    4&&  &     &         6&&\row{$v_1=0$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&120&\omit&            &&   &\omit&       \red0&&   &\omit&\red0&&  &\omit&  \red{10}&\cr
\omit&\multispan{17}\hrulefill\cr
 \row{A: 300}&&   &     &           0&&   &     &           2&&   &     &    4&&  &     &         0&&\row{$v_2=0$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&300&\omit&            &&   &\omit&       \red0&&   &\omit&\red0&&  &\omit&     \red4&\cr
\omit&\multispan{17}\hrulefill\cr
\row{AA: 100}&&   &     &           8&&   &     &          10&&   &     &   12&&  &     &         0&&\row{$v_3=8$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&  0&\omit&            &&100&\omit&            &&   &\omit&\red0&&  &\omit&$\red{-4}$&\cr
\omit&\multispan{17}\hrulefill\cr
 \row{B: 300}&&   &     &    $\infty$&&   &     &           0&&   &     &    2&&  &     &         0&&\row{$v_4=-2$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&   &\omit&$\red\infty$&&260&\omit&            && 40&\omit&     &&  &\omit&     \red6&\cr
\omit&\multispan{17}\hrulefill\cr
\row{BB: 100}&&   &     &    $\infty$&&   &     &           8&&   &     &   10&&  &     &         0&&\row{$v_5=6$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&   &\omit&$\red\infty$&&   &\omit&       \red0&&100&\omit&     &&  &\omit&$\red{-2}$&\cr
\omit&\multispan{17}\hrulefill\cr
 \row{C: 300}&&   &     &    $\infty$&&   &     &    $\infty$&&   &     &    0&&  &     &         0&&\row{$v_6=-4$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&   &\omit&$\red\infty$&&   &\omit&$\red\infty$&&300&\omit&     &&  &\omit&     \red8&\cr
\omit&\multispan{17}\hrulefill\cr
\row{CC: 100}&&   &     &    $\infty$&&   &     &    $\infty$&&   &     &    8&&  &     &         0&&\row{$v_7=4$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&   &\omit&$\red\infty$&&   &\omit&$\red\infty$&& 10&\omit&     &&90&\omit&          &\cr
\omit&\multispan{17}\hrulefill\cr
\noalign{\vskip2pt}
&\omit&\multispan3\hfil\strut$w_1=0$\hfil&\omit&\multispan3\hfil\strut$w_2=2$\hfil
	&\omit&\multispan3\hfil\strut$w_3=4$\hfil&\omit&\multispan3\hfil\strut$w_4=-4$\hfil\cr
}}$$
Note that the AAX~square has been made basic, with a value of~0, to complete
the ``stair-step'' pattern from the upper left to the lower right. This is
important because it gives us the correct number of basic squares and causes
the basic squares to correspond to the edges of a tree in the bipartite graph
whose vertices are the origins and destinations.

This tableau contains negative test values, so it is not optimal. The most
negative test value occurs in the AAU~square, so this will be our pivot square.
The corresponding pivot circuit goes AAU---CCU---CCZ---BZ---BY---AAY---AAU, so
we will add~$t$ to the flows in the AAU,~CCZ, and BY~squares and subtract~$t$
from the flows in the CCU,~BZ, and AAY~squares. Therefore the largest allowable
value of~$t$ (without causing a negative flow in the CCU,~BZ, or AAY~square) is
$t=40$. We adjust the flows around the pivot cycle; the flow in the BZ~square
becomes zero, so that square falls out of the basis. Then we construct the next
tableau.
$$\def\row#1{\smash{\lower6pt\hbox{\strut#1}}}
\def\red#1{\pdfliteral{1 0 0 rg 1 0 0 RG}#1\pdfliteral{0 0 0 rg 0 0 0 RG}}
\vbox{\offinterlineskip
\halign{\hfil#\ &&\vrule#&\ \bf#\hfil\ &\vrule#&\ \hfil\strut#\ \cr
&\omit&\multispan3\hfil\strut X: 420\hfil&\omit&\multispan3\hfil\strut Y: 360\hfil
	&\omit&\multispan3\hfil\strut Z: 450\hfil&\omit&\multispan3\hfil\strut U: 90\hfil\cr
\omit&\multispan{17}\hrulefill\cr
%              --------- X ----------  --------- Y ----------  ------ Z ------  -------- U --------
 \row{I: 120}&&   &     &           0&&   &     &           2&&   &     &    4&&  &     &         6&&\row{$v_1=0$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&120&\omit&            &&   &\omit&       \red0&&   &\omit&\red4&&  &\omit&  \red{14}&\cr
\omit&\multispan{17}\hrulefill\cr
 \row{A: 300}&&   &     &           0&&   &     &           2&&   &     &    4&&  &     &         0&&\row{$v_2=0$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&300&\omit&            &&   &\omit&       \red0&&   &\omit&\red4&&  &\omit&     \red8&\cr
\omit&\multispan{17}\hrulefill\cr
\row{AA: 100}&&   &     &           8&&   &     &          10&&   &     &   12&&  &     &         0&&\row{$v_3=8$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&  0&\omit&            && 60&\omit&            &&   &\omit&\red4&&40&\omit&          &\cr
\omit&\multispan{17}\hrulefill\cr
 \row{B: 300}&&   &     &    $\infty$&&   &     &           0&&   &     &    2&&  &     &         0&&\row{$v_4=-2$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&   &\omit&$\red\infty$&&300&\omit&            &&   &\omit&\red4&&  &\omit&  \red{10}&\cr
\omit&\multispan{17}\hrulefill\cr
\row{BB: 100}&&   &     &    $\infty$&&   &     &           8&&   &     &   10&&  &     &         0&&\row{$v_5=10$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&   &\omit&$\red\infty$&&   &\omit&  $\red{-4}$&&100&\omit&     &&  &\omit&$\red{-2}$&\cr
\omit&\multispan{17}\hrulefill\cr
 \row{C: 300}&&   &     &    $\infty$&&   &     &    $\infty$&&   &     &    0&&  &     &         0&&\row{$v_6=0$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&   &\omit&$\red\infty$&&   &\omit&$\red\infty$&&300&\omit&     &&  &\omit&     \red8&\cr
\omit&\multispan{17}\hrulefill\cr
\row{CC: 100}&&   &     &    $\infty$&&   &     &    $\infty$&&   &     &    8&&  &     &         0&&\row{$v_7=8$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&   &\omit&$\red\infty$&&   &\omit&$\red\infty$&& 50&\omit&     &&50&\omit&          &\cr
\omit&\multispan{17}\hrulefill\cr
\noalign{\vskip2pt}
&\omit&\multispan3\hfil\strut$w_1=0$\hfil&\omit&\multispan3\hfil\strut$w_2=2$\hfil
	&\omit&\multispan3\hfil\strut$w_3=0$\hfil&\omit&\multispan3\hfil\strut$w_4=-8$\hfil\cr
}}$$

The most negative test value in this tableau occurs in the BBY~square, for
which the pivot circuit is BBY---AAY---AAU---CCU---CCZ---BBZ---BBY. In the
pivot we will add~$t$ to the flows in the BBY,~AAU, and CCZ~squares and
subtract~$t$ from the flows in the AAY,~CCU, and BBZ~squares, so the largest
permissible value of~$t$ is $t=50$. When we adjust the flows, the flow in the
CCU~square becomes zero, so it falls out of the basis. The next tableau
appears below.
$$\def\row#1{\smash{\lower6pt\hbox{\strut#1}}}
\def\red#1{\pdfliteral{1 0 0 rg 1 0 0 RG}#1\pdfliteral{0 0 0 rg 0 0 0 RG}}
\vbox{\offinterlineskip
\halign{\hfil#\ &&\vrule#&\ \bf#\hfil\ &\vrule#&\ \hfil\strut#\ \cr
&\omit&\multispan3\hfil\strut X: 420\hfil&\omit&\multispan3\hfil\strut Y: 360\hfil
	&\omit&\multispan3\hfil\strut Z: 450\hfil&\omit&\multispan3\hfil\strut U: 90\hfil\cr
\omit&\multispan{17}\hrulefill\cr
%              --------- X ----------  --------- Y ----------  ------ Z ------  -------- U --------
 \row{I: 120}&&   &     &           0&&   &     &           2&&   &     &    4&&  &     &         6&&\row{$v_1=0$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&120&\omit&            &&   &\omit&       \red0&&   &\omit&\red0&&  &\omit&  \red{14}&\cr
\omit&\multispan{17}\hrulefill\cr
 \row{A: 300}&&   &     &           0&&   &     &           2&&   &     &    4&&  &     &         0&&\row{$v_2=0$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&300&\omit&            &&   &\omit&       \red0&&   &\omit&\red0&&  &\omit&     \red8&\cr
\omit&\multispan{17}\hrulefill\cr
\row{AA: 100}&&   &     &           8&&   &     &          10&&   &     &   12&&  &     &         0&&\row{$v_3=8$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&  0&\omit&            && 10&\omit&            &&   &\omit&\red0&&90&\omit&          &\cr
\omit&\multispan{17}\hrulefill\cr
 \row{B: 300}&&   &     &    $\infty$&&   &     &           0&&   &     &    2&&  &     &         0&&\row{$v_4=-2$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&   &\omit&$\red\infty$&&300&\omit&            &&   &\omit&\red0&&  &\omit&  \red{10}&\cr
\omit&\multispan{17}\hrulefill\cr
\row{BB: 100}&&   &     &    $\infty$&&   &     &           8&&   &     &   10&&  &     &         0&&\row{$v_5=6$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&   &\omit&$\red\infty$&& 50&\omit&            && 50&\omit&     &&  &\omit&     \red2&\cr
\omit&\multispan{17}\hrulefill\cr
 \row{C: 300}&&   &     &    $\infty$&&   &     &    $\infty$&&   &     &    0&&  &     &         0&&\row{$v_6=-4$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&   &\omit&$\red\infty$&&   &\omit&$\red\infty$&&300&\omit&     &&  &\omit&  \red{12}&\cr
\omit&\multispan{17}\hrulefill\cr
\row{CC: 100}&&   &     &    $\infty$&&   &     &    $\infty$&&   &     &    8&&  &     &         0&&\row{$v_7=4$}\cr
\omit&&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill&\omit&\multispan3\hrulefill\cr
             &&   &\omit&$\red\infty$&&   &\omit&$\red\infty$&&100&\omit&     &&  &\omit&     \red4&\cr
\omit&\multispan{17}\hrulefill\cr
\noalign{\vskip2pt}
&\omit&\multispan3\hfil\strut$w_1=0$\hfil&\omit&\multispan3\hfil\strut$w_2=2$\hfil
	&\omit&\multispan3\hfil\strut$w_3=4$\hfil&\omit&\multispan3\hfil\strut$w_4=-8$\hfil\cr
}}$$

In this tableau, all test values are nonnegative, so we have reached an optimal
solution. In the first month, the manufacturer should use all of the starting
inventory and usual production to meet demand and should use increased
production to produce an extra 10~units. Those 10~units will be used to satisfy
the demand in the second month, along with all of the usual production and
50~extra units produced using increased production in the second month. An
additional 50~extra units should also be produced using increased production
in the second month to satisfy the demand in the third month, together with
all of the usual production and 100~extra units of increased production. The
cost of this solution is
$120(\$0)+300(\$0)+0(\$8)+10(\$10)+90(\$0)+300(\$0)+50(\$8)+50(\$10)+300(\$0)+100(\$8)=\$1800$.

Alternatively, we may formulate this problem as a linear program. For
$i\in\{\rm I,A,\allowbreak AA,\allowbreak B,\allowbreak BB,\allowbreak C,CC\}$
and $j\in\{\rm X,Y,Z,U\}$, let $x_{ij}$ denote the number of units to be taken
from origin~$i$ and used to satisfy demand at destination~$j$. These variables
are all nonnegative. Actually, we do not need the variables
$x_{\rm BX}$,~$x_{\rm BBX}$, $x_{\rm CX}$, $x_{\rm CCX}$, $x_{\rm CY}$,
and~$x_{\rm CCY}$, because these origin-destination combinations are
impossible. We also do not need the variables $x_{\rm AU}$,~$x_{\rm AAU}$,
$x_{\rm BU}$, $x_{\rm BBU}$, $x_{\rm CU}$, and~$x_{\rm CCU}$ if we do not
require that total supply equal total demand, and we can remove that
requirement by formulating the constraints as inequalities. The linear program
is shown below.
$$\eqalign{
	{\rm minimize}\quad 2x_{\rm IY}+4x_{\rm IZ}+6x_{\rm IU}+2x_{\rm AY}+4x_{\rm AZ}+8x_{\rm AAX}+10x_{\rm AAY}&\cr
	{}+12x_{\rm AAZ}+2x_{\rm BZ}+8x_{\rm BBY}+10x_{\rm BBZ}+8x_{\rm CCZ}&\cr
	{\rm subject\ to}\quad\phantom{2x_{\rm IY}+4x_{\rm IZ}+6x_{\rm IU}+2x_{\rm AY}+4x_{\rm AZ}+8x_{\rm AAX}+10x_{\rm AAY}}
		\llap{$x_{\rm IX}+x_{\rm IY}+x_{\rm IZ}+x_{\rm IU}$}&=120\cr
	x_{\rm AX}+x_{\rm AY}+x_{\rm AZ}&\le300\cr
	x_{\rm AAX}+x_{\rm AAY}+x_{\rm AAZ}&\le100\cr
	x_{\rm BY}+x_{\rm BZ}&\le300\cr
	x_{\rm BBY}+x_{\rm BBZ}&\le100\cr
	x_{\rm CZ}&\le300\cr
	x_{\rm CCZ}&\le100\cr
	x_{\rm IX}+x_{\rm AX}+x_{\rm AAX}&\ge420\cr
	x_{\rm IY}+x_{\rm AY}+x_{\rm AAY}+x_{\rm BY}+x_{\rm BBY}&\ge360\cr
	x_{\rm IZ}+x_{\rm AZ}+x_{\rm AAZ}+x_{\rm BZ}+x_{\rm BBZ}+x_{\rm CZ}+x_{\rm CCZ}&\ge450\cr
	&\phantom{{}=000}\llap{all variables nonnegative}.\cr
}$$

\noindent The following Maple worksheet solves this linear program.

{\smallskip
\raggedright \advance\hsize by-\parindent \hangindent=\parindent
		\hangafter=0  \noindent\tt
> restart;\hfil\break
> with(Optimization);
$$\displaylines{
	[\it ImportMPS,Interactive,LPSolve,LSSolve,Maximize,Minimize,NLPSolve,\hfill\cr
	\qquad\it QPSolve]\hfill\cr
}$$
> cost:=(IY,IZ,IU,AY,AZ,AAX,AAY,AAZ,BZ,BBY,BBZ,CCZ)->2*IY+4*IZ+6*IU\hfil\break
	\strut\qquad+2*AY+4*AZ+8*AAX+10*AAY+12*AAZ+2*BZ+8*BBY+10*BBZ+8*CCZ;
$$\displaylines{
	\it cost:=(IY,IZ,IU,AY,AZ,AAX,AAY,AAZ,BZ,BBY,BBZ,CCZ)\to\rm2\,{\it IY}\hfill\cr
	\qquad{}+4\,{\it IZ}+6\,{\it IU}+2\,{\it AY}+4\,{\it AZ}+8\,{\it AAX}+10\,{\it AAY}+12\,{\it AAZ}+2\,{\it BZ}+8\,{\it BBY}\hfill\cr
	\qquad{}+10\,{\it BBZ}+8\,{\it CCZ}\hfill\cr
}$$
> supply:=[IX+IY+IZ+IU=120,AX+AY+AZ<=300,AAX+AAY+AAZ<=100,\hfil\break
	\strut\qquad BY+BZ<=300,BBY+BBZ<=100,CZ<=300,CCZ<=100];
$$\displaylines{
	\it supply:=[IX+IY+IZ+IU={\rm120},AX+AY+AZ\le{\rm300},\hfill\cr
	\qquad\it AAX+AAY+AAZ\le{\rm100},BY+BZ\le{\rm300},BBY+BBZ\le{\rm100},CZ\le{\rm300},\hfill\cr
	\qquad\it CCZ\le{\rm100}]\hfill\cr
}$$
> demand:=[IX+AX+AAX>=420,IY+AY+AAY+BY+BBY>=360,\hfil\break
	\strut\qquad IZ+AZ+AAZ+BZ+BBZ+CZ+CCZ>=450];
$$\displaylines{
	\it demand:=[{\rm420}\le IX+AX+AAX,{\rm360}\le IY+AY+AAY+BY+BBY,\hfill\cr
	\qquad\it{\rm450}\le IZ+AZ+AAZ+BZ+BBZ+CZ+CCZ]\hfill\cr
}$$
> constraints:=[op(supply),op(demand)];
$$\displaylines{
	\it constraints:=[IX+IY+IZ+IU={\rm120},AX+AY+AZ\le{\rm300},\hfill\cr
	\qquad\it AAX+AAY+AAZ\le{\rm100},BY+BZ\le{\rm300},BBY+BBZ\le{\rm100},CZ\le{\rm300},\hfill\cr
	\qquad\it CCZ\le{\rm100},{\rm420}\le IX+AX+AAX,{\rm360}\le IY+AY+AAY+BY+BBY,\hfill\cr
	\qquad\it {\rm450}\le IZ+AZ+AAZ+BZ+BBZ+CZ+CCZ]\hfill\cr
}$$
> LPSolve(cost(IY,IZ,IU,AY,AZ,AAX,AAY,AAZ,BZ,BBY,BBZ,CCZ),\hfil\break
	\strut\qquad constraints,assume=nonnegative);
$$\displaylines{
	\bigl[1799.99999999174,[{\it AAX}=0.,{\it AAY}=0.,{\it AAZ}=9.99999999896738,{\it AX}=300.,\hfill\cr
	\qquad{\it AY}=1.03259778874000\;10^{-9},{\it AZ}=0.,{\it BBY}=59.9999999989674,\hfill\cr
	\qquad{\it BBZ}=40.0000000010326,{\it BY}=300.,{\it BZ}=0.,{\it CCZ}=100.,{\it CZ}=300.,\hfill\cr
	\qquad{\it IU}=0.,{\it IX}=120.,{\it IY}=0.,{\it IZ}=0.]\bigr]\hfill\cr
}$$

}

\noindent The optimal solution found by Maple is shown in the table below.
$$\vbox{\offinterlineskip
\halign{\enspace\hfil\strut#\hfil\enspace&\vrule#&&\enspace\hfil\strut#\hfil\enspace\cr
&&X&Y&Z\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
I&&120&&\cr
A&&300&&\cr
AA&&&&10\cr
B&&&300&\cr
BB&&&60&40\cr
C&&&&300\cr
CC&&&&100\cr
}}$$
This solution also has cost \$1800. \qed

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye
