naginterfaces.library.mip.transportation

naginterfaces.library.mip.transportation(kost, k15, maxit)

transportation solves the classical Transportation (‘Hitchcock’) problem.

For full information please refer to the NAG Library document for h03ab

https://support.nag.com/numeric/nl/nagdoc_30/flhtml/h/h03abf.html

Parameters

kostint, array-like, shape $(\text{ma},\text{mb})$

The coefficients $c_{\text{i}\text{j}}$, for $\text{j}=1,2,\dots ,m_b$, for $\text{i}=1,2,\dots ,m_a$.

k15int, array-like, shape $\left(m\right)$

$k15\left[\text{i}\right]$ must be set to the availabilities $A_{\text{i}}$, for $\text{i}=1,2,\dots ,m_a$; and $k15[m_a+j]$ must be set to the requirements $B_{\text{j}}$, for $\text{j}=1,2,\dots ,m_b$.

maxitint

The maximum number of iterations allowed.

Returns

k15int, ndarray, shape $\left(m\right)$

The contents of $k15$ are undefined.

numitint

The number of iterations performed.

k6int, ndarray, shape $\left(m\right)$

$k6[\text{k}-1]$, for $\text{k}=1,2,\dots ,m_a+m_b-1$, contains the source indices of the optimal solution (see $k11$).

k8int, ndarray, shape $\left(m\right)$

$k8[\text{k}-1]$, for $\text{k}=1,2,\dots ,m_a+m_b-1$, contains the destination indices of the optimal solution (see $k11$).

k11int, ndarray, shape $\left(m\right)$

$k11[\text{k}-1]$, for $\text{k}=1,2,\dots ,m_a+m_b-1$, contains the optimal quantities $x_{ij}$ which, sent from source $i=k6[k-1]$ to destination $j=k8[k-1]$, minimize $z$.

k12int, ndarray, shape $\left(m\right)$

$k12[\text{k}-1]$, for $\text{k}=1,2,\dots ,m_a+m_b-1$, contains the unit cost $c_{ij}$ associated with the route from source $i=k6[k-1]$ to destination $j=k8[k-1]$.

zfloat

The value of the minimized total cost.

Raises

NagValueError

(errno $1$)

On entry, the sum of the availabilities does not equal the sum of the requirements.

(errno $2$)

During computations $maxit$ has been exceeded.

(errno $3$)

On entry, $maxit=⟨value⟩$.

Constraint: $maxit>0$.

(errno $4$)

On entry, $m=⟨value⟩$, $\text{ma}=⟨value⟩$ and $\text{mb}=⟨value⟩$.

Constraint: $m=\text{ma}+\text{mb}$.

(errno $4$)

On entry, $\text{ma}=⟨value⟩$ and $\text{ldkost}=⟨value⟩$.

Constraint: $\text{ma}\le \text{ldkost}$.

(errno $4$)

On entry, $\text{mb}=⟨value⟩$.

Constraint: $\text{mb}>0$.

(errno $4$)

On entry, $\text{ma}=⟨value⟩$.

Constraint: $\text{ma}>0$.

Notes

In the NAG Library the traditional C interface for this routine uses a different algorithmic base. Please contact NAG if you have any questions about compatibility.

transportation solves the Transportation problem by minimizing

$$z=\sum _i^{m_a}\sum _j^{m_b}{c}_{ij}{x}_{ij}\text{.}$$

subject to the constraints

$$\begin{array}{c}\begin{array}{c}{\sum }_j^{m_b}{x}_{ij}=A_i\text{(Availabilities)}\\ {\sum }_i^{m_a}{\sum }_i{x}_{ij}=B_j\text{(Requirements)}\end{array}\end{array}$$

where the $x_{\text{i}\text{j}}$ can be interpreted as quantities of goods sent from source $\text{i}$ to destination $\text{j}$, for $\text{j}=1,2,\dots ,m_b$, for $\text{i}=1,2,\dots ,m_a$, at a cost of $c_{\text{i}\text{j}}$ per unit, and it is assumed that ${\sum }_i^{m_a}{A}_i={\sum }_j^{m_b}{\sum }_j{B}_j$ and $x_{ij}\ge 0$.

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

References

Hadley, G, 1962, Linear Programming, Addison–Wesley