\documentclass[12pt]{article}
\usepackage{fullpage,amsmath,amsfonts,eurosym,graphicx}
\usepackage{tikz,calc}
\usetikzlibrary{arrows,positioning,automata}


\begin{document}

\title{Operations Research}
\author{Homework 6}
\date{Due via Moodle/Mailbox by Wednesday, October 21, 2020}
\maketitle


\begin{enumerate}



\item A construction company needs a heavy excavator for a three-year
project.  Since maintenance is expensive, it may be cheaper to replace
the machine in the interim.  The overall net cost (in 1000\,\euro) of
purchasing the excavator at the beginning of year $i$ and trading it
at the end of year $j$ is as follows.

\begin{center}
\begin{tabular}{cc@{~~~~~~~~~~~~}c@{~~~~~~~~~~~~}c}
\hline
& \multicolumn{3}{c}{\textbf{Trade in end of year}} \\
  \textbf{Purchase start of year}$\vphantom{1^{1^1}}$ & \textbf{1} &
  \textbf{2} & \textbf{3} \\
\hline
\textbf{1}$^{\vphantom{\tfrac11}}$ & 25 & 60 & 95 \\
\textbf{2}                         & -- & 29 & 65 \\
\textbf{3}                         & -- & -- & 37 \\
\hline
\end{tabular}
\end{center}
The task is to find the most economical schedule of purchasing and
trading in the excavator(s).

\begin{enumerate}
\item Draw a graphical representation and show that this is a shortest
path problem.
\item Solve the problem.  This is most easily done by hand in this
case. 
\end{enumerate}

\item 
\begin{enumerate}

\item Write a Pyomo program to solve the maximum flow problem for the
Seervada Park example from Hillier and Lieberman, with the network
data reproduced here.  The arcs are directed and have a flow capacity
as indicated.

\item Ask the solver to return dual variables as well.  Print out the
dual variables that correspond to the capacity constraints.  Use the
results to identify the minimum cut and draw the minimum cut into the
network. 
\end{enumerate}

\begin{center}
\begin{tikzpicture}[>=stealth',shorten >=1pt,node distance=3cm,on grid,initial/.style    ={}]
  \node[state] (O)                    {O};
  \node[state] (A) [above right of=O] {A};
  \node[state] (B) [below right of=A]  {B};
  \node[state] (C) [below right of=O] {C};
  \node[state] (E) [below right of=B] {E};
  \node[state] (D) [above right of=E] {D};
  \node[state] (T) [right of=D] {T};
\tikzset{mystyle/.style={->}} 
\tikzset{every node/.style={auto}} 
\path (O) edge [mystyle] node {5} (A)
      (O) edge [mystyle] node {7} (B)
      (O) edge [mystyle] node {4} (C)
      (A) edge [mystyle] node {3} (D)
      (A) edge [mystyle] node[swap] {1} (B)
      (B) edge [mystyle] node {2} (C)
      (B) edge [mystyle] node[swap] {4} (D)
      (B) edge [mystyle] node {5} (E)
      (C) edge [mystyle] node {4} (E)
      (D) edge [mystyle] node {9} (T)
      (E) edge [mystyle] node {1} (D)
      (E) edge [mystyle] node[swap] {6} (T);
\end{tikzpicture}
\end{center}

\end{enumerate}

\end{document}
