\documentclass[12pt,a4paper]{article}

\usepackage{fullpage,amsmath,amsfonts,graphicx,colortbl,eurosym}
\usepackage{tikz,calc}
\usetikzlibrary{arrows,positioning,automata}


\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{Final Exam}
\date{December 21, 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 Use the graphical method to maximize
\begin{gather*}
  z = x + y
\end{gather*}
subject to
\begin{gather*}
  x^2 + y^2 \leq 20 \,, \\
  x \, y \leq 8 \,, \\
  x, y \geq 0 \,.
\end{gather*}
\hfill(20)


\item The attached Pyomo notebook shows a solution to the ``Diet
Problem''. 

\begin{enumerate}
\item State a concise formulation of the problem \emph{in words}.  (No
need to repeat the given numerical values of the data.)

\item Describe the meaning of the dual variables in words.

\item Which nutrient is supplied at more than its minimal requirement?
Explain your answer.

\item Suggest an additional constraint (or additional constraints) to
ensure that the resulting diet is more varied (without changing given
data of the problem).  State the idea in words and then write out the
corresponding lines of Pyomo code.
\end{enumerate}
\hfill(5+5+5+5)



\item You have decided to take advantage of your holidays and of the
recent heavy snowfall to try snowboarding. You hire the equipment at
the ski resort. The shop has three different offers: one day hiring
for 25\,\euro, two days 40\,\euro, and four days for 60\,\euro.

The weather forecast for the next 8 days is given in the following
table where a $1$ indicates that conditions are good for snowboarding
and a $0$ indicates that conditions are bad for snowboarding.  

\begin{center}
\begin{tabular}{lcccccccccc}
\hline
\textbf{Day}$^{\vphantom{\tfrac11}}$ & 
 1 & 2& 3& 4& 5& 6 & 7 & 8 \\
\textbf{Weather} & 
 1 & 0 & 1 & 1& 0& 1 & 0 & 1\\
\hline
\end{tabular}
\end{center}

Use dynamic programming to find out when and for how long to hire a
snowboard in order to minimize the total expense assuming you go
snowboarding if and only if the weather is good.
\hfill(20)

% From http://caseine.org/mod/resource/view.php?id=2049
% attributed to C. Rapine




\item A project consists of activities A, \ldots, G which have the
following dependencies:
\begin{center}
\begin{tikzpicture}[>=stealth',shorten >=1pt,node distance=3cm,on grid,initial/.style    ={}]
  \node[state] (O)                    {START};
  \node[state] (A) [above right of=O] {A\,(4)};
  \node[state] (B) [below right of=A] {B\,(1)};
  \node[state] (C) [right of=B] {C\,(2)};
  \node[state] (D) [above right of=C] {D\,(5)};
  \node[state] (E) [below of=B] {E\,(10)};
  \node[state] (F) [above right of=B] {F\,(4)};
  \node[state] (G) [below right of=C] {G\,(3)};
  \node[state] (T) [below right of=D] {FINISH};
\tikzset{mystyle/.style={->}} 
\tikzset{every node/.style={auto}} 
\path (O) edge [mystyle] node {} (A)
      (O) edge [mystyle] node {} (E)
      (A) edge [mystyle] node {} (B)
      (B) edge [mystyle] node {} (C)
      (C) edge [mystyle] node {} (G)
      (D) edge [mystyle] node {} (T)
      (A) edge [mystyle] node {} (F)
      (F) edge [mystyle] node {} (D)
      (E) edge [mystyle] node {} (C)
      (C) edge [mystyle] node {} (D)
      (G) edge [mystyle] node {} (T);
\end{tikzpicture}
\end{center}
The time (in days) that each step takes is indicated in parentheses.
Each day that the project is being worked on (independent of how many
activities are done in parallel) costs 1\,000\,\euro.  Furthermore,
special machinery must be rented from the beginning of task A up to
the end of task G at a cost of 5\,000\,\euro\ per day.

\begin{enumerate}
\item Formulate a linear program that minimizes the total cost of the
project.  You do not need to solve it, but you are required to state a
complete mathematical formulation.

\item In this case, the problem is simple enough to analyze it ``by
hand''.  Find the optimal solution.
\end{enumerate}
\hfill(10+10)

% Adapted from Section 4.2 of
% https://www.lix.polytechnique.fr/~liberti/teaching/isic/isc612-06/exercises-solutions.pdf



\item Consider the Goferbroke Co.\ problem discussed in class with the
following modified payoff table:
\begin{center}
\begin{tabular}{|l|cc|}
\hline
& \multicolumn{2}{c|}{\textbf{State of Nature}$\vphantom{1^{1^1}}$} \\
\textbf{Alternative}$\vphantom{1^{1^1}}$ & 
  \textbf{Oil} & \textbf{Dry}  \\
\hline
\textbf{Drill}$\vphantom{1}^{\vphantom{\tfrac11}}$ & $60$ & $-15$ \\
\textbf{Sell} & $10$ & $10$ \\
\hline
\textbf{Prior Probability}$\vphantom{1}^{\vphantom{\tfrac11}}$ 
& $1/3$ & $2/3$ \\
\hline
\end{tabular}
\end{center}
The Goferbroke Co.\ has to decide whether to drill for oil or to sell
the land.

\begin{enumerate}
\item Compute the expected payoffs for both alternatives.  What
decision should be taken based on a risk-neutral analysis?
\item A company offers exploration which returns the true state of
nature in $2/3$ of cases and gives a false result in $1/3$ of cases.
Compute the probability of obtaining a favorable exploration result
(i.e., one that indicates presence of oil), and
the probability of finding a non-favorable exploration result.
\item How much should you be willing to pay for these services?
\item How do you decide upon drilling or selling in response to the
exploration result?
\end{enumerate}
\hfill(5+5+5+5)

\end{enumerate}

\end{document}