transport
Solves a transportation problem.
Synopsis
#include <imsl.h>
float *imsl_f_transport (int nw, int ns, float wcap[], float sreq[], float cost[], …, 0)
The type double function is imsl_d_transport.
Required Arguments
int nw (Input)
Number of sources.
Number of sources.
int ns (Input)
Number of sinks.
Number of sinks.
float wcap[] (Input)
Array of size nw containing the source (warehouse) capacities.
Array of size nw containing the source (warehouse) capacities.
float sreq[] (Input)
Array of size ns containing the sink (store) requirements.
Array of size ns containing the sink (store) requirements.
float cost[] (Input)
Array of size nw × ns containing the cost matrix. costij is the per unit cost to ship from source i to sink j.
Array of size nw × ns containing the cost matrix. costij is the per unit cost to ship from source i to sink j.
Return Value
A pointer to the solution matrix x of size nw × ns containing the optimal routing. xij units should be shipped from source i to sink j. To release this space, use imsl_free. If no solution can be computed, then NULL is returned.
Synopsis with Optional Arguments
#include <imsl.h>
float *imsl_f_transport (int nw, int ns, float wcap[], float sreq[], float cost[],
IMSL_MAX_ITN, int max_itn,
IMSL_DUAL, float **y,
IMSL_DUAL_USER, float y[],
IMSL_TOTAL_COST, float *cmin,
IMSL_RETURN_USER, float x[],
0)
Optional Arguments
IMSL_MAX_ITN, int max_itn (Input)
Upper bound on the number of simplex steps.
Default: max_itn = 0 (no limit)
Upper bound on the number of simplex steps.
Default: max_itn = 0 (no limit)
IMSL_DUAL, float **y (Output)
The address of a pointer y to an array of size nw + ns containing the dual solution. On return, the necessary space is allocated by imsl_f_transport. Typically, float *y is declared, and &y is used as an argument.
The address of a pointer y to an array of size nw + ns containing the dual solution. On return, the necessary space is allocated by imsl_f_transport. Typically, float *y is declared, and &y is used as an argument.
IMSL_DUAL_USER, float y[] (Output)
A user-allocated array of size nw + ns. On return, y contains the dual solution.
A user-allocated array of size nw + ns. On return, y contains the dual solution.
IMSL_TOTAL_COST, float *cmin (Output)
Total cost of the optimal routing.
Total cost of the optimal routing.
IMSL_RETURN_USER, float x[] (Output)
Array of size nw × ns containing the optimal routing.
Array of size nw × ns containing the optimal routing.
Description
The function imsl_f_transport solves the transportation problem
Minimize
subject to the constraints
where c = cost, w = wcap and s = sreq.
The revised simplex method is used to solve a very sparse linear programming problem with nw + ns constraints and nw * ns variables. If nw = ns = k, the work per iteration is O(k 2), compared with O(k 3) when a dense simplex algorithm is used. For more details, see Sewell (2005), Section 4.6.
dual[i] gives the decrease in total cost per unit increase in wcap[i], for small increases, and ‑dual[nw + j] gives the increase in total cost per unit increase in –sreq[j].
Example
In this example, there are two warehouses with capacities 40 and 20, and three stores, which need 25, 10 and 22 units, respectively.
#include <stdio.h>
#include <imsl.h>
#define NW 2
#define NS 3
int main() {
int i, j;
float cmin, *x;
float wcap[NW] = { 40, 20 };
float sreq[NS] = { 25, 10, 22 };
float cost[NW][NS] = {
{ 550, 300, 400 },
{ 350, 300, 100 }
};
x = imsl_f_transport(NW, NS, wcap, sreq, &cost[0][0],
IMSL_TOTAL_COST, &cmin,
0);
printf("Minimum cost is %.2f\n\n", cmin);
for (i = 0; i < NW; i++) {
for (j = 0; j < NS; j++) {
printf("Ship %5.2f units from warehouse %d to store %d\n",
x[i * NS + j], i, j);
}
}
imsl_free(x);
}
Output
Minimum cost is 19550.00
Ship 25.00 units from warehouse 0 to store 0
Ship 10.00 units from warehouse 0 to store 1
Ship 2.00 units from warehouse 0 to store 2
Ship 0.00 units from warehouse 1 to store 0
Ship 0.00 units from warehouse 1 to store 1
Ship 20.00 units from warehouse 1 to store 2
Warning Errors
IMSL_INSUFFICIENT_CAPACITY | Insufficient source capacity. Sink needs will not all be met. |
Fatal Errors
IMSL_MAX_ITN_EXCEEDED | Maximum number of iterations exceeded. Try increasing max_itn or set max_itn = 0. |
