%  Problem set 4
%  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

% AMSFonts
\input amssym.tex

\font\titlefont=cmbx12  \font\smfont=cmr8

\headline={\hfil}
\footline={\hfil}

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

\def\R{{\mathord{\Bbb R}}}
\def\transpose{{\rm T}}

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

\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Problem set~4}
\smallskip
\centerline{Assigned Tuesday, June~9, 2015. Due Friday, June~12, 2015.}

\medskip

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

\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.

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

\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.

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

\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).

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

\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.

\medskip

\noindent[Hint: View this as a transportation problem. The first step is to
identify the various ``origins'' and ``destinations'' in this scenario.]

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

\bye
