SW aplikace MOV přednášky Šubrt KOSA Systémová podpora projektů Teorie grafů Projektové řízení I, II zápočet: alespoň 21 bodů z průběžných testů 75% účast na cvičení obhajoba projektů v MS Project pef.czu.cz/kosa Témata 1. přednášky: 1. seznámení s osnovami 2. základní pojmy teorie grafů 3.1. základní algoritmy teorie grafů 3.2. maximální tok jako úloha LP 3.3.nejkratší a kritická cesta jako úloha LP Graf - G = (U, E)
U … množina vrcholů E … množina neuspořádaných dvojic prvků
Podgraf - H = (U´,E´), U´ ⊂ U, E´ ⊂ E Úplný podgraf - H = (U´, E´), U´=U, E´ ⊂ E Incidentní (sousední) vrcholy - vrcholy, mezi kterými existuje hrana Stupeň vrcholu - deg (Ui) - počet incidujících hran
∑ deg(U ) = 2∑ h(i, j ) i
Konečný graf - množiny U, E jsou konečné Nekonečný graf - množiny U, E jsou nekonečné Orientovaný graf -hrany jsou orientované, lze jim přiřadit směr Hranově ohodnocený graf - každé hraně přiřazeno alespoň jedno číslo Uzlově ohodnocený graf - každému uzlu přiřazeno alespoň jedno číslo Sled vrcholů - posloupnost uzlů U1, U2, … Un, kde pro každé Ui a Ui+1 existuje hrana {Ui, Ui+1} Uzavřený sled - sled, kde U1 = Un Řetěz (Cesta) - sled, ve kterém se každý vrchol vyskytuje právě jednou (pro všechna i ≠ j:Ui ≠ Uj) Kružnie - sled, ve kterém se každý vrchol U2, U3, … Un vyskytuje právě jednou Hamiltonovská kružnice - kružnice procházející všemi vrcholy grafu Rovinný graf - graf, který lze v rovině nakreslit rovinným způsobem (bez křížení hran) Souvislý graf - mezi každými dvěma vrcholy může být definován sled Orientovaný graf - G = (U, E) U … množina vrcholů E … množina uspořádaných dvojic prvků z U Koncentrický uzel - více hran v něm končí, než začíná -1-
Christy
SW aplikace MOV přednášky Excentrický uzel - více hran v něm začíná, než končí Cesta (orientovaná cesta) - orientovaný sled, ve kterém se každý vrchol vyskytuje právě jednou (pro všechna i≠j:Ui≠Uj) Hamiltonovská cesta - cesta procházející všemi vrcholy grafu Cyklus - orientovaný sled, ve kterém se každý vrchol U2, U3 … Un-1 vyskytuje právě jednou a U1 = Un)
Základní typy grafů: - graf typu STROM - souvislý graf neobsahující kružnici - mezi každými dvěma vrcholy právě jeden řetěz - n vrcholů n-1 hran - v každém souvislém grafu lze určit podgraf typu strom (kostru grafu) - v každém hranově ohodnoceném neorientovaném grafu existuje minimální kostra - minimální kostra - kostra s minimálním součtem ohodnocení hran - seřazení hran neklesajícím způsobem - postupná konstrukce podgrafu (zařazování hran) tak, aby nevznikla kružnice - graf typu SÍŤ - konečný - souvislý - orientovaný - acyklický - s jedním počátkem a jedním koncem
Maximální tok v síti
- ohodnoceny cenou cij - hledám nejlevnější propojení nějakých vrcholů - ohodnoceny kapacitou hij - hledáme maximální množství materiálu, kterém můžeme protlačit z jednoho uzlu do druhého - ohodnoceny vzdáleností dij - algoritmus nejkratší cesty v grafu - ohodnoceny dobou trvání tij - algoritmy na hledání kritické (nejdelší) cesty - každý graf je možné popsat soustavou lineárních rovnic xij
i
xjk
j hij
k hjk
xij=xjk -xij + xjk = 0 xij < hij xjk < hjk
−Z +
∑x
k∈R1
1k
=0
-2-
Christy
SW aplikace MOV přednášky
− ∑ xij + i∈Pj
∑x
k∈R j
jk
=0
j = 2, 3,… (n-1)
− ∑ xin + Z = 0 i∈Pn
xij ≥ 0, xij ≤ hij kromě i, j Z … max
7 4 Z
4
1
6 5
n
Z
3 9
Nejkratší cesta
- úloha bivalentního programování xij ∈ {0,1}
− ∑ xij + ∑ xjk = 0
j = 2, 3 … (n-1)
∑ xij = 1 ∑ xin = 1 Z = ∑∑ dij ⋅ xij... min Kritická cesta - omezující podmínky jsou stejné, bivalentnost je také stejná
Z = ∑∑ tij ⋅ xij... max
r Ax = b x3 ∈ {0,1} r dx... max aij ->0, 1, -1 bi -> 0, 1
Metoda CPM - „Critical Path Method“ - cílem nalezení kritické cesty v deterministickém grafu - konstanta je doba trvání úkolu - umožňuje kompletní časovou analýzu ukazatelů všech činností - probíhá v několika krocích: 1. Formalizace projektu do grafu - nesmí mít multigraf (mezi dvěma vrcholy dvě a více hran - vyřeší se doplněním fiktivní cesty
-3-
Christy
SW aplikace MOV přednášky a 4
a 4
3 b
b f
3
0 ) a musí být síť 10 F 11 - nelze odstranit nekonečnost 2. Očíslování uzlů - uzly na všech cestách musí být číslovány vzestupně - metoda přeškrtávání hran - Fordův algoritmus 3. Výpočet vpřed - výpočet nejdříve možných termínů 4. Výpočet vzad - výpočet nejpozději možných termínů 5. Stanovení kritické cesty 6. Výpočet rezerv 7. Výpočet lhůtových ukazatelů
Metoda přeškrtávání hran 1. Stanovení řádu uzlů - kolika hranami je vzdálen od počátku 2. Očíslování uzlů vzestupně podle řádů, přičemž v rámci stejného řádu je číslování libovolné 3. stanovení Ti0 4. stanovení Ti1 5. Stanovení kritické cesty
I 2 8
II
8
5
2 8
10
24
4
4
0 0
14
4 III
7
5 12
3
19
IV 8
1 19
20
5
20
8
3 3
24
7 II
1
9
5 12
6
0
V
6
5 7
8
12
I
II
uzel je řádu k pokud do něj vstupují nejvýše kx uzlů Ti0 - termín nejdříve možné realizace uzlů i Ti1 - termín nejpozději možné realizace uzlu i Uzel se realizuje tehdy, když se realizují všechny hrany, které do něj vstoupí
-4-
Christy
SW aplikace MOV přednášky konjunktivita vstupu determinovanost výstupu
Ti 0 = 0 T j0 = max i∈Pj (Ti 0 + t ij ) - nejdříve možná realizace posledního uzlu je 24 = délka kritické cesty
Ti1 = min j∈Ri (T j1 − t ij ) 4 typy rezerv: 1. celková rezerva činnosti - udává o kolik časových jednotek je možné zpozdit činnost oproti jejímu nejdříve možnému počátku resp. jí prodloužit aniž by došlo k prodloužení projektu
Rijc = T j1 − (Ti 0 + t ij ) R36c = 12 − (3 + 5) = 4 2. rezerva volná - udává o kolik časových jednotek je možné zpozdit činnost oproti jejímu nejdříve možnému počátku resp. jí prodloužit aniž by došlo ke zpoždění činnosti následující
Rijv = T j0 − (Ti 0 + t ij ) R36v = 8 − (3 + 5) = 0 3. rezerva nezávislá - o kolik časových jednotek, lze zpozdit činnosti oproti nejpozději možné realizaci výchozího uzlu aniž by došlo ke zpoždění uzlu následující - může být záporná
RijN = T j0 − (Ti1 + t ij ) 4. rezerva závislá - o kolik časových jednotek, lze zpozdit činnosti oproti nejpozději možné realizaci výchozího uzlu aniž by došlo k prodloužení projektu
RijZ = T j1 − (Ti1 + t ij ) t i0 - nejdříve možný počátek činnosti i, je roven Ti 0 t i1 - nejpozději přípustný začátek činnosti, je roven T j1 − t ij
t 0j - nejdříve možný konec činnosti i, je roven Ti 0 + t ij t 1j - nejpozději přípustný konec činnosti, je roven T j1 Metoda PERT - topologie grafu je známá - stochastické ohodnocení hran
aij
tij
bij
- mírně asymetrické, rozdělené - nejvhodnější rozdělení je β rozdělení
µ (t ij ) =
aij + 4mij + bij 6
-5-
Christy
SW aplikace MOV přednášky
bij − aij δ (t ij ) = 6 2
2
Uzlově definované grafy 1) výhody a nevýhody AON a AOA 2) vzájemné převody AON a AOA 3) Metoda MPM - uzlový graf umožňuje: - modelovat různé typy vazeb - intervalové zadání - snazší konstrukci 2
1
4
3
1 2
2 4
F1
F2
2 3
1 3 3 4 FS - činnost následující začíná nejdříve po skončení činnosti předcházející SS - činnost následující začíná nejdříve se začátkem činnosti předcházející FF - činnost následující končí nejdříve SF - činnost následující končí nejdříve se začátkem činnosti předcházející - každá tato činnost může mít prodlevu - -d nebo přesah +d např. SS + 50%, FS -50% AON -> AOA
i
1) FS
j
=>
i
2) SS
FF
i
j
i
SF
i
j j
B 6
j
SS
FS A 4
D 1 FS SS+10 C 2
-6-
Christy
SW aplikace MOV přednášky 6 B
0 0
4 A
0 1 D
10 0
0 0
2 C
Metoda MPM - (Metra Potential Method) - metoda měření potenciálu v sítích - 1958 ve Francii - Bernard Roy - nalezení kritické cesty v uzlově orientovaném grafu aij
i
bij
j
aij - potenciál vazby - minimální vzdálenost po sobě následujících činností bji - záporný potenciál - maximální vzdálenost po sobě následujících činností FS
aij = ti ti FS tj
SS FF
aij = 0 aij = ti - tj
SF
aij = -tj
a ij , bij a ij ≤ b ji
i ti 0 0Ti
0 1Ti
1 0Ti
1 1Ti
Postup: 1. formalizace problému do uzlového grafu 2. očíslování uzlů 3. výpočet termínů nejdříve možných počátků s využití kladných potenciálů
T =0,
0 0 0
T j0 = max( 0Ti 0 + aij )
0
4. korekce termínů nejdříve možných počátků s využitím záporných potenciálů 0´ 0 0
T
= max( 0Ti 0 , 0T j0 + bij ) -7-
Christy
SW aplikace MOV přednášky 5. výpočet nejdříve možných konců
T 0 = 0Ti 0 + t ,
Tn =1Tn0
1 i
6. výpočet termínů nejpozději možných počátků s využitím kladných potenciálů
T = 0Tn0 ,
1 0 n
T = min( 0T j1 − aij )
1 0 i
7. výpočet termínů nejpozději možných počátků s využitím záporných potenciálů
T j1´ = min( 0T j1 , 0Ti1 − bij )
0
8. výpočet nejpozději možných konců
T 1 = 0Ti1 + t i
1 i
9. kritická cesta
Ria = 0Ti1 − 0Ti 0
Riv = min( 0T j0 ) −( 0Ti 0 + aij ) -2 2 42
2
A 4 0 20
x
B 6
D 3
1 35 5
8 8
-2 E 2
x 5 4 4
7 12 7 C 2
4 4 10 5 max (4, 7, -5)
max (3, 7, -2) x x F 4 5 79 8 14 9 8 14 -2 G 1
x 1 9 9
8 13
5 FIKT x 0 12 14 14 14 14 1
9 14
2 6 7
-5
min (12, 5, -(-2))
Simulační model kritické cesty ve stochastických grafech - simulace je proces během něhož počítač napodobuje reálné situace - simulace: - fyzikální - matematická - nepřichází v úvahu bez počítače - modely:
- dynamické - většina - statické - náhodné číslo - je z intervalu 0 a 1 - rovnoměrné rozdělení - náhodná veličina - je charakterizována určitým pevně daným rozdělením pravděpodobnosti - základní stavební kámen ->prvek má vlastnosti kvalitativní a kvantitativní - nad každou ? je možné provést elementární operaci - simulační modely se zaznamenávají pomocí vývojových diagramů - terminál - operátor - bivalence - čítač (simulátor) - výstup
-8-
Christy
SW aplikace MOV přednášky Z
K=0 C=0 K=K+1 VK = f(VK) gen τK K, C C/K
C = C + τK +
K
K
K - diskrétní sumátor C - spojitý sumátor - celková doba trvání operace 30% 20% 50%
f(vk) g(vk) h(vk) K
K=0 Cf = 0
n = 1000 Cg = 0 Ch = 0 K=K+1
+ K
gen ξ +
+ ξ > 0,5
ξ > 0,2
VK = h(v) gen τK1 Ch = Ch + τh1
VK = f(v) gen τK2 Cf = Cf + τf1
VK = g(v) gen τK3 Cg = Cg + τg1
-9-
Christy
SW aplikace MOV přednášky F A
D
94,5 33
3,3
C 2,5
B 91
G 35
E 135
H 10,5
A Střední hodnota doby trvání Směrodatná odchylka doby trvání
B
C
3,3
91
0,117
8,5
Č. pokusu 1 2 …
E
F
135
94,5
35
0,25 1,187 11,67 3,833 Doby trvání dle pokusů
3,333
2,5
D 33
G
H 10,5 0,333 Délka cesty Délka cesty X-B-C-D-F-G-H X-B-C-E-H
% kritičnosti cesty Max doba trvání projektu Min doba trvání projektu
277,302 97,6
Doba trvání projektu
232,909 2,4
277 286,736 242,389
obr. skripta str. 94 prezentace na Commonu a webu - SWA P 0406
vk t = max ik ri vi = ∑ vik
k
zde chybí jedna přednáška
Microsoft Project Vyrovnání zdrojů - automaticky - nepoužívat! - ručně - přetížení hledat: minutu po minutě - zaškrtnout „před vyrovnáním vymazat hodnoty určené k vyrovnání“ - pořadí vyrovnání: standardní - vyrovnat pouze v rámci časové rezervy - kritické úkoly se řeší ručně, nekritické automaticky - vyrovnání může změnit jednotlivá přiřazení úkolu - zdroje nemusí spolupracovat (stroj a obsluha) - vyrovnání může rozdělit zbývající práci Sledování průběhu projektu - Tracking Progress - sledování skutečného průběhu s aktuálním plánem, respektive se směrným plánem - „skutečný“ | dokončeno % a dokončeno (k) - týká se rozpracovanosti jednotlivých úkolů - „zbývající“ - skluz (slippage) Neplést si!:
prodleva (lag) - parametr vazby zpoždění (delay) - rezerva zleva - souvisí se zdrojovou dostupností/nedostupností skluz (splippage) - o kolik projekt začal později než bylo plánované
- 10 -
Christy
SW aplikace MOV přednášky Princip sledování průběhu projektu - updating - aktualizace 1. aktualizace podle plánu (update as scheduled) - stavové datum (status date) 2. aktualizace podle skutečnosti a) aktuální plán lze dohnat b) přerozvržení (rescheduling) - skluz Vytvořená hodnota - earned value - BCWS - rozpočtové náklady plánovaných prací - BCWP - ACWP - skutečné náklady provedených prací SV - odchylka plánování = BCWP - BCWS = rozdíl v plánování vzniklý časovými skluzy CV - odchylka nákladů = BCWP - ACWP Multiprojektování 1) Projekt - subrojekty 2) paralelní komunikace projektů - externí vazba 3) sdílení zdrojových fondů
Matematické modelování v tabulkových procesorech a jeho sw podpora 1) podstata modelové tvorby v tabulkovém procesoru 2) typy modelů 3) modely vycházející z kubických matic 4) třídění tabulkových modelů tabulkový procesor 1) prvky - buňky 2) vazby - vzorce 3) chování - vlastní výpočet (schopnost výpočtu) model ... zjednodušený obsah reality typy modelů: - ikonické - fyzikální podstata - symbolické - podstata v symbolice (řeči symbolů) - verbální - matematické - tabulkové - nový typ modelů metasystém ... systém pomocí něhož definujeme systém (učit se učit) metamodel ... model formalizující modely jako takové Trojrozměrná jednostupňová dopravní úloha dodavatelé spotřebitelé dopraví prostř.
D1, D2, ... Dm S1, S2, ... Sn V1, V2, ... Vp
s požadavky s kapacitou
a1, a2, ... am b1, b2, ... bn d1, d2, ... dp
C = (cijk ) - náklady na přepravu od a-tého dodavatele k b-tému spotřebiteli, d-tým dopravním prostředkem
X = ( xijk )
- 11 -
Christy
SW aplikace MOV přednášky n
p
∑∑ x
ijk
≤ ai
i = 1,2,...n
∑∑ x
ijk
= bj
j = 1,2,...m
∑∑ x
ijk
≤ dk
k = 1,2,... p
j =1 k =1
m
p
i =1 k =1 m n i =1 j =1
∑∑∑ c i
j
ijk
xijk ... min
k
Planární řezy
Aijk
Aikj
Aijk
červená dopravní prostředek list
zelená spotřebitel jeden sloupec ve všech listech
černá dodavatel jeden řádek ve všech listech
obr. 1 H-vrchol Tabulkové procesory lze řešit dvěma základními postupy 1) modely řešitelné analytickými postupy - pomocí vložených pevných funkcí - strukturální analýza, vícekriteriální rozhodování, stochastické modely 2) modely řešitelné iteračními postupy - nelze říci že výstup je přímou funkcí výstupu - modely matematické programování
- 12 -
Christy
