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.
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.
CMIN — Total cost of the optimal routing. (Output)
Optional Arguments
NW — Number of sources. (Input)
Default: NW = SIZE (WCAP, 1).
NS — Number of sinks. (Input)
Default: NS = SIZE (SREQ, 1).
MAXITN — Upper bound on the number of simplex steps. (Input)
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).
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
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
