\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 in class Tuesday, October 24, 2017}
\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 \emph{(From HL, Problem~8.3-2.)} Four cargo ships will be used
for shipping goods from one port to four other ports (labeled 1, 2, 3,
4).  Any ship can be used for making any one of these four trips.
However, because of differences in the ships and cargoes, the total
cost of loading, transporting, and unloading the goods for the
different ship-port combinations varies considerably, as shown in the
following table:

\begin{center}
\begin{tabular}{lcccc}
\hline
& \multicolumn{4}{c}{\textbf{Port}$\vphantom{1^{1^1}}$} \\
& \textbf{1}$\vphantom{1^{1^1}}$ & \textbf{2} &
  \textbf{3} & \textbf{4} \\
\hline
\textbf{Ship 1}$^{\vphantom{\tfrac11}}$ & \$500 & \$400 & \$600 & \$700 \\
\textbf{Ship 2} & \$600 & \$600 & \$700 & \$500 \\
\textbf{Ship 3} & \$700 & \$500 & \$700 & \$600 \\
\textbf{Ship 4} & \$500 & \$400 & \$600 & \$600 \\
\hline
\end{tabular}
\end{center}
The objective is to assign the four ships to four different ports in
such a way as to minimize the total cost for all four shipments.

\begin{enumerate}
\item Let $x_{ij}=1$ if ship $i$ is sent to port $j$ with $x_{ij}=0$
otherwise.  (A problem of this form is called an assignment problem.)
Formulate and solve this problem in Pyomo.  You should submit a
printout of your Ipython notebook showing code and solution.

\emph{Hint:} In Pyomo, you can declare a variable to take only values
$0$ and $1$ by using the option \verb+within=Boolean+.

\item Now suppose you drop the requirement that the $x_{ij}$ are
Boolean and replace it with the usual non-negativity requirement.  In
other words, you are allowing to send ``a fraction of a ship'' to one
port and another fraction to another.  Re-solve the problem in Pyomo.
What do you see?

% \item \emph{Extra credit:} Can you come up with a more general
% mathematical statement and a proof of what you have seen?

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