\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{Mock Midterm Exam}
\date{October 29, 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 With the start of school approaching, a store is planning on
having a sale on school materials. They have 600 notebooks, 500
folders and 400 pens in stock, and they plan on packing it in two
different forms. In the first package, there will be 2 notebooks, 1
folder and 2 pens, and in the second one, 3 notebooks, 1 folder and 1
pen. The price of each package will be \euro 6.50 and \euro 7.00,
respectively. How many packages should they put together of each type
to obtain the maximum revenue, assuming that all packages will be sold?
% From https://www.superprof.co.uk/resources/academic/maths/linear-algebra/linear-programming/linear-programming-word-problems.html
\mbox{}\hfill(10)

\item Consider linear programming problem
\begin{gather*}
  \text{maximize } z = x_1 + 2 \, x_2
\end{gather*}
subject to
\begin{gather*}
  -2 \, x_1 + x_2 + x_3 \leq 2 \,, \\
  - x_1 + x_2 - x_3 \leq 1 \,, \\
  x_1, x_2, x_3 \geq 0 \,.
\end{gather*}
\begin{enumerate}
\item Write this LP in the standard form.
\item Perform the simplex algorithm until you reach a stopping point.
Note that the final tableau corresponds to an unbounded solution.
\item Find a feasible solution for which the objective function
takes a value of at least $z=1000$.
\item Write out the \emph{dual} problem to this LP.
\item Show that the feasible region of the dual is empty.
\end{enumerate}
\hfill(3+7+3+4+4)

%\newpage\mbox{}
\newpage

\item Find the minimum cut in the network below.  Describe in words
how you found the solution.
\begin{center}
\begin{tikzpicture}[>=stealth',
                    shorten >=1pt,
                    node distance=2cm and 3cm,
                    on grid,
                    initial/.style={}]
  \node[state] (O)                    {O};
  \node[state] (A) [above right=of O] {A};
  \node[state] (B) [below right=of O] {B};
  \node[state] (C) [right=of A]       {C};
  \node[state] (D) [right=of B]       {D};
  \node[state] (T) [below right=of C] {T};
\tikzset{mystyle/.style={->}} 
\tikzset{every node/.style={auto}} 
\path (O) edge [mystyle] node[above left] {3} (A)
      (O) edge [mystyle] node[below left] {9} (B)
      (B) edge [mystyle] node {7} (A)
      (A) edge [mystyle] node {4} (C)
      (C) edge [mystyle] node[pos=0.25,below right] {3} (B)
      (A) edge [mystyle] node[pos=0.25,below left] {4} (D)
      (B) edge [mystyle] node[below] {2} (D)
      (C) edge [mystyle] node {8} (D)
      (C) edge [mystyle] node[above right] {3} (T)
      (D) edge [mystyle] node[below right] {8} (T);
\end{tikzpicture}
\end{center}
% From https://www.lix.polytechnique.fr/~liberti/teaching/dix/inf572-10/exercises-nosol.pdf
\mbox{}\hfill(10)

\item A museum director must decide how many guards should be employed
to control a new wing. Budget cuts have forced him to station guards
at each door, guarding two rooms at once. Formulate a linear program
to minimize the number of guards, referring to the map below.  (No
need to solve the problem on the exam.)
\begin{center}
\includegraphics[width=8cm]{museum.pdf}
\end{center}
% From https://www.lix.polytechnique.fr/~liberti/teaching/dix/inf572-10/exercises-nosol.pdf
% Attributed to P. Belotti, CMU
\mbox{}\hfill(10)

\item Consider the Pyomo program attached.



\begin{enumerate}
\item Write out the problem that is being solved in mathematical
notation.

\item Describe what the program does in plain language.  You may
choose a concrete application scenario beyond what is implied by the
names in the code.

\item What happens if you change the declaration of the decision
variables from \texttt{within=Boolean} to
\texttt{within=NonNegativeReals}?

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


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