H Chapter Contents
H Chapter Introduction
NAG Library Manual

# NAG Library Routine DocumentH03ABF

Note:  before using this routine, please read the Users' Note for your implementation to check the interpretation of bold italicised terms and other implementation-dependent details.

## 1  Purpose

H03ABF solves the classical Transportation (‘Hitchcock’) problem.

## 2  Specification

 SUBROUTINE H03ABF ( KOST, LDKOST, MA, MB, M, K15, MAXIT, K7, K9, NUMIT, K6, K8, K11, K12, Z, IFAIL)
 INTEGER KOST(LDKOST,MB), LDKOST, MA, MB, M, K15(M), MAXIT, K7(M), K9(M), NUMIT, K6(M), K8(M), K11(M), K12(M), IFAIL REAL (KIND=nag_wp) Z

## 3  Description

H03ABF solves the Transportation problem by minimizing
 $z = ∑ i ma ∑ j mb cij xij .$
subject to the constraints
 $∑ j mb x i j = A i (Availabilities) ∑ i ma ∑ i x i j = B j (Requirements)$
where the ${x}_{\mathit{i}\mathit{j}}$ can be interpreted as quantities of goods sent from source $\mathit{i}$ to destination $\mathit{j}$, for $\mathit{i}=1,2,\dots ,{m}_{a}$ and $\mathit{j}=1,2,\dots ,{m}_{b}$, at a cost of ${c}_{\mathit{i}\mathit{j}}$ per unit, and it is assumed that $\sum _{i}^{{m}_{a}}{A}_{i}=\sum _{j}^{{m}_{b}}{\sum }_{j}{B}_{j}$ and ${x}_{ij}\ge 0$.
H03ABF uses the ‘stepping stone’ method, modified to accept degenerate cases.

## 5  Parameters

1:     KOST(LDKOST,MB) – INTEGER arrayInput
On entry: the coefficients ${c}_{\mathit{i}\mathit{j}}$, for $\mathit{i}=1,2,\dots ,{m}_{a}$ and $\mathit{j}=1,2,\dots ,{m}_{b}$.
2:     LDKOST – INTEGERInput
On entry: the first dimension of the array KOST as declared in the (sub)program from which H03ABF is called.
Constraint: ${\mathbf{LDKOST}}\ge {\mathbf{MA}}$.
3:     MA – INTEGERInput
On entry: the number of sources, ${m}_{a}$.
Constraint: ${\mathbf{MA}}\ge 1$.
4:     MB – INTEGERInput
On entry: the number of destinations, ${m}_{b}$.
Constraint: ${\mathbf{MB}}\ge 1$.
5:     M – INTEGERInput
On entry: the value of ${m}_{a}+{m}_{b}$.
6:     K15(M) – INTEGER arrayInput/Output
On entry: ${\mathbf{K15}}\left(\mathit{i}\right)$ must be set to the availabilities ${A}_{\mathit{i}}$, for $\mathit{i}=1,2,\dots ,{m}_{a}$; and ${\mathbf{K15}}\left({m}_{a}+j\right)$ must be set to the requirements ${B}_{\mathit{j}}$, for $\mathit{j}=1,2,\dots ,{m}_{b}$.
On exit: the contents of K15 are undefined.
7:     MAXIT – INTEGERInput
On entry: the maximum number of iterations allowed.
Constraint: ${\mathbf{MAXIT}}\ge 1$.
8:     K7(M) – INTEGER arrayWorkspace
9:     K9(M) – INTEGER arrayWorkspace
10:   NUMIT – INTEGEROutput
On exit: the number of iterations performed.
11:   K6(M) – INTEGER arrayOutput
On exit: ${\mathbf{K6}}\left(\mathit{k}\right)$, for $\mathit{k}=1,2,\dots ,{m}_{a}+{m}_{b}-1$, contains the source indices of the optimal solution (see K11).
12:   K8(M) – INTEGER arrayOutput
On exit: ${\mathbf{K8}}\left(\mathit{k}\right)$, for $\mathit{k}=1,2,\dots ,{m}_{a}+{m}_{b}-1$, contains the destination indices of the optimal solution (see K11).
13:   K11(M) – INTEGER arrayOutput
On exit: ${\mathbf{K11}}\left(\mathit{k}\right)$, for $\mathit{k}=1,2,\dots ,{m}_{a}+{m}_{b}-1$, contains the optimal quantities ${x}_{ij}$ which, sent from source $i={\mathbf{K6}}\left(k\right)$ to destination $j={\mathbf{K8}}\left(k\right)$, minimize $z$.
14:   K12(M) – INTEGER arrayOutput
On exit: ${\mathbf{K12}}\left(\mathit{k}\right)$, for $\mathit{k}=1,2,\dots ,{m}_{a}+{m}_{b}-1$, contains the unit cost ${c}_{ij}$ associated with the route from source $i={\mathbf{K6}}\left(k\right)$ to destination $j={\mathbf{K8}}\left(k\right)$.
15:   Z – REAL (KIND=nag_wp)Output
On exit: the value of the minimized total cost.
16:   IFAIL – INTEGERInput/Output
On entry: IFAIL must be set to $0$, $-1\text{​ or ​}1$. If you are unfamiliar with this parameter you should refer to Section 3.3 in the Essential Introduction for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value $-1\text{​ or ​}1$ is recommended. If the output of error messages is undesirable, then the value $1$ is recommended. Otherwise, if you are not familiar with this parameter, the recommended value is $0$. When the value $-\mathbf{1}\text{​ or ​}\mathbf{1}$ is used it is essential to test the value of IFAIL on exit.
On exit: ${\mathbf{IFAIL}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see Section 6).

## 6  Error Indicators and Warnings

If on entry ${\mathbf{IFAIL}}={\mathbf{0}}$ or $-{\mathbf{1}}$, explanatory error messages are output on the current error message unit (as defined by X04AAF).
Errors or warnings detected by the routine:
${\mathbf{IFAIL}}=1$
On entry, the sum of the availabilities does not equal the sum of the requirements.
${\mathbf{IFAIL}}=2$
During computation MAXIT has been exceeded.
${\mathbf{IFAIL}}=3$
 On entry, ${\mathbf{MAXIT}}<1$.
${\mathbf{IFAIL}}=4$
 On entry, ${\mathbf{MA}}<1$, or ${\mathbf{MB}}<1$, or ${\mathbf{M}}\ne {\mathbf{MA}}+{\mathbf{MB}}$, or ${\mathbf{MA}}>{\mathbf{LDKOST}}$.

## 7  Accuracy

All operations are performed in integer arithmetic so that there are no rounding errors.

An accurate estimate of the run time for a particular problem is difficult to achieve.

## 9  Example

A company has three warehouses and three stores. The warehouses have a surplus of $12$ units of a given commodity divided among them as follows:
 Warehouse Surplus 1 1 2 5 3 6
The stores altogether need $12$ units of commodity, with the following requirements:
 Store Requirement 1 4 2 4 3 4
Costs of shipping one unit of the commodity from warehouse $i$ to store $j$ are displayed in the following matrix:
 Store 1 2 $3$ 1 8 8 11 Warehouse 2 5 8 14 3 4 3 10
It is required to find the units of commodity to be moved from the warehouses to the stores, such that the transportation costs are minimized. The maximum number of iterations allowed is $200$.

### 9.1  Program Text

Program Text (h03abfe.f90)

### 9.2  Program Data

Program Data (h03abfe.d)

### 9.3  Program Results

Program Results (h03abfe.r)