Treti prednaska z operacniho vyzkumu

Popis systemu, metoda CPM

Obsah

Popis systemu pomoci grafu.

Neformalni definice systemu
System je mnozina, ktera muze nabyvat ruznych stavu. Tyto stavy se mohou menit na zaklade urcitych pravidel.
Popis systemu pomoci grafu.
Vrcholy grafu odpovidaji stavum systemu, orientovane ohodnocene hrany prechodum mezi jednotlivymi stavy systemu.

Priklad analyzy systemu pomoci teorie grafu.

 Znama uloha o vlkovi, koze a zeli. Vesnican vede domu z trhu vlka, kozu a zeli. Musi prekonat pomoci lodky reku. Do lodky se krome nej vejde jen jedna dalsi vec (vlk, koza, zeli). Na jednom brehu nesmi zustat nehlidana koza a zeli, nebo vlk a koza. Reseni: System muze nabyvat 16ti ruznych stavu v zavislosti na tom, na kterem brehu se nachazi prevoznik (P), vlk (V), koza(K) a zeli (Z). Nasledujici tabulka udava jednotlive stavy -- vrcholy orientovaneho grafu (vzdy situaci na levem - vychozim a pravem - cilovem brehu), to, zda je stav povoleny a u povolenych vrcholu hrany vychazejici z daneho vrcholu (povolene prechody).
cislo levy breh pravy breh povoleno navazujici vrcholy
1. PVKZ -- + 9. 10. 11. 12.
2. PVK Z + 10. 13. 14.
3. PVZ K + 11. 13. 15.
4. PKZ V + 12. 14. 15.
5. PV KZ - 13. 16.
6. PK VZ + 14. 16.
7. PZ KV - 15. 16.
8. P VKZ - 16.
9. VKZ P - 1.
10. VK PZ - 1. 2.
11. VZ PK + 1. 3.
12. KZ PV - 1. 4.
13. V PKZ + 2. 3. 5.
14. K PVZ + 2. 4. 6.
15. Z PVK + 3. 4. 7.
16. -- PVK Z + 5. 6. 7. 8.
Najit nejrychlejsi zpusob prepravy pres reku nyni znamena najit nejkratsi cestu ve vyse uvedenem grafu popisujicim system z vrcholu 1. do vrcholu 16. Takovych nejkratsi cest je vice, napriklad 1. 11. 3. 13. 2. 14. 6. 16. Vsechny maji delku 8 vrcholu, pro prevezeni pres reku bude tedy potreba minimalne 7 prejezdu.

Prohledavani grafu

 Ukolem je pro zadany graf (V,E) a zadane ohodnoceni vrcholu zjistit, zda existuje vrchol s danym ohodnocenim a zda je dostupny z pocatecniho vrcholu grafu P po nejake ceste.
Prohledavani grafu do hloubky
U kazdeho vrcholu vyberu na zaklade nejakeho kriteria jedno pokracovani (napriklad hranu do vrcholu s nejmensim cislem. Pri dalsim postupu pak pokracuji z takto nalezeneho vrcholu tak dlouho, dokud prochazim vrcholy, kde jsem jeste nebyl. Pokud jiz zadna dalsi cesta neexistuje, vratim se o jeden vrchol zpet a zkousim dalsi hranu (backtracking). Prikladem muze byt prohledavani bludiste. U vyse uvedene ulohy (koza, vlk, zeli) by prohledavani do hloubky vedlo k tomuto postupu: 1. 9. 1. 10. 2. 13. 3. 11. 3. 15. 4. 12. 4. 14. 6. 16. nalezeno
Prohledavani grafu do sirky
V prvnim kroku najdu vsechy sousedy pocatecniho vrcholu. V dalsim kroku vsechny sousedy techto vrcholu a tak dale, dokud nenajdu cil, nebo neprohledam cely graf. Prikladem je algoritmus pro hledani nejkratsi cesty v grafu. U vyse uvedene ulohy (koza, vlk, zeli) by prohledavani do hloubky vedlo k tomuto postupu: 1. 9. 10. 11. 12. 3. 13. 15. 2. 5. 4. 7. 14. 6. 16. nalezeno

Metoda CPM

 Metodu CPM (critical path method, metoda kriticke cesty) pouziji pro popis postupu praci na nejakem souhrnem dile. Cely postup se sestava ze souhrnu dilcich cinnosti a jejich navaznosti (cinnost muze zacit tehdy az jina cinnost skonci). Vrcholy grafu budou tvorit jednotlive dilci cinnosti. Orientovane hrany vyjadruji povinne navaznosti jednotlivych cinnosti. Vrcholy jsou ohodnocene dobou trvani cinnosti. Prvnim krokem je nalezeni nejdelsi cesty z pocatecniho vrcholy do koncoveho vrcholu. Tato nejdelsi cesta je cesta kriticka, jakekoliv zdrzeni na ni zpusobi zdrzeni celeho projektu. Dale lze pro kazdou cinnost spocitat nejdrive mozny zacatek, nejdrive mozny konec, nejpozdeji pripustny zacatek, nejpozdeji pripustny konec a casovou rezervu.
Postup vypoctu

Priklad pouziti metody CPM.
(vareni burtgulase).
V tabulce jsou postupne jednotlive cinnosti, cinnosti ktere jim musi nutne predchazet a doba trvani (to jsou vstupni data). Dale nejdrive mozny zacatek, nejdrive mozny konec, nejpozdeji pripustny zacatek, nejpozdeji pripustny konec, casova rezerva a informace, zda cinnost lezi na kriticke ceste.
cislo cinnost predchozidoba trvani NMZ NMK NPZ NPK rezerva kriticka cesta
1. start --- 0 0 0 0 0 0 +
2. krajeni cibule 1. 10 0 10 10 20 10 -
3. krajeni salamu 1. 10 0 10 10 20 10 -
4. loupani brambor 1. 10 0 10 0 10 0 +
5. vareni brambor 4. 20 10 30 10 30 0 +
6. smazeni cibule a salamu 2. 3. 10 10 20 20 30 10 -
7. michani brambor, cibule a salamu 5. 6. 5 30 35 30 35 0 +
8. vyroba jisky 1. 5 0 5 30 35 30 -
9. zaverecne vareni smesi s jiskou 7. 8. 10 35 45 35 45 0 +
10. cil (jidlo) 9. 0 45 45 45 45 0 +
Cela priprava burtgulase bude tedy trvat minimalne 45 minut. Ostatni informace jsou zrejme z tabulky
Tuto stranku vytvoril Tomas Vanicek a jedna se o soucast prednasek ze Systemove analyzy a operacniho vyzkumu pro obor Inzenyrstvi zivotnioho prostredi Stavebni fakulty Ceskeho vysokeho uceni technickeho v Praze.