Szállítási feladat megoldása a GAMS segítségével

A feladat

Az alábbi szállítási feladatot szeretnénk megoldani. Adott két raktár és három felvevőhely. A szállítási egységköltségeket illetve a raktárakban levő mennyiségeket és a felvevőhelyek igényeit az alábbi táblázat írja le. Cél az igények legolcsóbb kielégítése.

Költségek  
  Felvevőhelyek  
Raktárak New York Chicago Topeka Raktárkészlet
Seattle 0.225 0.153 0.162 350
San Diego 0.225 0.162 0.126 600
Igény 325 300 275  

A GAMS modell

  SETS
       I   raktarak   / SEATTLE, SAN-DIEGO /
       J   felvevohelyek          / NEW-YORK, CHICAGO, TOPEKA / ;
  PARAMETERS
       A(I)  az i-edik raktar keszlete
         /    SEATTLE     350
              SAN-DIEGO   600  /
       B(J)  a j-edik felvevohely igenye
         /    NEW-YORK    325
              CHICAGO     300
              TOPEKA      275  / ;
  TABLE D(I,J)  a szallitas egysegkoltsegei
                    NEW-YORK       CHICAGO      TOPEKA
      SEATTLE         0.225         0.153        0.162
      SAN-DIEGO       0.225         0.162        0.126 ;
  VARIABLES
       X(I,J)  a szallitott mennyisegek
       Z       a teljes szallitasi koltseg ;
  POSITIVE VARIABLE X ;
  EQUATIONS
       COST        celfuggveny
       SUPPLY(I)   az i-edik raktarkeszlet korlatozo feltetele
       DEMAND(J)   a j-edik felvevohely igenyenek korlatozo feltetele ;
  COST ..        Z  =E=  SUM((I,J), D(I,J)*X(I,J)) ;
  SUPPLY(I) ..   SUM(J, X(I,J))  =L=  A(I) ;
  DEMAND(J) ..   SUM(I, X(I,J))  =E=  B(J) ;
  MODEL TRANSPORT /ALL/ ;
  SOLVE TRANSPORT USING LP MINIMIZING Z ;

Indexhalmazok 

  SETS
       I   raktarak   / SEATTLE, SAN-DIEGO /
       J   felvevohelyek          / NEW-YORK, CHICAGO, TOPEKA / ;

A GAMS bekéri az indexhalmazok leírását: adjuk meg a halmaz nevét és elemeit. (Itt, I és J), illetve az elemek felsorolása.

Paraméterek

  PARAMETERS
       A(I)  az i-edik raktar keszlete
         /    SEATTLE     350
              SAN-DIEGO   600  /
       B(J)  a j-edik felvevohely igenye
         /    NEW-YORK    325
              CHICAGO     300
              TOPEKA      275  / ;

Az indexelt paraméterek A(I) és B(J), megadása listázással.

Mint látható, a GAMS megengedi magyarázatok beszúrását, melyeket az eredmény jelentésben fel is használ.

Táblázat 

  TABLE D(I,J)  a szallitas egysegkoltsegei
                    NEW-YORK       CHICAGO      TOPEKA
      SEATTLE         0.225         0.153        0.162
      SAN-DIEGO       0.225         0.162        0.126 ;

Az adatok a fenti módon táblázat formában is megadhatók.

Változók 

  VARIABLES
       X(I,J)  a szallitott mennyisegek
       Z       a teljes szallitasi koltseg ;
  POSITIVE VARIABLE X ;

A változók (a megfelelő indexekkel) a fenti módon definiálhatók.

Az alabbi változótípusokkal dolgozhatunk: FREE (előjelkötetlen), POSITIVE (nemnegatív), NEGATIVE (nempozitív), BINARY (bináris 0,1) , vagy INTEGER (egész). Az alapértelmezés: FREE.

A célfüggvénynek megfelelő változó egyszerűen index nélkül van definiálva: Z.

Korlátozó feltételek 

  EQUATIONS
       COST        celfuggveny
       SUPPLY(I)   az i-edik raktarkeszlet korlatozo feltetele
       DEMAND(J)   a j-edik felvevohely igenyenek korlatozo feltetele ;
  COST ..        Z  =E=  SUM((I,J), D(I,J)*X(I,J)) ;
  SUPPLY(I) ..   SUM(J, X(I,J))  =L=  A(I) ;
  DEMAND(J) ..   SUM(I, X(I,J))  =E=  B(J) ;

A célfüggvény és a korlátozó feltételek a fenti módon irhatók le. Lehetőség van a megengedett megoldások halmazának bonyolultabb leírására is (pl. if-then-else használatára).

=E= jelentése 'egyenlő'
=L= jelentése 'kisebb vagy egyenlő'
=G= jelentése 'nagyobb vagy egyenlő'

A modell leírása 

  MODEL TRANSPORT /ALL/ ;

A modellnek adunk egy nevet (itt TRANSPORT), és megadjuk, hogy mely korlátozó feltételeket kell figyelembe venni. Ez esetben az összes feltételt bevesszük, erre utal az ALL, amely egyenértékű lenne a MODEL TRANSPORT /COST, SUPPLY, DEMAND/ megadással.

A feladat megoldása 

  SOLVE TRANSPORT USING LP MINIMIZING Z ;

A SOLVE megmondja a GAMSnak, hogy (1) melyik modellt oldja meg, (2) milyen megoldó programmal (solver) oldja meg (ez esetben LP solverrel), (3) minimalizáljon vagy maximalizáljon, MINIMIZING vagy MAXIMIZING , és (4) melyik változó legyen a célfüggvény.

A GAMS eredményjelentése (csak az excerpts)

Korlátozó feltételek 


---- COST        =E=  celfuggveny


COST..  - 0.225*X(SEATTLE,NEW-YORK) - 0.153*X(SEATTLE,CHICAGO)

      - 0.162*X(SEATTLE,TOPEKA) - 0.225*X(SAN-DIEGO,NEW-YORK)

      - 0.162*X(SAN-DIEGO,CHICAGO) - 0.126*X(SAN-DIEGO,TOPEKA) + Z =E= 0 ;

      (LHS = 0)


---- SUPPLY      =L=  az i-edik raktarkeszlet korlatozo feltetele


SUPPLY(SEATTLE)..  X(SEATTLE,NEW-YORK) + X(SEATTLE,CHICAGO)

      + X(SEATTLE,TOPEKA) =L= 350 ; (LHS = 0)


SUPPLY(SAN-DIEGO)..  X(SAN-DIEGO,NEW-YORK) + X(SAN-DIEGO,CHICAGO)

      + X(SAN-DIEGO,TOPEKA) =L= 600 ; (LHS = 0)


---- DEMAND      =E=  a j-edik felvevohely igenyenek korlatozo feltetele


DEMAND(NEW-YORK)..  X(SEATTLE,NEW-YORK) + X(SAN-DIEGO,NEW-YORK) =G= 325 ;

      (LHS = 0 ***)


DEMAND(CHICAGO)..  X(SEATTLE,CHICAGO) + X(SAN-DIEGO,CHICAGO) =G= 300 ;

      (LHS = 0 ***)


DEMAND(TOPEKA)..  X(SEATTLE,TOPEKA) + X(SAN-DIEGO,TOPEKA) =G= 275 ;

      (LHS = 0 ***)

A tablazattal megadott egyenletek, egyenlőtlenségek egyenkénti felsorolása.

Oszlopok felsorolása 

---- X          a szallitott mennyisegek


X(SEATTLE,NEW-YORK)
                (.LO, .L, .UP = 0, 0, +INF)
       -0.225   COST
        1       SUPPLY(SEATTLE)
        1       DEMAND(NEW-YORK)

X(SEATTLE,CHICAGO)
                (.LO, .L, .UP = 0, 0, +INF)
       -0.153   COST
        1       SUPPLY(SEATTLE)
        1       DEMAND(CHICAGO)

X(SEATTLE,TOPEKA)
                (.LO, .L, .UP = 0, 0, +INF)
       -0.162   COST
        1       SUPPLY(SEATTLE)
        1       DEMAND(TOPEKA)

REMAINING 3 ENTRIES SKIPPED


---- Z          a teljes szallitasi koltseg 


Z
                (.LO, .L, .UP = -INF, 0, +INF)
        1       COST

Felsorolja az oszlopokat a változók szerint

Megoldási üzenetek 


MODEL STATISTICS

BLOCKS OF EQUATIONS       3     SINGLE EQUATIONS        6
BLOCKS OF VARIABLES       2     SINGLE VARIABLES        7
NON ZERO ELEMENTS        19


GENERATION TIME      =        0.017 SECONDS


EXECUTION TIME       =        0.033 SECONDS        VERID AXU-25-085


               S O L V E      S U M M A R Y

     MODEL   TRANSPORT           OBJECTIVE  Z
     TYPE    LP                  DIRECTION  MINIMIZE
     SOLVER  BDMLP               FROM LINE  47

**** SOLVER STATUS     1 NORMAL COMPLETION
**** MODEL STATUS      1 OPTIMAL
**** OBJECTIVE VALUE              153.6750

 RESOURCE USAGE, LIMIT          0.184     1000.000
 ITERATION COUNT, LIMIT         4         1000



 B D M L P   1.1  ---  AXP/OSF  1.1.045-017

 A. Brooke, A. Drud, and A. Meeraus,
 Analytic Support Unit,
 Development Research Department,
 World Bank,
 Washington, D.C. 20433, U.S.A.

 EXIT -- OPTIMAL SOLUTION FOUND.

Először pár statisztikai adat: feltételek, változók, nemnulla elemek száma.

Látható, hogy a BDMLP solver oldotta meg a feladatot: optimális megoldást talált 4 lépésben 0.184 másodperc alatt.

Megoldás


                       LOWER     LEVEL     UPPER    MARGINAL

---- EQU COST            .         .         .        1.000

  COST        define objective function


---- EQU SUPPLY      observe supply limit at plant i

             LOWER     LEVEL     UPPER    MARGINAL

SEATTLE       -INF    350.000   350.000      EPS
SAN-DIEGO     -INF    550.000   600.000      .


---- EQU DEMAND      satisfy demand at market j

            LOWER     LEVEL     UPPER    MARGINAL

NEW-YORK   325.000   325.000     +INF      0.225
CHICAGO    300.000   300.000     +INF      0.153
TOPEKA     275.000   275.000     +INF      0.126


---- VAR X           shipment quantities in cases

                      LOWER     LEVEL     UPPER    MARGINAL

SEATTLE  .NEW-YORK      .       50.000     +INF       .
SEATTLE  .CHICAGO       .      300.000     +INF       .
SEATTLE  .TOPEKA        .         .        +INF      0.036
SAN-DIEGO.NEW-YORK      .      275.000     +INF       .
SAN-DIEGO.CHICAGO       .         .        +INF      0.009
SAN-DIEGO.TOPEKA        .      275.000     +INF       .


                       LOWER     LEVEL     UPPER    MARGINAL

---- VAR Z              -INF    153.675     +INF       .

  Z           total transportation costs in thousands of dollars


**** REPORT SUMMARY :        0     NONOPT
                             0 INFEASIBLE
                             0  UNBOUNDED

A részletes megoldás leírása. A 'marginals' a szimplex tábla alsó sorára utal.

Irodalom

A GAMS weboldala