\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 26, 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}

% From www.maths.unp.ac.za/coursework/MATH331/2012/linearprogramming.pdf
\item A furniture company produces tables and chairs.  Each table
takes $4$ hours of carpentry and $2$ hours of painting.  Each chair
requires $3$ hours of carpentry and $1$ hour of painting.  During the
current week, there are $240$ hours for carpentry work and $100$ hours
for painting available.  Each table is sold at a profit of \EUR 7
and each chair at a profit of \EUR 5.

Find the number of tables and chairs to produce in order to maximize
profit.  Use the graphical method to solve the resulting linear
programming problem. 
\hfill(20)



\item Perform one step of the simplex algorithm (choice of entering
variable, choice of leaving variable, elimination, check of
termination condition) on the following tableau:

\newcolumntype{B}{%
  >{\columncolor[gray]{.8}[.5\tabcolsep]}c}
\begin{center}
\begin{tabular}{cccBBB|c}
  $x_1$ & $x_2$ & $x_3$ & $s_1$ & $s_2$ & $s_3$  \\
  \hline
  $2$ & $1$ & $0$ & $1$ & $0$ & $0$ & $10$ \\
  $1$ & $2$ & $-2$ & $0$ & $1$ & $0$ & $20$ \\
  $0$ & $1$ & $2$ & $0$ & $0$ & $1$ & $5$ \\
  \hline
  $-1$ & $1$ & $-2$ & $0$ & $0$ & $0$ & $0$ 
\end{tabular}
\end{center}
\hfill (5+5+5+5)

\item The Brick \& Mortar Construction Co.\ needs to excavate a
construction pit with a total volume of $100\,\mathrm m^3$ for a
building extension.  The construction site is close to trees and other
buildings, so a large excavator could only be used for the first
$90\,\mathrm m^3$ at a cost of $1\,\text{\euro}/\mathrm m^3$ plus a
\EUR{1000} flat fee.  A mini excavator could be used for all but the
last $1\,\mathrm m^3$ at a cost of $10\,\text{\euro}/\mathrm m^3$ plus
a \EUR{100} flat fee.  Manual digging can be performed at
$100\,\text{\euro}/\mathrm m^3$ with no flat fee.

Consider all possible options to divide the work between a large
excavator, a mini excavator, and manual digging.  The objective is
minimizing the total cost.

\begin{enumerate}
\item Recognize this problem as a shortest path problem.  Draw the
network and assign the cost to each arc.

\item Solve the problem any way you like.
\end{enumerate}
\hfill (10+10)

\item The Pyomo program on the last page is solving a network optimization
problem. 

\begin{enumerate}
\item What problem is the program solving?  As part of your answer,
explain the meaning of the given data and of the objective function!

\item Draw the network which corresponds to the given data.

\item Give an interpretation of the dual variables.  Draw the
dual information obtained from the program output into your graph.

\item Suggest a change of the data so that the optimal value of the
objective function is increased by exactly one.

\item Can you be sure, without re-solving, that your suggested change
will achieve its goal?  Explain!  (Hint: look at the values of the
slack variables!)

\item Suppose the network nodes are ``leaky,'' losing exactly one unit
of flow each.  Suggest a change to the code to account for this.

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


\end{enumerate}

\end{document}