\documentclass[12pt,a4paper]{article}

\usepackage{fullpage,amsmath,amsfonts,graphicx}
\usepackage{tikz}
\let\newpage\relax
\let\mbox\relax

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

\begin{document}

\title{Operations Research}
\author{Midterm Exam}
\date{April 1, 2016}
\maketitle

% \vspace*{\fill}
% {\baselineskip=40pt
% \begin{tabbing}\
% Student ID Number: \= \kill
% Last Name: \> \rule[-2pt]{10cm}{0.3pt} \\
% First Name:  \> \rule[-2pt]{10cm}{0.3pt} \\
% Signature: \> \rule[-2pt]{10cm}{0.3pt} \\
% %Code: \> \fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% \end{tabbing}}
% \vspace*{\fill}

\newpage
\begin{enumerate}

\item Use the graphical method to minimize
\begin{gather*}
  z = 4 \, x + 3 \, y
\end{gather*}
subject to
\begin{gather*}
  2 \, x + 3 \, y \geq 6 \,, \\
  3 \, x - 2 \, y \leq 9 \,, \\
  x + 5 \, y \leq 20 \,,\\
  x, y \geq 0 \,.
\end{gather*}
\hfill(20)

\newpage\mbox{}\newpage

\item The Steelworks have three machines each of which has $t_i$ hours
of spare operating time available.  They can be used to make four
products, each with possible profit of $p_j$ Euros per unit sold.  The
production of one unit of product $j$ requires $w_{ij}$ hours of
working time on machine $i$.

The production schedule for the week has been planned using the
attached Pyomo program.  Look at the program output to answer the
following questions.

\begin{enumerate}
\item Marketing determines that product P02 will still sell if the
unit price is raised by 20 Euros.  Give an estimate of the resulting
increase in profits.

\item On Tuesday, three hours before the end of the last shift, the
cutting machine breaks down.  The service engineer needs the rest of
the day to fix the machine, but is certain that it will be back in
service the next morning.  Will this affect the planned weekly output?

\item One of the workers would like to borrow the welding machine to
mend his fender.  His boss is inclined to grant the request, but
insists that the cost in lost profits to the company must be covered
by the borrower.  How much should he charge if the machine is used for
two hours?

\item In an alternative scenario, the welding machine is out for 10
hours.  Do you expect that the loss in profits is $5$ times your
answer to question (b)?  What do you advise?

\end{enumerate}
\hfill(5+5+5+5)

\newpage\mbox{}\newpage

\item Prove that if there are feasible solutions for both primal and
dual form of a linear programming problem, then both must have an
optimal solution.
\hfill(10)

\newpage

\item Andy, Bob, and Curt together with Doris, Erica, and Fiona visit
a desert island.  Each woman is spending a certain fraction of her
time with one of the men and none alone; likewise, each man is
spending a certain fraction of his time with one of the women and none
alone.  The following table gives a measure of the happiness that
ensues from each possible couple spending time together.
\begin{center}
\begin{tabular}{lccc}
\hline
& \textbf{Doris}$\vphantom{1^{1^1}}$ & \textbf{Erica} &
  \textbf{Fiona}  \\
\hline
\textbf{Andy}$^{\vphantom{\tfrac11}}$ & 1 & 3 & 3 \\
\textbf{Bob} & 4 & 3 & 2 \\
\textbf{Curt} & 5 & 4 & 2 \\
\hline
\end{tabular}
\end{center}


\begin{enumerate}
\item Formulate a linear programming problem to maximize overall
happiness on the island, assuming that happiness is additive and
proportional to the fraction of time each couple spends together.

(You do not need to solve this problem.)

\item Do you expect the result to suggest monogamous or polygamous
relationships?  Explain.

\end{enumerate}
\hfill(10+5)

\newpage


\item Recall that the primal form of the standard activity analysis problem
\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*}
has the symmetric dual
\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$. 

Now a certain type of application leads to the linear programming
problem
\begin{equation*}
\begin{gathered}
  \text{maximize } s \\
\text{subject to } 
  s \leq B \p \,, \\
  p_1 + \dots + p_\ell = 1 \,, \\
  \p \geq 0 \,,
\end{gathered}
  \tag{P'}
\end{equation*}
where $B$ is a given $k \times \ell$ matrix.  There are $\ell+1$
decision variables, namely $s \in \R$ and $\p \in \R^\ell$.  Note that
there is no sign constraint on $s$ and there is one \emph{equality}
constraint.
\begin{enumerate}
\item Write this problem in the standard form (P) by introducing an
artificial nonnegative variable and representing the equality by two
inequalities.  In particular, write out $A$, $\b$, and $\c$ for a given
matrix $B$ and state their dimensions.

\item Show that problem (P') also has a symmetric dual formulation,
namely
\begin{equation*}
\begin{gathered}
  \text{minimize } t \\
\text{subject to } 
  t \geq B^T \q \,, \\
  q_1 + \dots + q_k = 1 \,, \\
  \q \geq 0 \,.
\end{gathered}
  \tag{D'}
\end{equation*}
\end{enumerate}
\hfill(5+10)
\newpage\mbox{}\newpage

\item A railway line is used for passenger and freight traffic in a
single direction.  The line is composed of $6$ signal blocks.  Each
block can be used by only one train at a time, but at the start of
each signal block there is a siding where another train can be kept
waiting.

\begin{center}
\begin{tikzpicture}

  \foreach \x in {0,2.5,...,12.5}
    {\draw [>->] (\x,0.25) [rounded corners=2] --
          +(0.25,0) -- +(0.25,-0.25) -- +(2.25,-0.25) -- +(2.25,0) -- +(2.5,0);
     \draw [>->] (\x,0) -- +(2.5,0);
    }


   % \foreach \x in {0,2.5,...,10}
   %    {\draw (\x,-0.1) -- (\x,0.1);
   %     \draw (\x,0.2) -- (\x,0.3);}

   \node at (1.25,0.25) {\small Block A};
   \node at (3.75,0.25) {\small Block B};
   \node at (6.25,0.25) {\small Block C};
   \node at (8.75,0.25) {\small Block D};
   \node at (11.25,0.25) {\small Block E};
   \node at (13.75,0.25) {\small Block F};

\end{tikzpicture}
\end{center}

For simplicity, we analyze the problem in discrete $5$-minute time
slots.  Trains enter a signal block exactly at the start of each slot.

A freight train takes exactly $5$ minutes to traverse a signal block.
Passenger trains travel twice as fast and must not be delayed.  Thus,
the block entered by a passenger train \emph{as well as one block
ahead} must be free of moving freight trains, but there could be a
freight train kept waiting in one of the sidings.

This problem can be analyzed as a maximum flow problem for the
movement of freight trains on a network whose nodes represent the
signal blocks at the start of each time slot.

\begin{center}
\begin{tikzpicture}
  \foreach \x in {0,5,...,15}
    {\node at (0.3*\x,0) {\small\x\,min};
     \foreach \y in {1,...,6}
      {\node at (0.3*\x,\y) [circle,draw] {};}}
  
   \node at (-1.5,6) {\small Block A};
   \node at (-1.5,5) {\small Block B};
   \node at (-1.5,4) {\small Block C};
   \node at (-1.5,3) {\small Block D};
   \node at (-1.5,2) {\small Block E};
   \node at (-1.5,1) {\small Block F};
\end{tikzpicture}
\end{center}

At time $t=0\,\text{min}$, a passenger train enters the the first
block A.  The schedule repeats every 15 minutes, so that the occupancy
of blocks at $t=0\,\text{min}$ and $t=15\,\text{min}$, as well as the
respective in- and outflows must coincide.

\begin{enumerate}
\item Mark the signal blocks occupied by the passenger train
in the network graph.

\item Indicate with arcs the possible movement of freight trains in
the network.  Each node in the top layer can receive unrestricted
inflow, each node at the bottom layer can have an outflow subject to
the restrictions explained above.


\item How many freight trains can enter the line during each 15 minute
period?  

\item How much time do to the freight trains spend waiting in a siding?

\end{enumerate}


\end{enumerate}
\hfill(5+5+5+5)
\newpage\mbox{}\newpage
\end{document}