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)

 Contents

    1  Purpose
    2  Syntax
    7  Accuracy
    9  Example

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 xij can be interpreted as quantities of goods sent from source i to destination j, for i=1,2,,ma and j=1,2,,mb, at a cost of cij per unit, and it is assumed that i ma Ai= j mb j Bj  and xij0.
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:     kostldkostmb int64int32nag_int array
ldkost, the first dimension of the array, must satisfy the constraint ldkostma.
The coefficients cij, for i=1,2,,ma and j=1,2,,mb.
2:     k15m int64int32nag_int array
k15i must be set to the availabilities Ai, for i=1,2,,ma; and k15ma+j must be set to the requirements Bj, for j=1,2,,mb.
3:     maxit int64int32nag_int scalar
The maximum number of iterations allowed.
Constraint: maxit1.

Optional Input Parameters

1:     ma int64int32nag_int scalar
Default: the first dimension of the array kost.
The number of sources, ma.
Constraint: ma1.
2:     mb int64int32nag_int scalar
Default: the second dimension of the array kost.
The number of destinations, mb.
Constraint: mb1.
3:     m int64int32nag_int scalar
Default: the dimension of the array k15.
The value of ma+mb.

Output Parameters

1:     k15m int64int32nag_int array
The contents of k15 are undefined.
2:     numit int64int32nag_int scalar
The number of iterations performed.
3:     k6m int64int32nag_int array
k6k, for k=1,2,,ma+mb-1, contains the source indices of the optimal solution (see k11).
4:     k8m int64int32nag_int array
k8k, for k=1,2,,ma+mb-1, contains the destination indices of the optimal solution (see k11).
5:     k11m int64int32nag_int array
k11k, for k=1,2,,ma+mb-1, contains the optimal quantities xij which, sent from source i=k6k to destination j=k8k, minimize z.
6:     k12m int64int32nag_int array
k12k, for k=1,2,,ma+mb-1, contains the unit cost cij associated with the route from source i=k6k to destination j=k8k.
7:     z – double scalar
The value of the minimized total cost.
8:     ifail int64int32nag_int scalar
ifail=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
On entry, the sum of the availabilities does not equal the sum of the requirements.
   ifail=2
During computation maxit has been exceeded.
   ifail=3
On entry,maxit<1.
   ifail=4
On entry,ma<1,
ormb<1,
ormma+mb,
orma>ldkost.
   ifail=-99
An unexpected error has been triggered by this routine. Please contact NAG.
   ifail=-399
Your licence key may have expired or may not have been installed correctly.
   ifail=-999
Dynamic memory allocation failed.

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

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

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–2015