Řešení úloh lineárního programování v systému GAMS

17.4.11

Řešení úloh lineárního programování v systému GAMS

Doc. Ing. Alois Fiala, CSc.

Chceme-li řešit optimalizační problém v systému GAMS (General Algebraic Modeling System), musíme nejprve příslušný matematický model zapsat ve speciálním modelovacím jazyku. Omezíme se zde pouze na stručný úvod do tohoto jazyka založený na následujícím příkladu (detailní popisy uvedeného jazyka a systému je možno nalézt na adrese http://www.gams.com/ ).

 NahoruStruktura modelu v jazyku GAMS

Základní komponenty modelu v jazyku GAMS jsou tyto:

SETS

Deklarace množin indexů a přiřazení jejich prvků.

Data (PARAMETERS, TABLES, SCALARS)

Deklarace vstupních veličin modelu a přiřazení jejich hodnot.

VARIABLES

Deklarace proměnných modelu, přiřazení jejich typů a případně také jejich mezí a/nebo počátečních hodnot.

EQUATIONS

Deklarace a definice účelové funkce a vlastních omezení (rovnic a nerovností).

MODEL

Specifikuje se, které vztahy z EQUATIONS jsou součástí modelu.

SOLVE

Specifikuje se, co a jak má být řešeno.

DISPLAY (volitelné)

Specifikuje se, co má být zobrazeno ve výstupech z řešení.

 NahoruModel v GAMSu

Model v GAMSu je souhrnem příkazů v jazyku GAMS a ukládá se do souboru s příponou .gms (jedná se vlastně o jistý druh programu). Pokud jde o uspořádání příkazů, platí pravidlo, že žádná entita modelu nemůže být použita dříve, než je deklarována. Typografická úprava příkazů je téměř volná. Příkaz může být rozdělen do několika řádků, mohou být do něj vnořeny prázdné řádky a na jednom řádku může být uvedeno několik příkazů. Každý příkaz by měl být ukončen středníkem.

Překladač GAMSu nerozlišuje velká a malá písmena, takže např. proměnná x je totožná s proměnnou X. V našem příkladě používáme velká písmena pro symboly a slova jazyka GAMS a pro deklarované entity modelu, kdežto malými písmeny jsou psány dokumentační texty (komentáře), které popisují význam jednotlivých částí modelu. V uvedeném příkladě jsou komentáře součástí některých příkazů.

Komentář v příkazu nesmí přesáhnout 80 znaků, musí být na jednom řádku, nesmí začínat rezervovaným slovem GAMSu, dvěma tečkami nebo rovnítkem a nesmí obsahovat čárku, středník a lomítko. Dokumentační text představuje také každý řádek začínající na prvé pozici hvězdičkou.

Tvorba entit modelu zahrnuje dva kroky: deklaraci a přiřazení nebo definici. Deklarací se oznamuje existence něčeho a dává se tomu jméno. Jméno entity musí začínat písmenem následovaným nejvýše 30 písmeny nebo číslicemi. Přiřazení nebo definice znamená určení specifické hodnoty nebo tvaru. V případě vztahů (EQUATIONS) musí být každá deklarace a definice udělána v samostatném příkazu. U ostatních entit je možné deklarace a přiřazení entit stejného typu uskutečnit v jediném příkazu nebo v několika oddělených příkazech.

 NahoruMnožiny (SETS)

Pomocí příkazu SETS se vymezují množiny odpovídající množinám indexů v algebraickém vyjádření modelu. Příkaz

SETS

I zdroje /Z1, Z2, Z3, Z4/

J vyrobky /V1, V2/;

deklaruje dvě množiny indexů, dává jim jména I a J a přiřazuje jim prvky. Význam tohoto příkazu je následující:

I = {Z1, Z2, Z3, Z4}

J = {V1, V2}

Slova zdroje a vyrobky představují dokumentační texty. Jména prvků množin nesmějí přesáhnout 10 znaků, musejí začínat písmenem nebo číslicí a nesmějí obsahovat jiné znaky než písmena, číslice a znaky + a –.

Uvedený příkaz bychom mohli nahradit dvěma příkazy

SET I zdroje /Z1, Z2, Z3, Z4/;
SET J vyrobky /V1, V2/;

Množina I by mohla být deklarována také takto:

SET I zdroje /Z1 * Z4/;

 NahoruData

Data modelu mohou být v GAMSu zadávána v následujících třech formátech:

• seznamy,

• tabulky,

• přímá přiřazení.

Data nemusejí být přímo součástí programu v GAMSu, ale mohou být zadána ve speciálních souborech a načítána pomocí prostředků GDX (GAMS Data Exchange).

 NahoruZadání dat pomocí seznamů

Zadání dat pomocí seznamů je zajišťováno pomocí příkazů PARAMETERS, resp. PARAMETER.

PARAMETERS

B(I) kapacity zdroju /Z1 210, Z2 100, Z3 60, Z4 40/

C(J) jednotkove zisky /V1 4, V2 6/;

Tento příkaz deklaruje existenci dvou parametrů, dává jim jména B a C, deklaruje domény I, resp. J, nad kterými jsou tyto parametry definovány, a přiřazuje těmto parametrům hodnoty pro každý prvek I, resp. J. Uvedený příkaz je možno nahradit následujícími dvěma příkazy:

PARAMETER B(I) kapacity zdroju /Z1 210, Z2 100, Z3 60, Z4 40/;

PARAMETER C(J) jednotkove zisky
/ V1 4
V2 6 /;

Přiřazení hodnot parametrům je zadáno pomocí seznamu dvojic uzavřeného mezi lomítka. Každá dvojice je tvořena prvkem domény a odpovídající hodnotou parametru. Jednotlivé dvojice jsou oddělovány čárkou nebo musejí být uvedeny na samostatných řádcích. Implicitní hodnotou všech parametrů je nula. Stačí tedy zadávat pouze nenulové hodnoty pomocí dvojic prvek a hodnota, přičemž tyto dvojice mohou být uvedeny v libovolném pořadí.

Zvláštním případem parametru je skalár, což je parametr, který nemá žádnou doménu. Je zadáván pomocí příkazu SCALAR, který obsahuje jméno skaláru, případný dokumentační text a "degenerovaný“ seznam obsahující pouze jedinou hodnotu:

SCALAR S nejaka konstanta /50/;

 NahoruZadání dat pomocí tabulek

Zadání dat pomocí tabulek se provádí pomocí příkazu TABLE. V následujícím příkladě je zadána dvourozměrná tabulka (matice):

TABLE A(I,J)

Tento příkaz deklaruje parametr A, specifikuje jeho doménu jako množinu uspořádaných dvojic prvků I a J (tj. kartézský součin množin I a J) a každé dvojici těchto prvků přiřazuje příslušnou hodnotu parametru. Jestliže se v tabulce vyskytují nevyplněná místa, jsou interpretována jako nuly.

 NahoruZadání dat přímým přiřazením

Zadání dat přímým přiřazením se uskutečňuje pomocí přiřazovacího příkazu, který má následující strukturu:

parametr = výraz;

Parametr na levé straně přiřazovacího příkazu musí být předem definován. Výraz na pravé straně může obsahovat číselné konstanty, parametry (musejí ovšem být předem definovány a mít přiřazenou hodnotu), matematické operátory, kulaté závorky a vestavěné funkce GAMSu. Při provádění přiřazovacího příkazu se vyhodnotí výraz na pravé straně a jeho hodnota se přiřadí parametru na straně levé (pokud už tento parametr nějakou hodnotu měl, je přepsána novou hodnotou).

V příkladu 1 není použit žádný přiřazovací příkaz. Hodnoty parametru C v tomto příkladu jsou vyjádřeny v 1 000 Kč za 10 ks výrobku (viz příklad 1 v § 17/4.1). Pokud bychom z nějakého důvodu chtěli zadat parametr D, jehož hodnoty budou vyjádřeny v Kč za kus, mohli bychom to udělat takto:

PARAMETER
D(J) zisky v Kc za kus;
D(J) = 100*C(J);

Prvý příkaz deklaruje parametr D s doménou J bez přiřazení hodnot tomuto parametru (implicitně jsou tedy přiřazeny nuly). Druhý příkaz je přiřazovací, který zajistí, že se pro každý prvek domény J přiřadí parametru D stonásobek odpovídající hodnoty parametru C.

Pokud bychom chtěli přiřadit parametru D hodnotu pro jeden určitý prvek domény J, např. pro prvek V1, mohli bychom to udělat těmito způsoby:

D(‘V1’) = 400;
D("V1“) = 400;

Tedy pokud jako index parametru (nebo proměnné) chceme uvést konkrétní prvek domény, musíme tento prvek uzavřít do apostrofů nebo uvozovek.

 NahoruProměnné (VARIABLES)

Proměnné modelu musejí být deklarovány pomocí příkazu VARIABLES.

VARIABLES

X(J) vyrobena mnozstvi

Z celkovy zisk;

Důsledkem tohoto příkazu je deklarace proměnné X pro každý prvek domény J. Proměnná Z je deklarována bez uvedení domény, protože je to skalární veličina. Každý optimalizační model musí obsahovat jednu takovou proměnnou, která reprezentuje hodnotu účelové funkce, jež se bude maximalizovat nebo minimalizovat.

Když je proměnná deklarována, musí jí být přiřazen typ. Povolené typy jsou tyto:

Typy BINARY a INTEGER se používají při řešení celočíselných problémů.

Proměnná, která reprezentuje hodnotu účelové funkce, musí být skalární a musí být typu FREE (tento typ je implicitní, takže to není nutné explicitně uvádět). V příkladu 1 je touto proměnnou proměnná Z. Rozhodovací proměnné musejí být nezáporné, což je specifikováno příkazem

POSITIVE VARIABLE X;

Je také možné zadat dolní meze, horní meze a počáteční hodnoty proměnných. Dolní a horní meze hodnot proměnných jsou automaticky dány použitým typem. Tyto meze ale může uživatel přepsat pomocí přiřazovacích příkazů, kde je na levé straně specifikace proměnné a typu meze a na pravé straně je výraz reprezentující hodnotu příslušné meze. Typ meze je specifikován tak, že se za jméno proměnné uvede

.LO pro dolní mez (lower bound) a
.UP pro horní mez (upper bound).

Pokud bychom měli data modelu zadána tak jako v příkladu 2, pak bychom horní meze rozhodovacích proměnných zadali příkazem

X.UP(J) = H(J);

Pokud bychom v naší úloze chtěli zadat, že každého výrobku je nutno vyrobit alespoň 10 jednotek, použili bychom příkaz

X.LO(J) = 10;

Zadání počátečních hodnot proměnných nemá při řešení úloh lineárního programování smysl. Při řešení nelineárních úloh je však velmi užitečné zadat vhodné výchozí řešení, z nějž pak řešič pokračuje při hledání optimálního řešení. Příkaz pro zadání výchozího řešení vypadá např. takto:

X.L(J) = 0;

Symbol ".L“ specifikuje zadanou (ve výstupu pak vypočtenou) úroveň (level) proměnné.

 NahoruVztahy (EQUATIONS)

V této části modelu jsou deklarovány a definovány rovnice a nerovnosti reprezentující účelovou funkci a vlastní omezení. Deklaraci zajišťuje příkaz EQUATIONS, v němž se pro každou rovnici či nerovnost uvádí její jméno, případná doména a dokumentační text.

EQUATIONS

F ucelova funkce

O(I) kapacitni omezeni;

V daném příkladě jméno F reprezentuje účelovou funkci (tato funkce je skalární, a proto zde není uvedena žádná doména) a jméno O s doménou I reprezentuje kapacitní omezení.

Každá rovnice či nerovnost musí být definována zvláštním příkazem, který má tyto složky:

• jméno definovaného vztahu (rovnice či nerovnosti),

• doménu tohoto vztahu (pokud existuje),

• symbol "..“ (dvě tečky),

• levostranný výraz,

• některý z těchto relačních operátorů: =L= (menší nebo rovno), =G= (větší nebo rovno), =E= (rovno),

• pravostranný výraz.

Vztahy F a O jsou v našem příkladu definovány takto:

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

O(I) .. SUM(J, A(I,J)*X(J)) =L= B(I);

Prvý vztah definuje účelovou funkci jako rovnici, kde je na levé straně je skalární proměnná Z a na pravé straně je výraz definující její hodnotu. Odpovídající matematický zápis vypadá…