\documentclass[12pt,a4paper]{article}

\usepackage{fullpage,amsmath,amsfonts,graphicx,colortbl,eurosym}


\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{October 27, 2017}
\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 Consider linear programming problem
\begin{gather*}
  \text{maximize } z = 3 \, x_1 + 2 \, x_2 + x_3
\end{gather*}
subject to
\begin{gather*}
  x_1 + x_2 + x_3 \leq 2 \,, \\
  3 \, x_1 + x_2 \leq 1 \,, \\
  x_1, x_2, x_3 \geq 0 \,.
\end{gather*}
\begin{enumerate}
\item Write out the \emph{dual} problem to this LP.
\item Solve the dual problem using the graphical method.
\item Which constraints in the dual formulation are binding?
\item Which variables in the primal formulation are basic?
\item Using your answer to (d), verify your solution by a direct
computation on the \emph{primal} problem.
\end{enumerate}
\hfill(5+10+3+3+4)

%\newpage\mbox{}\newpage


\item Consider the linear programming problem 
\[
  \text{maximize } z = 2 \, x_1 + x_2
\]
subject to
\begin{gather*}
  -x_1 + x_2 \leq 1 \,, \\
  x_1 - 2 \, x_2 \leq 2 \,, \\
  x_1, x_2 \geq 0 \,.
\end{gather*}
Determine the solvability of this problem and find the solution,
if it exists, \emph{using the simplex method}.
\hfill (20)
%\newpage

\item You are tasked with setting up an image processing pipeline for a
medical laboratory.  Images come from a database in LIFF, a format
specifically designed for microscope image processing.  The lab would
like to make these images available in PNG format via their web server.
Unfortunately, you do not have an LIFF-to-PNG converter.  However,
you have access to a large set of image converters which take the
following average times (in milliseconds) to convert an image.
Missing format converters are indicated by a dash.
\begin{center}
\begin{tabular}{lccccc}
\hline
 & \multicolumn{5}{c}{\textbf{Destination Format}$\vphantom{1^{1^1}}$} \\
\textbf{Source Format\quad} & \textbf{LIFF}$\vphantom{1^{1^1}}$ & \textbf{PNG} &
  \textbf{JPG} & \textbf{BPG} & \textbf{BMP} \\
\hline
\textbf{LIFF}$^{\vphantom{\tfrac11}}$ & -- & -- & 800 & 700 & 300 \\
\textbf{PNG} & 500 & -- & 600 & -- & -- \\
\textbf{JPG} & -- & 900 & -- & 700 & -- \\
\textbf{BPG} & 700 & 300 & 100 & -- & 600 \\
\textbf{BMP} & -- & 600 & 200 & 200 & -- \\
\hline
\end{tabular}
\end{center}
Find the most efficient way to realize the conversion from LIFF to
PNG. Illustrate your solution by drawing an appropriate network
representation of the problem.

\mbox{}\hfill(20)
 

%\newpage

\item The Pyomo program on the last page is showing a min-cost flow
problem similar to ``Distribution Unlimited'' Example from Hillier and
Lieberman. 

\begin{enumerate}
\item Draw the network that is described by the data in the code.

\item Management is considering investing in expanding the
transportation capacities on any of the currently capacity-constrained
routes.  Which route should be invested in first, assuming that it
costs the same on all routes to per unit increase of the maximal
capacity, and that the unit cost of transportation will not change?

\item The route from the distribution center DC to warehouse W1 is cut
due to road damage.  Is it possible to still supply the warehouses?
If not, how many units can you still deliver to the warehouses?  Which
problem did you solve to find out?

\item One truck can be loaded with 10 units of the product.  Thus, it
is desirable that the optimal solution will be in multiples of 10.
Which property of the data ensures that this is possible?

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


\end{enumerate}
%\newpage\mbox{}\newpage
\end{document}