MASARYKOVA UNIVERZITA ÚSTAV MATEMATIKY A STATISTIKY

MASARYKOVA UNIVERZITA PRˇI´RODOVEˇDECKA´ FAKULTA U´STAV MATEMATIKY A STATISTIKY

Bakala´rˇska´ praće

BRNO 2013

MICHAL OHLI´DAL

MASARYKOVA UNIVERZITA PRˇI´RODOVEˇDECKA´ FAKULTA U´STAV MATEMATIKY A STATISTIKY

Software pro rˇesˇenı´ u´lohy linea´rnı´ho programovańı´ Bakala´rˇska´ praće

Michal Ohlı´dal

Vedoucı´ praće: Mgr. Michal Bulant, Ph.D.

Brno 2013

Bibliograficky´ za´znam Autor:

Michal Ohlı´dal Prˇ´ırodoveˇdecka´ fakulta, Masarykova univerzita ´ stav matematiky a statistiky U

Na´zev praće:

Software pro rˇesˇenı´ u´lohy linea´rnı´ho programovańı´

Studijnı´ program:

Matematika

Studijnı´ obor:

Aplikovana´ matematika pro vıćeoborove´ studium

Vedoucı´ praće:

Mgr. Michal Bulant, Ph.D.

Akademicky´ rok:

2012/2013

Pocˇet stran:

viii + 36

Klıćˇova´ slova:

Linea´rnı´ programovańı´; program; GUSEK; GMPL

Bibliographic Entry Author:

Michal Ohlı´dal Faculty of Science, Masaryk University Department of Mathematics and Statistics

Title of Thesis:

Linear programming software

Degree Programme:

Mathematics

Field of Study:

Applied Mathematics for Multi-Branches Study

Supervisor:

Mgr. Michal Bulant, Ph.D.

Academic Year:

2012/2013

Number of Pages:

viii + 36

Keywords:

Linear programming; software; GUSEK; GMPL

Abstrakt Tato praće se zaby´va´ softwarem pro rˇesˇenı´ u´lohy linea´rnı´ho programovańı´. Cı´lem praće je popsat problematiku linea´rnı´ho programovańı´ z hlediska softwarovyćh mozˇnostı´ pro jejı´ rˇesˇenı´. Praće je rozdeˇlena do cˇtyrˇ cˇa´stı´. Prvnı´ cˇa´st prˇedstavuje strucˇny´ u´vod do linea´rnı´ho programovańı´. Jsou v nı´ uvedeny a definovańy za´kladnı´ pojmy a principy linea´rnı´ho programovańı´. Druha´ cˇa´st obsahuje popis dostupne´ho spektra programu˚ urcˇenyćh pro rˇesˇenı´ u´lohy linea´rnı´ho programovańı´. Ve trˇetı´ cˇa´sti jsou popsańy, a na typickyćh u´lohaćh linea´rnı´ho programovańı´ demonstrovańy, mozˇnosti programu GUSEK. V poslednı´ cˇa´sti je uka´zańo pouzˇitı´ programu GUSEK pro rˇesˇenı´ rozsa´hlejsˇ´ıch proble´mu˚.

Abstract This work deals with a software constructed for solving the linear programming problems. The main goal of the work is to describe the linear programing taking the point of view of software options of its solving. The thesis is divided into four parts – the first part provides a brief introduction to the linear programming. The list and definitions of the basic terms and principles of linear programming are covered. The second part deals with descriptions of the available programs used for solving the linear programming problems. In the third part the options of the GUSEK program are described and also shown on the typical examples of linear programing. In the last, fourth part, the use of the GUSEK program for solving more complex problems is shown.

Podeˇkovańı´ Na tomto mı´steˇ bych chteˇl podeˇkovat vedoucı´mu me´ bakala´rˇske´ praće Mgr. Michalu Bulantovi, Ph.D. za odborne´ vedenı´. Da´le bych vyja´drˇil sve´ podeˇkovańı´ Sˇa´rce Ohlı´dalove´, Bc. Haneˇ Ohlı´dalove´, MgA. Alfredu Texelovi a Zuzaneˇ Dudkove´ za pomoc s fina´lnı´mi u´pravami praće.

Prohla´sˇenı´ Prohlasˇuji, zˇe jsem svoji bakala´rˇskou praći vypracoval samostatneˇ s vyuzˇitı´m informacˇnıćh zdroju˚, ktere´ jsou v praći citovańy.

Brno 17. kveˇtna 2013

.......................... Michal Ohlı´dal

Obsah ´ vod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii U Kapitola 1. Linea´rnı´ programovańı´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ loha linea´rnı´ho programovańı´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 U 1.2 Geometrie linea´rnı´ho programovańı´ . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Simplexova´ metoda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 1 4 5

Kapitola 2. Prˇehled programu˚ pro rˇesˇenı´ u´lohy linea´rnı´ho programovańı´ 2.1 Rozdı´ly mezi programy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Vybrane´ programy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 GLPK a GUSEK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 GLPK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 GUSEK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

6 6 7 7 7 8

Kapitola 3. Typicke´ prˇ´ıklady . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 GMPL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Kapacitnı´ proble´m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Smeˇsˇovacı´ proble´m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 MPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Plańovańı´ reklamy (media selection problem) . . . . . . . . . . . . . . . . 3.3 CPLEX LP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ loha o deˇlenı´ materia´lu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 U

9 9 9 13 16 17 22 22

Kapitola 4. Dalsˇ´ı prˇ´ıklady . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Einsteinova ha´danka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Zadańı´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2 Modelovy´ soubor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Dieta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Zadańı´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Modelovy´ soubor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.3 Datovy´ soubor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24 24 24 25 28 28 29 30

Za´veˇr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

Seznam pouzˇite´ literatury . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

– vii –

´ vod U Linea´rnı´ programovańı´ je aplikovana´ matematicka´ disciplıńa. Jakozˇto podmnozˇina problematiky obecne´ho matematicke´ho programovańı´ se zaby´va´ optimalizacı´. A pra´veˇ optimalizace hraje prˇi rozhodovańı´ nejen lidı´, ale hlavneˇ firem a vla´d, vy´znamnou roli. Asi nejcˇasteˇji se s ota´zkou optimalizace, a tedy i prakticke´ho vyuzˇitı´ linea´rnı´ho programovańı´, setka´va´me v ekonomii. Veˇtsˇina u´loh linea´rnı´ho programovańı´, ktere´ jsou prakticky vyuzˇitelne´, dosahuje znacˇnyćh rozmeˇru˚, a je tedy bez vyuzˇitı´ patrˇicˇne´ho softwaru te´meˇrˇ nerˇesˇitelna´. Proto jsem se ve sve´ praći zameˇrˇil na popis programu˚ urcˇenyćh pro rˇesˇenı´ u´lohy linea´rnı´ho programovańı´. Prvnı´ cˇa´st praće popisuje obecne´ vlastnosti neˇkolika vybranyćh softwaru˚. V dalsˇ´ı cˇa´sti je problematika zu´zˇena na popis programu GUSEK a forma´tu˚, ktere´ podporuje. V praći je na typickyćh prˇ´ıkladech, jako je smeˇsˇovacı´ cˇi kapacitnı´ proble´m, demonstrovańa funkcˇnost programu. V praći jsou rozebrańy vsˇechny trˇi typy vstupu˚, ktere´ GUSEK umı´ zpracovat. Nejveˇtsˇ´ı pozornost je pak veˇnovańa forma´tu GMPL, ktery´ je pro GUSEK defaultnı´m.

– viii –

Kapitola 1 Linea´rnı´ programovańı´ Linea´rnı´ programovańı´ se zaby´va´ proble´my souvisejıćı´mi s hledańı´m va´zanyćh extre´mu˚ linea´rnıćh funkcı´, jejichzˇ omezujıćı´ podmıńky majı´ tvar linea´rnıćh rovnic a nerovnic.

1.1

´ loha linea´rnı´ho programovańı´ U

Definice 1.1 Necht’ ai j , bi , c j jsou dana´ rea´lna´ cˇ´ısla, pro i = 1, ..., m; j = 1, ..., n, kde m, n ∈ N . Necht’I¯ ⊆ I = {1, ..., m}, J¯ ⊆ J = {1, ..., n}. Optimalizacˇnı´ u´lohu maximalizovat funkci n

∑ c jx j

j=1

na mnozˇineˇ rˇesˇenı´ soustavy rovnic a nerovnic n

∑ ai j x j ≤ bi

i ∈ I¯

∑ ai j x j = bi

i ∈ I − I¯

xj ≥ 0

j ∈ J¯

j=1 n

j=1

nazy´va´me maximalizacˇnı´ u´lohou linea´rnı´ho programovańı´ v obecne´m tvaru. Funkce ∑nj=1 c j x j se pak nazy´va´ ućˇelova´ funkce. Jestlizˇe I¯ = 0/ a J¯ = J, pak tuto u´lohu maximalizovat n

∑ c jx j

j=1

na mnozˇineˇ rˇesˇenı´ soustavy linea´rnıćh rovnic n

∑ ai j x j = bi

i∈I

xj ≥ 0

j∈J

j=1

–1–

Kapitola 1. Linea´rnı´ programovańı´

2

nazy´va´me maximalizacˇnı´ u´lohou linea´rnı´ho programovańı´ ve standardnı´m tvaru. Jestlizˇe I¯ = I a J¯ = J, pak tuto u´lohu maximalizovat n

∑ c jx j

j=1

na mnozˇineˇ rˇesˇenı´ soustavy linea´rnıćh nerovnic n

∑ ai j x j ≤ bi

i∈I

xj ≥ 0

j∈J

j=1

nazy´va´me u´lohou linea´rnı´ho programovańı´ v kanonicke´m tvaru. Pozna´mka 1.1 Vy´sˇe popsane´ tvary jsou vza´jemneˇ ekvivalentnı´ a lze je mezi sebou prˇeva´deˇt. Kazˇdou podmıńku ve tvaru rovnice n

∑ a jx j = b

j=1

lze zapsat jako soustavu dvou nerovnic n

∑ a jx j ≤ b

j=1 n

− ∑ a j x j ≤ −b j=1

Take´ kazˇdou nerovnici

n

∑ a jx j ≤ b

j=1

lze zapsat ve tvaru rovnice n

∑ a j x j + xn+1 = b

j=1

Pro takto prˇidanou promeˇnnou (xn+1 ) pak do ućˇelove´ funkce prˇida´me koeficient cn+1 = 0. Takzˇe tato promeˇnna´ nebude mı´t na optima´lnı´ hodnotu vliv. V prˇ´ıpadeˇ, kdy v obecne´m tvaru u´lohy linea´rnı´ho programovańı´ nenı´ pro neˇktere´ x j kladen pozˇadavek neza´pornosti, pouzˇijeme u´pravu: x+j ≥ 0, x−j ≥ 0 x j = x+j − x−j Tyto dveˇ nove´ promeˇnne´ pak dosadı´me do vsˇech podmıńek i do ućˇelove´ funkce.


3

Pozna´mka 1.2 Uvedene´ u´lohy lze zapsat i maticoveˇ. Naprˇ´ıklad maximalizacˇnı´ u´loha linea´rnı´ho programovańı´ ve standardnı´m tvaru se da´ zapsat jako u´loha maximalizovat f (x) = cx za podmıńek Ax = b x ≥ 0 Kde A = (ai, j ) je matice, x = (x j ) je vektor promeˇnnyćh b = (bi ), c = (c j )T jsou vektory koeficientu˚ a 0 je nulovy´ vektor, pro i, j ∈ N. Veˇta 1.1

Pro libovolnou mnozˇinu M ⊆ Rn a libovolnou funkci f : M → R platı´: min f (x) = − max(− f (x))

x∈M

Z veˇty 1.1 tedy plyne, zˇe kteroukoliv minimalizacˇnı´ u´lohu linea´rnı´ho programovańı´ lze prˇeve´st na u´lohu maximalizacˇnı´, proto nenı´ trˇeba tyto u´lohy rozebı´rat samostatneˇ. Definice 1.2 Mnozˇinu M = {x ∈ Rn | Ax = b, x ≥ 0} nazy´va´me mnozˇinou prˇ´ıpustnyćh rˇesˇenı´ u´lohy linea´rnı´ho programovańı´ ve standardnı´m tvaru. Definice 1.3 Prˇ´ıpustne´ rˇesˇenı´ x0 ∈ M nazveme optima´lnı´m rˇesˇenı´m maximalizacˇnı´ u´lohy linea´rnı´ho programovańı´, platı´-li pro kazˇde´ x ∈ M : cx0 ≥ cx. Veˇta 1.2 (Dualita v linea´rnı´m programovańı´) Necht’ A je matice a necht’ b,c jsou vektory. Pak pro dvojici u´loh linea´rnı´ho programovańı´ max{cx | Ax ≤ b, x ≥ 0} min{yb | yA ≥ c, y ≥ 0} platı´ pra´veˇ jedno z na´sledujıćıćh trˇ´ı tvrzenı´: 1. obeˇ u´lohy majı´ optima´lnı´ rˇesˇenı´ a optima´lnı´ hodnoty ućˇelovyćh funkcı´ jsou si rovny; 2. jedna z u´loh nema´ zˇa´dne´ prˇ´ıpustne´ rˇesˇenı´ a druha´ u´loha ma´ prˇ´ıpustne´, ale nema´ optima´lnı´ rˇesˇenı´ (ućˇelova´ funkce nenı´ omezena´); 3. ani jedna u´loha nema´ prˇ´ıpustne´ rˇesˇenı´. Tuto veˇtu lze vyslovit pro u´lohu linea´rnı´ho programovańı´ v libovolne´m tvaru. Veˇta 1.3 Necht’A je matice typu (m, n), necht’b ∈ Rm . Pak ma´ soustava Ax = b neza´porne´ rˇesˇenı´, pra´veˇ kdyzˇ pro vsˇechna u ∈ Rm splnˇujıćı´ podmıńku AT u ≥ 0 platı´ bT u ≥ 0.


4

Veˇta 1.4 Necht’M = {x ∈ Rn | Ax = b, x ≥ 0} = 6 0. / Jestlizˇe existuje rea´lne´ cˇ´ıslo γ tak, zˇe pro libovolne´ x ∈ M platı´ cT x ≤ γ pak existuje optima´lnı´ rˇesˇenı´ u´lohy linea´rnı´ho programovańı´ max{cT x | Ax = b, x ≥ 0}

1.2

Geometrie linea´rnı´ho programovańı´

Definice 2.1 Mnozˇinu S ⊆ Rn nazveme konvexnı´ mnozˇinou1 , jestlizˇe pro libovolne´ dva body x1 , x2 ∈ S a pro libovolne´ α ∈ (0, 1) platı´ αx1 + (1 − α)x2 ∈ S Definice 2.2 Konvexnı´ polyedricka´ mnozˇina (nebo take´ polyedr) M ⊆ Rn je takova´ mnozˇina, kterou lze vyja´drˇit jako pru˚nik konecˇne´ho pocˇtu uzavrˇenyćh poloprostoru˚. Hranicˇnı´ mnozˇiny teˇchto poloprostoru˚ se nazy´vajı´ vytva´rˇejıćı´ nadroviny mnozˇiny M. Veˇta 2.1 Mnozˇina prˇ´ıpustnyćh ˇresˇenı´ u´lohy linea´rnı´ho programovańı´ je konvexnı´ polyedricka´ mnozˇina. Mnozˇina M ∗ optima´lnıćh rˇesˇenı´ u´lohy max{cx | Ax = b, x ≥ O} je rovneˇzˇ konvexnı´ polyedricka´ mnozˇina. Definice 2.3 Necht’ S ⊆ Rn je libovolna´ mnozˇina. Bod s ∈ S nazveme krajnı´m bodem mnozˇiny S, jestlizˇe neexistujı´ body x1 , x2 ∈ S a cˇ´ıslo α ∈ (0, 1) takove´, zˇe x1 6= x2 a s = αx1 + (1 − α)x2 . Veˇta 2.2

Konvexnı´ polyedricka´ mnozˇina ma´ konecˇny´ pocˇet krajnıćh bodu˚.

Definice 2.4 Necht’ M ⊆ Rn je konvexnı´ polyedricka´ mnozˇina a S ⊂ M je nepra´zdna´ mnozˇina. Jestlizˇe lze S vyja´drˇit jako pru˚nik mnozˇiny M a teˇch jejich vytva´rˇejıćıćh nadrovin, ktere´ mnozˇinu S obsahujı´, je S steˇna mnozˇiny M. Definice 2.5 Jednorozmeˇrna´ steˇna se nazy´va´ hrana. Definice 2.6 Prˇ´ıpustne´ rˇesˇenı´ x ∈ M = {x ∈ Rn | Ax = b, x ≥ 0} nazveme bazicky´m (za´kladnı´m) rˇesˇenı´m u´lohy linea´rnı´ho programovańı´, jestlizˇe jsou sloupce matice A s indexy odpovı´dajıćı´mi nenulovy´m slozˇka´m vektoru x linea´rneˇ neza´visle´. Veˇta 2.3 Bod x ∈ M = {x ∈ Rn | Ax = b, x ≥ 0} je krajnı´m bodem mnozˇiny M pra´veˇ tehdy, kdyzˇ je bazicky´m rˇesˇenı´m. 1 Prakticke ´ prˇ´ıklady konvexnıćh mnozˇin i dalsˇ´ıch pojmu˚ z teorie linea´rnı´ho programovańı´ je mozˇno nale´zt

v [7].


1.3

5

Simplexova´ metoda

Simplexova´2 metoda je metoda urcˇena´ k rˇesˇenı´ u´lohy linea´rnı´ho programovańı´. Za´kladnı´ mysˇlenka se da´ jednodusˇe geomericky popsat: Prˇedpokla´dejme, zˇe zna´me krajnı´ bod x0 mnozˇiny M prˇ´ıpustnyćh rˇesˇenı´ u´lohy. Z tohoto bodu vycha´zı´ konecˇny´ pocˇet hran mnozˇiny M, z nichzˇ kazˇda´ bud’ obsahuje jediny´ dalsˇ´ı krajnı´ bod mnozˇiny M, nebo je neomezena´. Jestlizˇe na neˇktere´ neomezene´ hraneˇ existuje bod, pro ktery´ je hodnota ućˇelove´ funkce veˇtsˇ´ı nezˇ cT x0 , nema´ u´loha optima´lnı´ rˇesˇenı´ a postup koncˇ´ı. V opacˇne´m prˇ´ıpadeˇ hleda´me sousednı´ krajnı´ bod x1 , pro ktery´ platı´ cT x1 > cT x0 . Potom stejny´ postup, ktery´ jsme pouzˇili pro x0 , aplikujeme na x1 . Pokud neexistuje sousednı´ krajnı´ bod s vlastnostı´ cT x > cT x0 , je x0 hledany´m optima´lnı´m rˇesˇenı´m.

2 Teorie simplexove ´ metody prˇesahuje rozsah te´to praće, proto zde nebude podrobneˇ rozebrańa. Odvozenı´

a du˚kazy je mozˇne´ nale´zt naprˇ´ıklad v [11]. Detailneˇjsˇ´ı popis simplexove´ metody obsahuje take´ [6].

Kapitola 2 Prˇehled programu˚ pro rˇesˇenı´ u´lohy linea´rnı´ho programovańı´ Programu˚, umozˇnˇujıćıćh rˇesˇenı´ u´loh linea´rnı´ho programovańı´, je cela´ rˇada. Neˇktere´ majı´ formu samostatne´ho softwaru, jine´ formu knihovny, dostupne´ prostrˇednictvı´m jine´ho softwarove´ho na´stroje1 . Neˇktere´ balıćˇky nabı´zı´ obeˇ tyto mozˇnosti soucˇasneˇ. Veˇtsˇina progamu˚ je schopna rˇesˇit nejen u´lohy linea´rnı´ho programovańı´, ale i dalsˇ´ı, slozˇiteˇjsˇ´ı, optimalizacˇnı´ u´lohy2 . Mozˇnosti, ktere´ nabı´zı´ veˇtsˇina programu˚, jsou z velke´ cˇa´sti srovnatelne´, proto nejprve vypı´sˇu neˇktere´ vlastnosti, ve kteryćh se navza´jem mohou lisˇit. Pote´ se zmıńı´m podrobneˇji o neˇkolika vybranyćh programech3 .

2.1

Rozdı´ly mezi programy

Typ - Programy mohou obsahovat pouze prostrˇedı´ pro vytva´rˇenı´ modelu˚, solver (program, ktery´ samotny´ model vyrˇesˇ´ı), nebo obeˇ tyto soucˇa´sti integrovane´ do jednoho celku. Podporovane´ operacˇnı´ syste´my - Veˇtsˇina programu˚ je multiplatformnı´, ale neˇktere´ beˇzˇ´ı pouze pod urcˇity´m operacˇnı´m syste´mem4 . Dostupnost - Optimalizacˇnı´ programy jsou veˇtsˇinou komercˇnı´, avsˇak nabı´zı´ zdarma trial verzi, nebo verzi pro studijnı´ a vy´zkumne´ ućˇely. K dostańı´ jsou i freewarove´ na´stroje, ty ale by´vajı´ obecneˇ o neˇco pomalejsˇ´ı.

1 Naprˇ´ıklad

MATLAB, Microsoft Office Excel, TOMLAB atp. je mozˇnost rˇesˇenı´ u´loh celocˇ´ıselne´ho a smı´sˇene´ho programovańı´, tyto dalsˇ´ı typy u´loh vsˇak vzhledem k zameˇrˇenı´ a rozsahu praće nebudu da´le rozebı´rat. 3 Srovna ´ nı´ programu˚ vycha´zı´ z [13]. 4 Nejc ˇ asteˇji programy fungujı´ pod Windows, cˇasteˇji chybı´ podpora Linuxu nebo Mac OS. 2 Standardem

–6–

Kapitola 2. Prˇehled programu˚ pro rˇesˇenı´ u´lohy linea´rnı´ho programovańı´

2.2

7

Vybrane´ programy

GLPK (GNU Linear Programming Kit) – popis GLPK je obsahem na´sledujıćı´ kapitoly. IBM ILOG CPLEX Optimization Studio je komplexnı´ optimalizacˇnı´ na´stroj vyvı´jeny´ spolecˇnostı´ IBM. Pro modelovańı´ u´loh pouzˇ´ıva vlastnı´ modelovacı´ jazyk CPLEX LP. K programu existuje obsa´hla´ dokumentace a je zdarma dostupny´ pro studijnı´ a vy´zkumne´ ućˇely v ra´mci IBM Academic Initiative[4]. MOSEK je komercˇnı´ solver dostupny´ jako samostatny´ program, nebo jako knihovna pro MATLAB. MOSEK je dostupny´ zdarma, jako trial verze nebo ve verzi pro akademicke´ ućˇely. Nabı´zı´ take´ rozhranı´ pro C, Javu, Python a dalsˇ´ı. Linear Programming Solver je zdarma dostupny´ program, jehozˇ hlavnı´ devizou je jednoduche´ graficke´ uzˇivatelske´ prostrˇedı´. Vy´stupem programu je prˇesny´ vy´pis kroku˚ simplexove´ metody (jednotlive´ simplexove´ tabulky), cozˇ jej cˇinı´ vhodny´m pro vzdeˇla´vacı´ ućˇely. Lindo solver suite je balıćˇek optimalizacˇnıćh produktu˚ od firmy Lindo. Soucˇa´stı´ balıćˇku je What’sBest! (add-in pro MS Excel), LINGO (modelovacı´ prostrˇedı´ a solver) a Lindo API (knihovna optimalizacˇnıćh postupu˚ a solveru˚). CLP je open-source solver u´loh linea´rnı´ho programovańı´. Tento program je vyvı´jeny´ neza´vislou iniciativou COIN-OR.[2]

2.3 2.3.1

GLPK a GUSEK GLPK

GLPK (GNU Linear Programming Kit) je volneˇ sˇirˇitelny´5 balıćˇek, urcˇeny´ pro rˇesˇenı´ u´loh linea´rnı´ho a smı´sˇene´ho celocˇ´ıselne´ho programovańı´. Hlavnı´mi soucˇa´stmi GLPK jsou: • prima´rnı´ a dua´lnı´ simplexova´ metoda, • prima´rnı´ a dua´lnı´ metoda vnitrˇnıćh bodu˚, • metoda veˇtvı´ a rˇezu˚, • prˇekladacˇ pro GNU MathProg,6 • aplikacˇnı´ programove´ rozhranı´, • samostatny´ solver. 5 Program

je soucˇa´stı´ GNU projektu, spada´ tedy pod podmıńky GNU General Public Licence, je tedy mozˇne´ jej volneˇ pouzˇ´ıvat, sˇ´ırˇit i modifikovat za podmıńek danyćh licencı´. [10] 6 GNU MathProg je modelovacı´ jazyk podporovany ´ GLPK.

Kapitola 2. Prˇehled programu˚ pro rˇesˇenı´ u´lohy linea´rnı´ho programovańı´

8

Vzhledem k licenci, pod kterou je GLPK sˇ´ırˇen, existuje neˇkolik programu˚, ktere´ jsou na za´kladeˇ GLPK postaveny. Kromeˇ programu GUSEK, ktere´mu se budu veˇnovat v na´sledujıćı´m textu, se jedna´ naprˇ´ıklad o GLPK Lab. GLPK podporuje, kromeˇ sve´ho prima´rnı´ho jazyku, ktery´m je GNU MathProg, i vstup ve forma´tu CPLEX LP a MPS7 .

2.3.2

GUSEK

Pro pouzˇitı´ GLPK stacˇ´ı obycˇejny´ textovy´ editor, ve ktere´m lze vytvorˇit modelove´ soubory a na´sledneˇ pomocı´ prˇ´ıkazove´ho rˇa´dku spustit GLPK solver. Tento postup je vsˇak, zvla´sˇteˇ pro neinformatiky, poneˇkud slozˇity´. Pra´veˇ proto vznikl GUSEK, cozˇ je v podstateˇ pouze mı´rneˇ upraveny´ editor8 zdrojove´ho ko´du, prˇ´ımo napojeny´ na GLPK solver. Licence GUSEKu je stejna´ jako v prˇ´ıpadeˇ GLPK, je tedy prˇ´ıstupny´ ke stazˇenı´9 a pouzˇ´ıvańı´ zcela zdarma. Instalacı´ programu se nebudu podrobneˇ zaby´vat, vy´sˇe prˇilozˇeny´ odkaz je v tomhle ohledu plneˇ dostacˇujıćı´.

Obra´zek 2.1: GUSEK GUSEK umı´ pouzˇ´ıvat neˇkolik typu˚ souboru˚, ktere´ rozlisˇuje na za´kladeˇ prˇ´ıpon: .mod - soubor GMPL modelu (mu˚zˇe obsahovat i datovou cˇa´st), .dat - datova´ cˇa´st GMPL modelu, .out - vy´stupnı´ soubor, .mps - model ve forma´tu MPS, .lp - model ve forma´tu CPLEX LP. 7 Popis

jednotlivyćh forma´tu˚, tedy GMPL, CPLEX LP a MPS je obsahem na´sledujıćı´ kapitoly. o SciTE editoru k nalezenı´ na [12]. 9 Dalsˇ´ı informace o staz ˇ enı´ a instalaci GUSEKu na [1]. 8 Informace

Kapitola 3 Typicke´ prˇ´ıklady V te´to cˇa´sti praće uvedu na´zorne´ prˇ´ıklady pouzˇitı´ programu GUSEK. Prima´rnı´m modelovacı´m jazykem GUSEKu je GNU Math Prog,1 proto mu bude veˇnovańa nejveˇtsˇ´ı pozornost. Krom modelu˚ zapsanyćh pomocı´ GMPL (GNU Mathematical Programming Language je pouze jine´ oznacˇenı´ pro GNU Math Prog) uka´zˇu a popı´sˇu model2 vytvorˇeny´ v CPLEX LP a MPS.

3.1

GMPL

GNU Math Prog je jazyk urcˇeny´ k vytva´rˇenı´ modelu˚ matematicke´ho programovańı´. Oficia´lnı´ dokumentace je soucˇa´stı´ instalacˇnı´ho balıćˇku GLPK i GUSEKu. GMPL je, jak jizˇ bylo zmıńeˇno, hlavnı´m jazykem, se ktery´m GUSEK pracuje, proto mu bude v na´sledujıćı´ cˇa´sti vyhrazen nejveˇtsˇ´ı prostor.

3.1.1

Kapacitnı´ proble´m

Prvnı´ u´lohou, jejı´zˇ rˇesˇenı´ budu prezentovat, je jednoduchy´ kapacitnı´ proble´m. Firma uvazˇuje o vy´robeˇ 3 typu˚ vy´robku˚ (pro jednoduchost pouzˇiji oznacˇenı´ A, B, C). K jejich vy´robeˇ potrˇebuje surovinu N a praći L. Jak mnozˇstvı´ suroviny na skladeˇ, tak mnozˇstvı´ praće, je ´ kolem je maximalizovat omezene´. Firma da´le vı´, za kolik dany´ vy´robek proda´ na trhu. U zisk firmy. Zadańı´ u´lohy Prˇejdeˇme tedy ke konkretizaci zadańı´. Na´sledujıćı´ tabulka obsahuje v rˇa´dcıćh mnozˇstvı´ praće L a suroviny N, potrˇebne´ k vyrobenı´ dane´ho vy´robku (sloupecˇky A, B, C). V poslednı´m sloupci jsou maxima´lnı´ mozˇne´ dostupne´ zdroje. Jedna´ se tedy o mnozˇstvı´ suroviny na skladeˇ a dostupny´ pracovnı´ cˇas. V poslednı´m rˇa´dku je pak pro kazˇdy´ vy´robek uveden zisk firmy z prodeje jednoho kusu. 1 Kompletnı´ 2 Prˇ´ıklady

manua´l ke GMPL je k nalezenı´ v instalacˇnı´ dokumentaci, neˇktere´ dalsˇ´ı informace na [3]. v te´to cˇa´sto jsou inspirovańy typicky´mi prˇ´ıklady v [8] a [5].

–9–

Kapitola 3. Typicke´ prˇ´ıklady

10

L N Zisk

A B 1 3 2 1 30 45

C Omezenı´ 2 480 2 600 40

Pro vytvorˇenı´ modelu musı´me urcˇit promeˇnne´, omezenı´ a ućˇelovou funkci. V nasˇem prˇ´ıpadeˇ jsou promeˇnne´ 3: • x1 - mnozˇstvı´ vyrobene´ho produktu A, • x2 - mnozˇstvı´ vyrobene´ho produktu B, • x3 - mnozˇstvı´ vyrobene´ho produktu C. Omezenı´ dane´ho modelu jsou maxima´lnı´ dostupne´ mnozˇstvı´ praće L a suroviny N. V prˇedchozı´ tabulce jsou udańa jednotkova´ mnozˇstvı´ suroviny a praće, potrˇebna´ k vy´robeˇ jednotlivyćh vy´robku˚. Omezenı´ tedy zapı´sˇeme pomocı´ nerovnic: x1 + 3x2 + 2x3 ≤ 480 2x1 + x2 + 2x3 ≤ 600 ´ kolem je maximalizace zisku, jde tedy o maximalizaci rovnice: U zisk = 30x1 + 45x2 + 40x3 Modelovy´ soubor Nynı´, kdyzˇ zna´me zadańı´ a vı´me co chceme zjistit, je na cˇase prˇejı´t k prakticke´ realizaci. Zadany´ proble´m musı´me zapsat pomocı´ GMPL. Klıćˇove´ polozˇky, ktere´ musı´me deklarovat jsou: • promeˇnne´, • ućˇelova´ funkce, • omezenı´, • data prˇ´ıslusˇna´ dane´mu proble´mu. Na´sledujıćı´ ko´d ukazuje, jak vypada´ jednoduchy´ kapacitnı´ proble´m, zapsany´ v jazyce MathProg3 .

3C ˇ ´ısla

rˇa´dku˚ nejsou prˇ´ımou soucˇa´stı´ ko´du, jsou prˇidańa pouze pro snazsˇ´ı orientaci.

Kapitola 3. Typicke´ prˇ´ıklady 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

11

# # Výrobní problém # # Maximalizace zisku. # /* Proměnné */ var x1 >= 0; /* Množství výrobku A */ var x2 >= 0; /* Množství výrobku B */ var x3 >= 0; /* Množství výrobku C */ /* Účelová funkce */ maximize zisk: 30*x1 + 45*x2 + 40*x3; /* Omezení */ s.t. L : x1 + 3*x2 + 2*x3 <= 480; s.t. N : 2*x1 + x2 + 2*x3 <= 600; end;

ˇ a´dky 1 azˇ 5 jsou komenta´rˇe - cokoliv vyskytujıćı´ se na rˇa´dku za krˇ´ızˇkem (#) je R povazˇovańo za komenta´rˇ. Stejneˇ tak se za komenta´rˇ povazˇuje vsˇe, napsane´ mezi znaky /* a */. Takove´to komenta´rˇe se pak mohou vyskytovat kdekoliv v ko´du. Jako prvnı´ krok je trˇeba nadeklarovat promeˇnne´. Rˇa´dky 8 azˇ 10 deklarujı´ promeˇnne´ x1, x2 a x3. Deklarace promeˇnne´ zacˇ´ına´ klıćˇovy´m slovem var. MathProg umozˇnˇuje zapsat omezenı´ promeˇnnyćh prˇ´ımo v jejich deklaraci (nejen >= 0, ale i jine´). Na´zvy promeˇnnyćh mohou by´t libovolne´ alfanumericke´ kombinace znaku˚. Prvnı´ znak na´zvu vsˇak nesmı´ by´t cˇ´ıslo. Kazˇdy´ rˇa´dek ko´du musı´ by´t ukoncˇen strˇednı´kem (;). ˇ a´dek 13 specifikuje ućˇelovou funkci. Vzhledem k tomu, zˇe se jedna´ o maximalizacˇnı´ R u´lohu, je klıćˇovy´m slovem maximize, v prˇ´ıpadeˇ minimalizacˇnı´ u´lohy by bylo pouzˇito ´ cˇelova´ funkce je pojmenovańa zisk a jejı´ hodnota je 30 ∗ x1 + klıćˇove´ slovo minimize. U 45 ∗ x2 + 40 ∗ x3. Dvojtecˇka (:) oddeˇluje na´zev ućˇelove´ funkce od jejı´ definice. ˇ a´dky 16 a 17 definujı´ omezenı´ modelu. V nasˇem prˇ´ıpadeˇ se jedna´ o maxima´lnı´ R mnozˇstvı´ suroviny na skladeˇ a maxia´lnı´ mnozˇstvı´ dostupne´ praće. Klıćˇove´ slovo s.t. (subject to) nenı´ povinnou soucˇa´stı´ deklarace, ale zlepsˇuje cˇitelnost ko´du. Jednotliva´ omezenı´ jsou pojmenovańa L a N. Na´zev omezenı´ a jeho definice jsou opeˇt oddeˇleny dvojtecˇkou (:). Kazˇdy´ soubor v jazyce GMPL musı´ koncˇit klıćˇovy´m slovem end; (rˇa´dek 19). Za pozna´mku zajiste´ stojı´ fakt, zˇe tento modelovy´ soubor neobsahuje datovou cˇa´st. To je zpu˚sobeno jednoduchostı´ prˇ´ıkladu, kdy jsou data prˇ´ımou soucˇa´stı´ deklaracı´ promeˇnnyćh a omezenı´. Na druhe´m prˇ´ıkladu uka´zˇu, jak vypada´ model obsahujıćı´ vsˇechny regule´rnı´ cˇa´sti.


12

ˇ esˇenı´ u´lohy R Pro vyrˇesˇenı´ u´lohy postupujeme v na´sledujıćıćh krocıćh. Vytvorˇeny´ soubor ulozˇ´ıme (File/Save) s prˇ´ıponou .mod (naprˇ´ıklad vyrobni1.mod) a na´sledneˇ spustı´me samotny´ GLPK solver (Tools/Go). Pokud chceme, aby GLPK vygenerovalo vy´stupnı´ soubor, zatrhneme v menu Tools polozˇku Generate Output File on Go. GLPK pak vygeneruje vy´stupnı´ soubor, ktery´ pojmenuje stejneˇ jako modelovy´ soubor, ale s prˇ´ıponou .out, a ulozˇ´ı do slozˇky, ve ktere´ se nacha´zı´ modelovy´ soubor. Vy´stupnı´ soubor se take´ ihned otevrˇe v GUSEKu. Vy´stupnı´ informace Kromeˇ vy´stupnı´ho souboru vyrobni1.out obsahuje neˇktere´ informace i vy´stup, ktery´ GUSEK zobrazı´ v prave´ polovineˇ pracovnı´ho okna. >D:\dokumenty\škola\mat\Bc\gusek\glpsol.exe ... ... OPTIMAL SOLUTION FOUND Time used: 0.0 secs Memory used: 0.1 Mb (108157 bytes) Writing basic solution to ‘vyrobni1.out’... >Exit code: 0 Time: 0.251

V prˇ´ıpadeˇ chybne´ syntaxe modelu se pra´veˇ v tomto reportu zobrazı´ chybova´ zpra´va i s informacı´, na ktere´m rˇa´dku se proble´m nacha´zı´ (po kliknutı´ na tuto chybovou hla´sˇku se zbarvı´ zˇluteˇ hla´sˇenı´ i rˇa´dek v ko´du, ktere´ho se ty´ka´). Pokud je model v porˇa´dku a optima´lnı´ rˇesˇenı´ existuje, hla´sı´ program: OPTIMAL SOLUTION FOUND. V prˇ´ıpadeˇ, kdy u´loha ma´ prˇ´ıpustna´ rˇesˇenı´, ale optima´lnı´ rˇesˇenı´ neexistuje, vypı´sˇe zde GUSEK hla´sˇenı´ PROBLEM HAS UNBOUNDED SOLUTION, v prˇ´ıpadeˇ, kdy neexistuje zˇa´dne´ prˇ´ıpustne´ rˇesˇenı´, a tedy ani rˇesˇenı´ optima´lnı´, zahla´sı´ GUSEK PROBLEM HAS NO FEASIBLE SOLUTION. Vy´stupnı´ soubor Problem: Rows: Columns: Non-zeros: Status: Objective: No. -----1 2 3

vyrobni1 3 3 9 OPTIMAL zisk = 11160 (MAXimum)

Row name -----------zisk L N

St Activity Lower bound Upper bound Marginal -- ------------- ------------- ------------- ------------B 11160 NU 480 480 12 NU 600 600 9

Kapitola 3. Typicke´ prˇ´ıklady No. -----1 2 3 ...

Column name -----------x1 x2 x3

13

St Activity Lower bound Upper bound Marginal -- ------------- ------------- ------------- ------------B 264 0 B 72 0 NL 0 0 -2

Vy´stupnı´ soubor se skla´da´ ze 4 cˇa´stı´4 : • informace o proble´mu a optima´lnı´ hodnota ućˇelove´ funkce; • prˇesne´ informace o stavu ućˇelove´ funkce a omezenı´; • prˇesne´ informace o optima´lnıćh hodnotaćh promeˇnnyćh; • informace o podmıńkaćh optimality. Pro tento konkre´tnı´ proble´m tedy existuje optima´lnı´ rˇesˇenı´, jak je videˇt v prvnı´ cˇa´sti vy´stupu, (Status: OPTIMAL) a jeho hodnota je 11160. Pokud by u´loha optima´lnı´ rˇesˇenı´ nemeˇla, zobrazı´ se zde Status: UNDEFINED nebo Status: INFEASIBLE, v za´vislosti na tom, zda existujı´ prˇ´ıpustna´ rˇesˇenı´, ale neexistuje optima´lnı´, nebo neexistuje zˇa´dne´ prˇ´ıpustne´ rˇesˇenı´. Ve trˇetı´ cˇa´sti vy´stupnı´ho souboru vidı´me, prˇi jakyćh hodnotaćh promeˇnnyćh x1 , x2 a x3 je optima dosazˇeno. Aby firma dosa´hla optima´lnı´ho zisku, bude vyra´beˇt 264 kusu˚ produktu A, 72 kusu˚ produktu B a produkt C nebude vyra´beˇt vu˚bec.

3.1.2

Smeˇsˇovacı´ proble´m

Druhy´m prˇ´ıkladem, ktere´mu se ve sve´ praći budu veˇnovat, je smeˇsˇovacı´ proble´m. Firma, zaby´vajıćı´ se zpracovańı´m kovu˚, potrˇebuje zı´skat dane´ mnozˇstvı´ dvou ru˚znyćh kovu˚ (kov1, kov2). K dispozici ma´ 3 ru˚zne´ slitiny (A,B,C), z nichzˇ kazˇda´ obsahuje urcˇite´ mnozˇstvı´ ´ kolem teˇchto dvou kovu˚. Zna´me take´ cenu, za kterou firma jednotlive´ slitiny nakupuje. U je zı´skat potrˇebna´ mnozˇstvı´ kovu˚ za co nejnizˇsˇ´ı cenu. Zadańı´ u´lohy V na´sledujıćı´ tabulce reprezentujı´ sloupecˇky jednotlive´ suroviny, v rˇa´dcıćh je pak uvedeno mnozˇstvı´ (v kilogramech) jednotlivyćh kovu˚ ve 100 kilogramech suroviny a cena suroviny (v korunaćh), opeˇt vztazˇena´ ke 100 kg. V poslednı´m sloupci je pak uvedeno mnozˇstvı´ obou kovu˚, ktere´ firma potrˇebuje zı´skat.

Kov 1 Kov 2 Cena

4 Podrobny ´

vy´znamne´.

A 4,5 51 800

B C 11,5 30 48 54 1000 950

Mnozˇstvı´ 210 600

popis prˇesahuje rozsah te´to praće, proto vyberu jen informace, ktere´ jsou pro tuto praći


14

Mu˚zˇeme tedy definovat promeˇnne´, ktere´ se budou jmenovat: • A - mnozˇstvı´ zakoupene´ slitiny A, • B - mnozˇstvı´ zakoupene´ slitiny B, • C - mnozˇstvı´ zakoupene´ slitiny C. Omezenı´ v dane´m modelu jsou dveˇ. Jedna´ se o minima´lnı´ pozˇadovana´ mnozˇstvı´ jednotlivyćh kovu˚: 4, 5A + 11, 5B + 30C ≥ 210 51A + 48B + 54C ≥ 600 ´ cˇelovou funkcı´ pak je soucˇet cen jednotlivyćh slitin: U cena = 800A + 1000B + 950C Tuto konecˇnou cenu chceme minimalizovat, jedna´ se tedy o minimalizacˇnı´ u´lohu. Modelovy´ soubor Modely zapsane´ v jazyce MathProg obvykle obsahujı´ dveˇ cˇa´sti: modelovou a datovou. Tyto dveˇ cˇa´sti se mohou vyskytovat bud’ v jednom souboru (s prˇ´ıponou .mod) nebo ve dvou, kdy modelova´ cˇa´st je ulozˇena s prˇ´ıponou .mod a datova´ cˇa´st je ulozˇena s prˇ´ıponou .dat. Samostatny´ soubor pro datovou cˇa´st je vy´hodny´, pracuje-li na projektu vıće lidı´, nebo v prˇ´ıpadeˇ, zˇe chceme pouzˇ´ıt jeden model na neˇkolik ru˚znyćh skupin dat. V tomto konkre´tnı´m prˇ´ıkladeˇ jsem pouzˇil jeden soubor, ktery´ obsahuje jak modelovou cˇa´st (rˇa´dky 1-25) a datovou cˇa´st (rˇa´dky 26-46). 1 2 3 4 5 5 7 8 9 10 11 12 13 14 15 16 17 18 19 20

# # Směšovací problém # # Minimalizace nákladů # /* Množina potřebných kovů */ set SLIT; /* Parametry */ param kov1 {i in SLIT}; param kov2 {i in SLIT}; param cena {i in SLIT}; /* Proměnné */ var x {i in SLIT} >=0; /* Účelová funkce */ minimize z : sum{i in SLIT} cena[i]*x[i];

Kapitola 3. Typicke´ prˇ´ıklady 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

15

/* Omezení */ s.t. hmotnost : sum{i in SLIT} x[i] <= 12; s.t. potreba_kov1 : sum{i in SLIT} kov1[i]*x[i] >= 210; s.t. potreba_kov2 : sum{i in SLIT} kov2[i]*x[i] >= 600; data; /* Datová část */ set SLIT := A B C; param kov1:= A 4.5 B 11.5 C 30; param kov2:= A 51 B 48 C 54; param cena:= A 800 B 1000 C 950; end;

Klıćˇova´ slovo set definuje mnozˇinu. Pod pojmenovańı´ mnozˇina spada´ v GMPL znacˇne´ mnozˇstvı´ elementu˚. Ve vy´sˇe uvedene´m ko´du je mnozˇinou vektor, pojmenovany´ SLIT. Mnozˇina SLIT obsahuje prvky A, B a C. Samotne´ hodnoty, prˇ´ıslusˇne´ te´to mnozˇineˇ, jsou pak uvedeny azˇ v datove´ cˇa´sti souboru (rˇa´dek 29). Da´le na rˇa´dku 29 vidı´me, jak se prvky mnozˇiny deklarujı´: set SLIT := A B C kde set je klıćˇove´ slovo, SLIT je na´zev mnozˇiny (pro ktery´ platı´ stejna´ pravidla jako pro pojmenova´vańı´ promeˇnnyćh) a prvky mnozˇiny jsou zapsańy za znakem := a vza´jemneˇ se oddeˇlujı´ mezerou. ˇ a´dky 11-13 definujı´ parametry modelu. Parametry jsou kov1 – mnozˇstvı´ kovu 1 v dane´ R surovineˇ, kov2 – mnozˇstvı´ kovu 2 v dane´ surovineˇ a cena suroviny. Tyto parametry vytva´rˇejı´ datovou matici a jsou da´le pouzˇity k vy´pocˇtu omezenı´. Jako prˇ´ıklad pouzˇiji parametr kov1 (tedy mnozˇstvı´ prvnı´ho kovu v jednotlivyćh slitinaćh). Tento parametr je definovań na mnozˇineˇ SLIT, takzˇe kazˇda´ slitina v te´to mnozˇineˇ obsazˇena´ obsahuje urcˇite´ mnozˇstvı´ prvnı´ho kovu. Nynı´ se podı´vejme na rˇa´dky 31 azˇ 34. Zde je definice mnozˇstvı´ prvnı´ho kovu v jednotlivyćh slitinaćh. Parametr kov1 je tedy vektor de´lky 3, ktery´ obsahuje na´sledujıćı´ u´daje: kov1[A] = 4,5; kov1[B] = 11,5; kov1[C] = 30. Zby´vajıćı´ parametry jsou definovańy analogicky. Nynı´ se vrat’me k definici promeˇnnyćh. Ta se nacha´zı´ na rˇa´dku 16. Tento rˇa´dek deklaruje 3 promeˇnne´. Promeˇnnou x pro kazˇdy´ cˇlen mnozˇiny SLIT (tedy x[A], x[B], x[C]). Na tomto rˇa´dku je pak jesˇteˇ omezenı´ vsˇech promeˇnnyćh, ktere´ musı´ by´t ≥ 0.


16

´ cˇelovou funkci definuje rˇa´dek 19. Za´klad deklarace je stejny´ jako v prˇedchozı´m U prˇ´ıkladu (klıćˇove´ slovo minimize, na´zev funkce z a jejı´ definice na´sledujıćı´ za dvojtecˇkou). Rozdı´lne´ je pouze vyja´drˇenı´ ve tvaru funkce s vyuzˇitı´m datove´ matice. Vyja´drˇenı´ minimize z : sum{i in SLIT} cena[i]*x[i] ˇr´ıka´, zˇe chceme minimalizovat sumu soucˇinu˚ ceny a mnozˇstvı´ jednotlivyćh slitin prˇes vsˇechny prvky mnozˇiny SLIT. Omezenı´ na rˇa´dcıćh 22 azˇ 24 je deklarovańo obdobneˇ. Jako prˇ´ıklad uvedu omezenı´ potreba kov1. Opeˇt scˇ´ıta´me prˇes vsˇechny prvky mnozˇiny SLIT, tentoka´t vsˇak soucˇin mnozˇstvı´ prvnı´ho kovu v dane´ slitineˇ a mnozˇstvı´ pouzˇite´ slitiny (kov[A] * x[A]). ˇ esˇenı´ u´lohy R V prˇ´ıpadeˇ, kdy je datova´ cˇa´st soucˇa´stı´ modelove´ho souboru, je postup rˇesˇenı´ u´lohy shodny´ s postupem v prˇedchozı´ sekci. Proto se ted’zameˇrˇ´ım na situaci, kdy chceme datovy´ a modelovy´ soubor oddeˇlit. Samotny´ ko´d zu˚sta´va´ stejny´, pouze z modelove´ho souboru vyjmeme rˇa´dky 26 azˇ 45 a ulozˇ´ıme je do nove´ho souboru, na jehozˇ konec jesˇteˇ doplnı´me klıćˇove´ slovo end. Tento soubor pak ulozˇ´ıme s prˇ´ıponou .dat (naprˇ´ıklad smesovaci.dat). Pro jednoduchost je vhodne´, aby se modelovy´ a datovy´ soubor jmenovaly stejneˇ (samozrˇejmeˇ s vyjı´mkou prˇ´ıpony). Pokud se oba tyto soubory jmenujı´ stejneˇ a nacha´zı´ se ve stejne´ slozˇce, stacˇ´ı prˇed spusˇteˇnı´m modelovańı´ (pomocı´ prˇ´ıkazu Go) zatrhnout v menu Tools polozˇku Use External .dat. Pokud bychom chteˇli, aby se datovy´ soubor jmenoval jinak nezˇ soubor modelovy´, musı´me nejprve otevrˇ´ıt datovy´ soubor, v menu Tools vybrat mozˇnost Use as Default .dat File. Tento datovy´ soubor pak bude povazˇovań za defaultnı´ pro vsˇechny modelove´ soubory bez ohledu na jejich na´zev, dokud takto nevybereme jiny´ datovy´ soubor, nebo pameˇt’nevycˇistı´me prˇ´ıkazem Clear Extra .dat Files, opeˇt v menu Tools. Vy´stup Vy´stupnı´ informace i vy´stupnı´ soubor jsou ekvivalentnı´ vy´stupu˚m v minule´m prˇ´ıkladu, proto jejich prˇesny´ popis tentokra´t nebudu uva´deˇt. Omezı´m se pouze na informaci, ohledneˇ rˇesˇenı´ u´lohy. Prˇ´ıklad ma´ opeˇt optima´lnı´ rˇesˇenı´, jehozˇ hodnoty jsou: • mnozˇstvı´ pouzˇite´ slitiny A je 5,15 kg, • slitina B pouzˇita nebude, • mnozˇstvı´ pouzˇite´ slitiny C je 6,22 kg. Prˇi te´to kombinaci vstupnıćh slitin, dosa´hneme optima´lnı´ ceny surovin, ktera´ je 10052,4 korun.

3.2

MPS

MPS je sloupcoveˇ orientovany´ forma´t, urcˇeny´ pro za´pis modelu˚ linea´rnı´ho a celocˇ´ıselne´ho programovańı´. V soucˇasnosti nepatrˇ´ı mezi nejpouzˇ´ıvaneˇjsˇ´ı, ale je velmi univerza´lneˇ akceptovany´ mnoha programy (jak komercˇnı´mi, tak ostatnı´mi).


3.2.1

17

Plańovańı´ reklamy (media selection problem)

Trˇetı´m prˇ´ıkladem, na ktere´m budu demonstrovat pouzˇitı´ vstupu ve forma´tu MPS, je proble´m plańovańı´ reklamy. Zadańı´ u´lohy Reklamnı´ agentura dostala zaka´zku na zpracovańı´ reklamnı´ kampaneˇ jiste´ho produktu. Zna´me celkovy´ objem prostrˇedku˚, ktery´ mu˚zˇe reklamnı´ agentura na kampanˇ pouzˇ´ıt (10 mil. Kcˇ). Vı´me, jaky´ pocˇet lidı´ ovlivnı´ reklama za 1000 Kcˇ v jednotlivyćh me´diıćh (televize - 750, ra´dio - 420, cˇasopis - 300, noviny - 360, billboardy - 180). Zada´vajıćı´ firma si da´le stanovila podmıńky: • za reklamu v televizi a ra´diu nesmı´me utratit vıće nezˇ polovinu rozpocˇtu; • do kazˇde´ho z peˇti typu˚ me´diı´ je trˇeba umı´stit reklamu za minima´lneˇ 10% a maxima´lneˇ 30% celkove´ho rozpocˇtu; • chceme, aby reklama zapu˚sobila na alesponˇ 2,5 mil. osob ve veˇku do 40 let, 0,8 mil. osob s prˇ´ıjmem nad 15000 Kcˇ meˇsıćˇneˇ a 1,5 mil. osob se strˇedosˇkolsky´m nebo vysˇsˇ´ım vzdeˇlańı´m. V na´sledujıćı´ tabulce jsou zobrazeny informace o strukturˇe diva´ku˚ (potazˇmo cˇtena´rˇu˚, posluchacˇu˚) danyćh me´diı´. Koeficienty v tabulce uda´vajı´ pocˇet osob dane´ kategorie, ovlivneˇnyćh reklamou na 1000 Kcˇ vynalozˇenyćh prostrˇedku˚. televize veˇk do 40 let 320 prˇ´ıjem nad 15000 Kcˇ 120 SSˇ vzdeˇlańı´ 350

ra´dio cˇasopis noviny 280 140 240 90 60 60 200 120 140

billboard 120 50 60

Formulace modelu Nynı´ tedy prˇistoupı´m k formulaci modelu pomocı´ rovnic a nerovnic. Promeˇnny´mi budou mnozˇstvı´ prostrˇedku˚ vynalozˇenyćh na reklamu v jednotlivyćh me´diıćh: • x1 reklama v televizi, • x2 reklama v ra´diu, • x3 reklama v cˇasopise, • x4 reklama v novinaćh, • x5 reklama na billboardech.


18

Podmıńky: Celkovy´ rozpocˇet kampaneˇ nesmı´ prˇesa´hnout 10 mil. Kcˇ: x1 + x2 + x3 + x4 + x5 ≤ 10 Za reklamu v ra´diu a televizi nesmı´me utratit vıće nezˇ polovinu rozpocˇtu: x1 + x2 ≤ 5 Za reklamu v kazˇde´m typu me´dia musı´me utratit mezi 10% a 30% celkove´ho rozpocˇtu: 1 ≤ x j ≤ 3,

j = 1, 2, ..., 5

Podmıńky pro veˇk, prˇ´ıjem a vzdeˇlańı´: 320x1 + 280x2 + 140x3 + 240x4 + 120x5 ≥ 2500 120x1 + 90x2 + 60x3 + 60x4 + 50x5 ≥ 800 350x1 + 200x2 + 120x3 + 140x4 + 60x5 ≥ 1500 ´ cˇelovou funkcı´ modelu je pak maximalizace celkove´ho dopadu reklamy: U z = 750x1 + 420x2 + 300x3 + 360x4 + 180x5 Modelovy´ soubor Pro potrˇeby modelu ve forma´tu MPS je vhodne´ rovnice poneˇkud upravit. Prvnı´ u´pravou, je zmeˇna ućˇelove´ funkce. MPS podporuje pouze minimalizacˇnı´ funkce, proto ućˇelovou funkci prˇepı´sˇeme do podoby: value = −z = −750x1 − 420x2 − 300x3 − 360x4 − 180x5 Ostatnı´ nerovnice prˇepı´sˇeme do podoby rovnic, kdy za jejich prave´ strany dosadı´me promeˇnne´, ktere´ na´sledneˇ omezı´me. Tento postup je shodny´ pro vsˇechny nerovnice, proto zde uvedu pouze jeden prˇ´ıklad: 320x1 + 280x2 + 140x3 + 240x4 + 120x5 = A A ≥ 2500 V MPS forma´tu ma´ modelovy´ soubor svou pevneˇ danou strukturu. Skla´da´ se z neˇkolika sekcı´: • NAME • ROWS • COLUMNS • RHS


19

• RANGES • BOUNDS • ENDATA Kazˇda´ z teˇchto sekcı´ zacˇ´ına´ jejı´m oznacˇenı´m, ktere´ musı´ zacˇ´ınat v prvnı´m sloupecˇku.5 Konec dane´ sekce je indikovań pocˇa´tkem sekce na´sledujıćı´ (naprˇ´ıklad rˇa´dky 4, 5, 12 v na´sledujıćı´m ko´du). Sekce RHS, RANGES a BOUNDS jsou, narozdı´l od ostatnıćh, nepovinne´. Soubor nesmı´ obsahovat zˇa´dne´ pra´zdne´ rˇa´dky (komenta´rˇe v MPS zacˇ´ınajı´ hveˇzdicˇkou (*) - rˇa´dky 1-3). Kazˇda´ ze sekcı´ je horizonta´lneˇ rozdeˇlena na 6 polı´: Sloupce Obsah 1 2 3 4 5 5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

Pole1 Pole2 2-3 5-12 Ko´d Na´zev

Pole3 15-22 Na´zev

Pole4 25-36 Cˇ´ıslo

Pole5 Pole6 40-47 50-61 Na´zev Cˇ´ıslo

*000000001111111111222222222233333333334444444444555555555566 *234567890123456789012345678901234567890123456789012345678901 * NAME Reklama ROWS N value G A G B G C L D L F COLUMNS x1 value -750 A 320 B 120 C 350 D 1 F 1 x2 value -420 A 280 B 90 C 200 D 1 F 1 x3 value -300 A 140 B 60 C 120 D 0 F 1 x4 value -360 A 240 B 60 C 140 D 0 F 1 x5 value -180 A 120 B 50 C 60 D 0 F 1 RHS RHS1 A 2500 B 800 C 1500 D 5 F 10

5 Vzhledem

k sloupcove´ strukturˇe souboru doporucˇuji prˇi jeho tvorbeˇ v GUSEKu vybrat mozˇnost Use Monospaced Font v menu Options.

Kapitola 3. Typicke´ prˇ´ıklady 34 BOUNDS 35 UP BND1 36 LO 37 UP 38 LO 39 LO 40 UP 41 LO 42 UP 43 LO 44 UP 45 ENDATA 46

x1 x1 x2 x2 x3 x3 x4 x4 x5 x5

20

3 1 3 1 1 3 1 3 1 3

Sekce NAME obsahuje ve 3. poli na´zev proble´mu. V nasˇem prˇ´ıkladeˇ se jedna´ o na´zev Reklama. Sekce ROWS obsahuje definici jednotlivyćh rˇa´dku˚ proble´mu. V prvnı´m poli oznacˇ´ıme, jak je dany´ rˇa´dek omezeny´ (N - neomezeny´, L - mensˇ´ı nezˇ, G - veˇtsˇ´ı nezˇ). Druhe´ pole obsahuje na´zev rˇa´dku, tedy value (ućˇelova´ funkce - za ućˇelovou funkci se povazˇuje prvnı´ neomezeny´ rˇa´dek), A, B, C, D, a F. Sekce COLUMNS obsahuje v druhe´m poli na´zev jednotlivyćh sloupcu˚ (tedy promeˇnnyćh), ve trˇetı´m a cˇtvrte´m poli (stejneˇ jako v pa´te´m a sˇeste´m) pak na´zev a hodnotu pro jednotlive´ rˇa´dky. Konkre´tneˇ rˇa´dky 13 azˇ 15 rˇ´ıkajı´, zˇe v ućˇelove´ funkci je promeˇnna´ x1 zahrnuta -750 kra´t, v rˇa´dku F (maxima´lnı´ mozˇne´ vy´daje na reklamu) jednou a obdobneˇ pro ostatnı´ rˇa´dky. Sekce RHS doplnˇuje hodnoty pro jednotliva´ linea´rnı´ omezenı´ rˇa´dku˚ (jedna´ se tedy o prave´ strany pu˚vodnıćh nerovnic). V druhe´m poli je na´zev omezenı´ (stacˇ´ı pro prvnı´ omezenı´), ve trˇetı´m na´zev rˇa´dku, ktery´ omezujeme a ve cˇtvrte´m hodnota tohoto omezenı´. Sekce RANGES je nepovinna´ cˇa´st, ktera´ doplnˇuje sekci RHS v prˇ´ıpadeˇ, kdy ma´ neˇktery´ z rˇa´dku˚ hornı´ i dolnı´ omezenı´. Sekce BOUNDS obsahuje omezenı´ promeˇnnyćh (tedy x1 , ..., x5 ). Pro spodnı´ hranici pouzˇijeme v prvnı´m poli oznacˇenı´ LO, pro hornı´ hranici UP. Druhe´ pole obsahuje na´zev vektoru omezenı´ (stacˇ´ı u prvnı´ho omezenı´). Trˇetı´ pole pak obsahuje na´zev promeˇnne´, jejı´zˇ omezenı´ chceme zapsat a cˇtvrte´ pole obsahuje hodnotu tohoto omezenı´. Pokud chceme zapsat omezenı´ hornı´ i dolnı´ pro promeˇnnou x1 musı´me je zapsat zvla´sˇt’, do dvou rˇa´dku˚ (naprˇ´ıklad rˇa´dky 35 a 36 zapisujı´ omezenı´ 1 ≤ x1 ≤ 3). ENDATA je sekce, ktere´ ukoncˇuje soubor.


21

ˇ esˇenı´ R Vzhledem k tomu, zˇe se jedna´ o soubor ve forma´tu MPS, je trˇeba tento soubor take´ spra´vneˇ ulozˇit. To znamena´ s prˇ´ıponou .mps. Jinak nebude GUSEK schopen vytvorˇit model. Zby´vajıćı´ postup rˇesˇenı´ je pak opeˇt shodny´ s prˇedchozı´mi prˇ´ıklady. Optima´lnı´ rozvrzˇenı´ reklamy je pak na´sledujıćı´: • reklama v televizi: 3 mil. Kcˇ, • reklama v ra´diu: 2 mil. Kcˇ, • reklama v cˇasopisu: 1 mil. Kcˇ, • reklama v novinaćh: 3 mil. Kcˇ, • reklama na billboardech: 1 mil. Kcˇ. Prˇi tomto rozlozˇenı´ vy´daju˚ na reklamu povede kampanˇ k ovlivneˇnı´ 4,65 mil. osob.6

6 Prˇi

zjisˇt’ovańı´ hodnoty ućˇelove´ funkce, musı´me mı´t na pameˇti, zˇe funkce value, kterou jsme minimalizovali, odpovı´da´ opacˇne´ hodnoteˇ pu˚vodnı´ funkce z, kterou jsme chteˇli maximalizovat.


3.3

22

CPLEX LP

Poslednı´m forma´tem vstupnı´ho souboru, ktery´ mu˚zˇeme v GUSEKu pouzˇ´ıt je CPLEX LP. Tento forma´t budu prezentovat na prˇ´ıkladeˇ u´lohy o optima´lnı´m deˇlenı´ materia´lu.

3.3.1

´ loha o deˇlenı´ materia´lu U

Zadańı´ u´lohy Firma, ktera´ vyra´bı´ kovove´ soucˇa´stky, nakupuje trubky o de´lce 65 cm v ceneˇ 1500 Kcˇ za kus. Jaky´m zpu˚sobem ma´ firma tyto trubky rozrˇezat, aby prˇi co nejnizˇsˇ´ıch na´kladech zı´skala alesponˇ 1200 trubek de´lky 20 cm a alesponˇ 900 trubek de´lky 15 cm? Cˇtyrˇi mozˇnosti, jak z vyćhozı´ho materia´lu zı´skat cı´love´ kusy, zobrazuje tabulka:

20 cm 15 cm Odpad

1. 2. 3 2 0 1 5 10

3. 4. 1 0 3 4 0 5

Rozhodujeme mezi teˇmito 4 zpu˚soby, promeˇnne´ tedy budou: • x1 : pocˇet pu˚vodnıćh trubek, rozrˇezanyćh prvnı´m zpu˚sobem (to znamena´ na 3 trubky de´lky 20 cm, velikost odpadu pro tento prˇ´ıklad nenı´ podstatna´), • x2 : pocˇet pu˚vodnıćh trubek, rozrˇezanyćh druhy´m zpu˚sobem (to znamena´ na 2 trubky po 20 cm a jednu trubku de´lky 15 cm), • x3 : pocˇet trubek, rozrˇezanyćh trˇetı´m zpu˚sobem, • x4 : pocˇet trubek, rozrˇezanyćh cˇtvrty´m zpu˚sobem. Omezenı´ modelu jsou dańa pozˇadavky na minima´lnı´ mnozˇstvı´ trubek jednotlivyćh de´lek. Chceme nejmeńeˇ 1200 trubek de´lky 20 cm: 3x1 + 2x2 + x3 ≥ 1200 Obdobneˇ chceme nejmeńeˇ 900 kusu˚ trubek, de´lky 15 cm: x2 + 3x3 + 4x4 ≥ 900 Mnozˇstvı´ trubek, rozrˇezanyćh jednotlivy´mi zpu˚soby, musı´ by´t neza´porne´: x j ≥ 0, j = 1, 2, 3, 4 Chceme minimalizovat na´klady, to znamena´, zˇe minimalizujeme ućˇelovou funkci: cena = 1500x1 + 1500x2 + 1500x3 + 1500x4


23

Modelovy´ soubor 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

\ \ Optimální dělení materiálu \ minimize cena: 1500 x1 + 1500 x2 + 1500 x3 + 1500 x4 subject to 3 x1 + 2 x2 + x3 >= 1200 x2 + 3 x3 + 4 x4 >= 900 bounds x1 >= x2 >= x3 >= x4 >=

0 0 0 0

end

Komenta´rˇe v CPLEX LP forma´tu zacˇ´ınajı´ zpeˇtny´m lomı´tkem (\) a pokracˇujı´ do konce rˇa´dku (naprˇ´ıklad rˇa´dky 1-3). Pra´zdne´ rˇa´dky jsou prˇekladacˇem prˇeskakovańy, jejich mnozˇstvı´ a pozice jsou libovolne´. Deklarace ućˇelove´ funkce zacˇ´ına´ klıćˇovy´m slovem minimize (pro minimalizacˇnı´ u´lohu [rˇa´dek 5], pro maximalizacˇnı´ by to pak bylo maximize). Na´zev, ktery´ je nepovinny´, je od jejı´ samotne´ definice oddeˇlen dvojtecˇkou (Rˇa´dek 6), na´zev funkce je tedy cena a jejı´ tvar je cena: 1500 x1 + 1500 x2 + 1500 x3 + 1500 x4. Definice omezenı´ zacˇ´ına´ klıćˇovy´m slovem subject to (rˇa´dek 12). Jednotliva´ omezenı´ mohou, ale nemusı´ by´t pojmenovańa. Forma omezenı´ je intuitivnı´ (rˇa´dky 9 a 10). Omezenı´ promeˇnnyćh na´sleduje za klıćˇovy´m slovem bounds. Zde mohou by´t zapsańa jednostranna´ omezenı´, ale i omezenı´ oboustranne´ (naprˇ´ıklad 0 ≤ x1 ≤ 5). Klıćˇove´ slovo end by meˇlo ukoncˇovat soubor (nenı´ povinnou soucˇa´stı´, ale doporucˇuje se jej pouzˇ´ıt). ˇ esˇenı´ R Stejneˇ, jako u vsˇech souboru˚, pouzˇ´ıvanyćh v GUSEKu, je i zde trˇeba dba´t na spra´vnou prˇ´ıponu souboru. V prˇ´ıpadeˇ forma´tu CPLEX LP je touto prˇ´ıponou .lp. Dalsˇ´ı postup je ekvivalentnı´ prˇedchozı´m prˇ´ıkladu˚m, omezı´m se tedy na zapsańı´ vy´slednyćh hodnot. Minima´lnı´ ceny (900 000 Kcˇ) dosa´hneme, pokud rozrˇezˇeme 300 trubek prvnı´m zpu˚sobem a 300 trubek trˇetı´m zpu˚sobem.

Kapitola 4 Dalsˇ´ı prˇ´ıklady Po prˇedchozı´ kapitole, kde byly uka´zańy za´klady pouzˇitı´ programu GUSEK na jednoduchyćh u´lohaćh, uvedu v te´to cˇa´sti dva prˇ´ıklady obsa´hlejsˇ´ı. Konkre´tneˇ se jedna´ o Einsteinovu ha´danku a Stigleru˚v vy´zˇivovy´ proble´m.

4.1

Einsteinova ha´danka

Einsteinova ha´danka1 je pomeˇrneˇ zna´ma´ logicka´ ha´danka, vyskytujıćı´ se v neˇkolika ru˚znyćh verzıćh. I tato ha´danka je rˇesˇitelna´ za pomoci programu GUSEK.

4.1.1

Zadańı´

Ma´me 5 domu˚ v 5 rozdı´lnyćh barvaćh. V kazˇde´m domeˇ zˇije osoba rozdı´lne´ na´rodnosti, ktera´ pije neˇktery´ z 5 na´poju˚, chova´ neˇktere´ z 5 zvı´rˇat a kourˇ´ı neˇktery´ z 5 druhu˚ cigaret. Kazˇdy´ z obyvatel pije jiny´ na´poj, chova´ jine´ zvı´rˇe a kourˇ´ı jine´ cigarety nezˇ ostatnı´. Da´le ma´me jesˇteˇ neˇkolik informacı´: • Anglicˇan zˇije v cˇervene´m domeˇ, • Sˇpaneˇl vlastnı´ psa, • ka´va je pita v zelene´m domeˇ, • Ukrajinec pije cˇaj, • zeleny´ du˚m je hned napravo od slonovinove´ho, • kurˇa´k cigaret Old Gold vlastnı´ sˇneky, • cigarety Kools jsou kourˇeny ve zˇlute´m domeˇ, • obyvatel prostrˇednı´ho domu pije mle´ko, • Nor zˇije v prvnı´m domeˇ, 1 Zada ´ nı´

prˇ´ıkladu a zdrojovy´ ko´d pocha´zı´ ze vzorovyćh sobouru˚ programu GLPK.

– 24 –

Kapitola 4. Dalsˇ´ı prˇ´ıklady

• muzˇ, ktery´ kourˇ´ı Chesterfieldky, zˇije v domeˇ vedle muzˇe, ktery´ chova´ lisˇku, • cigarety Kools jsou kourˇeny v domeˇ vedle domu, kde je chovań ku˚nˇ, • kurˇa´k cigaret Lucky Strike pije pomerancˇovy´ dzˇus, • Japonec kourˇi cigarety Parliaments, • Nor zˇije vedle modre´ho domu. Ota´zky znı´: Kdo pije vodu? A kdo vlastnı´ zebru?

4.1.2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

Modelovy´ soubor

set HOUSE := { 1..5 }; set COLOR := { "blue", "green", "ivory", "red", "yellow" }; set NATIONALITY := { "Englishman", "Japanese", "Norwegian", "Spaniard", "Ukrainian" }; set DRINK := { "coffee", "milk", "orange_juice", "tea", "water" }; set SMOKE := { "Chesterfield", "Kools", "Lucky_Strike", "Old_Gold", "Parliament" }; set PET := { "dog", "fox", "horse", "snails", "zebra" }; var color{HOUSE, COLOR}, binary; c1{h in HOUSE}: sum{c in COLOR} color[h,c] = 1; c2{c in COLOR}: sum{h in HOUSE} color[h,c] = 1; var nationality{HOUSE, NATIONALITY}, binary; n1{h in HOUSE}: sum{n in NATIONALITY} nationality[h,n] = 1; n2{n in NATIONALITY}: sum{h in HOUSE} nationality[h,n] = 1; var drink{HOUSE, DRINK}, binary; d1{h in HOUSE}: sum{d in DRINK} drink[h,d] = 1; d2{d in DRINK}: sum{h in HOUSE} drink[h,d] = 1; var smoke{HOUSE, SMOKE}, binary; s1{h in HOUSE}: sum{s in SMOKE} smoke[h,s] = 1; s2{s in SMOKE}: sum{h in HOUSE} smoke[h,s] = 1; var pet{HOUSE, PET}, binary; p1{h in HOUSE}: sum{p in PET} pet[h,p] = 1; p2{p in PET}: sum{h in HOUSE} pet[h,p] = 1; f2{h in HOUSE}: nationality[h,"Englishman"] = color[h,"red"]; f3{h in HOUSE}: nationality[h,"Spaniard"] = pet[h,"dog"]; f4{h in HOUSE}: drink[h,"coffee"] = color[h,"green"];

25

Kapitola 4. Dalsˇ´ı prˇ´ıklady 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91

f5{h in HOUSE}: nationality[h,"Ukrainian"] = drink[h,"tea"]; f6{h in HOUSE}: color[h,"green"] = if h = 1 then 0 else color[h-1,"ivory"]; f7{h in HOUSE}: smoke[h,"Old_Gold"] = pet[h,"snails"]; f8{h in HOUSE}: smoke[h,"Kools"] = color[h,"yellow"]; f9: drink[3,"milk"] = 1; f10: nationality[1,"Norwegian"] = 1; f11{h in HOUSE}: (1 - smoke[h,"Chesterfield"]) + (if h = 1 then 0 else pet[h-1,"fox"]) + (if h = 5 then 0 else pet[h+1,"fox"]) >= 1; f12{h in HOUSE}: (1 - smoke[h,"Kools"]) + (if h = 1 then 0 else pet[h-1,"horse"]) + (if h = 5 then 0 else pet[h+1,"horse"]) >= 1; f13{h in HOUSE}: smoke[h,"Lucky_Strike"] = drink[h,"orange_juice"]; f14{h in HOUSE}: nationality[h,"Japanese"] = smoke[h,"Parliament"]; f15{h in HOUSE}: (1 - nationality[h,"Norwegian"]) + (if h = 1 then 0 else color[h-1,"blue"]) + (if h = 5 then 0 else color[h+1,"blue"]) >= 1; solve; printf "\n"; printf "------------------------------------------------------------\n"; printf "HOUSE COLOR NATIONALITY DRINK SMOKE PET\n"; for {h in HOUSE} { printf "%5d", h; printf{c in COLOR: color[h,c]} " %-6s", c; printf{n in NATIONALITY: nationality[h,n]} " %-11s", n; printf{d in DRINK: drink[h,d]} " %-12s", d; printf{s in SMOKE: smoke[h,s]} " %-12s", s; printf{p in PET: pet[h,p]} " %-6s", p; printf "\n"; } printf "-------------------------------------------------------------\n"; printf "\n"; end;

26


27

Popis modelove´ho souboru Na zacˇa´tku modelu definujeme postupneˇ 6 mnozˇin. Prvnı´ je mnozˇina HOUSE, ktera´ obsahuje cˇ´ısla od 1 do 5 (rˇa´dek 1). Rˇa´dek 3 definuje mnozˇinu COLOR, ktera´ obsahuje vsˇech 5 mozˇnyćh barev, ktere´ mohou jednotlive´ domy mı´t (modra´, zelena´, slonovinova´, cˇervena´, zˇluta´). Obdobneˇ jsou na na´sledujıćıćh rˇa´dcıćh definovańy mnozˇiny NATIONALITY (na´rodnost), DRINK (co kdo pije), SMOKE (jake´ cigarety kourˇ´ı) a PET (jake´ zvı´rˇe chova´). Jednotlive´ prvky teˇchto mnozˇin je mozˇne´ vycˇ´ıst ze zadańı´. ˇ a´dek 15 definuje promeˇnnou color, jako bina´rnı´ promeˇnnou, ktera´ naby´va´ hodnoty R 1, pokud du˚m h z mnozˇiny HOUSE ma´ danou barvu c z mnozˇiny COLOR. Pokud du˚m h ma´ jinou barvu nezˇ c, naby´va´ promeˇnna´ hodnoty 0. Pokud by tedy byl naprˇ´ıklad trˇetı´ du˚m modry´, bude hodnota promeˇnne´ color{3,blue} rovna 1 a hodnota color{3,green} bude rovna 0. Podmıńka c1 na rˇa´dku 16 rˇ´ıka´, zˇe kazˇdy´ du˚m ma´ pra´veˇ jednu barvu. Obdobneˇ podmıńka c2 na rˇa´dku 17 rˇ´ıka´, zˇe kazˇda´ barva musı´ by´t pouzˇita pra´veˇ jednou. Analogicky jsou definovańy promeˇnne´ a podmıńky na rˇa´dıćh 19 azˇ 33.

Dalsˇ´ı zna´me´ informace: Vı´me, zˇe Anglicˇan zˇije v cˇervene´m domeˇ. Tento fakt je zapsań na rˇa´dku 35. Tento rˇa´dek rˇ´ıka´: pra´veˇ tehdy, kdyzˇ v domeˇ h zˇije Anglicˇan, pak je tento du˚m cˇerveny´. Tı´mto zpu˚sobem je zapsańa veˇtsˇina zna´myćh informacı´. Trosˇku jiny´ je za´pis 5. bodu: zeleny´ du˚m je hned napravo od slonovinove´ho. Tento bod je zapsań na rˇa´dcıćh 43 a 44. Tyto rˇa´dky rˇ´ıkajı´ zˇe kdyzˇ je h-ty´ du˚m zeleny´, tak platı´ dveˇ mozˇnosti (rozdeˇlenı´ pomocı´ funkce if). Pokud by zeleny´m domem byl du˚m prvnı´, nemohl by lezˇet napravo od slonovinove´ho, proto tuto mozˇnost vylucˇujeme. Pro vsˇechny ostatnı´ cˇ´ısla domu˚ pak platı´, zˇe kdyzˇ je h-ty´ du˚m zeleny´, h-1. du˚m je slonovinovy´. ˇ a´dek 50 zapisuje informaci, zˇe v prostrˇednı´m domeˇ (tedy ve 3. domeˇ) je pito mle´ko. R ˇ a´dek 52 analogicky rˇ´ıka´, zˇe v prvnı´m domeˇ zˇije osoba norske´ na´rodnosti. R Na rˇa´dcıćh 54 azˇ 57 je zapsańa informace, zˇe muzˇ, ktery´ kourˇ´ı Chesterfieldky, zˇije v domeˇ vedle muzˇe, ktery´ chova´ lisˇku. Tento za´pis obsahuje 3 promeˇnne´: • smoke[h,"Chesterfield"], • pet[h-1,"fox"], • pet[h+1,"fox"], ktere´ naby´vajı´ hodnot 1 nebo 0. Pokud je pravda, zˇe obyvatel n-te´ho domu kourˇ´ı Chesterfieldky (smoke[h,"Chesterfield"]=1), je vy´sledek 55. rˇa´dku 0. Potom musı´ platit jeden ze dvou na´sledujıćıćh rˇa´dku˚, aby soucˇet teˇchto rˇa´dku˚ byl vysˇsˇ´ı nebo roven jedne´ (je zrˇejme´, zˇe platit nemu˚zˇou soucˇasneˇ, proto bude v tomto prˇ´ıpadeˇ vy´sledek roven jedne´). Pokud obyvatel h-te´ho domu nebude kourˇit tyto cigarety (vy´sledek 55. rˇa´dku je 1) mu˚zˇe ale nemusı´ by´t pravdivy´ jeden z na´sledujıćıćh rˇa´dku˚ a celkovy´ soucˇet hodnot pak bude veˇtsˇ´ı nebo roven 1. Vy´sˇe popsane´ rˇa´dky ko´du zahrnujı´ vsˇechny typy informacı´, ktere´ o obyvatelıćh jednotlivyćh domu˚ ma´me, proto popis ostatnıćh rˇa´dku˚ nebudu uva´deˇt.


28

Prˇ´ıkaz solve na 73. rˇa´dku vyrˇesˇ´ı dany´ proble´m. Za zmıńku stojı´ fakt, zˇe v tomto ´ loha ma´ totizˇ jedine´ prˇ´ıpustne´ rˇesˇenı´. prˇ´ıpadeˇ nepotrˇebujeme zˇa´dnou ućˇelovou funkci. U Prˇ´ıkaz printf na rˇa´dcıćh 75 - 88 slouzˇ´ı k forma´tovańı´ vy´stupu a pro pochopenı´ u´lohy jej nenı´ potrˇebne´ rozebı´rat.

ˇ esˇenı´ R Po spusˇteˇnı´ vy´pocˇtu (Tools/Go) dojdeme k rˇesˇenı´, ktere´ je zobrazeno formou tabulky: ----------------------------------------------------------------HOUSE COLOR NATIONALITY DRINK SMOKE PET 1 yellow Norwegian water Kools fox 2 blue Ukrainian tea Chesterfield horse 3 red Englishman milk Old_Gold snails 4 ivory Spaniard orange_juice Lucky_Strike dog 5 green Japanese coffee Parliament zebra -----------------------------------------------------------------

Z vy´stupu tedy plynou odpoveˇdi na obeˇ ota´zky: Vodu pije Nor a zebru chova´ Japonec.

4.2

Dieta

Proble´mem spra´vne´ kombinace slozˇek potravy se lide´ zaby´vajı´ uzˇ dlouhou dobu. Zna´my´m proble´m se v minulosti zaby´val i George Stigler. Stiglerova dieta2 je optimalizacˇnı´ proble´m, rˇesˇitelny´ pomocı´ GUSEKu.

4.2.1

Zadańı´

Tento proble´m je v podstateˇ pouze rozsˇ´ırˇenou variantou uzˇ zmıńeˇne´ho smeˇsˇovacı´ho proble´mu. Ma´me 9 ru˚znyćh zˇivin, pro ktere´ zna´me jejich doporucˇenou dennı´ spotrˇebu. Zˇiviny Energie Bı´lkoviny Va´pnı´k Zˇelezo Vitamıń A Vitamıń B1 Vitamıń B2 Vitamıń B3 Vitamıń C

Doporucˇena´ dennı´ da´vka 3000 kaloriı´ 70 gramu˚ 0,8 gramu˚ 12 miligramu˚ 5000 IU 1,8 miligramu˚ 2,7 miligramu˚ 18 miligramu˚ 75 miligramu˚

Da´le ma´me tabulku, ktera´ obsahuje informace o obsahu jenotlivyćh zˇivin a ceneˇ pro prˇiblizˇneˇ 80 druhu˚ potravin (z prostorovyćh du˚vodu˚ na tomto mı´steˇ tabulku nebudu uva´deˇt). Chceme zjistit, prˇi jak velke´ spotrˇebeˇ kteryćh potravin, budeme prˇijı´mat nejmeńeˇ doporucˇenou dennı´ da´vku kazˇde´ zˇiviny, prˇi co nejnizˇsˇ´ı celkove´ ceneˇ. 2 Prˇ´ıklad

je prˇevzat a upraven z [9].


4.2.2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

29

Modelovy´ soubor

set C; set N; param data{c in C, {"price", "weight"} union N}; param allowance{n in N}; var x{c in C}, >= 0; s.t. nb{n in N}: sum{c in C} data[c,n] * x[c] >= allowance[n]; minimize cost: sum{c in C} x[c]; solve; param days := 365.25; param commodity{c in C}, symbolic; param unit{c in C}, symbolic; printf "\n"; printf "MINIMUM COST ANNUAL DIET\n"; printf "\n"; printf " Commodity Unit Quantity Cost \n"; printf "------------------------- ---------- ---------- ----------\n"; printf{c in C: x[c] != 0} "%-25s %10s %10.2f $%7.2f\n", commodity[c], unit[c], 100 * days * x[c] / data[c,"price"], days * x[c]; printf " -----------------\n"; printf " Total: $%7.2f\n", days * sum{c in C} x[c]; printf "\n"; end;

Popis modelove´ho souboru Na zacˇa´tku modelove´ho souboru definujeme dveˇ mnozˇiny (klıćˇove´ slovo set). Mnozˇinu C, jejı´mizˇ slozˇkami budou jednotlive´ potraviny (komodity) a mnozˇinu N, ktera´ bude obsahovat vsˇechny zˇiviny, jejichzˇ mnozˇstvı´ na´s zajı´ma´. Na rˇa´dku 6 definujeme parametr data (klıćˇove´ slovo je zde param). Je definovany´ pro vsˇechny prvky mnozˇiny C. Slozˇky tohoto parametru jsou price, weight a vsˇechny prvky mnozˇiny N (tedy vsˇechny druhy zˇivin). Funkce union sjednocuje prvky price a weight


30

se vsˇemi prvky mnozˇiny N. Pod parametr data tedy zapı´sˇeme v datove´m souboru vsˇechny potrˇebne´ informace o jednotlivyćh potravinaćh, ktere´ potrˇebujeme k vyrˇesˇenı´ modelu. Konkre´tnı´ hodnoty zapı´sˇeme azˇ v datove´ cˇa´sti, zde pouze poznamena´m, zˇe cena je vztazˇena´ k zakoupitelne´ jednotce (jedno balenı´ mouky, jeden pomerancˇ a podobneˇ), zatı´mco ostatnı´ u´daje v tabulce jsou vztazˇeny k 1$ vy´daju˚. To znamena´, zˇe naprˇ´ıklad u´daj ve sloupci weight uda´va´ mnozˇstvı´ potraviny, ktere´ mu˚zˇeme koupit za 1 $. Naproti tomu u´daj ve sloupecˇku price uda´va´ cenu jednoho balenı´ dane´ potraviny. ˇ a´dek 8 definuje parametr allowance pro kazˇdy´ prvek mnozˇiny N. Tento parametr R bude obsahovat minima´lnı´ dennı´ mnozˇstvı´ jednotlivyćh zˇivin. Promeˇnne´ v tomto modelu jsou pojmenovańy x[c] a rˇ´ıkajı´, kolik peneˇz utratı´me za kterou potravinu z mnozˇiny C. Omezenı´ tohoto modelu prˇedstavujı´ minima´lnı´ pozˇadovane´ dennı´ da´vky jednotlivyćh zˇivin. Toto je souhrnneˇ zapsańo na rˇa´dku 12: s.t. nb{n in N}: sum{c in C} data[c,n] * x[c] >= allowance[n] Klıćˇove´ slovo je zde stejneˇ jako u prˇedchozıćh prˇ´ıkladu˚ s.t. a omezenı´ je pojmenovańo nb. Pro kazˇdou zˇivinu z mnozˇiny N scˇ´ıta´me prˇes vsˇechny potraviny c vy´raz data[c,n] * x[c] kde x[c] je cena, kterou zaplatı´me celkoveˇ za potravinu c a data[c,n] je mnozˇstvı´ zˇiviny n v potravineˇ c, kterou koupı´me za 1 $. ´ cˇelova´ funkce je zapsańa na rˇa´dku 14 a rˇ´ıka´, zˇe chceme minimalizovat soucˇet cen, U ktere´ zaplatı´me za jednotlive´ potraviny. Parametry na rˇa´dcıćh 18 azˇ 22 (tedy days, commodity a unit) slouzˇ´ı pro forma´tovańı´ vy´stupu. Parametr days ovlivnˇuje mnozˇstvı´ potrˇebnyćh potravin v za´vislosti na tom, na jak dlouhou dobu tuto dietu plańujeme. Parametry commodity a unit slouzˇ´ı pouze k forma´lnı´ u´praveˇ vy´stupu. Vy´stup3 je forma´tovań na rˇa´dcıćh 24 azˇ 34.

4.2.3 1 2 3 4 5 6 7 ... ... 79 80 81 82 83

Datovy´ soubor

data; param : C : flour macaroni cereal

commodity "Wheat Flour (Enriched)" "Macaroni" "Wheat Cereal (Enriched)"

unit := "10 lb." "1 lb." "28 oz."

cornsirup molasses stawberry ;

"Corn Sirup" "Molasses" "Strawberry Preserve"

"24 oz." "18 oz." "1 lb."

3 Forma ´ tovańı´

vy´stupu se opeˇt nebudu zaby´vat, pro pochopenı´ prˇ´ıkladu to nenı´ podstatne´.

Kapitola 4. Dalsˇ´ı prˇ´ıklady 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ... ... 175 176 177 178 179 180 181 182 183 ... ... 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268

31

set N := calories protein calcium iron vitaminA thiamine riboflavin niacin ascorbicAcid ; param data : flour macaroni cereal

price 36.0 14.1 24.2

cornsirup molasses stawberry

13.7 13.6 20.5

: flour macaroni cereal

cornsirup molasses stawberry ;

weight calories protein 12600 44.7 1411 3217 11.6 418 3280 11.8 377

4996 3752 2213

14.7 9.0 6.4

vitaminA thiamine riboflavin .0 55.4 33.3 .0 3.2 1.9 .0 14.4 8.8

.0 .0 .2

param allowance := calories 3 protein 70 calcium .8 iron 12 vitaminA 5 thiamine 1.8 riboflavin 2.7 niacin 18 ascorbicAcid 75 ; end;

.0 1.9 .2

.0 7.5 .4

0 0 11

calcium 2.0 .7 14.4

.5 10.3 .4

niacin 441 68 114

5 146 3

iron := 365 54 175

74 244 7

ascorbicAcid := 0 0 0

0 0 0


32

Popis datove´ho souboru Datovy´ soubor je znacˇneˇ obsa´hly´, proto jej zde uvedu pouze ve zkraćene´ podobeˇ. Datovy´ soubor, jak jizˇ bylo zmıńeˇno v jednom z prˇedchozıćh prˇ´ıkladu˚, zacˇ´ına´ klıćˇovy´m slovem data; (rˇa´dek 2) a koncˇ´ı klıćˇovy´m slovem end; (rˇa´dek 267). V prvnı´ cˇa´sti souboru jsou definovańy parametry commodity a unit pro jednotlive´ prvky mnozˇiny C. Tyto parametry slouzˇ´ı pouze pro vytvorˇenı´ vy´stupu. Oba tyto parametry jsou typu symbolic, cozˇ znamena´ zˇe se mu˚zˇe jednat o libovolny´ text, uzavrˇeny´ v uvozovkaćh. Parametr commodity definuje pro kazˇdou potravinu jejı´ cely´ na´zev (na´zvy prvku˚ mnozˇiny C jsou pro jednoduchost zkracovańy). Parametr unit pak uda´va´ jednotku,4 ve ktere´ je ve vy´stupu uva´deˇno mnozˇstvı´ dane´ potraviny (jedna´ se tedy o velikost beˇzˇneˇ dostupne´ho balenı´ potraviny, ke ktere´ je vztazˇena´ i cena). Na rˇa´dku 84 zacˇ´ına´ definice mnozˇiny N. Jak jizˇ bylo zmıńeˇno drˇ´ıve, mnozˇina N obsahuje jako sve´ prvky vsˇechny zˇiviny, jejichzˇ mnozˇstvı´ chceme sledovat. Vyćˇet jednotlivyćh zˇivin zacˇ´ına´ za znakem (:=), ktery´ odeˇluje na´zev mnozˇiny od jejıćh prvku˚. Jednotlive´ prvky mnozˇiny mohou by´t (tak jako v uvedene´m prˇ´ıpadeˇ) napsańy do rˇa´dku˚ pod sebou, nebo mohou by´t zapsańy do jednoho rˇa´dku a oddeˇleny mezerami. Vyćˇet prvku˚ mnozˇiny musı´ by´t ukoncˇen strˇednı´kem (; - rˇa´dek 94). Definice parametru data zacˇ´ına´ na rˇa´dku 96. Vzhledem k pocˇtu slozˇek, ktere´ parametr data obsahuje, je tato jeho definice rozdeˇlena do dvou cˇa´stı´, prvnı´ zacˇ´ına´ na rˇa´dku 97 a druha´ na rˇa´dku 180. Na teˇchto rˇa´dcıćh jsou postupneˇ vyjmenovańy vsˇechny slozˇky parametru data, tak jak jsou definovańy v modelove´m souboru. Pro kazˇdou potravinu z mnozˇiny C jsou pak na dane´m rˇa´dku postupneˇ uvedeny konkre´tnı´ hodnoty. Naprˇ´ıklad pro mouku obsahujı´ rˇa´dky 98 a 181 tyto informace: • jedno balenı´ mouky stojı´ 36 centu˚ (sloupecˇek price), • hmotnost mouky v hodnoteˇ 1 $ je 12600 gramu˚ (sloupecˇek weight), • v tomto mnozˇstvı´ (koupitelne´m za 1 $) je pak: – 44700 kaloriı´ (calories), – 1411 gramu˚ bı´lkovin (protein), – 2 gramy va´pnı´ku (calcium), – 365 miligramu˚ zˇeleza (iron), – nulove´ mnozˇstvı´ vitamıńu A (vitaminA), – 55,4 miligramu˚ vitamıńu B1 (thiamine), – 33,3 miligramu˚ vitamıńu B2 (riboflavin), – 441 gramu˚ vitamıńu B3 (niacin), – nulove´ mnozˇstvı´ vitamıńu C (ascorbicAcid). Definice tohoto parametru je pak opeˇt ukoncˇeno strˇednı´kem na rˇa´dku 254. Poslednı´m parametrem, ktery´ je trˇeba nadefinovat, je minima´lnı´ dennı´ da´vka jednotlivyćh zˇivin. Toto je skryto pod parametrem allowance, ktery´ je definovań obdobny´m zpu˚sobem jako prˇedchozı´ parametry (rˇa´dek 256). 4V

prˇ´ıkladu jsou pouzˇity zkratky lb - libra, oz - unce.


33

ˇ esˇenı´ R Postup rˇesˇenı´ v GUSEKu uzˇ byl popsań vy´sˇe, proto zde uka´zˇu pouze vy´stup: MINIMUM COST ANNUAL DIET Commodity Unit Quantity Cost ------------------------- ---------- ---------- ---------Wheat Flour (Enriched) 10 lb. 29.95 $ 10.78 Liver (Beef) 1 lb. 2.58 $ 0.69 Cabbage 1 lb. 110.70 $ 4.10 Spinach 1 lb. 22.58 $ 1.83 Navy Beans, Dried 1 lb. 377.81 $ 22.29 ----------------Total: $ 39.69

Kde v prvnı´m sloupecˇku je na´zev dane´ potraviny, ve druhe´m jednotka, po jake´ se dana´ surovina kupuje (naprˇ´ıklad mouka – prvnı´ rˇa´dek – se tedy kupuje v desetilibrove´m balenı´), ve trˇetı´m sloupecˇku je mnozˇstvı´ takovyćhto balenı´ a v poslednı´m souhrnna´ cena, kterou zaplatı´me za danou potravinu.

Za´veˇr Cı´lem praće bylo, po kra´tke´m u´vodu do teorie linea´rnı´ho programovańı´ a strucˇne´m prˇehledu dostupne´ho software, demonstrovat pouzˇitı´ programu GUSEK pro rˇesˇenı´ u´loh linea´rnı´ho programovańı´. V textu praće bylo popsańo sˇest prˇ´ıkladu˚ vyuzˇitı´ programu. Po cˇtyrˇech typickyćh u´lohaćh (kapacitnı´ proble´m, smeˇsˇovacı´ proble´m, media selection problem a u´loha a optima´lnı´m deˇlenı´ materia´lu) na´sledovala u´loha, pro jejı´zˇ rˇesˇenı´ nenı´ pouzˇitı´ linea´rnı´ho programovańı´ zrˇejme´, kterou byla Einsteinova ha´danka. Poslednı´m prˇ´ıkladem byl Stigleru˚v vy´zˇivovy´ proble´m, na ktere´m byla demonstrovańa praće s rozsa´hlejsˇ´ım datovy´m souborem. U kazˇde´ z rˇesˇenyćh u´loh bylo popsańo jejich zadańı´, na´sledneˇ uka´zań a rozebrań zdrojovy´ ko´d v programu GUSEK. Postupneˇ byly demontrovańy vsˇechny mozˇne´ typy vstupnıćh souboru˚, se ktery´mi GUSEK umı´ pracovat.

– 34 –

Seznam pouzˇite´ literatury [1] BETTONI, Luiz M. M. GUSEK. [online]. [cit. 2013-05-17]. Dostupne´ z: http://gusek.sourceforge.net/gusek.html [2] COIN-OR. [online]. [cit. 2013-05-17]. Dostupne´ z: http://www.coin-or.org/ [3] GLPK/GMPL (MathProg). [online]. [cit. 2013-05-17]. http://en.wikibooks.org/wiki/GLPK/GMPL (MathProg)

Dostupne´

z:

[4] IBM Academic Initiative. [online]. [cit. 2013-05-17]. Dostupne´ z: http://www03.ibm.com/ibm/university/academic/pub/page/academic initiative [5] JABLONSKY´, Josef. Operacˇnı´ vy´zkum: kvantitativnı´ modely pro ekonomicke´ rozhodovańı´. 2. vyd. Praha: Professional Publishing, 2002, 323 s. ISBN 80-864-1942-8. ´ , Petra. Rˇesˇene´ u´lohy z linea´rnı´ho programovańı´. Brno, 2003. Baka[6] KAISAROVA la´rˇska´ praće. Masarykova univerzita. Prˇ´ırodoveˇdecka´ fakulta. Katedra matematiky. [7] KLAPKA, Jindrˇich. Metody operacˇnı´ho vy´zkumu. Vyd. 2. Brno: Vutium, 2001, iii, 165 s. ISBN 80-214-1839-7. ´ , Milada. Linea´rnı´ modely v prˇ´ıkladech. 1.vyd. Praha: Vysoka´ sˇkola eko[8] LAGOVA nomicka´, 2002, 273 s. ISBN 80-245-0456-1. [9] MathProg. [online]. [cit. 2013-05-26]. http://www3.nd.edu/ jeff/mathprog/mathprog.html

Dostupne´

z:

´ K, Tibor. GNU General Public License: Prˇeklad do cˇesˇtiny. [online]. [cit. 2013[10] PETA 05-17]. Dostupne´ z: http://www.gnugpl.cz/v3/ ´ a Milan VLACH. Linea´rne programovanie. 1. [11] PLESNI´K, Jań, Jitka DUPACˇOVA vyd. Bratislava: Alfa, 1990, 314 s. ISBN 80-050-0679-9. [12] SciTE: A free source code editor for Win32 and X. HIRSCHMAN, Jack. [online]. [cit. 2013-05-17]. Dostupne´ z: http://www.scintilla.org/SciTE.html [13] Software Survey: Linear Programming. FOURER, Robert. [online]. [cit. 201305-17]. Dostupne´ z: https://www.informs.org/ORMS-Today/Public-Articles/JuneVolume-38-Number-3/Software-Survey-Linear-Programming [14] SˇMARDA, Bohumil. Linea´rnı´ programovańı´. Praha: Sta´tnı´ pedagogicke´ nakladatelstvı´, 1983, 151 s. – 35 –

Seznam pouzˇite´ literatury

36

[15] The GNU Linear Programming Kit, Part 1: Introduction to near optimization. [online]. [cit. 2013-05-17]. Dostupne´ http://www.ibm.com/developerworks/linux/library/l-glpk1/

liz:

MASARYKOVA UNIVERZITA ÚSTAV MATEMATIKY A STATISTIKY

Recommend Documents