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:
Mark 22: ma has been made optional
.

Description

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

Parameters

Compulsory Input Parameters

1:     kost(ldkost,mb) – int64int32nag_int array
ldkost, the first dimension of the array, must satisfy the constraint ldkostma$\mathit{ldkost}\ge {\mathbf{ma}}$.
The coefficients cij${c}_{\mathit{i}\mathit{j}}$, for i = 1,2,,ma$\mathit{i}=1,2,\dots ,{m}_{a}$ and j = 1,2,,mb$\mathit{j}=1,2,\dots ,{m}_{b}$.
2:     k15(m) – int64int32nag_int array
k15(i)${\mathbf{k15}}\left(\mathit{i}\right)$ must be set to the availabilities Ai${A}_{\mathit{i}}$, for i = 1,2,,ma$\mathit{i}=1,2,\dots ,{m}_{a}$; and k15(ma + j)${\mathbf{k15}}\left({m}_{a}+j\right)$ must be set to the requirements Bj${B}_{\mathit{j}}$, for j = 1,2,,mb$\mathit{j}=1,2,\dots ,{m}_{b}$.
3:     maxit – int64int32nag_int scalar
The maximum number of iterations allowed.
Constraint: maxit1${\mathbf{maxit}}\ge 1$.

Optional Input Parameters

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

ldkost k7 k9

Output Parameters

1:     k15(m) – int64int32nag_int array
The contents of k15 are undefined.
2:     numit – int64int32nag_int scalar
The number of iterations performed.
3:     k6(m) – int64int32nag_int array
k6(k)${\mathbf{k6}}\left(\mathit{k}\right)$, for k = 1,2,,ma + mb1$\mathit{k}=1,2,\dots ,{m}_{a}+{m}_{b}-1$, contains the source indices of the optimal solution (see k11).
4:     k8(m) – int64int32nag_int array
k8(k)${\mathbf{k8}}\left(\mathit{k}\right)$, for k = 1,2,,ma + mb1$\mathit{k}=1,2,\dots ,{m}_{a}+{m}_{b}-1$, contains the destination indices of the optimal solution (see k11).
5:     k11(m) – int64int32nag_int array
k11(k)${\mathbf{k11}}\left(\mathit{k}\right)$, for k = 1,2,,ma + mb1$\mathit{k}=1,2,\dots ,{m}_{a}+{m}_{b}-1$, contains the optimal quantities xij${x}_{ij}$ which, sent from source i = k6(k)$i={\mathbf{k6}}\left(k\right)$ to destination j = k8(k)$j={\mathbf{k8}}\left(k\right)$, minimize z$z$.
6:     k12(m) – int64int32nag_int array
k12(k)${\mathbf{k12}}\left(\mathit{k}\right)$, for k = 1,2,,ma + mb1$\mathit{k}=1,2,\dots ,{m}_{a}+{m}_{b}-1$, contains the unit cost cij${c}_{ij}$ associated with the route from source i = k6(k)$i={\mathbf{k6}}\left(k\right)$ to destination j = k8(k)$j={\mathbf{k8}}\left(k\right)$.
7:     z – double scalar
The value of the minimized total cost.
8:     ifail – int64int32nag_int scalar
${\mathrm{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:
ifail = 1${\mathbf{ifail}}=1$
On entry, the sum of the availabilities does not equal the sum of the requirements.
ifail = 2${\mathbf{ifail}}=2$
During computation maxit has been exceeded.
ifail = 3${\mathbf{ifail}}=3$
 On entry, maxit < 1${\mathbf{maxit}}<1$.
ifail = 4${\mathbf{ifail}}=4$
 On entry, ma < 1${\mathbf{ma}}<1$, or mb < 1${\mathbf{mb}}<1$, or m ≠ ma + mb${\mathbf{m}}\ne {\mathbf{ma}}+{\mathbf{mb}}$, or ma > ldkost${\mathbf{ma}}>\mathit{ldkost}$.

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

```function nag_mip_transportation_example
kost = [int64(8),8,11;5,8,14;4,3,10];
k15 = [int64(1);5;6;4;4;4];
maxit = int64(200);
[k15Out, numit, k6, k8, k11, k12, z, ifail] = nag_mip_transportation(kost, k15, maxit)
```
```

k15Out =

3
10
14
11
5
0

numit =

2

k6 =

3
3
2
1
2
3

k8 =

2
3
3
3
1
6

k11 =

4
2
1
1
4
2

k12 =

3
10
14
11
5
0

z =

77

ifail =

0

```
```function h03ab_example
kost = [int64(8),8,11;5,8,14;4,3,10];
k15 = [int64(1);5;6;4;4;4];
maxit = int64(200);
[k15Out, numit, k6, k8, k11, k12, z, ifail] = h03ab(kost, k15, maxit)
```
```

k15Out =

3
10
14
11
5
0

numit =

2

k6 =

3
3
2
1
2
3

k8 =

2
3
3
3
1
6

k11 =

4
2
1
1
4
2

k12 =

3
10
14
11
5
0

z =

77

ifail =

0

```