III.1.3. Az átmeneti valószínűségek és a sorhossz várható értéke


A következő fejezetekben a rendszerre jellemző mennyiségeket számoljuk ki. Először is bevezetünk néhány jelölést, amelyekre a későbbiekben szükségünk lesz. $C_n\ \ \ \ -\ \ $ a rendszerbe belépő $n$-edik igény; $\tau_n\ \ \ \ \ -\ \ $ a $C_n$ igény beérkezési ideje; $t_n\ \ \ \ \ -\ \ $ $\tau_n-\tau_{n-1}$, a $C_{n-1}$ és $C_n$ igények beérkezése közötti időtartam; $x_n \ \ \ \ -\ \ $ a $C_n$ igény kiszolgálási ideje; $q_n\ \ \ \ -\ \ \ $ a $C_n$ igény távozásakor hátrahagyott igények száma; $v_n\ \ \ \ -\ \ \ $ a $C_n$ igény kiszolgálása alatt a rendszerbe érkező új igények száma.


$(q_n, n\ge 1)$ az ú.n. beágyazott Markov-lánc, amelynek egylépéses átmenetvalószínűségei:

\begin{displaymath} p_{ij}:=P\left(q_{n+1}=j\ \vert\ q_n=i\right). \end{displaymath}

Elsősorban a $q_n$ eloszlását vizsgáljuk, vagyis a $P\left(q_n=k\right)$ valószínűségeket. Ezek függenek az időtől, határeloszlásukat (ha $n\to\infty$), $D_k$-val jelöljük. A ${\bf P}=\left(p_{ij}\right)_{i,j=0,1,\ldots}$ átmenetvalószínűségi mátrix a következő alakú lesz:

\begin{displaymath} {\bf P}=\pmatrix{\alpha_0&\alpha_1&\alpha_2&\alpha_3&\ldots... ...\alpha_0&\ldots\cr \vdots&\vdots&\vdots&\vdots&\ddots\cr} , \end{displaymath}

ahol $\alpha_k:=P\left(v_{n+1}=k\right)$. Az $i$-edik sor $j$-edik eleme annak a valószínűségét adja meg, hogy ha $C_n$ távozásakor $i$ igényt hagyott maga után a rendszerben, akkor $C_{n+1}$ távozásakor éppen $j$ igény maradt a rendszerben. Ez éppen azt jelenti, hogy pontosan $j-i+1$ új igény érkezett, amíg a $C_{n+1}$ igény kiszolgálása tartott. Az $\alpha_k$ kiszámolásához vegyük figyelembe, hogy a beérkezési folyamat független a rendszer állapotától. A $C_n$ igény, ( $B\left(x\right)$ eloszlású), $x_n$ kiszolgálási ideje pedig független az $n$-től, ezért $v_n$ szintén független az $n$ értékétől. Hagyjuk el tehát az $n$-et a jelölésünkből és vezessük be az $\tilde{x}$ és $\tilde{v}$ valószínűségi változókat. $P\left(x_n\le x\right)=P\left(\tilde{x}\le x\right)=B\left(x\right)$ és $P\left(v_n=k\right)=P\left(\tilde{v}=k\right)=\alpha_k$. A teljes valószínűség tétele alapján

\begin{displaymath} \alpha_k=P\left(\tilde{v}=k\right)=\int\limits_0^\infty P\left(\tilde{v}=k,x<\tilde{x}\le x+dx\right)dx, \end{displaymath}

melyet a feltételes valószínűségekkel kifejezve

\begin{displaymath} \alpha_k=\int\limits_0^\infty P\left(\tilde{v}=k\ \vert\ \tilde{x}=x\right)b\left(x\right)dx , \end{displaymath}

ahol $b\left(x\right)={dB\left(x\right)\over dx}$, a kiszolgálási idő sűrűségfüggvénye. Mivel a beérkezési folyamat $\lambda$ paraméterű Poisson-folyamat, ahol $x=\tilde{x}$ az időváltozó, a következő átmenetvalószínűségeket ($P$ elemeit) kapjuk:

\begin{displaymath} \alpha_k=\int\limits_0^\infty{{\left(\lambda x\right)}^k\over k!}e^{-\lambda x}b\left(x\right)dx.\leqno(3) \end{displaymath}

Figyelembe véve, hogy $\alpha_k>0$ minden $k\ge 0$-ra, a ${\bf P}$ mátrix alakjából következik, hogy bármely adott állapotból az összes többi elérhető, azaz a Markov-lánc irreducibilis (és aperiodikus). A sorbanállási elmélet alapjainál használt szokásos jelöléssel

\begin{displaymath} \varrho={\lambda\over\mu}=\lambda\bar{x} , \end{displaymath}

ahol $\bar{x}$ a kiszolgálási idő hosszának várható értéke. A Markov-lánc ergodikus, ha $\varrho<1$. (A továbbiakban ezt feltételezzük.) Most vizsgáljuk a $q_{n+1}$ és $q_n$ valószínűségi változók kapcsolatát két speciális esetben. Az első annak felel meg, amikor $C_n$ nem üres rendszert hagy maga után (azaz $q_n>0$). Ez azt jelenti, hogy a $C_n$ távozásakor a $C_{n+1}$ már a rendszerben van. Ekkor $q_{n+1}$ nyilván megkapható, ha $q_n$-ből levonunk egyet (mivel $YC_{n+1}$ eltávozik) és hozzáadjuk azon igények számát, melyek az $x_{n+1}$ kiszolgálási időtartam alatt érkeztek be, azaz $v_{n+1}$-et. A második eset az, amikor $q_n=0$, azaz a távozó $C_n$ igény üres rendszert hagy maga után, azaz $C_{n+1}$ nem érkezett meg a $C_n$ távozási időpontjáig. Így $q_{n+1}$ éppen a $C_{n+1}$ kiszolgálási ideje alatt a rendszerbe érkezett igények számával egyenlő. Végeredményben azt kaptuk, hogy

\begin{displaymath} q_{n+1}=\cases{q_n-1+v_{n+1}&, ha $q_n>0$\cr v_{n+1}&, ha $q_n=0$.\cr} \end{displaymath}

Vezessük be a

\begin{displaymath} \Delta_k=\cases{1&, ha $k=1,2,\ldots$\cr 0&, ha $k\le 0$\cr} \end{displaymath}

mennyiségeket. Ennek segítségével

\begin{displaymath} q_{n+1}=q_n-\Delta_{q_n}+v_{n+1}.\leqno(4) \end{displaymath}

Ebből az egyenletből határozzuk meg a $q_n$ várható értékét. Először nem az időtől függő viselkedéssel foglalkozunk, hanem a határeloszlással (feltéve a létezését), azaz $\tilde{q}$-mal. Tegyük fel, hogy léteznek a $j$-edik momentumok is és

\begin{displaymath} \lim_{n\to\infty}E\left(q_n^j\right)=E\left(\tilde{q}^j\right). \end{displaymath}

(Ismét az ergodikusságot használva.) Formális számolással vegyük $(4)$ mindkét oldalának várható értékét és végezzük el az $n\to\infty$ határátmenetet.

\begin{displaymath} E\left(\tilde{q}\right)=E\left(\tilde{q}\right)-E\left(\Delta_{\tilde{q}}\right)+E\left(\tilde{v}\right). \end{displaymath}

Ebből

\begin{displaymath} E\left(\Delta_{\tilde{q}}\right)=E\left(\tilde{v}\right).\leqno(5) \end{displaymath}

Tudjuk, hogy $E\left(\tilde{v}\right)$ a beérkezések átlagos száma egy igény kiszolgálási ideje alatt. $(5)$ bal oldala definíció szerint

\begin{displaymath} E\left(\Delta_{\tilde{q}}\right)= 0\cdot P\left(\tilde{q}=... ...)+1\cdot P\left(\tilde{q}>0\right)=P\left(\tilde{q}>0\right). \end{displaymath}

Mivel egyetlen kiszolgáló csatornánk van,

\begin{displaymath} E\left(\Delta_{\tilde{q}}\right)=P(\tilde{q}>0)=P\left(\hbox{ a rendszer foglalt }\right). \end{displaymath}

A $\varrho$ kihasználtsági tényező pedig éppen a rendszer foglaltságának valószínűségét adja meg, ezért

\begin{displaymath} P\left(\hbox{ a rendszer foglalt }\right)=\varrho. \end{displaymath}

Így $(5)$ alapján

\begin{displaymath} E\left(\tilde{v}\right)=\varrho.\leqno(6) \end{displaymath}

Tehát az egy igény kiszolgálási ideje alatti beérkezések számának várható értéke $\varrho(=\lambda\bar{x})$. A stabilitáshoz megkövetelt $\varrho<1$ miatt a (6) egyenlethez szükséges, hogy az igényeknek lassabban kell érkezniük, mint ahogyan a kiszolgálás történik. $(4)$ négyzetre emelésével

\begin{displaymath} q_{n+1}^2=q_n^2+\Delta_{q_n}^2+v_{n+1}^2-2q_n\Delta_{q_n}+2q_nv_{n+1}- 2\Delta_{q_n}v_{n+1}. \end{displaymath}

Nyilvánvaló, hogy ${\left(\Delta_{q_n}\right)}^2=\Delta_{q_n}$ és $q_n\Delta_{q_n}=q_n$, így

\begin{displaymath} \eqalign{ E\left(q_{n+1}^2\right)=&E\left(q_n^2\right)+E\l... ...ft(q_nv_{n+1}\right)- 2E\left(\Delta_{q_n}v_{n+1}\right).\cr} \end{displaymath}

Mivel $v_{n+1}$ független $q_n$-től, a két utolsó tag várható értékét mint várható értékek szorzatát lehet felírni. $n\to\infty$ határátmenetet véve

\begin{displaymath} 0=E\left(\Delta_{\tilde{q}}\right)+E\left(\tilde{v}^2\right... ...- 2E\left(\tDelta_{\tilde{q}}\right)E\left(\tilde{v}\right). \end{displaymath}

$(5)$-öt és $(6)$-ot kihasználva kifejezhetjük $E\left(\tilde{q}\right)$-ot.

\begin{displaymath} 0=2E\left(\tilde{q}\right)E\left(\tilde{v}\right)+E\left(\t... ...de{v}\right)+2E\left(\tilde{v}\right)-E\left(\tilde{v}\right) \end{displaymath}


\begin{displaymath} 2E\left(\tilde{q}\right)-2\varrho E\left(\tilde{q}\right)=... ...ho\right)+E\left(\tilde{v}^2\right)-E\left(\tilde{v}\right) , \end{displaymath}

ahonnan

\begin{displaymath} E\left(\tilde{q}\right)=\varrho+{E\left(\tilde{v}^2\right)-E\left(\tilde{v}\right)\over 2\left(1-\varrho\right)}.\leqno(7) \end{displaymath}

(7)-ben már csak ismeretlen. Ennek meghatározásához egy általános módszert, a generátorfüggvények módszerét használjuk. Legyen a $\tilde{v}$ változó generátorfüggvénye.

\begin{displaymath} V\left(z\right):=E\left(tz^{\tilde{v}}\right):=\sum_{k=0}^\infty P\left(\tilde{v}=k\right)z^k. \end{displaymath}

Innen $(3)$ felhasználásával

\begin{displaymath} V\left(z\right)=\sum_{k=0}^\infty\int\limits_0^\infty{{\lef... ...a x\right)}^k\over k!}e^{-\lambda x} b\left(x\right) dx z^k= \end{displaymath}


\begin{displaymath} =\int\limits_0^\infty e^{-\lambda x}\left(\sum_{k=0}^\infty... ...imits_0^\infty e^{-\lambda x}e^{\lambda xz}b\left(x\right)dx= \end{displaymath}


\begin{displaymath} =\int\limits_0^\infty e^{-\left(\lambda-\lambda z\right)x}b\left(x\right)dx. \end{displaymath}

Legyen $B^*(s)$ a kiszolgálási idő sűrűségfüggvényének Laplace-transzformáltja, vagyis

\begin{displaymath} B^*\left(s\right):=\int\limits_0^\infty e^{-sx}b\left(x\right)dx. \end{displaymath}

A következő hasznos összefüggést vehetjük észre az előző két egyenlet között:

\begin{displaymath} V\left(z\right)=B^*\left(\lambda-\lambda z\right).\leqno(8) \end{displaymath}

Mint ismert, a generátorfüggvény deriváltjainak a $z=1$ helyen vett helyettesítési értékei, valamint a Laplace-transzformált $s=0$ helyen vett helyettesítési értékei a vizsgált valószínűségi változó megfelelő momentumait adják meg. A valószínűségi változó várható értékére a felülvonással való jelölést használva, a következőket írhatjuk:

\begin{displaymath} B^{*^{\left(k\right)}}\left(0\right):={\left(-1\right)}^kE\... ...ilde{x}^k\right)={\left(-1\right)}^k\overline{x^k} ;\leqno(9) \end{displaymath}


\begin{displaymath} V^{'}\left(1\right):={\left.{dV\left(z\right)\over dz}\right\vert}_{z=1}=E\left(\tilde{v}\right)=\bar{v} ;\leqno(10) \end{displaymath}


\begin{displaymath} V^{\left(2\right)}\left(1\right):={\left.{d^2V\left(z\right... ...)-E\left(\tilde{v}\right)= \overline{v^2}-\bar{v}.\leqno(11) \end{displaymath}


\begin{displaymath} B^*\left(0\right)=V\left(1\right)=1. \end{displaymath}

$(8)$-ból láthatóan

\begin{displaymath} {dV\left(z\right)\over dz}={dB^*\left(\lambda-\lambda z\right)\over dz}= \leqno(12) \end{displaymath}


\begin{displaymath} ={dB^*\left(\lambda-\lambda z\right)\over dz}=\left({dB^*\l... ...ight)\over dz}\right)=-\lambda{dB^*\left(y\right)\over dy} , \end{displaymath}

ahol $y=\lambda-\lambda z$. Végezzük el a $z=1$ helyettesítést. Ekkor

\begin{displaymath} V^{'}\left(1\right)=-\lambda{\left.{dB^*\left(y\right)\over dy}\right\vert}_{z=1}= -\lambda B^{*^{'}}\left(0\right). \end{displaymath}

mivel $z=1$-nél $y=0$ adódik. Ebből $(9)$-et és $(10)$-et felhasználva

\begin{displaymath} \bar{v}=\lambda\bar{x}=\varrho , \end{displaymath}

amit már az előzőekből ismerünk. Most differenciáljuk még egyszer $(12)$-t:

\begin{displaymath} {d^2V\left(z\right)\over dz^2}={d^2B^*\left(\lambda-\lambda z\right)\over dz^2}. \end{displaymath}

$B^*$ első deriváltját felhasználva a másodikra az alábbi összefüggés adódik:

\begin{displaymath} {d^2B^*\left(\lambda-\lambda z\right)\over dz^2}={d\over dz... ...dy\over dz}\right)=\lambda^2{d^2B^*\left(y\right)\over dy^2}. \end{displaymath}

f $z=1$-et helyettesítve

\begin{displaymath} V^{\left(2\right)}\left(1\right)=\lambda^2B^{*^{\left(2\right)}}\left(0\right). \end{displaymath}

A korábbiakból

\begin{displaymath} \overline{v^2}-\bar{v}=\lambda^2\overline{x^2}. \end{displaymath}

A további momentumok is hasonlóan határozhatók meg. Térjünk vissza $(7)$-hez és alkalmazzuk az előző összefüggést, adódik

\begin{displaymath} \bar{q}=\varrho+{\lambda^2\overline{x^2}\over 2\left(1-\varrho\right)}.\leqno(13) \end{displaymath}

Mivel $\lambda^2\overline{x^2}=\lambda^2\left(\sigma_b^2+\bar{x}^2\right)= \lambda^2\sigma_b^2+\varrho^2$, ahol $\sigma_b^2$ a kiszolgálási idő szórásnégyzete, $(13)$ más alakban:

\begin{displaymath} \bar{q}=\varrho+{\varrho^2+\lambda^2\sigma_b^2\over 2\left(1-\varrho\right)}.\leqno(13a) \end{displaymath}

Ez a keresett formula, ami az átlagos sorhosszat, azaz az $M/G/1$ rendszerben tartózkodó igények számának várható értékét adja meg ismert mennyiségek segítségével. Ezt Pollaczek-Hincsin-féle (P-H) várható érték-formulának nevezzük. A P-H várható érték-formula a $\bar{q}$ mennyiségekre, a távozási pillanatokban a rendszerben tartózkodó igények számának várható értékére ad egy kifejezést. De tudjuk, hogy aérkezési pillanatokban, sőt bármelyik pillanatban is ez a várható érték. Az általában használt jelölés szerint $\bar{N}$ jelenti ezt a mennyiséget. Vezessük be most $\bar{N}_q$-t a sorbanálló igények számának várható értékeként (ez nem tartalmazza a kiszolgálócsatornában lévő igényt).

\begin{displaymath} \bar{N}:=\sum_{k=0}^\infty kP\left(\tilde{q}=k\right) ; \end{displaymath}


\begin{displaymath} \bar{N}_q=\sum_{k=1}^\infty \left(k-1\right)P\left(\tilde{q}=k\right). \end{displaymath}

Innen

\begin{displaymath} \bar{N}_q=\sum_{k=0}^\infty kP\left(\tilde{q}=k\right)-\sum_{k=1}^\infty P\left(\tilde{q}=k\right)= \bar{N}-\varrho, \end{displaymath}


\begin{displaymath} \bar{N}_q={\varrho^2+\lambda^2\sigma_b^2\over 2(1-\varrho)}. \end{displaymath}

Bebizonyítunk egy általános eredményt, az első Little-formulát, ami a beérkezési intenzitás, a rendszerben tartózkodó igények számának várható értéke és az igények rendszerbeli idejének várható értéke között ad meg egy egyszerű összefüggést. Legyen $\alpha(t)$ a $(0,t)$ intervallum alatt beérkezett igények száma, $\delta(t)$ a $(0,t)$ intervallum alatt a rendszerből kilépett igények száma. $N(0)=0$-t feltéve nyilvánvalóan $N(t)=\alpha(t)-\delta(t)$. Jelölje a $(0,t)$ intervallumban a beérkezési intenzitást

\begin{displaymath} \bar{\lambda}_t:={\alpha(t)\over t}. \end{displaymath}

$\gamma(t)$ legyen a $t$ pillanatig felgyűlt összes igényidő, pontosabban az az idő, amit a $(0,t)$ időtartam során az igények összesen eltöltöttek a rendszerben. A $\overline{T}_t$ mennyiség legyen az egy igényre eső rendszerbeli idő átlaga, a $(0,t)$ intervallum összes igényét figyelembe véve. Ezekből nyilván

\begin{displaymath} \overline{T}_t={\gamma(t)\over\alpha(t)}. \end{displaymath}

Végül legyen $\bar{N}_t$ a rendszerben tartózkodó igények átlagos száma a $(0,t)$ intervallumban:

\begin{displaymath} \bar{N}_t={\gamma(t)\over t}. \end{displaymath}

Az utolsó három egyenletből

\begin{displaymath} \bar{N}_t=\bar{\lambda}_t \bar{T}_t. \end{displaymath}

Sorbanállási rendszerünkben (ergodikusság esetén) léteznek az alábbi határértékek

\begin{displaymath} \bar{\lambda}=\lim\limits_{t\to\infty}\bar{\lambda}_t ,\ \ \ \ \ \ \ \ \bar{T}=\lim\limits_{t\to\infty}\bar{T}_t. \end{displaymath}

Így (Little-formula)

\begin{displaymath} \bar{N}=\bar{\lambda}\bar{T}. \end{displaymath}

Most levezetünk egy eredményt a rendszerben eltöltött átlagos időre. Ha felhasználjuk a fenti Little-formulát, $\bar{N}=\bar{\lambda}\bar{T}$-t, valamint $(13)$-at, és tudjuk, hogy $\bar{q}$ egy találomra választott időpontra is megadja a rendszerben található igények számának várható értékét, azaz $\bar{q}=\bar{N}$, akkor

\begin{displaymath} \bar{N}=\v(arrho+{\varrho^2+\lambda^2\sigma_b^2\over 2\left(1-\varrho\right)}= \bar{\lambda}\bar{T}. \end{displaymath}

Innen

\begin{displaymath} \bar{T}=\bar{x}+{\varrho\bar{x}+\lambda\sigma_b^2\over 2\left(1-\varrho\right)}. \end{displaymath}

Ez egy igény rendszerben eltöltött összidejének átlaga, ami egyenlő az átlagos kiszolgálási időnek, valamint a sorbanállási idő átlagának összegével, amit $\bar W$-vel jelölünk. Így

\begin{displaymath} \bar{W}={\varrho\bar{x}+\lambda\sigma_b^2\over 2\left(1-\varrho\right)} , \end{displaymath}

vagy

\begin{displaymath} \bar{W}={\bar{W}_0\over 1-\varrho} ,\leqno(14) \end{displaymath}

ahol $\bar{W}_0:={\lambda\overline{x^2}\over 2}$, az új igény érkezésekor a kiszolgálócsatornában található igény átlagos hátralévő kiszolgálási ideje. Ezt megkaphatjuk a hátralévő élettartamra vonatkozó képletünkből, ami

\begin{displaymath} r_1={m_2\over 2m_1}={m_1\over 2}+{\sigma^2\over 2m_1}={\lambda\overline{x^2}\over 2\varrho} , \end{displaymath}

mivel itt $m_1=\bar{x},\ m_2=\overline{x^2}$. Viszont ez hátralévő élettartam esetén teljesül, hiszen élettartamról akkor beszélhetünk, ha ,,létezik" az a bizonyos dolog, tehát már ,,él". ,,Kiszolgálási terminológiánk" alapján ezt meg kell még szoroznunk annak a valószínűségével, hogy van igény a kiszolgálócsatornában, azaz van értelme hátralévő kiszolgálási időről beszélnünk. Jelen esetben a rendszer foglaltságának valószínűsége $\varrho$, tehát

\begin{displaymath} \bar{W}_0=r_1\cdot\varrho={\lambda\overline{x^2}\over 2\varrho}\cdot\varrho={\lambda\overline{x^2}\over 2}. \end{displaymath}

Ha tekintjük a ${\bar{T}\over\bar{x}}$ hányadost, ami azt fejezi ki, hogy milyen ,,kényelmetlenséget" okoz a rendszer az igényeknek azzal, hogy más igényekkel is osztozniuk kell a kiszolgálóegységeken, a következőt kapjuk:

\begin{displaymath} {\bar{T}\over\bar{x}}=1+{\varrho+{\lambda\over\bar{x}}\sigma_b^2\over 2\left(1-\varrho\right)} ,\leqno(15) \end{displaymath}

és hasonlóan

\begin{displaymath} {\bar{W}\over\bar{x}}={\varrho+{\lambda\over\bar{x}}\sigma_b^2\over 2\left(1-\varrho\right)} ;\leqno(16) \end{displaymath}

$(14)$-et valamint $(15)$-öt és $(16)$-ot szintén P-H várható érték-formulának nevezzük.

 

Nyitólap    Tartalomjegyzék    Fejezetek ( B I II III IV F )    Letöltések
FRAME-mel FRAME nélkül
<<   Előző Következő  >>