Tömegkiszolgálás - Fogalmak és jelölések - Laptörténet

Szikszayl, 2014. március 13., 12:54-n

2014-03-13T12:54:19Z

← Régebbi változat		A lap 2014. március 13., 14:54-kori változata
105. sor:		105. sor:
	-- [[PallosPeter\|Peti]] - 2006.11.07.		-- [[PallosPeter\|Peti]] - 2006.11.07.

	[[~~Category~~:~~InfoMsc~~]]		[[Kategória:Mérnök informatikus MSc]]

Szikszayl: /* Folytonos Markov-lánc tulajdonságai */

2014-02-25T17:34:48Z

Folytonos Markov-lánc tulajdonságai

← Régebbi változat		A lap 2014. február 25., 19:34-kori változata
101. sor:		101. sor:
	** homogén Markov-láncra: ''E(Τ<sub>i</sub>)'' = 1/-<i>q<sub>ii</sub></i>		** homogén Markov-láncra: ''E(Τ<sub>i</sub>)'' = 1/-<i>q<sub>ii</sub></i>

	Lásd még: [[Tömegkiszolgálás ~~összefoglaló~~]]		Lásd még: [[Tömegkiszolgálás - Összefoglaló]]

	-- [[PallosPeter\|Peti]] - 2006.11.07.		-- [[PallosPeter\|Peti]] - 2006.11.07.

	[[Category:InfoMsc]]		[[Category:InfoMsc]]

Szikszayl: Szikszayl átnevezte a(z) Tömegkiszolgálási fogalmak és jelölések lapot a következő névre: Tömegkiszolgálás - Fogalmak és jelölések

2014-02-25T17:23:31Z

Szikszayl átnevezte a(z) Tömegkiszolgálási fogalmak és jelölések lapot a következő névre: Tömegkiszolgálás - Fogalmak és jelölések

← Régebbi változat	A lap 2014. február 25., 19:23-kori változata
(Nincs különbség)

Szikszayl, 2014. február 25., 17:23-n

2014-02-25T17:23:04Z

← Régebbi változat		A lap 2014. február 25., 19:23-kori változata
1. sor:		1. sor:
			{{Vissza\|Tömegkiszolgálás}}

	==Alapfogalmak==		==Alapfogalmak==

Szikszayl, 2014. január 18., 13:57-n

2014-01-18T13:57:18Z

← Régebbi változat		A lap 2014. január 18., 15:57-kori változata
1. sor:		1. sor:
	~~{{GlobalTemplate\|Infoszak\|TeljesitmenyElemzesFogalmak}}~~

	~~<style>~~
	~~span.sum { font-size: larger; position:relative; bottom:-1px; }~~
	~~</style>~~

	~~__TOC__~~

	==Alapfogalmak==		==Alapfogalmak==

24. sor:		16. sor:

	===Idő jellegű mennyiségek===		===Idő jellegű mennyiségek===

	* _W_ = várakozással töltött idő		* _W_ = várakozással töltött idő
	** E[<i>W</i>] = egy igény átlagos várakozással töltött ideje.		** E[<i>W</i>] = egy igény átlagos várakozással töltött ideje.
32. sor:		23. sor:
	* _T_ = rendszerben töltött idő		* _T_ = rendszerben töltött idő
	** E[<i>T</i>]: egy igény rendszerben átlagosan eltöltött ideje.		** E[<i>T</i>]: egy igény rendszerben átlagosan eltöltött ideje.

	* E[<i>W</i>] + E[<i>x</i>] = E[<i>T</i>]		* E[<i>W</i>] + E[<i>x</i>] = E[<i>T</i>]

	===Darabszám jellegű mennyiségek===		===Darabszám jellegű mennyiségek===

	* <i>X</i>(<i>t</i>): a rendszerben lévő várakozó és kiszolgálás alatti igények száma a _t_ időpontban, valószínűségi változó		* <i>X</i>(<i>t</i>): a rendszerben lévő várakozó és kiszolgálás alatti igények száma a _t_ időpontban, valószínűségi változó
	** X: a rendszerbeli igények számának eloszlása, ha az eloszlás független az időtől		** X: a rendszerbeli igények számának eloszlása, ha az eloszlás független az időtől
45. sor:		34. sor:

	==Folyamegyensúly==		==Folyamegyensúly==

	* Folyamegyensúly: veszteségmentes és stabil rendszerben E[<i>λ</i>]=E[<i>S</i>]		* Folyamegyensúly: veszteségmentes és stabil rendszerben E[<i>λ</i>]=E[<i>S</i>]
	** M/M/1 rendszerre alkalmazva ''λ=S'' és ''P(X=0)=1-λ/μ''		** M/M/1 rendszerre alkalmazva ''λ=S'' és ''P(X=0)=1-λ/μ''

	==Little-formula==		==Little-formula==

	* Munkamegőrző (work-conserving) rendszer: ha van várakozó kérés és szabad kiszolgáló, a kiszolgálás azonnal megkezdődik		* Munkamegőrző (work-conserving) rendszer: ha van várakozó kérés és szabad kiszolgáló, a kiszolgálás azonnal megkezdődik
	* Little-formula: veszteségmentes és munkamegőrző rendszerben tetszőleges kiszolgálási elv mellett E[<i>X</i>]=E[<i>λ</i>]E[<i>T</i>], ha léteznek a várható értékek. Azaz (rendszerbeli igények átlagos száma) = (átlagos érkezési intenzitás) * (rendszerben eltöltött átlagos idő)		* Little-formula: veszteségmentes és munkamegőrző rendszerben tetszőleges kiszolgálási elv mellett E[<i>X</i>]=E[<i>λ</i>]E[<i>T</i>], ha léteznek a várható értékek. Azaz (rendszerbeli igények átlagos száma) = (átlagos érkezési intenzitás) * (rendszerben eltöltött átlagos idő)
58. sor:		45. sor:

	==Diszkrét Markov-lánc==		==Diszkrét Markov-lánc==

	* _p<sub>i</sub><sup>(t)</sup>_: _i_. állapot valószínűsége _t_ időpontban		* _p<sub>i</sub><sup>(t)</sup>_: _i_. állapot valószínűsége _t_ időpontban
	* _p<sub>ij</sub><sup>(k)</sup>(t)_: _k_ lépéses ''i→j'' átmeneti valószínűség _t_ időpontban		* _p<sub>ij</sub><sup>(k)</sup>(t)_: _k_ lépéses ''i→j'' átmeneti valószínűség _t_ időpontban
64. sor:		50. sor:

	===Chapman-Kolmogorov egyenlőség===		===Chapman-Kolmogorov egyenlőség===

	* állapotátmenetre: ''p<sub>ij</sub><sup>(k+n)</sup>(m)'' = <span class="sum">Σ</span><i><sub>l</sub></i> ''p<sub>il</sub><sup>(k)</sup>(m) p<sub>lj</sub><sup>(n)</sup>(m+k)''		* állapotátmenetre: ''p<sub>ij</sub><sup>(k+n)</sup>(m)'' = <span class="sum">Σ</span><i><sub>l</sub></i> ''p<sub>il</sub><sup>(k)</sup>(m) p<sub>lj</sub><sup>(n)</sup>(m+k)''
	* láncra: ''Π<sup>(k+n)</sup>(m)'' = ''Π<sup>(k)</sup>(m) Π<sup>(n)</sup>(m+k)''		* láncra: ''Π<sup>(k+n)</sup>(m)'' = ''Π<sup>(k)</sup>(m) Π<sup>(n)</sup>(m+k)''
	* ~~[[#homogeneous\|~~homogén]] láncra: <i>Π<sup>(k+n)</sup></i>=<i>Π<sup>(k)</sup>Π<sup>(n)</sup></i>, és <i>P<sup>(n)</sup></i>=<i>P<sup>(0)</sup>Π<sup>n</sup></i>		* homogén láncra: <i>Π<sup>(k+n)</sup></i>=<i>Π<sup>(k)</sup>Π<sup>(n)</sup></i>, és <i>P<sup>(n)</sup></i>=<i>P<sup>(0)</sup>Π<sup>n</sup></i>

	===Diszkrét Markov-lánc tulajdonságai===		===Diszkrét Markov-lánc tulajdonságai===
			* homogén (homogeneity): az állapotátmeneti mátrix független az időtől: ''Π<sup>(1)</sup>(t) = Π'', ''p<sub>ij</sub><sup>(k)</sup>(t) = p<sub>ij</sub>''
	* ~~<div id="homogeneous"></div>~~homogén (homogeneity): az állapotátmeneti mátrix független az időtől: ''Π<sup>(1)</sup>(t) = Π'', ''p<sub>ij</sub><sup>(k)</sup>(t) = p<sub>ij</sub>''
	* irreducibilitás (irreducibility): minden állapot minden állapotból elérhető. <big>∀</big><i>i,j</i> állapotpárra <big>∃</big><i>k</i>: <i>p<sub>ij</sub><sup>(k)</sup></i>>0		* irreducibilitás (irreducibility): minden állapot minden állapotból elérhető. <big>∀</big><i>i,j</i> állapotpárra <big>∃</big><i>k</i>: <i>p<sub>ij</sub><sup>(k)</sup></i>>0
	* aperiodikusság (aperiodicity)		* aperiodikusság (aperiodicity)
77. sor:		61. sor:
	** a Markov-lánc aperiodikus, ha <big>∀</big><i>i,j</i> <big>∃</big><i>n<sub>0</sub></i>, hogy <big>∀</big> <i>n>n<sub>0</sub> p<sub>ij</sub><sup>(n)</sup></i>>0		** a Markov-lánc aperiodikus, ha <big>∀</big><i>i,j</i> <big>∃</big><i>n<sub>0</sub></i>, hogy <big>∀</big> <i>n>n<sub>0</sub> p<sub>ij</sub><sup>(n)</sup></i>>0
	** ha a lánc irreducibilis és egy állapota aperiodikus, akkor a lánc is aperiodikus		** ha a lánc irreducibilis és egy állapota aperiodikus, akkor a lánc is aperiodikus
	* ~~<div id="recurrence"></div>~~visszatérőség (recurrence)		* visszatérőség (recurrence)
	** ''f<sub>ij</sub><sup>(k)</sup>'' homogén Markov-láncban annak a valószínűsége, hogy ha _i_ állapotban vagyunk, _j_ állapotot legközelebb _k_ lépés múlva érintjük		** ''f<sub>ij</sub><sup>(k)</sup>'' homogén Markov-láncban annak a valószínűsége, hogy ha _i_ állapotban vagyunk, _j_ állapotot legközelebb _k_ lépés múlva érintjük
	** ''f<sub>ij</sub>'' = <span class="sum">Σ</span><i>f<sub>ij</sub><sup>(n)</sup></i>		** ''f<sub>ij</sub>'' = <span class="sum">Σ</span><i>f<sub>ij</sub><sup>(n)</sup></i>
94. sor:		78. sor:

	==Folytonos Markov-lánc==		==Folytonos Markov-lánc==

	* _p<sub>ij</sub>(t)_: P(_t_ idő múlva a _j_ állapotban lesz a rendszer \| most az _i_ állapotban van)		* _p<sub>ij</sub>(t)_: P(_t_ idő múlva a _j_ állapotban lesz a rendszer \| most az _i_ állapotban van)
	* ''Π'' = [<i>p<sub>ij</sub>(t)</i>]: állapotátmeneti mátrix		* ''Π'' = [<i>p<sub>ij</sub>(t)</i>]: állapotátmeneti mátrix
102. sor:		85. sor:

	===Folytonos Markov-lánc tulajdonságai===		===Folytonos Markov-lánc tulajdonságai===

	* irreducibilitás: minden állapot minden állapotból véges időn belül elérhető. <big>∀</big><i>i,j</i> állapotpárra <big>∃</big><i>t</i>: <i>p<sub>ij</sub>(t)</i>>0		* irreducibilitás: minden állapot minden állapotból véges időn belül elérhető. <big>∀</big><i>i,j</i> állapotpárra <big>∃</big><i>t</i>: <i>p<sub>ij</sub>(t)</i>>0
	* visszatérőség: ugyanúgy, mint ~~[[#recurrence\|~~diszkrét esetben]]		* visszatérőség: ugyanúgy, mint diszkrét esetben
	** ha a lánc irreducibilis és egy állapota visszatérő, akkor a lánc is visszatérő		** ha a lánc irreducibilis és egy állapota visszatérő, akkor a lánc is visszatérő
	* stabilitás feltétele		* stabilitás feltétele
117. sor:		99. sor:
	** homogén Markov-láncra: ''E(Τ<sub>i</sub>)'' = 1/-<i>q<sub>ii</sub></i>		** homogén Markov-láncra: ''E(Τ<sub>i</sub>)'' = 1/-<i>q<sub>ii</sub></i>

	Lásd még: [[~~ToKiZh\|Összefoglaló a töki zh-hoz~~]]		Lásd még: [[Tömegkiszolgálás összefoglaló]]

	-- [[PallosPeter\|Peti]] - 2006.11.07.		-- [[PallosPeter\|Peti]] - 2006.11.07.

			[[Category:InfoMsc]]
	[[Category:~~Infoszak~~]]

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|TeljesitmenyElemzesFogalmak}} TOC ==Alapfogalmak== =…”

2012-10-22T09:47:28Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|TeljesitmenyElemzesFogalmak}} <style> span.sum { font-size: larger; position:relative; bottom:-1px; } </style> __TOC__ ==Alapfogalmak== =…”

Új lap

{{GlobalTemplate|Infoszak|TeljesitmenyElemzesFogalmak}}

<style>
span.sum { font-size: larger; position:relative; bottom:-1px; }
</style>

__TOC__

==Alapfogalmak==

===Ráta jellegű mennyiségek===
(mértékegység: 1/s, 1/óra, stb)

* Érkezési ráta
** ''λ(t)'' = pillanatnyi érkezési ráta, mértékegysége: [kérés/idő]
** ''λi'' = érkezési ráta _i_ sorhossz mellett
** _E[λ]_: várható érkezési ráta, csak stabil rendszerre értelmezett. ''E[λ] = ΣP(X=i)λi''
* Kiszolgálási intenzitás
** _μ(t)_: pillanatnyi kiszolgálási intenzitás, mértékegysége: [kiszolgált kérés/idő]
** ''μi'' = kiszolgálási intenzitás _i_ sorhossz mellett
* Távozási ráta
** S(t): pillanatnyi távozási ráta
** E[S]: várható távozási ráta, csak stabil rendszerre értelmezett. E[S] = ΣP(X=i)μi

===Idő jellegű mennyiségek===

* _W_ = várakozással töltött idő
** E[W] = egy igény átlagos várakozással töltött ideje.
* _x_ = kiszolgálási idő
** E[x] = egy igény átlagos kiszolgálási ideje.
** Exponenciális eloszlású kiszolgálási idő esetén E[x] = 1/μ
* _T_ = rendszerben töltött idő
** E[T]: egy igény rendszerben átlagosan eltöltött ideje.

* E[W] + E[x] = E[T]

===Darabszám jellegű mennyiségek===

* X(t): a rendszerben lévő várakozó és kiszolgálás alatti igények száma a _t_ időpontban, valószínűségi változó
** X: a rendszerbeli igények számának eloszlása, ha az eloszlás független az időtől
** X(t) = Xw(t) + Xs(t)
* Xw(t): a várakozó igények száma a _t_ időpontban
* Xs(t): a kiszolgálás alatti igények száma a _t_ időpontban
* U(t): a munkahátralék a _t_ időpontban, azaz mennyi idő alatt ürülne ki a rendszer, ha nem érkezne több kérés

==Folyamegyensúly==

* Folyamegyensúly: veszteségmentes és stabil rendszerben E[λ]=E[S]
** M/M/1 rendszerre alkalmazva ''λ=S'' és ''P(X=0)=1-λ/μ''

==Little-formula==

* Munkamegőrző (work-conserving) rendszer: ha van várakozó kérés és szabad kiszolgáló, a kiszolgálás azonnal megkezdődik
* Little-formula: veszteségmentes és munkamegőrző rendszerben tetszőleges kiszolgálási elv mellett E[X]=E[λ]E[T], ha léteznek a várható értékek. Azaz (rendszerbeli igények átlagos száma) = (átlagos érkezési intenzitás) * (rendszerben eltöltött átlagos idő)
** Probléma: _T_ függ λ-tól, ezért a képlet alkalmazhatósága ilyen formában nehézkes
** Alkalmazás kiszolgálóra: E[Xs]=E[λ]E[x], azaz (kiszolgálás alatti igények átlagos száma) = (átlagos érkezési intenzitás) * (átlagos kiszolgálási idő)
** Alkalmazás pufferra: E[Xw]=E[λ]E[W], azaz (átlagos sorhossz) = (átlagos érkezési intenzitás) * (átlagos várakozási idő)

==Diszkrét Markov-lánc==

* _pi(t)_: _i_. állapot valószínűsége _t_ időpontban
* _pij(k)(t)_: _k_ lépéses ''i→j'' átmeneti valószínűség _t_ időpontban
* _Π(k)(t)_: _k_ lépéses átmeneti valószínűségmátrix _t_ időpontban

===Chapman-Kolmogorov egyenlőség===

* állapotátmenetre: ''pij(k+n)(m)'' = Σl ''pil(k)(m) plj(n)(m+k)''
* láncra: ''Π(k+n)(m)'' = ''Π(k)(m) Π(n)(m+k)''
* [[#homogeneous|homogén]] láncra: Π(k+n)=Π(k)Π(n), és P(n)=P(0)Πn

===Diszkrét Markov-lánc tulajdonságai===

* <div id="homogeneous"></div>homogén (homogeneity): az állapotátmeneti mátrix független az időtől: ''Π(1)(t) = Π'', ''pij(k)(t) = pij''
* irreducibilitás (irreducibility): minden állapot minden állapotból elérhető. <big>∀</big>i,j állapotpárra <big>∃</big>k: pij(k)>0
* aperiodikusság (aperiodicity)
** _i_ állapot aperiodikus, ha <big>∃</big>n0, hogy <big>∀</big> n>n0 pii(n)>0
** a Markov-lánc aperiodikus, ha <big>∀</big>i,j <big>∃</big>n0, hogy <big>∀</big> n>n0 pij(n)>0
** ha a lánc irreducibilis és egy állapota aperiodikus, akkor a lánc is aperiodikus
* <div id="recurrence"></div>visszatérőség (recurrence)
** ''fij(k)'' homogén Markov-láncban annak a valószínűsége, hogy ha _i_ állapotban vagyunk, _j_ állapotot legközelebb _k_ lépés múlva érintjük
** ''fij'' = Σfij(n)
** _i_ állapot visszatérő, ha a jövőben 1 valószínűséggel újból érintjük: fii=1
** _i_ állapot pozitív visszatérő, ha visszatérő, és a következő előfordulás idejének várható értéke véges: Σnfii(n)<∞
** ha a lánc irreducibilis és egy állapota visszatérő, akkor az a lánc is visszatérő
* stabilitás (stability)
** <big>∀</big>i <big>∃</big>limt→∞ pi(t)=pi, és ez a határérték független a kezdőállapottól
** az eloszlás határértékét egyensúlyi eloszlásnak (stationary distribution) hívjuk
* stabilitás feltétele
** véges Markov-láncra: stabil <big>⇐</big> irreducibilis és aperiodikus
** végtelen Markov-láncra: stabil <big>⇐</big> irreducibilis, aperiodikus és pozitív visszatérő
** végtelen Markov-láncra: stabil <big>⇐</big> irreducibilis, aperiodikus és teljesül a Foster-kritérium
* _i_ állapot tartásideje: átlagosan hány lépésig maradunk az _i_ állapotban (pii<1)
** homogén Markov-láncra: ''E(Τi)'' = 1/(1-pii)

==Folytonos Markov-lánc==

* _pij(t)_: P(_t_ idő múlva a _j_ állapotban lesz a rendszer | most az _i_ állapotban van)
* ''Π'' = [pij(t)]: állapotátmeneti mátrix
* ''P(t)'' = [p0(t), p1(t), ...]: állapotok eloszlása az idő függvényében
* _qij_: ''i→j'' állapotátmenet rátája. Σj ''qij'' = 0
* _Q_ = [qij]: rátamátrix

===Folytonos Markov-lánc tulajdonságai===

* irreducibilitás: minden állapot minden állapotból véges időn belül elérhető. <big>∀</big>i,j állapotpárra <big>∃</big>t: pij(t)>0
* visszatérőség: ugyanúgy, mint [[#recurrence|diszkrét esetben]]
** ha a lánc irreducibilis és egy állapota visszatérő, akkor a lánc is visszatérő
* stabilitás feltétele
** véges Markov-láncra: stabil <big>⇐</big> irreducibilis (periodikusság nem értelmezhető)
** végtelen Markov-láncra: stabil <big>⇐</big> irreducibilis és pozitív visszatérő
** végtelen Markov-láncra: stabil <big>⇐</big> teljesül a Foster-kritérium
* határeloszlás
** stabil láncra <big>∃</big> limt→∞ pi(t) = ''pi''
** _P_ = [p0, p1, ...]
** meghatározása: a PQ=0 egyenletrendszert vagy az állapotgráf vágásaira felírt folyamegyensúlyi egyenleteket kell megoldani.
* _i_ állapot tartásideje: átlagosan mennyi ideig maradunk az _i_ állapotban
** homogén Markov-láncra: ''E(Τi)'' = 1/-qii

Lásd még: [[ToKiZh|Összefoglaló a töki zh-hoz]]

-- [[PallosPeter|Peti]] - 2006.11.07.

[[Category:Infoszak]]