Vysoká škola báňská
Technická univerzita Ostrava
Fakulta strojní
Základy teorie pravděpodobnosti
a teorie grafů
Autoři :
Doc. Ing. Miluše Vítečková, CSc., Bc. Přidal Petr, Ing. Koudela Tomáš
Ostrava 2006
2
Obsah
Obsah
SEZNAM POUŽITÉHO ZNAČENÍ ..................................................................................... 3
1
ÚVOD ............................................................................................................................... 5
2
TEORIE PRAVDĚPODOBNOSTI ............................................................................... 6
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.7.1
2.7.2
2.7.3
2.7.4
2.7.5
3
ZÁKLADNÍ POJMY ................................................................................................................................. 6
NEZÁVISLÉ JEVY ................................................................................................................................... 9
OPAKOVANÉ NEZÁVISLÉ POKUSY ....................................................................................................... 12
PODMÍNĚNÁ PRAVDĚPODOBNOST ....................................................................................................... 15
PRAVDĚPODOBNOST HYPOTÉZ ............................................................................................................ 18
NÁHODNÁ VELIČINA ........................................................................................................................... 19
ROZDĚLENÍ NÁHODNÉ VELIČINY ......................................................................................................... 23
Rovnoměrné rozdělení náhodné veličiny....................................................................................... 24
Normální rozdělení náhodné veličiny............................................................................................ 27
Exponenciální rozdělení náhodné veličiny .................................................................................... 33
Binomické rozdělení diskrétní náhodné veličiny ........................................................................... 35
Poissonovo rozdělení diskrétní náhodné veličiny.......................................................................... 37
TEORIE GRAFŮ .......................................................................................................... 39
3.1
3.2
3.3
3.4
3.5
3.6
3.7
ZÁKLADNÍ POJMY ............................................................................................................................... 39
EULEROVSKÉ TAHY ............................................................................................................................ 44
HAMILTONOVSKÉ CESTY A KRUŽNICE ................................................................................................ 48
METODA MINIMÁLNÍ CESTY ................................................................................................................ 50
METODA KRITICKÉ CESTY (CPM - CRITICAL PATH METHOD) ............................................................ 53
METODA PERT................................................................................................................................... 61
PROPUSTNOST DOPRAVNÍ SÍTĚ ............................................................................................................ 65
SEZNAM LITERATURY .................................................................................................... 70
Seznam použitého značení
3
Seznam použitého značení
A, B, C .................. velkými písmeny abecedy značíme jevy
B .......................... jev opačný k jevu B
G ..........................graf
G D ........................ duální graf ke grafu G
E , E (G ) ................ množina hran grafu G
f ( x) ..................... hustota pravděpodobnosti
f ( xi ) .................... frekvenční funkce náhodné veličiny X
F ( x) ..................... distribuční funkce náhodné veličiny X
h ........................... hrana v grafu
m .......................... počet pokusů příznivých danému jevu, modus (nejpravděpodobnější doba
trvání činnosti)
n ........................... počet všech možných pokusů, které mohou nastat
p .......................... pravděpodobnost, že jev A nastane, p = P(A)
P * ......................... relativní četnost určitého jevu
P( A / H ) ............... podmíněná pravděpodobnost jevu A v případě, že nastal jev H
P ( A) ..................... pravděpodobnost jevu A
()
q ........................... pravděpodobnost, že jev A nenastane, q = 1 − p = P A
rk .......................... hodnota náhodné veličiny normovaného rovnoměrného rozdělení
R .......................... časová rezerva
t e .......................... očekávaná doba trvání činnosti
t eij .......................... očekávaný termín činnosti vystupující z uzlu i a vstupující do uzlu j
t ij .......................... doba trvání činnosti vystupující z uzlu i a vstupující do uzlu j
Ti p ......................... nejpozději přípustný termín
Tnm ......................... termín realizace úkolu
TE ......................... očekávaný termín realizace celého úkolu
T P ......................... plánovaný termín realizace celého úkolu
u k .......................... hodnota náhodné veličiny normovaného normálního rozdělení
V , V (G ) ................ množina vrcholů grafu G
x ........................... hodnota náhodné veličiny X
4 Seznam použitého značení
X , Y , Z ................. náhodné veličiny (náhodné proměnné)
σ 2 ......................... rozptyl náhodné veličiny, centrální moment 2. řádu
σ t2 ......................... rozptyl očekávané doby trvání činnosti
e
σ ........................ rozptyl očekávaného termínu realizace celého úkolu
2
TE
µ .......................... střední hodnota náhodné veličiny X, obecný moment 1.řádu
δ ........................... velikost minimální rezervy
Úvod
5
1 Úvod
Katedra ATŘ má dlouhodobou zkušenost s hypertextovými učebnicemi, které jsou volně
přístupné na internetu. Učebnice byly vytvořeny převážně jako projekty studentů pro
doplňkovou výuku.
Elektronické učebnice mají mnoho výhod oproti psaným učebnicím. Výhody lze spatřovat
především v možnosti prohlížet učebnice odkudkoliv, kde je připojení k internetu, a dále
možnost jejich prohlížení více uživateli najednou. Byly vytvořeny hlavně pro potřeby
studentů kombinované formy výuky.
V této elektronické učebnici studenti najdou základy z teorie pravděpodobnosti a teorie
grafů v rozsahu vyučovaném v magisterském studiu na katedře automatické techniky a řízení.
6 Teorie pravděpodobnosti
2 Teorie pravděpodobnosti
2.1 Základní pojmy
Pokus je každá realizace určitého předem stanoveného komplexu podmínek
[Kába, B., 1999]. Pokus musí být reprodukovatelný, to znamená:
•
je nutno, aby podmínky, za nichž pokus probíhá, byly stabilizovány,
•
existuje alespoň teoretická možnost opakování pokusu,
•
výsledek pokusu není předem znám (výsledek není jednoznačně určen jeho
podmínkami), je to však právě jeden z prvků známé množiny výsledků, kterou
nazýváme základní prostor (možné výsledky náhodného pokusu).
Jev je každý fakt, o kterém, jakožto o výsledku pokusu, má smysl prohlásit, zda nastal
nebo nenastal.
Typy jevů:
•
jev jistý - vždy nastane při daném komplexu podmínek,
•
jev nemožný - nikdy nenastane při daném komplexu podmínek,
•
jev náhodný - může a nemusí nastat při daném komplexu podmínek.
Další pojmy
Opačný jev
Jev, který spočívá v nenastoupení jevu A je jev opačný k jevu A, značí se A (A negace).
P ( A) + P ( A ) = 1
⇒
P( A) = 1 − P (A ),
P (A ) = 1 − P( A).
A
A
Obr. 2.1 Opačný jev
Teorie grafu
7
Průnik jevů A I B
A
B
Obr. 2.2 Průnik jevů
Sjednocení jevů A U B
A
B
Obr. 2.3 Sjednocení jevů
Relativní četnost:
je definována jako poměr počtu pokusů příznivých danému jevu m ku počtu všech pokusů
n:
P* =
m
.
n
Statistická definice pravděpodobnosti
Vychází se z experimentálního zjištění, že při zvětšování počtu pokusů n → ∞ se relativní
četnost určitého jevu P* blíží k určité konstantní hodnotě, kterou nazveme pravděpodobností
jevu A [Kába, B., 1999]
P ( A) = lim P * .
n →∞
8 Teorie grafu
Klasická definice pravděpodobnosti
Pravděpodobnost jevu A je rovna počtu m možných výsledků pokusů příznivých jevu A k
počtu n všech možných výsledků pokusu [Kába, B., 1999]:
P ( A) =
m
.
n
Za předpokladu, že všechny výsledky jsou stejně možné a jsou všechny, n je konečné
číslo.
Axiomatická definice pravděpodobnosti (A. N. Kolmogorov, 1933)
a) 0 ≤ P( A) ≤ 1 ,
b) pravděpodobnost nemožného jevu A je rovna nule [P(A) = 0],
c) pravděpodobnost jistého jevu A je rovna jedné [P(A) = 1],
d) A1, A2,…, An jsou po dvou neslučitelné jevy, to znamená, nikdy nemohou nastat
současně dva z těchto jevů, potom platí
P( A1 , A2 ,.., An ) = P( A1 U A2 U .. U An ) = P( A1 ) + P( A2 ) + .. + P( An ).
Tato kapitola je podrobně popsána v literatuře [Kába, B., 1999].
Teorie grafu
9
2.2 Nezávislé jevy
Jsou takové jevy, kdy nastání jednoho z nich nemá vliv na nastání nebo nenastání druhého
jevu [Kába, B., 1999], potom:
pro dva nezávislé jevy A, B platí:
P(A ∩ B) = P(A)P(B),
pro tři nezávislé jevy A, B, C platí:
P(A ∩ C) = P(A)P(C),
P(A ∩ B) = P(A)P(B),
P(B ∩ C) = P(B)P(C),
P(A ∩ B ∩ C) = P(A)P(B)P(C).
Příklad 2.1
Hodíme bílou a černou kostkou, b značí číslo na bílé kostce, c číslo na černé kostce. V
každém z následujících případů rozhodněte, zda jevy jsou nebo nejsou závislé.
a) Jev A je b = 3, jev B je c = 4.
Řešení:
1 ⎫
6 ⎪⎪
⎬ ⇒ P( A) P( B) = P( A I B) ⇒ A a B jsou nezávislé jevy
1 ⎪
P( A I B) =
36 ⎪⎭
P(A) = P(B) =
P(A ∩ B) ⇒ Počet všech pokusuje n = 6 ⋅ 6 =36, chceme však jen jednu kombinaci m = 1.
b) Jev C je b + c = 7, jev D je c = 3.
Řešení:
1 ⎫
6 ⎪⎪
⎬ ⇒ P(C ) P( D) = P(C I D) ⇒ C a D jsou nezávislé jevy
1 ⎪
P (C I D) =
36 ⎪⎭
P(C) = P(D) =
P(C) ⇒ Máme 36 možností, z toho nám 6 vyhovuje (1+6, 2+5, 3+4 a 6+1, 5+2, 4+3) ⇒
6 1
= .
36 6
c) Jev C je b + c = 7, jev E je c < 3.
Řešení:
2 1⎫
1
P(C) = , P(E) = = ⎪
6 3⎪
6
⎬ ⇒ P(C ) P( E ) = P (C I E ) ⇒ C a E jsou nezávislé jevy
2
1
⎪
=
P (C I E ) =
36 18 ⎪⎭
P(E) ⇒ Máme 6 možností, z toho nám 2 vyhovují (5+2, 6+1).
10 Teorie grafu
d) Jev F je b + c = 11, jev G je c ≠ 5.
Řešení:
2
1
5
= , P(G ) =
36 18
6
1
P( F I G) =
36
P( F ) =
⎫
⎪⎪
⎬ ⇒ P ( F ) P(G ) = P( F I G ) ⇒ F a G jsou závislé jevy
⎪
⎭⎪
Jev G je opačný k jevu G , kdy chceme aby padla 5 a jeho pravděpodobnost je P( G ) =
1
.
6
Jevy v bodech a), b) a c) nejsou na sobě nezávislé a v bodě d) jsou jevy na sobě závislé.
Příklad 2.2
Čtyři stroje pracují nezávisle na sobě a mají různou poruchovost. Pravděpodobnost, že
během jedné hodiny dojde k poruše na prvním stroji je P(A1) = 0,1; na druhém stroji P(A2) =
0,2; na třetím stroji P(A3) = 0,3; na čtvrtém stroji P(A4) = 0,05. Jaká je pravděpodobnost, že
během jedné hodiny nedojde k žádné poruše?
Řešení:
(
) ( )( )( )( )
P A1 I A2 I A3 I A4 = P A1 P A2 P A3 P A4 =
= [1 − P( A1 )] [1 − P( A2 )] [1 − P( A3 )] [1 − P( A4 )] =
= 0,9 ⋅ 0,8 ⋅ 0,7 ⋅ 0,95 = 0,479.
Pravděpodobnost, že během jedné hodiny nedojde k žádné poruše, je 47,9 %.
Nezávislé jevy a jejich sjednocení
a) neslučitelné jevy (nikdy nemohou nastat oba jevy najednou)
P ( A U B ) = P ( A ) + P (B )
A
B
Obr. 2.4 Nezávislé jevy A, B neslučitelné
Teorie grafu
11
b) slučitelné jevy (mohou nastat oba jevy najednou)
P( A U B ) = P( A) + P(B ) − P( A I B ) ⇒ P( A U B ) = P( A) + P(B ) − P( A)P(B )
A
B
Obr. 2.5 Nezávislé jevy A, B slučitelné
Pro sjednocení jevů slučitelných a nezávislých platí:
a) pro dva jevy:
()()
P( A U B ) = 1 − P A P B = 1 − [1 − P( A)][1 − P(B )] .
b) pro více jevů:
n
⎛ n ⎞
P⎜⎜ U Ai ⎟⎟ = 1 − ∏ [1 − P( Ai )]
i =1
⎝ i =1 ⎠
Příklad 2.3
Pracovník má navštívit tři arabská města postižená nemocí. Pravděpodobnost nakažení
v některém městě je: P(A) = 0,3; P(B) = 0,4; P(C) = 0,5. Jaká je pravděpodobnost, že se
v některém z těchto měst nakazí?
Řešení:
P( A U B U C ) = 1 − ([1 − P( A)] [1 − P(B )] [1 − P(C )]) = 1 − (0,7 ⋅ 0,6 ⋅ 0,5) = 0,79
.
Pravděpodobnost, že se pracovník během své cesty nakazí, je 79 %.
Příklad 2.4
S jakou pravděpodobností bude sdružená telefonní linka s 10 účastníky obsazena, je-li pro
každého účastníka pravděpodobnost hovoru v daném okamžiku 1 % a vyskytují-li se hovory
nezávisle na sobě?
Řešení:
10
10
⎛ 10 ⎞
P⎜ U Ai ⎟ = 1 − ∏ (1 − P( Ai )) = 1 − (1 − 0,01) = 0,0956
i =1
⎝ i =1 ⎠
Linka bude v daném okamžiku obsazena s pravděpodobností 9,5 %.
12 Teorie grafu
2.3 Opakované nezávislé pokusy
Nechť se pokus skládá z n nezávislých dílčích pokusů, z nichž každý končí buď zdarem s
pravděpodobností p nebo nezdarem s pravděpodobností q = 1 – p [Kába, B., 1999]. Potom
pravděpodobnost, že právě k dílčích pokusů bude zdařilých je dána vztahem
⎛ n ⎞ k n−k
⎜⎜ ⎟⎟ p q , kde k = 0, 1, ..., n.
⎝k ⎠
Tato pravděpodobnost je rovna jednomu sčítanci z binomické věty
( p + q )n = ⎛⎜⎜
n ⎞ n ⎛ n ⎞ n −1 ⎛ n ⎞ 2 n − 2
⎛ n⎞
⎟⎟q + ⎜⎜ ⎟⎟ pq + ⎜⎜ ⎟⎟ p q + ... + ⎜⎜ ⎟⎟ p n
⎝0⎠
⎝1⎠
⎝ 2⎠
⎝ n⎠
kde je:
⎛n⎞ ⎛ n ⎞ ⎛
⎞
n!
⎟⎟ = ⎜⎜
⎜⎜ ⎟⎟ = ⎜⎜
⎟⎟ - binomický koeficient.
⎝ k ⎠ ⎝ n − k ⎠ ⎝ k! (n − k )! ⎠
Platí:
n≥k
⎛ n⎞ ⎛ n⎞
⎜⎜ ⎟⎟ = ⎜⎜ ⎟⎟ = 1
⎝0⎠ ⎝ n⎠
⎛n⎞ ⎛ n ⎞
⎜⎜ ⎟⎟ = ⎜⎜
⎟⎟ = n
⎝ 1 ⎠ ⎝ n − 1⎠
Tabulka 2.1 Opakované nezávislé pokusy
Pravděpodobnost, že právě k pokusů je zdařilých:
⎛ n ⎞ k n−k
⎜⎜ ⎟⎟ p q
⎝k ⎠
Pravděpodobnost, že alespoň k dílčích pokusů je zdařilých:
n
⎛ n⎞
⎛ n⎞
⎛ n ⎞ k n − k ⎛ n ⎞ k +1 n − k −1
⎟⎟ p q
⎜⎜ ⎟⎟ p q + ⎜⎜
+ ... + ⎜⎜ ⎟⎟ p n = ∑ ⎜⎜ ⎟⎟ p i q n −i
i =k ⎝ i ⎠
⎝ k + 1⎠
⎝ n⎠
⎝k ⎠
Pravděpodobnost, že nejvýše k dílčích pokusů je zdařilých:
k
⎛ n ⎞ n ⎛ n ⎞ n −1
⎛n⎞
⎛ n⎞
⎜⎜ ⎟⎟q + ⎜⎜ ⎟⎟ pq + ... + ⎜⎜ ⎟⎟ p k q n − k = ∑ ⎜⎜ ⎟⎟ p i q n −i
i =0 ⎝ i ⎠
⎝0⎠
⎝1⎠
⎝k ⎠
Platí:
n
⎛ n⎞
i =0
⎝ ⎠
∑ ⎜⎜ i ⎟⎟ p q
i
n −i
=1
Teorie grafu
13
Příklad 2.5
Máme osudí s deseti černými a dvaceti bílými koulemi. Táhneme náhodně šest koulí,
přičemž každou taženou kouli vrátíme zpět do osudí dříve, než táhneme další. Jaká je
pravděpodobnost, že mezi taženými koulemi budou právě dvě koule bílé?
Řešení:
počet pokusů n = 6,
pravděpodobnost vytažení bílé koule p =
20 2
= ,
30 3
pravděpodobnost vytažení černé koule q = 1 − p =
1
,
3
počet tažených bílých koulí k = 2,
pak platí:
2
4
⎛ n ⎞ k n −k ⎛ 6 ⎞ ⎛ 2 ⎞ ⎛ 1 ⎞
6! 4 1
⎜⎜ ⎟⎟ p q = ⎜⎜ ⎟⎟ ⋅ ⎜ ⎟ ⋅ ⎜ ⎟ =
⋅ ⋅ = 0,082.
4!⋅2! 9 81
⎝k ⎠
⎝ 2⎠ ⎝ 3 ⎠ ⎝ 3 ⎠
Pravděpodobnost, že mezi šesti taženými koulemi budou právě dvě bílé, je 8,2 %.
Příklad 2.6
Jaká je pravděpodobnost, že rodina se čtyřmi dětmi má: a) alespoň tři chlapce, b) alespoň
jednoho chlapce?
Řešení:
počet dětí v rodině: n = 4,
pravděpodobnost narození chlapce: p =
1
,
2
1
,
2
pravděpodobnost narození dívky: q =
pak platí:
a) rodina má alespoň tři chlapce, tj. má tři nebo čtyři chlapce:
3
4
⎛ 4⎞ ⎛ 1 ⎞ 1 ⎛ 4⎞ ⎛ 1 ⎞
1 1
1
P(3) = ⎜⎜ ⎟⎟ ⋅ ⎜ ⎟ ⋅ + ⎜⎜ ⎟⎟ ⋅ ⎜ ⎟ = 4 ⋅ ⋅ + 1 ⋅ = 0,3125,
8 2
16
⎝ 3⎠ ⎝ 2 ⎠ 2 ⎝ 4⎠ ⎝ 2 ⎠
b) rodina má alespoň jednoho chlapce, tj. rodina má 1, 2, 3 nebo 4 chlapce:
3
2
2
4
⎛ 4⎞ 1 ⎛ 1 ⎞ ⎛ 4⎞ ⎛ 1 ⎞ ⎛ 1 ⎞
⎛ 4⎞ ⎛ 1 ⎞ ⎛ 4⎞ ⎛ 1 ⎞
P(1) = ⎜⎜ ⎟⎟ ⋅ ⋅ ⎜ ⎟ + ⎜⎜ ⎟⎟ ⋅ ⎜ ⎟ ⋅ ⎜ ⎟ + ⎜⎜ ⎟⎟ ⋅ ⎜ ⎟ + ⎜⎜ ⎟⎟ ⋅ ⎜ ⎟ = 0,9375.
⎝ 1⎠ 2 ⎝ 2 ⎠ ⎝ 2⎠ ⎝ 2 ⎠ ⎝ 2 ⎠
⎝ 3⎠ ⎝ 2 ⎠ ⎝ 4⎠ ⎝ 2 ⎠
14 Teorie grafu
Problém lze převést na opačný jev: rodina nemá chlapce
0
4
4
⎛ 4⎞ ⎛ 1 ⎞ ⎛ 1 ⎞
1
⎛1⎞
P(0 ) = 1 − ⎜⎜ ⎟⎟ ⋅ ⎜ ⎟ ⋅ ⎜ ⎟ = 1 − ⎜ ⎟ = 1 − = 0,9375;
16
⎝2⎠
⎝0⎠ ⎝ 2 ⎠ ⎝ 2 ⎠
Rodina se čtyřmi dětmi má alespoň jednoho chlapce s pravděpodobností 93,75 % a
alespoň tři chlapce s pravděpodobností 31,25 %.
Příklad 2.7
Písemný test má dvacet otázek, každá otázka má čtyři různé odpovědi. Jaká je
pravděpodobnost, že student vykoná správně test, má-li správně odpovědět alespoň na patnáct
otázek, přičemž nic neví?
Řešení:
počet otázek v textu: n = 20,
pravděpodobnost správně zodpovězené otázky: p =
1
,
4
pravděpodobnost nesprávně zodpovězené otázky: q =
3
.
4
Pak pravděpodobnost, že student zodpoví 15 a více otázek správně, je:
15
5
16
4
17
3
18
2
⎛ 20 ⎞ ⎛ 1 ⎞ ⎛ 3 ⎞ ⎛ 20 ⎞ ⎛ 1 ⎞ ⎛ 3 ⎞
⎛ 20 ⎞ ⎛ 1 ⎞ ⎛ 3 ⎞
⎛ 20 ⎞ ⎛ 1 ⎞ ⎛ 3 ⎞
⎜⎜ ⎟⎟ ⋅ ⎜ ⎟ ⋅ ⎜ ⎟ + ⎜⎜ ⎟⎟ ⋅ ⎜ ⎟ ⋅ ⎜ ⎟ + ⎜⎜ ⎟⎟ ⋅ ⎜ ⎟ ⋅ ⎜ ⎟ + ⎜⎜ ⎟⎟ ⋅ ⎜ ⎟ ⋅ ⎜ ⎟ +
⎝ 17 ⎠ ⎝ 4 ⎠ ⎝ 4 ⎠ ⎝ 18 ⎠ ⎝ 4 ⎠ ⎝ 4 ⎠
⎝ 16 ⎠ ⎝ 4 ⎠ ⎝ 4 ⎠
⎝ 15 ⎠ ⎝ 4 ⎠ ⎝ 4 ⎠
19
1
⎛ 20 ⎞ ⎛ 1 ⎞ ⎛ 3 ⎞ ⎛ 20 ⎞ ⎛ 1 ⎞
+ ⎜⎜ ⎟⎟ ⋅ ⎜ ⎟ ⋅ ⎜ ⎟ + ⎜⎜ ⎟⎟ ⋅ ⎜ ⎟
⎝ 19 ⎠ ⎝ 4 ⎠ ⎝ 4 ⎠ ⎝ 20 ⎠ ⎝ 4 ⎠
20! ⎛ 1 ⎞
+
⋅⎜ ⎟
17!⋅3! ⎝ 4 ⎠
20
20! ⎛ 1 ⎞
⋅3 +
⋅⎜ ⎟
18!⋅2! ⎝ 4 ⎠
3
20
20
20! ⎛ 1 ⎞
=
⋅⎜ ⎟
15!⋅5! ⎝ 4 ⎠
20
20! ⎛ 1 ⎞
⋅3 +
⋅⎜ ⎟
19!⋅1! ⎝ 4 ⎠
2
20! ⎛ 1 ⎞
⋅3 +
⋅⎜ ⎟
16!⋅4! ⎝ 4 ⎠
5
20
⎛1⎞
⋅ 3 + 1⋅ ⎜ ⎟
⎝4⎠
Student vykoná správně test s pravděpodobností 3,81˙10-4 %.
20
⋅ 34 +
20
= 3,81 ⋅ 10 − 6
Teorie grafu
15
2.4 Podmíněná pravděpodobnost
P(A/B) je podmíněná pravděpodobnost jevu A za podmínky, že nastal jev B [Kába, B., 1999]
P( A / B ) =
P( A I B )
, P(B ) ≠ 0 ⇒ B nesmí být jev nemožný,
P (B )
P (B / A) =
P( A I B )
, P( A) ≠ 0 ⇒ A nesmí být jev nemožný,
P ( A)
P( A I B ) = P(B )P( A / B ) = P( A)P(B / A) .
Pak platí:
P( A / B ) =
P( A)P(B / A)
,
P (B )
P ( B / A) =
P(B )P( A / B )
.
P ( A)
Pro nezávislé jevy A, B platí:
P ( A I B ) = P( A) P( B) ,
pak
P ( A / B ) = P ( A), P(B / A) = P (B ) .
Tento vztah vyjadřuje, že podmíněná pravděpodobnost jevu A (za podmínky jevu B) je
rovna pravděpodobnosti jevu A, pokud A, B jsou nezávislé jevy.
Příklad 2.8
Jaká je pravděpodobnost, že rodina se třemi dětmi má dva chlapce a jedno děvče za
podmínky, že má alespoň jednoho chlapce?
Řešení:
Jev A - dva chlapci a jedno děvče.
Jev B - alespoň jeden chlapec.
(Jev B - žádný chlapec, tj. rodina má 3 dívky).
()
0
3
()
⎛ 3⎞ ⎛ 1 ⎞ ⎛ 1 ⎞
1 1
7
P B = ⎜⎜ ⎟⎟ ⋅ ⎜ ⎟ ⋅ ⎜ ⎟ = 1 ⋅ = ⇒ P(B ) = 1 − P B = ,
8 8
8
⎝ 0⎠ ⎝ 2 ⎠ ⎝ 2 ⎠
P ( A I B ) = P ( A),
16 Teorie grafu
2
⎛ 3⎞ ⎛ 1 ⎞
P( A) = ⎜⎜ ⎟⎟ ⋅ ⎜ ⎟
⎝ 2⎠ ⎝ 2 ⎠
3
3
P( A / B ) = 8 =
7 7
8
⋅
1 3
= ,
2 8
= 0,428.
Pravděpodobnost, že rodina se třemi dětmi má dva chlapce a jedno děvče za podmínky, že
má alespoň jednoho chlapce, je 42,8 %.
Celková pravděpodobnost
Bayesův vzorec:
()(
)
P(B )P( A / B ) + P B P A / B = P( A),
P (B / A) =
P(B )P( A / B )
()(
P (B )P ( A / B ) + P B P A / B
)
=
P (B )P( A / B )
.
P ( A)
Tato kapitola je podrobně popsána v literatuře [Kába, B., 1999].
Příklad 2.9
Sodovkárna má dva automaty na plnění a uzavírání lahví. První automat zpracuje 1000
lahví za hodinu, druhý automat zpracuje 1500 lahví za hodinu. Z tohoto počtu má zpravidla
pět lahví z prvního a dvanáct lahví z druhého automatu vadný uzávěr.
Máme za úkol určit:
1) Má-li láhev vadný uzávěr, jaká je pravděpodobnost, že pochází z druhého automatu?
2) Jaká je pravděpodobnost, že náhodně vybraná láhev je vadná?
Řešení:
Jev A značí, že láhev má vadný uzávěr.
Jev B značí, že láhev je z prvního automatu P(B ) =
1000
= 0,4 .
2500
()
Jev B značí, že láhev je z druhého automatu P B = 1 − P(B ) =
Pravděpodobnost, že láhev je vadná a je z prvního automatu:
P( A / B ) =
5
= 0,005;
1000
Pravděpodobnost, že láhev je vadná a je z druhého automatu:
(
)
P A/ B =
12
= 0,008;
1500
1500
= 0,6 .
2500
Teorie grafu
17
ad 1) Má-li láhev vadný uzávěr, pochází z druhého automatu s pravděpodobností:
(
,6 ⋅ 0,008
) P(B P)P((AA) / B ) = 0,6 ⋅ 0,0008
= 0,706.
+ 0,4 ⋅ 0,005
P B/ A =
S pravděpodobností 70,6 % bude vadná láhev pocházet z druhého automatu.
ad 2) Pravděpodobnost, že náhodně vybraná láhev je vadná:
()(
)
P ( A) = P B P A / B + P(B )P( A / B ) = 0,6 . 0,008 + 0,4 . 0,005 = 0,0068 .
Vadná láhev je vybrána s pravděpodobností 0,68 %.
Příklad 2.10
Hodíme dvěma kostkami, bílou a černou. Jaká je pravděpodobnost, že na bílé padlo číslo
menší než 4 za podmínky že padl součet 7.
Řešení:
Jev A – součet je 7.
Jev B – číslo menší než 4 na bílé kostce.
P ( A) =
6 1
= (viz příklad 2.1 b),
36 6
P (B ) =
3 1
= ,
6 2
P( A I B ) =
1 1 1
⋅ =
(průnik jevů je jejich součin),
6 2 12
1
P( A I B ) 12 1
P (B / A) =
=
= ⇒ 50 %.
1 2
P ( A)
6
Na bílé kostce padne číslo menší než 4 s celkovým součtem 7 s pravděpodobností 50 %.
18 Teorie grafu
2.5 Pravděpodobnost hypotéz
H1, H2,…, Hn jsou vzájemně neslučitelné podmínky
Nechť jev A může nastat jen při nastoupení některé ze vzájemně neslučitelných podmínek
H1, H2,…, Hn, které nazýváme hypotézy [Kába, B., 1999].
Známe:
1. P(Hi), i = 1, 2, …, n
2. P(A/Hi) značí pravděpodobnost nastoupení jevu A při nastoupení určité podmínky Hi
(pravděpodobnost a priori).
Jestliže provedeme pokus, ve kterém skutečně dojde k nastoupení jevu A, můžeme
určit pravděpodobnost hypotéz za předpokladu, že jev A nastal (pravděpodobnost a
posteriori).
Určíme:
⎡
⎢
⎢ P (H i / A) =
⎢
⎢
⎣
⎤
P(H i )P( A / H i ) ⎥⎥
, kde
n
⎥
P (H j )P (A / H j )⎥
∑
j =1
⎦
∑ P(H )P(A / H ) = P( A).
n
j =1
j
j
Příklad 2.11
V obchodě jsou žárovky ze tří podniků. 20 % z jednoho podniku, 30 % z druhého podniku
a 50 % z třetího podniku. Mezi nimi je 5 % zmetků z prvního podniku, 7 % zmetků z druhého
podniku, 10 % zmetků z třetího podniku.
Naším úkolem je určit:
1) Koupíme-li žárovku, jaká je pravděpodobnost, že je vadná?
2) Koupíme-li žárovku a je vadná, jaká je pravděpodobnost, že je ze třetího podniku?
Řešení:
Jev A – vadná žárovka.
Jev H1 – žárovky z prvního podniku.
Jev H2 – žárovky z druhého podniku.
Jev H3 – žárovky ze třetího podniku.
P(H1) = 0,2;
P(A/ H1) = 0,05;
P(H2) = 0,3;
P(A/ H2) = 0,07;
P(H3) = 0,5;
P(A/ H3) = 0,1;
Teorie grafu
19
ad 1)
P( A) = ∑ P(H j )P (A / H j ) = 0,2 . 0,05 + 0,3 . 0,07 + 0,05 . 0,1 = 0,081 .
3
j =1
Vadnou žárovku koupíme s pravděpodobností 8,1 %.
ad 2)
P (H 3 / A) =
P(H 3 )P( A / H 3 ) 0,1 ⋅ 0,5
=
= 0,62.
P ( A)
0,081
Vadnou žárovku z třetího podniku koupíme s pravděpodobností 62 %.
Příklad 2.12
V souboru deseti výrobků mohou být jeden, dva nebo tři zmetky. Pravděpodobnost
jednotlivých alternativ jsou postupně 50 %, 20 %, 30 %. Vybereme–li z tohoto souboru
náhodně jeden výrobek, jaká je pravděpodobnost, že je špatný?
Řešení:
A – výrobek je zmetek,
H1 - v souboru je jeden zmetek
P( A / H 1 ) = 0,5 ;
H2 - v souboru jsou dva zmetky
P( A / H 2 ) = 0,2 ;
H3 - v souboru jsou tři zmetky
P( A / H 3 ) = 0,3 .
1
,
10
2
P (H 2 ) = ,
10
3
P (H 3 ) = ,
10
P (H 1 ) =
P( A) = ∑ P(H j )P (A / H j ) =
n
j =1
1
1
3
⋅ 0,5 + ⋅ 0,2 + ⋅ 0,3 = 0,05 + 0,04 + 0,09 = 0,18.
10
5
10
Špatný výrobek vytáhneme s pravděpodobností 18 %.
2.6 Náhodná veličina
Náhodná veličina X je proměnná, jejíž hodnota x je jednoznačně určena výsledkem
náhodného pokusu. Charakteristickým rysem náhodné veličiny je, že při opakování
náhodného pokusu dochází vlivem náhodných činitelů k měnlivosti hodnot. Nemůžeme před
provedením pokusu určit, jaké hodnoty veličina nabude [Škrášek, J., Tichý, Z., 1990],
[Vítečková, M.].
20 Teorie grafu
Tabulka 2.2: Dělení náhodné veličiny
Spojitá náhodná veličina
Diskrétní náhodná veličina
Nabývá libovolných hodnot z určitého Nabývá konečný počet hodnot z intervalu
intervalu (např. odečet z měřicího přístroje) (např. kostka, ruleta)
Distribuční funkce
F ( x i ) = P( X ≤ x i )
F (x ) = P( X ≤ x )
F (−∞ ) = 0
F (+∞ ) = 1
F (−∞ ) = 0
F (+∞ ) = 1
x1 ≤ x 2 ⇔ F ( x1 ) ≤ F ( x2 )
x1 ≤ x 2 ⇔ F ( x1 ) ≤ F ( x2 )
Distribuční funkce je funkce neklesající.
F ( xi ) ∈ 0,1
F ( x ) ∈ 0,1
f ( x) =
Obr. 2.6 Hladká funkce
Obr. 2.7 Schodovitá funkce
Hustota pravděpodobnosti
Frekvenční funkce
dF ( x)
dx
f ( xi ) = ∇F ( xi ) = F ( x i ) - F ( x i-1 )
Obr. 2.8 Hustota pravděpodobnosti
Obr. 2.9 Frekvenční funkce
+∞
∫ f (x )dx = 1 = F (∞ )
∞
∑ f (xk ) = 1
−∞
P( x1 ≤ X ≤ x 2 ) =
x2
∫ f (x )dx = F (x ) − F (x )
2
x1
F (x ) =
x
∫
f (s )ds
0 ≤ f (x )
−∞
P( x1 ≤ X ≤ x 2 ) = P( x1 < X < x 2 ) =
= P( x1 ≤ X < x 2 ) = P( x1 < X ≤ x 2 )
1
k =1
f ( x k ) = ∇F ( x k ) = F ( x k ) − F ( x k −1 )
i −1
F ( xi ) = ∑ f ( x k )
k =1
0 ≤ f (xi ) ≤ 1
Teorie grafu
21
Číselné charakteristiky náhodných veličin
Číselné charakteristiky popisují některé základní rysy náhodných veličin, jako například
obecné a centrální momenty [Škrášek, J., Tichý, Z., 1990].
Tabulka 2.3 Charakteristiky náhodných veličin
Spojitá náhodná veličina
Diskrétní náhodná veličina
Obecný moment náhodné veličiny s-tého řádu
M s [X ] =
∞
+∞
∫x
s
M s [ X ] = ∑ xis f ( xi )
f ( x) dx
i =1
−∞
Obecný moment náhodné veličiny prvního řádu (střední hodnota)
M 1 [X ] = E [X ] = x = µ =
∞
+∞
M 1 [X ] = E [X ] = µ = ∑ xi f ( xi )
∫ xf ( x)dx
i =1
−∞
Centrální moment s-tého řádu
ms [X ] =
∞
+∞
m s [ X ] = ∑ ( xi − µ ) f ( xi )
s
∫ (x − µ ) f (x )dx
s
i =1
−∞
Obecný zápis centrálního momentu: ms[X] = E[(X - E[X])s]
Centrální moment prvního řádu
m1 [ X ] = 0
Důkaz: (pro diskrétní NV)
∞
∞
∞
i =1
i =1
i =1
m1 ⎡ X ⎤ = ∑ ( xi − µ ) f ( xi ) = ∑ xi f ( xi ) − µ ∑ f (xi ) = µ − µ 1 = 0
Centrální moment druhého řádu (rozptyl, disperze, variace)
D[ X ] = σ 2 = m 2 [ X ] =
∞
+∞
D[ X ] = σ 2 = m 2 [ X ] = ∑ ( x i − µ ) 2 f ( x i )
2
∫ ( x − µ ) f ( x)dx
−∞
[
]
i =1
m2 [ X ] = E ( X − E [X ]) ,
2
Směrodatná odchylka (standardní, střední kvadratická odchylka)
σ = D[ X ] = m 2 [ X ]
Vlastnosti µ a σ2 (platí pro spojité i diskrétní náhodné veličiny)
C - konstanta
X, Y - náhodné veličiny (platí pro spojité i diskrétní)
µ - střední hodnota
σ 2 - rozptyl náhodné veličiny
µ (C ) = C
µ ( X + Y ) = µ ( X ) + µ (Y )
µ (X + C ) = µ(X ) + C
µ (CX ) = Cµ ( X )
µ ( XY ) = µ ( X )µ (Y )
σ 2 (C ) = 0
σ 2 ( X + Y ) = σ 2 ( X ) + σ 2 (Y )
σ 2 (X + C ) = σ 2 (X )
σ 2 (CX ) = C 2σ 2 ( X )
22 Teorie grafu
Příklad 2.13
Při hodu dvěma hracími kostkami současně, nechť na první padne číslo j a na druhé
kostce padne číslo k. Hodnota náhodné veličiny je: x = j + k. Najděte frekvenční a distribuční
funkci.
Řešení:
i −1
F ( xi ) = ∑ f ( x k )
k =1
Tabulka 2.4: Tabulka hodnot frekvenční a distribuční funkce
xi
2
3
4
5
6
7
8
9
10
11
12
f ( xk )
1
36
F ( xi )
0
2
36
1
36
3
36
3
36
4
36
6
36
5
36
10
36
6
36
15
36
5
36
21
36
4
36
26
36
3
36
30
36
2
36
33
36
1
36
35
36
Obr. 2.10 Znázornění průběhu distribuční funkce k příkladu 2.13
Obr. 2.11 Znázornění průběhu frekvenční funkce k příkladu 2.13
Vypočtené hodnoty frekvenční a distribuční funkce jsou uvedené v tabulce 2.4. Obr. 2.10
znázorňuje průběh distribuční funkce a Obr. 2.11 znázorňuje průběh frekvenční funkce.
Teorie grafu
23
Příklad 2.14
Náhodná veličina X má pravděpodobnostní funkci P(X). Jaká je pravděpodobnost, že
nabude hodnoty a) menší než 3 (x < 3), b) větší než 4 (x > 4), c) větší než 1 a menší než 4 (1 <
x < 4).
⎧3
x
⎪ ⋅ 0,7 ;
P( X ) = ⎨ 7
⎪⎩0;
pro x = 1, 2, 3; ,... , n
pro ostatní x,
Řešení:
i −1
F ( xi ) = ∑ f (xk );
k =1
a) x < 3
2
P( x < 3) = F (3) = ∑ f ( x 3 ) =
k =1
b) x > 4
3 7 3 49
3
21
⋅ + ⋅
=
+
= 0,51 .
7 10 7 100 10 100
⎛ 3 7 3 49 3 ⎛ 7 ⎞ 3 3 ⎛ 7 ⎞ 4 ⎞
P(x > 4) = 1 − P(x ≤ 4) = 1 − ⎜ ⋅ + ⋅
+ ⋅
+ ⋅⎜ ⎟ ⎟ =
⎜ 7 10 7 100 7 ⎜⎝ 10 ⎟⎠
7 ⎝ 10 ⎠ ⎟⎠
⎝
= 1 − (0,3 + 0,21 + 0,147 + 0,1029) = 0,2401.
2
c) 1 < x < 4
3
3 ⎛7⎞
3 ⎛7⎞
P(1 < x < 4) = ⋅ ⎜ ⎟ + ⋅ ⎜ ⎟ = 0,21 + 0,147 = 0,357.
7 ⎝ 10 ⎠
7 ⎝ 10 ⎠
Náhodná veličina nabývá hodnoty x menší než 3 (x < 3) s pravděpodobností 51 %,
hodnotu větší než 4 (x > 4) s pravděpodobností 24 % a hodnoty větší než 1 a menší než 4 (1 <
x < 4) s pravděpodobností 35,7 %.
2.7 Rozdělení náhodné veličiny
Zákony rozdělení pravděpodobností jsou užívány jako pravděpodobnostní modely, které
mají adekvátním způsobem popisovat děje a procesy závisející na náhodě. Pokud chceme
pracovat pouze s pojmem náhodné veličiny a vyhnout se manipulaci s jevy, je nutné, kromě
vztahu mezi elementárními jevy a hodnotou náhodné veličiny, definovat také
pravděpodobnosti všech jevů [Kába, B., 1999].
Rozdělení náhodné veličiny je pravidlo, které každé hodnotě nebo každému intervalu
hodnot přiřazuje pravděpodobnost, že náhodná veličina nabude této hodnoty nebo hodnoty
z tohoto intervalu.
Tabulka 2.5 Rozdělení náhodné veličiny
Rozdělení náhodné veličiny
Spojitá náhodná veličina
Diskrétní náhodná veličina
- Rovnoměrné - obecné
- Binomické
- Poissonovo
- normované
- Normální
- obecné
- normované
- Exponenciální
24 Teorie grafu
Spojitá náhodná veličina
2.7.1 Rovnoměrné rozdělení náhodné veličiny
a)
Obecné rovnoměrné rozdělení
Rovnoměrné rozdělení nabývají například chyby při zaokrouhlování čísel, chyby při
odečítání údajů z lineárních měřicích přístrojů, doby čekání na uskutečnění jevu opakujícího
se v pravidelných intervalech. Náhodná veličina X má rovnoměrné rozdělení, jestliže pro
všechna x ∈ 〈α; β〉 má konstantní hustotu pravděpodobnosti. Interval 〈α; β〉 vymezuje
hodnotu náhodné veličiny [Kába, B., 1999], [Vítečková, M.].
Tabulka 2.6: Charakteristiky rovnoměrného rozdělení
Hustota pravděpodobnosti:
⎧ 1
,
pro x ∈ α , β ,
⎪
f (x ) = ⎨ β − α
⎪0,
pro x ∈ (− ∞, α U β , + ∞ ).
⎩
Distribuční funkce:
⎧0,
pro x ∈ − ∞; α ,
⎪x
1
x −α
⎪
F ( x ) = ⎨∫
dx =
, pro x ∈ α ; β ,
β −α
⎪α β − α
⎪1,
pro x ∈ β ; +∞ .
⎩
(
)
(
)
Číselné charakteristiky
Střední hodnota:
β
1
β +α
dx =
µ = ∫ xf ( x )dx = ∫ x
2
β −α
−∞
α
+∞
Obr. 2.12 Hustota pravděpodobnosti
Rozptyl:
+∞
β −α
−∞
12
σ 2 = ∫ (x − µ )2 f ( x )dx =
Obr. 2.13 Distribuční funkce
Teorie grafu
25
Příklad 2.15
Při měření s přesností ± 0,5 mm je hustota pravděpodobnosti v celém intervalu konstantní.
Určete: a) kolik je f(x),
b) jaká je pravděpodobnost, že chyba bude omezena intervalem (-0,2; +0,2),
c) distribuční funkci F(x).
Řešení:
x ∈ − 0,5; +0,5 ⇒ α = −0,5; β = 0,5;
a)
f (x ) =
1
= k = 1;
β −α
P(− 0,2 < X < +0,2) =
b)
+0 , 2
+0 , 2
− 0, 2
− 0, 2
∫ f (x )dx = ∫ 1dx =0,4.
⎧0,
pro x ∈ ( − ∞; − 0,5);
x + 0,5
1
⎪⎪ x − α
=
= x + , pro x ∈ − 0,5; + 0,5 ;
F (x ) = ⎨
2
⎪ β − α 0,5 + 0,5
⎪⎩1,
pro x ∈ ( + 0,5; + ∞ ).
c)
Určili jsme hustotu pravděpodobnosti k = 1, chyba bude omezena intervalem (-0,2 < x <
0,2) s pravděpodobností 0,4. Distribuční funkce F(x) nabývá hodnot vypočtených výše.
b)
Normované rovnoměrné rozdělení
Při normovaném normálním rozdělení nabývá spojitá náhodná veličina hodnot z intervalu
〈0, 1〉, α = 0, β = 1, z toho vyplývají hodnoty číselných charakteristik:
střední hodnota
β +α
=
1
,
2
(
β − α )2
=
=
µr =
2
rozptyl
σ
2
r
12
1
.
12
Hustota pravděpodobnosti:
⎧1
f (x ) = ⎨
⎩0
pro x ∈ 0;1
pro x ∈ (− ∞;0 ) U (1;+∞ )
.
26 Teorie grafu
Obr. 2.14 Hustota pravděpodobnosti normovaného rovnoměrného rozdělení
Distribuční funkce:
(
⎧0
⎪⎪
F (x ) = ⎨ x
⎪
⎩⎪1
pro x ∈ − ∞; 0
)
pro x ∈ 0; 1
(
pro x ∈ 1; +∞
).
Obr. 2.15 Distribuční funkce normovaného rovnoměrného rozdělení
Transformace normovaného rovnoměrného rozdělení na obecné rovnoměrné rozdělení:
x k = µ x + 12σ x (rk − 0,5)
rk = 0,5 +
1
1
σ x 12
(x k − µ x )
obecné
normované
kde jsou:
rk - hodnoty normovaného rovnoměrného rozdělení,
xk - hodnoty obecného rovnoměrného rozdělení se střední hodnotou µx, a směrodatnou
odchylkou σ x .
Teorie grafu
27
2.7.2 Normální rozdělení náhodné veličiny
a) Označováno též obecné normální rozdělení [Kába, B., 1999], [Škrášek, J., Tichý, Z.,
1990], [Vítečková, M.]. Je velmi důležité, protože:
•
se nejčastěji vyskytuje,
•
mnoho jiných rozdělení se mu blíží,
•
řada jiných rozdělení se jím dá nahradit.
Pravidlo 3σ
Hodnoty náhodné veličiny jsou z intervalu x ∈ µ x − σ x ; µ x + σ x
s pravděpodobností 0,6824.
Hodnoty náhodné veličiny jsou z intervalu x ∈ µ x − 2σ x ; µ x + 2σ x
s pravděpodobností 0,9545.
Hodnoty náhodné veličiny jsou z intervalu x ∈ µ x − 3σ x ; µ x + 3σ x
s pravděpodobností 0,9973.
Distribuční funkci normálního rozdělení náhodné veličiny určíme podle vztahu:
F (x ) =
x
∫σ
−∞
1
x
2π
e
−
(t − µ x )2
2σ x2
dt .
Hustotu pravděpodobnosti normálního rozdělení náhodné veličiny určíme podle vztahu:
f (x ) =
1
σ x 2π
e
⎡ ( x − µ x )2 ⎤
⎢−
⎥
2σ x2 ⎥⎦
⎢⎣
.
Obr. 2.16 Hustota pravděpodobnosti obecného normálního rozdělení
28 Teorie grafu
b) Normované normální rozdělení
Jedná se o speciální případ obecného normálního rozložení, kdy µ u = 0, σ u2 = 1.
kde je:
u - označení náhodné veličiny s normovaným normálním rozdělením.
Obr. 2.17 Hustota pravděpodobnosti normovaného normálního rozdělení
Obr. 2.18 Distribuční funkce normovaného normálního rozdělení
σ u2 = 1 ⇒ σ u = 1 , µ u = 0 .
Distribuční funkci normovaného normálního rozdělení náhodné veličiny určíme podle
vztahu
F (u ) =
u
1
∫
−∞
e
2π
−
t2
2
dt ,
a hustotu pravděpodobnosti normovaného normálního rozdělení náhodné veličiny určíme
podle vztahu
f (u ) =
1
2π
e
−
u2
2
.
Hodnoty distribuční funkce normovaného normálního rozdělení jsou uvedeny v tabulce 2.7.
Teorie grafu
29
Tabulka 2.7 Hodnoty distribuční funkce normovaného normálního rozdělení
u
0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1,0
1,1
1,2
1,3
1,4
1,5
1,6
1,7
1,8
1,9
2,0
2,1
2,2
2,3
2,4
2,5
2,6
2,7
2,8
2,9
3,0
3,1
3,2
3,3
3,4
3,5
3,6
3,7
3,8
3,9
4,0
4,1
4,2
F(u)
0,5
0,53983
0,57926
0,61791
0,65542
0,69146
0,72575
0,75804
0,78814
0,81594
0,84134
0,86433
0,88493
0,90320
0,91924
0,93319
0,94520
0,95543
0,96407
0,97128
0,97725
0,98214
0,98610
0,98928
0,99180
0,99379
0,99534
0,99653
0,99744
0,99813
0,99865
0,99903
0,99931
0,99952
0,99966
0,99977
0,99984
0,99989
0,99993
0,99995
0,99997
0,99998
0,99999
u
0
-0,1
-0,2
-0,3
-0,4
-0,5
-0,6
-0,7
-0,8
-0,9
-1,0
-1,1
-1,2
-1,3
-1,4
-1,5
-1,6
-1,7
-1,8
-1,9
-2,0
-2,1
-2,2
-2,3
-2,4
-2,5
-2,6
-2,7
-2,8
-2,9
-3,0
-3,1
-3,2
-3,3
-3,4
-3,5
-3,6
-3,7
-3,8
-3,9
-4,0
-4,1
-4,2
F(u)
0,5
0,46017
0,42074
0,38209
0,34458
0,30854
0,27425
0,24196
0,21186
0,18406
0,15866
0,13567
0,11507
0,09680
0,08076
0,06681
0,05480
0,04457
0,03593
0,02872
0,02275
0,01786
0,01390
0,01072
0,00820
0,00621
0,00466
0,00347
0,00256
0,00187
0,00135
0,00097
0,00069
0,00048
0,00034
0,00023
0,00016
0,00011
0,00007
0,00005
0,00003
0,00002
0,00001
30 Teorie grafu
Pro záporné hodnoty platí vztah:
F (− u ) = 1 − F (u )
Transformace normovaného normálního rozdělení na obecné normální rozdělení
Pro transformaci platí vztah:
xk = µx + σxuk,
kde je:
uk - hodnota náhodné veličiny normovaného normálního rozdělení,
xk - vypočítané hodnoty obecného normálního rozdělení,
µx a σx - střední hodnota a směrodatná odchylka obecného normálního rozdělení.
Opačná transformace se provádí podle vztahu:
uk =
xk − µ k
σx
.
Příklad 2.16
Ze zkušenosti je známo, že hmotnost určitých výrobků má normální rozdělení se
směrodatnou odchylkou 1,1 g. Jaká je průměrná hmotnost těchto výrobků, jestliže pouze 3 %
výrobků váží méně než 448 g?
Řešení:
Hmotnost výrobků je náhodnou veličinou X s rozdělením N (µ , 1,12 ) . Ze zadání úlohy
vyplývá, že P(X < 448) = 0,03.
Pomocí vzorce:
⎛b−µ ⎞
⎛a−µ⎞
P(a < x < b ) = F ⎜
⎟ − F⎜
⎟
⎝ σ ⎠
⎝ σ ⎠
dostaneme:
⎛ 448 − µ ⎞
P(a < 448) = F ⎜
⎟ = 0,03.
⎝ 1,1 ⎠
Z tabulky hodnot normální distribuční funkce (tabulka 2.7) zjistíme, že
F(-1,88) = 0,03;
448 − µ
= −1,88 ⇒ µ = 450,068.
1,1
Hledaná průměrná hmotnost výrobku je µ = 450,068 g .
Teorie grafu
31
Transformace rovnoměrného rozdělení na normální rozdělení
Tato transformace vychází z centrální limitní věty Linberga a Lévyho [Kába, B., 1999].
Věta:
Sečteme-li dostatečný počet hodnot náhodné veličiny xi kde i = 1, 2, …, n, jež jsou
vzájemně nezávislé a mají totéž rozdělení s toutéž střední hodnotou µx a s tímtéž rozptylem
σ x2 , pak proměnná z vytvořená podle rovnice
1
⎡ n x − nµ ⎤
x⎥
⎢∑ i
⎦
nσ x2 ⎣ i =1
z=
,
s rostoucím n konverguje k normovanému normálnímu rozdělení
(z → u,
µ u = 0, σ u2 = 1) .
Pro transformaci normovaného rovnoměrného rozdělení na normované normální rozdělení
je výhodné, aby n = 12, protože
σ r2 =
1
, µr = 0,5 ;
12
pak
12
u = ∑ ri − 6 ,
i =1
kde je:
ri - hodnota náhodné veličiny normovaného rovnoměrného rozdělení,
u - hodnota náhodné veličiny normovaného normálního rozdělení.
32 Teorie grafu
Příklad 2.17
Hmotnost výrobku je vyhovující, pokud je v mezích 68 g až 69 g. Standardní hmotnost má
obecné normální rozdělení se střední hodnotou µx = 68,3 g a směrodatnou odchylkou σx =
0,2 g. Jaká je pravděpodobnost, že hmotnost bude v mezích 68 g až 69 g?
Řešení:
Transformace na hodnoty normovaného normálního rozdělení:
u1 =
x1 − µ x
u2 =
σx
x2 − µ x
σx
=
68 − 68,3
= −1,5 ;
0,2
=
69 − 68,3
= 3,5 ;
0,2
Protože hodnoty distribuční funkce jsou obvykle uváděny jen pro kladné hodnoty u,
využije se vztahu:
F(1,5) + F(-1,5) = 1 ⇒ F(-1,5) = 1 - F(1,5) = 0,0668.
P(68 < x < 69) = P(-1,5 < x <3,5) = F(3,5) - F(-1,5) = 0,933.
Hmotnost bude ve stanovených mezích 68 g až 69 g s pravděpodobností 93,3 %. Byly
použity hodnoty distribuční funkce normovaného normálního rozdělení z tabulky 2.7.
Příklad 2.18
Náhodná veličina x představující chybu měření má normální rozdělení se střední hodnotou
µx = 0,2 a rozptylem σ x2 = 0,64 . Je třeba určit pravděpodobnost, že absolutní hodnota bude
menší než jedna (|x| < 1).
Řešení:
N(0,2; 0,64), µx = 0,2, σ x2 = 0,64 .
P( x < 1) = P(− 1 < x < 1)
Transformace na normální rovnoměrné rozdělení:
uk =
xk − µ k
σk
; u k1 =
− 1 − 0,2
1 − 0,2
= −1,5; u k 2 =
= 1;
0,8
0,8
Z tabulky 2.7 jsou odečteny hodnoty distribuční funkce hodnot NV normovaného normálního
rozdělení.
P(− 1 < x < 1) = P (− 1,5 < u < 1) = F (1) − F (− 1,5 ) = F (1) − 1 + F (1,5 ) = 0,774
Absolutní hodnota x bude menší než jedna s pravděpodobností 77,4 %.
Teorie grafu
33
2.7.3 Exponenciální rozdělení náhodné veličiny
Náhodnou veličinou je obvykle čas, v němž nastane sledovaný jev. Pravděpodobnost, že
jev nastane v časovém okamžiku x. Používá se pro určování pravděpodobnosti, životnosti
zařízení, pro řešení problémů teorie hromadné obsluhy a pro řešení teorie grafů [Kába, B.,
1999].
Charakteristiky exponenciálního rozdělení
Hustotu pravděpodobnosti exponenciálního rozdělení náhodné veličiny (Obr. 2.19)
určíme podle vztahu
⎧λe − λx
f (x ) = ⎨
⎩ 0
pro x ≥ 0,
pro x < 0.
Obr. 2.19 Hustota pravděpodobnosti exponenciálního rozdělení
Distribuční funkci exponenciálního rozdělení náhodné veličiny (Obr. 2.20) určíme podle
vztahu:
⎧1 − e − λx
F (x ) = ⎨
⎩0
pro x ≥ 0
pro x < 0 .
Obr. 2.20 Distribuční funkce exponenciálního rozdělení
34 Teorie grafu
Číselné charakteristiky exponenciálního rozložení:
střední hodnota
µx =
1
λ
,
rozptyl
σ x2 =
1
λ
2
.
Pokud sledovaný jev může nastat až v čase a, kde a > 0, pak je hustota pravděpodobnosti:
f ( x ) = λe − λ ( x − a ) , pro x ≥ a
distribuční funkce:
F ( x ) = 1 − e − λ ( x − a ) , pro x ≥ a .
Grafy jsou posunuty. Rozptyl se nemění, střední hodnota je posunuta o hodnotu a (viz
obr.2.21).
σ x2 =
1
λ
2
; µx =
1
λ
+a.
Obr. 2.21 Grafy hustoty pravděpodobnosti a distribuční funkce
exponenciálního rozdělení posunutého o hodnotu a
Příklad 2.19
Střední doba čekání zákazníka na obsluhu v prodejně je 50 sekund. Doba čekání se řídí
exponenciálním rozdělením (pravděpodobnost, že zákazník nebude obsloužen s rostoucím
časem klesá exponenciálně). Jaká je pravděpodobnost, že náhodný zákazník bude obsloužen
dříve než za 30 sekund?
Řešení:
µ = 50s, µ =
1
λ
⇒λ =
P(0 < x < 30 ) = F (30 ),
F (30 ) = 1 − e
−
1
30
50
1
= 0,02;
50
= 0,451.
Zákazník bude obsloužen dříve než za 30 sekund s pravděpodobností 45,1 %.
Teorie grafu
35
Diskrétní náhodná veličina
2.7.4 Binomické rozdělení diskrétní náhodné veličiny
Předpokládejme, že určitý pokus opakujeme n-krát za stejných podmínek. V každém
pokusu může nastat náhodný jev A (úspěch pokusu) se stejnou pravděpodobností p a
nevyskytnout se (neúspěch pokusu) s pravděpodobností q = 1 – p [Kába, B., 1999].
Počet realizací náhodného jevu A (úspěchů) n nezávislých pokusů je zřejmě diskrétní
náhodnou veličinou x, jež může nabývat hodnot 0, 1, …, n. Vzhledem k nezávislosti pokusů
pro její frekvenční funkci platí:
⎛n⎞
n−k
f (k ) = P( x = k ) = ⎜⎜ ⎟⎟ p k (1 − p ) ,
⎝k ⎠
kde je:
k = 0, 1, …, n.
Charakteristiky binomického rozdělení
Frekvenční funkci (pravděpodobnost, že k pokusů končí zdarem) binomického rozdělení
diskrétní náhodné veličiny určíme podle vztahu
⎧⎛ n ⎞ k n − k ⎛ n ⎞ k
n−k
⎪⎜⎜ ⎟⎟ p q = ⎜⎜ ⎟⎟ p (1 − p ) , pro k = 1,2,3,..., n,
f (k ) = ⎨⎝ k ⎠
⎝k ⎠
⎪0,
pro k ≠ 1,2,3,..., n.
⎩
a distribuční funkci binomického rozdělení diskrétní náhodné veličiny určíme podle vztahu
⎧0,
⎪
k −1
⎪
F (k ) = ⎨ P( X ≤ k ) = ∑ f ( j ),
j =1
⎪
⎪1,
⎩
pro k < 0
pro k = 1, 2,..., n ,
pro k ≥ n
kde je
n - počet nezávislých dílčích pokusů,
k - počet pokusů končících zdarem s pravděpodobností p,
(n-k) - počet pokusů končících nezdarem s pravděpodobností q = 1 – p.
36 Teorie grafu
Číselné charakteristiky binomického rozdělení diskrétní náhodné veličiny
střední hodnota
µ k = np ,
rozptyl
σ k2 = npq = np(1 − p ) .
Příklad 2.20
Výrobní družstvo dodává výrobky, u kterých nebyla provedena kontrola jakosti, balené po
deseti kusech. Družstvo předpokládá, že každý balík, v němž je alespoň jeden výrobek vadný,
bude reklamován a zaručilo se, že při reklamaci vrátí peníze. Je známo, že pravděpodobnost
vyrobení kvalitního výrobku je 0,95 a že náklady na jeden balík jsou dvě koruny. Jakou by
mělo družstvo stanovit cenu jednoho balíčku, aby mohlo očekávat zisk 25 %?
Řešení:
n = 10;
p = 0,95;
q = 0,05;
cena (c) = ?;
k = 10;
f (10 ) ⋅ c − 2 = 0,5
⎫
2,5
⎪
= 4,50 Kč .
⎛10 ⎞ 10 0
⎬⇒c =
f (10 ) = ⎜⎜ ⎟⎟ p q = 0,5987 ⎪
0,5987
⎝10 ⎠
⎭
Jeden balíček by měl stát cca 4,50 Kč.
Teorie grafu
37
2.7.5 Poissonovo rozdělení diskrétní náhodné veličiny
Je vhodné pro velmi velký počet opakovaných nezávislých pokusů (počet opakovaných
pokusů je větší než třicet). Například počet vadných výrobků velké série, kdy
pravděpodobnost vyrobení vadného výrobku je malá (počet těžkých úrazů v jednom městě),
pravděpodobnost zdaru je malá. Poissonovo rozdělení je charakteristické tím, že jeho střední
hodnota µ k a rozptyl σ k2 se sobě rovnají [Kába, B., 1999].
Charakteristiky Poissonova rozdělení
Frekvenční funkci Poissonova rozdělení diskrétní náhodné veličiny určíme podle vztahu
⎧ λ k e −λ
, pro k = 0,1,2,...n
⎪
f (k ) = ⎨ k!
,
⎪0,
pro k ≠ 0,1,2,...n
⎩
kde je
λ > 0, λ = np.
Distribuční funkci Poissonova rozdělení diskrétní náhodné veličiny určíme podle vztahu
k −1
F (k ) = P( X < k ) = ∑ f ( j ) .
j =1
Číselné charakteristiky Poissonova rozdělení diskrétní náhodné veličiny
střední hodnota
µ k = λ,
rozptyl
σ k2 = λ .
Příklad 2.21
Telefonní ústředna zapojí během hodiny průměrně patnáct hovorů. Jaká je
pravděpodobnost, že během čtyř minut zapojí: 1) právě jeden hovor, 2) alespoň jeden hovor,
3) alespoň dva a nejvíce pět hovorů [Hebák, P., Kalounová, J., 1978].
Řešení:
Střední hodnota pro 4 minuty: λ = 1
ad 1) k = 1 ⇒ f (1) =
λe − λ
= 0,37;
1!
ad 2) k = 2, 3,..., n ⇒ f (2) + f (3) + ... + f (n ) = 1 − F (2) = 1 − f (0) − f (1) = 0,26;
ad 3) k = 2, 3, 4, 5 ⇒ f (2 ) + f (3) + f (4) + f (5) = 0,18 + 0,06 + 0,015 + 0,003 = 0,26.
38 Teorie grafu
Ústředna během čtyř minut zapojí právě jeden hovor s pravděpodobností 37 %, alespoň
jeden hovor s pravděpodobností 26 %, alespoň dva a nejvíce pět hovorů s pravděpodobností
26 %.
Příklad 2.22
Znázorněme
grafy
λ1 = 2, λ2 = 5, λ3 = 6, λ4 = 10.
k
λ1
λ2
λ3
λ4
k
λ1
λ2
λ3
λ4
0
frekvenční
funkce
Poissonova
Tabulka 2.8 Hodnoty frekvenční funkce
2
3
4
5
6
7
8
1
rozložení
9
pro
10
0,135 0,271 0,271 0,180 0,090 0,036 0,012 0,003 0,001 0,000 0,000
0,007 0,034 0,084 0,140 0,175 0,175 0,146 0,104 0,065 0,036 0,018
0,002 0,015 0,045 0,089 0,134 0,161 0,161 0,138 0,103 0,069 0,041
0,000 0,000 0,002 0,008 0,019 0,038 0,063 0,090 0,113 0,125 0,125
11
12
13
14
15
16
17
18
19
20
0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000 0,000
0,008 0,003 0,001 0,000 0,000 0,000 0,000 0,000 0,000 0,000
0,023 0,011 0,005 0,002 0,001 0,000 0,000 0,000 0,000 0,000
0,114 0,095 0,073 0,052 0,035 0,022 0,013 0,007 0,004 0,002
frekvenční funkce
0,30
0,25
λ1
f(k)
0,20
λ2
0,15
λ3
0,10
λ4
0,05
0,00
1
3
5
7
9
11
13
15
17
19
21
k
Obr. 2.22 Poissonovo rozdělení příklad 2.22
Protože je koeficient šikmosti větší než nula, jsou příslušné křivky asymetrické zprava.
Teorie grafu
39
3 Teorie grafů
Teorie grafů patří mezi relativně mladé matematické disciplíny. Jedná se o obor
matematiky, pomocí něhož lze formulovat a řešit mnoho problémů z různých oblastí,
nejčastěji celočíselné a kombinatorické povahy [Demel, J., 1988], [Sedláček, J., 1981].
3.1 Základní pojmy
Graf je určitý útvar (systém), který je možno znázornit obrázkem v rovině pomocí bodů (uzly
grafu) a spojnic mezi body (hrany grafu).
Orientovaný graf je trojice G = (V, E, ε) tvořená konečnou množinou prvků V, jejíž prvky
nazýváme uzly, konečnou množinou E, jejíž prvky nazýváme orientovanými
hranami a zobrazením ε : E → V2, které nazýváme vztahem incidence, a které
přiřazuje každé hraně e ∈ E uspořádanou dvojici uzlů.
Neorientovaný graf je trojice G = (V, E, ε) tvořená konečnou množinou V, jejíž prvky
nazýváme uzly, konečnou množinou E, jejíž prvky nazýváme neorientovanými
hranami a zobrazením ε (vztah incidence), které přiřazuje každé hraně e jedno nebo
dvouprvkovou množinu uzlů.
Cesta v grafu je posloupnost orientovaných hran, při které vždy následující hrany začínají
v uzlu, v němž končí předcházející hrana.
Cyklus (kružnice u neorientovaného grafu) je taková cesta, která začíná a končí v témže uzlu.
Řetěz je cesta bez ohledu na orientaci grafu.
Souvislý graf je graf, u kterého mezi všemi dvojicemi uzlů existuje alespoň jedna cesta.
Nesouvislý graf je graf, u kterého neexistuje alespoň jedna cesta mezi všemi dvojicemi uzlů.
Strom je takový graf, který neobsahuje žádný cyklus.
Podgraf původního grafu je graf, který vznikne tím, že vynecháme z grafu některé uzly a
příslušné hrany těchto uzlů.
Acyklický graf je graf, který neobsahuje žádný cyklus.
Ohodnocený graf (orientovaný, neorientovaný) je graf, ve kterém reálná funkce definovaná
na množině hran přiřazuje každé hraně nějakou hodnotu (například vzdálenost,
doba, energie…).
Síť je graf, který je konečný, souvislý, orientovaný, acyklický a ohodnocený, v němž existuje
jeden konečný a jeden počáteční uzel.
Konečný graf má konečný počet uzlů a hran.
Řezem sítě se nazývá množina všech hran, které spojují uzly množiny U1 s uzly množiny U2,
kdy U1 je množina uzlů, která obsahuje počáteční uzel a všechny uzly dosažitelné z
počátečního uzlu po nenasycené cestě. Množina uzlů U2 je taková množina, která
obsahuje koncový uzel a všechny zbývající uzly.
Kapacita řezu je číslo, které je tvořeno součtem kapacit (ohodnocení) všech hran řezu.
Minimální řez je řez, který má nejmenší kapacitu.
Multigraf je graf, v němž mezi některou dvojicí uzlů existuje v jednom směru větší počet
hran než jedna.
40 Teorie grafu
Druhy hran:
Tabulka 3.1 Druhy hran
Smyčky
Hrana, která inciduje s jedním
uzlem
Rovnoběžné hrany
Incidují se stejnými uzly.
Orientované hrany
Je naznačen směr orientace
Neorientované hrany
Násobné hrany
Jsou rovnoběžné hrany, které
jsou buď neorientované nebo
všechny souhlasně orientované.
Tabulka 3.2 Rozdělení hran a smyček
ROVNOBĚŽNÉ
HRANY
Násobné
Nenásobné
SMYČKY
Teorie grafu
41
Klasifikace grafů:
a)
Podle hran:
•
jednoduchý graf (orientovaný, neorientovaný) je graf, který obsahuje prosté
hrany bez smyček.
•
prostý graf (orientovaný, neorientovaný) je graf, v němž násobnost každé hrany je
nejvýše rovna jedné (neobsahují násobné hrany),
•
multigraf (orientovaný, neorientovaný) je graf, v němž násobnost alespoň jedné
hrany je větší než jedna (obsahují násobné hrany),
Tabulka 3.3 Typ grafu podle hran
TYP GRAFU
Jednoduchý graf
Prostý graf
Multigraf
NEORIENTOVANÝ
ORIENTOVANÝ
42 Teorie grafu
b)
Podle počtů hran a uzlů:
•
konečný graf (konečný počet hran a uzlů),
•
nekonečný graf (nekonečný počet hran a uzlů),
•
prázdný graf (prázdná množina uzlů a hran).
Úplný graf je graf, mezi jehož každými dvěma různými uzly existuje právě jedna hrana,
pak platí
⎛n⎞
⎜⎜ ⎟⎟ - počet hran
⎝ 2⎠
kde je:
n - počet uzlů
Obr. 3.1 Příklad úplného grafu
Podgraf – graf G´ je podgrafem grafu G, jestliže V´⊆ V, E´⊆ E a ε ′ je zúžením zobrazení
ε pro graf G´,
kde grafy
G´= (V´, E´, ε ′ ),
G = (V, E, ε ),
jsou buď oba orientované nebo oba neorientované.
Obr. 3.2 Podgraf úplného grafu z obrázku. 3.1
Faktor grafu – graf G´ je faktorem grafu G, jestliže graf G´je podgrafem grafu G, který
má stejnou množinu uzlů (V´ = V) a jeho množina hran E´ je podmnožinou množiny hran E
(E´⊂ E ) .
Teorie grafu
43
Obr. 3.3 Faktory úplného grafu z obrázku 3.1
Stupeň uzlu je počet hran incidujících s daným uzlem (smyčka se počítá dvakrát).
Přesuny z jednoho uzlu do druhého uzlu
Sled je uspořádaná posloupnost uzlů a hran (uzly a hrany se mohou opakovat).
S1 = (1, a, 2, b, 3, d, 4, e, 1)
S2 = (1, a, 2, c, 4, e, 1)
Obr. 3.4 Přesuny uzlů
Délka sledu:
l(S1) = a + b + d + e
l(S2) = a + c + e
počáteční uzel = koncový uzel ⇒ uzavřený sled
počáteční uzel ≠ koncový uzel ⇒ otevřený sled
Násobnost hrany – počet výskytů téže hrany v určitém sledu.
Tah je sled, v němž se žádná hrana nevyskytuje více než jednou.
Cesta je takový tah, v němž se každý uzel vyskytuje jen jednou.
Kružnice je uzavřená cesta (viz obr. 3.5).
Obr. 3.5 Kružnice – uzavřená cesta
44 Teorie grafu
3.2 Eulerovské tahy
Eulerovský tah je takový tah, který obsahuje všechny hrany právě jednou. Orientované
grafy obsahují orientované tahy a neorientované grafy obsahují neorientované tahy [Demel,
J., 1982], [Plesník, J., 1983].
•
Uzavřené Eulerovské tahy jsou takové tahy, u kterých je počáteční a koncový
uzel totožný.
•
Neuzavřené Eulerovské tahy jsou takové tahy, které nemají totožný počáteční a
koncový uzel.
“Jednotažky“ jsou všechny hrany nakresleny jedním tahem.
Obr. 3.6 Neuzavřená jednotažka
Obr. 3.7 Uzavřená jednotažka
Typy úloh
1. Rozhodnout, zda v daném grafu existuje otevřený nebo uzavřený Eulerovský tah.
2. V daném grafu sestrojit otevřený nebo uzavřený Eulerovský tah.
3. V daném grafu najít nejmenší počet tahů, nikoli Eulerovských, které pokrývají
všechny hrany grafu.
4. V daném souvislém grafu (mezi každými dvěma uzly existuje hrana), jehož hrany jsou
ohodnoceny kladnými čísly, máme za úkol najít nejkratší uzavřený sled, který
obsahuje každou hranu alespoň jednou. Obecně nazývána Úloha čínského pošťáka.
Věta 1:
Nechť graf G je neorientovaný, pak v grafu existuje neorientovaný uzavřený Eulerovský
tah právě tehdy, když každý uzel grafu je sudého stupně.
Věta 2:
Nechť graf G je orientovaný, pak v grafu G existuje orientovaný uzavřený Eulerovský
tah právě tehdy, když pro každý uzel grafu platí, že počet hran vstupujících do uzlu je roven
počtu hran z uzlu vystupujících.
Příklad 3.1
Máme město, které se rozkládá na dvou ostrovech a dvou březích, které jsou spojeny
sedmi mosty. Naším úkolem je určit, zda je možno projít přes každý ze sedmi mostů přesně
jednou, aniž bychom přeplavali řeku (viz obr. 3.8)?
Teorie grafu
45
Obr. 3.8 Sedm mostů a dva břehy daného města a odpovídající graf
Není možno projít přes každý most bez přeplavání řeky právě jednou, protože všechny
uzly mají lichý stupeň.
Algoritmus pro hledání uzavřeného Eulerovského tahu
Musí být zajištěna platnost věty 1 nebo 2. V algoritmu se pak střídavě prodlužují dvě fáze:
•
Existující tah prodlužujeme, dokud se nestane uzavřeným.
•
Uzavřený tah kontrolujeme, zda je Eulerovský. Při kontrole procházíme podél tahu
a v každém uzlu x testujeme, zda v okolí uzlu x existuje hrana, která dosud neleží
v tahu. Jestliže ano, pak přerušíme kontrolu, tah v uzlu x rozpojíme a začneme jej
prodlužovat. Prodlužování skončí v uzlu x. Po rozpojení nového a starého tahu
pokračujeme v kontrole počínaje uzlem x a postupujeme podél nové části tahu.
Takto je zajištěno, že jak při prodlužování, tak i při kontrole postupujeme podél
každé hrany pouze jednou. Celý postup je tedy velmi rychlý.
Příklad 3.2
Sestrojme uzavřený orientovaný Eulerovský tah (viz obr. 3.9) pomocí výše uvedeného
postupu.
Obr. 3.9 Graf k příkladu 3.2
Podle algoritmu pro hledání uzavřeného Eulerovského tahu je pro graf na obr. 3.9 sled
hran uzavřeného tahu: 1 – 8 – 7 – 4 – 3 – 2. Při kontrole zjistíme, že v uzlu, ve kterém končí
hrana 8 vychází hrana 6 a vstupuje hrana 5, takže Eulerovský tah upravíme 1 – 8 – 6 – 5 – 7 –
4 – 3 – 2.
46 Teorie grafu
Věta 3:
Nechť G je neorientovaný souvislý graf, který obsahuje k uzlů lichého stupně, pak
nejmenší počet neorientovaných tahů pokrývajících všechny hrany grafu je k/2.
Počet uzlů lichého stupně v grafu (obr. 3.10): k = 4 ⇒ 2 tahy.
Obr. 3.10 Graf potvrzující větu 3
Věta 4:
V souvislém orientovaném grafu je právě jeden Eulerovský tah neuzavřený právě tehdy,
když graf je souvislý a existují-li v něm dva uzly u1, u2, pro které platí (viz obr. 3.11):
d + (u1 ) = d − (u1 ) − 1,
d + (u 2 ) = d − (u 2 ) + 1,
kde je:
d + ( u1) - počet hran vstupujících do uzlu u1,
d - ( u2) - počet hran vystupujících z uzlu u2.
Pak uzel u1 je počáteční uzel a uzel u2 je koncový uzel neuzavřeného Eulerovského tahu.
Pro ostatní uzly platí d+(u) = d -(u).
u1 = 4 – 3 – 2 – 1 – 4 – 2 = u2
Obr. 3.11 Graf potvrzující větu 4
Teorie grafu
47
Algoritmus čínského pošťáka
Pošťák musí při roznášce pošty alespoň jedenkrát projít každou ulicí svého rajónu. Jak má
postupovat, aby ušel co nejméně kilometrů, to znamená, aby kratší cesty procházel vícekrát
[Demel, J., 1982]?
1. Zjistit, zda jsou všechny uzly sudého stupně.
2. Není-li tomu tak, musíme přidat hrany, abychom tuto podmínku splnili a to
provedeme tak, že spojíme uzly s lichým stupněm nejkratší cestou.
3. Provedeme kontrolu, zda cesta pošťáka je opravdu nejkratší.
Příklad 3.3
Řešme úlohu čínského pošťáka pro graf na obr. 3.12.
Řešení:
Hrany tvořící nejlevnější perfektní párování jsou označeny tučně (viz obr. 3.13). Stupně
všech jeho uzlů jsou sudé, nečiní tedy potíže nalézt v tomto grafu uzavřený Eulerovský tah.
Obr. 3.12 Graf k úloze čínského pošťáka – příklad 3.3
Obr. 3.13 Hrany tvořící nejlevnější perfektní párování – tučné hrany
48 Teorie grafu
3.3 Hamiltonovské cesty a kružnice
•
Hamiltonovská cesta v grafu G je cesta, která obsahuje každý uzel grafu G právě
jednou.
•
Hamiltonovská kružnice (cyklus) v grafu G je kružnice (cyklus), která prochází
každým uzlem grafu, u které je počáteční a koncový uzel totožný [Demel, J.,
1982].
Typy úloh:
1.
2.
3.
4.
Najít Hamiltonovskou kružnici (cyklus) - (úloha obchodního cestujícího).
Najít Hamiltonovskou cestu (mezi libovolnými dvěma uzly).
Najít Hamiltonovskou cestu, jejíž krajní uzel je fixován.
Najít Hamiltonovskou cestu, jejíž oba krajní uzly jsou fixovány.
Pro řešení těchto typů úloh neexistuje žádný efektivní algoritmus.
Příklad 3.4
Máme za úkol najít Hamiltonovu kružnici a nejkratší cestu (viz obr. 3.14).
Obr. 3.14 Graf k příkladu 3.4
Délka Hamiltonovské kružnice: A – B – C – D – A = 23 jednotek.
Nejkratší délka cesty A – D – C – B – C – A = 20 jednotek.
Rozhodovací strom
•
Používá se pro jednoduché úlohy.
•
V každém uzlu rozhodujeme, kam jít dál, ale nesmíme se vrátit do uzlu, ve kterém
jsme byli.
Teorie grafu
49
Příklad 3.5
Máme za úkol najít Hamiltonovu kružnici pomocí rozhodovacího stromu (viz obr. 3.15).
Obr. 3.15 Síťový graf k příkladu 3.5
Řešení:
Tam, kde nelze dále pokračovat, je značka X.
D
B
C
G
F
E
F X
G
E
D X
G
E
F
A
1
D X
B X
C
A
D
G
G
E X
E X
D X
F
C X
E
G
D
C
B
A
2
B X
F
C
E
C
G
D
D
G X
G
B X
F X
C
B X
F X
Obr. 3.16 Rozhodovací strom - příklad 3.5
Pro graf na obr. 3.16 existují dvě Hamiltonovské kružnice, které se liší jen pořadím uzlů.
Hamiltonovské kružnice:
První: A – F – E – G – D – C – B – A.
Druhá: A – B –C – D – G – E – F – A.
50 Teorie grafu
3.4 Metoda minimální cesty
a)
Orientovaný graf:
Pro určení minimální cesty v orientovaném ohodnoceném grafu se využívá Bellmanův
princip optimality [Demel, J., 1988].
•
je-li cesta z A do C optimální, pak na této cestě musí ležet i cesta z B do C
Obr. 3.17 Podmínka Bellmanova principu optimality
Podmínky pro graf, aby mohl být použít Bellmanův princip optimality:
•
všechny hrany grafu jsou ohodnoceny t ij ,
•
v grafu nesmí být cykly ⇒ i < j (hrana musí vystupovat z uzlu i s číslem menším a
vstupovat do uzlu j s číslem větším),
Obr. 3.18 Podmínka užití Bellmanova principu optimality
•
nesmí být rovnoběžné hrany – odstraníme pomocí fiktivních hran s nulovým
ohodnocením.
Obr. 3.19 Tvorba fiktivního prvku
Hrana spojující uzly i, k je fiktivní hrana s nulovým ohodnocením.
Postup určování cesty v orientovaném grafu:
Při hledání minimální (maximální) cesty v ohodnoceném orientovaném grafu postupujeme
od koncového uzlu k počátečnímu uzlu.
Teorie grafu
51
Ohodnocení v koncovém uzlu (Tn = 0) položíme rovno nule. Pak postupujeme proti směru
orientace hran k počátečnímu uzlu a u každého uzlu si pamatujeme minimální (maximální)
hodnotu součtu ohodnocení hran předchozí části cesty a směr, odkud jsme do daného uzlu
došli. Hodnota v počátečním uzlu dává celkovou nejkratší (nejdelší) cestu v grafu.
Tabulka 3.4 Stanovení délek cesty
Nejkratší cesta
Ti = min ( Tj + tij )
Tn = 0
Nejdelší cesta
Ti = max ( Tj + tij )
Tn = 0
Nejkratší cesta:
9
2
3
1
1
4
5
10
7
4
2
6
6
5
7
3
11
4
8
5
8
15
Obr. 3.20 Příklad orientovaného grafu – nejkratší cesta
Nejkratší cesta vede uzly: 1 – 2 – 3 – 4 – 6,
Délka cesty: 3 + 1 + 2 + 4 = 10 jednotek.
Nejdelší cesta:
9
2
3
1
20
1
4
5
19
16
4
2
6
6
5
3
4
7
8
5
8
15
Obr. 3.21 Příklad orientovaného grafu – nejdelší cesta
Nejdelší cesta vede uzly: 1 – 3 – 5 – 6,
Délka cesty: 5 + 7 + 8 = 20 jednotek.
52 Teorie grafu
b)
Neorientovaný graf
5
2
2
4
0
4
1
1
2
5
3
3
2
3
5
Obr. 3.22 Příklad neorientovaného grafu
Postup hledání minimální cesty v neorientovaném grafu:
Graf musí být ohodnocený, neorientovaný, bez číslování uzlů.
1. Označíme počáteční uzel číslem nula.
2. V každém dalším kroku budeme ohodnocovat neohodnocené uzly, které jsou spojeny
hranami s již ohodnocenými uzly a to tak, že je hodnotíme podle vztahu
[
]
U (t j ) = min U (t i ) + t ij .
kde je:
U( ti ) - hodnota ohodnoceného uzlu,
[
]
tij - hodnota hrany mezi ohodnoceným [U (t i )] a neohodnoceným U (t j ) uzlem.
3. Hodnota koncového uzlu nám dává hodnotu minimální cesty
4. Hrany, které leží na minimální cestě určíme podle vztahu
[
]
t ij = U (t j ) − U (t i ) ,
směrem od posledního uzlu k prvnímu.
Platí, že rozdíl hodnot sousedících uzlů musí být hodnota hrany.
a)
b)
5
1
2
4
0
2
1
4
0
3
5
2
1
1
3
3
3
2
2
3
c)
d)
2
2
0
5
4
4
1
1
3
3
2
0
3
2
5
5
2
4
4
1
1
5
3
3
3
2
Obr. 3.23 Postup ohodnocování uzlů
5
Teorie grafu
53
3.5 Metoda kritické cesty (CPM - Critical Path Method)
Pro řešení metodou kritické cesty využíváme tzv. síťový graf, který se skládá z uzlů a
orientovaných hran. Hrany odpovídají jednotlivým dílčím činnostem úkolu. Danou činnost
jednoznačně určují počáteční a koncový uzel, kterými je každá činnost ohraničena. Činnost
označujeme uspořádanou dvojici čísel (i, j), přičemž musí platit i < j, tj. v grafu se nevyskytují
cykly a rovnoběžné hrany [Víteček, A., Wawrziczková, M., 1988], [Vítečková, M.]).
Na realizaci činnosti je třeba určité doby, tzv. doby trvání činnosti tij, a vynaložení
určitých nákladů.
Některé činnosti musí být vykonány v určitém časovém pořadí, proto je třeba do síťového
grafu zavést ještě fiktivní činnosti (obr. 3.24 b) s nulovou dobou trvání, které vyjadřují vazby
a závislosti mezi činnostmi.
Síťovým grafem G rozumíme tedy dvojici množin: množinu uzlů V a množinu činností E
(množinu hran). Síťový graf zapisujeme ve tvaru G = (V, E).
a)
b)
Obr. 3.24 Znázornění činnosti: a) skutečné, b) fiktivní
Příklad 3.6
Síťový graf G na obr. 3.25 popíšeme množinou uzlů V a množinou hran E.
Obr. 3.25 Síťový graf k příkladu 3.6
Řešení:
Pro síťový graf podle obr. 3.25 platí G = (V, E),
kde je:
V = [1, 2, 3, 4],
E = [(1; 2), (1; 3), (2; 3), (2; 4), (3; 4)].
54 Teorie grafu
Posloupnost hran v síťovém grafu, u které koncový uzel každé hrany (mimo poslední) se
shoduje s počátečním uzlem následující hrany, se nazývá cesta. Součet dob trvání všech
činností tvořící cestu je doba trvání cesty.
Maximální doba trvání cesty z uzlu 1 do uzlu j se nazývá: nejdříve možný termín uzlu j,
označuje se symbolem T jm a určí se ze vztahu:
(
)
T jm = max Ti m + t ij , T1m = 0 .
Je to nejdříve možný termín zahájení všech činností vystupujících z uzlu j.
Termín realizace úkolu Tnm je nejdříve možný termín uzlu n. Je to minimální doba nutná
ke splnění všech činností a tím i celého úkolu. Této době odpovídá maximální doba trvání
cesty z uzlu 1 do uzlu n.
Symbolem Ti p se označuje nejpozději přípustný termín uzlu i. Je roven rozdílu mezi
termínem Ti p = T jp − t ij . Předpokládá se, že nejdříve možný termín koncového uzlu Tnm je
zároveň roven jeho nejpozději přípustnému termínu Tnp . Nejpozději přípustný termín Ti p
vypočteme ze vztahu
(
)
Ti p = min T jp − t ij , Tnp = Tnm .
Uzly, pro které platí:
Tkm = Tkp , k ∈ V ,
nazýváme kritické uzly a činnosti, které spojují tyto kritické uzly nazýváme kritické
činnosti a vytvářejí kritickou cestu v grafu. Dojde-li k jakémukoli zpoždění v provádění
kritických činností, nutně dojde ke zpoždění splnění celého úkolu. V síťovém grafu může
existovat několik kritických cest. Znalost kritických cest, a tedy i kritických činností, je pro
řízení realizace celého úkolu velmi důležitá.
Časové rezervy
U každé operace rozeznáváme několik druhů časových rezerv (obr. 3.26):
Celková časová rezerva činnosti - představuje časový interval, ve kterém lze posunout
celou dílčí akci, aniž by se tím ovlivnil výsledný plánovaný termín. Počítáme ji podle vztahu:
Rijc = T jp − Ti m − t ij .
Volná časová rezerva je takový časový interval, o který lze prodloužit nebo posunout
činnost, aniž by byla ovlivněna činnost na ni navazující. Tuto rezervu počítáme podle vztahu:
Rijv = T jm − Ti m − t ij .
Nezávislá časová rezerv, je to množství času, o který může být činnost prodloužena, aniž
by se tím ovlivnila kterákoliv jiná činnost síťového grafu. Výpočet se provede dle vztahu:
Rijn = max (0, T jm − Ti p − t ij ) .
Teorie grafu
55
Mezi jednotlivými časovými rezervami platí vztah:
Rijc ≥ Rijv ≥ Rijn .
Kritické činnosti mají nulové celkové časové rezervy ( Rijc = 0 ).
Obr. 3.26 Vzájemné vztahy mezi časovými rezervami
Subkritické činnosti jsou činnosti s malou celkovou časovou rezervou Rijc ≤ δ ,
kde je:
δ - předem zvolená minimální rezerva (závisí na povaze realizovaného úkolu).
Síťový graf má tyto základní vlastnosti:
•
Každý síťový graf musí mít vždy jeden počátek, ze kterého hrany pouze vystupují,
a jeden konec, do kterého hrany pouze vstupují. Tuto podmínku lze splnit vždy
pomocí fiktivních činností (viz obr. 3.27 a).
•
Každá činnost může být zahájena jen tehdy, když jsou dokončeny všechny
předcházející činnosti .
•
Souběžné (paralelní) činnosti z důvodu jednoznačné identifikace musí být
odděleny fiktivní činností (viz obr. 3.27 b).
•
Délky hran neodpovídají dobám trvání činností.
•
Uzly lze očíslovat tak, aby platila nerovnost i < j. V tomto případě v síťovém grafu
nevystupují cykly (viz obr. 3.27 c).
56 Teorie grafu
Při sestavování síťových grafů je třeba provést rozbor činností a uvědomit si, které
činnosti bezprostředně předcházejí každé činnosti, které činnosti za danou činností
bezprostředně následují, které činnosti probíhají souběžně a které činnosti na sobě nezávisejí.
Všechny údaje o činnostech zapisujeme do tabulky, na jejíž základě pak sestavíme vlastní
síťový graf.
Obr. 3.27 Základní vlastnosti síťových grafů pro použití metody CPM
Pro očíslování uzlů v síťovém grafu můžeme použít následující algoritmus:
Očíslování uzlů síťového grafu:
•
První krok - počátek označit číslem 1.
•
Druhý krok - následujícím číslem označit libovolný neočíslovaný uzel, u kterého
jsou všechny předcházející uzly očíslovány (takový uzel vždy existuje, protože
síťový graf neobsahuje cykly). Krok 2 je třeba opakovat tak dlouho, až budou
všechny uzly očíslovány. Konec bude mít vždy největší číslo rovné počtu uzlů.
Teorie grafu
57
Po očíslování uzlů můžeme kritickou cestu a časové rezervy určit algoritmem:
Určení nejdříve možných termínů (postup vpřed):
První krok - položit T1m = 0 .
Druhý krok - pro j = 2, 3, …, n vypočítat:
(
)
T jm = max Ti m + t ij .
Určení nejpozději přípustných termínů uzlů (postup vzad):
Třetí krok - položit Tnp = Tnm , musí platit:
Tnp ≥ Tnm .
Čtvrtý krok - pro i = n – 1, n – 2, …, 1 vypočítat:
Ti p = min (T jp − t ij ) .
Určení časových rezerv činností:
Pátý krok - pro (i, j ) ∈ E vypočítat:
Rijc = T jp − Ti m − t ij ,
Rijv = T jm − Ti m − t ij ,
Rijn = max (0, T jm − Ti p − t ij ) ,
kde je:
T jm - nejdříve možný termín uzlu j,
T jp - nejpozději přípustný termín uzlu j,
t ij - doba trvání činnosti.
Určení kritické cesty
Šestý krok - vyznačit činnosti (i, j), pro které Rijc = 0. Tyto činnosti jsou kritické a určují
kritickou cestu.
U jednoduchých síťových grafů určení kritické cesty provádíme přímo v síťovém grafu
[Víteček, A., Wawrziczková, M., 1988]. Po očíslování uzlů postupujeme nejdříve od počátku
ke konci (postup vpřed) a počítáme všechny nejdříve možné termíny a zapisujeme je vlevo
(viz obr. 3.29). Pak postupujeme od konce k počátku (postup vzad) a počítáme nejpozději
přípustné termíny a zapisujeme je nad příslušnými uzly vpravo. Kritickou cestu vyznačují
uzly, u kterých nejdříve možné termíny jsou shodné s nejpozději přípustnými termíny
Ti m = Ti p . Celkové časové rezervy zapisujeme u jednotlivých činností do závorek
(viz obr. 3.28). U kritických činností všechny časové rezervy jsou nulové.
58 Teorie grafu
Příklad 3.7
Máme za úkol sestrojit zařízení, které se skládá ze tří částí. Podle tabulky 3.5 sestrojte
síťový graf a určete kritickou cestu a časové rezervy. Činnosti jsou označeny písmeny velké
abecedy. Například symbol A < B, C označuje, že činnost A předchází činnostem B a C a tak
dále. Doby trvání činností jsou uvedeny ve zvolených časových jednotkách (č.j.).
Tabulka 3.5 Vypočtené hodnoty k příkladu 3.7
činnost
i
vstupní návrh
fiktivní činnost
projekt
rozbor
objednávka 1
objednávka 2
objednávka 3
dodávka součástky 1
dodávka součástky 2
dodávka součástky 3
dílčí montáž
konečná montáž
A
B
C
D
E
F
G
H
I
J
K
L
1
2
2
3
4
4
4
5
6
7
8
9
j
t ij
2
3
4
4
5
6
7
8
8
9
9
10
2
0
5
3
1
2
1
3
3
4
4
5
podmínky
A < B, C
C < E, F, G
D < E, F, G
E<H
F<I
G<J
H<K
I<K
J<L
K<L
Řešení:
Nejdříve sestrojíme síťový graf s uvažováním omezení na časové činnosti, viz obr.3.28.
Přečíslování uzlů nemusíme provádět, protože vyhovuje podmínce i < j.
Obr. 3.28 Síťový graf k příkladu 3.7
Teorie grafu
59
V uzlech jsou hodnoty
T jm Ti p
i
číslo uzlu
Obr. 3.29 Označení uzlů na obr. 3.28
Výpočet nejdříve možných a nejpozději přípustných termínů provedeme přímo v síťovém
grafu. Například nejdříve možný a nejpozději přípustný termín uzlu 4 je :
(
= max (T
)
)= T
T4m = max Ti m + t i 4 = T2m + t 24 = 2 + 5 = 7 časových jednotek (i = 2, 3),
T4p
p
j
− t4 j
p
6
− t 46 = 9 − 2 = 7 časových jednotek (j = 5, 6, 7),
pro jiné uzly je postup stejný.
Kritická cesta vede přes uzly: 1 – 2 – 4 – 6 – 8 – 9 – 10 (zesílenou čarou).
Doba realizace celého úkolu: T10m = T10p = 21 č. j.
Časové rezervy při výpočtu je vhodné sestavit do tabulky (viz tabulka 3.6), protože
fiktivní činnost (2,3) slouží pouze k jednoznačné identifikaci činnosti (3, 4), dostaneme, že
činnost (3,4) má nezávislou časovou rezervu 2 č.j. Činnosti (4,5) a (5,8) mají celkovou
časovou rezervu 1 č. j. a činnosti (4,7) a (7,9) mají celkovou časovou rezervu 4 č.j. Zvolíme-li
δ = 1 č. j., dostaneme, že činnosti (4,5) a (5,8) lze považovat za subkritické činnosti,
kde je:
δ - předem zvolená minimální rezerva.
Tabulka 3.6 Časové rezervy k příkladu 3.7
i
A
B
C
D
E
F
G
H
I
J
K
L
1
2
2
3
4
4
4
5
6
7
8
9
j
t ij
Rijc
Rijv
Rijn
2
3
4
4
5
6
7
8
8
9
9
10
2
0
5
3
1
2
1
3
3
4
4
5
0
2
0
2
1
0
4
1
0
4
0
0
0
0
0
2
0
0
0
1
0
4
0
0
0
0
0
2
0
0
0
0
0
0
0
0
60 Teorie grafu
Agregace a desagregace síťových grafů
Každý síťový graf svojí strukturou odpovídá úrovni řízení, pro kterou je určen. Pro vyšší
úrovně je méně podrobný – je agregován. Agregace se týká nejen činností, ale i dob jejich
trvání. Při agregaci síťového grafu je třeba vyznačit důležité tzv. klíčové uzly, které
v agregovaném síťovém grafu mají zůstat. Dobu trvání agregované činnosti určuje největší
doba trvání cesty z jejího počátečního do jejího koncového uzlu. Mezi dvěma klíčovými uzly
uvažujeme činnost tehdy, existuje-li mezi těmito uzly cesta ve výchozím síťovém grafu,
respektive tvoří-li tato činnost cestu s nejdelší dobou trvání mezi těmito uzly.
Obr. 3.30 Znázornění agregace a desagregace síťových grafů
Agregace a desagregace síťového grafu umožňuje použití metody kritické cesty s výhodou
v hierarchické struktuře řízení. Je to také jeden z hlavních důvodů jejího využívání při
plánování a řízení realizace složitých úkolů, především rozsáhlých projektů s počtem činností
až do několika desetitisíců. Metoda kritické cesty je však s úspěchem používána i pro nevelké
projekty, ve kterých vystupuje pouze několik desítek činností.
Teorie grafu
61
3.6 Metoda PERT
Je zobecněním metody kritické cesty(CPM). Tato metoda se používá k řízení složitých
akcí majících stochastickou povahu. Zde se doba trvání každé dílčí činnosti chápe jako
náhodná proměnná mající určité rozložení pravděpodobnosti. Empiricky bylo zjištěno, že
v praxi toto nejlépe vystihuje tzv. beta rozdělení, které lépe vystihuje proměnlivost
provozních podmínek (například důlní provoz).
Odhady dob trvání jednotlivých činností
Momenty beta rozdělení se vypočítávají na základě odhadů expertů daného oboru, kteří
dovedou odhadnout rizika a podmínky realizace dílčích činností, za které nesou odpovědnost
[Víteček, A., Wawrziczková, M., 1988], [Vítečková, M.].
Tyto odhady se opírají o možnost vyjádření ve třech časových charakteristikách:
•
Optimistický odhad a uvažuje nejkratší dobu trvání činnosti s hypotetickou
četností 1:100 (Hypotetická četnost 1:100 znamená, že kdybychom 100x dělali
tutéž činnost za stejných podmínek, tak by se nám podařilo v čase a realizovat
činnost právě jednou).
•
Modus (nejpravděpodobnější odhad) m je to nejpravděpodobnější hodnota doby
trvání činnosti.
•
Pesimistický odhad b předpokládá nejdelší dobu trvání činnosti s hypotetickou
četností 1:100.
Metoda PERT se opírá o Ljapunovu centrální limitní větu, která předpokládá
nezávislost náhodných proměnných.
Při provádění odhadů se berou v úvahu jen ty vlivy, které je možno klasifikovat jako
náhodné jevy:
•
vliv počasí u práce venku,
•
vliv organizace práce,
•
vliv kvalifikace,
•
vliv pracovní morálky a disciplíny,
•
výkonnost,
•
poruchovost a podobně.
Na základě tří odhadů lze konstruovat hypotetickou křivku funkce hustoty
pravděpodobnosti ve třech variantách. Symetrická funkce vznikne v případě, že střední doba
trvání dílčí činnosti je rovna modusu. Je nutno podotknou, že většina odhadců se jistí poměrně
vysokou hodnotou pesimistického odhadu, proto je křivka hustoty nejčastěji zkosena vpravo
(obr. 3.31 vlevo).
62 Teorie grafu
Obr. 3.31 Typické průběhy funkce hustoty pravděpodobnosti
Pro hustotu pravděpodobnosti platí vztah:
+∞
∫ f (t )dt = 1.
−∞
Číselné charakteristiky určíme takto:
Očekávaná doba trvání dané činnosti vypočítáme podle empirického vztahu:
te =
a + 4m + b
,
6
rozptyl (variaci, disperzi) vypočítáme podle vztahu:
2
⎛b−a⎞
σ =⎜
⎟ ,
⎝ 6 ⎠
2
te
a směrodatnou odchylku doby trvání činnosti vypočítáme podle vztahu:
σt =
e
b−a
.
6
Je-li činnost určena jen optimistickým odhadem (a) a pesimistickým odhadem (b),
určíme číselné charakteristiky takto:
očekávaná doba trvání dané činnosti vypočítáme podle empirického vztahu:
te =
3a + 2b
,
5
rozptyl (variaci, disperzi) doby trvání činnosti vypočítáme podle vztahu:
σ t2 =
e
(b − a ) ,
5
a směrodatnou odchylku doby trvání činnosti vypočítáme dle vztahu:
σt =
e
b−a
,
5
Při určování kritické cesty v grafu postupujeme stejně jako u metody CPM, ale navíc
počítáme v každém uzlu cestou vpřed ještě rozptyl, jako součet rozptylů předchozích činností,
viz příklad 3.8.
Teorie grafu
63
V koncovém uzlu budeme mít hodnotu TE – očekávaný termín realizace celého úkolu a
její rozptyl σ T2E .
Protože se pracuje jen s očekávanými dobami trvání činnosti t eij , je třeba věnovat
zvýšenou pozornost i očekávaným sub-kritickým cestám, protože očekávané kritické
činnosti se mohou změnit v nekritické a sub-kritické na kritické.
Analýza pravděpodobnosti dodržení plánovaných termínů
Pokud je zadán plánovaný termín ukončení celého úkolu TP, pak pro odhad
pravděpodobnosti, že tento termín bude dodržen, platí:
⎛ T − TE
P(T ≤ TP ) = F ⎜ P
⎜ σT
E
⎝
⎞
⎟
⎟
⎠
kde je:
TP - plánovaný termín ukončení celého úkolu,
TE - očekávaný termín realizace celého úkolu,
⎛ T − TE
F⎜ P
⎜ σT
E
⎝
⎞
⎟ = F (u ) - distribuční funkce normované náhodné veličiny u.
⎟
⎠
Jestliže platí:
TP = TE,
pak:
P(TE ≤ TP ) = F (0 ) = 0,50 .
Můžeme tedy s 50 % pravděpodobností očekávat, že dojde k dodržení stanoveného termínu.
Jestliže platí:
TP > TE,
pak:
u > 0 a P(T ≤ TP ) > 0,5 .
Naopak pro
TP < TE
je vždy:
P(T ≤ TP ) < 0,5 .
Praxe ukazuje, že pravděpodobnost dodržení plánovaného termínu Tp v rozsahu 0,4 - 0,6
(40 – 60 %) v dostatečném stupni zabezpečuje realizaci úkolu. Hodnoty převyšující
0,6 (60 %) svědčí o nadbytečném využívání zdrojů a hodnoty pod 0,4 (40 %) signalizují
nutnost lepšího zajištění činností ležících na cestě do daného uzlu (přiřazení dalších zdrojů,
zlepšení organizace práce atd.).
64 Teorie grafu
V případě vystupování více očekávaných kritických cest je třeba věnovat větší pozornost
očekávané kritické cestě s největším rozptylem.
Metoda PERT je výpočetně náročnější než metoda kritické cesty. Dovoluje však
kvalitativně i kvantitativně odhadnout pravděpodobnost realizace jak jednotlivých činností,
tak i celého úkolu.
Příklad 3.8
Máme za úkol pomocí metody PERT určit očekávaný termín realizace úkolu, jeho
směrodatnou odchylku a očekávané celkové časové rezervy. Naším dalším úkolem bude určit
pravděpodobnost dodržení plánovaného termínu TP = 24 a 30 časových jednotek (č. j.)
[Víteček, A., Wawrziczková, M., 1988].
Tabulka 3.7 Zadání k příkladu 3.8
činnost
i
j
a
m
b
te
σ t2
omezení
Rijc
A
B
C
D
E
F
G
1
2
2
3
3
4
5
2
3
4
4
5
5
6
2
5
2
0
3
2
1
3
11
2
0
5
9
5
4
11
2
0
13
10
15
3
10
2
0
6
8
6
0,11
1
0
0
2,78
1,78
5,44
A < B, C
B < E, F
C<F
0
0
8
0
2
0
0
e
E<G
F<G
Řešení:
Doby te v tabulce 3.7 byly dopočteny pomocí vztahu
te =
a + 4m + b
6
a hodnoty σ t2e pomocí vzorce:
⎛b − a⎞
⎟
⎝ 6 ⎠
2
σ t2 = ⎜
e
V uzlech jsou rozmístěny hodnoty takto
i
∑σ
Ti m
Ti P
2
Obr. 3.32 Označení v uzlu u metody PERT
kde i je číslo uzlu
Teorie grafu
65
Obr. 3.33 Výsledný síťový graf - příklad 3.8
Z grafu odečteme hodnoty pro realizaci celého úkolu:
σ T2 = 8,33 ⇒ σ T = 2,89 č. j.
E
E
TE = 27 č. j.
Pravděpodobnost dodržení plánovaného termínu TP = 24 č.j. (viz tab. 2.7):
⎛ 24 − 27 ⎞
P(T ≤ 24) = F ⎜
⎟ ⇒ F (u ) = F (− 1,04) ⇒ F (u ) = 0,15.
⎝ 2.89 ⎠
Pravděpodobnost dodržení plánovaného termínu TP = 30 č.j. (viz tab. 2.7):
⎛ 30 − 27 ⎞
P(T ≤ 30 ) = F ⎜
⎟ ⇒ F (u ) = F (1,04) ⇒ F (u ) = 0,85.
⎝ 2.89 ⎠
Očekávané celkové časové rezervy pro jednotlivé činnosti jsou uvedeny v tabulce 3.7.
Pravděpodobnost dodržení plánovaného termínu TP(24) = 15 % a TP(30) = 85 %. Výsledný
síťový graf je uveden na obr. 3.33.
3.7 Propustnost dopravní sítě
Používá se:
•
při řešení dopravního problému,
•
při přepravě nějaké látky a podobně, přičemž je třeba nadimenzovat potrubí (cestu,
kabel), kterým proteče jen určité množství látky.
Použijeme vždy neorientovaný ohodnocený graf, kde hrany jsou trasy a uzly jsou
křižovatky. Musí být jeden zdroj u (počáteční uzel) a jeden spotřebič v (koncový uzel). Pokud
je více zdrojů, je třeba je sloučit do jednoho zdroje a propustnost nových hran se rovná
kapacitě dílčích zdrojů. To samé je také u spotřebičů. Každá hrana je ohodnocena takzvanou
propustností hrany C(h) a znamená, kolik maximálně může protéct látky.
Tok hranou F(h) je skutečné množství, které hranou proteče
F (h ) ≤ C (h ) .
66 Teorie grafu
Úkolem je určit:
•
propustnost celé dopravní sítě C*(u, v), to znamená maximální množství, které
může sítí protéct ze zdroje do spotřebiče,
•
tok dopravní sítí F(u, v), tj. skutečné množství, které proteče sítí ze zdroje do
spotřebiče
(
)
F (u , v ) ≤ C * u , v .
Dále je třeba udělat z grafu orientovaný acyklický graf. Hrany, kterými neprotéká žádná
látka, musíme vyloučit, jinak by mohl vzniknout sací efekt. V každém uzlu platí Kirchhoffovy
zákony (platí i pro zdroj a spotřebič).
Hledáme hranový řez mezi uzly u a v.
C (k) – hranový řez
C (kmin) – minimální hodnota hranového řezu
C (kmin) = C*(u,v)
Hranový řez mezi uzly u a v v souvislém neorientovaném grafu G je taková množina hran
K, pro které platí:
•
Graf G, který má množinu hran zmenšenou o K , má právě dvě komponenty,
přičemž uzel u leží v jedné z nich a uzel v leží v druhé.
•
Je-li množina hran K´ podmnožinou množiny K (K´⊂ K a zároveň K´≠ K), pak
v grafu G, který má množinu hran K´, existuje sled mezi uzly u a v.
Metody k určení minimálního hranového řezu C (kmin)
a) Metoda dolní cesty
•
Úprava grafu na jeden zdroj a jeden spotřebič.
•
Překreslení grafu tak, aby uzly u a v ležely na hranici grafu.
Obr. 3.34 Zavedení pomocné hrany r0
Teorie grafu
67
•
Zavedeme pomocnou hranu r0 s ohodnocením nula, která rozdělí graf na dvě
oblasti E1 a E2
•
Na hranici oblasti E1 vybereme hranu s nejmenším ohodnocením a tuto hranu
vynecháme, zvětší se oblast E2.
•
Ohodnocení vypuštěné hrany se zapíše do hranatého řezu a graf překreslíme (viz
obr. 3.35) tak, abychom snížili krajní hrany, které sousedily s E1 o hodnotu
vypuštěné hrany.
Obr. 3.35 Ohodnocení vypuštěné hrany
•
Toto opakujeme tak dlouho, až se nám graf rozpadne na dvě komponenty.
•
Pokud je více hran se stejným ohodnocením, vypustíme všechny hrany, ale do
hranového řezu zapíšeme pouze jednu (viz obr. 3.36 a obr. 3.37).
Obr. 3.36 Vypuštění hran se stejným ohodnocením
68 Teorie grafu
Obr. 3.37 Výsledný graf
b) Metoda vytvoření duálního grafu
Sestrojení duálního grafu GD: Do každé oblasti grafu umístíme jeden uzel a pro každou
hranu K sestrojíme hranu KD spojující uzly duálního grafu GD, které odpovídají oblastem
grafu G incidentním s hranou K. Oblast grafu je uzavřená část grafu vymezená hranami.
První krok: Graf rozdělíme na oblasti.
Obr. 3.38 Rozdělení grafu na oblasti
Druhý krok: Stávající graf překreslíme do duálního grafu - oblasti se stávají uzly.
Obr. 3.39 Výsledný duální graf
Teorie grafu
69
Hledáme minimální cestu z E1 do E2 a to je:
C (kmin) = C * (u, v ) .
Typy úloh
•
dopravní úlohy (kapacita silnic, rozvod vody, plynu a podobně),
•
přiřazovací úlohy (přiřazení n-úkolů m-pracovníkům),
•
jízdní řády.
Příklad 3.9
Máme za úkol najít minimální hranový řez pro graf na obr. 3.40.
Obr. 3.40 Zadaný graf k příkladu 3.9
Řešení:
Nejdříve upravíme graf tak, aby uzly zdroje u a spotřebiče v byly na okraji grafu, přidáme
pomocnou hranu s ohodnocením nula a pak postupujeme podle algoritmu dolní cesty.
Obr. 3.41 Výsledný graf k příkladu 3.9
C(k) = 1 + 1 + 1 +1 + 2 = 6 jednotek.
Minimální hranový řez je C(kmin) = 6 jednotek (viz obr. 3.41).
70 Teorie grafu
Seznam literatury
CYHELSKÝ, L., KAHOUNOVÁ, J. & HINDLS, R. 1996. Elementární statistická analýza.
1. vyd. Praha: Management press, 1996. 302 s. ISBN 80-85943-18-2.
DEMEL, J. 1982. Teorie grafů. 2. vyd. Praha: ČVUT, 1982. 200 s. ISBN 80-01-00567-4.
DEMEL, J. 1988. Grafy. 1. vyd. Praha: SNTL, 1988. 184 s.
DUDORKIN, J. 2003. Systémové inženýrství a rozhodování. 4. vyd. Praha: ČVUT, 2003. 164
s. ISBN 80-01-02737-6.
FARANA, R. & KAČMÁŘ, D. 1996. Tvorba HTML dokumentů. [online]. Dostupný z www:
<URL: http://www.fs.vsb.cz/books/prirHTML/Welcome.htm>
FARANA, R. & KAČMÁŘ, D. 1996. Tvorba HTML dokumentu. Interní učební text. Ostrava:
FS VŠB – TU Ostrava, 1996. 44 s.
HEBÁK, P.KAHOUNOVÁ, J. 1978. Počet pravděpodobnosti v příkladech. Praha: SNTL,
Polytechnická knižnice, 1978.
JIROUŠ, F. 1995. Systémové inženýrství. 1. vyd. Praha: ČVUT, 1995. 134 s. ISBN 80-0101356-1.
KÁBA, B. 1999. Teorie pravděpodobnosti. 1. vyd. Praha: PEF ČZU, 1999. 88 s. ISBN 80213-0545-2.
KOSEK, J. Jak psát web. [online]. Dostupný z www: <URL: http://www.jakpsatweb.cz >
NEČAS, J. 1978. Grafy a jejich použití. 1. vyd. Praha: SNTL, 1978. 191 s.
NEŠETŘIL, J. 1979. Teorie grafů. 1. vyd. Praha: SNTL, 1979. 320 s.
PLESNÍK, J. 1983. Grafové algoritmy. 1. vyd. Bratislava: VEDA, 1983. 343 s.
Referenční příručka HTML. [online]. Dostupný z www: <URL:
http://www.fs.vsb.cz/books/HTML/Default.htm>
SEDLÁČEK, J. 1981. Úvod do teorie grafů. 3. vyd. Praha: Academia, 1981. 272 s.
ŠKRÁŠEK, J. & TICHÝ, Z. 1990. Základy aplikované matematiky. 2. vyd. Praha: SNTL,
1990.
VÍTEČEK, A. & WAWRZICZKOVÁ, M. 1988. Síťová analýza (CPM a PERT). Ostrava: FS
VŠB – TU Ostrava, 1988.
VÍTEČKOVÁ, M. Učební text –z přednášek Systémová analýza .
WALTER, J., VEJMOLA, S. & FIALA, P. 1989. Aplikace metod síťové analýzy v řízení a
plánování. 1. vyd. Praha: SNTL/ALFA, 1989. 288 s. ISBN 80-03-00101-3.
ZÍSKAL, J. & KOSKOVÁ, I. 2002. Cvičení z metod operační a systémové analýzy. 3. vyd.
Praha: CREDIT, 2002. 206 s. ISBN 80-213-0411-1.
Download

formát PDF - sylaby a elektronické učebnice