hide long namesshow long names
hide short namesshow short names
Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
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
mamb
z = cijxij.
ij
z = i ma j mb cij xij .
subject to the constraints
mb
x i j = Ai  (Availabilities)
j
ma
 x i j = Bj  (Requirements)
ii
j mb x i j = A i   (Availabilities) i ma i x i j = B j   (Requirements)
where the xijxij can be interpreted as quantities of goods sent from source ii to destination jj, for i = 1,2,,mai=1,2,,ma and j = 1,2,,mbj=1,2,,mb, at a cost of cijcij per unit, and it is assumed that ima Ai = jmb j Bj i ma Ai= j mb j Bj  and xij0xij0.
nag_mip_transportation (h03ab) uses the ‘stepping stone’ method, modified to accept degenerate cases.

References

Hadley G (1962) Linear Programming Addison–Wesley

Parameters

Compulsory Input Parameters

1:     kost(ldkost,mb) – int64int32nag_int array
ldkost, the first dimension of the array, must satisfy the constraint ldkostmaldkostma.
The coefficients cijcij, for i = 1,2,,mai=1,2,,ma and j = 1,2,,mbj=1,2,,mb.
2:     k15(m) – int64int32nag_int array
k15(i)k15i must be set to the availabilities AiAi, for i = 1,2,,mai=1,2,,ma; and k15(ma + j)k15ma+j must be set to the requirements BjBj, for j = 1,2,,mbj=1,2,,mb.
3:     maxit – int64int32nag_int scalar
The maximum number of iterations allowed.
Constraint: maxit1maxit1.

Optional Input Parameters

1:     ma – int64int32nag_int scalar
Default: The first dimension of the array kost.
The number of sources, mama.
Constraint: ma1ma1.
2:     mb – int64int32nag_int scalar
Default: The second dimension of the array kost.
The number of destinations, mbmb.
Constraint: mb1mb1.
3:     m – int64int32nag_int scalar
Default: The dimension of the array k15.
The value of ma + mbma+mb.

Input Parameters Omitted from the MATLAB Interface

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)k6k, for k = 1,2,,ma + mb1k=1,2,,ma+mb-1, contains the source indices of the optimal solution (see k11).
4:     k8(m) – int64int32nag_int array
k8(k)k8k, for k = 1,2,,ma + mb1k=1,2,,ma+mb-1, contains the destination indices of the optimal solution (see k11).
5:     k11(m) – int64int32nag_int array
k11(k)k11k, for k = 1,2,,ma + mb1k=1,2,,ma+mb-1, contains the optimal quantities xijxij which, sent from source i = k6(k)i=k6k to destination j = k8(k)j=k8k, minimize zz.
6:     k12(m) – int64int32nag_int array
k12(k)k12k, for k = 1,2,,ma + mb1k=1,2,,ma+mb-1, contains the unit cost cijcij associated with the route from source i = k6(k)i=k6k to destination j = k8(k)j=k8k.
7:     z – double scalar
The value of the minimized total cost.
8:     ifail – int64int32nag_int scalar
ifail = 0ifail=0 unless the function detects an error (see [Error Indicators and Warnings]).

Error Indicators and Warnings

Errors or warnings detected by the function:
  ifail = 1ifail=1
On entry, the sum of the availabilities does not equal the sum of the requirements.
  ifail = 2ifail=2
During computation maxit has been exceeded.
  ifail = 3ifail=3
On entry,maxit < 1maxit<1.
  ifail = 4ifail=4
On entry,ma < 1ma<1,
ormb < 1mb<1,
ormma + mbmma+mb,
orma > ldkostma>ldkost.

Accuracy

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

Further Comments

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



PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2013