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.
int ns (Input)
Number of sinks.
float wcap[] (Input)
Array of size nw containing the source (warehouse) capacities.
float sreq[] (Input)
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.
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_METHOD, Imsl_transport_solve_method solve_method,
IMSL_MAX_ITN, int max_itn,
IMSL_INIT_BASIS_METHOD, Imsl_init_basis_simplex_method init_method,
IMSL_DUAL, float **y,
IMSL_DUAL_USER, float y[],
IMSL_TOTAL_COST, float *cmin,
IMSL_RETURN_USER, float x[],
0)
Optional Arguments
IMSL_METHOD, Imsl_transport_solve_method solve_method (Input)
The algorithmic method used to solve the transportation problem. Select the method by setting solve_method to one of the following:
|
solve_method |
Algorithm |
|
IMSL_SIMPLEX_METHOD |
Revised simplex method |
|
IMSL_INTERIOR_POINT_METHOD |
Interior-point method |
|
IMSL_GRAPH_SIMPLEX_METHOD |
Graph-based simplex method |
Default: solve_method = IMSL_SIMPLEX_METHOD.
IMSL_MAX_ITN, int max_itn (Input)
Upper bound on the number of simplex or interior-point steps.
The default value depends on optional argument IMSL_METHOD:
|
solve_method |
max_int |
|
IMSL_SIMPLEX_METHOD |
0 (no limit) |
|
IMSL_INTERIOR_POINT_METHOD |
200 |
|
IMSL_GRAPH_SIMPLEX_METHOD |
0 (no limit) |
IMSL_INIT_BASIS_METHOD, Imsl_init_basis_simplex_method init_method (Input)
The method used to find an initial basic feasible solution for the graph-based simplex method.
|
init_method |
Algorithm |
|
IMSL_NW_CORNER_METHOD |
Northwest Corner Method |
|
IMSL_VOGEL_METHOD |
Vogel's Approximation method (VAM) |
Default: init_method = IMSL_VOGEL_METHOD.
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.
IMSL_DUAL_USER, float y[] (Output)
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.
IMSL_RETURN_USER, float x[] (Output)
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.
Alternatively, a graph-based variant of the simplex method can be used to solve the transportation problem. Internally, the transportation problem is first balanced to guarantee the existence of an optimal solution. Then either Vogel’s approximation method (VAM) or the Northwest Corner rule is used to compute an initial basic feasible solution for the problem. On larger problems VAM is often slower than the Northwest Corner method, but the computed solution is usually much closer to the optimum, so that in the following part of the algorithm less iterations are needed. The simplex algorithm now works on the bipartite graph defined by the transportation problem: The disjoint node sets are represented by the sources and sinks, respectively, and the edges are the links between sources and sinks. The basic variables of the initial feasible solution form a tree with nw + ns - 1edges, a subgraph of the transport graph. The edges of the tree describe the quantities transported from the incident source to the incident sink. The algorithm then iteratively updates this tree by replacing in each step one edge by an edge currently not in the basis, thereby updating the transport quantities along edges in the tree and at the same time reducing the overall transportation costs. This process continues until the optimum is reached. The final tree contains the transport quantities along the optimum basic variables. For more details, see Jarre and Stoer (2019), section 5.1. For large transport problems, the graph-based variant of the simplex method combined with VAM is often significantly faster than the revised simplex method since the update of a tree with k = nw + ns – 1 edges has complexity O(k) while the update of the inverse of a basis matrix in the revised simplex method has complexity O(k2).
As a third option, the interior-point method implemented in function sparse_lin_prog can be used to solve the transportation problem. Since the interior-point method works with sparse data structures and is of polynomial complexity, it is in general much faster than the revised simplex method when applied to large transportation problems. On the other hand, in contrast to the simplex method, the solution will not be guaranteed to be integer if the capacities and demands are all integer, see Example 2. Since sparse_lin_prog is available in double precision only, all internal interior-point related computations are done in double precision, even if function transport is called in single precision.
Denoting the dual solution of the transportation problem as dual, 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].
Examples
Example 1
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
Example 2
In this example, a random transportation problem is solved using variants of the simplex method and the interior-point method.
The problem is slightly larger, of integer type and satisfies the saturation condition
As the results indicate, the solution of the transportation problem is not unique. In accordance with the theory of the two solution methods, the optimal routings computed by the revised and graph-based simplex method contain integer values only while the interior-point solution can contain non-integer values as well - even if all the source capacities and destination requirements are integer-valued.
#include <stdio.h>
#include <stdlib.h>
#include <imsl.h>
int main() {
int i, j, nw, ns;
float *wcap = NULL, *sreq = NULL, *cost = NULL, *x = NULL, *y = NULL;
float cmin, dual_optval;
nw = 100;
ns = 100;
wcap = (float *)malloc(nw * sizeof(float));
sreq = (float *)malloc(ns * sizeof(float));
cost = (float *)malloc(nw * sizeof(float) * ns);
x = (float *)malloc(nw * sizeof(float) * ns);
y = (float *)malloc((nw + ns) * sizeof(float));
imsl_random_seed_set(123457);
imsl_f_random_uniform(nw, IMSL_RETURN_USER, wcap, 0);
for (i = 0; i < nw; i++) {
/*
* Generate uniform discrete random numbers in
* the interval [1, 20].
*/
wcap[i] = (int)(20.0 * wcap[i] + 1.0);
}
/*
* Copy wcap into sreq. The saturation condition is
* satisfied then.
*/
for (i = 0; i < ns; i++) {
sreq[i] = wcap[i];
}
/*
* Create random cost vector with integer entries between 1 and 10.
*/
imsl_f_random_uniform(nw * ns, IMSL_RETURN_USER, cost, 0);
for (i = 0; i < nw; i++) {
for (j = 0; j < ns; j++) {
cost[i * ns + j] = (int)(10.0 * cost[i * ns + j] + 1.0);
}
}
/*
* Solve the transportation problem with the revised simplex method.
*/
printf("\n**************************\n");
printf("* Revised simplex method *\n");
printf("**************************\n");
imsl_f_transport(nw, ns, wcap, sreq, cost,
IMSL_TOTAL_COST, &cmin,
IMSL_DUAL_USER, y,
IMSL_RETURN_USER, x,
0);
printf("Minimum cost using revised simplex method is %.2f\n", cmin);
/*
* Compute dual optimum value, trans(b) * y.
*/
dual_optval = 0.0;
for (i = 0; i < nw; i++) {
dual_optval += y[i] * wcap[i];
}
for (i = 0; i < ns; i++) {
dual_optval += y[nw + i] * sreq[i];
}
printf("Dual optimum value is %.2f\n\n", dual_optval);
/*
* Print all shipments from source 0 to the sinks.
*/
for (i = 0; i < ns; i++) {
if (x[i] != 0.0) {
printf("Ship %5.2f units from source 0 to sink %d\n",
x[i], i);
}
}
/*
* Solve the transportation problem with the graph-based variant of
* the simplex method.
*/
printf("\n\n******************************\n");
printf("* Graph-based simplex method *\n");
printf("******************************\n");
imsl_f_transport(nw, ns, wcap, sreq, cost,
IMSL_TOTAL_COST, &cmin,
IMSL_DUAL_USER, y,
IMSL_METHOD, IMSL_GRAPH_SIMPLEX_METHOD,
IMSL_RETURN_USER, x,
0);
printf("Minimum cost using graph-based simplex method is %.2f\n",
cmin);
/*
* Compute dual optimum value, trans(b) * y.
*/
dual_optval = 0.0;
for (i = 0; i < nw; i++) {
dual_optval += y[i] * wcap[i];
}
for (i = 0; i < ns; i++) {
dual_optval += y[nw + i] * sreq[i];
}
printf("Dual optimum value is %.2f\n\n", dual_optval);
/*
* Print all shipments from source 0 to the sinks.
*/
for (i = 0; i < ns; i++) {
if (x[i] != 0.0) {
printf("Ship %5.2f units from source 0 to sink %d\n",
x[i], i);
}
}
/*
* Solve the problem with the interior-point method.
*/
printf("\n\n*************************\n");
printf("* Interior-point method *\n");
printf("*************************\n");
imsl_f_transport(nw, ns, wcap, sreq, cost,
IMSL_TOTAL_COST, &cmin,
IMSL_DUAL_USER, y,
IMSL_METHOD, IMSL_INTERIOR_POINT_METHOD,
IMSL_RETURN_USER, x,
0);
printf("Minimum cost using interior-point method is %.2f\n", cmin);
/*
* Compute dual optimum value, trans(b) * y.
*/
dual_optval = 0.0;
for (i = 0; i < nw; i++) {
dual_optval += y[i] * wcap[i];
}
for (i = 0; i < ns; i++) {
dual_optval += y[nw + i] * sreq[i];
}
printf("Dual optimum value is %.2f\n\n", dual_optval);
/*
* Print the transport quantities delivered from source 0 to all
* sinks that are larger than 0.1.
*/
for (i = 0; i < ns; i++) {
if (x[i] > 0.1) {
printf("Ship %5.2f units from source 0 to sink %d\n",
x[i], i);
}
}
if (wcap)
free(wcap);
if (sreq)
free(sreq);
if (cost)
free(cost);
if (x)
free(x);
if (y)
free(y);
}Output
**************************
* Revised simplex method *
**************************
Minimum cost using revised simplex method is 1001.00
Dual optimum value is 1001.00
Ship 1.00 units from source 0 to sink 14
Ship 3.00 units from source 0 to sink 40
Ship 15.00 units from source 0 to sink 69
Ship 1.00 units from source 0 to sink 97
******************************
* Graph-based simplex method *
******************************
Minimum cost using graph-based simplex method is 1001.00
Dual optimum value is 1001.00
Ship 4.00 units from source 0 to sink 14
Ship 5.00 units from source 0 to sink 24
Ship 6.00 units from source 0 to sink 40
Ship 1.00 units from source 0 to sink 58
Ship 3.00 units from source 0 to sink 69
Ship 1.00 units from source 0 to sink 97
*************************
* Interior-point method *
*************************
Minimum cost using interior-point method is 1001.00
Dual optimum value is 1001.00
Ship 0.63 units from source 0 to sink 14
Ship 1.81 units from source 0 to sink 24
Ship 5.39 units from source 0 to sink 40
Ship 0.35 units from source 0 to sink 58
Ship 2.21 units from source 0 to sink 66
Ship 8.24 units from source 0 to sink 69
Ship 1.38 units from source 0 to sink 97
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. |