\section{Transportation and Transshipment Problems}\label{S:Transportation_Transshipment}
\setcounter{progress_ck_counter}{0}

\noi Many linear programming problems focus on cost-effective ways to transport goods and services of one type or another.

\subsection{A Coal Distribution Problem}\label{SS:Transportation_Transhipment_Coal_Delivery}\index{transportation problem}

\noi Three coal mines transport coal to four different municipal power plants. Suppose the mines, which we label as Mine 1, 2, and 3, have respective annual productions of 500,000; 500,000; and 400,000 tons. The four municipalities, Cities 1, 2, 3, and 4, have corresponding annual demands of 400,000; 300,000; 500,000; and 200,000 tons. To each combination of a mine and city, there is a cost per unit amount associated with transporting coal from the mine to the city. Table \ref{Ta:Transportation_Transhipment_Coal_Delivery_Costs} summarizes costs, in units of millions of dollars per hundred thousand tons, for each different mine-city combination.

\begin{table}[h]
\caption{Mine-city transportation costs}\label{Ta:Transportation_Transhipment_Coal_Delivery_Costs}
\begin{tabular}{|l|c|c|c|c|}
\hline
Mine/City & City 1 & City 2 & City 3 & City 4 \\ \hline
Mine 1 & 2 & 3 & 2 & 4 \\ \hline
Mine 2 & 4 & 2 & 2 & 1 \\ \hline
Mine 3 & 3 & 4 & 3 & 1 \\
\hline
\end{tabular}
\end{table}

\newpar
We seek to construct an LP whose objective is to minimize the total cost of transporting the coal from the mines to the cities. Because the total coal amount produced by the mines equals the combined demand of the cities, this LP
constitutes a \emph{balanced transportation problem}\index{transportation problem!balanced}. Clearly if the total demand exceeds total available supply, any LP model attempting to minimize cost will prove infeasible. The case when total supply exceeds total demand is addressed in the exercises.

\newpar
We begin by defining $x_{ij}$, where $1 \leq i \leq 3$ and $1 \leq j \leq 4$, as the amount of coal, in hundreds of thousands of tons, transported from Mine $i$ to City $j$. Because of the double subscript nature of these decision variables, we enter them as an array in Maple:

\begin{maplelist}
\item \mf{x:=array(1..3,1..4);}
\mo{array(1..3,1 .. 4, [])}
\end{maplelist}

\noi If the entries of Table \ref{Ta:Transportation_Transhipment_Coal_Delivery_Costs} are also entered as a 3-by-4 array (matrix), labeled \mf{Cost}, the total transportation cost, in millions of
dollars, is computed as follows:
\begin{maplelist}
\item \mf{Cost:=Matrix(3,4,[2,3,2,4,4,2,2,1,3,4,3,1]):}
\item \mf{TotalCost:=add(add(Cost[i,j]*x[i,j],i=1..3),j=1..4);}

\MultiLineMapleOutput{TotalCost:=2x_{1,1}+3x_{1,2}+2x_{1,3}+4x_{1,4}+
4x_{2,1} \\ + 2x_{2,2}+2x_{2,3}+x_{2,4}+
3x_{3,1}
+4x_{3,2}+3x_{3,3}+x_{3,4}
}
\end{maplelist}

\newpar
As was the case for the Four-Sandwich Diet Problem from Section \ref{S:Maple_Diet_Problem}, the \mf{seq}
and \mf{add} commands, can be combined to ensure that supply and demand constraints are met. For example, suppose that the cities' respective demand amounts are defined by the list (or array or vector) named \mf{Demand}.
Then \mf{seq(add(x[i,j],i=1..3) >=Demand[j], j=1..4)} is a sequence of four inequalities, which, if satisfied, ensures that
demand is met.

\begin{progress_ck}
In a manner similar to that used for demand, define a list, \mf{Supply}, and use it to construct a sequence of inequalities that reflects the amount of supply available at each mine. Combine this sequence with that for demand to form a list of constraints for this transportation LP. Then solve the LP using Maple's \mf{LPSolve} command. Immediately after the \mf{LPSolve} command, enter the following commands, which assigns the decision variables their solution values and prints these values in tabular form.
Your results should agree with what appears below.

\begin{maplelist}
\item \mf{assign(\%[2]): \# Assign the decision variables to their solution values.}
\item \mf{print(x): \# Print the solution array in tabular format.}
\mo{  \begin{bmatrix} 2 & 0 & 3 & 0 \\ 0 & 3 & 2 & 0 \\ 2 & 0 & 0 & 2 \end{bmatrix}}
\end{maplelist}
\end{progress_ck}

\subsection{The Integrality of the Transportation Problem Solution}\label{SS:Transportation_Transhipment_Integrality}\index{transportation problem!integrality of solution}

\newpar
The solution of the Coal Distribution Problem has the property that all decision variables
are integer-valued. This is a trait we desire of LPs in a wide variety of contexts. In many situations we are forced to
use the techniques of integer linear programming, which form the basis of discussion in Chapter \ref{C:Integer_Linear_Programming}. Fortunately, the nature of the Coal Distribution Problem, in particular the form of its constraints, guarantees, a priori, an integer-valued solution.

\newpar
To explain this phenomenon in terms of matrix theory, we start
 with the general transportation problem consisting
of $m$ supply points and $n$ demand points. Let
$\ds \vecs= \begin{bmatrix} s_1 \\ s_2 \\ \vdots \\ s_m \end{bmatrix} $ and
$\vecd=\begin{bmatrix} d_1 \\ d_2 \\ \vdots \\ d_n \end{bmatrix}$ denote vectors in
$\R^m$ and $R^n$, whose entries record the supply amounts and demand amounts, respectively,
at each of the supply points and demand points. Assume further that entries in these
vectors are all integer-valued and that the problem is \emph{balanced}, meaning
$ \ds \sum_{i=1}^m s_i = \sum_{j=1}^n d_j$. If $x_{ij}$, where $1 \leq i \leq m$ and $1 \leq j \leq n$, denotes
the amount of goods delivered from supply point $i$ to demand point $j$ and if $c_{ij}$ denotes the corresponding cost, then the balanced transportation problem may be stated as

\begin{align}\label{E:Transportation_Transshipment_GeneralForm}
 \mbox{minimize } z &=\sum_{i=1}^m \sum_{j=1}^n c_{ij}x_{ij}   \\
	\mbox{ subject to} \notag\\
	\sum_{j=1}^n x_{ij} &= s_i \quad 1 \leq i \leq m \notag\\
	\sum_{i=1}^m x_{ij} &= d_j \quad 1 \leq j \leq n  \notag\\
	x_{ij} &\geq 0 \mbox{ for } 1 \leq i \leq m \mbox{ and } 1 \leq j \leq n.  \notag
	\end{align}

\noi
Observe that we may express each constraint as an equality due to the balanced nature of the LP.

\newpar
The constraints of LP (\ref{E:Transportation_Transshipment_GeneralForm}) can be written compactly if we introduce new notation. More specifically, let us define $\zerovec_{1 \times n}$ and $\onevec_{1 \times n}$ to be the row vectors in $\R^n$ of all zeros and all ones, respectively. Then the constraints
of (\ref{E:Transportation_Transshipment_GeneralForm}) can be expressed in partitioned matrix equation form as follows:

\begin{equation}\label{E:Transportation_Transshipment_MatrixForm}
\mbox{\raisebox{.1in}
{
\mbox{
$\ds m \mbox{ blocks}
\begin{cases}
\\
\\
\\
\end{cases}
 $}
 }
 }
\overbrace{\begin{bmatrix}
\onevec_{1 \times n} & \zerovec_{1 \times n} & \zerovec_{1\times n} & \cdots & \zerovec_{1 \times n} \\
\zerovec_{1 \times n} & \onevec_{1 \times n} & \zerovec_{1 \times n} & \cdots & \zerovec_{1 \times n}\\
\vdots & \vdots & \vdots & \vdots &  \vdots \\
\zerovec_{1 \times n} & \zerovec_{1 \times n} &  \ddots & \zerovec_{1 \times n} & \onevec_{1 \times n} \\ I_n & I_n & \cdots & I_n & I_n
\end{bmatrix} }^{\mbox{$m$ blocks}}
\cdot
\begin{bmatrix} x_{11} \\ \vdots \\ x_{1n} \\ x_{21} \\ x_{22} \\ \vdots \\ x_{mn} \end{bmatrix}
= \begin{bmatrix} \vecs \\ \vecd \end{bmatrix}.
\end{equation}

\newpar
The $(m+n)$ by $mn$ coefficient matrix in (\ref{E:Transportation_Transshipment_MatrixForm}) takes a very special form that guarantees each of its square submatrices has determinant equal
to 0 or $\pm 1$. The proof of this fact uses basic determinant properties, and we do not include it here \cite{Heller_Tompkins_UnimodularMatrix}).

\newpar
Because the LP is balanced, the equation corresponding to the bottom row of matrix
equation (\ref{E:Transportation_Transshipment_MatrixForm}) is merely the sum of the
equations corresponding to the first $m$ rows, less the sum of those corresponding to rows
$m+1$ through $m+n$. It follows that (\ref{E:Transportation_Transshipment_MatrixForm})
can be rewritten as
\begin{equation}\label{E:Transportation_Transshipment_MatrixForm2}
A\vecx=\vecb,
\end{equation}
where $A$ is an $(m+n-1)$-by-$mn$ matrix, $\vecx$ is a vector in $\R^{mn}$
consisting of $mn$ decision variables, and $\vecb$ is a vector $\R^{m+n-1}$ having integer-valued
entries.

\newpar
Our standard procedure for calculating a basic solution of (\ref{E:Transportation_Transshipment_GeneralForm}) requires us to
set $mn- (m+n-1) = (m-1)(n-1)$ decision variables to zero and solve for the remaining basic variables, assuming that the columns of $A$ corresponding to the basic variables form a linearly
independent set. Of course, the square matrix formed using these columns is an invertible
submatrix of the coefficient matrix in (\ref{E:Transportation_Transshipment_MatrixForm}), and
hence must have determinant equal to $\pm=1$. We leave it as an exercise to show that
{\underbar{any}} matrix
equation, $A\vecx=\vecb$, in which $A$ and $\vecb$ have integer entries
and $\det A = \pm 1$, leads to a solution vector $\vecx$ whose entries are also integer-valued. Thus,
we arrive at the following theorem.

\begin{theorem}\label{Th:Transportation_Transshipment_IntegralSolutions}\index{transportation problem!integrality of solution}
The decision variable values in any basic solution of a transportation problem
are integer-valued, provided the problem is balanced and the demand and supply amounts are themselves integer-valued. Hence, the decision variable values in the optimal solution of such an LP are also integer-valued.
\end{theorem}


\subsection{Coal Distribution with Transshipment}\label{SS:Transportation_Transhipment_Coal_Transshipment}\index{transportation problem!with transshipment}

\noi We now consider a variant on our coal shipment problem by adding two intermediate points between the mines and the cities. In the context of this problem, these intermediate points, sometimes referred to as \emph{transshipment} points, can be thought of as railyard facilities where shipments from different mines are combined and then delivered to each of the four cities. In this situation, there exists a cost per unit amount to transfer coal from each mine to each transshipment point and from each transshipment point to each city. These costs, in millions of dollars per one hundred thousand tons, are summarized in Tables
\ref{Ta:Transportation_Transhipment_Mine_to_Transshipment_Points} and
\ref{Ta:Transportation_Transhipment_to_City}, where we have labeled the transshipment points as Station 1 and Station 2.

\begin{table}[h]
\caption{Mine-railyard transportation costs}\label{Ta:Transportation_Transhipment_Mine_to_Transshipment_Points}
\begin{tabular}{|l|c|c|}
\hline
Mine/Station & Station 1 & Station 2  \\ \hline
Mine 1 & 4 & 3 \\ \hline
Mine 2 &  5 & 4 \\ \hline
Mine 3 &  2 & 4 \\
\hline
\end{tabular}
\end{table}

\begin{table}[h]
\caption{Railyard-city transportation costs}\label{Ta:Transportation_Transhipment_to_City}
\begin{tabular}{|l|c|c|c|c|}
\hline
Station/City & City 1 & City 2  & City 3 & City 4\\ \hline
Station 1 & 3 & 5 & 4 & 3 \\ \hline
Station 2 &  4 & 3 & 4 & 4 \\
\hline
\end{tabular}
\end{table}

\noi To minimize the cost of transporting the coal from the mines to the cities, we view the problem as one combining two separate transportation problems. In the first of these, transshipment points are viewed as ``demand points''; in the second, they constitute ``supply points.'' Combined with these two problems are constraints, sometimes referred to as \emph{conservation constraints}\index{conservation constraints}, which reflect the requirement that the amount of coal entering a transshipment point is the same as the amount leaving.

\newpar
In a manner similar to that for the original problem, we use arrays to record the shipment amounts between the various points.  We define $x_{ij}$ where $1 \leq i \leq 3$ and $1 \leq j \leq 2$, as the amount of coal transported from Mine $i$ to Station $j$. Similarly, $y_{jk}$, where
$1 \leq j \leq 2$ and $1 \leq k \leq 4$, denotes the amount transported from Station $j$ to City $k$.
In Maple we have:

\begin{maplelist}
\item \mf{x:=array(1..3,1..2):}
\item \mf{y:=array(1..2,1..4):}
\end{maplelist}

\noi Entries from Tables \ref{Ta:Transportation_Transhipment_Mine_to_Transshipment_Points} and
\ref{Ta:Transportation_Transhipment_to_City} can be entered as two matrices, which we label
\mf{CostTo} and \mf{CostFrom}. Using them, we construct the total transportation cost as follows:

\begin{maplelist}
\item \mf{CostTo:=Matrix(3,2,[4,3,5,4,2,4]):}
\item \mf{CostFrom:=Matrix(2,4,[3,5,4,3,4,3,4,4]):}
\item \mf{TotalCost:=add(add(CostTo[i,j]*x[i,j],i=1..3),j=1..2)+ \newline
add(add(CostFrom[j,k]*y[j,k],j=1..2),k=1..4):}
\end{maplelist}

\noi
Each constraint for the LP belongs to three one of the three categories:
\begin{enumerate}
\item The supply at each mine is the sum of the amounts transported from that mine to each of the stations.
\item The demand at each city is the sum of the amounts transported to that city from each of the stations.
\item Conservation constraints that guarantee the total amounts transported into and out of each station are equal.
\end{enumerate}
\noi Using the arrays \mf{x} and \mf{y} and the \mf{Demand} and \mf{Supply} lists defined in the first problem, we express these constraints in Maple as follows:
\begin{maplelist}
\item \mf{SupplyConstraints:=seq(add(x[i,j],j=1..2) <=Supply[i],i=1..3):}
\item \mf{DemandConstraints:=seq(add(y[j,k],j=1..2) >=Demand[k],k=1..4):}
\item \mf{NetFlowConstraints:=\newline seq(add(x[i,j],i=1..3)=add(y[j,k],k=1..4),j=1..2):}
\end{maplelist}

\begin{progress_ck}
Use the previously defined sequences to form a list of constraints and determine the entries of \mf{x} and \mf{y} that minimize total costs in this transshipment model.
\end{progress_ck}

\section*{Exercises Section \protect\ref{S:Transportation_Transshipment}}

\addcontentsline{toc}{subsection}{Exercises}

\input{Exercises/Exercises_Transportation_Transshipment}

\endinput 