%  Midterm examination
%  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

\edef\restoreinterlineskip{\noexpand\baselineskip=\the\baselineskip\relax\noexpand\lineskiplimit=\the\lineskiplimit\relax\noexpand\lineskip=\the\lineskip}

\long\def\boxed#1{\vbox{\offinterlineskip
	\hrule
	\hbox to \hsize{%
	\hss\vrule\hskip1em%
	\vbox{\advance\hsize by-2em \advance\hsize by-0.8pt
	\restoreinterlineskip
	\vskip1ex
	\noindent#1\par
	\vskip1ex
	}\hskip1em\vrule\hss}%
	\hrule}}

\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{{\raise0.5pt\hbox{\transposefont T}}}
\def\labs{\mathopen|}  \def\rabs{\mathclose|}  \def\abs#1{\labs#1\rabs}

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

\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Midterm examination}
\smallskip
\centerline{Released Thursday, June~18, 2015. Due 1:30~p.m., Monday, June~22, 2015.}

\medskip

\noindent You must read, understand, and agree to follow all of the rules of
this exam, which were given to you separately. By opening the envelope
containing these problems, you have begun this exam and are bound by these
rules until class on Monday. Here are the rules again as a reminder.

\medskip

\boxed{%
\font\eightrm=cmr8 \font\eightbf=cmbx8 \fam0\eightrm \def\bf{\fam\bffam\eightbf}%
\normalbaselineskip=9pt \normalbaselines
\input midterm-rules-include.tex
}

\noindent After completing this exam, please sign the statement accompanying
the rules and submit it with your solutions.

\medskip\hbox to\hsize{\hskip1in\hrulefill\hskip1in}\bigskip

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

\noindent Each of the five problems on this exam is worth 20~points.

\advance\hsize by-\parindent \everypar={\hangindent=\parindent \hangafter=0}

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

\problem Solve the following linear program. You may not use Maple for this
problem.
$$\eqalign{
	{\rm minimize}\quad 3x_1+2x_2-\phantom1x_3-4x_4&\cr
	{\rm subject\ to}\quad\phantom1x_1+\phantom1x_2+\phantom1x_3+\phantom1x_4&=\phantom+\llap10\cr
	2x_1\phantom{{}+0x_2}+\phantom1x_3-2x_4&\ge\phantom+6\cr
	x_1\phantom{{}+0x_2+0x3}+3x_4&\le\phantom+\llap30\cr
	3x_1+\phantom1x_2\phantom{{}+0x_3+0x_4}&\ge-8\cr
	x_2+3x_3\phantom{{}+0x_4}&\ge\phantom+3\cr
	&\phantom{{}=+0}\llap{$x_1\ge0$,\quad$x_2$ unrestricted,\quad$x_3\le0$,\quad$x_4\ge0$}.\cr
}$$

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

\problem Formulate a linear program for the following scenario. Then solve the
linear program and interpret your results.

{\medskip\narrower

\noindent Leisure Furniture, Inc.\ (LFI) makes outdoor chairs, tables, lounges,
and benches. The main resources required for production are plastic webbing,
metal tubing, and wood. The number of units of each resource required per item
and the per-item profit are given below.
$$\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\hfil\quad
	&\quad\hfil\strut#\hfil\quad&\quad\hfil\strut#\hfil\quad&\vrule#
	&\quad\hfil\strut#\hfil\quad\cr
&&Tubing&Webbing&Wood&&Per-unit\cr
&&(feet)&(yards)&(board feet)&&profit\cr
\omit&height2pt&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt&\omit&\omit&\omit&height2pt\cr
Chair&&18&28&&&\$11\cr
Table&&18&&10&&\$18\cr
Lounge&&24&35&&&\$14\cr
Bench&&20&&14&&\$\phantom09\cr}}$$

\goodbreak

\noindent The main activities in production are tube bending and assembly. The
number of hours of each activity required per unit of each product are given
in the table below.
$$\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&&\quad\hfil\strut#\hfil\quad\cr
&&Chair&Table&Lounge&Bench\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
Tube bending&&1/3&1/8&1/4&1/8\cr
Assembly&&1/2&1/2&1/3&1/3\cr}}$$

\goodbreak

\noindent LFI is planning its first week's production for the spring. Available
during that week are 120~hours of bending time, 160~hours of assembly time,
6,000~feet of tubing, 5,000~yards of webbing, and 1,000~board feet of wood. The
lounge is the most popular product, so LFI wants to make at least 100 of them.
Tables and chairs are commonly sold in sets of two chairs and a table, so they
want to make at least twice as many chairs as tables. Otherwise they want to
make the products that will maximize their profit if sold.

\medskip}

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

\problem Find an extreme point of the feasible region of the following linear
program.
$$\eqalign{
	{\rm maximize}\quad\phantom{+1}x_1-2x_2+\phantom1x_3\phantom{{}+0x_4}&\cr
	{\rm subject\ to}\quad\phantom+3x_1+3x_2-\phantom1x_3-2x_4&\le90\cr
	x_1\phantom{{}+0x_2}+5x_3\phantom{{}+0x_4}&\ge20\cr
	-4x_1-\phantom1x_2+\phantom1x_3-\phantom1x_4&=\phantom06\cr
	x_2-2x_3+\phantom1x_4&\le40\cr
	&\phantom{{}=00}\llap{$x_1\ge0$,\quad$x_2\ge0$,\quad$x_3\ge0$,\quad$x_4\ge0$}.\cr
}$$

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

\problem Consider a project consisting of several activities, each having a
usual time and a set of immediate prerequisites. Some of the activities can be
sped up; these activities additionally have a crash time and a per-unit speedup
cost. (This is the kind of problem we considered when we discussed the critical
path method.) Suppose that the overall project needs to be sped up to meet a
deadline, and it is desired to do so at minimum total speedup cost. Is it true
that only the critical activities (under the usual times) are candidates to be
sped up? If so, explain why. If not, give a counterexample.

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

\problem An important communications line is to be built between locations
$s$~and~$t$ in a dangerous, disaster-prone area. The line cannot be built
directly; it will need to be built as a sequence of links joining intermediate
points $a$,~$b$, \dots,~$g$. The following table shows the estimated
probabilities of {\it failure\/} of a link built between pairs of points. (Not
all pairs of points are possible locations for a communications link;
impossible locations are indicated with a dash.) If any link fails, then the
entire communications line fails. Determine a route for the line that minimizes
the probability of failure.
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\hfil\quad&&\hfil\strut#\hfil\quad\cr
&&$s$&$a$&$b$&$c$&$d$&$e$&$f$&$g$&$t$\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
$s$&&---&1.5\%&---&---&---&---&3.0\%&4.0\%&---\cr
$a$&&1.5\%&---&---&---&5.0\%&---&2.0\%&---&---\cr
$b$&&---&---&---&6.0\%&8.0\%&---&---&---&0.5\%\cr
$c$&&---&---&6.0\%&---&---&2.0\%&3.5\%&7.0\%&---\cr
$d$&&---&5.0\%&8.0\%&---&---&---&2.5\%&---&---\cr
$e$&&---&---&---&2.0\%&---&---&---&5.5\%&5.0\%\cr
$f$&&3.0\%&2.0\%&---&3.5\%&2.5\%&---&---&1.0\%&---\cr
$g$&&4.0\%&---&---&7.0\%&---&5.5\%&1.0\%&---&---\cr
$t$&&---&---&0.5\%&---&---&5.0\%&---&---&---\cr
}}$$

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

\bye