TRAN

Solves a transportation problem.

Required Arguments

WCAP — Array of size NW containing the source (warehouse) capacities. (Input)

SREQ — Array of size NS containing the sink (store) requirements. (Input)

COST — Array of size NW by NS containing the cost matrix. (Input)

COST (I, J) is the per unit cost to ship from source I to sink J.

COST (I, J) is the per unit cost to ship from source I to sink J.

X — Array of size NW by NS containing the optimal routing. (Output)

X (I, J) units should be shipped from source I to sink J.

X (I, J) units should be shipped from source I to sink J.

CMIN — Total cost of the optimal routing. (Output)

Optional Arguments

NW — Number of sources. (Input)

Default: NW = SIZE (WCAP, 1).

Default: NW = SIZE (WCAP, 1).

NS — Number of sinks. (Input)

Default: NS = SIZE (SREQ, 1).

Default: NS = SIZE (SREQ, 1).

MAXITN — Upper bound on the number of simplex steps. (Input)

Default: MAXITN = 0, means no limit.

Default: MAXITN = 0, means no limit.

DUAL — Array of size NW + NS containing the dual solution. (Output)

FORTRAN 90 Interface

Generic: CALL TRAN (WCAP, SREQ, COST, X, CMIN [, …])

Specific: The specific interface names are S_TRAN and D_TRAN.

Description

Routine TRAN solves the transportation problem.

Minimize

subject to the constraints

and

and

where C = COST, X = X, 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).

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).

–DUAL (NW+J) gives the increase in total cost per unit increase in SREQ (J).

Comments

Informational errors

Type | Code | Description |
---|---|---|

3 | 1 | There is insufficient source capacity. The total source capacity is less than the total sink needs, so TRAN will return a solution which minimizes the cost to distribute everything in the sources, but does not fill all the sink needs. |

4 | 2 | The maximum number of iterations has been exceeded. |

Example

In this example, there are two warehouses with capacities 40 and 20, and 3 stores, which need 25, 10 and 22 units, respectively.

USE TRAN_INT

IMPLICIT NONE

INTEGER, PARAMETER :: NW=2, NS=3

INTEGER :: I, J, NOUT

REAL :: X(NW,NS), COST(NW,NS), CMIN

! WAREHOUSE CAPACITIES

REAL :: WCAP(NW) =(/40, 20/)

! STORE REQUIREMENTS

REAL :: SREQ(NS) =(/25, 10, 22/)

! COSTS

DATA COST/550,350,300,300,400,100/

!

CALL UMACH(2, NOUT)

! SOLVE TRANSPORTATION PROBLEM

!

CALL TRAN(WCAP, SREQ, COST, X, CMIN)

! PRINT RESULTS

WRITE(NOUT, 99995) CMIN

DO I=1, NW

DO J=1, NS

WRITE (NOUT, 99996) X(I,J),I,J

END DO

END DO

99995 FORMAT (' Minimum cost is ',F10.2)

99996 FORMAT (' Ship ',F5.2,' units from warehouse ',I2, &

' to store ',I2)

END

Output

Minimum cost is 19550.00

Ship 25.00 units from warehouse 1 to store 1

Ship 10.00 units from warehouse 1 to store 2

Ship 2.00 units from warehouse 1 to store 3

Ship 0.00 units from warehouse 2 to store 1

Ship 0.00 units from warehouse 2 to store 2

Ship 20.00 units from warehouse 2 to store 3