Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

Chapter Contents
Chapter Introduction
NAG Toolbox

# NAG Toolbox: nag_mip_transportation (h03ab)

## Purpose

nag_mip_transportation (h03ab) solves the classical Transportation (‘Hitchcock’) problem.

## Syntax

[k15, numit, k6, k8, k11, k12, z, ifail] = h03ab(kost, k15, maxit, 'ma', ma, 'mb', mb, 'm', m)
[k15, numit, k6, k8, k11, k12, z, ifail] = nag_mip_transportation(kost, k15, maxit, 'ma', ma, 'mb', mb, 'm', m)
Note: the interface to this routine has changed since earlier releases of the toolbox:
 At Mark 22: ma was made optional

## Description

nag_mip_transportation (h03ab) 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$.
nag_mip_transportation (h03ab) uses the ‘stepping stone’ method, modified to accept degenerate cases.

## Parameters

### Compulsory Input Parameters

1:     $\mathrm{kost}\left(\mathit{ldkost},{\mathbf{mb}}\right)$int64int32nag_int array
ldkost, the first dimension of the array, must satisfy the constraint $\mathit{ldkost}\ge {\mathbf{ma}}$.
The coefficients ${c}_{\mathit{i}\mathit{j}}$, for $\mathit{i}=1,2,\dots ,{m}_{a}$ and $\mathit{j}=1,2,\dots ,{m}_{b}$.
2:     $\mathrm{k15}\left({\mathbf{m}}\right)$int64int32nag_int array
${\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}$.
3:     $\mathrm{maxit}$int64int32nag_int scalar
The maximum number of iterations allowed.
Constraint: ${\mathbf{maxit}}\ge 1$.

### Optional Input Parameters

1:     $\mathrm{ma}$int64int32nag_int scalar
Default: the first dimension of the array kost.
The number of sources, ${m}_{a}$.
Constraint: ${\mathbf{ma}}\ge 1$.
2:     $\mathrm{mb}$int64int32nag_int scalar
Default: the second dimension of the array kost.
The number of destinations, ${m}_{b}$.
Constraint: ${\mathbf{mb}}\ge 1$.
3:     $\mathrm{m}$int64int32nag_int scalar
Default: the dimension of the array k15.
The value of ${m}_{a}+{m}_{b}$.

### Output Parameters

1:     $\mathrm{k15}\left({\mathbf{m}}\right)$int64int32nag_int array
The contents of k15 are undefined.
2:     $\mathrm{numit}$int64int32nag_int scalar
The number of iterations performed.
3:     $\mathrm{k6}\left({\mathbf{m}}\right)$int64int32nag_int array
${\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).
4:     $\mathrm{k8}\left({\mathbf{m}}\right)$int64int32nag_int array
${\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).
5:     $\mathrm{k11}\left({\mathbf{m}}\right)$int64int32nag_int array
${\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$.
6:     $\mathrm{k12}\left({\mathbf{m}}\right)$int64int32nag_int array
${\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)$.
7:     $\mathrm{z}$ – double scalar
The value of the minimized total cost.
8:     $\mathrm{ifail}$int64int32nag_int scalar
${\mathbf{ifail}}={\mathbf{0}}$ unless the function detects an error (see Error Indicators and Warnings).

## Error Indicators and Warnings

Errors or warnings detected by the function:
${\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}}>\mathit{ldkost}$.
${\mathbf{ifail}}=-99$
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.

## 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.

## 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$.
```function h03ab_example

fprintf('h03ab example results\n\n');

m = 3 + 3;
kost = [int64(8), 8, 11;
5,  8, 14;
4,  3, 10];
k15  = [int64(1); 5; 6;
4;  4; 4];
maxit = int64(200);

[k15, numit, k6, k8, k11, k12, z, ifail] = ...
h03ab( ...
kost, k15, maxit);

fprintf('Total cost = %5.1f\n\n', z);
fprintf('Goods   from   to\n');
for j = 1:m-1
fprintf('%4d%7d%6d\n',k11(j),k6(j),k8(j));
end

```
```h03ab example results

Total cost =  77.0

Goods   from   to
4      3     2
2      3     3
1      2     3
1      1     3
4      2     1
```