GAMS pierwsze kroki.pdf

GAMS | pierwsze kroki

Marian Kostrzewski, WEiA, Politechnika Gda«ska

Technika systemów { materiaªy pomocnicze

Publikacja jest w stanie jakim jest. Licz¡c, »e mimo wszystko mo»e oka-

za¢ si¦ po»yteczn¡ udost¦pniam j¡ publiczno±ci do u»ytku. Przyjmuj¦

wszelkie uwagi co do tre±ci i redakcji broszury.

Zamierzam zawrze¢ w niej wi¦cej informacji ni» wynika to z aktualnego

spisu tre±ci. Póki co zawarto±¢ odpowiada popeªnionemu przeze mnie

brykowi sprzed 3 lat. . .

Spis tre±ci

GAMS

1.1

Gªówne zaªo»enia j¦zyka GAMS . . . . . . . . . . . . . . . . . . .

1.2

Model w j¦zyku GAMS

. . . . . . . . . . . . . . . . . . . . . . .

Struktura modelu

2.1

ZBIORY ( SETS ) . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2

Dane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.1

Wprowadzenie poprzez listy ( PARAMETERS ) . . . . . . . . .

2.2.2

Wprowadzenie poprzez tablice (TABLE) . . . . . . . . . .

2.2.3

Wprowadzenie poprzez bezpo±rednie przypisanie

. . . . .

2.3

Zmienne decyzyjne ( VARIABLES )

. . . . . . . . . . . . . . . . . .

2.4

Równania (EQUATIONS) . . . . . . . . . . . . . . . . . . . . . .

2.4.1

Deklaracja równiania . . . . . . . . . . . . . . . . . . . . .

2.4.2

Denicja równania . . . . . . . . . . . . . . . . . . . . . .

2.5

Funkcja celu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.6

Instrukcja MODEL . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.7

Instrukcja SOLVE . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.8

Instrukcja DISPLAY . . . . . . . . . . . . . . . . . . . . . . . . .

Przykªady

GAMS

GAMS (General Algebraic Modelling System) jest j¦zykiem wysokiego pozio-

mu umo»liwiaj¡cym zgrabne formuªowanie problemów optymalizacji za pomoc¡

zwi¦zªych formuª. Zapis jest czytelny dla osoby formuªuj¡cej problem, nadto

daje si¦ ªatwo modykowa¢ i przenosi¢ pomi¦dzy ró»nymi ±rodowiskami kom-

puterowymi (sprz¦towymi i operacyjnymi). Posta¢ ¹ródªowa jest niezale»na od

GAMS

stosowanego dalej we wªa±ciwych obliczeniach motoru (ang. solver ). Gªówni au-

torzy j¦zyka GAMS to Anthony Brook, Paul van der Eijk i Alexander Meeraus.

Opracowanie GAMS'a nansowane byªo przez Bank wiatowy (Bank's Research

Comittee, projekty RPO 671{58 i 673{06).

Dystrybujc¡ pakietu zajmuje si¦ rma:

GAMS Development Corporation

1217 Potomac Street N.W.

Washington, DC 20007

Phone: (202)342{0180

Fax: (202)342{0181

Email: gams@gams.com

Web site: http://www.gams.com/

Dalej w tre±ci tego opracowania wyst¦powa¢ b¦d¡ fragmenty

zapisane w j¦zyku GAMS. Dla ich wyró»nienia wtedy stosowana

b¦dzie czcionka o staªym odst¦pie pomi¦dzy znakami

(jak w tym akapicie).

Tre±¢ tej broszury opracowano na podstawie ksi¡»ki \GAMS release 2.25, A

User's Guide" autorstwa A.Brooke, D.Kendrick, A. Meeraus, The Scientic

Press, rok wydania 1992. Przykªady modeli GAMS pochodz¡ ze strony w Inter-

necie http://www.gams.com/ . Ponadto wykorzystano strony \man" na temat

GAMS'a pochodz¡ce ze stron www Cornell Theory Center.

1.1 Gªówne zaªo»enia j¦zyka GAMS

Lata pi¦¢dziesi¡te i pojawienie si¦ komputerów daªy pocz¡tek gwaªtownemu roz-

wojowi algorytmów i programów komputerowych. Opracowano wiele metod roz-

wi¡zywania ró»nych problemów matematycznych. Gdy przeprowadzono analiz¦

stosowania ró»nych programów okazaªo si¦, »e lwi¡ cz¦±¢ czasu po±wi¦canego na

rozwi¡zanie problemów zabiera odpowiednie przygotowanie danych i opracowa-

nie wyników. Ka»dy model wymagaª wielogodzinnych analiz i programowania;

wszystko po to aby przygotowa¢ dane w formacie wymaganym przez program

realizuj¡cy obliczenia. W takim stanie rzeczy odszukanie i wyszukanie bª¦dów

byªo znacznie utrudnione | zazwyczaj kto inny ukªadaª model, kto inny wpro-

wadzaª dane. Pojawiªo si¦ dodatkowe zadanie | sprawdzenie, »e wprowadzone

dane s¡ poprawne.

J¦zyk GAMS byª czym± na ksztaªt próby uporz¡dkowania tego stanu rze-

czy. Dawaª pewien sformalizowany j¦zyk umo»liwiaj¡cy sformuªowanie pewnej

klasy problemów. Autorzy przygotowuj¡cy projekt postawili sobie nast¦puj¡ce

zadania:

opracowa¢ j¦zyk umo»liwiaj¡cy zwarty opis modeli wielkich systemów;

j¦zyk powinien umo»liwia¢ w prosty sposób dokonywanie modykacji mo-

delu;

informacja o relacjach powinna by¢ jednoznaczna;

opis modelu nie powinien zale»e¢ od programu rozwi¡zuj¡cego.

GAMS

1.2 Model w j¦zyku GAMS

Zanim podejmiemy prób¦ formalizacji denicji j¦zyka GAMS spróbujemy przed-

stawi¢ przykªad jego u»ycia na prostym problemie optymalizacji. Przykªad jest

czystej postaci zagadnieniem transportowym programowania liniowego. Poka»e-

my sformuªowanie zagadnienia w postaci zapisu matematycznego, dalej przed-

stawimy ten sam opis dokonany w j¦zyku GAMS w postaci bez zb¦dnych ko-

mentarzy i z drobiazgowym komentarzem ilustruj¡cym poszczególne zapisy.

Matematycznie problem formuªowany jest nast¦puj¡co:

Indeksy:

i = wytwórcy towaru

j = odbiorcy towaru

dane:

a i = zdolno±¢ produkcyjna i{tego wytwórcy (w sztukach)

b j = wymagana chªonno±¢ rynku j{tego odbiorcy (w sztukach)

c ij = koszt transportu towaru od i{tego wytwórcy do j{tego odbiorcy

($/sztuk¦)

zmienne decyzyjne

x ij = ilo±¢ towaru do przesªania od i{tego wytwórcy do j{tego odbiorcy

(w sztukach); gdzie 8i8j x ij 0

ograniczenia

badaj zdolno±¢ produkcyjn¡ i-tego wytwórcy (w sztukach):

x ij a i

zagwarantuj minimalne dostawy dla j-tego odbiorcy (w sztukach):

x ij b j

funkcja celu

minimalizuj (w k$, i.e. w tysi¡cach $):

Q =

c ij x ij

Prosz¦ zwróci¢ uwag¦, »e ten prosty przykªad prezentuj¦ pewn¡ praktyk¦ formu-

ªowania modelu, dodajmy | zgodn¡ ze sposobem konstrukcji modeli w j¦zyku

GAMS. Po pierwsze, wszystkie wielko±ci modelu j¡ nazwane, zdeniowane i po-

grupowane; okre±lony jest ich typ. Po drugie, porz¡dek wybrano tak, »e »adna

z wielko±ci nie zostaªa u»yta zanim zostaªa zdeniowana. Po trzecie, wsz¦dzie

nazwane s¡ jednostki miary. Po czwarte, jednostki dobrano w taki sposób (k$)

aby program optymalizuj¡cy nie musiaª zmaga¢ si¦ w jednym zadaniu z liczbami

ró»ni¡cymi si¦ o kilka rz¦dów wielko±ci.

W j¦zyku GAMS wprowadzono nast¦puj¡c¡ terminologi¦:

GAMS

wska¹niki

= SETS

dane

= PARAMETERS

zmienne decyzyjne

= VARIABLES

ograniczenia i funkcja celu

= EQUATIONS

Model zagadnienia transportowego zapisany w j¦zyku GAMS mocno przy-

pomina opisany powy»ej model algebraiczny. Podstawowa ró»nica to fakt, »e

wersja GAMS mo»e by¢ odczytana i przetworzona przez komputer.

Sformuªowanie zadania wymaga podania kilku liczb. Zaªó»my, »e nasz przy-

kªad dotyczy instytucji, która ma dwa zakªady produkuj¡ce konserwy (Seattle,

San Diego) oraz trzech odbiorców okre±lonych jako Nowy Jork, Chicago i To-

peka. (Przykªad pochodzi z ksi¡»ki: Dantzig G. B., Linear Programming and

Extensions, Princeton University Press, Princeton, New Jersey, 1963, Rozdziaª

3{3.)

Zaªo»ono, »e odlegªo±ci podano w tysi¡cach mil. Koszt przesyªki jest staªy

(nie zale»y od miejsca poªo»enia producenta i odbiorcy) i wynosi 90 dolarów za

transport jednej partii na odcinku dªugo±ci 1000 mil. (Zachowano oznaczenia

pochodz¡ce z danych opublikowanych przez rm¦ GAMS).

Markets

New York

Chicago

Topeka

Plants

Distances

Supply

Seattle

2.5

1.7

1.8

350

San Diego

2.5

1.8

1.4

600

Demand

325

300

275

Maªy sªowniczek (mo»e si¦ przyda¢):

demand

wielko±¢ zamówiona

distance

odlegªo±¢

market

odbiorca

plant

zakªad produkcyjny

supply

moc produkcyjna

Poni»ej przedstawiono modej sformuªowany w j¦zyku GAMS.

SETS

I canning plants / SEATTLE, SAN-DIEGO /

J markets

/ NEW-YORK, CHICAGO, TOPEKA / ;

PARAMETERS

A(I) capacity of plant i in cases

/ SEATTLE 350

SAN-DIEGO 600 /

B(J) demand at market j in cases

/ NEW-YORK 325

CHICAGO 300

TOPEKA 275 / ;

TABLE D(I,J) distance in thousands of miles

NEW-YORK

CHICAGO

TOPEKA

SEATTLE

2.5

1.7

1.8

SAN-DIEGO

2.5

1.8

1.4;

STRUKTURA MODELU

SCALAR F freight in dollars per case per thousand miles /90/;

PARAMETER C(I,J) transport cost in thousands of dollars per case;

C(I,J) = F * D(I,J) / 1000;

VARIABLES

X(I,J) shipment quantities in cases

Z total transportation costs in thousands of dollars;

POSITIVE VARIABLE X ;

EQUATIONS

COST define objective function

SUPPLY(I) observe supply limit at plant i

DEMAND(J) satisfy demand at market j;

COST .. Z =E= SUM((I,J), C(I,J)*X(I,J));

SUPPLY(I) .. SUM(J, X(I,J)) =L= A(I);

DEMAND(J) .. SUM(I, X(I,J)) =G= B(J);

MODEL TRANSPORT /ALL/;

SOLVE TRANSPORT USING LP MINIMIZING Z;

Poni»ej raz jeszcze rozpiszemy ten model tym razem z komentarzem ilustruj¡-

cym znaczenie u»ytych w zapisie sformuªowa«. Zaczniemy jednak od rozwa»a«

natury ogólnej.

Struktura modelu

W odniesieniu do dalszej tre±ci rozdziaªu omawiaj¡c podstawowe elementy mo-

delu w j¦zyku GAMS odnosi¢ si¦ b¦dziemy do przykªadu przedstawionego wy»ej.

Podstawowe (istniej¡ tak»e zaawansowane) skªadowe modelu to:

na wej±ciu

{ zbiory ( SETS )

deklaracja

okre±lenie (wyliczenie) elementów

{ dane ( PARAMETERS , TABLES , SCALARS )

deklaracja

przypisanie warto±ci

{ zmienne ( VARIABLES )

deklaracja

przypisanie typu

(opcjonalnie) przypisanie ogranicze« i/lub warto±ci pocz¡tko-

wych

{ równania ( EQUATIONS )

deklaracja

denicja

{ instrukcjae MODEL

{ instrukcja SOLVE

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: