void	h03abc (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)

The function may be called by the names: h03abc, nag_mip_transportation or nag_transport.

3 Description

h03abc 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{matrix} \sum_{j}^{m_{b}} x_{i j} = A_{i} & (availabilities) \\ \sum_{i}^{m_{a}} x_{i j} = B_{j} & (requirements) \end{matrix}

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}} B_{j}

and

x_{i j} \geq 0

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

4 References

Hadley G (1962) Linear Programming Addison–Wesley

5 Arguments

1: $cost [navail \times tdcost]$ – const double Input: On entry: $cost [(i - 1) \times tdcost + j - 1]$ contains the coefficients $c_{i j}$ , for $i = 1, 2, \dots, m_{a}$ and $j = 1, 2, \dots, m_{b}$ .
2: $tdcost$ – Integer Input: On entry: the stride separating matrix column elements in the array cost.

Constraint: $tdcost \geq nreq$ .
3: $avail [navail]$ – const double Input: On entry: $avail [i - 1]$ must be set to the availabilities $A_{i}$ , for $i = 1, 2, \dots, m_{a}$ ;
4: $navail$ – Integer Input: On entry: the number of sources, $m_{a}$ .

Constraint: $navail \geq 1$ .
5: $req [nreq]$ – const double Input: On entry: $req [j - 1]$ must be set to the requirements $B_{j}$ , for $j = 1, 2, \dots, m_{b}$ .
6: $nreq$ – Integer Input: On entry: the number of destinations, $m_{b}$ .

Constraint: $nreq \geq 1$ .
7: $maxit$ – Integer Input: On entry: the maximum number of iterations allowed.

Constraint: $maxit \geq 1$ .
8: $numit$ – Integer * Output: On exit: the number of iterations performed.
9: $optq [navail + nreq]$ – double Output: On exit: $optq [k - 1]$ , for $k = 1, 2, \dots, m_{a} + m_{b} - 1$ , contains the optimal quantities $x_{i j}$ which, when sent from source $i = source [k - 1]$ to destination $j = dest [k - 1]$ , minimize $z$ .
10: $source [navail + nreq]$ – Integer Output: On exit: $source [k - 1]$ , for $k = 1, 2, \dots, m_{a} + m_{b} - 1$ , contains the source indices of the optimal solution (see optq above).
11: $dest [navail + nreq]$ – Integer Output: On exit: $dest [k - 1]$ , for $k = 1, 2, \dots, 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]$ – double Output: On exit: $unitcost [k - 1]$ , for $k = 1, 2, \dots, m_{a} + m_{b} - 1$ , contains the unit cost $c_{i j}$ 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 7 in the Introduction to the NAG Library CL Interface).

6 Error Indicators and Warnings

NE_2_INT_ARG_LT: On entry, $tdcost = ⟨ value ⟩$ while $nreq = ⟨ value ⟩$ . These arguments must satisfy $tdcost \geq nreq$ .
NE_ALLOC_FAIL: Dynamic memory allocation failed.
NE_INT_ARG_LT: On entry, $maxit = ⟨ value ⟩$ .
Constraint: $maxit \geq 1$ .

On entry, $navail = ⟨ value ⟩$ .
Constraint: $navail \geq 1$ .

On entry, $nreq = ⟨ value ⟩$ .
Constraint: $nreq \geq 1$ .
NE_REQ_AVAIL: The relative difference between the sum of availabilities and the sum of requirements is greater than machine precision. relative difference $= ⟨ value ⟩$ , $machine precision = ⟨ value ⟩$ .
NE_TOO_MANY: Too many iterations ( $⟨ value ⟩$ )

7 Accuracy

The computations are stable.

8 Parallelism and Performance

Background information to multithreading can be found in the Multithreading documentation.

h03abc is not threaded in any implementation.

9 Further Comments

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

10 Example

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:

		Store
		$1$	$2$	$3$
Warehouse	$1$	$8$	$8$	$11$
	$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.