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


\begin{document}

\title{Operations Research}
\author{Homework 7}
\date{Due in class Wednesday, April 6, 2016}
\maketitle


\begin{enumerate}

\item Take the Pyomo file \texttt{20160318-Reliable-CMPmethod.ipynb}
demonstrating the project time crashing optimization problem.  Modify
the code to
\begin{enumerate}
\item Compute the minimal time to completion without crashing, and
\item Compute the minimal time to completion with full crashing, and
the minimal associated extra cost.
\end{enumerate}

\item \emph{(HL, Exercise 9.8-4.)} The 21st Century Studios is about to
begin the production of its most important (and most expensive) movie
of the year.  The movie's producer, Dusty Hoffmer, has decided to use
PERT/CPM to help plan and control this key project. He has identified
the eight major activities (labeled $A, B, \dots, H$) required to
produce the movie.  Their precedence relationships are shown in the
project network below.
\begin{center}
\newdimen\nodeDistance
\nodeDistance = 2cm
\tikzset{
    position/.style args={#1:#2 from #3}{
        at=(#3.#1), anchor=#1+180, shift=(#1:#2)
    }
}
\begin{tikzpicture}[shorten >=1pt,node distance=\nodeDistance,on grid]
  \node[state] (O)                    {START};
  \node[state] (A) [position=30:{\nodeDistance} from O]  {$A$};
  \node[state] (B) [position=-30:{\nodeDistance} from O] {$B$};
  \node[state] (C) [position=15:{\nodeDistance} from A]  {$C$};
  \node[state] (D) [position=-15:{\nodeDistance} from A] {$D$};
  \node[state] (G) [position=-15:{\nodeDistance} from C] {$G$};
  \node[state] (E) [position=15:{\nodeDistance} from B]  {$E$};
  \node[state] (F) [position=-15:{\nodeDistance} from B] {$F$};
  \node[state] (H) [position=-15:{\nodeDistance} from E] {$H$};
  \node[state] (T)[position=-30:{\nodeDistance} from G] {FINISH};
\tikzset{mystyle/.style={->}} 
\path (O) edge [mystyle] (A)
      (O) edge [mystyle] (B)
      (A) edge [mystyle] (C)
      (A) edge [mystyle] (D)
      (B) edge [mystyle] (E)
      (B) edge [mystyle] (F)
      (C) edge [mystyle] (G)
      (E) edge [mystyle] (G)
      (D) edge [mystyle] (H)
      (F) edge [mystyle] (H)
      (G) edge [mystyle] (T)
      (H) edge [mystyle] (T);
\end{tikzpicture}
\end{center}
Dusty now has learned that another studio also will be coming out with
a blockbuster movie during the middle of the upcoming summer, just
when his movie was to be released.  This would be very unfortunate
timing.  Therefore, he and the top management of 21st Century Studios
have concluded that they must accelerate production of their movie and
bring it out at the beginning of the summer (15 weeks from now) to
establish it as \emph{the} movie of the year.  Although this will
require substantially increasing an already huge budget, management
feels that this will pay off in much larger box office earning both
nationally and internationally. 

Dusty now wants to determine the least costly way of meeting the new
deadline 15 weeks hence.  Using the CPM method of time-cost
trade-offs, he has obtained the following data.

\begin{center}
\begin{tabular}{ccccc}
\hline
  \textbf{Activity}$\vphantom{1^{1^1}}$ & \textbf{Normal Time} & 
  \textbf{Crash Time} & \textbf{Normal Cost} & \textbf{Crash Cost} \\
\hline
$A^{\vphantom{\tfrac11}}$ & 5 weeks & 3 weeks & \$24 million & \$36 million \\
$B$ & 3 weeks & 2 weeks & \$13 million & \$25 million \\
$C$ & 4 weeks & 2 weeks & \$21 million & \$29 million \\
$D$ & 6 weeks & 3 weeks & \$30 million & \$50 million \\
$E$ & 5 weeks & 4 weeks & \$26 million & \$36 million \\
$F$ & 7 weeks & 4 weeks & \$35 million & \$57 million \\
$G$ & 9 weeks & 5 weeks & \$30 million & \$53 million \\
$H$ & 8 weeks & 6 weeks & \$35 million & \$51 million \\
\hline
\end{tabular}
\end{center}
Use Pyomo to compute the optimal schedule to achieve completion in 15
weeks. 


\item Recall that the maximum flow problem for a network with node set
$N$ and arc set $A$ can be formulated as a linear programming problem:
\begin{equation*}
\begin{gathered}
  \text{maximize } \sum_{(i,T) \in A} x_{iT} \\
  \text{subject to } \sum{(i,j) \in A} x_{ij} = \sum_{(j,i) \in A)} x_{ji} 
  \text{ for every } j \in N \backslash \{ S,T \} \\
  \text{and } 0 \leq x_{ij} \leq u_{ij} \,,
\end{gathered}
\tag{P1}
\end{equation*}
where $S$ is the source node, $T$ is the final (sink) node, $u_{ij}$
are the maximal capacities of the arcs, and the decision variable
$x_{ij}$ is the flow through arc $(i,j)$.

There is an alternative linear programming formulation: let
$\mathcal{P}$ denote the set of all paths from $S$ to $T$.  Let $x_p$
denote the flow through the path $p \in \mathcal P$.  Then the problem
can be formulated as follows:
\begin{equation*}
\begin{gathered}
   \text{maximize } \sum_{p \in \mathcal P} x_p \\
   \text{subject to } \sum_{p \colon a \in p} x_p \leq u_a
   \text{ for every } a \in A \\
   \text{and } x_p \geq 0 \,.
\end{gathered}
\tag{P2}
\end{equation*}
The sum in the constraint is to be understood as follows: we fix an
arc $a\in A$ and then sum over all paths from $S$ to $T$ which contain
this selected arc.  We also write $u_a$ as shorthand for $u_{ij}$ when
$a=(i,j)$.  

Formulation (P2) is only of theoretical interest, because the number
of paths from $S$ to $T$ typically increases exponentially with the
size of the network, so that it does not provide an efficient way to
solve the maximum flow problem.

\begin{enumerate}
\item Give an argument why (P1) and (P2) are equivalent.
\item (P2) has the form of the standard ``resource allocation
problem''.  Verify this statement by listing the analogies to
\emph{resource}, \emph{activity}, and \emph{profit}.

\item (P2) has a standard dual.  Write it out and interpret the
meaning of the dual variables in the network context.
\end{enumerate}



\end{enumerate}
\end{document}
