Solves a transportation problem.
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)
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)
Generic: CALL TRAN (WCAP, SREQ, COST, X, CMIN [, ])
Specific: The specific interface names are S_TRAN and D_TRAN.
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).
Informational errors
Type Code
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.
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
PHONE: 713.784.3131 FAX:713.781.9260 |