VYSOKÁ ŠKOLA EKONOMICKÁ V PRAZE FAKULTA INFORMATIKY A STATISTIKY
BAKALÁŘSKÁ PRÁCE
2009
Tereza Drechslerová
VYSOKÁ ŠKOLA EKONOMICKÁ V PRAZE FAKULTA INFORMATIKY A STATISTIKY Obor: Statistika a ekonometrie
Název bakalářské práce
Řešení vybraných úloh teorie grafů pomocí systému LINGO
Autor bakalářské práce: Vedoucí bakalářské práce:
Tereza Drechslerová prof. Ing. Josef Jablonský, CSc. 2
Prohlášení: Prohlašuji, že jsem bakalářskou práci na téma ,, Úlohy teorie grafů “ zpracovala samostatně. Veškerou použitou literaturu a další podkladové materiály uvádím v seznamu použité literatury. Tereza Drechslerová
Praha, 9.7.2009 3
Poděkování: Chtěla bych vřele poděkovat svému vedoucímu práce prof. Ing. Josefu Jablonskému, CSc. za velmi příjemnou spolupráci a za rady, které mi při psaní mé bakalářské práce poskytl. 4
OBSAH 1.
ÚVOD ............................................................................................................... 6
2.
HISTORIE TEORIE GRAFŮ ....................................................................... 7
3.
SYSTÉM LINGO ........................................................................................... 9
4.
ÚLOHA HLEDÁNÍ MIMINÁLNÍ KOSTRY .............................................. 11 Matematický model úlohy ............................................................................ 12 Příklad řešený systémem LINGO ................................................................. 12 Speciální algoritmus na optimalizaci v grafech ............................................ 14 Příklad řešený pomocí daného algoritmu ..................................................... 15
4.1 4.2 4.3 4.4 5.
ÚLOHA HLEDÁNÍ MAXIMÁLNÍHO TOKU .......................................... 16 5.1. Matematický model úlohy ............................................................................ 17 5.2 Příklad řešený systémem LINGO ................................................................. 17 5.3 Speciální algoritmus na optimalizaci v grafech ............................................. 20 5.4 Příklad řešený pomocí daného algoritmu ..................................................... 20
6.
NÁKLADOVĚ OCENĚNÉ TOKY .............................................................. 22 6.1 Matematický model úlohy ............................................................................ 22 6.2 Příklad řešený systémem LINGO ................................................................. 23 6.3 Speciální algoritmus na optimalizaci v grafech ............................................ 24 6.4 Příklad řešený pomocí daného algoritmu .................................................... 25
7.
METODA KRITICKÉ CESTY ................................................................... 26 7.1 Matematický model úlohy ............................................................................ 27 7.2 Příklad řešený systémem LINGO ................................................................. 28 7.3 Speciální algoritmus na optimalizaci v grafech ............................................ 30 7.4 Příklad řešený pomocí daného algoritmu ..................................................... 32
8.
ZÁVĚR ............................................................................................................ 33
9.
LITERATURA ................................................................................................ 34
5
1. ÚVOD
Vědeckou disciplinu, kterou nazýváme teorií grafů, tvoří soubor poznatků a metod, které vznikly především při zkoumání praktických úloh, které byly později doplněny a zobecněny. Kromě metod teorie grafů lze využít i metody celočíselného programování, pokud pro tyto úlohy nalezneme adekvátní matematické modely ve formě úlohy smíšeného celočíselného programování. Jde o klasické úlohy typu hledání maximálního nebo minimálního toku, úlohu hledání minimální kostry grafu, okružní úlohu, úlohu čínského listonoše a další. Některými z nich se zde budu blíže zabývat. Existuje řada způsobů jak úlohy teorie grafů řešit. V triviálních případech je možné tyto úlohy řešit ručně na základě určitých algoritmů a pravidel. V komplikovanějších případech se úlohy řeší pomocí modelovacích systémů, jako jsou například LINGO, LINDO, XA, MPL for Windows a další. Pro triviálnější úlohy lze také využít program Microsoft Excel. Cílem této práce je seznámení se základními typy úloh teorie grafů a s možnostmi jejich řešení. Do této práce jsem vybrala 4 základní typy úloh z oblasti teorie grafů, které jsou formulované jako úloha lineárního programování. Ke každému typu úlohy je připojen ukázkový příklad, který je jednak řešený pomocí systému LINGO a také na základě představených speciálních algoritmů pro optimalizaci v grafech. Druhá kapitola je věnována historickému vývoji úloh teorie grafů a stručnému vysvětlení základních pojmů. Ve třetí kapitole je krátce představen systém LINGO a jeho modelovací jazyk. Dále jsem si vybrala čtyři typy úloh teorie grafů, které jsou jednotlivě rozděleny do následujících čtyř kapitol. Konkrétně jsou to tyto typy úloh: hledání minimální kostry, hledání maximálního toku, nákladově oceněné toky a jako poslední metoda kritické cesty. K těmto jednotlivým typům úloh je zapsán matematický model úlohy, který je pro ilustraci doplněn jednoduchým příkladem vypočteným v systému LINGO a také pomocí představeného algoritmu.
6
2. HISTORICKÝ VÝVOJ TEORIE GRAFŮ Za zakladatele teorie grafů je považován Leonhard Euler (1707-1783), který roku 1736 publikoval řešení příkladu Sedmi mostů města Königsbergu, města Královce. Zadání úlohy znělo, zda je možné projít každým mostem ve městě právě jednou a vrátit se zpět do původního místa. Tuto situaci převedl Euler na graf tak, že si každý břeh představil jako vrchol a každý most použil jako hranu, která břehy spojuje. Matematicky dokázal, že úloha není řešitelná. Grafy pak zůstávaly přes sto let na okraji zájmu matematiků - vrátili se k nim až roku 1847 Gustav Kirchhoff (1824-1887 a roku 1857 Arthur Cayley (1821-1895). Ve druhé polovině 19. století se poprvé objevuje název graf v tom smyslu, jak jej chápeme dnes. Jako první tento pojem použil James Joseph Sylvester (1814-1897) v roce 1878. Nejznámější úlohou teorie grafů v 19. století byl problém čtyř barev - otázka zněla, zda je možné každou mapu obarvit pomocí čtyř barev tak, aby sousední státy měly různé barvy. Tato úloha byla kompletně vyřešena až roku 1976. Ve 20. století docházelo k velkému rozvoji teorie grafů. V roce 1926 publikoval Otakar Borůvka (1899-1995) svůj algoritmus pro nalezení minimální kostry. Tento problém měl praktický důvod, a to co nejvýhodnější výstavbu elektrických sítí. Vznik teorie grafů jako samostatné matematické disciplíny je možno počítat od roku 1936, kdy vyšla monografie D. Königa ,,Teorie konečných a nekonečných grafů”. Od té doby vyšla řada publikací, které dále prohlubují teorii anebo se zabývají nejrůznějšími aplikacemi teorie grafů v oblasti matematiky, informatiky, ekonomie, sociologie, chemie atd. Různost oblastí, v nichž je možné využití teorie grafů, je dána hlavně tím, že v řadě případů je znázornění pomocí grafu výhodné.
7
Grafy si můžeme představit jako zjednodušení reálného světa, kde studovaný problém znázorníme pomocí bodů a čar, které je spojují, a tím popisují vlastnosti. Takovým bodům pak v teorii grafů říkáme uzly. Čáry, které je spojují, nazýváme hrany grafu. Samotný graf G je definován jako dvojice dvou množin - vrcholů (V) a hran (E). Zkratky V a E pocházejí z angličtiny - vrcholy jsou anglicky VERTICES, hrany EDGES.
G = (V, E) Mezi další základní pojmy teorie grafů patří například pojem kostra grafu. ,,Kostra grafu G je faktor, který je stromem. Odstraněním hrany v grafu G, patřící nějakému cyklu, se nenaruší souvislost. Použijeme-li tuto proceduru dále na zbývající cykly, dokud nezůstane ani jeden cyklus, dostaneme strom, který spojuje všechny vrcholy původního grafu. Tento strom se nazývá kostra původního grafu.„„[3] Různé typy grafu jsou popsány následovně. Plochý graf je zobrazen v rovině tak, že žádné dvě hrany se nezkřižují. Konečný graf má konečný počet uzlů a hran. Orientovaný graf je tvořen orientovanými hranami, kterým je přiřazen určitý směr. Souvislý graf je takový graf, pro který platí, že pro všechny dvojice uzlů existuje alespoň jedna cesta, která je spojuje. Cesta je posloupnost hran v orientovaném grafu, ve kterém každá hrana vychází z uzlu, v němž končí předcházející. Pokud cesta začíná a končí ve stejném uzlu, potom se jedná o cyklus. Síť je konečný, souvislý, orientovaný, acyklický, hranově nebo uzlově ohodnocený graf, v němž existuje jeden počáteční uzel a jeden uzel koncový. Příkladem sítě je telefonní síť, rozvod plynu, kanalizace atd.
8
3. SYSTÉM LINGO Optimalizační systém LINGO je systém určený pro řešení širokého spektra optimalizačních úloh. Řeší úlohy lineárního, celočíselného a smíšeného celočíselného programování. Jeho velkou předností je pro uživatele způsob zadávání modelu. Popis modelu je velice podobný matematickému zápisu modelu. Systém LINGO řeší úlohu formulovanou jako textový soubor, který obsahuje matematický model zapsaný podle určitých pravidel a v určitém modelovacím jazyku. Řeší lineární i nelineární optimalizační úlohy a také soustavy lineárních i nelineárních rovnic. ,, Popis úlohy začíná slovem MODEL: a končí slovem END. Všechny popisy, rovnice, nerovnosti jsou ukončeny středníkem. Vlastní model tvoří nerovnosti, rovnice, účelová funkce a další podmínky. Proměnné jsou označovány jmény, která tvoří maximálně 32 znaků. Při tvorbě jména se nerozlišují velká a malá písmena.”[1] Komentáře v modelu se uvozují vykřičníkem. Všechno od vykřičníku do následujícího středníku je považováno za komentář. Dále jsou zde stručně představeny jednotlivé sekce modelovacího systému LINGO. Mezi ty nejzákladnější sekce, které jsou použity při tvorbě kódů daných úloh teorie grafů vypadají následovně.
MODEL:
SETS: Zde se nachází definice primitivních a odvozených množin ENDSETS Primitivní množina je charakterizována konečným počtem prvků a je přímo zadávána zadavatelem. Primitivní množina může být zapsána následovně: JMÉNO_MNOŽINY/prvky množiny/:atributy;
9
Odvozená množina je množina, jejíž počet prvků závisí přímo na počtu prvků primitivní množiny. Může to být buď podmnožina prvků primitivní množiny nebo kombinace všech prvků dvojice primitivních množin.Odvozenou množinu lze definovat například takto: JMÉNO_MNOŽINY(primitivní množiny):atributy;
DATA: Zadaná data do modelu nebo odkaz na jiný soubor kde se nachází a odkud se načítají. ENDDATA END
Samotný matematický model úlohy se nachází mezi sekcí SETS a DATA a není uvozen žádnými klíčovými slovy. Účelová funkce začíná klíčovým slovem MIN, resp. MAX, za kterým se nachází samotný zápis funkce.
10
4. ÚLOHA HLEDÁNÍ MINIMÁLNÍ KOSTRY Úloha optimálního spojení je formulována jako problém spojení n míst tak, aby všechna místa byla navzájem spojena a součet ohodnocení spojení všech míst byl minimální. Příkladem může být spojení obcí telefonním kabelem tak, aby bylo možné se dovolat z každé obce do každé a celková délka použitého kabelu byla minimální. Dalším příkladem může být plánování zimní údržby komunikací nebo vybudování železniční sítě mezi městy daného regionu tak, aby každá dvě města byla po železnici dosažitelná a přitom náklady na vybudování železniční sítě byly minimální. Hledání minimální kostry má smysl u ohodnocených grafů. ,,Mějme neorientovaný graf G = (V, E), který je hranově ohodnocený, tzn. každá hrana (𝑖, 𝑗) ∈ E je ohodnocena číslem cij (náklady na zřízení hrany). Uzly z množiny 𝑉 = 1,2, . . 𝑛 představují místa, mezi kterými musí existovat spojení vytvořené z hran. Pokud chceme zajistit spojení v grafu G s nejmenšími celkovými náklady, pak z grafu G odstraníme některé hrany tak, aby zbývající hrany zajistily spojení mezi uzly a jejich ocenění bylo minimální.”[1] Hledáme tedy množinu hran " 𝐸 ´ ⊂ 𝐸 ". Úloha spočívá v rozhodnutí, zda hranu 𝑖, 𝑗 ∈ 𝐸 vybereme do množiny E´, která tvoří tzv. minimální kostru grafu G. Každý vrchol 𝑖 ∈ 𝑉 musí být možno propojit hranami z E´s libovolným vrcholem z 𝑉.Proto musí ležet alespoň na jedné hraně z E´.Pro účely matematické formulace zavedeme orientaci hran tak, že vznikne kostra s kořenem v uzlu 1 s orientací, která směřuje do tohoto uzlu 1. Z každého uzlu v kostře E´existuje jednoznačně cesta do uzlu 1. Proto opatříme touto orientací všechny hrany ležící na této cestě. Tím je jednoznačně určena orientace kostry E, a E´se stává orientovaným stromem s kořenem v uzlu 1. Protože vrchol 1 je kořen, nevychází z vrcholu 1 žádná hrana. Dále je třeba zajistit souvislost grafu. Všechny vrcholy kromě vrcholu 1 jsou zdroji produktu, vrchol 1 je naopak koncový vrchol, kam všechny toky ze všech uzlů směřují.
11
4.1 Matematický model úlohy Matematický model úlohy hledání minimální kostry grafu vypadá následovně:
Minimalizovat 𝑛 𝑖=1
𝑛 𝑗 =1 𝑐 ijxij,
(4.1)
za podmínek 𝑗 = 2,3, … 𝑛,
(4.2)
pro 𝑖 = 2,3, … 𝑛,
(4.3)
𝑖 = 2,3, … 𝑛,
(4.4)
0 ≤ 𝑦ij≤ 𝑛 − 1 𝑥 ij
𝑖, 𝑗 = 1,2, … 𝑛,
(4.5)
𝑥ij∈ 0,1
𝑖, 𝑗 = 1,2, … 𝑛.
x1j = 0
pro
𝑛 𝑗 =1 𝑥 ij
= 1
𝑛 𝑗 =1 𝑦ij
–
𝑛 𝑗 =2 𝑦ji
= 1
pro
kde :
cij jsou náklady na zřízení hrany (i,j),
xij je bivalentní proměnná, xij = 1 pro hranu (i,j), která je prvkem množiny E´, xij = 0 pro hranu (i,j), která není prvkem množiny E´,
yij je tok na každé hraně (i,j) ∈ E. Rovnice (4.1) je účelová funkce, která minimalizuje celkové náklady na zřízení
hrany. Ostatní rovnice jsou omezujícími podmínkami. Podmínka(4.2) se týká vrcholu 1, který je kořenem a nevychází z něj žádná hrana, proto musí být rovno nule. Podmínka (4.3) naopak zobrazuje ostatní uzle a říká, že musí existovat právě jedna cesta do kořene, resp. hrana vycházející z libovolného uzlu i. Každý vrchol 𝑖 ∈ 2,3, … , 𝑛 je zdrojem velikosti 1, podmínka (4.4) ukazuje bilanci toku do tohoto uzlu a toku z tohoto uzlu. Omezení ve tvaru (4.5) zabraňuje toku hranou (i,j), která není prvkem E´,platí pro ni xij = 0. Naopak pokud tok yij > 0, pak je nutné hranu (i,j) do množiny E´zařadit a proměnná xij = 1.
12
4.2 Příklad řešený systémem LINGO Obrázek 4.6 se skládá z pěti uzlů a deseti hran. Našim úkolem je najít minimální kostru tohoto grafu. Při řešení příkladu pomocí daného speciálního algoritmu se budu odkazovat na stejné zadání jako je na tomto obrázku.
2
1
2
5 8
8
4
7 9
5 4
1 3
3 4
Obr. 4.6: Minimální kostra grafu Zápis modelu hledání minimální kostry grafu v systému LINGO je zobrazen na obrázku 4.7.
Obrázek 4.7: Zápis v systému LINGO
13
Na obrázku 4.8 jsou vidět hrany, které tvoří minimální kostru grafu. Jsou to hrany, kde xij = 1, jak jsme si definovali již u zápisu matematického modelu. Minimální kostru tedy tvoří hrany (2,1) , (3,2) , (4,3) a (5,4). Součet ohodnocení těchto hran je roven číslu 10.
Obr. 4.8: Řešení v systému LINGO
4.3 Speciální algoritmus na optimalizaci v grafu Existují různé typy algoritmů pro řešení těchto typů úloh. Já jsem si vybrala pouze jeden z nich pro ilustraci tohoto příkladu. Tento algoritmus se skládá ze tří kroků, které jsou zde popsány. Krok 1. Vybereme z původního grafu dvě hrany s minimálním ohodnocením a zařadíme je do výsledné kostry. Krok 2. Vybíráme další hrany s minimálním ohodnocením, které netvoří s dříve vybranými cyklus. Krok 3. Podle kroku dva pokračujeme až do vybrání 𝑛 − 1 hran.
14
Tento algoritmus vychází z faktu, že výsledná vytvořená kostra K výchozího grafu G musí mít 𝑛 − 1 hran a kostra nemůže obsahovat cyklus. Je vhodné uspořádat všechny hrany do neklesající posloupnosti od hrany s nejmenším ohodnocením až po hranu s nejvyšším ohodnocením. Dále musíme sledovat, aby nevznikl nějaký cyklus mezi vybranými hranami.
4.4 Příklad řešený pomocí daného algoritmu Zadání příkladu je stejné jako na obrázku 4.6, který jsme řešili pomocí systému LINGO. Nejdříve se uspořádají hrany do neklesající posloupnosti podle jejich ohodnocení. Toto uspořádání je zobrazeno na obrázku 4.9. Poté je už vybírání hran, které tvoří minimální kostru grafu, snadné a přehledné. i 2 1 3 4 1 1 2 2 1 3
j
cij
3 2 4 5 4 3 4 5 5 5
1 2 3 4 4 5 7 8 8 9
Obr. 5.9: Uspořádání hran do neklesající posloupnosti Graf má 5 uzlů, musíme tedy vybrat 4 hrany, které tvoří minimální kostru grafu. Vybrané hrany a jejich ohodnocení je vyznačeno modrou barvou na obrázku 4.9. Vytvořená kostra se tedy skládá z vyznačených hran a její ohodnocení je dáno součtem ohodnocení vybraných hran. V tomto příkladě se rovná číslu 10. Když se podíváme zpět na řešení, které jsme dostali pomocí systému LINGO a které je zobrazeno na obrázku 4.8, je vidět, že se nám výsledky shodují.
15
5. ÚLOHA HLEDÁNÍ MAXIMÁLNÍHO TOKU
Úloha hledání maximálního toku je jednou z typických úloh teorie grafů. ,, Mějme orientovaný graf 𝐺 = 𝑉, 𝐸 , 𝑉 je množina uzlů 𝑉 = 1,2, … , 𝑛 a 𝐸 množina orientovaných hran. Uzel 1 označuje zdroj, uzel 𝑛 místo určení toku. Ostatní uzly představují místa, kterými tok pouze prochází. Hrana 𝑖, 𝑗 ∈ 𝐸 představuje ropovod, elektrické vedení, komunikační vedení, plynovod. Tato hrana má určitou kapacitu 𝑘ij , což je maximální množství produktu, které je možno hranou 𝑖, 𝑗 transportovat.”[1] Objem všech toků, které vycházejí z uzlu 𝑢i je přicházejí do uzlu 𝑢i je analogicky
𝑗
𝑗
𝑥 ij a objem všech toků, které
𝑥ji .
Množství produktu, které se transportuje hranou 𝑖, 𝑗 , označíme jako 𝑥ij a musí platit 0 ≤ 𝑥 ij ≤ 𝑘 ij . Produkt je transportován z uzlu 1 do uzlu 𝑛 , ostatní uzly 2,3, … , 𝑛 − 1 jsou uzly, ve kterých se produkt ani neshromažďuje ani nejsou zdrojem produktu. Dále musí platit, že množství produktu, které je do tohoto uzlu dopraveno, musí být rovno množství produktu, které je z tohoto uzlu transportováno. Cílem je zjistit celkovou maximální kapacitu sítě 𝑇 , tj. kolik jednotek lze za jednotku času přepravit ze zdroje do cílového místa tak, aby byly respektovány omezené propustnosti hran. Protože žádný produkt není v hranách ani v ostatních uzlech přidáván, ale ani tam nezůstává, musí být celkový produkt, který je dopraven do uzlu 𝑛 , roven množství produktu opouštějící uzel 1. Toto číslo nazveme velikostí toku grafem a budeme jej maximalizovat.
16
5.1 Matematický model úlohy Matematický model popisované úlohy je definován následovně:
maximalizovat z=
𝑛 𝑗 =1 𝑥 1j,
(5.1)
za podmínek 𝑛 𝑗 =1 𝑥 ij
=
𝑛 𝑗 =1 𝑥 ji
0 ≤ 𝑥ij ≤ 𝑘ij
𝑝𝑟𝑜 𝑖 ≠ 1, 𝑖 ≠ 𝑛,
(5.2)
𝑖, 𝑗 = 1,2, … , 𝑛.
(5.3)
kde :
kij značí kapacitu hrany (i,j), nebo – li maximální propustnost hrany (i,j)
xij značí objem toku po hraně (i,j). Rovnice (5.1) je účelová funkce, která maximalizuje objem všech toků, které
opouštějí uzel u1. Cílem je nalézt objem maximálního toku, tj. kolik jednotek lze za jednotku času přepravit ze zdroje do cílového místa bez porušení omezených propustností hran. Podmínka (5.2) říká, že součet všech toků, které přijdou do uzlu ui , se musí rovnat součtu všech toků, které z tohoto uzlu odejdou. Poslední podmínka (5.3) značí, že objem toku po hraně (i,j) musí být větší nebo roven nule a zároveň musí být menší nebo roven kapacitě hrany (i,j).
5.2 Příklad řešený systémem LINGO Na níže uvedeném obrázku 5.4 je jednoduchá síť se sedmi uzly a 11 hranami. U každé hrany je uvedená její propustnost. Cílem je nalézt objem maximálního toku, který lze danou sítí přepravit.
17
7
7 5
2 0
5 4
T
8
5
8
4 5
1
T
5
0
5 3
3
7 2
10
0
8 2 7
7
4
10 6
Obr.5.4: Maximální tok sítí
Zápis daného typu úlohy dle uvedeného matematického modelu (5.1), (5.2), (5.3) je v systému LINGO zobrazen na obrázku 5.5. Zkratka X značí tok a zkratka KAP vyjadřuje kapacitu hrany.
Obrázek 5.5: Zápis v systému LINGO
18
Hodnota ,,objective value“ obsahuje informaci o hodnotě účelové funkce. Objem maximálního toku uvedenou sítí je tedy 15 jednotek. Hodnoty toků (X) po jednotlivých hranách jsou jako výstup z optimalizačního systému LINGO uvedeny na obrázku 5.6.
Obrázek 5.6: Řešení v programu LINGO V grafické podobě jsou stejné informace uvedeny také na obrázku 5.7. Grafická podoba je vhodná z hlediska přehlednosti, proto jsem ji zde také uvedla. Jsou zde přesně vidět hodnoty toků po jednotlivých hranách.
7 5
2 7 3 4 15
5
5
5
1
15
3 3
7 2
10
5 4
6
Obr. 5.7: Maximální tok sítí – optimální řešení
19
5.3 Speciální algoritmus na optimalizaci v grafu Jelikož jsem si zvolila jako příklad plochý graf, tak zde představím algoritmus pro ploché grafy, abych ho mohla také uplatnit na zadaném příkladě. Krok 1. Nalezneme horní cestu mezi vstupem a výstupem sítě. Tuto cestu tvoří hrany , které sestavujeme od vstupního uzlu tak , že z každého uzlu na cestě zvolíme tu hranu, která je první nalevo od hrany, kterou jsme se do uzlu už dostali. Tato horní cesta má tu vlastnost, že všechny zbývající hrany a uzly leží uvnitř plochy v rovině. Pokud tato cesta neexistuje, algoritmus končí. Celkový tok sítí je roven součtu propustností jednotlivých nalezených cest mezi vstupem a výstupem. Krok 2. Určíme propustnost horní cesty 𝑘(𝐶), jakožto minimální zbytkovou kapacitu na této cestě. Dále na nalezené cestě odstraníme hrany s minimální kapacitou hrany a ostatním hranám na této cestě snížíme kapacity o tuto minimální hodnotu. Přejdeme zpátky na krok 1 a opakujeme to samé do doby, kdy algoritmus končí.
5.4 Příklad řešený pomocí daného algoritmu Níže uvedený obrázek 5.8 se skládá ze 7 uzlů označených písmeny a 12 – ti hran. Úkolem je najít maximální tok mezi uzly C a E. Uzel C je výchozí uzel, který je zdrojem a uzel E je cílovým místem, do kterého se mají jednotky přepravit.
1
A 4 2 5
C
F
3
6
D
E
2 1
G
6 B
4
5
Obr. 5.8: Maximální tok sítí
20
10
Podle uvedeného algoritmu je řešen příklad 5.8. Pro přehlednost a orientaci je zapsán jak postup tak i grafické řešení. 1) Cesta C – A – F – E
,+1
2) Cesta C – A – D – F – E
,+2
3) Cesta C – D – F – E
,+1
4) Cesta C – D – G – E
,+2
5) Cesta C – D – B – G – E
;+1
6) Cesta C – B – G – E
;+4
Další cesta mezi vstupem a výstupem již neexistuje. Dosažený maximální tok 𝑋max = 11 a je vyjádřen na Obr. 5.9 a 5.10.
+1 +1+2
+2 +2+1
+2+1+1+2+1
+1+2+1
+1+1+2
+1+2+1+2+1+4 +2 +1
+4
+2+1+4
+1+4
Obr.5.9: Maximální tok sítí – optimální řešení
1 3
2 3
11
4
4
11 2 1
4
7
5
Obr. 5.10: Maximální tok sítí – optimální řešení
21
6. NÁKLADOVĚ OCENĚNÉ TOKY Zatím jsem se zabývala pouze toky sítí bez nákladů na průchod sítí. Pokud zavedeme na každé hraně 𝑖, 𝑗 jednotkový náklad 𝑐 ij na přesun jednotky toku, dostáváme nákladově oceněné toky. Na hraně 𝑖, 𝑗 vznikají náklady dané součinem jednotkových nákladů a velikosti toku 𝑐ij𝑥ij a celkové náklady na síti jsou součtem 𝑐ij𝑥ij .Na takové síti mohu definovat úlohy toku
nákladů na všech hranách
s minimálními náklady. Písmeno 𝑇 označuje celkovou výši toku, kterou chceme přepravit od uzlu 1 do uzlu 𝑛 .Úloha pak může spočívat v minimalizaci celkových nákladů na tuto přepravu.
6.1 Matematický model úlohy Matematický model úlohy při zadané velikosti celkového rozpočtu C∗ a hledání maximálního toku sítí X vypadá takto.
maximalizovat 𝑖=1
𝑥1j = X
(6.1)
za podmínek O ≤ 𝑥ij ≤ 𝑘ij,
(6.2)
𝑐ij𝑥ij ≤ C∗ ,
(6.3)
𝑗
𝑥ij =
𝑗 =1 𝑥 ij
𝑗
𝑥ji ,
pro i ≠ 1 i≠ n,
= 0,
(6.4) (6.5)
kde:
cij jsou jednotkové náklady,
xij je velikost toku,
C∗ značí velikost celkového rozpočtu, který je zadaný,
X je tok sítí,
kij je kapacita hrany.
22
Rovnice (6.1) je účelová funkce, která maximalizuje tok X. Podmínka (6.2) říká, že velikost toku xij musí být větší nebo rovný nule a zároveň musí být menší nebo rovný kapacitě hrany (i,j). Další podmínka (6.3) se týká zadané velikosti celkového rozpočtu C∗.Součet nákladů na všech hranách musí být menší než zadaná hodnota celkového rozpočtu. Podmínka (6.4) říká, že součet všech toků, které přijdou do uzlu ui , se musí rovnat součtu všech toků, které z tohoto uzlu odejdou. Poslední podmínka (6.5) říká, že výpočet začíná s nulovou hodnotou pro tok X.
6.2 Příklad řešený systémem LINGO Na obrázku 6.6 je zadána síť s hodnotami kij , cij a velikostí celkového rozpočtu C∗ = 37. Úkolem je nalézt maximální tok sítí X při zadané velikosti C∗ .
2
3, 5
2, 3 1
2, 4
5
1, 6
4, 3
3, 2 3
4 4, 2
Obr. 6.6: Nákladově oceněné toky Zápis dané úlohy na základě matematického modelu (6.1), (6.2), (6.3), (6.4), (6.5) je zobrazen na obrázku 6.7
Obrázek 6.7: Zápis v systému LINGO
23
Na obrázku 6.8 je zobrazeno optimální řešení daného příkladu. První cesta vede přes hrany (1,2) a (2.5) a velikost toku je 2. Druhá cesta vede přes hrany (1.3), (3.4) a (4.5) a velikost toku je zde 3. Po sečtení je tedy nalezený tok maximální X = 5 při zadaných nákladech C∗ = 37.
Obrázek 6.8: Řešení v systému LINGO
6.3 Speciální algoritmus na optimalizaci v grafu Pro řešení tohoto typu úloh existují dva různé algoritmy. Vybrala jsem si jeden z nich, který zde popíši a ilustruji na zadaném příkladě. Algoritmus, který jsem si vybrala, je založen na postupném hledání nejkratších cest na síti vzhledem k modifikovaným nákladům 𝑐´ij. Délka této cesty určuje jednotkové náklady pro propuštění jednotkového toku na této cestě. Propustnost je dána minimem zbytkových kapacit hran této cesty a po této cestě je možno zvýšit tok o hodnotu 𝑥 = min( 𝑘ij − 𝑥ij ).
Krok 1. Vyjdeme z výchozích hodnot 𝑋 = 0 , 𝐶 = 0 . V tomto případě platí 𝑐´ij = 𝑐 ij .
24
Krok 2. Vzhledem k hodnotám 𝑐´ij hledáme nejkratší cestu na síti a po této cestě zvýšíme tok o hodnotu 𝑥 = min( 𝑘ij − 𝑥ij ). Přepočteme průběžné hodnoty 𝑋 a 𝐶 .Dále přepočteme modifikované náklady 𝑐´ij a zbytkové kapacity hran kij − 𝑥ij . Krok 3. Pokud platí, že 𝐶 = 𝐶 ∗ nebo 𝑋 = 𝑋 ∗ , algoritmus končí nalezením optimálního řešení. V ostatních případech přejdeme zpět na krok 2.
6.4 Příklad řešený pomocí daného algoritmu Zadání grafu je stejné jako při řešení systémem LINGO a je zobrazeno na obrázku 6.6. Pomocí uvedeného algoritmu a jednotlivých kroků hledáme postupně nejkratší cesty vzhledem k hodnotám c´ij (v tomto případě jsou c´ij = cij ). První cesta vede přes uzly ( 1 – 3 – 4 – 5 ) a její délka je rovna 3 + 2 + 2 = 7. Druhá cesta vede přes uzly ( 1 – 2 – 5 ) a její délka je rovna 3 + 5 = 8. Nyní se průběžné náklady C rovnají celkovému zadanému rozpočtu C∗, tudíž algoritmus končí nalezením optimálního řešení. Výsledky jsou zahrnuty v tabulce 6.9, kde je vidět, že nalezený tok je maximální X = 5 při minimálních nákladech 37.
CESTA
TOK
NÁKLAD
X
C
1. 2.
3 2
7 8
3 5
21 37
Tabulka 6.9: Optimální řešení
25
7. METODA KRITICKÉ CESTY Metoda kritické cesty vznikla z anglického spojení Critical Path Method, ve zkratce CPM. Metoda CPM je jednou z nejširších a nejznámějších metod síťové analýzy, která vznikla v USA. Jejím cílem je stanovení doby trvání projektu na základě délky tzv., kritické cesty. Tato metoda slouží jako nástroj pro odhad nákladů. Používá se například ve stavebním průmyslu, kde lze doby trvání projektu odhadnout s vysokou přesností. Doby trvání pro činnosti projektu jsou známy většinou podle minulých zkušeností z předešlého projektu. Kritická cesta je definována jako nejdelší možná cesta z počátečního bodu do koncového bodu grafu. Každý projekt má minimálně jednu kritickou cestu. Každá kritická cesta se skládá ze seznamu činností, na které by se měl manažer projektu nejvíce zaměřit. Datum dokončení posledního úkolu na kritické cestě je také datem dokončení projektu. Pro úplnost zde uvedu zákony kritické cesty.
Zpoždění úkolu na kritické cestě se promítá do zpoždění projektu jako celku.
Zrychlení prací na úkolu ležícím na kritické cestě zkracuje trvání projektu jako celku.
Díky prvním dvěma aspektům lze rozlišit prioritu úkolů.
Výpočet kritické cesty může být proveden ručně nebo s použitím software. Časovou rezervou (rezervní dobou) nazýváme takový časový interval, o který můžeme posunout ukončení práce nebo práci prodloužit, aniž by se změnila celková doba dokončení projektu. Celkové rezervy budou na některých hranách grafu rovny nule, tyto hrany se nazývají kritické hrany. Tyto kritické hrany tvoří kritickou cestu mezi vstupem a výstupem sítě.
26
7.1 Matematický model úlohy Matematický model úlohy hledání kritické cesty může být definován následovně:.
minimalizovat z=
i,j tij𝑥 ij
(7.1)
za podmínek Dj = max (Di +tij),
j = 2,3,..,n.
(7.2)
Pi = min (Pj – tij),
i = 1,2,..,n-1.
(7.3)
RCij = Pj – Di - tij,
(7.4)
xij ≥ 1 - M∗RCij,
(7.5)
xij∈ 0,1
i,j = 1,2,..,n.
(7.6)
D(1) = 0,
(7.7)
LUZEL = n,
(7.8)
P (LUZEL) = D (LUZEL),
(7.9)
Kde:
xij je bivalentní proměnná, xij = 1 pro hranu (i,j), která je součástí kritické cesty, xij = 0 pro hranu (i,j), která není součástí kritické cesty,
tij značí dobu trvání činnosti,
Dj značí nejdříve možný začátek činností, které vycházejí z uzlu j,
Pi značí nejpozději možný začátek činností, které vycházejí z uzlu i,
RCij značí časové rezervy na hraně (i,j),
M je označení pro dostatečně velké kladné číslo. Zajišťuje, že pro činnosti s kladnou časovou rezervou je hodnota proměnné xij rovna nule, s nulovou časovou rezervou je rovna 1,
LUZEL značí číslo posledního uzlu, Rovnice (7.1) je účelová funkce, která minimalizuje celkovou dobu trvání, například daného projektu.
27
Podmínka (7.2) říká, že nejdříve možný začátek činností vycházejících z uzlu (j) je maximum ze součtu nejdříve možného začátku činností přicházejících do uzlu (i) a dob trvání těchto činností (i,j). Podmínka (7.3) naopak říká, že nejpozději možný začátek činností, které přicházejí do uzlu (i) je minimum z rozdílu nejpozději možného začátku činností, které přicházejí do uzlu (j) a dob trvání těchto činností (i,j). Podmínka (7.4) se týká celkových časových rezerv na jednotlivých hranách. Říká, že celková rezerva na hraně (i,j) se vypočítá tak, že od nejpozději možného začátku činností přicházejících do uzlu (j) se odečte nejdříve možný začátek činnosti vycházejících z uzlu (i) a doba trvání dané činnosti (i,j). Podmínka (7.5) značí, že když je časová rezerva rovna nule, tak bivalentní proměnná je rovna jedné. Podmínka (7.6) zobrazuje bivalentní proměnnou xij, která nabývá hodnot pouze nula jedna. Podmínka (7.7) znázorňuje fakt, že nejdříve možný začátek uzlu jedna je roven nule. Podmínka (7.8) nás informuje o celkovém počtu uzlů. Poslední podmínka (7.9) říká, že nejpozději přípustné konce činností se musí rovnat nejdříve možným začátkům činností v konečném uzlu grafu. Hodnota účelové funkce nemusí vždy představovat délku kritické cesty. (V případě, že kritická cesta je alternativní ). Délka kritické cesty je vždy dána hodnotou nejpozději přípustného konce konečného uzlu.
7.2 Příklad řešený systémem LINGO Na obrázku 7.10 je zobrazeno zadání následujícího příkladu. Cílem je zjistit celkovou délku kritické cesty a nejdříve možný termín dokončení daného projektu. 2 4
4
7
1 2
3
2
5
1
3
4 3
6
2
Obrázek 7.10: Metoda kritické cesty 28
Zápis modelu hledání kritické cesty je sestaven na základě matematického modelu (7.1), (7.2), (7.3), (7.4), (7.5), (7.6), (7.7), (7.8), (7.9) a nachází se na obrázku 7.11.
Obrázek 7.11: Zápis v systému LINGO
Na obrázku 7.12 je zobrazeno řešení, které ukazuje následující výsledky. Nejdříve možný termín dokončení dané úlohy je devět jednotek. Zkratka RC pod sebou skrývá celkové časové rezervy. Kritickou cestu tvoří hrany, které mají časové rezervy rovny nule. Kritická cesta tedy vede přes uzly 1 – 3 – 6 – 7. Zkratka D značí nejdříve možné začátky činností a zkratka P značí nejpozději možné začátky činností. Tyto údaje jsou také zobrazeny na obrázku 7.12.
29
Obrázek 7.12: Řešení v systému LINGO
7.3 Speciální algoritmus na optimalizaci v grafu Základní vzorce:
𝒕ij doba trvání činnosti 𝑖, 𝑗
𝒕i(0) termín nejdříve možného začátku činnosti 𝑖, 𝑗
𝒕j(0) termín nejdříve možného konce činnosti 𝑖, 𝑗
𝒕i(1) termín nejpozději přípustného začátku činnosti 𝑖, 𝑗
𝒕j(1) termín nejpozději přípustného konce činnosti 𝑖, 𝑗
𝑻i(0) nejdříve možný termín uzlu 𝑖
𝑻i(1) nejpozději přípustný termín uzlu 𝑖
𝑻p plánovaná délka trvání projektu
𝑻n nejdříve možný termín dokončení celého projektu
Výpočet termínů probíhá ve dvou fázích, a to jako výpočet vpřed a výpočet vzad.
30
Výpočet vpřed Určíme nejdříve možný termín zahájení projektu
𝑡1(0) = 𝑇1(0) = 0
Určíme nejdříve možné konce činností
𝑡j(0) = 𝑡i(0) + 𝑡ij
Nejdříve možný termín realizace uzlu
𝑇j(0) = max 𝑡j(0)
Pro další činnosti určíme jejich nejdříve možné začátky
𝑡i(0) = 𝑇i(0)
Podle prvních tří vzorců postupně určujeme nejdříve možné termíny všech činností a uzlů. Výpočet vzad Určíme nejpozději přípustný konec projektu
𝑇n(1) = 𝑡n(1) = 𝑇n(0)
Nejpozději přípustné termíny dalších činností a uzlů určíme postupně podle vztahů: 𝑡i(1) = 𝑡j(1) – 𝑡ij 𝑇i(1) = min 𝑡i(1) 𝑡j(1) = 𝑇j(1)
Na základě těchto výpočtů můžeme stanovit celkové časové rezervy 𝑹𝑪ij pro všechny činnosti. 𝑅𝐶 ij = 𝑇j(1) – 𝑇i(0) – 𝑡ij = 𝑡j(1) – 𝑡i(0) – 𝑡ij Celkové rezervy budou na některých hranách grafu rovny nule a tyto hrany se nazývají kritické. Metoda CPM se dá vypočítat různými způsoby. Je to buď graficky, v tabulce nebo v matici. V mém případě ilustruji výpočet graficky, který se nachází na obrázku 7.8.
31
7.4 Příklad řešený pomocí daného algoritmu
Použiji stejné zadání příkladu jako na obrázku 7.10 pro snadné porovnání výsledků ze systému LINGA a ze samotného výpočtu pomocí daného algoritmu. Kritická cesta vede přes uzly 1 – 3 – 6 – 7 a je vyznačena červenou barvou. Každé zpoždění kritické činnosti má za následek prodloužení termínu dokončení například celého projektu. Nejdříve možný termín dokončení je v tomto příkladě roven devíti. Jak je opět vidět, grafické výsledky se shodují s výsledky v systému LINGO, což nám dává za pravdu, že průběh výpočtu je správný. Na následujícím obrázku 7.13 je zobrazeno grafické řešení pro tuto zadanou úlohu.
5 5
8
2 (1)
4 (1)
3 (3)
2 2
7
1 (3)
3
9
4 6
7
2 (1)
3 (0)
1 0 0 000 4 (0)
6 3 4
6
6
4 2 /0)
Obrázek 7.13: Optimální řešení pro CPM
32
9
8. ZÁVĚR Cílem této práce bylo představení základních typů úloh teorie grafů formulovaných jako úlohy lineárního programování a možné způsoby jejich řešení. Způsobů, jak tyto úlohy řešit, je nespočetně mnoho. Pro mou práci jsem si vybrala systém LINGO, ve kterém jsem řešila dané příklady, a na základě absolvování kurzu ,,Řízení projektů“ jsem zde představila speciální algoritmy na optimalizaci v grafu. Na začátku práce jsem Vás seznámila s historií teorie grafů a základními pojmy, které se pak dále vyskytovaly v textu. Část práce je dále věnována stručně popisu systému LINGO a sekci modelovacího systému LINGO. Dle toho si lze snadno udělat obrázek o tom, jak jsou dále konkrétní příklady tvořeny. Pro jednotlivé příklady je vždy formulován matematický model dané úlohy, který koresponduje se zápisem modelu v systému LINGO. Zbytek práce je rozdělen do 4 větších kapitol, ve kterých jsem se podrobněji věnovala těmto vybraným typům úloh teorie grafů: hledání minimální kostry, hledání maximálního toku, nákladově oceněné toky a metoda kritické cesty. Úlohy teorie grafů mají velké uplatnění v praxi, zejména v oblasti silniční a železniční dopravy.
33
9. LITERATURA Seznam použité literatury 1 Pelikán, J.: Diskrétní modely, VSE Praha 1999. 2 Jablonský, J.: Programy pro matematické modelování, Oeconomica,Praha 2007. 3 Fiala, P.: Řízení projektů, Oeconomica, Praha 2008.
Internetové zdroje: [4] www.lindo.com , (15.7.2009) [5] www.teorie-grafu.elfineer.cz , (15.7.2009) [6] www.kvic.cz , (18.7.2009) [7] www.eunet.cz , (20.7.2009)
34
