% FIGURE 4.7.1
      function [CMIN,X,Y] = DTRAN(WCAP,SREQ,COST,NW,NS)
%
%  FUNCTION DTRAN SOLVES THE TRANSPORTATION PROBLEM
%
%    MINIMIZE    CMIN = COST(1,1)*X(1,1) + ... + COST(NW,NS)*X(NW,NS)
%
%    WITH X(1,1),...,X(NW,NS) NONNEGATIVE, AND
%
%          X(1,1) + ... + X(1,NS)  .LE. WCAP(1)
%             .              .            .
%             .              .            .
%          X(NW,1)+ ... + X(NW,NS) .LE. WCAP(NW)
%          X(1,1) + ... + X(NW,1)    =  SREQ(1)
%             .              .            .
%             .              .            .
%          X(1,NS)+ ... + X(NW,NS)   =  SREQ(NS)
%
%  CAUTION: IF TOTAL STORE REQUIREMENTS EXACTLY EQUAL TOTAL WAREHOUSE
%           CAPACITIES, ALTER ONE WCAP(I) OR SREQ(I) SLIGHTLY, SO THAT 
%           WAREHOUSE CAPACITIES SLIGHTLY EXCEED STORE REQUIREMENTS.
%
%  ARGUMENTS
%
%             ON INPUT                          ON OUTPUT
%             --------                          ---------
%
%    WCAP   - A VECTOR OF LENGTH NW CONTAINING
%             THE WAREHOUSE CAPACITIES.
%
%    SREQ   - A VECTOR OF LENGTH NS CONTAINING
%             THE STORE REQUIREMENTS.  
%
%    COST   - THE NW BY NS COST MATRIX. COST(I,J)
%             IS THE PER UNIT COST TO SHIP FROM
%             WAREHOUSE I TO STORE J.
%
%    NW     - THE NUMBER OF WAREHOUSES.
%
%    NS     - THE NUMBER OF STORES.
%
%    CMIN   -                                   THE TOTAL COST OF THE
%                                               OPTIMAL ROUTING.
%
%    X      -                                   AN NW BY NS MATRIX
%                                               CONTAINING THE OPTIMAL
%                                               ROUTING.  X(I,J) UNITS
%                                               SHOULD BE SHIPPED FROM
%                                               WAREHOUSE I TO STORE J.
%
%    Y      -                                   A VECTOR OF LENGTH NW+NS
%                                               CONTAINING THE DUAL. Y(I)
%                                               GIVES THE DECREASE IN 
%                                               TOTAL COST PER UNIT
%                                               INCREASE IN WCAP(I), FOR
%                                               SMALL INCREASES, AND 
%                                               -Y(NW+J) GIVES THE 
%                                               INCREASE IN TOTAL COST
%                                               PER UNIT INCREASE IN
%                                               SREQ(J).
%
%-----------------------------------------------------------------------
      M = NW+NS;
      N = NW*NS+NW;
%                              SET UP SPARSE CONSTRAINT MATRIX 
      NZ = 0;
      for I=1:NW
         for J=1:NS
            NZ = NZ+1;
            IROW(NZ) = I;  
            JCOL(NZ) = (I-1)*NS + J;
            A(NZ) = 1.0;
         end
         NZ = NZ+1;
         IROW(NZ) = I;
         JCOL(NZ) = NW*NS+I;
         A(NZ) = 1.0;
%                              LOAD WAREHOUSE CAPACITIES INTO B 
         B(I) = WCAP(I);
      end
      for J=1:NS
         for I=1:NW
            NZ = NZ+1;
            IROW(NZ) = NW+J;
            JCOL(NZ) = J + (I-1)*NS;
            A(NZ) = 1.0;
         end
%                              LOAD STORE REQUIREMENTS INTO B 
         B(NW+J) = SREQ(J);
      end
%                              FIRST NW*NS ENTRIES IN C ARE
%                              -COST(I,J).  NEGATIVE SIGN USED
%                              BECAUSE WE WANT TO MINIMIZE COST 
      K = 0;
      for I=1:NW
         for J=1:NS
            K = K+1;
            C(K) = -COST(I,J);
         end
      end
%                              NEXT NW COSTS ARE ZERO, CORRESPONDING
%                              TO WAREHOUSE CAPACITY SLACK VARIABLES
      for I=1:NW
         K = K+1;
         C(K) = 0.0;
      end
%                              USE REVISED SIMPLEX METHOD TO SOLVE
%                              TRANSPORTATION PROBLEM
      [P,XSOL,Y] = DLPRV(A,IROW,JCOL,NZ,B,C,N,M);
%                              FORM OPTIMAL ROUTING MATRIX, X
      CMIN = -P;
      K = 0;
      for I=1:NW
         for J=1:NS
            K = K+1;
            X(I,J) = XSOL(K);
         end
      end
