\documentclass[12pt]{article}
\usepackage{fullpage,amsmath,amsfonts,graphicx}

\newcommand{\x}{\boldsymbol{x}}
\newcommand{\y}{\boldsymbol{y}}
\renewcommand{\a}{\boldsymbol{a}}
\renewcommand{\b}{\boldsymbol{b}}
\renewcommand{\c}{\boldsymbol{c}}
\newcommand{\R}{\mathbb{R}}

\begin{document}

\title{Operations Research}
\author{Homework 4}
\date{Due in class Wednesday, March 2, 2016}
\maketitle


\begin{enumerate}

\item The primal form of the standard \emph{activity analysis problem}
(or \emph{resource allocation problem}) is given by
\begin{equation*}
  \begin{gathered}
    \text{maximize } \c^T \x \\
    \text{subject to } A\x \leq \b, \x \geq 0 \,.
  \end{gathered}
  \tag{P}
\end{equation*}
The corresponding dual problem reads
\begin{equation*}
  \begin{gathered}
    \text{minimize } \y^T \b \\
    \text{subject to } \y^T A \geq \c^T, \y \geq 0 \,.
  \end{gathered}
  \tag{D}
  \end{equation*}Here, $A$ is an $n\times m$ matrix, $\x, \c \in
  \R^m$, and $\y, \b \in \R^n$. 

\begin{enumerate}
\item
Show that if $\x$ solves (P) and $\y$ solves (D), then
\[
  \y^T\b \geq \c^T \x \,.
\]

\item Conclude that the primal problem does not have a finite maximum
if and only if the feasible region of the dual problem is empty.

\item Show that if $\x$ is
feasible for problem (P) and $\y$ is feasible for problem (D), and if
furthermore
\[
  \y^T \b = \c^T \x \,,
\]
then $\x$ solves (P) and $\y$ solves (D).
\end{enumerate}

\item \emph{(This is a variation of Exercise 6.8-8 from HL.)} David,
LaDeana, and Lydia are the sole partners and workers in a company
which produces fine clocks.  David and LaDeana each are available to
work a maximum of 40 hours per week at the company, while Lydia is
available to work a maximum of 20 hours per week.  The company makes
two different types of clocks: a grand-father clock and a wall clock.
To make a clock, David (a mechanical engineer) assembles the inside
mechanical parts of the clock while LaDeana (a woodworker) produces
the handcarved wood casings.  Lydia is responsible for taking orders
and shipping the clocks.  The amount of time required for each of
these tasks is shown below.


\begin{center}
\begin{tabular}{lcc}
\hline
& \multicolumn{2}{c}{\textbf{Time Required}$\vphantom{1^{1^1}}$} \\
  \textbf{Task}$\vphantom{1^{1^1}}$ & \textbf{Grandfather Clock} &
                                                                   \textbf{Wall Clock}
                                                      \\
\hline
Assemble clock mechanism$^{\vphantom{\tfrac11}}$ & $6$ hours & $4$ hours \\
Carve wood casing & $8$ hours & $4$ hours \\
Shipping & $3$ hours & $3$ hours \\
\hline
\end{tabular}
\end{center}

Each grandfather clock built and shipped yields a profit of \$300
while each wall clock yields a profit of \$200.

\begin{enumerate}
\item Formulate and solve the problem in Pyomo, and ask Pyomo to
compute shadow prices (dual variables) for each activity.  Please
submit a printout of your Ipython notebook showing code and output.

\item Occasionally, someone stops by asking for help with restoring
antique clocks.  How much should David charge per hour for mechanical
repairs and how much should LaDeana charge per hour for wood
restoration assuming that they do not wish to add more working hours
and also do not wish to reduce company profit if one of them is taking
on a repair job?
\end{enumerate}

\end{enumerate}

\end{document}
