MA2BP_PDM1 Diskrétní matematika 1
5. Plánování projektu
Lukáš Másilko
Středisko pro pomoc studentům se specifickými nároky
Masarykova univerzita
7. 11. 2017
7. 11. 2017 1/29
Program prezentace
□ Představení problému
Sestavení grafové reprezentace projektu
Nalezení kritické cesty
□ Použité zdroje
7. 11. 2017       2 / 29
Stavba domu
Stavební firma má za úkol postavit rodinný dům. Stavbyvedoucí dodal operačnímu manažerovi firmy tabulku, v níž uvedl seznam činností a dílčích úkolů včetně jejich návaznosti a doby, za jakou mohou být dokončeny.
✓
Úkolem manažera je naplánovat sled aktivit tak, aby mohl stanovit dobu, za kterou bude dům postaven. Zároveň má určit ty aktivity, které musí být zahájeny a dokončeny v konkrétních dnech, aby jejich zpoždění neznamenalo prodloužení doby stavby.
7. 11. 2017       3 / 29
Stavba domu - přehled činností
Činnost	Popis	Následuje po	Počet dní
A	Úprava místa	—	1
B	Převzetí materiálů a strojů	—	2
C	Vybagrování základů	A	1
D	Položení základů	C	2
E	Kanalizace a přípojka plynu	B, C	6
F	Hrubá stavba	D	10
G	Rozvod elektřiny	F	3
H	Položení podlah	G	1
1	Hrubá stavba střechy	F	1
J	Instalatérské práce	E, H	5
K	Pokrytí střechy	1	2
L	Vnější omítka	F, J	1
M	Instalace oken a dveří	F	2
N	Zednické práce	L, M	4
0	Izolace stěn a stropů	G, J	2
P	Vnitřní omítka	0	2
Q	Izolace střechy	1, P	1
R	Dokončení interiéru	P	7
S	Dokončení exteriéru	1, N	7
T	Úprava a úklid terénu	S	3
7. 11. 2017       4 / 29
Reprezentace pomocí orientovaného grafu
Projekt a jeho činnosti je možné reprezentovat pomocí ohodnoceného orientovaného grafu:
■ Hrany reprezentují aktivity (ohodnocení hran znamená počet dní spotřebovaných na provedení aktivity)
■ Vrcholy znamenají časové okamžiky, kdy některé činnosti končí a jiné začínají (vrcholy budeme číslovat)
7. 11. 2017       5 / 29
Reprezentace pomocí orientovaného grafu
Projekt a jeho činnosti je možné reprezentovat pomocí ohodnoceného orientovaného grafu:
■ Hrany reprezentují aktivity (ohodnocení hran znamená počet dní spotřebovaných na provedení aktivity)
■ Vrcholy znamenají časové okamžiky, kdy některé činnosti končí a jiné začínají (vrcholy budeme číslovat)
Je vhodné se držet následujících tří pravidel.
■ Pravidlo 1: Každá aktivita je reprezentována právě jednou hranou.
■ Pravidlo 2: Nejsou povoleny násobné hrany (žádné dvě aktivity nesmí mít stejný počáteční i koncový vrchol).
■ Pravidlo 3: Uspořádání hran a vrcholů respektuje návaznost činností, nepřidává žádné další podmínky navíc.
7. 11. 2017       5 / 29
Řešení situace nesplňující Pravidlo 2
Pravidlo 2: Nejsou povoleny násobné hrany - není povolena tato situace: B
7. 11. 2017       6 / 29
Řešení situace nesplňující Pravidlo 2
Pravidlo 2: Nejsou povoleny násobné hrany - není povolena tato situace: B
Řešení: přidáme pomocný vrchol a pomocnou (umělou) hranu, která má nulové ohodnocení. Máme čtyři možnosti, jak to provést, viz obrázek:
7. 11. 2017       6 / 29
Porušení Pravidla 3 - příklad
Fakta
□ činnost C následuje po dokončení A, B Q činnost E následuje po dokončení B jsou chybně reprezentována tímto grafem:
Vysvětlení: činnost E nemusí nutně začínat až v době, kdy končí činnost A.
7. 11. 2017       7 / 29
Porušení Pravidla 3 - příklad
Fakta
O činnost C následuje po dokončení A, B Q činnost E následuje po dokončení B jsou chybně reprezentována tímto grafem:
Vysvětlení: činnost E nemusí nutně začínat až v době, kdy končí činnost A. Řešení: přidání pomocného vrcholu a pomocné hrany:
A
B
□      g ► < -E ► < =
7. 11. 2017       7 / 29
Stavba domu a jej f reprezentace grafem
-*7- Činnost	Popis	Následuje po	Počet dní
A	Úprava místa	—	1
B	Převzetí materiálů a strojů	—	2
c	Vybagrování základů	A	1
D	Položení základů	c	2
a-
7. 11. 2017       8 / 29
Stavba domu a jej í reprezentace grafem (2)
-*7- Činnost	Popis	Nasleduje po	Počet dní
E	Kanalizace a přípojka plynu	B, C	6
□ i3i
Stavba domu a jej í reprezentace grafem (2)
-*7- Činnost	Popis	Nasleduje po	Počet dní
E	Kanalizace a přípojka plynu	B, C	6
□ 31
Stavba domu a jej í reprezentace grafem (3)
-*7- Činnost	Popis	Následuje po	Počet dní
F	Hrubá stavba	D	10
G	Rozvod elektriny	F	3
H	Položení podlah	G	1
1	Hrubá stavba střechy	F	1
□ i3i
Stavba domu a jej í reprezentace grafem (4)
Činnost	Popis	Následuje po	Počet dní
J	Instalatérské práce	E, H	5
□ [3
Stavba domu a jej í reprezentace grafem (4)
-*7- Činnost	Popis	Nasleduje po	Počet dní
J	Instalatérské práce	E, H	5
□       [S ► < -E ►
7. 11. 2017       11 / 29
Stavba domu a jej í reprezentace grafem (5)
-*7- Činnost	Popis	Následuje po	Počet dní
K	Pokrytí střechy	1	2
L	Vnější omítka	F, J	1
M	Instalace oken a dveří	F	2
7. 11. 2017       12 / 29
Stavba domu a jej í reprezentace grafem (5)
-*7- Činnost	Popis	Následuje po	Počet dní
K	Pokrytí střechy	1	2
L	Vnější omítka	F, J	1
M	Instalace oken a dveří	F	2
7. 11. 2017       12 / 29
Stavba domu a jej í reprezentace grafem (5)
-*7- Činnost	Popis	Následuje po	Počet dní
K	Pokrytí střechy	1	2
L	Vnější omítka	F, J	1
M	Instalace oken a dveří	F	2
7. 11. 2017       12 / 29
Stavba domu a jej í reprezentace grafem (5)
-*7- Činnost	Popis	Následuje po	Počet dní
K	Pokrytí střechy	1	2
L	Vnější omítka	F, J	1
M	Instalace oken a dveří	F	2
7. 11. 2017       12 / 29
Stavba domu a jej í reprezentace grafem (6)
-*7- Činnost	Popis	Nasleduje po	Počet dní
N	Zednické práce	L, M	4
□ i3i
Stavba domu a jej í reprezentace grafem (6)
Stavba domu a jej í reprezentace grafem (7)
7. 11. 2017       14 / 29
Stavba domu a jej í reprezentace grafem (7)
-*7- Činnost	Popis	Nasleduje po	Počet dní
0	Izolace stěn a stropů	G, J	2
□ 31
Stavba domu a jej í reprezentace grafem (8)
-*7- Činnost	Popis	Nasleduje po	Počet dní
P	Vnitřní omítka	0	2
□ i3i
Stavba domu a jej í reprezentace grafem (9)
-*7- Činnost	Popis	Nasleduje po	Počet dní
Q	Izolace střechy	1, P	1
R	Dokončení interiéru	P	7
S	Dokončení exteriéru	1, N	7
L /
K
©br*© ®
□     g ► < -E ► < =
7. 11. 2017       16 / 29
Stavba domu a jej í reprezentace grafem (9)
-*7- Činnost	Popis	Nasleduje po	Počet dní
Q	Izolace střechy	1, P	1
R	Dokončení interiéru	P	7
S	Dokončení exteriéru	1, N	7
£>JKE)
□ i3>
Stavba domu a jej í reprezentace grafem (9)
-*7- Činnost	Popis	Nasleduje po	Počet dní
Q	Izolace střechy	1, P	1
R	Dokončení interiéru	P	7
S	Dokončení exteriéru	1, N	7
□ i3i
Stavba domu a jej í reprezentace grafem (9)
-*7- Činnost	Popis	Nasleduje po	Počet dní
Q	Izolace střechy	1, P	1
R	Dokončení interiéru	P	7
s	Dokončení exteriéru	1, N	7
□ i3i
Stavba domu a jej í reprezentace grafem (9)
Činnost	Popis	Nasleduje po	Počet dní
Q	Izolace střechy	1, P	1
R	Dokončení interiéru	P	7
S	Dokončení exteriéru	1, N	7
7. 11. 2017       16 / 29
Stavba domu a jej í reprezentace grafem (10)
-*7- Činnost	Popis	Nasleduje po	Počet dní
T	Úprava a úklid terénu	S	3
7. 11. 2017       17 / 29
Příklad 1 k procvičení
Vytvořte síťový diagram popisující aktivity A, B, L a respektující jejich návaznost dle následujících vztahů:
□ A, B, C jsou počáteční aktivity projektu, mohou začít simultánně. H A, B předchází D.
El B předchází E, F, H.
□ F, C předchází G. H E, H předchází I, K.
□ C, D, F, J předchází K.
□ K předchází L.
□ I, G, L jsou závěrečné aktivity projektu.
7. 11. 2017       18 / 29
Příklad 1 k procvičení - řešení
7. 11. 2017       19 / 29
Kritická cesta
Hledání kritické cesty se skládá ze dvou fází:
□ Přímý chod - postupujeme od počátečního ke koncovému uzlu a pro každý vrchol / hledáme ES; (čas nejdřívějšího možného začátku), který poté vložíme do □.
B Zpětný chod - postupujeme od koncového k počátečnímu uzlu a pro každý vrchol j hledáme LCj (čas nejpozdějšího možného dokončení), který poté vložíme do A.
Platí:
■ ES0 = 0
■ ESj = max;{ES; + D,y} - díváme se na všechny vrcholy /, ze kterých vede hrana do uzlu j. Djj je ohodnocení hrany mezi vrcholy ij.
■ LCn = ESn, přičemž n je koncový uzel sítě.
■ LCj = mm j {LCj — D,y} - díváme se na všechny vrcholy j, do kterých vede hrana z uzlu /. Dn je ohodnocení hrany mezi vrcholy ij.
7. 11. 2017       20 / 29
Přímý chod
Mějme síť o sedmi vrcholech s počátečním uzlem 0 a koncovým uzlem 7.
7. 11. 2017       21 / 29
Přímý chod
ESq = 0, proto k vrcholu 0 nastavíme do □ číslo 0.
7. 11. 2017       21 / 29
Přímý chod
Hledáme ESi. K uzlu 1 vede cesta pouze z vrcholu 0, proto ESi = ES0 + Doi = 0 + 2 = 2.
7. 11. 2017       21 / 29
Přímý chod
Hledáme ES2. K uzlu 2 vede cesta pouze z vrcholu 0, proto
ES2 = ES0 + D02 = 0 + 3 = 3.
7. 11. 2017       21 / 29
Přímý chod
Hledáme ES3. K uzlu 3 vedou dvě cesty z vrcholů 1, 2. Platí
ESi + D13 = 2 + 2 = 4 ES2 + D23 = 3 + 3 = 6
Vybíráme maximum z obou hodnot, proto ES3 = 6.
A
A
Přímý chod
Hledáme ES4. K uzlu 4 vedou dvě cesty z vrcholů 2, 3. Platí
ES2 + D24 = 3 + 2 = 5 ES3 + D34 = 6 + 0 = 6
Vybíráme maximum z obou hodnot, proto ES4 = 6.
Přímý chod
Hledáme ES5. K uzlu 5 vedou dvě cesty z vrcholů 3, 4. Platí
ES3 + D35 = 6 + 3 = 9 £S4 + D45 = 6 + 7 = 13
Vybíráme maximum z obou hodnot, proto ES5 = 13.
Přímý chod
Hledáme ESq. K uzlu 6 vedou tři cesty z vrcholů 1, 4, 5. Platí
ESx + Di6 = 2 + 2 = 4 ES4 + D46 = 6 + 5 = 11
ES5 + D56 = 13 + 6 = 19
Vybíráme maximum ze všech hodnot, proto ESq = 19.
Zpětný chod
Zpětný chod zahajujeme nastavením koncového uzlu 6, do A vložíme stejnou hodnotu, jakou máme ve □.
7. 11. 2017       22 / 29
Zpětný chod
Hledáme lc5. Z uzlu 5 vede jedna cesta do koncového vrcholu 6, proto LC5 = LC6 - D56 = 19 - 6 = 13.
7. 11. 2017       22 / 29
Zpětný chod
Hledáme Z.C4. Z uzlu 4 vedou dvě cesty do vrcholů 5, 6. Platí
LCS - D45 = 13 - 7 = 6 LQ - D46 = 19 - 5 = 14
Vybíráme minimum z obou hodnot, proto LC4 = 6.
Zpětný chod
Hledáme LQ. Z uzlu 3 vedou dvě cesty do vrcholů 4, 5. Platí
LQ - D34 = 6 - 0 = 6 LQ - D35 = 13 - 3 = 10
Vybíráme minimum z obou hodnot, proto LQ = 6.
Zpětný chod
Hledáme LQ. Z uzlu 2 vedou dvě cesty do vrcholů 3, 4. Platí
LQ - D23 = 6 - 3 = 3 LQ - D24 = 6 - 2 = 4
Vybíráme minimum z obou hodnot, proto LQ = 3.
Zpětný chod
Hledáme LC\. Z uzlu 1 vedou dvě cesty do vrcholů 3, 6. Platí
LC3 - On = 6 - 2 = 4 LQ - Die = 19 - 2 = 17
Vybíráme minimum z obou hodnot, proto /.Ci = 4.
Zpětný chod
Hledáme LCq. Z uzlu 0 vedou dvě cesty do vrcholů 1, 2. Platí
LCX - Doi = 4 - 2 = 2 Z.C2 - D02 = 3 - 3 = 0
Vybíráme minimum z obou hodnot, proto LCq = 0.
Nalezení kritické cesty
Hrana        patří do kritické cesty, jestliže pro vrcholy i J platí tři následující podmínky:
□ ES; = LC; (čísla ve □ a A vrcholu / jsou stejná)
B ESj = LCj (čísla ve □ a A vrcholu j jsou stejná)
B ESj — ES; = LCj — LC; = D,y (odečteme-li čísla ve □ či A vrcholů j\/, pokaždé nám vyjde ohodnocení hrany (/,j).
7. 11. 2017       23 / 29
Nalezení kritické cesty
Hrana (/,j) patří do kritické cesty, jestliže pro vrcholy i J platí tři následující podmínky:
□ ES; = LC; (čísla ve □ a A vrcholu / jsou stejná)
B ESj = LCj (čísla ve □ a A vrcholu j jsou stejná)
B ESj — ES; = LCj — LC; — D,y (odečteme-li čísla ve □ či A vrcholů j,/, pokaždé nám vyjde ohodnocení hrany (ij).
Na následujícím obrázku jsou červeně vyznačeny hrany kritické cesty. Všimněte si například, že
■ hrana (1,2) není v kritické cestě, protože vrchol 1 nemá stejná čísla ve □, resp. A;
■ hrana (3,5) není v kritické cestě. Vrcholy 3,5 sice mají stejná čísla ve □ , resp. A, ale odečtením hodnot ve □ obou vrcholů dostáváme
13 — 6 = 7, což není ohodnocení hrany (3,5) (stejně tak pro hodnoty v A).
7. 11. 2017       23 / 29
Nalezení kritické cesty - výsledné řešení
7. 11. 2017       24 / 29
Příklad 2 k procvičení
7. 11. 2017       25 / 29
Příklad 2 k procvičení - řešení
7. 11. 2017       26 / 29
Příklad 3 k procvičení
Dva kamarádi si chtějí založit prodejnu ovoce a zeleniny. Naplánovali si jednotlivé aktivity vedoucí k založení obchodu a jejich návaznosti, viz následující tabulka:
Činnost	Popis	Následuje po	Počet týdnů
A	Výběr a nákup objektu	—	6
B	Zpracování projektu	A	4
c	Obsazení pozice manažera	A	3
D	Výběr personálu	B, C	3
E	Rekonstrukce a vybavení objektu	B	8
F	Skolení personálu	D	2
G	Výběr sortimentu zboží	B, C	2
H	Uzavření smluv s dodavateli	G	5
1	Nákup zboží	E, F, H	3
J	Reklama	H	2
Sestavte síťový diagram výše uvedených aktivit, který respektuje jejich návaznost. Následně najděte kritickou cestu v síti.
7. 11. 2017       27 / 29
Příklad 3 k procvičení - řešení
Síťový diagram zkonstruovaný dle tabulky na předchozím slajdu
4 ^ >■   <        > 4
7. 11. 2017       28 / 29
Příklad 3 k procvičení - řešení
Červeně vyznačená kritická cesta projektu:
A
7. 11. 2017       28 / 29
Použité zdroje
TAH A, Hamdy A. Operations Research. An Introduction. 4th edition. New York: Macmillan Publishing Company, 1989. ISBN 0-02-946750-0.
JABLONSKÝ, J. Modely operačního výzkumu I - Přednáška 5: CPM a PERT. [PPT prezentace]. VŠE v Praze, 2017. Dostupné z: https://webhosting.vse.cz/jablon/vyuka.htm.
7. 11. 2017       29 / 29