\be
\item A network consists of 5 nodes, labeled 1-5, whose net outflows are $2, -3, 4, -2$ and $-1$, respectively. Assume that the flow capacity along each arc connecting any two pair of nodes is 2, with the exception of any arc starting at the third node, which has flow capacity 1. If the matrix
    \begin{equation*}
    C= \begin{bmatrix} 1 & 2 & 1 & 4 & 3 \\
    1 & 3 & 3 & 2 & 1 \\
    3 & 4 & 1 & 2 &1 \\
    4 & 4 & 3 & 3 & 3 \\
    1 & 1 & 2 & 1 & 3
    \end{bmatrix}
    \end{equation*}
records the cost per unit flow between any two nodes, determine the solution to the corresponding
minimum cost network flow problem.


\item The figure below illustrates a network
consisting of 5 nodes and 6 paths, together with the flow capacity along each arc. Find
the maximum flow from node 1 to node 5.

\begin{figure}[h]
\centering
\includegraphics{images/f04x03x05.eps}
\hfil
\label{Fi:BasicNetworkModelsMaximumFlowExercise}
\end{figure}


\item Consult a road atlas and determine the route of shortest driving distance from Billings to Great Falls, Montana that uses only interstate and U.S. highways. Then determine the route of shortest time duration, assuming interstate highway speeds of 70 miles per hour and U.S. highway speeds of 55 miles per hour.

\item A hospital discharges to its outpatient system a portion of its patients, each of whom receives one of three types of follow-up services: speech therapy, physical therapy, and occupational therapy. Each therapy type is performed at two different
    outpatient clinics.\footnote{Based upon Duncan and Noble,
    \cite{Duncan_Hospital_Allocation}, (1979).} Table \ref{Ta:ShortestPath_MaximumFlow_HospitalResources}
indicates the maximum number of new outpatient admissions of a specified therapy type that each clinic can accept during any given day.

    \begin{table}[h]
\caption{Maximum number of outpatient admissions of each therapy type at each clinic}\label{Ta:ShortestPath_MaximumFlow_HospitalResources}
\begin{tabular}{|l|c|c|c|}
\hline
Therapy Type/Clinic & Clinic 1 & Clinic 2 \\ \hline
Speech  & 3 & 2 \\ \hline
Physical & 6 & 4 \\ \hline
Occupational & 2 & 3 \\ \hline
\end{tabular}
\end{table}

\noi
Assume that the hospital can discharge at most 10 patients daily to each clinic and that both speech and occupational therapy services can perform up to 5 daily discharges from the outpatient system but that physical therapy can only perform up to 4. Assume also that at most 3 patients can have services transferred from one clinic to the other on any given day.

\newpar
Suppose the hospital represents the source and the state of complete discharge denotes
the sink. Using the clinics and therapy types as nodes in the network, determine the maximum number of patients the hospital can discharge daily for outpatient services.

\ee


