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 | |
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 ;
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.
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.
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.
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.
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õ'
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.
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.
---- 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.
---- 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
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.
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.