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

C Header Interface

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

3 Description

h03abf solves the Transportation problem by minimizing

z = \sum_{i}^{m_{a}} \sum_{j}^{m_{b}} c_{i j} x_{i j} .

subject to the constraints

\begin{array}{l} \sum_{j}^{m_{b}} x_{i j} = A_{i} (Availabilities) \\ \sum_{i}^{m_{a}} \sum_{i} x_{i j} = B_{j} (Requirements) \end{array}

where the

x_{i j}

can be interpreted as quantities of goods sent from source

i

to destination

j

, for

i = 1, 2, \dots, m_{a}

and

j = 1, 2, \dots, m_{b}

, at a cost of

c_{i j}

per unit, and it is assumed that

\sum_{i}^{m_{a}} A_{i} = \sum_{j}^{m_{b}} \sum_{j} B_{j}

and

x_{i j} \geq 0

h03abf uses the ‘stepping stone’ method, modified to accept degenerate cases.

4 References

Hadley G (1962) Linear Programming Addison–Wesley

5 Arguments

1: $kost (ldkost, mb)$ – Integer array Input: On entry: the coefficients $c_{i j}$ , for $i = 1, 2, \dots, m_{a}$ and $j = 1, 2, \dots, m_{b}$ .
2: $ldkost$ – Integer Input: On entry: the first dimension of the array kost as declared in the (sub)program from which h03abf is called.

Constraint: $ldkost \geq ma$ .
3: $ma$ – Integer Input: On entry: the number of sources, $m_{a}$ .

Constraint: $ma \geq 1$ .
4: $mb$ – Integer Input: On entry: the number of destinations, $m_{b}$ .

Constraint: $mb \geq 1$ .
5: $m$ – Integer Input: On entry: the value of $m_{a} + m_{b}$ .
6: $k15 (m)$ – Integer array Input/Output: On entry: $k15 (i)$ must be set to the availabilities $A_{i}$ , for $i = 1, 2, \dots, m_{a}$ ; and $k15 (m_{a} + j)$ must be set to the requirements $B_{j}$ , for $j = 1, 2, \dots, m_{b}$ .

On exit: the contents of k15 are undefined.
7: $maxit$ – Integer Input: On entry: the maximum number of iterations allowed.

Constraint: $maxit \geq 1$ .
8: $k7 (m)$ – Integer array Workspace
9: $k9 (m)$ – Integer array Workspace
10: $numit$ – Integer Output: On exit: the number of iterations performed.
11: $k6 (m)$ – Integer array Output: On exit: $k6 (k)$ , for $k = 1, 2, \dots, m_{a} + m_{b} - 1$ , contains the source indices of the optimal solution (see k11).
12: $k8 (m)$ – Integer array Output: On exit: $k8 (k)$ , for $k = 1, 2, \dots, m_{a} + m_{b} - 1$ , contains the destination indices of the optimal solution (see k11).
13: $k11 (m)$ – Integer array Output: On exit: $k11 (k)$ , for $k = 1, 2, \dots, m_{a} + m_{b} - 1$ , contains the optimal quantities $x_{i j}$ which, sent from source $i = k6 (k)$ to destination $j = k8 (k)$ , minimize $z$ .
14: $k12 (m)$ – Integer array Output: On exit: $k12 (k)$ , for $k = 1, 2, \dots, m_{a} + m_{b} - 1$ , contains the unit cost $c_{i j}$ associated with the route from source $i = k6 (k)$ to destination $j = k8 (k)$ .
15: $z$ – Real (Kind=nag_wp) Output: On exit: the value of the minimized total cost.
16: $ifail$ – Integer Input/Output: On entry: ifail must be set to $0$ , $- 1 or 1$ . If you are unfamiliar with this argument you should refer to Section 4 in the Introduction to the NAG Library FL Interface for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value $- 1 or 1$ is recommended. If the output of error messages is undesirable, then the value $1$ is recommended. Otherwise, if you are not familiar with this argument, the recommended value is $0$ . When the value $- 1 or 1$ is used it is essential to test the value of ifail on exit.

On exit: $ifail = 0$ unless the routine detects an error or a warning has been flagged (see Section 6).

6 Error Indicators and Warnings

If on entry

ifail = 0

- 1

, explanatory error messages are output on the current error message unit (as defined by x04aaf).

Errors or warnings detected by the routine:

$ifail = 1$: On entry, the sum of the availabilities does not equal the sum of the requirements.

$ifail = 2$: During computations maxit has been exceeded.

$ifail = 3$: On entry, $maxit = 〈value〉$ .
Constraint: $maxit > 0$ .

$ifail = 4$: On entry, $m = 〈value〉$ , $ma = 〈value〉$ and $mb = 〈value〉$ .
Constraint: $m = ma + mb$ .

On entry, $ma = 〈value〉$ .
Constraint: $ma > 0$ .

On entry, $ma = 〈value〉$ and $ldkost = 〈value〉$ .
Constraint: $ma \leq ldkost$ .

On entry, $mb = 〈value〉$ .
Constraint: $mb > 0$ .

$ifail = - 99$: An unexpected error has been triggered by this routine. Please contact NAG.
See Section 7 in the Introduction to the NAG Library FL Interface for further information.

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

$ifail = - 999$: Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.

7 Accuracy

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

8 Parallelism and Performance

h03abf is not threaded in any implementation.

9 Further Comments

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

10 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

Interfaces: FL CL AD

NAG FL Interface Introduction

H (Mip) Chapter Contents

H (Mip) Chapter Introduction

h03ab: FL CL AD

NAG FL Interfaceh03abf (transportation)

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

NAG FL Interface
h03abf (transportation)