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

\font\titlefont=cmbx12

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

\def\transpose{{\rm T}}

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

\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Problem set~1}
\smallskip
\centerline{Assigned Thursday, May~28, 2015. Due Monday, June~1, 2015.}

\bigskip

\item{\bf1.} Formulate a linear program for the following optimization problem.
Then solve your linear program with Maple and interpret the results. (Please
include a printout of your Maple worksheet.)

{\medskip\narrower\narrower

\noindent The Ace Refining Company produces two types of unleaded gasoline,
regular and premium, which it sells to its chain of service stations for
\$36~and~\$42 per barrel, respectively. Both types are blended from Ace's
inventories of refined domestic and refined foreign oil and must meet the
following specifications:
$$\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\hfil\quad&&\hfil\strut#\hfil\quad\cr
&&Maximum&Minimum&Maximum&Minimum\cr
&&vapor&octane&demand,&deliveries,\cr
&&pressure&rating&bbl/wk&bbl/wk\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
Regular&&23&88&100,000&50,000\cr
Premium&&23&93&\phantom020,000&\phantom05,000\cr}}$$
The characteristics of the refined oils in inventory are:
$$\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\hfil\quad&&\hfil\strut#\hfil\quad\cr
&&Vapor&Octane&Inventory,&Cost,\cr
&&pressure&rating&bbl&\$/bbl\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
Domestic&&25&87&40,000&16\cr
Foreign&&15&98&60,000&30\cr}}$$
What quantities of the two oils should Ace blend into the two gasolines in
order to maximize weekly profit? (Assume that vapor pressure and octane ratings
combine linearly in a blend.)

\medbreak}

\item{\bf2.} Formulate a linear program for the following optimization problem.
Carefully draw the feasible region (i.e., the set of feasible solutions). Solve
the linear program graphically. Draw at least three level curves of the
objective function, including the level curve corresponding to the optimal
value. (To get a nice, careful drawing of the feasible region and level curves,
I suggest you use graphing software, or at least graph paper and a ruler.)

{\medskip\narrower\narrower

\noindent A kennel owner has a choice of two dog foods to buy in bulk
quantities to feed the dogs under her care. The average dog in her kennel needs
at least 36~grams of protein, 12~grams of fat, and 9~milligrams of iron a day.
An ounce of Dog Grub includes 3~grams of protein, 1.5~grams of fat, and
0.5~milligrams of iron. An ounce of Canine Chow includes 2~grams of protein,
0.5~grams of fat, and 0.75~milligrams of iron. If Dog Grub and Canine Chow cost
\$0.12~and~\$0.15 per ounce, respectively, how much of each should she buy to
meet the daily needs of the average dog at a minimum cost?

\medbreak}

\item{\bf3.} Give a (simple) example of each of the following:

\smallskip

\itemitem{(a)} An infeasible linear program.

\itemitem{(b)} An unbounded linear program (i.e., a linear program with an
unbounded objective value).

\itemitem{(c)} A linear program with a unique optimal solution.

\itemitem{(d)} A linear program with a nonunique optimal solution.

\itemitem{(e)} A linear program with an unbounded feasible region that does
{\it not\/} have an unbounded objective value.

\medbreak

\item{\bf4.} A {\it convex combination\/} of two vectors $x$~and~$x'$ (of the
same size) is a vector of the form $\lambda x+(1-\lambda)x'$, where $\lambda$
is a scalar in the interval $[0,1]$. Let $A=[a_{ij}]$ be an $m\times n$ matrix
and let $b=[b_1,\ldots,b_m]^\transpose$ be an $m\times1$ column vector.
Consider the set of constraints $Ax\le b$, where $x$ is an $n\times1$ column
vector. (The inequality $Ax\le b$ means that each coordinate of~$Ax$ is less
than or equal to the corresponding coordinate of~$b$; so it is a set of
$m$~inequalities.) Suppose that $x=[x_1,\ldots,x_n]^\transpose$ and
$x'=[x'_1,\ldots,x'_n]^\transpose$ are both feasible solutions to this set of
constraints. Prove that any convex combination of $x$~and~$x'$ is also
feasible.

\medbreak

\item{\bf5.} Here is another example of a combinatorial optimization problem.
We have not yet discussed methods for solving problems like this, but see if
you can find a good approach. Your goal is to find the optimal solution to the
problem and to {\it prove\/} that it is optimal.

{\medskip\narrower\narrower

\noindent Indiana Jones has made it through the deadly traps of an ancient
temple and has discovered ten treasures inside. Unfortunately, his knapsack is
too small to carry them all, so he must choose (wisely). He has made the
following estimates of the objects' weights and values. If his knapsack can
hold at most 20~pounds of treasure, which objects should he take to maximize
the value of his loot?
$$\hss\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\quad&&\hfil\strut#\quad\cr
Treasure&&Weight&Value\cr
\omit&height2pt&\omit&\omit\cr
\noalign{\hrule}
\omit&height2pt&\omit&\omit\cr
Crown of Atahualpa&&4 lb.&\$\phantom04,000\cr
Itzcoatl's Orb&&6 lb.&9,000\cr
Tablet of the Heavens&&7 lb.&7,000\cr
Golden Quetzal&&13 lb.&17,000\cr
Mask of the Ancients&&5 lb.&5,000\cr
}}\qquad\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\quad&&\hfil\strut#\quad\cr
Treasure&&Weight&Value\cr
\omit&height2pt&\omit&\omit\cr
\noalign{\hrule}
\omit&height2pt&\omit&\omit\cr
Key of Silver Light&&2 lb.&\$\phantom02,000\cr
Idol of Inti&&10 lb.&15,000\cr
Eternal Quipu&&5 lb.&8,000\cr
Goblet of Uxmal&&3 lb.&4,000\cr
Sacred Stone of Cuzco&&8 lb.&11,000\cr
}}\hss$$

\medbreak}

\item{\bf6.} The phrase ``combinatorial optimization'' is a mouthful. Come up
with a shorter way to say it.

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

\bye
