# NAG FL Interfaceh03abf (transportation)

## ▸▿ Contents

Settings help

FL Name Style:

FL Specification Language:

## 1Purpose

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

## 2Specification

Fortran Interface
 Subroutine h03abf ( kost, ma, mb, m, k15, k7, k9, k6, k8, k11, k12, z,
 Integer, Intent (In) :: kost(ldkost,mb), ldkost, ma, mb, m, maxit Integer, Intent (Inout) :: k15(m), ifail Integer, Intent (Out) :: k7(m), k9(m), numit, k6(m), k8(m), k11(m), k12(m) Real (Kind=nag_wp), Intent (Out) :: z
#include <nag.h>
 void h03abf_ (const Integer kost[], const Integer *ldkost, const Integer *ma, const Integer *mb, const Integer *m, Integer k15[], const Integer *maxit, Integer k7[], Integer k9[], Integer *numit, Integer k6[], Integer k8[], Integer k11[], Integer k12[], double *z, Integer *ifail)
The routine may be called by the names h03abf or nagf_mip_transportation.

## 3Description

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.

## 5Arguments

1: $\mathbf{kost}\left({\mathbf{ldkost}},{\mathbf{mb}}\right)$Integer array Input
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: $\mathbf{ldkost}$Integer Input
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: $\mathbf{ma}$Integer Input
On entry: the number of sources, ${m}_{a}$.
Constraint: ${\mathbf{ma}}\ge 1$.
4: $\mathbf{mb}$Integer Input
On entry: the number of destinations, ${m}_{b}$.
Constraint: ${\mathbf{mb}}\ge 1$.
5: $\mathbf{m}$Integer Input
On entry: the value of ${m}_{a}+{m}_{b}$.
6: $\mathbf{k15}\left({\mathbf{m}}\right)$Integer array Input/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: $\mathbf{maxit}$Integer Input
On entry: the maximum number of iterations allowed.
Constraint: ${\mathbf{maxit}}\ge 1$.
8: $\mathbf{k7}\left({\mathbf{m}}\right)$Integer array Workspace
9: $\mathbf{k9}\left({\mathbf{m}}\right)$Integer array Workspace
10: $\mathbf{numit}$Integer Output
On exit: the number of iterations performed.
11: $\mathbf{k6}\left({\mathbf{m}}\right)$Integer array Output
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: $\mathbf{k8}\left({\mathbf{m}}\right)$Integer array Output
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: $\mathbf{k11}\left({\mathbf{m}}\right)$Integer array Output
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: $\mathbf{k12}\left({\mathbf{m}}\right)$Integer array Output
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: $\mathbf{z}$Real (Kind=nag_wp) Output
On exit: the value of the minimized total cost.
16: $\mathbf{ifail}$Integer Input/Output
On entry: ifail must be set to $0$, $-1$ or $1$ to set behaviour on detection of an error; these values have no effect when no error is detected.
A value of $0$ causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of $-1$ means that an error message is printed while a value of $1$ means that it is not.
If halting is not appropriate, the value $-1$ or $1$ is recommended. If message printing is undesirable, then the value $1$ is recommended. Otherwise, the value $0$ is recommended. When the value $-\mathbf{1}$ 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).

## 6Error Indicators and Warnings

If on entry ${\mathbf{ifail}}=0$ or $-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 computations maxit has been exceeded.
${\mathbf{ifail}}=3$
On entry, ${\mathbf{maxit}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{maxit}}>0$.
${\mathbf{ifail}}=4$
On entry, ${\mathbf{m}}=⟨\mathit{\text{value}}⟩$, ${\mathbf{ma}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{mb}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{m}}={\mathbf{ma}}+{\mathbf{mb}}$.
On entry, ${\mathbf{ma}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{ma}}>0$.
On entry, ${\mathbf{ma}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{ldkost}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{ma}}\le {\mathbf{ldkost}}$.
On entry, ${\mathbf{mb}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{mb}}>0$.
${\mathbf{ifail}}=-99$
See Section 7 in the Introduction to the NAG Library FL Interface for further information.
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library FL Interface for further information.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.

## 7Accuracy

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

## 8Parallelism and Performance

h03abf is not threaded in any implementation.

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

## 10Example

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 Warehouse $1$ $2$ $3$ $1$ $8$ $8$ $11$ $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$.

### 10.1Program Text

Program Text (h03abfe.f90)

### 10.2Program Data

Program Data (h03abfe.d)

### 10.3Program Results

Program Results (h03abfe.r)