\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 10, 2020}
\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
\begin{enumerate}
\item
Use the graphical method to maximize
\begin{gather*}
  z = 2\, x + 3 \, y
\end{gather*}
subject to
\begin{gather*}
  x + y \leq 3 \,, \\
  3 \, x - x^2 - y \geq 0 \,, \\
  x, y \geq 0 \,.
\end{gather*}
\item Is this a convex optimization problem?  What can you conclude
for this problem if convexity was/is satisfied? 
\end{enumerate}
\hfill(10+5)


\item The Chemtails Supply Co.\ produces scientific laboratory
equipment.  Production is done by three teams who each need a given
amount of time for each unit produced.  The unit profit for each
product is known and it is assumed that all units that are produced
will be sold.  Each team has a certain number of hours available.
Further, the company has long-term supply contracts for two of their
products, the microscope and the Bunsen burner, that require a certain
minimum number of units per week to be produced.

The weekly production schedule has been planned using the Pyomo
notebook attached.  Given the data and the output from this notebook,
answer the following questions.

\begin{enumerate}
\item Marketing suggests a discount campaign, lowering the price of a
thermometer by \euro\,1.  How will this affect profits on the given
weekly production schedule?

\item A member of Team~1 is sick and misses one day (8 hours) of work.
Estimate the decrease in profit if (i) no other worker can replace her
or (ii) a worker of Team~2 can take over her work or (iii) only a
worker of Team~3 can take over her work.

\item Management would like to increase production in the short term
to meet surging demand and decides to offer workers an overtime bonus
of half of the marginal increase in profits generated by extra work.
Compute the bonus on the hourly wage for each of the teams.

\item Controlling are reviewing the long-term contracts.  Give a
recommendation toward a possible re-negotiation of the terms of these
contracts.

\item Sales are finding out that they cannot sell more than 100 safety
goggles per week at full price.  Any additional pairs need to be
discounted by \euro\,3.  Suggest changes to the Pyomo code that model
this additional constraint.

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



\item Suppose each of the following tableaus occurs in the course of
performing the simplex algorithm on a linear programming problem in
standard form.
\begin{enumerate}
\item\newcolumntype{B}{%
  >{\columncolor[gray]{.8}[.5\tabcolsep]}c}
\begin{tabular}{BcBc|c}
  $x_1$ & $x_2$ & $x_3$ & $x_4$ \\
  \hline
  $0$ & $-1$ & $1$ & $-1$ & $2$  \\
  $1$ & $0$ & $0$ & $2$ & $3$ \\
  \hline
  $0$ & $-1$ & $0$ & $3$ & $4$
\end{tabular}
\item
\begin{tabular}{ccBB|c}
  $x_1$ & $x_2$ & $x_3$ & $x_4$ \\
  \hline
  $0$ & $0$ & $0$ & $1$ & $-1$  \\
  $0$ & $0$ & $1$ & $0$ & $1$ \\
  \hline
  $2$ & $1$ & $0$ & $0$ & $10$
\end{tabular}
\item
\begin{tabular}{cBBc|c}
  $x_1$ & $x_2$ & $x_3$ & $x_4$ \\
  \hline
  $2$ & $1$ & $0$ & $1$ & $1$  \\
  $1$ & $0$ & $1$ & $4$ & $3$ \\
  \hline
  $-3$ & $0$ & $0$ & $-1$ & $8$
\end{tabular}
\end{enumerate}

State, for each case:
\begin{itemize}
\item Whether the problem is feasible.
\item If the problem is feasible, whether the solution represented by the tableau is optimal.
\item If the solution represented by the tableau is not optimal, if
bounded optimal solutions exist and how to to choose the entering and
leaving variable for the next iteration of the algorithm.
\end{itemize}
\hfill (5+5+5)


\item You are traveling home for the holidays.  You have bought a
number of presents for family and friends, listed in the table below.
In your baggage, you have an allowance of 5\,kg left.  Which presents
should you take along and which should you leave for another time if
you intend to maximize the total value taken home?

\begin{center}
\begin{tabular}{lcccccccccc}
\hline
\textbf{Item}$^{\vphantom{\tfrac11}}$ & 
 1 & 2& 3& 4& 5 \\
\textbf{Value [EUR]} & 
 20 & 5 & 25 & 10& 20 \\
\textbf{Weight [kg]} & 
 2 & 1 & 4 & 1& 3 \\
\hline
\end{tabular}
\end{center}

Use dynamic programming to solve this problem.  (No credit will be
given for a brute-force solution which is possible for the small
problem at hand, but does not scale well with problem size.)

\hfill(15)





\item
% From: W. L. Winston, "Operations Research, Application and Algorithms"
Sailco manufactures sailboats. During the next 4 months the
company must meet the following demands for their sailboats:
\begin{center}
\begin{tabular}{lcccc}
\hline
\textbf{Month}$^{\vphantom{\tfrac11}}$ & 
 1 & 2& 3& 4 \\
\textbf{Number of boats} & 
 40 & 60 & 70 & 25 \\
\hline
\end{tabular}
\end{center}
At the beginning of Month 1, Sailco has 10 boats in inventory.  Each
month it must determine how many boats to produce.  During any month,
Sailco can produce up to 40 boats with regular labor and an unlimited
number of boats with overtime labor. Boats produced with regular labor
cost \euro\,400 each to produce, while boats produced with overtime
labor cost \euro\,450 each. It costs \euro\,20 to hold a boat in
inventory from one month to the next.  The goal is to determine the
production and inventory schedule that minimizes the cost of meeting
the next 4 months' demands.

Since there are no setup costs for production, this problem can be
formulated as a min cost flow problem.
\begin{enumerate}
\item Show that this is indeed a min cost flow problem by drawing the
network.  Label all nodes and arcs with the relevant quantities from
the text.
\item Write out the corresponding linear program.  You may use indexed
variables for data and decision variables.  There is no need to copy
the concrete problem data from part (a).  You do not need to solve
this problem.
\end{enumerate}
\hfill(5+5)



\item
% From
% http://user.engineering.uiowa.edu/~dbricker/OR_Sample_HW/OR_HW_F02_Soln.pdf
% Problem credited to
% Operations Research: a Practical Introduction, by M. Carter & C. Price
You are about to buy a used car and you have narrowed your choice down
to two possible models: one car is a private sale and the other is
from a dealer.  The cars are similar, and the only criterion is to
minimize expected cost.  The dealer car is more expensive, but it
comes with a limited warranty.  You decide that, if the car will last
for 1 year, you can sell it again and recover a large part of your
investment.  If it falls apart, it will not be worth fixing. After
test driving both cars and checking for obvious flaws, you make the
following evaluation of probable resale values:
\begin{center}
\begin{tabular}{|l|ccc|}
\hline
& \textbf{Purchase$\vphantom{1^{1^1}}$} & \textbf{Est.} &
\textbf{Probability of} \\
\textbf{Car}$\vphantom{1^{1^1}}$ & 
  \textbf{price} & \textbf{resale value}  & \textbf{lasting one year} \\
\hline
\textbf{Private (A)}$\vphantom{1}^{\vphantom{\tfrac11}}$ &
  \euro\,800 & \euro\,600 & 0.3 \\
\textbf{Dealer (B)} & \euro\,1\,500 & \euro\,1\,000 & 0.9 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}
\item Which car would you buy, based on risk-neutral valuation?
(Assume that no replacement is required should the car break down.)
\item What is the expected value of perfect information on car A?
\item Suppose you have the opportunity to take car A to an independent
mechanic who will charge \euro\,50 for doing an inspection and offer
an opinion as to whether the car will last one year.  Suppose you
estimate the following probabilities to the accuracy of the mechanic's
opinion:
\begin{center}
\begin{tabular}{|l|cc|}
\hline
& \textbf{Mechanic says YES}$\vphantom{1^{1^1}}$ & 
  \textbf{Mechanic says NO} \\
\hline
\textbf{Car will last 1 year}$\vphantom{1}^{\vphantom{\tfrac11}}$ &
  0.7 & 0.3 \\
\textbf{Car won't last 1 year} & 0.1 & 0.9 \\
\hline
\end{tabular}
\end{center}
Formulate this problem as a decision tree and determine the optimal
strategy. 
\end{enumerate}
\hfill(5+5+10)

\end{enumerate}

\end{document}