Základní poznatky o markovských řetězcích se spojitým časem
Definice markovského řetězce se spojitým časem
Nechť ( )P,,ΑΩ je pravděpodobnostní prostor,
)∞= ,0T je indexová množina, jejíž prvky nazveme okamžiky a
J = {..., -2, -1, 0, 1, 2, ...} je nejvýše spočetná množina stavů (bez újmy na obecnosti lze
předpokládat, že J = {0, 1, 2, ...} nebo J = {0,1, ..., n}).
Stochastický proces { }Tt;Xt ∈ definovaný na měřitelném prostoru ( )ΑΩ, , jehož složky Xt
nabývají hodnot z množiny stavů J, se nazývá markovský řetězec (se spojitým časem), jsou-li
splněny následující podmínky:
a) ( ) 0jXP:TtJj t >=∈∃∈∀ (vyloučení nepotřebných stavů)
b) ( ) ( )1ntnt0t2nt1ntntn10n10 jX/jXPjXjXjX/jXP:Jj,,j,jTttt 1nn02n1nn −−− ====∧∧=∧==∈∀∈<<<∀ −−−
KKK
za předpokladu, že ( ) 0jXjXjXP 0t2nt1nt 02n1n
>=∧∧=∧= −− −−
K (markovská vlastnost – budoucí
chování markovského řetězce závisí pouze na přítomném stavu a nikoliv na stavech minulých).
Vysvětlení: Markovské řetězce se spojitým časem modelují fyzikální či jiné soustavy, které
mohou v libovolném okamžiku náhodně přejít do některého ze svých možných stavů.
Markovská vlastnost znamená, že to, do jakého stavu se soustava dostane při následující změně,
závisí pouze na tom, v jakém stavu se soustava právě nachází a nezávisí na stavech předchozích.
Např. sledujeme-li během pracovní doby provoz automatických strojů v dílně, náhodná veličina
Xt, )T,0t∈ je počet strojů, které v okamžiku t nepracují (jsou opravovány nebo čekají na
opravu).
Označení:
Jev {Xt = j} – markovský řetězec je v okamžiku t ve stavu j.
P(Xt = j) = pj(t) – absolutní pravděpodobnost stavu j v okamžiku t.
p(t) = (...., pj(t), ...) – vektor absolutních pravděpodobností.
( ) ( )ht,tpiX/jXP ijtht +===+ – pravděpodobnost přechodu ze stavu i v okamžiku t do stavu j
v okamžiku t+h










+=+
M
LL
M
)ht,t(p)ht,t( ij
P - matice pravděpodobností přechodu mezi
okamžiky t, t+h.
P(X0 = j) = pj(0) – počáteční pravděpodobnost stavu j.
p(0) = (...., pj(0), ...) – vektor počátečních pravděpodobností.
Definice HMŘ se spojitým časem
Nechť { }Tt;Xt
∈ je markovský řetězec se spojitým časem. Řekneme, že tento řetězec je
homogenní, jestliže platí:
( ) ( )hpiX/jXP:Tht,Jj,i ijtht ===∈∀∈∀ + .
Vysvětlení: Znamená to, že pravděpodobnosti přechodu ( )iX/jXP tht ==+ – pokud existují –
závisí pouze na časovém přírůstku h a nezávisí na časovém okamžiku t.
Matice pravděpodobností přechodu P(t,t+h) se pak značí P(h) a nazývá se matice přechodu za
časový přírůstek h. Pro HMŘ se spojitým časem tedy existuje celý systém matic přechodu
( ){ }Th,h ∈P . Je zvykem definovat P(0) = I.
Vlastnosti HMŘ se SČ (CH-K rovnice a zákon evoluce)
Nechť { }Tt;Xt
∈ je homogenní markovský řetězec se spojitým časem, s vektorem počátečních
pravděpodobností p(0) a systémem matic přechodu ( ){ }Th,h ∈P . Pak pro Tg,h ∈∀ platí:
a) P(h+g) = P(h) P(g) (Chapmanova – Kolmogorovova rovnice)
b) p(h) = p(0) P(h) (zákon evoluce)
Definice matice intenzit přechodu
Nechť { }Tt;Xt ∈ je homogenní markovský řetězec se spojitým časem se systémem matic přechodu
( ){ }Th,h ∈P . Pak definujeme:
a) Jj,i ∈∀ :
( )
h
hp
limq ij
0hij
+→
= - intenzita přechodu ze stavu i do stavu j
b) Ji∈∀ :
( )
h
hp1
limq ii
0h
i
−
=
+→
- intenzita výstupu ze stavu i.
Matice Q = (qij)i,j J∈ , kde qii = -qi, se nazývá matice intenzit přechodu HMŘ se spojitým časem.
Vysvětlení: Matice Q je charakterizována tím, že qij ≥ 0 pro i ≠ j a qii < 0 a součet prvků v každém řádku je
nulový. Je to kvazistochastická matice.
Matici intenzit přechodu lze graficky vyjádřit pomocí přechodového diagramu. Je to ohodnocený
orientovaný graf, kde
a) vrcholy jsou stavy, b) hrany odpovídají nenulovým intenzitám přechodu
c) ohodnocení hran je rovno těmto intenzitám. Hrany, které nejsou smyčkami, mají kladné ohodnocení
(qij > 0) a smyčky mají záporné ohodnocení (qii < 0).
Definice stacionárního vektoru HMŘ se SČ
Nechť { }Tt;Xt
∈ je HMŘ se SČ, který má systém matic přechodu ( ){ }Tt;t ∈P . Stochastický
vektor a takový, že pro Tt∈∀ platí a = aP(t), se nazývá stacionární vektor (stacionární
rozložení) daného řetězce.
Výpočet stacionárního vektoru pomocí matice intenzit přechodu
Nechť { }Tt;Xt
∈ je HMŘ se SČ, který má systém matic přechodu ( ){ }Tt;t ∈P a matici intenzit
přechodu Q = (qij)i,j J∈ .
Jestliže existuje Tt∈ tak, že matice P(t) je regulární (tj. všechny její prvky jsou kladné), pak
existuje stacionární vektor daného řetězce a je dán vztahem: aQ = 0. Toto řešení je jediné.
Kolmogorovovy systémy a systém evolučních diferenciálních rovnic
Nechť { }Tt;Xt
∈ je homogenní markovský řetězec se spojitým časem, který má systém matic
přechodu ( ){ }Tt;t ∈P , systém vektorů absolutních pravděpodobností ( ){ }Tt;t ∈p , vektor
počátečních pravděpodobností p(0) a matici intenzit přechodu Q. Pak platí:
a) ( ) ( )QPP tt' = s počáteční podmínkou P(0) = I (Kolmogorovův systém prospektivních
diferenciálních rovnic)
b) ( ) ( )tt' QPP = s počáteční podmínkou P(0) = I (Kolmogorovův systém retrospektivních
diferenciálních rovnic)
c) ( ) ( )Qpp tt' = s počáteční podmínkou p(0) = daný stochastický vektor (systém evolučních
diferenciálních rovnic).
Definice Poissonova procesu
Nechť { }Tt;Xt
∈ je homogenní markovský řetězec se spojitým časem, který má množinu stavů
J = {0, 1, 2, …}, vektor počátečních pravděpodobností p(0) = (1, 0, …) a matici intenzit
přechodu












λλ−
λλ−
λλ−
=
KKKKK
K
K
K
00
00
00
Q
, kde 0>λ je konstanta, nazývá se intenzita.
Přechodový diagram:
Tento HMŘ se nazývá Poissonův proces (s parametrem λ). (Vidíme, že v Poissonově procesu je
možné jen setrvání v dosavadním stavu nebo přechod do nejbližšího vyššího stavu.)
Pravděpodobnostní rozložení složek Poissonova procesu
Nechť { }Tt;Xt
∈ je Poissonův proces s parametrem λ. Pak platí:
( ) ( ) t
j
j
e
!j
t
tp:JjTt λ−λ
=∈∀∈∀ .
Pravděpodobnosti přechodu v Poissonově procesu
Nechť { }Tt;Xt
∈ je Poissonův proces s parametrem λ. Pak platí:
( )
( )
( )





<
≥
−
λ
=∈∀∈∀
λ−
−
ijpro0
ijproe
!ij
t
tp:Jji,Tt
t
ij
ij .
Grafické znázornění realizací Poissonova procesu
Předpokládejme, že během 15 minut zaznamenáváme příchozí hovory do informačního střediska. První
zákazník volal 3 minuty po zahájení sledování, další zákazníci pak 4, 7, 9 a 13 minut po zahájení sledování.
Během sledovaných 15 minut tedy nastalo 5 příchozích hovorů.
Vysvětlení: Náhodná veličina Xt, která udává např. počet zákazníků, kteří přijdou do fronty v intervalu
( t,0 , se řídí rozložením Po(λt). Střední hodnota počtu událostí, které nastanou v intervalu ( t,0 , je rovna
číslu λt, tedy konstanta λ představuje střední hodnotu počtu událostí, které nastanou za jednotkový časový
interval. Proto se λ nazývá intenzita procesu.
Čísla pj(t) udávají pravděpodobnosti, že v intervalu ( t,0 nastalo právě j událostí.
Číslo p0(t) = e-λt
udává pravděpodobnost, že v intervalu ( t,0 nenastala žádná událost.
Označíme-li S dobu čekání na změnu mezi stavy (tj. dobu čekání na příchod události resp. dobu setrvání ve
stavu), pak P(S > t) = e-λt
, tedy ( )



<
≥−
=≤
λ−
0t,0
0t,e1
tSP
t
. To znamená, že je-li rozložení počtu událostí,
které nastaly v intervalu ( t,0 Poissonovo, je rozložení doby čekání na změnu resp. doby setrvání ve stavu
exponenciální.
Definice procesu vzniku a zániku
Nechť { }Tt;Xt
∈ je homogenní markovský řetězec se spojitým časem, který má množinu stavů
J = {0, 1, 2, …}, vektor počátečních pravděpodobností p(0) = (1, 0, …) a matici intenzit přechodu
( )
( )












λλ+µ−µ
λλ+µ−µ
λλ−
=
KKKKK
K
K
K
2222
1111
00
0
0
00
Q
, kde K0,1,2,j,0j
=>λ a K1,2,j,0j
=>µ jsou konstanty.
Tento řetězec se nazývá proces vzniku a zániku (resp. množení a úmrtí).
Přechodový diagram:
Upozornění: Je zřejmé, že Poissonův proces je speciálním případem procesu vzniku a zániku, v němž
μj = 0, j = 1, 2, … a λj = λ, j = 0, 1, 2, …
Vysvětlení:
Proces vzniku a zániku modeluje kolísání rozsahu souboru objektů v čase za předpokladu, že
a) v náhodných okamžicích vstupují do tohoto souboru nové objekty, přičemž pravděpodobnost,
že v intervalu ( ht,t + vstoupí do souboru rozsahu j nový objekt, je ( )hohj
+λ , kde λj > 0 je
intenzita vstupu do stavu j;
b) v náhodných okamžicích vystupují z tohoto souboru jiné objekty, přičemž pravděpodobnost,
že v intervalu ( ht,t + vystoupí ze souboru rozsahu j jeden objekt, je ( )hohj +µ , kde μj > 0 je
intenzita výstupu ze stavu j;
c) vstupy a výstupy objektů jsou stochasticky nezávislé jevy;
d) během krátkého časového intervalu zůstává rozsah souboru týž nebo se jedničku zvětší či
zmenší.
6. Základní pojmy teorie hromadné obsluhy (THO)
6.1. Motivace
THO je matematická disciplína, která se zabývá matematickým modelováním činnosti systému hromadné
obsluhy (SHO), tj. systému zákazník – obslužná linka – obsluha. THO se používá pro modelování
komunikačních, dopravních, obchodních a zdravotnických systémů a výrobních procesů. Počátky THO
spadají do 30. let 20. století a jsou spjaty především s modelováním provozu telefonních ústředen.
6.2. Základní pojmy
Základní jednotkou SHO je trojice zákazník – obslužná linka – obsluha.
Zákazník je subjekt, který vyžaduje vyřízení svého požadavku. Např. zákazník je telefonní účastník, který
vyžaduje uskutečnění telefonního spojení.
Obslužná linka je osoba nebo zařízení, které zpracovává požadavky zákazníků, např. to může být telefonní
ústředna.
Obsluha je činnost, která vede k uspokojení požadavku zákazníka, např. spojení s volaným účastníkem.
Do SHO přicházejí zákazníci ve vstupním proudu, což je posloupnost okamžiků příchodů zákazníků do
SHO. Okamžiky příchodů mohou být deterministické nebo náhodné a počet zákazníků může být omezený
nebo neomezený.
Zdroj zákazníků může být prakticky neomezený (řádově tisíce – klienti banky, auta, která jezdí k benzínové
čerpací stanici, registrovaní pacienti lékaře, klienti mobilního operátora) nebo omezený (stroje ve výrobní
hale, které je nutné udržovat a opravovat).
Pokud zákazníci nemohou být po svém příchodu do SHO okamžitě obslouženi, řadí se do fronty. Způsob
řazení zákazníků do fronty a výběr zákazníků k obsluze se nazývá frontový režim.
Nejznámější frontové režimy jsou:
FIFO (první vstupuje, první je obsloužen)
LIFO (poslední vstupuje, první je obsloužen)
SIRO (obsluhy v náhodném pořadí)
PRI (obsluha podle priorit).
Doba obsluhy může být:
pevná (tj. stejná pro všechny zákazníky)
závislá na typu zákazníka
náhodná
Výstupní proud je posloupnost okamžiků výstupů zákazníků ze SHO. Vlastnosti výstupního proudu jsou
závislé na vlastnostech vstupního proudu a na době obsluhy.
Základní struktura SHO
Úloha THO: najít funkční závislost veličin, které charakterizují kvalitu činnosti SHO na charakteristikách
vstupního proudu, linek obsluhy a na způsobu organizace SHO jako celku.
Příklady SHO
systém obslužné linky zákazníci
banka úředníci klienti banky
samoobsluha pokladny nakupující
poliklinika lékaři pacienti
benzínová čerpací stanice čerpadla vozidla
dopravní systém křižovatky se semafory vozidla
6.3. Dělení SHO podle různých kritérií
a) Podle typu matematického modelu
- markovské modely (doby mezi příchody zákazníků se řídí exponenciálním rozložením)
- semimarkovské modely (doby mezi příchody zákazníků se řídí Erlangovým rozložením)
- nemarkovské modely
b) Podle počtu zákazníků
- systém s ohraničeným počtem zákazníků
- systém s neohraničeným počtem zákazníků
c) Podle čekání zákazníků na obsluhu
- systém bez čekání (zákazník, který se nedostane k obsluze hned po příchodu, nečeká a odchází)
- systém s čekáním (zákazník nemůže odejít bez obsloužení. Jsou-li všechny linky obsazené, čeká ve frontě,
která je buď ohraničená nebo neohraničená)
- systém smíšený (zákazník čeká ve frontě jen tehdy, je-li splněna nějaká dodatečná podmínka)
6.4. Kendallova klasifikace SHO
David Georg Kendall (1918 – 2007): britský statistik, působil na univerzitách v Oxfordu a Cambridge. Patřil
ke světové špičce v oblasti teorie pravděpodobnosti a analýzy dat a byl jedním ze zakladatelů stochastické
geometrie.
Při Kendallově klasifikaci se SHO dělí podle:
- rozložení doby mezi příchody zákazníků
- rozložení doby obsluhy
- počtu linek obsluhy
- kapacity systému
- frontového režimu.
Používá se označení X/Y/n nebo X/Y/n/m/z
X … označuje rozložení doby mezi příchody zákazníků
Y … označuje rozložení doby obsluhy
n … počet linek obsluhy
m … kapacita systému
z … frontový režim
Na místě X a Y mohou být tyto symboly:
M pro exponenciální rozložení
Ek pro Erlangovo rozložení s parametrem k
D pro degenerované rozložení
G pro obecné rozložení
Na místě n a m: čísla 1, 2, …
Na místě z: FIFO, LIFO, SIRO, PRI
Např. M/D/2/∞/FIFO je systém, kde vstupní proud tvoří Poissonův proces, doba obsluhy je konstantní,
v systému jsou dvě linky, systém má neomezenou kapacitu a frontový režim je „první vstoupí, první je
obsloužen“.
6.5. Používaná označení v SHO
λ … intenzita vstupního proudu (průměrný počet zákazníků, kteří vstoupí do SHO za jednotku času)
µ … intenzita obsluhy (průměrný počet zákazníků, které linka obslouží za jednotku času)
µ
λ
=β
ρ … intenzita provozu (základní charakteristika systému, často se udává v %)
Časové charakteristiky
W … doba pobytu zákazníka v systému
WS … doba obsluhy
WQ … doba čekání zákazníka v systému
Je zřejmé, že W = WS + WQ.
Charakteristiky týkající se počtu zákazníků
N … počet zákazníků ve stabilizovaném systému – nezávisí již na čase t
NS … počet obsluhovaných zákazníků
NQ … počet zákazníků ve frontě
Je zřejmé, že N = NS + NQ.
Pravděpodobnostní charakteristiky
a0 … pravděpodobnost, že systém je prázdný
aj … pravděpodobnost, že v systému je právě j zákazníků
PQ … pravděpodobnost, že přicházející zákazník bude čekat ve frontě
PZ … pravděpodobnost, že přicházející zákazník bude odmítnut
Nákladové charakteristiky
Pokud je uživatel schopen ohodnotit náklady na čekání zákazníka, náklady na prostoj či provoz linek
obsluhy, je možno systém optimalizovat vzhledem na jeho nákladovou efektivnost.
Je možno určit např. optimální intenzitu obsluhy nebo optimální počet obslužných linek.
6.6. Littleův vzorec
V systémech s neomezeným zdrojem zákazníků platí, že střední hodnota počtu zákazníku v systému (resp. ve
frontě resp. u obsluhy) je rovna součinu intenzity vstupního proudu a střední hodnoty doby pobytu zákazníka
v systému (resp. ve frontě resp. u obsluhy):
( ) ( )WENE λ=
( ) ( )QQ WENE λ=
( ) ( )SS WENE λ=
Za předpokladu, že známe intenzity µλ, , lze ze znalosti aspoň jedné charakteristiky E(N), E(NQ), E(NS),
E(W), E(WQ), E(WS) ostatní charakteristiky dopočítat.
6.7. Metody zkoumání SHO
Existují dvě různé metody zkoumání SHO.
Analytická metoda: Analytik zná nebo je schopen odvodit vzorce pro výpočet jednotlivých charakteristik
systému. Pak stačí jenom dosadit do těchto vzorců konkrétní parametry systému.
Nevýhoda: analytické řešení je známé jenom u několika nejjednodušších modelů.
Simulační metoda: Systém nahradíme simulačním modelem a jeho činnost mnohonásobně nezávisle
simulujeme na počítači. Jednotlivé výstupní charakteristiky systému pak nahradíme jejich odhady, např.
střední hodnotu průměrem, pravděpodobnost relativní četností apod. Takto lze analyzovat i velmi složité
systémy.
6.8. Intenzita provozu v SHO s jednou linkou obsluhy
V tomto případě je intenzita provozu
µ
λ
=ρ .
Mohou nastat tři různé situace:
a) Intenzita vstupu = intenzita obsluhy: ρ = 1
Ideální situace, netvoří se fronta a linka obsluhy je využita na 100 %.
b) Intenzita vstupu < intenzita obsluhy: ρ < 1
Nově příchozí zákazník je obsloužen bez čekání, ale linka obsluhy je po určitou dobu nevyužita. Využití
linky je 100* ρ %.
c) Intenzita vstupu > intenzita obsluhy: ρ > 1
Nestabilní systém, začínají se postupně hromadit zákazníci, i když linka obsluhy pracuje nepřetržitě. Pokud
zákazníci nečekají na obsluhu a odcházejí, jde o systém se ztrátami.
6.9. Ilustrace SHO s jednou linkou obsluhy
Máme k dispozici záznamy o okamžicích příchodů a odchodů 16 zákazníků do SHO během 8 hodin.
č. zák. příchod odchod doba čekání doba mezi příchody obsluha prostoj celkem
1 0,20 0,30 0 20 10 20 10
2 0,40 1,10 0 20 30 10 30
3 0,50 1,30 20 10 20 0 40
4 2,10 3,10 0 80 60 10 60
5 3,20 3,50 0 70 30 10 30
6 3,40 4,10 10 20 20 0 30
7 4,10 4,40 0 30 30 0 30
8 4,20 5,00 20 10 20 0 40
9 4,50 5,50 10 30 50 0 60
10 5,10 6,00 40 20 10 0 50
11 5,50 6,10 10 40 10 0 20
12 6,20 6,40 0 30 20 10 20
13 6,40 6,50 0 20 10 0 10
14 7,10 7,30 0 30 20 20 20
15 7,40 7,50 0 30 10 10 10
16 7,50 8,00 0 10 10 0 10
Předpokládáme, že vstupní proud zákazníků je Poissonův proces s parametrem λ (tj. střední hodnota počtu
zákazníků, kteří vstoupí do SHO za jednotku času, je λ). Za časovou jednotku zvolíme 1 hodinu.
Odhad parametru λ: 2
8
16ˆ ==λ .
Počty zákazníků v jednohodinových intervalech se mají řídit Poissonovým rozložením.
č. hodiny 1 2 3 4 5 6 7 8
počet zákazníků 3 0 1 2 3 2 2 3
Použijeme jednoduchý test Poissonova rozložení hladinu významnosti zvolíme 0,05.
m = 2
( ) ( ) ( )[ ] 7
8
232023
7
1
s
2222
=−++−+−= K
Testová statistika:
( )
4
2
7
8
7
m
s1n
K
2
=
⋅
=
−
=
Kritický obor: ( ) ( ) ) )∞∪=∞χ∪χ= ;01,1669,1;0,77,0W 975,0
2
025,0
2
∉WK H0 nezamítáme na asymptotické hladině významnosti 0,05.
Odhad parametru μ: průměrná doba obsluhy je ( ) h375,0min5,2210...3010
16
1
m ==+++=
6,2
m
1
ˆ ==µ zákazníků za 1 h.
Doba obsluhy se má řídit exponenciálním rozložením. Použijeme Darlingův test, hladinu významnosti
volíme 0,05.
m = 22,5
( ) ( ) ( )[ ] 2205,22105,22305,2210
15
1
s
2222
=−++−+−= K
( ) 5185,6
5,22
22015
m
s1n
K 22
2
=
⋅
=
−
=
Kritický obor: ( ) ( ) ) )∞∪=∞χ∪χ= ;488,27262,6;0,1515,0W 975,0
2
025,0
2
∉ WK H0 nezamítáme na asymptotické hladině významnosti 0,05.
Využití systému:
75,0
6,2
2
ˆ
ˆ
ˆ ==
µ
λ
=ρ , tedy systém je využit na 75 %.
Doba mezi příchody zákazníků se má řídit exponenciálním rozložením. Použijeme Darlingův test, hladinu
významnosti volíme 0,05.
( ) 375,29102020
16
1
m =+++= K
( ) ( ) ( )[ ] 9167,392375,2910375,2920375,2920
15
1
s
2222
=−++−+−= K
( ) 8302,6
375,29
9167,39215
m
s1n
K 22
2
=
⋅
=
−
=
Kritický obor: ( ) ( ) ) )∞∪=∞χ∪χ= ;488,27262,6;0,1515,0W 975,0
2
025,0
2
∉ WK H0 nezamítáme na asymptotické hladině významnosti 0,05.