NAG C Library Function Document

nag_transport (h03abc)


nag_transport (h03abc) solves the classical transportation (‘Hitchcock’) problem.


#include <nag.h>
#include <nagh.h>
void  nag_transport (const double cost[], Integer tdcost, const double avail[], Integer navail, const double req[], Integer nreq, Integer maxit, Integer *numit, double optq[], Integer source[], Integer dest[], double *optcost, double unitcost[], NagError *fail)


nag_transport (h03abc) solves the transportation problem by minimizing
z = i m a j m b c ij x ij .  
subject to the constraints
j m b x ij = A i availabilities i m a x ij = B j requirements  
where the x ij  can be interpreted as quantities of goods sent from source i  to destination j , for i=1,2,, m a  and j=1,2,, m b , at a cost of c ij  per unit, and it is assumed that i m a A i = j m b B j  and x ij 0 .
nag_transport (h03abc) uses the ‘stepping stone’ method, modified to accept degenerate cases.


Hadley G (1962) Linear Programming Addison–Wesley


1:     cost[navail×tdcost] const doubleInput
On entry: cost[i-1×tdcost+j-1]  contains the coefficients c ij , for i=1,2,, m a  and j=1,2,, m b .
2:     tdcost IntegerInput
On entry: the stride separating matrix column elements in the array cost.
Constraint: tdcostnreq .
3:     avail[navail] const doubleInput
On entry: avail[i-1]  must be set to the availabilities A i , for i=1,2,, m a ;
On entry: the number of sources, m a .
Constraint: navail1 .
5:     req[nreq] const doubleInput
On entry: req[j-1]  must be set to the requirements B j , for j=1,2,, m b .
6:     nreq IntegerInput
On entry: the number of destinations, m b .
Constraint: nreq1 .
7:     maxit IntegerInput
On entry: the maximum number of iterations allowed.
Constraint: maxit1 .
8:     numit Integer *Output
On exit: the number of iterations performed.
9:     optq[navail+nreq] doubleOutput
On exit: optq[k-1] , for k=1,2,, m a + m b - 1, contains the optimal quantities x ij  which, when sent from source i = source[k-1]  to destination j = dest[k-1] , minimize z .
10:   source[navail+nreq] IntegerOutput
On exit: source[k-1] , for k=1,2,, m a + m b - 1, contains the source indices of the optimal solution (see optq above).
11:   dest[navail+nreq] IntegerOutput
On exit: dest[k-1] , for k=1,2,, m a + m b - 1, contains the destination indices of the optimal solution (see optq above).
12:   optcost double *Output
On exit: the value of the minimized total cost.
13:   unitcost[navail+nreq] doubleOutput
On exit: unitcost[k-1] , for k=1,2,, m a + m b - 1, contains the unit cost c ij  associated with the route from source i = source[k-1]  to destination j = dest[k-1] .
14:   fail NagError *Input/Output
The NAG error argument (see Section 3.7 in How to Use the NAG Library and its Documentation).

Error Indicators and Warnings

On entry, tdcost=value  while nreq=value . These arguments must satisfy tdcostnreq .
Dynamic memory allocation failed.
On entry, maxit=value.
Constraint: maxit1.
On entry, navail=value.
Constraint: navail1.
On entry, nreq=value.
Constraint: nreq1.
The relative difference between the sum of availabilities and the sum of requirements is greater than machine precision. relative difference =value , machine precision=value .
Too many iterations (value)


The computations are stable.

Parallelism and Performance

nag_transport (h03abc) is not threaded in any implementation.

Further Comments

An a priori estimate of the run time for a particular problem is difficult to obtain.


A company has three warehouses and three stores. The warehouses have a surplus of 12 units of a given commodity divided between 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:
    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.

Program Text

Program Text (h03abce.c)

Program Data


Program Results

Program Results (h03abce.r)