PEF ČZU
Modely teorie grafů, min.kostra, max.tok, CPM, MPM, PERT Okruhy SZB č. 5 Zdroje: Demel, J., Operační výzkum Jablonský J., Operační výzkum Šubrt, T., Langrová, P., Projektové řízení I. … a různá internetová všehochuť.
Tak jednoduše, jak jen je možné…
16.5.2009
Pojem grafu Pojem grafu je přirozeným prostředkem k vyjádření párových vztahů – tj. vztahů mezi dvojicemi. 1. 2. 3. 4.
Graf se skládá z vrcholů (množina V) a hran (množina E – edge). Hrana spojuje vždy dva vrcholy a je buď orientovaná anebo neorientovaná. U orientovaných hran rozlišujeme počáteční a koncový vrchol. Orientovaný graf má všechny hrany orientované (a opačně neorientovaný graf hrany neorientované). 5. Podgraf vznikne z grafu vynecháním nějakých hran a (nepovinně) uzlů.
Popis grafu Graf lze zobrazit a popisovat:
Graficky Množinově – jako dvojice Maticí sousednosti = čtvercová matice, jejíž řádky a sloupce odpovídají jednotlivým vrcholům a jejíž prvky nabývají hodnoty 1 (či více) v případě, že mezi vrcholy existuje hrana(y). Maticí incidence = matice, jejíž řádky odpovídají vrcholům a sloupce hranám a jejíž prvky jsou rovny 1, je-li uzel počátečním, a -1, je-li koncovým vrcholem hrany.
Obvyklé struktury a pojmy Základní struktury a pojmy grafu:
Les = graf, který nevytváří cyklus Strom = graf, který nevytváří cyklus a je souvislý. Kořenový strom = je orientovaný graf, v němž existuje vrchol r = kořen takový, že do kořene nevede žádná hrana, a do každého jiného vrcholu vede právě jedna hrana. Každý souvislý graf má tzv. faktor, který je stromem (kořenovým) – ten nazýváme kostrou grafu. Minimální je v grafu s ohodnocenými hranami taková kostra, která má nejmenší součet ohodnocení hran. Acyklický je orientovaný graf, který neobsahuje žádný cyklus a má: o alespoň jeden (počáteční) vrchol, do nějž nevede žádná hrana, o alespoň jeden (koncový) vrchol, z nějž nevede žádná hrana. Síť je acyklický graf s nezáporně ohodnocenými hranami.
2
Modelové problémy Nalezení minimální kostry grafu Pomocí tzv. hladového (též Kruskalova) algoritmu – viz matematika III: 1. Vezmeme vrcholy původního grafu a vytvoříme z nich tzv. diskrétní graf. 2. Seřadíme hrany grafu od nejlevnější po nejdražší. 3. Bereme hrany jednu po druhé a ty, které netvoří cyklus, přidáváme do grafu.
Nalezení stromu nejkratších cest K nalezení kořenového stromu nejkratších cest slouží Dijkstrův algoritmus – viz opět matematika III. (Není v zadání otázky, tak nepopisuji).
Maximální tok v síti Maximální tok v síti (např. dopravní, elektrická či datová; u vodovodní to není tak jednoduché, protože voda třeba do kopce moc neteče, viď Jirko:-)) zjistitíme pomocí Ford-Fulkersonova algoritmu: 1. Mějme graf s dvojím ohodnocením hran (průtok jedním a druhým směrem). 2. Najdeme libovolnou cestu ze vstupního do koncového uzlu sítě (s kladnými kapacitami hran). 3. Na nalezené cestě najdeme hranu s nejnižší kapacitou – označíme ji 𝛿. O hodnotu 𝛿 zvýšíme celkový tok sítí. 4. O 𝛿 snížíme na dané cestě kapacitu všech hran a zvýšíme kapacitu všech hran v opačném směru. 5. Goto 1 Pro důkaz správnosti: 6. Platí Ford-Fulkersonova věta, tj. „Maximální tok v síti je roven minimálnímu řezu sítí“. 7. Řez sítí je množina hran, bez nichž by síť už nebyla souvislá. 8. Minimální řez obsahuje jen ty hrany, jejichž celkové ohodnoceni je minimální.
3
Graf typu síť při řízení projektů Síťový graf je základním nástrojem pro časovou analýzu při řízení projektů. V projektovém řízení rozlišujeme síťové grafy typu: činnost na hraně
činnost v uzlu
událost v uzlu
Ve všech sítích a metodách budeme zpravidla hledat kritickou cestu. Jeto nejdelší logická posloupnost od počátečního ke koncovému uzlu v síti.
CPM (metoda kritické cesty) Metoda CPM je základní deterministickou metodou síťové analýzy v grafech činnost na hraně. Postup výpočtu: 1. Vypočteme Ti(0) uzlů – procházíme grafem a sčítáme „délky hran“, přičemž se uzly chovají jako konjunktivní svodné prvky (tj. „větší bere“). 2. Vypočteme Ti(1) uzlů – procházíme grafem zpět a doby trvání odčítáme, přičemž se uzly chovají jako disjunktivní (tj. preferujeme nejnižší hodnotu). Spojnice uzlů, kde se Ti(0) = Ti(1), vyznačíme jako kritickou cestu. 3. Vypočteme rozdíly: Ri = Ti(1) - Ti(0) nazýváme interferenční rezervou uzlu. Vyjadřuje možné prodloužení délky operace nebo posunu jejího počátku, aniž by se změnili parametry kritické cesty. U kritické cesty je tato rezerva pochopitelně nulová. Celková rezerva
Rijc = Tj1 - Ti0 - tij = možné prodloužení délky operace (doby trvání), nebo posunu jejího počátku, aniž by se změnily parametry kritické cesty
Volná rezerva
Rijv = Tj0 - Ti1 - tij = možnost posunu počátku, nebo prodloužení operace, aniž by se změnily časové hodnoty návazných operací
Nezávislá rezerva
Rijn = Tj0 - Tj1 - tij = možné prodloužení nebo posunu počátku, aniž by to ovlivnilo jakýkoli jiný časový údaj celé sítě
platí vztah
Rc ≥ R v ≥ Rn 4
MPM (metoda měření potenciálů v sítích) Je hlavním zástupcem metod sloužících k časové analýze grafů typu činnost na uzlu. MPM předpokládá, že činnosti jsou vzájemně provázány svými počátky a ohodnocení hrany spojující následující činnosti znázorňuje vzdálenost těchto počátků. Výhodou je možnost práce s intervalovým zadáním parametrů vazeb. Hrany – vazby jsou ohodnoceny tzv. potenciály, a to kladným potenciálem aij udávajícím minimální vzdálenost počátků dvou sousedních činností a záporným potenciálem bij, který udává vzdálenost počátků maximální. Zjednodušený postup výpočtu: 1. Stanoví se počátek projektu a vypočtou termíny nejdříve možných počátků všech činností s využitím kladných potenciálů. Provede se korekce termínů nejdříve možných počátků s využitím záporných potenciálů. 2. Zpětně se vypočtou termíny nejpozději přípustných počátků s kladnými potenciály a zkorigují se pomocí potenciálů záporných. 3. Nulový rozdíl nejpozději přípustného a nejdříve možného začátku indikuje činnosti ležící na kritické cestě.
Stochastický přístup – metoda PERT Jde o pravděpodobnostní rozšíření metody CPM. Ta předpokládá, že je osoba sestavující projekt schopna přesně odhadnout doby trvání jednotlivých operací. To je ale v praxi zřídka možné. Proto zavádíme její pravděpodobnostní rozšíření PERT. Výpočet probíhá totožně s CPM, pouze pracujeme se středními dobami trvání jednotlivých operací. Budiž: teij
- očekávaná délka trvání (resp. střední doba trvání operace) a
- optimistický časový odhad
m
- modální (střední) časový odhad
b
- pesimistický časový odhad
Vyjádříme:
𝑡𝑖𝑗𝑒 = 𝜇𝑖𝑗 =
𝑎 𝑖𝑗 +4𝑚 𝑖𝑗 +𝑏 𝑖𝑗 6
a
𝜎𝑖𝑗 =
𝑏 𝑖𝑗 −𝑎 𝑖𝑗 6
Doba trvání operací je spojitá náhodná veličina, jejíž pravděpodobnostní rozdělení není předem známé, lze jej však s úspěchem aproximovat β-rozdělením. Postup výpočtu: 1. Ohodnotíme hrany v grafu danými odhady a, m, b.
5
2. Vypočteme 𝑡𝑖𝑗𝑒 = 𝜇𝑖𝑗 =
𝑎 𝑖𝑗 +4𝑚 𝑖𝑗 +𝑏 𝑖𝑗 6
a 𝜎𝑖𝑗 =
𝑏 𝑖𝑗 −𝑎 𝑖𝑗 6
.
3. Vypočteme Ti(0) uzlů. 4. Vypočteme Ti(1) uzlů. Spojnice uzlů, kde se Ti(0) = Ti(1), vyznačíme jako kritickou cestu. -
Kritickou cestu = střední dobu trvání celého projektu označíme písmenem M
-
2 Skutečná doba trvání projektu je náhodná veličina, kde 𝜇𝐾𝐶 = 𝑀 a 𝜎𝐾𝐶 =
𝜎𝑖𝑗2
a kterou již můžeme aproximovat normálním rozdělením -
Tedy pravděpodobnost dokončení projektu v daném čase Ts vyjádříme pomocí vztahu 𝑧 =
-
𝑇𝑠 −𝑀 𝜎𝐾𝐶
Nebo analogicky čas dokončení projektu s danou pravděpodobností jako 𝑇𝑠 = 𝑀 + 𝑧𝑝 𝜎𝐾𝐶
5. Vypočteme rezervy Ri = Ti(1) - Ti(0). 6. Rozvrhneme operace v čase.
6
