3. část: Teorie hromadné obsluhy
1Ing. Michal Dorda, Ph.D.
Základy teorie pravděpodobnosti
• Náhodný pokus je děj, jehož výsledek není ani
při dodržení všech předepsaných podmínek
předem znám.
• Náhodný jev je výsledkem náhodného
pokusu, náhodné jevy označujeme X,Y,…
• Elementární jev E – jev, který nejde dále
rozložit.
• Základní prostor Ω – množina všech
elementárních jevů.
2Ing. Michal Dorda, Ph.D.
Základy teorie pravděpodobnosti
• Jistý jev I – jev, který vždy nastane (jev, který
nastane s pravděpodobností 1).
• Nemožný jev 0 – jev, který nikdy nenastane.
• Opačný jev – opačný jev k jevu A je jev Ā,
který nastane právě tehdy, když nenastane jev
A.
• Disjunktní jevy – jevy A a B jsou disjunktní,
nemohou-li nastat současně.
3Ing. Michal Dorda, Ph.D.
Základy teorie pravděpodobnosti
• Axiomatické zavedení pravděpodobnosti:
1. Pravděpodobnost jevu je nezáporná veličina.
2. Pravděpodobnost sjednocení konečně nebo
spočetně mnoho disjunktních jevů je rovna
součtu pravděpodobností těchto jevů.
3. Pravděpodobnost jevu jistého je rovna 1.
4Ing. Michal Dorda, Ph.D.
  0AP
       nn APAPAPAAAP  ...... 2121
  1IP
Základy teorie pravděpodobnosti
• Na základě uvedených axiomů plyne, že
pravděpodobnost jevu opačného k jevu A je
rovna doplňku do 1.
5Ing. Michal Dorda, Ph.D.
   APAP 1
Náhodná proměnná a její popis
• Náhodná proměnná je reálná funkce
definovaná na množině všech elementárních
jevů, která každému jevu přiřadí reálné číslo.
• Rozlišujeme náhodnou proměnnou:
– Diskrétní (obor hodnot náhodné proměnné je
konečná nebo nekonečná posloupnost).
– Spojitou (obor hodnot náhodné proměnné je
určitý konečný nebo nekonečný interval).
6Ing. Michal Dorda, Ph.D.
Náhodná proměnná a její popis
• Diskrétní náhodnou proměnnou můžeme
popsat funkčními závislostmi:
– Pravděpodobnostní funkce .
– Distribuční funkce .
• Spojitou náhodnou proměnnou můžeme
popsat pomocí:
– Hustoty pravděpodobnosti .
– Distribuční funkce .
7Ing. Michal Dorda, Ph.D.
   xXPxp 
     

xx
i
i
xpxXPxF
 xf
     

x
dttfxXPxF
Náhodná proměnná a její popis
• Pro distribuční funkci DNP i SNP platí:
– .
– .
– .
• Pro pravděpodobnostní funkci DNP platí:
– .
– .
Ing. Michal Dorda, Ph.D. 8
  10  xF
     aFbFbXaP 
    1lim,0lim 

xFxF
xx
  10  ixp
  1
ix
ixp
Náhodná proměnná a její popis
• Pro hustotu pravděpodobnosti SNP platí:
– .
– .
Ing. Michal Dorda, Ph.D. 9
  0xf
  1


dxxf
Náhodná proměnná a její popis
• Náhodnou proměnnou můžeme dále popsat
pomocí číselných charakteristik. Číselné
charakteristiky NP dělíme:
– Podle způsobu výpočtu na momentové, kvantilové
a ostatní.
– Podle toho, které vlastnosti rozdělení
pravděpodobnosti charakterizují na charakteristiky
polohy, variability, šikmosti a špičatosti.
Ing. Michal Dorda, Ph.D. 10
Náhodná proměnná a její popis
• Střední hodnota (počáteční moment 1. řádu):
– Pro DNP .
– Pro SNP .
• Pro střední hodnotu platí:
– .
– .
– .
Ing. Michal Dorda, Ph.D. 11
 
ix
ii xpxEX 1
 


 dxxxfEX 1
  ccE 
  cEXcXE 
  EYEXYXE 
Náhodná proměnná a její popis
• Rozptyl (centrální moment 2. řádu):
– Pro DNP .
– Pro SNP .
• Při výpočtech rozptylu se spíš užívá vztahu:
,
kde pro DNP ,pro SNP .
Ing. Michal Dorda, Ph.D. 12
    
ix
ii xpEXxDX
2
2
2

   


 dxxfEXxDX
2
2
2

   222
EXEXEXXEDX 
 
ix
ii xpxEX 22
 


 dxxfxEX 22
Poissonovo rozdělení
pravděpodobnosti – Po(λ)
• Patří mezi diskrétní náhodné proměnné.
• Rozdělení je definováno jedním parametrem
λ > 0 – střední počet událostí za jednotku času.
Poissonova NP může nabývat hodnot 0,1,2,… a může
např. představovat počet zákazníků přicházejících za
jednotku času.
• Pravděpodobnostní funkce je definována:
• Pro střední hodnotu a rozptyl platí:
.
Ing. Michal Dorda, Ph.D. 13
 DXEX
 
  jinde.0
...,2,1,0,0pro
!

 
kXP
ke
k
kXP
k

 
Poissonovo rozdělení
pravděpodobnosti – Po(λ)
• Odvození vztahu pro střední hodnotu:
Ing. Michal Dorda, Ph.D. 14
 
 
....
!2!1!0!1
!1!
*210
1
1
100



































eee
k
e
e
kk
ke
k
kPkEK
k
k
k
k
k
k
k
k
* Maclaurinova řada
....
!2!1!0
210

xxx
ex
Poissonovo rozdělení
pravděpodobnosti – Po(λ)
Ing. Michal Dorda, Ph.D. 15
Ukázka průběhu pravděpodobnostní funkce Poissonovy
náhodné proměnné.
Exponenciální rozdělení
pravděpodobnosti E(λ)
Ing. Michal Dorda, Ph.D. 16
• Patří mezi spojitá rozdělení pravděpodobnosti.
• Rozdělení je definováno jedním parametrem
λ > 0. Exponenciální NP představuje dobu
trvání činnosti (např. obsluhy zákazníka), příp.
dobu mezi jednotlivými událostmi (příchody
zákazníků) – jestliže se počet přicházejících
zákazníků za jednotku času řídí Poissonovým
rozdělením, potom délky mezer mezi příchody
zákazníků se řídí exponenciálním rozdělením.
Exponenciální rozdělení
pravděpodobnosti E(λ)
Ing. Michal Dorda, Ph.D. 17
• Pro hustotu pravděpodobnosti platí:
• Pro distribuční funkci platí:
 
  .jinde0
,00,pro

 
xf
xexf x
 
 
  .jinde0
0,x0,pro1

 
xF
exF x

Exponenciální rozdělení
pravděpodobnosti E(λ)
Ing. Michal Dorda, Ph.D. 18
• Pro střední hodnotu exponenciální NP platí:
.
• Pro rozptyl exponenciální NP platí:
.

1
EX
2
1

DX
Exponenciální rozdělení
pravděpodobnosti E(λ)
• Odvození vztahu pro střední hodnotu:
Ing. Michal Dorda, Ph.D. 19
 







11
00
11
lim
lim
222
0
*
000


























aa
a
a
x
a
xx
ee
a
dxxedxxedxexdxxxfEX
22
0
22
0
00
00000
11
1111111
11
1
1
*

































































aa
aaaa
a
x
a
x
a
x
a
x
a
x
a
x
x
xa
x
ee
a
eee
a
eee
a
ee
x
dxee
x
dxee
x
evu
evxu
dxxe
Exponenciální rozdělení
pravděpodobnosti E(λ)
Ing. Michal Dorda, Ph.D. 20
Ukázka průběhu hustoty pravděpodobnosti exponenciální
náhodné proměnné.
Exponenciální rozdělení
pravděpodobnosti E(λ)
Ing. Michal Dorda, Ph.D. 21
Ukázka průběhu distribuční funkce exponenciální náhodné
proměnné.
Systémy hromadné obsluhy
• Za systém hromadné obsluhy (SHO) lze
považovat každý systém, k němuž přicházejí
požadavky na obsluhu v systému.
Ing. Michal Dorda, Ph.D. 22
Fronta požadavků
čekajících na
obsluhu v SHOVstupní proud
požadavků
Linky
provádějící
obsluhu
Výstupní
proud
požadavků
Systémy hromadné obsluhy
• SHO lze členit podle mnoha kritérií, rozeznáváme
např.:
– Systémy bez fronty a systémy tvořící frontu.
– Systémy tvořící frontu lze rozdělit na systémy s
neomezenou nebo omezenou délkou fronty.
– Systémy tvořící frontu lze dále rozdělit podle
frontového režimu – FIFO, LIFO, PRI.
– Systémy s paralelně, sériově nebo kombinovaně
řazenými linkami.
– Systémy se spolehlivými linkami a systémy s
nespolehlivými linkami.
Ing. Michal Dorda, Ph.D. 23
Systémy hromadné obsluhy
Ing. Michal Dorda, Ph.D. 24
SS
Systém
hromadné
obsluhy
Vstupní údaje
o SHO
Výstupní údaje
o SHO
Systémy hromadné obsluhy
• Každý SHO lze charakterizovat několika faktory:
– Charakter vstupního toku zákazníků.
– Charakter obsluhy.
– Počet obslužných linek a jejich uspořádání.
– Kapacita fronty a frontový režim (pokud SHO
umožňuje tvorbu fronty).
• Tyto údaje představují oblast vstupních dat
(potřebujeme je znát, abychom mohli SHO
matematicky modelovat).
Ing. Michal Dorda, Ph.D. 25
Systémy hromadné obsluhy
• U daného SHO nás zajímá např.:
– Procento odmítnutých zákazníků, resp.
pravděpodobnost odmítnutí zákazníka PODM.
– Využití obslužných linek κ.
– Střední počet zákazníků v systému EK.
– Střední počet zákazníků v obsluze ES.
– Střední počet zákazníků ve frontě EL.
• Tyto údaje představují oblast výstupních dat
(tedy to, co chceme řešením matematického
modelu SHO získat) – provozní charakteristiky.
Ing. Michal Dorda, Ph.D. 26
Systémy hromadné obsluhy
• SHO se pro názornost označují dle Kendallovy
klasifikace SHO:
X / Y / n / m,
kde: X vyjadřuje pravděpodobnostní rozdělení
příchodu zákazníků k SHO,
Y vyjadřuje pravděpodobnostní rozdělení,
kterým se řídí doba trvání obsluhy zákazníka,
n označuje počet obslužných linek v SHO,
m označuje celkový počet míst v SHO.
Ing. Michal Dorda, Ph.D. 27
Systémy hromadné obsluhy
Ing. Michal Dorda, Ph.D. 28
Pozice X Pozice Y
M
exponenciální doby mezi příchody
(elementární vstupní tok)
exponenciální doba
obsluhy
Ek
Erlangovo rozdělení dob mezi
příchody
Erlangovo rozdělení
doby obsluhy
D konstantní doby mezi příchody
konstantní doba
obsluhy
G
obecné rozdělení dob mezi
příchody
obecné rozdělení
doby obsluhy
Systémy hromadné obsluhy
• Budeme se zabývat systémy:
– Vstupní tok zákazníků bude elementární.
– Doba obsluhy zákazníka bude exponenciální
náhodná proměnná.
– U systémů tvořících frontu budeme uvažovat FIFO
režim výběru zákazníků z fronty.
– Obslužné linky budou řazeny paralelně, budou
homogenní a nebudeme uvažovat možnost jejich
poruchy.
Ing. Michal Dorda, Ph.D. 29
Elementární vstupní tok
• Elementární vstupní tok je takový tok, který
splňuje tři základní vlastnosti:
– Stacionárnost, beznáslednost a ordinárnost.
• Stacionárnost (neměnnost stochastického
režimu): Počet zákazníků, kteří přicházejí k
SHO za čas t, závisí pouze na délce tohoto
intervalu a nezávisí na jeho poloze na časové
ose.
Ing. Michal Dorda, Ph.D. 30
Elementární vstupní tok
• Beznáslednost (neexistence následných
účinků): Počet zákazníků, kteří přijdou k SHO
za čas t, nezávisí na počtu zákazníků, kteří k
SHO přišli před začátkem tohoto časového
intervalu.
• Ordinárnost: Zákazníci přicházejí k SHO
jednotlivě.
Ing. Michal Dorda, Ph.D. 31
Elementární vstupní tok
• Pro elementární vstupní tok platí:
– Pravděpodobnost , tedy že za čas t přijde k
SHO k zákazníků, je rovna:
• Elementární vstupní tok je tedy Poissonův,
mezery mezi příchody zákazníků k SHO jsou
exponenciální.
Ing. Michal Dorda, Ph.D. 32
 tpk
   
  jinde.0
,...,2,1,0,0,0pro
!

 
tp
kte
k
t
tp
k
t
k
k 
 
Intenzity přechodů
• Za krátký časový okamžik ∆t→0 jsou přípustné
pouze tyto přechody:
– Příchod jednoho zákazníka nastane s intenzitou
přechodu λ (intenzita příchodu zákazníka nezávisí
na počtu zákazníků nacházejících se v systému).
– Odchod jednoho z k obsluhovaných zákazníků, kde
k=1,…,n nastane s intenzitou kµ (intenzita
odchodu zákazníka závisí na počtu zákazníků, kteří
jsou v obsluze).
Ing. Michal Dorda, Ph.D. 33
M/M/n/n SHO
• Systém je tvořen n paralelně řazenými
homogenními linkami.
• Systém nepřipouští tvorbu fronty čekajících
zákazníků na obsluhu, je-li systém plný, jsou
přicházející zákazníci odmítáni.
Ing. Michal Dorda, Ph.D. 34
M/M/n/n SHO
• Vstupní tok je elementární s intenzitou λ.
– Střední počet zákazníků, kteří přicházejí k SHO za
jednotku času je tedy roven λ.
– Jelikož je vstupní tok elementární (tedy
Poissonův), jsou doby mezi příchody po sobě
jdoucích zákazníků exponenciální náhodnou
proměnnou s parametrem λ. Převrácená hodnota
tohoto parametru je rovna střední době mezi
příchody zákazníků k systému.
Ing. Michal Dorda, Ph.D. 35
M/M/n/n SHO
• Doba obsluhy zákazníka je náhodná a řídí se
exponenciálním rozdělením pravděpodobnosti,
které je definováno parametrem μ.
– Parametr μ nazýváme parametrem obsluhy a udává,
kolik zákazníků je průměrně schopna 1 linka obsloužit
za jednotku času, hodnota 1/ μ potom udává střední
dobu obsluhy jednoho zákazníka.
– Parametr nμ nazýváme parametrem systému a udává,
kolik zákazníků za jednotku času je systém schopen
průměrně obsloužit.
Ing. Michal Dorda, Ph.D. 36
M/M/n/n SHO
• Nyní nás například zajímá, jaký je střední počet
zákazníků v systému – EK. Jelikož náhodnou
proměnnou je počet zákazníků v systému, který je
diskrétní, můžeme psát:
• Z uvedeného vztahu je zřejmé, že k výpočtu
potřebujeme znát pravděpodobnosti, že v
systému se nachází k zákazníků pro k = 0,1,…,n. Ty
stanovíme postupem, který si ukážeme dále.
Ing. Michal Dorda, Ph.D. 37
.
0


n
k
kPkEK
Přechodový graf M/M/n/n SHO
• Systém se může nacházet v následujících stavech
tvořících množinu S (množina všech stavů
systému):
– 0 – systém je prázdný (v systému se nenachází žádný
zákazník).
– 1 – v systému se nachází 1 zákazník – tento zákazník je
obsluhován.
– k – v systému (a tedy i v obsluze) se nachází k
zákazníků, kde k = 1, 2,…, n – 1.
– n – v systému (a tedy i v obsluze) se nachází n
zákazníků, systém je zaplněn.
Ing. Michal Dorda, Ph.D. 38
Přechodový graf M/M/n/n SHO
Ing. Michal Dorda, Ph.D. 39
0 1 k n

   
 2
k
 1k
n
Vrcholy grafu představují stav systému (počet zákazníků v systému),
hrany představují možné změny stavu systému za čas Δt→0 a
ohodnocení hran představuje intenzitu přechodu.
Rovnice globální rovnováhy
• Jedná se sice o dynamický systém, my budeme
ale vyšetřovat systém v tzv. ustáleném
(rovnovážném) stavu, tedy pro t→∞.
• V ustáleném stavu platí tzv. princip globální
rovnováhy: Pro každou množinu stavů A, která
je podmnožinou S, platí, že tok
(pravděpodobnost stavu násobená intenzitou
přechodu) z této množiny je roven toku do
této množiny.
Ing. Michal Dorda, Ph.D. 40
Rovnice globální rovnováhy –
M/M/n/n SHO
Ing. Michal Dorda, Ph.D. 41
0 1 k n

   
 2
k
 1k
n
10 PP  
Rovnice globální rovnováhy –
M/M/n/n SHO
Ing. Michal Dorda, Ph.D. 42
0 1 k n

   
 2
k
 1k
n
21 2 PP  
Rovnice globální rovnováhy –
M/M/n/n SHO
Ing. Michal Dorda, Ph.D. 43
0 1 k n

   
 2
k
 1k
n
kk PkP  1
Rovnice globální rovnováhy –
M/M/n/n SHO
Ing. Michal Dorda, Ph.D. 44
0 1 k n

   
 2
k
 1k
n
  11  kk PkP 
Rovnice globální rovnováhy –
M/M/n/n SHO
Ing. Michal Dorda, Ph.D. 45
0 1 k n

   
 2
k
 1k
n
nn PnP  1
Rovnice globální rovnováhy –
M/M/n/n SHO
• Dostáváme soustavu n+1 lineárních rovnic s
n+1 neznámými pravděpodobnostmi Pk, kde
k = 0,1,…,n. Soustavu lze obecně zapsat ve
tvaru:
• Tato soustava má nekonečně mnoho řešení
(jedna rovnice je lineární kombinací ostatních
rovnic).
Ing. Michal Dorda, Ph.D. 46
.,...2,1pro1 nkPkP kk  
Rovnice globální rovnováhy –
M/M/n/n SHO
• Abychom získali pouze jedno řešení rovnice, je
nutné soustavu doplnit tzv. normativní
podmínkou pravděpodobnosti, která nám říká,
že systém se může nacházet pouze ve stavech
z množiny S. Zapsáno matematicky:
Ing. Michal Dorda, Ph.D. 47
.1
0


n
k
kP
Analytické řešení M/M/n/n SHO
• Z rovnice přímo
plyne vztah:
• Tento rekurentní vztah umožňuje spočítat
pravděpodobnost stavu k pomocí
pravděpodobnosti stavu k-1.
Ing. Michal Dorda, Ph.D. 48
nkPkP kk ,...2,1pro1  
.,...,2,1pro1 nkP
k
P kk  


Analytické řešení M/M/n/n SHO
• Nyní bychom potřebovali vyjádřit vztahy pro
výpočet pravděpodobností jednotlivých stavů
k pomocí pravděpodobnosti stavu 0, chceme
tedy vyjádřit závislost Pk pro k = 1,2,…,n na P0.
K tomu využijeme rekurentní vzorec, který
jsme si odvodili v předchozím postupu.
Ing. Michal Dorda, Ph.D. 49
Analytické řešení M/M/n/n SHO
Ing. Michal Dorda, Ph.D. 50
nkP
k
P
k
P
PPPP
PPPP
PPP
k
kk ,...,2,1pro
!
1
!3
1
1233
!2
1
122
!1
1
1
01
0
3
023
0
2
012
0
1
01
























































Pomocí tohoto
vztahu jsme schopni
spočítat všechny
pravděpodobnosti
kromě
pravděpodobnosti
P0, kterou odvodíme
z normativní
podmínky
pravděpodobnosti
.1
0

n
k
kP
Erlangův vzorec
Analytické řešení M/M/n/n SHO
• Abychom mohli použít vzorec odvozený v
předchozím snímku, musíme znát hodnotu
pravděpodobnosti P0. Vztah pro výpočet této
pravděpodobnosti odvodíme s využitím
normativní podmínky pravděpodobnosti.
Ing. Michal Dorda, Ph.D. 51
Analytické řešení M/M/n/n SHO
Ing. Michal Dorda, Ph.D. 52














































































n
k
k
n
k
k
nk
nk
nk
k
P
k
P
nk
P
P
n
P
k
PP
PPPP
0
0
0
0
10
0
000
1
0
0
10
!
1
1
1
!
1
1
!
1
...
!
1
...
!1
1
!0
1
1
!
1
...
!
1
...
!1
1
!0
1
1......




















Erlangův vzorec
Provozní charakteristiky M/M/n/n SHO
• Pravděpodobnost odmítnutí zákazníka PODM:
– Přicházející zákazník bude odmítnut, najde-li v
okamžiku svého příchodu systém plný, tedy ve
stavu n. Pro pravděpodobnost odmítnutí tedy
platí:
Ing. Michal Dorda, Ph.D. 53
.
!
1
!
1
!
1
0
0





















n
k
k
n
n
nODM
k
n
P
n
PP






Provozní charakteristiky M/M/n/n SHO
• Střední počet zákazníků v systému EK
stanovíme podle vzorce pro výpočet střední
hodnoty DNP, kde náhodnou proměnnou K je
počet zákazníků v systému. Tedy platí:
Ing. Michal Dorda, Ph.D. 54
   
 
   .1...
!1
1
...
!1
1
!0
1
!1
1
!1
1
!
1
1100
1
0
1
0
0
1
0
1
1
0
0
0
0
nn
n
n
k
k
n
k
k
n
k
k
n
k
k
PPPPP
n
PP
P
k
P
kk
kP
k
kkPEK















































































Provozní charakteristiky M/M/n/n SHO
• Vztah pro výpočet EK lze také odvodit
následujícím způsobem. Vyjdeme z výchozí
soustavy rovnic globální rovnováhy:
Ing. Michal Dorda, Ph.D. 55
.
,2
,
1
21
10
nn PnP
PP
PP








Provozní charakteristiky M/M/n/n SHO
• Sečtením všech rovnic globální rovnováhy
dostaneme:
Ing. Michal Dorda, Ph.D. 56
nn PnP
PP
PP






1
21
10
2






n
k
k
n
k
k kPP
1
1
0

Provozní charakteristiky M/M/n/n SHO
• Vyjdeme-li z definičního vztahu pro výpočet
střední hodnoty diskrétní náhodné proměnné
– počtu zákazníků v systému k, můžeme psát:
Ing. Michal Dorda, Ph.D. 57
....10
1
10
0



n
k
kn
n
k
k kPPnPPkPEK
Provozní charakteristiky M/M/n/n SHO
• Použijeme-li tento vztah ve vztahu
předcházejícím, získáváme postupnými
úpravami:
Ing. Michal Dorda, Ph.D. 58
  .1
,
,
1
0
1
0
EKP
EKP
EKP
n
n
k
k
n
k
k














Provozní charakteristiky M/M/n/n SHO
• Střední počet zákazníků v obsluze ES
stanovíme podle vzorce pro výpočet střední
hodnoty DNP, kde náhodnou proměnnou S je
počet zákazníků v obsluze. Jelikož u tohoto
systému platí, že počet zákazníků v systému se
rovná počtu zákazníků v obsluze, můžeme
psát:
Ing. Michal Dorda, Ph.D. 59
 .1 nPEKES 


Provozní charakteristiky M/M/n/n SHO
• Střední počet zákazníků ve frontě EL opět
stanovíme podle vzorce pro výpočet střední
hodnoty DNP, kde náhodnou proměnnou L je
počet zákazníků ve frontě. Jelikož tento systém
netvoří frontu (počet zákazníků ve frontě je
pořád roven 0), platí:
Ing. Michal Dorda, Ph.D. 60
.0EL
Provozní charakteristiky M/M/n/n SHO
• Využití obslužných linek (systému) κ stanovíme
na základě následující úvahy. Systém
průměrně obsluhuje ES zákazníků a je schopen
obsluhovat n zákazníků, tedy platí:
kde ρ nazýváme intenzitou provozu.
Ing. Michal Dorda, Ph.D. 61
 
   ,11
1
nn
n
PP
nn
P
n
ES


 




M/M/n/∞ SHO
• Systém je tvořen n paralelně řazenými
homogenními linkami.
• Systém připouští tvorbu fronty čekajících
zákazníků na obsluhu, přicházející zákazník
nachází vždy volné místo v systému, systém
tedy neodmítá zákazníky (v systému se může
teoreticky nacházet ∞ zákazníků).
• Aby byl systém stabilní, musí platit:
.
Ing. Michal Dorda, Ph.D. 62
1



n
M/M/n/∞ SHO
• Vstupní tok je elementární s intenzitou λ.
• Doba obsluhy zákazníka je exponenciální
náhodná proměnná s parametrem μ.
Ing. Michal Dorda, Ph.D. 63
Přechodový graf M/M/n/∞ SHO
• Systém se může nacházet ve stavech:
– 0 – systém je prázdný.
– 1 – v systému je 1 zákazník – 1 v obsluze, 0 ve
frontě.
– k – v systému se nachází k zákazníků, kde k = 1,
2,…, n – 1; k zákazníků je v obsluze, 0 ve frontě.
– n – v systému je n zákazníků, všichni jsou v
obsluze, fronta je prázdná.
– k – v systému je k zákazníků, kde k = n + 1,…; n
zákazníků je v obsluze a k – n ve frontě.
Ing. Michal Dorda, Ph.D. 64
Přechodový graf M/M/n/∞ SHO
Ing. Michal Dorda, Ph.D. 65
0 1 k n

   
 2
k
 1k
n
k

n
 
n n
Rovnice globální rovnováhy –
M/M/n/∞ SHO
Ing. Michal Dorda, Ph.D. 66
0 1 k n

   
 2
k
 1k
n
k

n
 
n n
10 PP  
Rovnice globální rovnováhy –
M/M/n/∞ SHO
Ing. Michal Dorda, Ph.D. 67
0 1 k n

   
 2
k
 1k
n
k

n
 
n n
21 2 PP  
Rovnice globální rovnováhy –
M/M/n/∞ SHO
Ing. Michal Dorda, Ph.D. 68
0 1 k n

   
 2
k
 1k
n
k

n
 
n n
kk PkP  1
Rovnice globální rovnováhy –
M/M/n/∞ SHO
Ing. Michal Dorda, Ph.D. 69
0 1 k n

   
 2
k
 1k
n
k

n
 
n n
  11  kk PkP 
Rovnice globální rovnováhy –
M/M/n/∞ SHO
Ing. Michal Dorda, Ph.D. 70
0 1 k n

   
 2
k
 1k
n
k

n
 
n n
nn PnP  1
Rovnice globální rovnováhy –
M/M/n/∞ SHO
Ing. Michal Dorda, Ph.D. 71
0 1 k n

   
 2
k
 1k
n
k

n
 
n n
1 nn PnP 
Rovnice globální rovnováhy –
M/M/n/∞ SHO
Ing. Michal Dorda, Ph.D. 72
0 1 k n

   
 2
k
 1k
n
k

n
 
n n
kk PnP  1
Rovnice globální rovnováhy –
M/M/n/∞ SHO
Ing. Michal Dorda, Ph.D. 73
0 1 k n

   
 2
k
 1k
n
k

n
 
n n
1 kk PnP 
Rovnice globální rovnováhy –
M/M/n/∞ SHO
• V tomto případě dostáváme soustavu
nekonečně mnoho lineárních rovnic s
nekonečně mnoho neznámými
pravděpodobnostmi Pk, kde k=0,1,2,…,n,…:
Ing. Michal Dorda, Ph.D. 74
.,...2,1pro
,,...2,1pro
1
1




nnkPnP
nkPkP
kk
kk


Analytické řešení M/M/n/∞ SHO
• Z těchto rovnic získáme přímo rekurentní
vztahy:
Ing. Michal Dorda, Ph.D. 75
.,...1,pro
,,...,2,1pro
1
1




nnkP
n
P
nkP
k
P
kk
kk




pozn. U druhého rekurentního vztahu uvádíme platnost i pro k=n, což neodpovídá
příslušné rovnici globální rovnováhy. Lze se ale snadno přesvědčit (dosazením k=n do
prvního rekurentního vztahu), že druhý rekurentní vztah platí i v tomto případě.
Analytické řešení M/M/n/∞ SHO
• Nyní bychom opět potřebovali vyjádřit vztahy
pro výpočet pravděpodobností jednotlivých
stavů k pomocí pravděpodobnosti stavu 0,
chceme tedy vyjádřit závislost Pk pro
k = 1,2,…,n,… na P0. K tomu využijeme
rekurentní vzorce, které jsme si odvodili v
předchozím postupu.
Ing. Michal Dorda, Ph.D. 76
Analytické řešení M/M/n/∞ SHO
Ing. Michal Dorda, Ph.D. 77
nkP
k
P
k
P
PPPP
PPPP
PPP
k
kk ,...,2,1pro
!
1
!3
1
1233
!2
1
122
!1
1
1
01
0
3
023
0
2
012
0
1
01
























































Vztah pro výpočet
Pk pomocí P0, vztah
platí pouze pro
k = 1,2,…,n!!!
Analytické řešení M/M/n/∞ SHO
Ing. Michal Dorda, Ph.D. 78
,...1,pro
!
1
!
1
,...1,pro
!
1
a,...1,pro:Víme
00
1
2
12
1
01




















































nnkP
nn
P
nn
PP
nnkPP
n
P
n
P
P
n
P
nn
P
n
P
P
n
P
P
n
PnnkP
n
P
k
nk
nnk
n
nk
k
n
nk
n
nk
kk
nnnn
nn
n
nkk



























Vztah pro výpočet Pk
pomocí Pn, platí pouze pro
k = n,…!!!
Vztah pro výpočet Pk pomocí P0, platí
pouze pro k = n,…!!!
Analytické řešení M/M/n/∞ SHO
Ing. Michal Dorda, Ph.D. 79
1pro
1!
1
!
1
1
1
!
1
!
1
1
!
1
!
1
1
1.........
0
0
1
0
0
0
0
10
0
10
110





















































































n
n
k
k
nk
nkn
n
k
k
k
nk
nk
n
k
k
nk
k
n
k
k
nnk
nk
P
nn
P
k
P
P
nn
P
k
PP
PPPPP 1pro
1
...32
11























nk
nk
nk
nk
n
Pravděpodobnost P0 opět
stanovíme z normativní
podmínky pravděpodobnosti.
Jedná se o nekonečnou
geometrickou řadu s
prvním členem a1 = ρ a
kvocientem q = ρ, pro
součet nekonečné
geometrické řady platí:
.1pro
1
1


 q
q
a
s
Provozní charakteristiky M/M/n/∞
SHO
• Pravděpodobnost odmítnutí zákazníka PODM:
– Přicházející zákazník nebude nikdy odmítnut,
najde-li v okamžiku svého příchodu některou z
linek neobsazenou, začíná ihned jeho obsluha, v
opačném případě se řadí do fronty, jejíž délka není
nijak omezena:
Ing. Michal Dorda, Ph.D. 80
.0ODMP
Provozní charakteristiky M/M/n/∞
SHO
• Střední počet zákazníků v obsluze ES
stanovíme podle vzorce pro výpočet střední
hodnoty DNP, kde náhodnou proměnnou S je
počet zákazníků v obsluze. Tedy platí:
Ing. Michal Dorda, Ph.D. 81
  .......
!
1
11210
***
1
0
0
1
00

































nnnn
nk
n
nk
n
k
k
nk
k
n
k
k
n
s
s
PPPPPP
P
n
nP
k
kPnkPsPES
Provozní charakteristiky M/M/n/∞
SHO
Ing. Michal Dorda, Ph.D. 82
 
 ....
!1
1
!
1
* 210
1
1
0
1
1
0
0 


















  n
n
k
k
n
k
k
PPPP
k
P
k
k








 
   ......
...
!1
1
!
1
**
1111
10
1
1
1
0
1
1
1
0
1











































































nnnnnn
nnn
nk
n
nkn
nk
n
nkn
nk
n
nk
n
nk
n
nk
PPPPPP
P
n
P
n
PP
n
P
n
P
nn
nP
n
nP
n
nnPP
n
n
































Provozní charakteristiky M/M/n/∞
SHO
Ing. Michal Dorda, Ph.D. 83
• Střední počet zákazníků v obsluze ES lze také
odvodit z rovnic globální rovnováhy, které
sečteme:
.,...2,1pro
,,...2,1pro
1
1




nnkPnP
nkPkP
kk
kk


.
111
1
1
1 






 
nk
k
n
k
k
nk
k
n
k
k nPkPPP 
Provozní charakteristiky M/M/n/∞
SHO
• Získaný vztah upravujeme:
Ing. Michal Dorda, Ph.D. 84
  ....
,
,
,
11
10
111
1
111
1
1
1
111
1
1
1





















































nk
k
n
k
k
nk
k
n
k
k
k
k
nk
k
n
k
k
nk
k
n
k
k
nk
k
n
k
k
nk
k
n
k
k
nPkPPP
nPkPP
nPkPPP
nPkPPP




Provozní charakteristiky M/M/n/∞
SHO
• Pro ES musí z definičního vztahu pro výpočet
střední hodnoty platit:
Ing. Michal Dorda, Ph.D. 85
 
....
110
11
1
110







nk
k
n
k
kn
nn
nPkPPn
PnPnPPES 
Provozní charakteristiky M/M/n/∞
SHO
• Použitím tohoto vztahu dostáváme:
• Z normativní podmínky pravděpodobnosti
plyne, že výraz v závorce na levé straně musí
být roven 1, proto dostáváme:
Ing. Michal Dorda, Ph.D. 86
  ....10 ESPP  
.


ES
Provozní charakteristiky M/M/n/∞
SHO
• Střední počet zákazníků ve frontě EL opět
stanovíme podle vzorce pro výpočet střední
hodnoty DNP, kde náhodnou proměnnou L je
počet zákazníků ve frontě. Můžeme tedy psát:
Ing. Michal Dorda, Ph.D. 87
 
.
11
0
2
11
1
1
1100
nn
l
l
n
l
l
n
l
l
n
l
n
l
l
ln
n
k
k
l
l
P
d
d
P
d
d
P
d
d
P
lPPllPPlPEL













































 1
...32
1l
l
Provozní charakteristiky M/M/n/∞
SHO
• Střední počet zákazníků v systému EK je roven
součtu středního počtu požadavků v obsluze a
středního počtu požadavků ve frontě. Můžeme
tedy psát:
Ing. Michal Dorda, Ph.D. 88
 
.
1
2 nPELESEK 






Provozní charakteristiky M/M/n/∞
SHO
• Využití obslužných linek (systému) κ stanovíme
na základě následující úvahy. Systém
průměrně obsluhuje ES zákazníků a je schopen
obsluhovat n zákazníků, tedy platí:
Ing. Michal Dorda, Ph.D. 89
.



 
nnn
ES
M/M/n/m SHO
• Systém je tvořen n paralelně řazenými
homogenními linkami.
• Systém připouští tvorbu fronty zákazníků
čekajících na obsluhu, délka fronty je omezena na
(m – n) míst. Nachází-li příchozí zákazník v
systému m zákazníků, je odmítnut (systém je tedy
vždy stabilní).
• Vstupní tok je elementární s intenzitou λ.
• Doba obsluhy zákazníka je exponenciální
náhodná proměnná s parametrem μ.
Ing. Michal Dorda, Ph.D. 90
Přechodový graf M/M/n/m SHO
• Systém se může nacházet ve stavech:
– 0 – systém je prázdný.
– 1 – v systému je 1 zákazník – 1 v obsluze, 0 ve frontě.
– k – v systému se nachází k zákazníků, kde k = 1, 2,…, n
– 1; k zákazníků je v obsluze, 0 ve frontě.
– n – v systému je n zákazníků, všichni jsou v obsluze,
fronta je prázdná.
– k – v systému je k zákazníků, kde k = n + 1,…, m - 1; n
zákazníků je v obsluze a k – n ve frontě.
– m – v systému je m zákazníků; n zákazníků je v obsluze
a m – n ve frontě.
Ing. Michal Dorda, Ph.D. 91
Přechodový graf M/M/n/m SHO
Ing. Michal Dorda, Ph.D. 92
0 1 k n

   
 2
k
 1k
n
k

n
 
n n m

n
Rovnice globální rovnováhy –
M/M/n/m SHO
Ing. Michal Dorda, Ph.D. 93
0 1 k n

   
 2
k
 1k
n
k

n
 
n n m

n
10 PP  
Rovnice globální rovnováhy –
M/M/n/m SHO
Ing. Michal Dorda, Ph.D. 94
0 1 k n

   
 2
k
 1k
n
k

n
 
n n m

n
21 2 PP  
Rovnice globální rovnováhy –
M/M/n/m SHO
Ing. Michal Dorda, Ph.D. 95
0 1 k n

   
 2
k
 1k
n
k

n
 
n n m

n
kk PkP  1
Rovnice globální rovnováhy –
M/M/n/m SHO
Ing. Michal Dorda, Ph.D. 96
0 1 k n

   
 2
k
 1k
n
k

n
 
n n m

n
  11  kk PkP 
Rovnice globální rovnováhy –
M/M/n/m SHO
Ing. Michal Dorda, Ph.D. 97
0 1 k n

   
 2
k
 1k
n
k

n
 
n n m

n
nn PnP  1
Rovnice globální rovnováhy –
M/M/n/m SHO
Ing. Michal Dorda, Ph.D. 98
0 1 k n

   
 2
k
 1k
n
k

n
 
n n m

n
1 nn PnP 
Rovnice globální rovnováhy –
M/M/n/m SHO
Ing. Michal Dorda, Ph.D. 99
0 1 k n

   
 2
k
 1k
n
k

n
 
n n m

n
kk PnP  1
Rovnice globální rovnováhy –
M/M/n/m SHO
Ing. Michal Dorda, Ph.D. 100
0 1 k n

   
 2
k
 1k
n
k

n
 
n n m

n
1 kk PnP 
Rovnice globální rovnováhy –
M/M/n/m SHO
Ing. Michal Dorda, Ph.D. 101
0 1 k n

   
 2
k
 1k
n
k

n
 
n n m

n
mm PnP  1
Rovnice globální rovnováhy –
M/M/n/m SHO
• V tomto případě dostáváme soustavu m+1
lineárních rovnic s m+1 neznámými
pravděpodobnostmi Pk, kde k=0,1,2,…,m:
Ing. Michal Dorda, Ph.D. 102
.,...,1pro
,,...2,1pro
1
1
mnkPnP
nkPkP
kk
kk






Analytické řešení M/M/n/m SHO
• Z těchto rovnic získáme přímo rekurentní
vztahy:
Ing. Michal Dorda, Ph.D. 103
.,...,1,pro
,,...,2,1pro
1
1
mnnkP
n
P
nkP
k
P
kk
kk








pozn. U druhého rekurentního vztahu uvádíme platnost i pro k=n, což neodpovídá
příslušné rovnici globální rovnováhy. Lze se ale snadno přesvědčit (dosazením k=n do
prvního rekurentního vztahu), že druhý rekurentní vztah platí i v tomto případě.
Analytické řešení M/M/n/m SHO
• Nyní si opět vyjádříme vztahy, pomocí kterých
jsme schopni stanovit hodnotu
pravděpodobnosti stavu k, kde k=1,…,m
pomocí pravděpodobnosti stavu 0. Využijeme
k tomu odvozené rekurentní vztahy.
Ing. Michal Dorda, Ph.D. 104
Analytické řešení M/M/n/m SHO
Ing. Michal Dorda, Ph.D. 105
nkP
k
P
k
P
PPPP
PPPP
PPP
k
kk ,...,2,1pro
!
1
!3
1
1233
!2
1
122
!1
1
1
01
0
3
023
0
2
012
0
1
01
























































Analytické řešení M/M/n/m SHO
Ing. Michal Dorda, Ph.D. 106
mnnkP
nn
P
nn
PP
mnnkPP
n
P
n
P
P
nn
P
nn
P
nnn
P
n
P
P
nn
P
nn
P
n
P
P
n
P
k
nk
nnk
n
nk
k
n
nk
n
nk
kk
nnn
nn
nn
nn
n
n
,...,1,pro
!
1
!
1
,...,1,pro
!
1
!
1
!
1
!
1
!
1
!
1
00
1
0
2
20
2
012
0
1
01
0




























































































































Analytické řešení M/M/n/m SHO
Ing. Michal Dorda, Ph.D. 107
 
1pro
!
1
!
1
1
1pro
1
1
!
1
!
1
1
1
!
1
!
1
1
!
1
!
1
1
1.........
0
0
0
0
1
0
0
0
1
0
0
0
10
110











































































































nm
nk
P
nk
P
nn
P
k
P
P
nn
P
k
PP
PPPPPP
n
n
k
k
nmn
n
k
k
m
nk
nkn
n
k
k
m
nk
k
nk
n
k
k
m
nk
k
n
k
k
mnnk
 
  1pro
...
1pro
1
1
...
32
11
32
11











































nm
nm
n
n
nm
m
nk
nk
m
nk
nk
nm
nm
m
nk
nk
m
nk
nk
Pravděpodobnost P0 opět
stanovíme z normativní
podmínky pravděpodobnosti.
Provozní charakteristiky M/M/n/m
SHO
• Pravděpodobnost odmítnutí zákazníka PODM:
– Přicházející zákazník bude odmítnut, najde-li v
okamžiku svého příchodu m zákazníků v systému
(tedy jsou obsazena všechna místa v obsluze i ve
frontě). Můžeme tedy psát:
Ing. Michal Dorda, Ph.D. 108
.
!
1
0P
nn
PP
m
nmmODM 







 


Provozní charakteristiky M/M/n/m
SHO
• Střední počet zákazníků v obsluze ES
stanovíme podle vzorce pro výpočet střední
hodnoty DNP, kde náhodnou proměnnou S je
počet zákazníků v obsluze. Tedy platí:
Ing. Michal Dorda, Ph.D. 109
   .1...
!
1
111210
***
1
0
0
1
00
mmnnnn
m
nk
n
nk
n
k
k
m
nk
k
n
k
k
n
s
s
PPPPPPPP
P
n
nP
k
sPnkPsPES































Provozní charakteristiky M/M/n/m
SHO
Ing. Michal Dorda, Ph.D. 110
 
 ....
!1
1
!
1
* 210
1
1
0
1
1
0
0 


















  n
n
k
k
n
k
k
PPPP
k
P
k
k








 
   .......
...
!1
1
!
1
**
111111
110
1
1
1
0
1
1
1
0
1

















































































mnnnmnnn
n
nm
nnn
m
nk
n
nkn
m
nk
n
nknm
nk
n
nk
n
m
nk
n
nk
PPPPPPPP
P
n
P
n
P
n
P
P
n
P
n
P
nn
nP
n
nP
n
nnPP
n
n


































Provozní charakteristiky M/M/n/m
SHO
Ing. Michal Dorda, Ph.D. 111
• Střední počet zákazníků v obsluze ES lze také
odvodit z rovnic globální rovnováhy, které
sečteme:
.,...,1pro
,,...2,1pro
1
1
mnkPnP
nkPkP
kk
kk






.
111
1
1
1 



 
m
nk
k
n
k
k
m
nk
k
n
k
k nPkPPP 
Provozní charakteristiky M/M/n/m
SHO
• Získaný vztah upravujeme:
Ing. Michal Dorda, Ph.D. 112
  ....
,
,
,
11
110
111
1
111
1
1
1
111
1
1
1












































m
nk
k
n
k
km
m
nk
k
n
k
k
m
k
k
m
nk
k
n
k
k
m
nk
k
n
k
k
m
nk
k
n
k
k
m
nk
k
n
k
k
nPkPPPP
nPkPP
nPkPPP
nPkPPP




Provozní charakteristiky M/M/n/m
SHO
• Pro ES musí z definičního vztahu pro výpočet
střední hodnoty platit:
Ing. Michal Dorda, Ph.D. 113
 
....
110
11
1
110
 




m
nk
k
n
k
kmn
nn
nPkPPnPn
PnPnPPES 
Provozní charakteristiky M/M/n/m
SHO
• Použitím tohoto vztahu dostáváme:
• Z normativní podmínky pravděpodobnosti
plyne, že výraz v závorce na levé straně musí
být roven 1−Pm, proto dostáváme:
Ing. Michal Dorda, Ph.D. 114
  .... 110 ESPPP m   
 .1 mPES 


Provozní charakteristiky M/M/n/m
SHO
• Střední počet zákazníků ve frontě EL opět
stanovíme podle vzorce pro výpočet střední
hodnoty DNP, kde náhodnou proměnnou L je
počet zákazníků ve frontě. Můžeme tedy psát:
Ing. Michal Dorda, Ph.D. 115
.0
100








nm
l
ln
n
k
k
nm
l
l lPPlPEL
Provozní charakteristiky M/M/n/m
SHO
• Střední počet zákazníků v systému EK je roven
součtu středního počtu požadavků v obsluze a
středního počtu požadavků ve frontě. Můžeme
tedy psát:
Ing. Michal Dorda, Ph.D. 116
  .1
1




nm
l
lnm lPPELESEK


Provozní charakteristiky M/M/n/m
SHO
• Využití obslužných linek (systému) κ stanovíme
na základě následující úvahy. Systém
průměrně obsluhuje ES zákazníků a je schopen
obsluhovat n zákazníků, tedy platí:
Ing. Michal Dorda, Ph.D. 117
 
 .1
1
m
m
P
n
P
n
ES


 


