Chapter 8: Optimization

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

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



http://www.vni.com/
PHONE: 713.784.3131
FAX:713.781.9260