C/ FIGURE 4.7.1
      SUBROUTINE DTRAN(WCAP,SREQ,COST,NW,NS,CMIN,X,Y)
      IMPLICIT DOUBLE PRECISION (A-H,O-Z)    
C                              DECLARATIONS FOR ARGUMENTS
      DOUBLE PRECISION WCAP(NW),SREQ(NS),COST(NW,NS),CMIN,X(NW,NS),
     & Y(NW+NS)
      INTEGER NW,NS
C                              DECLARATIONS FOR LOCAL VARIABLES
      DOUBLE PRECISION A(2*NW*NS+NW),B(NW+NS),C(NW*NS+NW),
     & XSOL(NW*NS+NW)
      INTEGER IROW(2*NW*NS+NW),JCOL(2*NW*NS+NW)
C
C  SUBROUTINE DTRAN SOLVES THE TRANSPORTATION PROBLEM
C
C    MINIMIZE    CMIN = COST(1,1)*X(1,1) + ... + COST(NW,NS)*X(NW,NS)
C
C    WITH X(1,1),...,X(NW,NS) NONNEGATIVE, AND
C
C          X(1,1) + ... + X(1,NS)  .LE. WCAP(1)
C             .              .            .
C             .              .            .
C          X(NW,1)+ ... + X(NW,NS) .LE. WCAP(NW)
C          X(1,1) + ... + X(NW,1)    =  SREQ(1)
C             .              .            .
C             .              .            .
C          X(1,NS)+ ... + X(NW,NS)   =  SREQ(NS)
C
C  CAUTION: IF TOTAL STORE REQUIREMENTS EXACTLY EQUAL TOTAL WAREHOUSE
C           CAPACITIES, ALTER ONE WCAP(I) OR SREQ(I) SLIGHTLY, SO THAT 
C           WAREHOUSE CAPACITIES SLIGHTLY EXCEED STORE REQUIREMENTS.
C 
C  ARGUMENTS
C
C             ON INPUT                          ON OUTPUT
C             --------                          ---------
C
C    WCAP   - A VECTOR OF LENGTH NW CONTAINING
C             THE WAREHOUSE CAPACITIES.
C
C    SREQ   - A VECTOR OF LENGTH NS CONTAINING
C             THE STORE REQUIREMENTS.   
C
C    COST   - THE NW BY NS COST MATRIX. COST(I,J)
C             IS THE PER UNIT COST TO SHIP FROM
C             WAREHOUSE I TO STORE J.
C
C    NW     - THE NUMBER OF WAREHOUSES.
C
C    NS     - THE NUMBER OF STORES.
C
C    CMIN   -                                   THE TOTAL COST OF THE
C                                               OPTIMAL ROUTING.
C
C    X      -                                   AN NW BY NS MATRIX
C                                               CONTAINING THE OPTIMAL
C                                               ROUTING.  X(I,J) UNITS
C                                               SHOULD BE SHIPPED FROM
C                                               WAREHOUSE I TO STORE J.
C
C    Y      -                                   A VECTOR OF LENGTH NW+NS
C                                               CONTAINING THE DUAL. Y(I)
C                                               GIVES THE DECREASE IN 
C                                               TOTAL COST PER UNIT
C                                               INCREASE IN WCAP(I), FOR
C                                               SMALL INCREASES, AND 
C                                               -Y(NW+J) GIVES THE INCREASE 
C                                               IN TOTAL COST PER UNIT
C                                               INCREASE IN SREQ(J).
C
C-----------------------------------------------------------------------
      M = NW+NS
      N = NW*NS+NW
C                              SET UP SPARSE CONSTRAINT MATRIX 
      NZ = 0
      DO 10 I=1,NW
         DO 5 J=1,NS
            NZ = NZ+1
            IROW(NZ) = I  
            JCOL(NZ) = (I-1)*NS + J
            A(NZ) = 1.0
    5    CONTINUE 
         NZ = NZ+1
         IROW(NZ) = I
         JCOL(NZ) = NW*NS+I
         A(NZ) = 1.0
C                              LOAD WAREHOUSE CAPACITIES INTO B 
         B(I) = WCAP(I)
   10 CONTINUE
      DO 20 J=1,NS
         DO 15 I=1,NW
            NZ = NZ+1
            IROW(NZ) = NW+J
            JCOL(NZ) = J + (I-1)*NS
            A(NZ) = 1.0
   15    CONTINUE
C                              LOAD STORE REQUIREMENTS INTO B 
         B(NW+J) = SREQ(J)
   20 CONTINUE
C                              FIRST NW*NS ENTRIES IN C ARE
C                              -COST(I,J).  NEGATIVE SIGN USED
C                              BECAUSE WE WANT TO MINIMIZE COST 
      K = 0
      DO 30 I=1,NW
         DO 25 J=1,NS
            K = K+1
            C(K) = -COST(I,J)
   25    CONTINUE
   30 CONTINUE 
C                              NEXT NW COSTS ARE ZERO, CORRESPONDING
C                              TO WAREHOUSE CAPACITY SLACK VARIABLES
      DO 35 I=1,NW
         K = K+1
         C(K) = 0.0
   35 CONTINUE
C                              USE REVISED SIMPLEX METHOD TO SOLVE
C                              TRANSPORTATION PROBLEM
      CALL DLPRV(A,IROW,JCOL,NZ,B,C,N,M,P,XSOL,Y)
C                              FORM OPTIMAL ROUTING MATRIX, X
      CMIN = -P
      K = 0
      DO 45 I=1,NW
         DO 40 J=1,NS
            K = K+1
            X(I,J) = XSOL(K)
   40    CONTINUE
   45 CONTINUE
      RETURN
      END