Informatikai rendszerek modellezése

Dr. Sztrik, János

Új Széchenyi Terv logó.

Debreceni Egyetem

Kelet-Magyarországi Informatika Tananyag Tárház

Nemzeti Fejlesztési Ügynökség http://ujszechenyiterv.gov.hu/ 06 40 638-638

Lektor

Dr. Bíró József

BME, Távközlési és Médiainformatikai Tanszék, egyetemi tanár, MTA doktora

A tananyagfejlesztés az Európai Unió támogatásával és az Európai Szociális Alap társfinanszírozásával a TÁMOP-4.1.2-08/1/A-2009-0046 számú Kelet-Magyarországi Informatika Tananyag Tárház projekt keretében valósult meg.


Tartalom

Előszó
I. Informatikai rendszerek modellezése, analízise
1. Valószínűségszámítási alapok
1.1. Valószínűségszámítási összefoglaló
1.2. Nevezetes diszkrét eloszlások
1.3. Nevezetes abszolút folytonos eloszlások
2. A sztochasztikus modellezés alapjai
2.1. Az exponencális eloszlással kapcsolatos eloszlások
2.2. Megbízhatóság-elméleti alapok
2.3. Véletlen számok generálása
2.4. Véletlen tagszámú összegek
3. Analitikus eszközök
3.1. Generátorfüggvény
3.2. Laplace-transzformált
4. Sztochasztikus rendszerek
4.1. Poisson-folyamat
4.2. Egyszerűbb rendszerek vizsgálata
5. Folytonos idejű Markov-láncok
5.1. Születési-halálozási folyamatok
II. Feladatgyűjtemény
6. Valószínűségszámítási alapok
6.1. Diszkrét eloszlások
6.2. Folytonos eloszlások
7. A sztochasztikus modellezés alapjai
7.1. Az exponenciális eloszlás és a belőle származtatott eloszlások
7.2. Megbízhatóság-elméleti alapok
7.3. Véletlen tagszámú összegek
8. Analitikus eszközök
8.1. Generátorfüggvény
8.2. Laplace-transzformált
9. Sztochasztikus rendszerek
9.1. Poisson-folyamat
9.2. Esettanulmányok
III. A sorbanállási elmélet alapjai
10. A sorbanállási elmélet alapfogalmai
10.1. A sorbanállási rendszerek jellemzői
10.2. Kendall-féle jelölés-rendszer
10.3. Születési-halálozási folyamatokra vonatkozó összefüggések
10.4. Sorbanállási szoftverek
11. Végtelen-forrású rendszerek
11.1. Az M/M/1 típusú sorbanállási rendszer
11.2. rendszer tétovázó (elriasztott) igények esetében
11.3. Prioritásos rendszer
11.4. Az típusú, véges befogadóképességű rendszer
11.5. Az típusú rendszer
11.6. Az típusú Erlang-féle veszteséges rendszer
11.7. Az típusú rendszer
11.8. Az rendszer
11.9. Az rendszer
12. Véges-forrású rendszerek
12.1. Az modell, Engset-féle veszteséges rendszer
12.2. Az modell
12.3. Inhomogén modellek
12.3.1. Az rendszer
12.3.2. Az rendszer
12.3.3. Az rendszer
12.3.4. Rendszerjellemzők
12.4. Homogén forrású modellek összehasonlítása
12.5. Az modell
12.5.1. A várakozási idő eloszlásfüggvénye
12.5.2. A tartózkodási idő Laplace-transzformáltja
12.6. Az rendszer
12.7. Az rendszer
12.8. A modell
12.8.1. A stacinárius eloszlás meghatározása
IV. Feladatgyűjtemény
13. Végtelen-forrású rendszerek
14. Véges-forrású rendszerek
15. Függelék
Irodalomjegyzék

Az ábrák listája

4.1. A példa állapot átmenetei
4.2. 2 gép, 2 szerelő
4.3. 2 gép, 1 szerelő
4.4. A példa állapot átmenet diagramja
4.5. FIFO kiszolgálási elv
4.6. Processor-sharing kiszolgálási elv
4.7. Abszolút prioritásos kiszolgálási elv
9.1. Hidegtartalék
9.2. Melegtartalék
9.3. A feladat
9.4. A feladat
9.5. A feladat
11.1. Az Az n^{*} pontos és közelítő értékei pontos és közelítő értékei
12.1. A példához tartozó A példához tartozó P_{n} értékek értékek
12.2. A példához tartozó A példához tartozó P_{k} értékek értékek
12.3. Futási eredmények
12.4. A különböző állapotok valószínűségei
12.5. A példához tartozó adatok
12.6. Stacionárius eloszlás
12.7. időegységre jutó költségek
15.1. A generátorfüggvény néhány fontos tulajdonsága
15.2. A Laplace-transzformált néhány fontos tulajdonsága

Jelen jegyzetet feleségemnek ajánlom, aki nélkül ez a munka sokkal hamarabb elkészült volna.

  • Ha valami egyszer elromolhat, akkor el is fog romlani.

  • A szakértői rendszerek arról ismerhetők fel, hogy abból az ismeretből, miszerint „egy rózsa illatosabb, mint egy káposztafej”, azt a következtetést vonják le, hogy a rózsából jobb levest is lehet főzni.

  • Minél kevesebb funkciója van egy programnak, annál tökéletesebben hajtja végre azokat.

  • Az a vírus, amelyik megtámadta gépedet csak azokat az állományokat fertőzi meg, amelyekről nincsenek biztonsági másolataid.

  • Hibátlan program megírása olyan, mint a kör négyszögesítése. Mindenki azt hiszi, hogy lehetséges, de ilyent még senki sem látott.

  • a egy rövid sor felé haladsz, az orrod előtt hosszú lesz belőle.

  • Ha hosszú sorban várakozol, a mögötted állókat új, rövidebb sorba terelik át.

  • Ha kilépsz egy pillanatra a rövid sorból, azonnal meghosszabbodik.

  • Ha rövid sorban várakozol, az előtted állók beeresztik barátaikat és rokonaikat, így lesz hosszú sor belőle.

  • Az, ami rövid sor az épületen kívül, valójában hosszú sor az épületen belül.

  • Ha elég hosszú ideig állsz egy helyben, sorbanállást idézel elő.

(Arthur Block: Murphy törvénykönyve)

Előszó

A mindennapi élet egyre több cselekvését átszövő modern infokommunikáció állandó fejlesztésre ösztönzi a szakembereket. Természetesen ez nem korlátozható egyetlen tudományágra, hiszen fontos szerepet játszanak a mérnökök és az elméleti kutatást végző tudósok is. Az informatikai rendszerek sok alkalmazási területet ölelnek fel, többek között a fent említett infokommunikációs hálózatokat. Hogy jobban megértsük a háttérben zajló fejlesztő munka egyes lépéseit, szükségünk van pl. az igények kiszolgálási folyamatát modellező matematikai módszerek és eszközök megismerésére. A kiszolgálási rendszerek hatékonyságának, megbízhatóságának elemzése az alkalmazott matematika egyik legdinamikusabban fejlődő területe. A gyakorlatban felmerülő problémák újabb és újabb módszerek kidolgozását igénylik.

Jelen segédletben a megbízhatóság-elméleti és sorbanállási problémákra koncentrálva a legfontosabbnak ítélt eljárásokat és megközelítéseket tárgyalom. Az összeállított Markovi-szintű modellek felépítése csupán alapvető valószínűségszámítási ismereteket tételez fel. Próbálok betekintést nyújtani a modellalkotásba, a képletek származtatásába kiszámításába és az eredmények kiértékelésébe.

A jegyzete célja, hogy az olvasókat megismertessem a sztochasztikus modellezés alapvető fogalmaival, eszközeivel és eljárásaival. Fontos szerep jut a szemléletmód kialakításának hiszen értelmes választ csak értelmes kérdésre lehet adni. Hiába a szép, zárt-alakú analitikus matematikai képlet, ha nem tudjuk kiszámítani. Ezért mutatom meg, hogyan lehet ugyanazt a problémát különböző oldalról is megközelíteni. Ne elégedjünk meg csak egyfajta megoldással, ha lehetséges más módszerrel is ellenőrizzük az eredményeket!

Arra törekedtem, hogy mind a mérnöki, mind pedig a matematikusi gondolkodásmód is helyet kapjon. Sok esetben megadtam a pontos formulák rekurzív illetve közelítő kiszámítási lehetőségét is. Egyszerű példákon keresztül igyekeztem megmutatni a szokásos megoldási eljárásokat és a matematikai módszereket. Az alapvető cél, hogy meglássuk mi van az analitikus képletek mögött, vagyis hogyan kapjuk őket. Ez azért fontos, hogy az olvasók később maguk is képesek legyenek a saját képleteiket megalkotni.

Hangsúlyozni kell, hogy ezek az egyszerű modellek egy nagyon fontos feltevésen alapulnak, nevezetesen, hogy a fellépő valószínűségi változók exponenciális eloszlásúak. Ezen eloszlás emlékezetnélkülisége lehetőséget ad arra, hogy a rendszerek működési jellemzőit viszonylag egyszerű matematikai módszerekkel határozzuk meg. Természetesen a gyakorlatban az exponenciális eloszlás mellett számos más eloszlás is szerepet kap, de a velük való modellezés már jóval bonyolultabb matematikai megközelítést igényel. Véleményem szerint az exponenciális eloszláson alapuló modellezés azért jelentős, mert segít a szemléletmód kialakításában, viszonylag egyszerű eszközökkel megadhatjuk a rendszer különböző paramétereinek a rendszerjellemzőkre gyakorolt hatását és ezzel felkészülhetünk a várható trendekre. Az analitikus módszerek jó kiindulási alapot szolgáltatnak a numerikus és szimulációs megközelítésekhez, hiszen segítségükkel a bonyolultabb rendszerek működését leíró modelleket validálhatjuk. A jegyzet a sztochasztikus folyamatok elméletéből csak annyit használ fel amennyire a modellalkotásnál és a hatékonysági mutatók kiszámításánál szükségünk van. Bizonyítás nélkül átvesz alapvető tételeket és az alkalmazásra koncentrál.

Be kell vallanom, hogy a jegyzet stílusának kialakításában Kleinrock [41] könyve döntő szerepet játszott. Nem követtem a szigorú definíció-tétel-bizonyítás lépéssorozatot, és így igyekeztem a nem matematikus olvasók részére is hasznos segédletet adni. Azonban vannak olyan fejezetek, ahol ez a szigorú felépítés a történeti hűség miatt megmaradt.

A jegyzet az alapképzésben részvevő mérnök informatikus, programtervező informatikus, gazdaságinformatikus, alkalmazott matematikus hallgatóknak készült, de utolsó fejezeteit mesterszakos hallgatók is jól használhatják. Több szemeszter anyagát öleli fel, kiforrott összeállítás, hiszen korábbi időszakban az osztatlan egyetemi képzés keretében sok éven át oktattam. Újdonság, hogy a különböző sorbanállási rendszerek jellemzőit könnyen ki tudjuk számítani az erre a célra írt Java-appletek segítségével, melyek a Gyakorlati sorbanállási elmélet elektronikus oktatási segédlet kisebb, de nagyon fontos részét alkotják, és megtalálhatók a szerző honlapján, így internetes környezetben a jegyzet hatékonyan használható. Természetesen ezen appletek más, bonyolultabb rendszerek jellemzőit is meghatározzák, de ezekre csak hivatkozást adok.

Arra törekedtem, hogy az adott problémát valószínűségszámítási szempontból lehetőleg teljes egészében tárgyaljam, vagyis nem elégedtem meg csak a várható értékekkel, hanem igyekeztem megadni a sűrűségfüggvényt, eloszlásfüggvényt, generátorfüggvényt, és a Laplace-transzformáltat is. Az elméleti problémákat a jobb megértés végett sok esetben példákkal illusztráltam és feladatokat gyűjtöttem össze, melyekhez megadtam a megoldást is. Meggyőződésem és tapasztalatom, hogy a jegyzet hiánypótló, tudtommal Magyarországon nincs olyan segédlet, amely ilyen részletességgel tárgyalja ezen témakört.

Köszönöm Bíró József egyetemi tanár lelkiismeretes lektori munkáját, amely javította a jegyzet tartalmát és formáját. A Latex szerkesztésben sok segítséget kaptam Kósa Márktól, Barnák Alberttől, Máté Balázstól, akiknek ezúton is szeretném kifejezni hálámat.

Az előforduló hibákra vonatkozó észrevételeket és mindenfajta javító szándékú megjegyzést örömmel veszek az alábbi címen:

sztrik.janos@inf.unideb.hu

http://irh.inf.unideb.hu/user/jsztrik/index.html

Debrecen, 2011.

A Szerző

I. rész - Informatikai rendszerek modellezése, analízise

1. fejezet - Valószínűségszámítási alapok

Sztochasztikus modellezés elképzelhetetlen valószínűségszámítási módszerek nélkül. Az a tapasztalatom, hogy érdemes a legfontosabb fogalmakról, tételekről egy rövid összefoglalót adni, mert a hallgatók esetleg más szinten és különböző megközelítésben tanulták ezt a tantárgyat. Csak azokat a tételeket sorolom fel, amiket többször használok majd és esetleg az alapozó oktatásnál nem került sor az ismertetésükre. Magyarországon bőséges forrás áll rendelkezésünkre, akár nyomtatott akár pedig digitális anyagokat tekintünk. Úgy gondolom, hogy Prékopa András [52] és Rényi Alfréd [57] klasszikus könyve minden intézményben megtalálható. Digitális formában számos jegyzetet és könyvet lehet letölteni mind magyar, mind pedig angol nyelven.

1.1. Valószínűségszámítási összefoglaló

1.1. Tétel. Teljes valószínűség tételének főbb alakjai: Legyen pozitív valószínűségű eseményekből álló teljes eseményrendszer, pedig tetszőleges esemény. Ekkor

ahol

1.2. Tétel. Bayes-tétel: Legyen pozitív valószínűségű eseményekből álló teljes eseményrendszer, pedig tetszőleges, pozitív valószínűségű esemény. Ekkor

1.3. Definíció. Azt mondjuk, hogy a , , eloszlású valószínűségi változónak van véges várható értéke, ha a sor abszolút konvergens. Ekkor a várható értéke

1.4. Definíció. Legyen a valószínűségi változó sűrűségfüggvénye . Ha véges akkor azt mondjuk, hogy -nek létezik véges várható értéke. Ekkor az

által meghatározott mennyiség létezik és véges. Az számot várható értékének nevezzük.

Bizonyítás nélkül felsoroljuk a várható érték főbb tulajdonságait.

Hogyha , akkor

  1. is létezik, és ,

  2. is létezik, és ,

  3. is létezik, és , ha és függetlenek,

  4. is létezik, és ,

  5. is létezik, és , ha léteznek a második momentumok,

  6. .

1.5. Tétel. A teljes momentum tétel: A teljes momentum tétel leggyakrabban használt alakja

ahol a feltételes -edik momentum. Használatos még az

alak is. esetben a teljes várható érték tételét kapjuk.

1.6. Definíció. Szórásnégyzet: Legyen valószínűségi változó, tegyük fel, hogy létezik és véges. A

mennyiséget (feltéve, hogy véges) szórásnégyzetének nevezzük.

Igazak a következőek

  1. Ha akkor .

  2. bármely esetén.

  3. ; akkor és csak akkor, ha .

1.2. Nevezetes diszkrét eloszlások

Binomiális eloszlás

A valószínűségi változót -ed rendű, paraméterű, vagy paraméterű binomiális eloszlásúnak nevezzük, ha a számokat rendre

valószínűséggel veszi fel. Jelölése: .

Bebizonyítható, hogy

Ha , akkor -t Bernoulli-eloszlásúnak nevezzük.

Poisson-eloszlás

A valószínűségi változót paraméterű Poisson-eloszlásúnak nevezzük, ha a valószínűségi változó a számokat rendre

valószínűséggel veszi fel. Jelölése: .

Jól ismert, hogy

Meg lehet mutatni, hogy

vagyis a binomiális eloszlást jól lehet közelíteni a Poisson-eloszlással. Ez a közelítés annál jobb, minél közelebb van a a nullához. Egy elfogadott szabály a közelítésre és .

Geometriai eloszlás

A valószínűségi változót paraméterű geometriai eloszlásúnak nevezzük, ha a valószínűségi változó a számokat rendre

valószínűséggel veszi fel. Jelölése: .

Bebizonyítható, hogy

A valószínűségi változót paraméterű módosított geometriai eloszlásnak nevezzük. Ekkor

Konvolúció

1.7. Definíció. Legyenek és független valószínűségi változók , eloszlással, . Ekkor a eloszlása

melyet a fenti eloszlások konvolúciójának nevezünk, vagyis a eloszlását határozzuk meg ily módon.

1.1. Példa. Mutassuk meg, hogyha , függetlenek, akkor !

Megoldás:

1.2. Példa. Igazoljuk, hogyha Po(), Po() függetlenek, akkor !

Megoldás:

1.3. Példa. Egy forgalmas áruházban paraméterű Poisson-eloszlással érkeznek látogatók. Mindegyikből a többitől függetlenül valószínűséggel lesz vásárló. Határozzuk meg a vásárlók számának az eloszlását!

Megoldás: Legyen a látogatók száma, vásárlók száma. Ekkor teljes valószínűség tétele alapján

Vagyis azt láthatjuk, hogy .

1.3. Nevezetes abszolút folytonos eloszlások

Egyenletes eloszlás

A valószínűségi változót az intervallumon egyenletes eloszlásúnak nevezzük, ha sűrűségfüggvénye

Könnyen látható, hogy eloszlásfüggvénye

Jelölése: .

Megmutatható, hogyha , akkor .

A véletlen számok generálásánál fontos szerepet játszik, hogyha létezik, akkor és így .

Ezt az alábbi módon mutathatjuk meg

vagyis . Ebből .

Exponenciális eloszlás

A valószínűségi változót paraméterű exponenciális eloszlásúnak nevezzük, ha sűrűségfüggvénye

Ebből pedig eloszlásfüggvénye

ahol rögzített. Jelölése: .

Belátható, hogy

Erlang-eloszlás

Az valószínűségi változót paraméterű Erlang-eloszlásúnak nevezzük, ha sűrűségfüggvénye

Hosszadalmasabb számolással bebizonyítható, hogy eloszlásfüggvénye

ahol természetes szám, . Jelölése: , vagy .

Könnyen látható, hogy esetben az exponenciális eloszlást kapjuk vissza.

Megmutatható, hogy

Gamma eloszlás

A valószínűségi változót paraméterű -eloszlásúnak nevezzük, ha sűrűségfüggvénye

ahol , ,

az úgynevezett teljes gamma-függvény.

Az eloszlásfüggvény explicite nem adható meg, kivéve az esetet.

Jelölése: .

Megmutatható, hogy

Az -t alak-paraméternek, -t pedig skála-paraméternek szokás nevezni.

esetben az paraméterű Erlang-eloszlást kapjuk vissza.

Weibull-eloszlás

A valószínűségi változót paraméterű Weibull-eloszlásúnak nevezzük, ha sűrűségfüggvénye

Könnyű látni, hogy

ahol ú.n. bf skála-paraméter, ú.n. alak-paraméter.

Speciálisan esetben az exponenciális eloszlást kapjuk vissza.

Jelölése: .

Megmutatható, hogy

Pareto-eloszlás

A valószínűségi változót paraméterű Pareto-eloszlásúnak nevezzük, ha sűrűség- és eloszlásfüggvénye

ahol .

Jelölése: , ahol a hely-paraméter, pedig az alak-paraméter.

Megmutatható, hogy

Így

Pareto-eloszlást követ például: egy általános processz CPU ideje, valamely file mérete egy Internet-szerveren, valamely web-böngésző gondolkodási ideje. -ra a következő intervallumokat becsülték az előbb említett jelenségeknél: , , .

Normális eloszlás (Gauss-eloszlás)

A valószínűségi változót paraméterű normális eloszlásúnak nevezzük, ha sűrűség- és eloszlásfüggvénye

ahol , . Jelölése: . -re nincs zárt alakú kifejezés.

Speciálisan, ha , , akkor , amit standard normálisnak nevezünk.

Ekkor ennek sűrűség- és eloszlásfüggvénye

Be lehet bizonyítani, hogy ha , akkor

továbbá . Jól ismert, hogy

Lognormális eloszlás

Legyen , akkor a valószínűségi változót lognormális eloszlásúnak nevezzük, jelölése .

Nem nehéz látni, hogy ekkor

és ebből

Megmutatható, hogy

1.8. Tétel. Markov-egyenlőtlenség: Legyen nemnegatív valószínűségi változó, melyre , tetszőleges szám. Ekkor

1.9. Tétel. Csebisev-egyenlőtlenség: Tegyük fel, hogy , és tetszőleges szám. Ekkor

1.10. Tétel. Központi (centrális) határeloszlás-tétel: Legyenek a független, azonos eloszlású valószínűségi változók, melyekre , . Ekkor

Speciálisan, ha , akkor és így

Ennek lokális alakja

Tapasztalatok azt mutatják, hogy ha és , akkor a normális eloszlás jó közelítést ad a binomiális eloszlásra.

2. fejezet - A sztochasztikus modellezés alapjai

Ebben a fejezetben a Markovi-szintű modellezésben fontos szerepet játszó alapvető eloszlásokat ismerhetjük meg. Szó esik a megbízhatóság-elméletben előforduló rendszerek sztochasztikus viselkedésének leírásáról és módszereket adunk meg a fontos jellemzők meghatározására. Megmutatjuk hogyan tudunk a szimulációs eljárásokhoz szükséges adott eloszlású véletlen számokat generálni. Végül tárgyaljuk a véletlen tagszámú összegeket, amely a gyakorlatban nagyon sokszor előfordulnak.

Az anyag összeállításában főleg Allen [2], Gnyedenko, Beljajev, Szolovjev [24], Jereb, Telek [36], Kleinrock [41], Ovcharov [51], Ravichandran [55], Ross [58], Tijms [75], Trivedi [78] könyvekre támaszkodtunk.

2.1. Az exponencális eloszlással kapcsolatos eloszlások

2.1. Tétel. Örökifjú tulajdonság: Ha akkor teljesülnek a következő, úgynevezett örökifjú ( emlékezetnélküliség ) tulajdonságok

Bizonyítás.

A második forma bizonyítása hasonlóan történik.

2.2. Tétel. , ahol o(h)(kisordó h) olyan mennyiség ami h-nél gyorsabban tart 0-hoz, azaz .

Bizonyítás. Mint látható az állítás ekvivalens

-val, amit a L'Hospital szabály felhasználásával bizonyítunk be, azaz

2.3. Tétel. Ha a valószínűségi változó eloszlásfüggvénye, melyre , valamint

akkor , ha .

Bizonyítás. Látható, hogy a feltételekből

összefüggést nyerjük, ebből pedig

Felhasználva, hogy kapjuk, hogy , ezzel pedig

Az alkalmazások során nagyon fontos szerepet játszik az alábbi állítás, amelynek segítségével párhuzamosan játszódó folyamatok közül tudjuk meghatározni a legelső esemény időtartamának az eloszlását.

2.4. Tétel. Ha függetlenek, akkor

szintén exponenciális eloszlású, mégpedig paraméterrel.

Bizonyítás. Jelen esetben felhasználjuk, hogy a komplementer esemény valószínűségéből hogyan határozhatjuk meg a kérdéses esemény valószínűségét, vagyis

2.1. Példa. Legyen , pedig paraméterű független exponenciális eloszlású valószínűségi változó. Határozzuk meg annak a valószínűségét, hogy !

Megoldás: akkor és csak akkor ha . A teljes valószínűség tételét felhasználva kapjuk, hogy

2.2. Példa. Párhuzamosan kapcsolt rendszerek élettartamának eloszlása: Legyenek független valószínűségi változók, valamint . Határozzuk meg eloszlásfüggvényét!

Megoldás:

Ha , akkor

Ha pedig , akkor .

2.3. Példa. Mi lesz a párhuzamosan kapcsolt rendszer élettartamának várható értéke, 2 darab inhomogén, exponenciális eloszlású elem esetén?

Megoldás: Oldjuk meg először a példát a definíciót követve!

Ekkor

Így

Egyszerű számolással látható, hogy ez tovább írható a következő formulába

Nézzük most meg, hogyan oldhatjuk meg ezt a példát rövidebben!

Kezdő állapotban mindkét gép jó és az első meghibásodás várható ideje

míg a második meghibásodás az első meghibásodásától számolva akkor történik ha az első elromlott és utána a második is vagy fordítva amiből az exponenciális eloszlás örökifjú tulajdonságát és a teljes várható érték tételt felhasználva következik, hogy a második meghibásodás várható ideje az első meghibásodás után

Így az átlagos működési idő

Homogén esetben ebből lesz, amint ezt a következő példából is látni fogjuk.

2.4. Példa. Párhuzamosan kapcsolt rendszer esetén mi a rendszer élettartamának várható értéke és szórásnégyzete, ha homogének az elemek , és függetlenek?

Megoldás:

Használjuk fel, hogy ha akkor

A helyettesítést alkalmazva kapjuk, hogy

A exponenciális eloszlás örökifjú tulajdonságából következik, hogy a meghibásodások közötti időtartamok is exponenciális eloszlásúak lesznek. Könnyen látható, hogy a -dik és -dik meghibásodás közötti idő paramétere , , és ezek az időtartamok egymástól függetlenek is az exponenciális eloszlás tulajdonságai miatt. Ezt a tényt nagyon jól tudjuk hasznosítani a -dik meghibásodás várható értékének és szórásnégyzetének a meghatározásához.

Ezek után érthető módon

Ebből a párhuzamosan kapcsolt rendszer élettartamának szórásnégyzete

2.5. Definíció. Legyenek és független valószínűségi változók és sűrűségfüggvénnyel. Ekkor a sűrűségfüggvénye

melyet és konvolúciójának nevezünk.

Ha és , akkor

2.5. Példa. Legyenek és független, paraméterű exponenciális eloszlású valószínűségi változók. Határozzuk meg sűrűségfüggvényét!

Megoldás: Az előző képlet alapján, behelyettesítve az exponenciális eloszlás sűrűségfüggvényét kapjuk

ami azt mutatja, hogy független, azonos paraméterű exponenciális eloszlású valószínűségi változók összege nem exponenciális eloszlást követ.

2.6. Példa. Legyenek független, paraméterű exponenciális eloszlású valószínűségi változók. Mutassuk meg, hogy

Megoldás: A bizonyítást teljes indukcióval fogjuk végezni, ahol felhasználjuk az előző példa eredményeit is. -re és -re láttuk, hogy igaz. Tegyük fel, hogy -re is igaz és nézzük meg -re mi történik!

ami éppen az paraméterű Erlang-eloszlás sűrűségfüggvénye.

Ez nagyban megkönnyíti a várható érték és a szórásnégyzet meghatározását.

Az Erlang-eloszlás jól használható olyan valószínűségi változók eloszlásának közelítésére, melynél . Ekkor ha az első momentum adott, akkor az

és paraméterű Erlang-eloszlások keveréke, ahol

rendelkezik azzal a tulajdonsággal, hogy

Ezt az -t szokás szimbólummal is jelölni.

Hipo-exponenciális eloszlás

Legyenek () független, exponenciális eloszlású valószínűségi változók. Az valószínűségi változót hipo-exponenciális eloszlásúnak nevezzük.

Megmutatható, hogy sűrűségfüggvénye

Belátható, hogy

A hipo-exponenciális eloszlás relatív szórása , vagyis

Hiper-exponenciális eloszlás

Legyenek () független, exponenciális valószínűségi változók, pedig eloszlás. Az valószínűségi változót hiper-exponenciális eloszlásúnak nevezzük ha sűrűségfüggvénye

Eloszlásfüggvénye

Könnyű látni, hogy

Megmutatható, hogy a hiper-exponenciális eloszlás relatív szórása mindig nagyobb vagy egyenlő mint 1, vagyis

Abban az esetben, ha , akkor momentum alapján az alábbi illeszkedés ajánlatos

vagyis -drendű hiper-exponenciális eloszlású.

Mivel sűrűségfüggvényében paraméter szerepel és az illeszkedés csak momentum alapján történik, ezért végtelen sok megoldás lehetséges.

Tekintsük az úgynevezett kiegyensúlyozott várható értékek esetét, vagyis amikor

Ekkor

melyből a megoldás

Ha az , , momentumok alapján szeretnénk ezt a hiper-exponenciális eloszlást illeszteni, akkor ez csak az feltétel mellett lehetséges és ekkor egyértelmű. Meg lehet mutatni, hogy a feltétel teljesül a Gamma és lognormális eloszlásra is. Ebben az esetben

ahol

Eloszlások keveréke

2.6. Definíció. Legyenek valószínűségi változók, pedig eloszlás.

Az eloszlásfüggvényt az eloszlásfüggvények súlyokkal vett keverékének nevezzük.

Hasonlóan

Az sűrűségfüggvényt az sűrűségfüggvények súlyokkal vett keverékének nevezzük.

Könnyű belátni, hogy valóban eloszlás- illetve sűrűségfüggvény.

Ezen terminológiát használva így a hiper-exponenciális eloszlás exponenciális eloszlások keveréke.

2.2. Megbízhatóság-elméleti alapok

2.7. Definíció. Jelölje valamely elem élettartamát.

Ekkor az -t megbízhatósági-függvénynek nevezzük.

Könnyű látni, hogy , valamint .

A megbízhatósági-függvény nagyon hasznos a különböző rendszerek megbízhatósági vizsgálatában. Az előzőek alapján könnyű látni, hogy

  • Sorosan kapcsolt rendszerek esetén

  • Párhuzamosan kapcsolt rendszerek esetén

Másik fontos jellemző a meghibásodási intenzitás-függvény (megbízhatósági ráta-függvény), amelyet a következőképpen értelmezünk

Mutassuk meg, hogyan fejezhető ki a segítségével!

mivel . Így

Legyen úgynevezett kumulatív megbízhatósági intenzitás-függvény.

Ekkor

Az alábbiakban nevezetes eloszlásokra írjuk fel az , , függvényeket ahol lehet, melyek az érintett függvények definíciójából számolással következnek.

Azt is megmutatjuk milyen kapcsolat van a függvény és a relatív szórásnégyzet között.

  • Exponenciális eloszlás

  • Erlang-eloszlás

    amely monoton növekvő és értékkészlete a intervallum.

  • Weibull-eloszlás

    Vagyis -nél monoton növekvő, -nél monoton csökkenő és -nél , .

    Megmutatható, hogy

  • Pareto-eloszlás

A fenti esetek azt támasztják alá, hogyha monoton növekedő (csökkenő) az értelmezési tartományán, akkor .

Azonban ez fordítva nem igaz, mert például a lognormális eloszlás esetén először monoton növekedő, majd utána monoton csökkenő.

2.3. Véletlen számok generálása

Mint már korábban is láttuk a véletlen számok generálásánál fontos szerepet játszik az alábbi képlet

, és így

A következő részben nevezetes eloszlású véletlen számokat fogunk előállítani.

2.7. Példa. Mutassuk meg hogyan generáljunk paraméterű exponenciális eloszlást követő véletlen számokat!

Megoldás: Ha és akkor így ha tudunk [0,1]-en egyenletest generálni akkor a paraméterű exponenciális eloszlást követő véletlen számokat a

képlet segítségével generálhatunk.

2.8. Példa. Mutassuk meg hogyan generáljunk paraméterű Erlang-eloszlást követő véletlen számokat!

Megoldás: Hasonlóan az előző példához, ha tudunk [0,1]-en egyenletest generálni akkor a paraméterű Erlang-eloszlást követő véletlen számokat a

képlet segítségével generálhatunk.

2.9. Példa. Mutassuk meg hogyan generáljunk hipo-exponenciális eloszlást követő véletlen számokat!

Megoldás: Hasonlóan az előző példához, ha tudunk [0,1]-en egyenletest generálni akkor a hipo-exponenciális eloszlást követő véletlen számokat a

képlet segítségével generálhatunk.

2.10. Példa. Mutassuk meg hogyan generáljunk hiper-exponenciális eloszlást követő véletlen számokat!

Megoldás: Először generáljuk le -en egyenletes eloszlás szerint -t, majd válasszuk ki azt az i-t amelyre teljesül, hogy

Második lépésként pedig generáljunk paraméterű exponenciális eloszlást követő véletlen számot a már ismert képlet szerint!

2.11. Példa. Mutassuk meg hogyan generáljunk Weibull-eloszlású véletlen számokat!

Megoldás:

2.12. Példa. Mutassuk meg hogyan generáljunk Pareto-eloszlású véletlen számokat!

Megoldás:

2.4. Véletlen tagszámú összegek

2.8. Definíció. Legyen valószínűségi változó, valamint független, azonos eloszlású valószínűségi változók amelyek függetlenek -től is.

Az , véletlen tagszámú összegnek nevezzük (, ).

Az eloszlását, eloszlásfüggvényét és sűrűségfüggvényét a teljes valószínűség-tétel felhasználásával kapjuk. Ennek következménye a teljes momentum-tétel, amit szintén alkalmazni fogunk.

Diszkrét esetben

Folytonos esetben

2.13. Példa. Legyen , és legyen paraméterű geometriai eloszlású. Határozzuk meg sűrűségfüggvényét!

Megoldás: Vegyük észre, hogy paraméterű Erlang-eloszlású lesz, ezért annak sűrűségfüggvényét helyettesítjük be. Vagyis

Amint látható .

2.9. Tétel. A véletlen tagszámú összeg várható értéke

Bizonyítás. A teljes várható érték tételt használva

2.10. Tétel. A véletlen tagszámú összeg szórásnégyzete

Bizonyítás. A teljes momentum tétel alapján

Ebből

3. fejezet - Analitikus eszközök

A transzformáció fogalma teljesen megszokott a vizsgálatok során. Ennek a hatékony módszernek tömören az a lényege, hogyha az eredeti problémát nem tudjuk, vagy csak körülményesen tudnánk megoldani, akkor alkalmas transzformációval átvisszük egy másik feladatba, majd ennek megoldásából megpróbálunk az eredeti problémára választ adni. A transzformáció fajtája függ a probléma jellegétől. Ebben a fejezetben 2 nagyon bevált módszert mutatunk meg, amelyek lényegében a diszkrét és folytonos esetet ölelik fel. Természetesen rajtuk kívül számos más transzformáció is létezik. Gyakran előfordul, hogy ugyanannak a transzformációnak különböző nevet adnak az eltérő tudományterületek.

A tematika összeállításában főleg Allen [2], Gnyedenko, Beljajev, Szolovjev [24], Kleinrock [41], Ovcharov [51], Tijms [75], Trivedi [78] könyvekre támaszkodtunk.

3.1. Generátorfüggvény

3.1. Definíció. Legyen nemnegatív diszkrét valószínűségi változó , eloszlással.

A függvényt az generátorfüggvényének nevezzük, ahol

akkor és csak akkor létezik ha a sor konvergens.

3.2. Tétel. A generátorfüggvényekre a következő tulajdonságok teljesülnek:

1. ,

2. ,

3. ,

4. ,

5. , .

Bizonyítás. 1. .

2. .

3. innen pedig .

4.

Ebből pedig átrendezés után

3.3. Tétel. Ha függetlenek, akkor

Bizonyítás. A bizonyítás során a harmadik lépésben felhasználjuk, hogy független valószínűségi változók szorzatának várható értéke egyenlő a várható értékük szorzatával.

3.4. Tétel. A véletlen tagszámú összeg generátorfüggvénye

Bizonyítás. A teljes várható érték tétel alapján

Az alkalmazások során nagyon fontosak az alábbi tételek.

3.5. Tétel. Ha nemnegatív, egész értékű változók egy sorozata azzal a tulajdonsággal bír, hogy eloszlásaik egy határeloszláshoz konvergálnak, azaz bevezetve a jelöléseket, léteznek a határértékek és , akkor a változók generátorfüggvényei a minden pontjában konvergálnak a eloszlás generátorfüggvényéhez, azaz

ahol

Ha a határértékek léteznek, de , akkor a generátorfüggvények konvergenciája csak az intervallum belsejében érvényes.

3.6. Megjegyzés. A tétel utolsó állítását illusztrálja a következő példa:

Legyen , azaz , és , ha , akkor

Azonban

3.7. Tétel. Ha a változók generátorfüggvényei konvergálnak egy függvényhez, ha , akkor a változók eloszlásai konvergálnak ahhoz a valószínűségeloszláshoz, melynek a a generátorfüggvénye.

3.8. Megjegyzés. Ha csak azt tesszük fel, hogy létezik, ha , akkor még nem következik, hogy generátorfüggvény.

3.1. Példa. Ha a és értékeket egyforma valószínűséggel veszi fel, akkor és , vagyis nem érvényes, hogy , mivel

<examend>

Ezeket a generátorfüggvény folytonossági tételének is szokás nevezni, és nagyon jól alkalmazhatóak a határeloszlás-tételek bizonyításánál.

Nevezetes eloszlások generátorfüggvénye

3.2. Példa. Határozzuk meg a Bernoulli-eloszlás generátorfüggvényét, majd ennek segítségével a várható értéket és s szórásnégyzetet!

Megoldás:

3.3. Példa. Határozzuk meg a paraméterű Poisson-eloszlás generátorfüggvényét, majd ennek segítségével a várható értéket és s szórásnégyzetet!

Megoldás:

3.4. Példa. Határozzuk meg független Poisson-eloszlások konvolúcióját generátorfüggvény segítségével!

Megoldás: Mivel független valószínűségi változók összegének generátorfüggvény a generátorfüggvények szorzata, valamint ismerve a Poisson-eloszlás generátorfüggvényét, kapjuk

amely éppen a paraméterű Poisson-eloszlás generátorfüggvénye.

3.5. Példa. Mutassuk meg a generátorfüggvények segítségével, hogy ha , úgy, hogy !

Megoldás: Használjuk fel, hogy ha akkor !

Azt fogjuk megmutatni, hogy a binomiális eloszlás generátorfüggvénye tart a Poisson-eloszlás generátorfüggvényéhez, azaz

amely a paraméterű Poisson-eloszlás generátorfüggvénye.

3.6. Példa. Legyen függetlenek, . Határozzuk meg generátor-függvényét!

Megoldás: Felhasználva a véletlen tagszámú összeg generátorfüggvényére kimondott tételt, kapjuk

amelyből látható, hogy .

3.7. Példa. Oldjuk meg a következő differenciálegyenlet-rendszert

kezdeti feltétel mellett!

Megoldás: Az egyenletek mindkét oldalát megfelelő hatványival megszorozva kapjuk

Bevezetve a

genetátorfüggvényt, láthatjuk, hogy a deriváltak generátorfüggvényét kapjuk a bal oldalon ha összeadjuk az egyenleteket. Ezért

A kezdeti feltétel pedig

Végül a differenciálegyenlet-rendszerből egyetlen egyenletet kaptunk, nevezetesen

a kezdeti feltétel pedig

Átrendezve az egyenletet kapjuk

ennek megoldása pedig

Mivel és , így azaz .

Így amelyből láthatjuk, hogy egy paraméterű Poisson-eloszlás generátorfüggvénye, ezért keresett megoldás

3.2. Laplace-transzformált

3.9. Definíció. Legyen nemnegatív valószínűségi változó sűrűségfüggvénnyel. A függvényt az Laplace-transzformáltjának nevezzük, ahol

3.10. Tétel. A Laplace-transzformáltra a következő tulajdonságok teljesülnek

  1. ,

  2. , ha ,

  3. Ha független valószínűségi változók, akkor

  4. .

Bizonyítás. Tehát:

1.

2. első része úgy látható be, hogy nemnegatív és nemnegatív függvények integrálja is nemnegatív. A második részt pedig úgy bizonyíthatjuk be, hogy az felülről becsülhető az 1 konstans függvénnyel a intervallumon amiből azt kapjuk, hogy

3. ami függetlensége miatt , így .

4.

amiből következik, hogy .

A gyakorlati alkalmazások miatt még függvények Laplace-transzformáltjaival is kell foglalkoznunk, hiszen sok esetben differenciálegyelenteket tudunk megoldani a segítségükkel.

3.11. Tétel. Függvények Laplace-transzformáltjára igazak az alábbiak

1.

2.

Bizonyítás. 1.

2. Parciális integrálást alkalmazva

3.12. Tétel. Véletlen tagszámú összeg Laplace-transzformáltja

Bizonyítás. A teljes várható érték tétel alapján

Bizonyítás nélkül közöljük a gyakorlati alkalmazásoknál fontos alábbi állításokat.

3.13. Tétel. -re teljesülnek a következő határértékek

1. Kezdetiérték-tétel

2. Határérték-tétel

3.14. Tétel. POST-WIDDER-féle inverziós formula: Ha folytonos és korlátos -n, akkor

3.15. Tétel. Folytonossági-tétel: Tekintsük a valószínűségi változók sorozatát, melyeknek eloszlásfüggvénye . Ha , ahol valamely eloszlásfüggvénye, akkor

és fordítva.

Azaz, ha a Laplace-transzformáltak sorozata konvergál valamely valószínűségi változó Laplace-transzformáltjához, akkor .

3.8. Példa. esetén

3.9. Példa. esetén

hiszen független, azonos paraméterű exponenciális eloszlású valószínűségi változók összege.

3.10. Példa. Határozzuk meg hipo-exponenciális eloszlás esetén a Laplace-transzformáltat!

Megoldás: Az előzőekhez hasonlóan, csak most különböző paraméterek is lehetnek, ezért

A következő példa arra szolgál, hogyan tudjuk viszonylag egyszerűen meghatározni egy exponenciális eloszlású valószínűségi változó -edik momentumát. Ha ezt sűrűségfüggvény segítségével kellene megtennünk, akkor elég sokat kellene számolnunk.

3.11. Példa. Mutassuk meg Laplace-transzformált segítségével, hogyha , akkor

Megoldás:

3.12. Példa. Legyen geometriai eloszlású számláló folyamat és összeadandók. Határozzuk meg a véletlen tagszámú összeg eloszlását!

Megoldás: Mivel ha , akkor , így

Ami pedig éppen Laplace-transzformáltja.

3.16. Tétel. Keverékek Laplace-transzformáltja a Laplace-transzformáltak keveréke.

Bizonyítás. Legyen

Ekkor

3.13. Példa. Határozzuk meg a függvény Laplace-transzformáltját!

Megoldás:

3.14. Példa. Oldjuk meg Laplace-transzformált segítségével a következő differenciálegyenlet-rendszert

kezdeti feltételek mellett!

Megoldás: Vegyük mindkét oldal Laplace-transzformáltját! Ekkor

A helyettesítéses integrálás szabályát alkalmazva kapjuk, hogy

Ha korlátos azaz akkor

Így azt kapjuk, hogy

Így a mi esetünkben

valamint

Az előbbieket kihasználva kapjuk, hogy

amiből rögtön következik, hogy

Valamint

így

amiből könnyen belátható, hogy

Ebből pedig előző számításunkat felhasználva kapjuk, hogy

4. fejezet - Sztochasztikus rendszerek

Az alapozás után lehetőségünk nyílik az időben dinamikusan változó rendszerek sztochasztikus modellezésére is. Bevezetjük az alapvető fontosságú Poisson-folyamatot és megmutatjuk milyen kapcsolatban áll más ismert eloszlásokkal. Az egyszerűbb rendszerek vizsgálatával szinte építőköveket gyártunk a bonyolultabb esetekre. Megismerkedhetünk a főbb rendszerjellemzők meghatározásának a módszereivel is. Számos példán keresztül mutatjuk meg az egyes paramétereknek a rendszer hatékonysági mutatóira gyakorolt hatását. A példákat főleg Allen [2], Ovcharov [51], Trivedi [78] könyvekre támaszkodva válogattuk össze.

4.1. Poisson-folyamat

4.1. Definíció. Legyenek a egymástól független, azonos eloszlású, nemnegatív valószínűségi változók. A

valószínűségi változót felújítási folyamatnak nevezzük, az -t pedig felújítási függvénynek.

4.2. Tétel. Ha egymástól független, exponenciális eloszlású valószínűségi változók, akkor

Bizonyítás. A konstrukcióból látszik, hogy paraméterű Erlang-eloszlású valószínűségi változó, vagyis

Számolásunknál felhasználjuk majd, hogyha az A eseményből következik a B esemény azaz , akkor . Látható, hogy a mi esetünkben az A esemény és a B esemény . A következő lépésben azt használjuk ki, hogy esemény pontosan akkor következett be, ha . Tehát

Ahogy láthatjuk az események száma egy paraméterű Poisson-eloszlást követ, ezt a folyamatot nevezzük paraméterű Poisson-folyamatnak.

Könnyű látni, hogy a Poisson-folyamat esetén

1. ,

2. ,

3. .

4.3. Definíció. Ritkasági feltétel:

Jelölje a idő intervallumban bekövetkezett események számát. A konstrukcióból szintén következik, hogy csak a -tól függ és nem attól, hol helyezkedik el. Továbbá, egymásba nem metsző idő intervallumokban vett események száma egymástól független valószínűségi változók.

A Poisson-folyamatot mint számláló folyamatot vezettük be, és levezettünk a mennyiségekre egy adott hosszúságú időintervallum alatt bekövetkező érkezések számának valószínűségeloszlására egy formulát.

Vizsgáljuk most meg a beérkezések időpillanatainak együttes eloszlását, ha előre ismert, hogy éppen igény érkezett ebben az intervallumban. Osszuk fel a intervallumot diszjunkt részre a következőképpen. Az hosszúságú intervallumok előzzék meg a hosszúságú intervallumokat , és az utolsó intervallum hosszúságú legyen, továbbá

Jelentse azt az eseményt, hogy éppen egy beérkezés fordul elő minden egyes intervallumban , az intervallumban pedig egy sem. valószínűségét akarjuk kiszámolni, feltéve, hogy éppen beérkezés történik a intervallumban.

A feltételes valószínűség definíciójából

Amikor a Poisson-folyamat szerinti beérkezéseket vizsgáljuk diszjunkt időintervallumokban, akkor független eseményeket vizsgálunk, azaz ezek együttes valószínűségét az egyes valószínűségek szorzataként lehet kiszámolni. Könnyű látni, hogy

és

Kihasználva ezt, azonnal kapjuk a következőt

Másrészt tekintsünk egy olyan folyamatot, amely a intervallumban darab pontot választ ki egymástól függetlenül, mégpedig mindegyiket az intervallumon egyenletes eloszlás szerint. Könnyen belátható, hogy

ahol a tényező amiatt jelenik meg, mert nem különböztetjük meg a pont permutációit. Észrevehetjük, hogy az előző összefüggésekben megadott két feltételes valószínűség megegyezik, és ennek alapján arra gondolhatunk, hogy ha a Poisson-folyamatban idő alatt beérkezés történik, akkor a beérkezések eloszlása ugyanaz, mint darab ugyanazon az intervallumon egyenletes eloszlású pont eloszlása.

4.1. Példa. Mi lesz az események intenzitása?

Megoldás:

4.4. Definíció. Sztochasztikus konvergencia:

4.5. Tétel. Bizonyítsuk be, hogy sztochasztikusan konvergál -hoz!

Bizonyítás. Felhasználva a Csebisev-egyenlőtlenséget valamint, hogy

kapjuk

amiből következik, hogy

4.6. Definíció. A felújítási folyamat esetén az események intenzitásán a határértéket értjük.

A gyakorlati problémáknál sokszor szükségünk van az igények beérkezési és kiszolgálási intenzitására, amely speciális esete az alábbi bizonyítás nélkül közölt tételnek.

4.7. Tétel. Elemi felújítási-tétel:

A differenciálegyenlet származtatása

Jelentse annak valószínűségét, hogy a t-edik időpillanatig esemény történt. A Poisson-folyamat tulajdonságai alapján ekkor felírhatjuk a következő egyenletrendszert

Az első egyenlet átalakítható a következő alakba

amelyből pedig a jól ismert módszerek alapján kapjuk, hogy

A többi egyenlettel is elvégezve a hasonló átalakításokat az egyenletrendszer az alábbi formában írható fel

Előző fejezetből ismerhetjük, hogy ennek a megoldása

4.2. Egyszerűbb rendszerek vizsgálata

A következő részben több viszonylag egyszerű rendszer működését modellezzük, mert ezek megértése után rátérhetünk majd a bonyolultabbak analízisére.

4.2. Példa. Tekintsünk egy gépet, amelynek 2 állapota van (0 ha működik, 1 ha a gép rossz) és a 0-dik időpillanatban a 0 állapotban tartózkodik! Mi a valószínűsége annak, hogy a t-edik időpillanatban az 1 állapotban lesz feltéve, hogy a működési idők paraméterű exponenciális míg a javítási idők paraméterű exponenciális eloszlású, egymástól független valószínűségi változók?

Megoldás: Legyenek -k a működési idők, amelyek független paraméterű exponenciális eloszlású valószínűségű változók, és -k a javítási idők amelyek független, paraméterű exponenciális eloszlású valószínűségű változók, valamint tegyük fel továbbá, hogy -k és -k is függetlenek egymástól!

Az egyszerűbb matematikai leírás végett vezessük be a következő jelöléseket!

Legyen

valamint

ezen állapotok eloszlása.

Ekkor a teljes valószínűség tétele alapján kihasználva az exponenciális eloszlás emlékezet nélküliségét az alábbi egyenletrendszert írhatjuk fel

Könnyű látni, hogy átalakítással és behelyettesítéssel kapjuk

Innen

Tehát a megoldandó egyenletünk

amely egy elsőrendű, inhomogén, konstans együtthatós, lineáris differenciálegyenlet és amelynek megoldását például a Laplace-transzformáltak segítségével határozhatjuk meg.

A számolás során felhasználjuk a Laplace-transzformáltaknál tanultakat nevezetesen, hogy

valamint, hogy a konstans c függvény Laplace-transzformáltja .

Ezek után kapjuk, hogy

Innen a parciális törtekre bontás módszerét alkalmazva haladunk tovább, nevezetesen

vagyis

ahonnan

Így

Felhasználva, hogy

kapjuk a megoldást, amely

Ha a kezdeti feltétel , akkor szimmetria okokból a megoldás

Egyensúlyi (stacionárius) eloszlás

Legyen . A megfelelő egyenleteknél határértéket véve könnyen láthatjuk, hogy

  • kezdeti feltétel esetén a megoldás

  • kezdeti feltétel esetén a megoldás pedig

Vegyük észre, hogy a rendszerünk egyensúlyi állapotban elveszti a kezdeti állapottól való függését!

4.3. Példa. Határozzuk meg a -t a stacionárius állapotegyenletek segítségével!

Megoldás: Stacionárius állapotban az időtől való függés eltűnik, így a baloldali deriváltak nullák lesznek. Ezek után egyszerű átrendezéssel és a normalizáló feltétel kihasználásával kapjuk a kívánt értékekett, vagyis

4.4. Példa. Határozzuk meg a -t az átlagok segítségével!

Megoldás: Az idő folyamán az állapotok váltják egymást és a működési idők + a javítási idők úgynevezett ciklusokat alkotnak, amelyek ráadásul még függetlenek is egymástól. Nem csak exponenciális eloszlás, hanem általános eloszlás esetén is igaz, hogy a stacionárius valószínűségeket úgy kaphatjuk meg, hogy megnézzük az átlagos ciklushossz hányad részét adja az érintett állapotban való átlagos tartózkodási idő.

Esetünkben

A megbízhatóság-elméletben nagyon fontos szerepet játszanak a rendszer első meghibásodásáig eltelt idők. Ezek eloszlása nyilvánvalóan függ attól, hogy milyen kezdeti állapotból indulunk ki. Az alábbi példa ezt a probléma kört érinti.

4.5. Példa. Tegyük fel, hogy van egy két, paraméterű exponenciális működési időközökkel rendelkező gépből álló rendszerünk és egy paraméterű javítási idővel rendelkező szerelőnk. Tegyük fel még azt, hogyha mindkét gép elromlik akkor a rendszer végérvényesen leáll és nincs több szerelés. Jelentse , hogy hány gép rossz és a rendszer induljon a 0 állapotból. Legyenek a működési és javítási idők függetlenek. Határozzuk meg az első meghibásodásig eltelt átlagos időt!

Megoldás: Mint ahogyan az előző példánál is tettük jelentse azt az állapotot, hogy hány gép rossz, . Mivel a -es állapotnál a rendszer meghibásodik, ezért onnan nincs visszatérés. Az exponenciális eloszlás tulajdonságai miatt, könnyű látni, hogy az állapotok közötti átmenetek intenzitását az alábbi ábrával szemléltethetjük

4.1. ábra - A példa állapot átmenetei

A példa állapot átmenetei

A már jól ismert módon az állapotegyenletekre az alábbi differenciálegyenlet-rendszert kapjuk

kezdeti feltétel mellett.

Elég és meghatározása mivel

A Laplace-transzformáltat véve mindkét oldalon, majd a megfelelő átalakításokat elvégezve kapjuk

Így

Hibamentes működési idő eloszlása

Jelölje a rendszer hibamentes működési idejét.

Könnyű látni, hogy

A jól ismert képlet alapján ezért

mivel

Tehát

-nál nincs javítás és ekkor a képletünk egyszerűsödik, vagyis

mint ahogyan ezt a párhuzamosan kapcsolt elemekből álló nem javítható rendszernél láttuk.

Természetesen magát a sűrűségfüggvényt is meghatározhatjuk, ha többet szeretnénk megtudni és nem csak az átlagra vagyunk kíváncsiak. Ezt megtehetjük az alábbi módon.

meghatározása

Ha az -t akarjuk kiszámítani, akkor nyilvánvalóan . Ezért a Laplace-transzformált tulajdonságai alapján a következő összefüggéseket írhatjuk fel

Vagy másképpen

vagyis

ahol

Így

Ezért

4.6. Példa. Módosítsuk az előző peldadatot annyiban, hogy a rendszer most az 1-es állapotból induljon! Határozzuk meg ebben az esetben is a hibamentes működés idő várható értékét!

Megoldás: Az előző példához viszonyítva csak a kezdeti feltétel változott meg, vagyis most azt az egyenletrendszert kell megoldani, csak kiinduló értékkel. Vagyis

Ezek után hasonló gondolatmenetet követve, mint az előbb

Így

Ebből az átlag

Speciálisan a nem javítható rendszernél esetben ami nyilvánvaló és a jó számítást bizonyítja.

Legyen az i-edik állapotból való indulás esetén az első meghibásodás átlagos ideje. Ekkor az előző eredmények alapján

Látható, hogy , hiszen

4.7. Példa. Mi annak a valószínűsége, hogy egyensúlyi állapotban független elemből álló rendszernél darab működik?

Megoldás: A megoldás kulcsa a eloszlás, hiszen egyensúlyi állapotban a működés valószínűsége és elemből darabnak kell jónak lennie, vagyis

A párhuzamos rendszer átlagos működési idejének a meghatározása

Jelöljük -val a rendelkezésre állás (készenléti tényezőt), ami annak a valószínűsége, hogy egyensúlyi állapotban a rendszer működik. Az független, párhuzamosan kapcsolt elemből álló rendszer pontosan akkor működik ha legalább egy eleme működik, tehát akkor nem működik ha mindegyik eleme hibás, amelynek a valószínűsége .

Így

Jelentse a hibás állapotban való átlagos tartózkodási időt, míg a működő állapotban való átlagos tartózkodási időt. Ekkor a rendszerre vonatkozóan

Ebből

Párhuzamosan kapcsolt rendszer esetén

Az értéket onnan kaptuk, hogy a hibás állapotban való tartózkodási idő paraméterű exponenciális eloszlású valószínűségi változó, hiszen ez éppen darab paraméterű exponenciális eloszlású javítási idő minimuma.

4.8. Példa. Vegyünk egy olyan rendszert ahol két gép és két szerelő van! Az előbbiekhez hasonlóan jelöljük 0-val azt az állapotot amikor mind a két gép jó, 1-el amikor az egyik gép jó, a másik nem, míg 2-vel amikor mind a két gép hibás. A működési idők paraméterű, míg a javítási idők paraméterű független exponenciális eloszlású valószínűségi változók. Írjuk fel a megfelelő egyenleteket!

Megoldás: Érthető módon az átmenetek intenzitását az alábbi ábra mutatja, melyből az egyenletek és a kezdeti feltétel a szokásos módon könnyen felírhatók. Nevezetesen

4.2. ábra - 2 gép, 2 szerelő

2 gép, 2 szerelő

4.9. Példa. Változtassuk meg az előző példát annyival, hogy nem 2 hanem 1 szerelő van! Határozzuk meg egyensúlyi valószínűségeket, a rendszer hibamentes működési idejének átlagát valamint azt, hogy a szerelő átlagosan mennyi ideig lesz foglalt!

Megoldás: Értelemszerűen módosítjuk az átmenetintenzitásokat, melyet az alábbi ábra mutat, majd ezt követően írhatjuk fel a kívánt egyensúlyi egyenleteket és a normalizáló feltételt. Nevezetesen

4.3. ábra - 2 gép, 1 szerelő

2 gép, 1 szerelő

Rövid számolással kapjuk, hogy

A második kérdés megválaszolásánál használjuk fel, hogy

Mivel a rendszer addig lesz a 2 állapotban amíg onnan valamelyik ki nem lép így , hiszen a javítási idő paraméterű exponenciális. A készenléti tényező pedig ebben az esetben .

A harmadik kérdés megválaszolásához vezessük be a következő jelölést: az átlagos tétlenségi idő, míg az átlagos foglaltsági idő. Ekkor

ahonnan kapjuk, hogy

Jelen esetben , gép esetén .

4.10. Példa. Hasonlítsuk össze 1 és 2 szerelő esetén az átlagos működési időket a rendszerre vonatkozóan! Jelölje 1 szerelő esetén, 2 szerelő esetén az átlagos működési időt.

Megoldás: Két szerelő esetén

Az előzőekben megmutattuk, hogy ha a rendszer a 0 állapotból indul akkor az első meghibásodás átlagos ideje

Könnyű látni, hogy

Egy szerelő esetén

Tehát

Mint látható ebben az esetben nem lehet különbséget tenni, hogy az a jó ha 1 vagy ha 2 szerelő van.

4.11. Példa. Vegyünk egy heterogén 2 szerelős rendszert ahol az i-edik elem és intenzitásokkal jellemezhető, azaz a működési idők paraméterű, a javítási idők paraméterű, független exponenciális eloszlású valószínűségi változók, i=1,2.

Határozzuk meg az időtől függő eloszlást, ha kezdetben mindkét gép működött! Mi lesz stacionárius esetben az átlagos működési ideje a párhuzamosan kapcsolt rendszernek?

Mi lesz az átlagos működési ideje ha nincs javítás?

Megoldás: A rendszer működésének a leírására az eddigiekhez hasonlóan be kell vezetni néhány jelölést, ügyelve, hogy heterogén gépekkel van dolgunk! Éppen ezért jelölje azt az állapot amikor mindkét gép jó, amikor az -es indexű hibás, amikor a -es indexű rossz, és végül amikor mindkettő rossz. Látható, hogy ekkor az állapotok átmenetének intenzitása kicsit bonyolultabb, mint ahogyan az alábbi ábra mutatja.

Menjünk tovább. Legyen most egy ábra:

4.4. ábra - A példa állapot átmenet diagramja

A példa állapot átmenet diagramja

A szokásos módon az időtől függő eloszlásra az alábbi differenciálegyenlet-rendszert írhatjuk fel

Időtől függő eloszlás

Ennek megoldása pedig

A további rendszerjellemzők pedig

Stacionárius eset

Jelentse Mint korábbról tudjuk

Ezt felhasználva kapjuk, hogy

Ezek után az átlagos működési idő

4.12. Példa. Vegyünk egy heterogén elemekből álló szerelős rendszert ahol az i-edik elem és intenzitásokkal jellemezhető, azaz a működési idők paraméterű, a javítási idők paraméterű, független, exponenciális eloszlású valószínűségi változók, i=1,2.

Határozzuk meg különböző kiszolgálási elvek mellett a rendszer egyensúlyi jellemzőit!

Párhuzamos kapcsolást feltételezve számítsuk ki a rendszer első meghibásodásának a várható idejét, ha kezdetben mindkét gép működött!

FIFO kiszolgálási elv

Először vezessük be az alábbi állapotokat, amelyek azt jelölik, hogy melyik gép és milyen sorrendben hibásodott meg! A rendszer értelemszerűen a javító egységet jelenti.

  • - nincs gép a rendszerben

  • -es gép van a rendszerben

  • -es gép van a rendszerben

  • - mindkét igény a rendszerben van, de az 1-es érkezett korábban

  • - mindkét igény a rendszerben van, de a 2-es érkezett korábban

Az állapotok átmenetintenzitását az alábbi ábra mutatja.

4.5. ábra - FIFO kiszolgálási elv

FIFO kiszolgálási elv

Egyensúlyi állapotban az egyenletek és a normalizáló feltétel

Megoldásuk

Az előző példa jelölését megtartva, a rendszerben tartózkodó igények számának eloszlása

A rendszerjellemzők

Processor-sharing kiszolgálási elv

Ezen kiszolgálási elvnél, ha több igény van a rendszerben a kiszolgálási intenzitás egyenletesen oszlik meg az igények között, vagyis igény esetén feleződik. Az állapotok lényegében ugyanazok maradnak, kivéve, hogy most nem számít melyen sorrendben jöttek be az igények.

Az állapotok átmenetintenzitását az alábbi ábra mutatja

4.6. ábra - Processor-sharing kiszolgálási elv

Processor-sharing kiszolgálási elv

Könnyű látni, hogy egyensúlyi állapotban az egyenletek és a normalizáló feltétel

Ennek megoldása

Rendszerjellemzők

Abszolút prioritásos kiszolgálási elv

Ezen elv mellett ha mindkét gép hibás, akkor az -es indexűt javítja a szerelő, mert az a fontosabb. Hiába szolgálta ki a -es indexűt, ha a fontosabb igény beérkezik, akkor az éppen folyamatban levő kiszolgálása megszakad és a fontosabbat szolgálják ki. Az állapotok ugyanazok maradnak, de az átmenetintenzitások értelemszerűen változnak, mint ahogyan a következő ábrán láthatjuk.

4.7. ábra - Abszolút prioritásos kiszolgálási elv

Abszolút prioritásos kiszolgálási elv

Könnyű látni, hogy egyensúlyi állapotban az egyenletek és a normalizáló feltétel

valamint a hibás gépek számának eloszlása

Megoldás

A rendszerjellemzők

Egyszerű behelyettesítéssel látható, hogy homogén esetben mindhárom kiszolgálási elvnél a hibás gépek számának eloszlása ugyanaz lesz, nevezetesen

mint ahogyan a korábbi példáknál is láttuk.

A rendszer első meghibásodásának az átlagát a Laplace-transzformált kiszámítása nélkül, a teljes várható érték és az exponenciális eloszlás tulajdonságainak a felhasználásával határozhatjuk meg. Ehhez szükségünk van a következő jelölésekre.

Jelölje a rendszer első meghibásodásának az átlagát ha az állapotból indulunk ki, . Ekkor felírhatjuk az alábbi egyenleteket

Ebből a megoldás

Megoldás:

Speciálisan a esetben, vagyis amikor nincs javítás a 2.3. Példa eredményeit kapjuk vissza, azaz

5. fejezet - Folytonos idejű Markov-láncok

A rendszerek időbeli változását különböző eszközökkel adhatjuk meg, erre szolgálnak pl. a differenciálegyenletek. Ha azonban még a véletlenszerűséget is bevesszük, akkor bonyolultabb módszereket kell alkalmazni. Ebben a részben nem célunk a precíz matematikai tárgyalásmód, ezt nehezen is tudnánk megtenni hiszen ennek a témának nagyon szerteágazó területei vannak és a jegyzet célja nem a véletlen folyamatok ismertetése. A Markov-folyamatok legegyszerűbb osztályát vezetjük be, melyekre később a sorbanállási rendszerek vizsgálatánál szükségünk lesz. Bőséges nyomtatott és digitális irodalom áll az olvasó rendelkezésére, említésképpen felsorolunk néhányat: Allen [2], Gnyedenko, Beljajev, Szolovjev [24], Kleinrock [41], Ovcharov [51], Sztrik [67], Trivedi [78] Tijms [75]. Jelen fejezetben a gyakorlat szempontjából egyik legfontosabb sztochasztikus-folyamattal foglalkozunk, vagyis amikor minden időpillanathoz egy értékeket felvevő valószínűségi változót rendelünk. Hogy megmutassuk milyen kapcsolat van az egyes időpillanatban felvett értékek között, a jövő és a múlt viszonyát írjuk fel matematikai formában. Az egyik legegyszerűbb kapcsolat, amit leegyszerűsítve úgy mondunk, hogy a jövő a múlttól csak a jelenen keresztül függ, az alábbi tulajdonság.

5.1. Definíció. (Markov-tulajdonság) Ha fennáll minden n-re és a változók összes lehetséges értékére, hogy

akkor az folyamatot Markov-láncnak nevezzük.

Jelöljük a valószínűséget -vel, míg időben homogén esetben -val. A formula azt jelenti, hogy idő alatt az állapotból a állapotba megy át a folyamat.

Nyilván

Hogy az állapotvalószínűségek időbeli változását felírjuk szükségünk van az átmenetvalószínűségek ismeretére, hiszen a teljes valószínűség tételét szeretnénk használni. Ezért vezetjük be a következő definíciót

5.2. Definíció. (Intenzitás-mátrix) Jelöljük Q-val a a folyamathoz tartozó intenzitás-mátrixot, melynek elemei és őket az alábbi módon értelmezzük

Vagyis az átmenetvalószínűségek

Ezek után az állapotegyenleteket akarjuk felírni, melyhez szükségünk lesz a már jól megszokott jelölésre, azaz, legyen

Ekkor az állapotegyenleteink a következők

Ezek átírhatóak az alábbi formákba

Ebből határértéket véve a keresett differenciálegyenlet-rendszer

Egyensúlyi (stacionárius) eloszlás

Mint már biztosan észrevettük az előző viszonylag egyszerű példák min speciális esetei ennek az általános egyenletrendszernek. Láttuk, hogy időtől függő megoldásuk eléggé bonyolult és sokszor zárt alakban nem is adható meg, de numerikusan esetleg meghatározhatjuk őket. Hogy jól használható formulákat kapjunk lemondunk az időtől való függésről és csak a határeloszlásra felírt egyenletek érdekelnek bennünket.

Nevezetesen a határátmenet végrehajtása után a stacionárius esetben az állapotegyenletek a következők

A modellezésnél bevezetett folyamatokról el kell döntenünk, hogy melyik osztályba tartoznak, mert azután a rájuk vonatkozó tételeket tudjuk alkalmazni. Mivel a Markov-láncok elmélete a legjobban kidolgozott, a gyakorlat szempontjából legérthetőbben tudjuk kezelni problémáinkat, nagyon hasznos az alábbi, bizonyítás nélkül közölt tétel.

5.3. Tétel. Az akkor és csak akkor folytonos idejű Markov-lánc, ha bármely állapotban a tartózkodási ideje paraméterű exponenciális eloszlású valószínűségi változó.

5.1. Születési-halálozási folyamatok

További egyszerűsítést jelent, ha a folyamat csak szomszédos állapotokba mehet. Ezt az esetet írják le az alábbi speciális intenzitások

Ekkor a -ket születési, míg -ket halálozási intenzitásoknak nevezzük. Ekkor az egyenletek is egyszerűsödnek, nevezetesen

Ezekből egyensúlyi helyzetben az alábbit nyerjük

Ezen egyenletrendszer megoldásához vegyük észre, hogy minden -re igaz a

összefüggés hiszen könnyen látható, hogy

Ezen tulajdonság felhasználásával rögtön kapjuk, hogy

így

amely nagy szerepet játszik majd különböző sorbanállási rendszerek modellezésében.

Végtelen számosságú állapottér esetén a normalizáló feltételt biztosító összegzés nem biztos, hogy konvergens sort ad, ezért annak konvergenciáját biztosítanunk kell, és ezután a megoldás egyértelmű lesz.

Erre nézzük meg az alábbi egyszerű példát!

Legyen és .

Ekkor

ami pontosan akkor konvergál ha .

Tiszta születési-folyamat

Ha és , akkor tiszta születési-folyamatról beszélünk és akkor a már jól ismert Poisson-folyamatra vonatkozó differenciálegyenlet-rendszert kapjuk

II. rész - Feladatgyűjtemény

6. fejezet - Valószínűségszámítási alapok

6.1. Diszkrét eloszlások

Mutassuk meg, hogy ha akkor , valamint !

Megoldás:

Mutassuk meg, hogy ha , akkor , valamint !

Megoldás:

Mutassuk meg, hogy ha , akkor , valamint !

Megoldás:

A levezetésnél felhasználtuk, hogy abszolút konvergens sor esetén a deriválás és az összegzés sorrendje felcserélhető.

Így

Nézzük meg hogyan számolhatók ki ezek a mennyiségek egy kicsit egyszerűbben kihasználva a geometriai eloszlás tulajdonságait!

Ebből . Hasonlóan

Így

Ebből

Határozzuk meg a p paraméterű módosított geometriai eloszlás várható értéket és szórásnégyzetét!

Megoldás: Mint tudjuk és , ahol amiből következik, hogy

Mutassuk meg, hogy a geometriai eloszlásra teljesül a

úgynevezett örökifjú tulajdonság!

Megoldás:

Legyen , és egymástól függetlenek. Határozzuk meg a -t!

Megoldás:

Mivel és függetlenek és és összegre szintén binomiális az egyenlőség az alábbi alakot ölti

vagyis hipergeometriai eloszlást kapunk.

Legyen és függetlenek! Mivel egyenlő ?

Megoldás:

Egy forgalmas áruházba paraméterű Poisson-eloszlás szerint érkeznek vásárlók, majd azok valószínűségekkel választják az -edik pénztárat . Határozzuk meg, hogy az -edik pénztárnál a vásárlók száma milyen eloszlást követ!

Megoldás: Végezzünk el kísérletet -szer és jelentse az -edik kimenetel (amelynek valószínűsége ) bekövetkezéseinek a számát. Ekkor együttes eloszlása és paraméterű polinomiális eloszlás, ezért

Mivel .

Amiből következik, hogy , és függetlenek.

6.2. Folytonos eloszlások

Legyen

az úgynevezett teljes Gamma-függvény ( függvény ). Mutassuk meg, hogy

Megoldás: A bizonyításhoz parciális integrálást fogunk használni, így

mivel az első tag értéke 0, amit a szokásos L'Hospital-szabály alkalmazásával láthatunk be.

Könnyű látni, hogy , és ezért vagyis -t a faktoriális függvény általánosításának is tekinthetjük.

Mutassuk meg, hogy

Megoldás:

A helyettesítést bevezetve így

Határozzuk meg az paraméterű -eloszlás várható értékét, szórásnégyzetét és -dik momentumát!

Megoldás:

ahol

Az helyettesítést bevezetve

mivel .

Hasonlóan

Ebből

Vagyis a szóródási együttható négyzete , ami lehet -nél nagyobb és kisebb is.

Ezek után

Speciálisan esetben az paraméterű Erlang-eloszlást kapjuk és ekkor

Ebből -nél az exponenciális eloszlást nyerjük, amelyre

Határozzuk meg az paraméterű Pareto-eloszlás várható értékét és szórásnégyzetét!

Megoldás:

Így

Legyen , és , ahol . Határozzuk meg eloszlásfüggvényét!

Megoldás:

vagyis paraméterű Pareto-eloszlást kapunk.

7. fejezet - A sztochasztikus modellezés alapjai

7.1. Az exponenciális eloszlás és a belőle származtatott eloszlások

Mutassuk meg, hogy az exponenciális eloszlásra teljesül a

úgynevezett örökifjú tulajdonság!

Megoldás:

Határozzuk meg a paraméterű exponenciális eloszlás -dik momentumát!

Megoldás:

A L'Hospital-szabály alkalmazásával látható, hogy az első tag értéke és így

Ebből a rekurziót figyelve

következik.

-ban két független exponenciális eloszlású ideig tartó tevékenység kezdődik. Az egyik ideig tart, ahol paraméterű exponenciális eloszlású, a második ideig, ahol paraméterű exponenciális eloszlású valószínűségi változó. Legyen , , .

Ezek után határozzuk meg

1. az első (azaz a rövidebb ideig tartó) tevékenység idejének az eloszlását és várható értékét ( eloszlását és várható értékét)

2. annak a valószínűségét, hogy az esemény fejeződik be előbb ()

3. az első és a második esemény befejezése közti idő eloszlását és várható értékét( eloszlását, várható értékét)

4. annak a valószínűségét, hogy egy tetszőleges időpillanatban

4.1 az esemény már befejeződött és az esemény még nem ()

4.2 az első esemény már befejeződött és a második még nem ()

4.3 mindkét esemény befejeződött ()

5. az a) és c) pontokban kapott valószínűségi változók összegének () eloszlását

6. X eloszlását, ha tudjuk, hogy ()

7. X eloszlását, ha tudjuk, hogy ()

8. X eloszlását, ha tudjuk, hogy ()!

Megoldás:

1. a rövidebb ideig tartó tevékenység befejezésének idejére

azaz, V paraméterű exponenciális eloszlású,

2. az esemény fejeződik be előbb

3. az első és második esemény befejezése közti idő

az feltétel mellett az hátralévő időtartama lesz, ami viszont az exponenciális eloszlás örökifjú tulajdonsága miatt

4. az esemény már befejeződött az még nem

az első esemény már befejeződött a második még nem

mindkét esemény befejeződött már

5. a és a valószínűségi változók összegének eloszlása

Mivel összefüggő valószínűségi változókról van szó nem lehet konvolúciót alkalmazni, hanem egyszerűen

6. X eloszlása, ha

7. X eloszlása ha

azaz paraméterű exponenciális eloszlás

8. X eloszlása ha

Mi a valószínűsége, hogy , ha , függetlenek?

Megoldás: A teljes valószínűség tétele alapján

Határozzuk meg a sorbakapcsolt rendszer várható élettartamát, ha a független elemek élettartama exponenciális eloszlást követ!

Megoldás: Sorbakapcsolt rendszer esetén ez éppen

Párhuzamosan kapcsolt rendszer esetén mi a rendszer élettartamának várható értéke és szórásnégyzete, ha homogének az elemek , és függetlenek?

Megoldás:

Használjuk fel, hogy ha akkor

A helyettesítést alkalmazva kapjuk, hogy

A exponenciális eloszlás örökifjú tulajdonságából következik, hogy a meghibásodások közötti időtartamok is exponenciális eloszlásúak lesznek. Könnyen látható, hogy a -dik és -dik meghibásodás közötti idő paramétere , , és ezek az időtartamok egymástól függetlenek is az exponenciális eloszlás tulajdonságai miatt. Ezt a tényt nagyon jól tudjuk hasznosítani a -dik meghibásodás várható értékének és szórásnégyzetének a meghatározásához.

Ezek után érthető módon

Ebből a párhuzamosan kapcsolt rendszer élettartamának szórásnégyzete

Legyenek , , független valószínűségi változók.

Mutassuk meg, hogy

Megoldás:

miatt

így

melyből következik az állítás.

Hasonlóan

így

melyből következik az állítás.

Bizonyítsuk be, hogy az paraméterű Erlang-eloszlásnak az eloszlásfüggvénye

Megoldás:

Parciális integrálást alkalmazva, ahol kapjuk, hogy

Következményként láthatjuk, hogy

Legyen és függetlenek. Határozzuk meg a konvolúciójukat!

Megoldás:

Határozzuk meg az előző példában meghatározott eloszlás várható értékét!

Megoldás:

amit az összefüggésből is megkaphattunk volna, de ezzel a sűrűségfüggvény helyességét ellenőriztük.

A 2-fázisú hipo-exponenciális eloszlás sűrűségfüggvényéből származtassuk a paraméterű Erlang-eloszlás sűrűségfüggvényét!

Megoldás: Mint láttuk

Ebből határértékkel nyerjük a kívánt sűrűségfüggvényt.

ezért alkalmazzuk a L'Hospital-szabályt! Ekkor -et kapunk, ami éppen a kívánt eredmény.

Határozzuk meg a 2-fázisú hipo-exponenciális eloszlás eloszlásfüggvényét!

Megoldás:

Ebből határátmenettel a L'Hospital-szabály alkalmazásával

-et kapunk, ami éppen a paraméterű Erlang-eloszlás eloszlásfüggvénye.

Legyenek , független valószínűségi változók. Határozzuk meg az feltételes sűrűségfüggvényt!

Megoldás:

Ha , akkor L'Hospital-szabállyal helyettesítéssel

vagyis egyenletes eloszlást kapunk.

Ha eleve a feltételből indulunk, akkor

mivel paraméterű Erlang-eloszlást követ.

Mi az paraméterű Erlang-eloszlás szóródási együtthatója?

Megoldás:

Mutassuk meg, hogy a hiper-exponenciális eloszlás sűrűségfüggvénye valóban sűrűségfüggvény!

Megoldás: A nemnegativitás egyből látható, valamint

Mutassuk meg, hogy a hiper-exponenciális eloszlás szóródási együtthatója mindig legalább 1!

Megoldás: Ehhez azt kell belátnunk, hogy

ami éppen a Cauchy-Bunyakovszkij-Schwartz-egyenlőtlenség

értékekkel.

Legyenek , , független valószínűségi változók.

Mutassuk meg, hogy

Megoldás: Jól ismert, hogy

amely az állításunkat igazolja.

Az speciális esetben az exponenciális eloszlásra kapott összefüggéseket kapjuk.

7.2. Megbízhatóság-elméleti alapok

Határozzuk meg a hiper-exponenciális eloszlás meghibásodási intenzitás-függvényét!

Megoldás:

amely monoton csökkenő és értékkészlete a intervallum.

Ezt a következőképpen láthatjuk be. Megmutatjuk, hogy a intervallumon így monoton csökkenő lesz. Mivel előjelével foglalkozunk elegendő csak a számlálót vizsgálni, mivel a nevező a deriválási szabály miatt pozitív lesz.

A számláló értéke

Alkalmazzuk a jól ismert

egyenlőtlenséget

helyettesítéssel, melyből adódik, hogy . Látható, hogy legnagyobb értékét a 0-nál veszi fel, így . Azt is észrevehetjük, hogy .

Határozzuk meg a 2 fázisú hipo-exponenciális eloszlás meghibásodási intenzitás-függvényét!

Megoldás:

amely monoton növekvő és értékkészlete a intervallumon.

Az előző feladathoz hasonlóan előjelét

határozza meg, így monoton növekedő, .

Ha , akkor . Hasonlóan ha , akkor .

Határozzuk meg az paraméterű Erlang-eloszlás meghibásodási intenzitás-függvényét!

Megoldás: Az előzőekhez hasonlóan elegendő csak a derivált számlálójával foglalkozni.

Vagyis számlálója

Ennek előjele a második tényezőtől függ. Legyen ez

Ha , akkor

Egyszerű helyettesítéssel látható, hogy

Tegyük fel, hogy . Teljes indukcióval bizonyítjuk, hogy .

mivel az indukció szerint .

7.3. Véletlen tagszámú összegek

Mi lesz az paraméterű Erlang-eloszlások paraméterű geometriai eloszlások vett keverékének eloszlása?

Megoldás:

Mi lesz az eloszlása binomiálisok Poisson súlyokkal vett keverékének ( ) ?

Megoldás:

Legyenek és és függetlenek.

Határozzuk meg a véletlen tagszámú összeg sűrűségfüggvényét!

Megoldás: A teljes valószínűség tétele szerint

Legyenek p paraméterű Bernoulli, míg függetlenek.

Határozzuk meg eloszlását!

Megoldás:

8. fejezet - Analitikus eszközök

8.1. Generátorfüggvény

Határozzuk meg a paraméterű binomiális eloszlás generátorfüggvényét és ennek segítségével a várható értéket és szórást valamint magát az eloszlást!

Megoldás:

Határozzuk meg a p paraméterű geometriai eloszlás generátorfüggvényét,valamint, hogy milyen s értékekre lesz konvergens a sor és ennek segítségével a várható értéket és szórást!

Megoldás:

Határozzuk meg, hogy mely eloszlás generátorfüggvénye a

Megoldás:

Így

amiből következik, hogy a paraméterű Poisson-eloszlás generátorfüggvénye.

Határozzuk meg generátorfüggvény segítségével a véletlen tagszámú összeg várható értékét és szórásnégyzetét!

Megoldás: Mint tudjuk a véletlen tagszámú összeg generátorfüggvénye

Így

Továbbá

így

Ezért

8.2. Laplace-transzformált

Határozzuk meg Laplace-transzformált segítségével a véletlen tagszámú összeg várható értékét és szórását!

Megoldás:

Ebből

Határozzuk meg az paraméterű Erlang-eloszlás Laplace-transzformáltját, majd annak segítségével a várható értéket és a szórást!

Megoldás:

Ezért

Határozzuk meg a hiper-exponenciális eloszlás várható értékét a Laplace-transzformált segítségével!

Megoldás:

Határozzuk meg a hipo-exponenciális eloszlás Laplace-transzformáltját!

Megoldás: Felhasználva a Laplace-transzformáltnál tanult szabályokat kapjuk, hogy

Határozzuk meg a -eloszlás Laplace-transzformáltját!

Megoldás:

ahol .

Mutassuk meg, hogyha , és függetlenek, akkor

Megoldás:

ami éppen az állítást jelenti.

9. fejezet - Sztochasztikus rendszerek

9.1. Poisson-folyamat

Határozzuk meg a Poisson-folyamat korrelációs együtthatóját!

Megoldás:

Ebből a képletből a értéket nem tudjuk egyből megmondani ezért annak meghatározáshoz a következő az eljárás

Így

Ezt behelyettesítve kapjuk, hogy a kérdéses érték

Tekintsünk egy rendszert paraméterű exponenciális eloszlású beérkezési időközökkel és paraméterű exponenciális eloszlású kiszolgálási idővel. Mi a valószínűsége, hogy egy kiszolgálás alatt k igény érkezik be?

Megoldás: A teljes valószínűség tétele szerint

Ha , akkor

ami paraméterű módosított geometriai eloszlást jelent.

Határozzuk meg, hogy egy tetszőleges eloszlású kiszolgálási idő alatt várhatóan mennyi igény érkezik be a rendszerbe!

Megoldás: A megoldáshoz a generátorfüggvény és a Laplace-transzformált tulajdonságait kell felhasználnunk.

azaz

Így

Legyen most a kiszolgálási idő paraméterű Erlang, a beérkezési időközök pedig maradjanak paraméterű exponenciális eloszlású valószínűségi változók. Határozzuk meg ebben az esetben is, hogy mi a valószínűsége annak, hogy egy kiszolgálás alatt k igény érkezik!

Megoldás:

vagyis -ed rendű negatív binomiális ( Pascal ) eloszlást követ.

9.2. Esettanulmányok

Oldjuk meg a következő differenciálegyenletet

kezdeti feltétel mellett!

Megoldás: A homogén rész

A konstans variálás módszerével nyerjük az inhomogén rész egy partikuláris megoldását, vagyis

így a partikuláris megoldás

Ebből az általános megoldás

A feltételből következik, hogy így .

Ezért

Ha a kezdeti feltételt akkor a megoldás a következő

Ha

Határozzuk meg, hogy mi annak a valószínűsége, hogy független gépből a t-edik pillanatban k darab működik, feltételezve, hogy kezdetben n darab gép működött és m darab gép volt hibás!

Megoldás:

Stacionárius esetben

Hideg tartalék

Legyen adott egy főgép amelynek működési ideje paraméterű exponenciális eloszlású valószínűségi változó és meghibásodás esetén egy tartalék kezd el működni, valamint két szerelő van. A javítási idő paraméterű exponenciális eloszlású valószínűségi változó. A meghibásodások és javítások függetlenek egymástól. Határozzuk meg a rendszer egyensúlyi jellemzőit!

Megoldás: A rendszer az egyes állapotokból a következő intenzitásokkal megy át.

9.1. ábra - Hidegtartalék

Hidegtartalék

A stacionárius esetet vizsgálva vezessük be a szokásos jelöléseket ! Jelentse annak a valószínűségét, hogy i darab gép rossz.

Ekkor a jól ismert módon az alábbi egyensúlyi egyenletrendszert írhatjuk fel

Innen

A normalizáló feltételt felhasználva kapjuk, hogy

Meleg tartalék

9.2. ábra - Melegtartalék

Melegtartalék

Meleg tartalék esetén mindkét gép működik, viszont a második gép működési ideje () paraméterű exponenciális eloszlású valószínűségi változó. Határozzuk meg most is az egyensúlyi rendszerjellemzőket!

Ebből

Végül

Legyen adott egy olyan gép amelynél hiba esetén szükség van még egy detektálásra is mielőtt míg javításra kerülne. Legyen a detektálási idő paraméterű exponenciális eloszlású valószínűségi változó! Írjuk fel egyensúlyi helyzetben az állapotegyenletek, majd oldjuk meg őket!

9.3. ábra - A feladat

A feladat

Megoldás:

Innen

A normalizáló feltételt felhasználva kapjuk, hogy

Tegyük fel, hogy van egy két, paraméterű exponenciális működési időközökkel rendelkező gépből álló rendszerünk és egy paraméterű javítási idővel rendelkező szerelőnk. Tegyük fel még azt, hogy ha mindkét gép elromlik akkor a rendszer végérvényesen leáll és nincs több szerelés. Jelentse , hogy hány gép rossz és a rendszer induljon a 0 állapotból. Határozzuk meg az első meghibásodásig eltelt átlagos időt feltételezve, hogy kezdetben mindkét gép működött!

9.4. ábra - A feladat

A feladat

Megoldás: A stacionárius állapotegyenletek a következő módon származtatjuk

Így a szokásos eljárást követve

kezdeti feltételek mellett. Laplace-transzformáltat alkalmazva és felhasználva az ott tanultakat kapjuk, hogy

Innen rövid számolással nyerjük, hogy

Felhasználva, hogy , melyet a normalizáló feltétel ad kapjuk, hogy

Innen az inverziós eljárással megkaphatjuk -t ami annak a valószínűsége, hogy egyetlen gép sem üzemel a t-edik időpillanatban.

Legyen a rendszer első elromlásának az ideje!

Ekkor azt jelenti, hogy a rendszer t-edik időpillantban vagy előtte romlott el. A rendszer megbízhatósága ekkor

Ennek a Laplace-transzformáltja

A nevezőt alakra hozva, hogy később parciális törtekre bontást tudjunk alkalmazni kapjuk, hogy

Így

Innen

Az első meghibásodásig eltelt idő átlagát az alábbi módon határozhatjuk meg

kiszámítását megtehetjük anélkül is, hogy meghatároznánk a sűrűségfüggvényt, hiszen ismerjük Laplace-transzformáltját. Azaz

Abban az esetben, amikor a gépeket nem javítják, vagyis a 2 elemből álló párhuzamosan kapcsolt rendszert kapjuk, amit már korábban is vizsgáltunk. Ekkor a behelyettesítés után

és így

ami szintén azt bizonyítja, hogy először vesszük az első meghibásodás idejét, majd ehhez hozzáadjuk a megmaradt gép hátramaradt működési idejét. Az első paraméterű exponenciális, a második pedig paraméterű exponenciális eloszlású valószínűségi változó. Függetlenek egymástól, így összegük Laplace-transzformáltját kapjuk.

Tegyük fel, hogy van egy két, paraméterű exponenciális eloszlású működési időközökkel rendelkező gépből álló rendszerünk és két paraméterű exponenciális eloszlású javítási idővel rendelkező szerelőnk. Tegyük fel még azt, hogy a javítás csak akkor indul meg ha mindkét gép elromlik. Feltéve, hogy meghibásodások és javítások egymástól függetlenek, határozzuk meg a stacionáris eloszlást!

9.5. ábra - A feladat

A feladat

Megoldás: Vezessük be az alaábbi jelöléseket.

  • 0 - mindkét gép működik

  • 1 - 1 gép nem működik, nincs javítás

  • 2 - 2 gép nem működik

  • 3 - 1 gép nem működik, van javítás (2 meghibásodás utáni javítás)

A jól ismert módon egyensúlyi állapotban az egyenletek a következők lesznek

Innen egyszerűen kapjuk, hogy

Felhasználva az előzőeket és a normalizáló feltételt nyerjük, hogy

A készenléti tényező

Ezek után

III. rész - A sorbanállási elmélet alapjai

10. fejezet - A sorbanállási elmélet alapfogalmai

A sorbanállási elmélet a köznapi életben előforduló egyik kellemetlen jelenség, nevezetesen a várakozás vizsgálatával foglalkozik. Nemcsak mi, hanem számos területen előforduló igények is sorba állnak, pl. hívások a telefonközpontban, levelek és iratok a hivatalban, programok a központi egységnél, csak hogy néhányat említsünk. Nem véletlen, hogy szóbahoztuk a telefonforgalmi és számítógépes problémákat. Az elmélet történetében döntő helyet foglalnak el ezek az alkalmazási területek. A sorbanállási rendszerek tanulmányozását a telefonforgalmi problémák megoldására A. K. Erlang dán mérnök kezdte el a XX. század elején.

Munkája nemcsak a mérnökök, hanem a matematikusok figyelmét is felkeltette, és nagyon sok cikk és könyv foglalkozott a valószínűségszámítási háttérrel. A sorbanállási elmélet szinte önálló tudománnyá nőtte ki magát, melynek eredményeit és módszereit sikerrel alkalmazzák többek között a megbízhatóság-elméletben, számítástudományban, operációkutatásban. Sok kiváló matematikus szerzett hírnevet a sorbanállási elmélet területén. Ami rendkívül fontos az az, hogy egy jelenleg is dinamikusan fejlődő területről van szó, melynek művelői ma is számos dolgozatot és könyvet írnak. Erről legkönnyebben úgy győződhetünk meg, ha a Google Scholar keresőjébe a témakörhöz tartozó szót írunk be. Külön érdeklődési csoport is létrejött, amelynek tagjai rendszeresen karbantartott honlapon értesítik egymást a fontos eseményekről. Erről a forrásról számos jegyzetet, szoftvert és más hasznos anyagot lehet letölteni, lásd

Magyarországon ebben a témakörben nem sok jegyzet, könyv jelent meg. Leginkább Györfi László, Páli István [26], Jereb László, Telek Miklós [36], Kleinrock [41], Lakatos László, Szeidl László, Telek Miklós [47] és Sztrik János [64], [65], [66], [67] munkáit tudnánk felsorolni. Feltétlenül meg kell azonban jegyezni, hogy a magyar matematikusok és mérnökök érdemben részt vettek az elméleti kutatásokban és számos esetben alkalmazták is az elért eredményeket. Mindenképpen meg kell említeni Takács Lajost, Tomkó Józsefet, Arató Mátyást, Györfi Lászlót, Benczúr Andrást, Lakatos Lászlót, Szeidl Lászlót, Jereb Lászlót, Telek Miklóst és Sztrik Jánost akik számos dolgozatot publikáltak neves nemzetközi folyóiratokban. Az angol és orosz nyelvű könyvek száma is tekintélyes, az irodalomjegyzékben csak a legfontosabbakat soroltuk fel és ezek mind megtalálhatók Debreceni Egyetem, Informatikai Kar könyvtárában. Bővebb összeállításért érdemes felkeresni az alábbi linket:

10.1. A sorbanállási rendszerek jellemzői

Ahhoz, hogy teljesen jellemezzünk egy sorbanállási rendszert, azonosítanunk kell azt a sztochasztikus folyamatot, amely a beérkező igényeket írja le, és meg kell adnunk a kiszolgálás szabályait és struktúráját. A beérkező folyamatot általában az egymás után beérkező igények közötti időintervallumok, mint valószínűségi változók eloszlásának segítségével jellemezhetjük. Ezt az szimbólummal jelöljük, ahol .

A sorbanállás elméletében többnyire feltesszük, hogy az egymás utáni beérkezések közötti időközök (röviden beérkezési időközök) azonos eloszlású független valószínűségi változók (ezért a beérkezési folyamat ún. felújítási folyamatot alkot). A másik sztochasztikus mennyiség, amelyet meg kell adni, a beérkező igények által a csatornával szemben támasztott követelmények (munka) nagysága; ezt kiszolgálási időnek nevezzük és valószínűségeloszlását -szel jelöljük, azaz .

A kiszolgálás ideje annak az időintervallumnak a hosszát jelenti, amelyet az igény a kiszolgáló egységben eltölt.

A kiszolgálás szabályára és struktúrájára vonatkozóan további mennyiségeket kell meghatározni. Ilyen jellemző a rendelkezésre álló kiszolgáló egységek (csatornák, kiszolgálók, szerverek, stb.) száma, valamint a befogadóképesség, ami nem más, mint a kiszolgálóegységben és a várakozási sorban tartózkodó igények maximális száma, amit gyakran végtelennek tekintünk. A kiszolgálási sorrend írja le azt a szabályt, amely szerint a várakozók közül sorra kerülnek az egyes igények kiszolgálás céljából. A leggyakrabban használt kiszolgálási elvek: FIFO (First In, First Out) érkezési sorrendben; LIFO (Last In, First Out) fordított sorrendben történő kiszolgálások. Ha a beérkező igényeket bizonyos csoportokba tartozás szerint meg lehet különböztetni, akkor a csoportok között prioritást lehet megállapítani, és ezen a prioritáson alapul a kiszolgálás sorrendje. Ez az egyik legalkalmasabb ütemezési elv, mivel így az igények közötti fontossági sorrendet felállítva történik a kiszolgálás.

A prioritásos sorbanállási elvnek két fő típusa van: abszolút és relatív. Az előbbi azt jelenti, hogy ha egy igény kiszolgálása folyamatban van, és érkezik egy magasabb prioritású igény, akkor a kiszolgálás megszakad, és újra beáll a várakozási sorba. He legközelebb rákerül a kiszolgálás, akkor az kezdődhet az elejétől vagy a megszakítás helyétől. A relatív prioritásos esetben a fontosabb igény beérkezésekor a kiszolgálás nem szakad meg, hanem folytatódik, majd a befejezéskor a legfontosabb várakozó igény kiszolgálása kezdődik.

A sorbanállási rendszerek hatékonyságának és teljesítményének vizsgálatához a következő rendszerjellemzőket igyekszünk meghatározni: az igények várakozási ideje; a rendszerben levő igények száma; a foglaltsági intervallum hossza (vagyis az a folytonos időintervallum, amelyben a kiszolgáló egység állandóan foglalt); az üresjárati időszakasz hossza; a pillanatnyi munkahátralék eloszlása. Mindegyik mennyiség valószínűségi változó, és így teljes valószínűségszámítási jellemzésüket (vagyis eloszlásfüggvényüket) keressük, amit általában nehéz megadni, így sokszor megelégszünk az átlagos mennyiségekkel.

Az elemi sorbanállási elmélet egyrészt történeti okokból fontos, másrészt pedig azért, mert alkalmas arra, hogy szemléltesse a bonyolultabb sorbanállási rendszerek jellemzőit is.

Az egyszerűség kedvéért tekintsünk először egy egykiszolgálós rendszert.

A sorbanállási rendszerek teljesítményének mérésére legalkalmasabb eszköz a torlódás vizsgálata. Legyen egy dimenzió nélküli mennyiség, amelyet a következőképpen lehet definiálni:

Feltételezzünk egy végtelen populációjú modellt, jelöljük a beérkezési intenzitást -val, ami nem más, mint az átlagos beérkezési időköz reciproka, valamint az átlagos kiszolgálási időt -vel. Ekkor a következőt kapjuk:

Az -nél nagyobb forgalmi intenzitás azt mutatja, hogy az igények gyorsabban érkeznek, mint ahogy egy szerver (kiszolgálóegység, csatorna) ki tudná szolgálni őket.

Jelölje az esemény karakterisztikus függvényét, azaz

és azt az eseményt, hogy a kiszolgáló tétlen a időpillanatban. Ekkor a szerver időegységre eső kihasználtsága

ahol egy elegendően hosszú időintervallum. Ha esetén a fenti mennyiségnek létezik határértéke, akkor a szerver kihasználtságán ezt az -sel jelölt mennyiséget értjük. Továbbá valószínűséggel fennáll

ahol annak stacionárius valószínűsége, hogy a szerver tétlen, a kiszolgáló egység átlagos foglaltsági periódushosszát, pedig az átlagos tétlenségi periódushosszát jelöli.

Ez az összefüggés Markov-folyamatoknál speciális esete a következő, gyakran felhasználható relációnak, amelynek magyar nyelvű bizonyítása megtalálható Tomkó József cikkében [77].

10.1. Tétel. Legyen egy ergodikus Markov-folyamat, pedig állapotterének egy részhalmaza. Látható, hogy az idő folyamán felváltva tartózkodik -ban és -ban. Ekkor valószínűséggel

ahol és az ill. az részhalmazban való átlagos tartózkodási időt jelöli egy ciklus alkalmával, pedig az folyamat ergodikus eloszlása.

Egy párhuzamos szerverből álló rendszerben T idő alatt átlagosan igény érkezik szerverenként, feltéve, hogy a forgalom egyenletes eloszlású az kiszolgáló egység között. Ha minden beérkezett kérés kiszolgálása átlagosan ideig tart, akkor egy adott szerver teljes foglaltsági idejének várható értéke . Osszuk el ezt a mennyiséget -vel, így

Mivel a kihasználtság maximum lehet, így az szerveres rendszer kihasználtsági tényezőre vonatkozó korrekt kifejezés:

A másik gyakran használt teljesítménymérő eszköz a rendszer átbocsátóképességének vizsgálata. Ezt a mennyiséget úgy definiálhatjuk, mint az időegységként kiszolgált igények átlagos számát: szerveres rendszerben minden időegység alatt igény kiszolgálása fejeződik be, így az

Ez azt jelenti, hogy az átbocsátóképesség ekvivalens a érkezési intenzitással ha a kisebb, mint a maximális kiszolgálási sebesség (), azon túl az átbocsátóképesség beáll -re.

Az igények szempontjából a legjelentősebb teljesítménymérő eszköz az az idő, amit a várakozási sorban vagy a rendszerben töltenek. Definiáljuk a várakozási időt, mint a -dik igény várakozási sorban eltöltött idejét, és a válaszidőt, mint az igény által e rendszerben eltöltött teljes időt. Ezen jelöléseket használva a következő egyenlőséget kapjuk:

ahol a kiszolgálási időt jelöli. és is valószínűségi változó, várható értékük és alkalmas a rendszer teljesítményének mérésére.

A rendszer teljesítményének vizsgálata történhet a várakozási sor hosszának mérésével is. A valószínűségi változó jelentse a időpillanatban a sorban található igények számát, és a időpillanatban a rendszerben található igények számát. Egy rendszerben levő igény vagy a várakozási sorban van, vagy éppen kiszolgálás alatt áll, tehát szerveres rendszer esetén:

10.2. Kendall-féle jelölés-rendszer

Mielőtt rátérnénk az elemi sorbanállási rendszerek vizsgálatára, vezessük be a Kendall-tól származó jelölést, melyek segítségével könnyen osztályozhatjuk őket:

ahol

  • : a beérkezési időközök eloszlásfüggvénye,

  • : a kiszolgálási idő eloszlásfüggvénye,

  • : a kiszolgálók száma,

  • : a rendszer befogadóképessége, azaz a kiszolgálóegységben és a várakozási sorban tartózkodó igények maximális száma,

  • : az igényforrás számossága,

  • : a kiszolgálás elv szerint történik.

Ha az említett eloszlások exponenciálisak, akkor az jelölést használjuk. Továbbá, ha a befogadóképesség vagy az igényforrás számossága végtelen, és a kiszolgálás elve , akkor ezeket a jelöléseket elhagyjuk.

Így pl. az egy egykiszolgálós Poisson beérkezéssel és exponenciális kiszolgálási idővel jellemzett rendszert jelöl. Az rendszernél a beérkezések Poisson-folyamat szerint történnek, a kiszolgálási idők általános eloszlásúak, és szerver áll rendelkezésünkre. Az rendszer esetén az igények egy elemű forrásból származnak, ahol exponenciális eloszlású ideig tartózkodnak, a kiszolgálást egység végzi exponenciális eloszlású ideig és a rendszerben egyidejűleg maximum igény tartózkodhat.

10.3. Születési-halálozási folyamatokra vonatkozó összefüggések

Mivel az egyszerűbb sorbanállási rendszerek működését születési-halálozási folyamatok segítségével fogjuk modellezni, nézzünk meg néhány rájuk vonatkozó fontos összefüggést. Értelemszerűen a születéseket az igények érkezése, a kihalást az igények kiszolgálása jelenti majd.

Jól ismert, hogy a folyamat egyensúlyi eloszlása az alábbi zárt formában adható meg

Most vizsgáljuk meg egyensúlyi állapotban valamely születési-halálozási folyamat állapotát a születési és halálozási pillanatokban, mert későbbiek során erre többször is szükségünk lesz!

Jelölje a folyamat állapotát a születés ill. a halálozás pillanatában, továbbá legyen .

A Bayes-tétel felhasználásával könnyű látni, hogy

Hasonlóan

Mivel , ezért

További hasznos összefüggés, hogy egyensúlyi állapotban az átlagos születési intenzitás egyenlő az átlagos kihalási intenzitással. Ezt nagyon egyszerűen a következőképpen láthatjuk be

10.4. Sorbanállási szoftverek

A gyakorlati problémák megoldásánál először a sorbanállási rendszert kell azonosítani, majd utána megadni a rendszer jellemzőit. Természetesen a modellezés szintje erősen függ a probléma jellegétől, de általában célszerű a legegyszerűbb rendszert venni, mert ekkor kevesebb paraméter befolyásolja a minőségi mutatókat. Különböző szoftverek állnak rendelkezésünkre, melyeket használva ki tudjuk számítani a kívánt metrikákat. Ebből a célból érdemes felkeresni linket

A hatékonyabb gyakorlat-orientált oktatás céljából magyar és angol nyelven mi is elkészítettünk egy képletgyűjteményt és egy Java-applet programcsomagot, amely megtalálható az alábbi linken

A szimulációs megközelítésekhez kiegészítésképpen javasoljuk még az következő Java-appletet

Ha a rendszerek egyike sem megfelelő, akkor magunknak kell az adott problémához elkészíteni az új matematikai modellt és igazából itt kezdődik az alkotás. A jegyzet ehhez kíván segítséget nyújtani.

Az anyag összeállításában főleg Allen [2], Bose [8], Daigle [13], Gnyedenko, Kovalenko [23], Gnyedenko, Beljajev, Szolovjev [24], Gross, Harris [25], Jain [34], Jereb, Telek [36], Kleinrock [41], Kobayashi [42], [43], Kulkarni [46], Nelson [50], Stewart [63], Sztrik [67], Tijms [75], Trivedi [78] könyvekre támaszkodtunk.

11. fejezet - Végtelen-forrású rendszerek

A sorbanállási rendszerek forrásuk szerint végtelen- és véges-forrású osztályba sorolhatók, majd ezekből a rendszerekből, mint csomópontokból képezhetjük a sorbanállási hálózatokat. Matematikailag a végtelen-forrású rendszerek könnyebben kezelhetők, mert ekkor a beérkezési intenzitások általában függetlenek a rendszer állapotától. Ilyenkor a leggyakoribb feltételezés, hogy az igények beérkezése Poisson-folyamat szerint történik és a kiszolgálási elv FIFO. Ez nagymértékben egyszerűsíti a matematikai tárgyalás módot.

11.1. Az M/M/1 típusú sorbanállási rendszer

Az rendszer a legegyszerűbb nem-triviális rendszer. Emlékeztetünk rá, hogy ebben az esetben a beérkezési folyamat paraméterű Poisson-folyamat, vagyis a beérkezési időközök paraméterű exponenciális eloszlású valószínűségi változók. A kiszolgálási idők paraméterű exponenciális eloszlású valószínűségi változók. Feltesszük továbbá, hogy a beérkezési időközök, és a kiszolgálási idők egymástól független valószínűségi változók. Jelölje most a időpillanatban a rendszerben tartózkodó igények számát, és azt mondjuk, hogy a rendszer a állapotban van, ha . Mivel a fellépő valószínűségi változók exponenciális eloszlásúak, vagyis emlékezetnélküliek, az folytonos idejű Markov-lánc lesz.

Vizsgáljuk meg a rendszer állapotváltozásainak valószínűségeit egy adott időtartam alatt

Az összeg első tagja annak a valószínűsége, hogy a rendszerben egy igény érkezett, és nem szolgáltak ki egyet sem. Az összeg második tagja pedig annak a valószínűségét adja, hogy a rendszerbe 2 vagy több igény érkezett, és a beérkezettnél eggyel kevesebb került kiszolgálásra. De ez a valószínűség éppen -val egyenlő, így

Az előbbiekhez hasonlóan írható fel annak valószínűsége, hogy a rendszer állapotban volt és a időtartam után a állapotba került

Könnyen látható továbbá, hogy

Tehát egy olyan születési-halálozási folyamattal van dolgunk, amit a születési és halálozási intenzitások alábbi megválasztásával lehet jellemezni

Vagyis az összes születési intenzitás , az összes halálozási intenzitás pedig . Feltesszük, hogy végtelen hosszúságú sorok is létrejöhetnek, és az igények kiszolgálása FIFO elv alapján történik.

Helyettesítsük be az intenzitásokat a születési-halálozási folyamatoknál kapott 10.1 képletbe, így a következő adódik

vagyis

Az eredmény kézenfekvő. Az ergodikusság feltétele általánosságban (és így annak is, hogy egy stacionárius megoldást kapjunk) és ; esetünkben az első feltétel

Az sor akkor és csak akkor konvergens, ha

Az ergodicitás második feltétele esetünkben

Ez akkor teljesül, ha . Tehát az ergodikusság szükséges és elégséges feltétele az sor esetén egyszerűen . A valószínűség kiszámolásához a normalizáló feltételt használjuk és azt kapjuk, hogy

Mivel , ezért a sor konvergens, és így

A kihasználtsági tényező vagy . A stabilitás feltétele miatt a

egyenlőséget meg kell követelni, ez biztosítja, hogy legyen. Így

amely valóban valószínűségi eloszlás, nevezetesen a módosított geometriai eloszlás.

A rendszer jellemzői:

1. A rendszerben tartózkodó igények átlagos száma

A rendszerben tartózkodó igények számának szórásnégyzete

2. A várakozó igények átlagos száma (átlagos sorhossz)

A sorhossz szórásnégyzete

3. A szerver kihasználtsága

10.1 Tétel alapján látható, hogy

ahol a kiszolgáló átlagos foglaltsági periódushossza, a tétlenségi idő várható értéke. Mivel a szerver addig tétlen, amíg igény nem érkezik, az pedig exponenciális eloszlású paraméterrel. Így

melyből

Megmutatjuk, hogyan lehet másképpen meghatározni a kiszolgáló átlagos foglaltsági periódushosszát.

Ehhez szükségünk lesz az alábbi jelölésekre.

Jelölje egy átlagos foglaltsági periódushossz alatt beérkezett igények átlagos számát, egy átlagos foglaltsági periódushossz alatt távozott igények átlagos számát, valamint egy igény kiszolgálása alatt beérkezett igények átlagos számát! Nyilvánvalóan

melyekből behelyettesítés után

adódik, vagyis a formulát más módon is ellenőriztük. Ezek után

4. Egy igény tartózkodási idejének eloszlása

Megmutatjuk, hogy olyan sorbanállási rendszernél, amelybe az igények Poisson-folyamat szerint érkeznek,

ahol - mint korábban is - annak valószínűsége, hogy a pillanatban a rendszer a állapotban van, pedig annak valószínűsége, hogy egy a pillanatban érkező igény a rendszert a állapotban találja. Jelölje

azt az eseményt, hogy egy beérkezés történik a intervallumban. Ekkor

Felhasználva a feltételes valószínűség definícióját,

Poisson-folyamat esetén tudjuk, hogy (az emlékezetnélküliség miatt) az esemény nem függ a pillanatban a rendszerben tartózkodó igények számától (és magától a időtől sem), ezért

így születési és halálozási folyamatok esetére is

Azaz, annak valószínűsége, hogy egy beérkező igény a rendszert a állapotban találja, éppen azzal a valószínűséggel egyezik meg, hogy a rendszer a állapotban van.

Egyensúlyi állapotban a (10.2) összefüggést alkalmazva esetben ugyanezt az eredményt kapjuk.

Ha egy tetszőleges pillanatban egy igény érkezik, lesz annak a valószínűsége, hogy nem kell várakoznia, hisz ekkor a rendszer üres. Minden más esetben várakoznia kell. Tegyük fel, hogy az érkezés pillanatában igény tartózkodik a rendszerben. Ekkor az érkező igénynek meg kell várnia, míg a kiszolgálás alatt álló igény kiszolgálása befejeződik és az előtte álló igény is elhagyja a rendszert, majd őt is kiszolgálták.

Feltettük, hogy a kiszolgálások egymástól függetlenek és paraméterű exponenciális eloszlásúak. Köztudott, hogy az exponenciális eloszlás emlékezetnélküli, így a kiszolgálás alatt levő igény eloszlása független attól mióta folyik a kiszolgálás, ezért a várakozási idő Erlang- eloszlású és paraméterrel és a tartózkodási idő is Erlang- eloszlású, de és paraméterrel. Emlékeztetőül az és paraméterű Erlang-eloszlás sűrűségfüggvénye

Ezért a teljes valószínűség tételének felhasználásával a tartózkodási idő sűrűségfüggvénye

Az eloszlásfüggvény

Vagyis azt kaptuk, hogy a tartózkodási idő is exponenciális eloszlású paraméterrel.

Ezért a rendszerbeli tartózkodási idő várható értéke és szórásnégyzete

Továbbá, nyilvánvalóan

5. Egy igény várakozási idejének eloszlása

A gondolatmenet az előzőhöz hasonló, de most az Erlang eloszlás tagból áll.

Jelölje egy tetszőleges igény várakozási idejének sűrűségfüggvényét, . A teljes valószínűség tétele értelmében

Tehát

Így

Az átlagos várakozási idő

Az is látható, hogy miatt, ahol és függetlenek

ebből

ami éppen .

Vegyük észre, hogy

Továbbá

Az (11.1), (11.2) összefüggéseket Little-formuláknak nevezzük, melyek általánosabb esetben is igazak maradnak.

Most vizsgáljuk meg az rendszer állapotát a távozási pillanatokban, mert ki akarjuk számolni az igények távozási időközének az eloszlását. Mint ahogyan az (10.3) összefüggésnél láttuk a távozási pillanatokban az eloszlás

Poisson beérkezés esetén , ezért .

Ezek után határozzuk meg a távozási időközök Laplace-transzformáltját, mely a feltéles Laplace-transzformáltak súlyozott összege azon feltétel mellett, hogy a távozási pillanatban a kiszolgáló tétlen vagy foglalt.

Nyilvánvalóan

hiszen, ha tétlen, akkor a következő igénynek először be kell érkezni majd ezt ki kell szolgálni. Ebből

ami azt mutatja, hogy a távozási időközök ugyancsak paraméterű exponenciális eloszlású valószínűségi változók. A kiszolgálási és beérkezési időközök függetlenségéből következik a távozási időközök függetlensége is, ezért a távozási folyamat paraméterű Poisson-folyamat.

Ez azért fontos, mert ha több típusú kiszolgálási csomópont van egymás után sorbakötve (tandem sorbanállási hálózat), akkor mindegyiknél a beérkezési folyamat paraméterű Poisson-folyamat és a csomópontok független -típusú rendszerként vizsgálhatók. Ekkor beérkezési és kiszolgálási intenzitással az -edik csomóponthoz jelölést bevezetve az összes rendszerjellemzőt meg tudjuk határozni a már ismert módon. A hálózatban lévő igények száma érthető módon az egyes csomópontokban lévő igények összege és a tartózkodási és várakozási idők összege adja a hálózatra vonatkozó időket.

Most mutassuk meg, hogyan adhatjuk meg sűrűségfüggvényét a Laplace-transzformált nélkül! Ekkor is a teljes valószínűség tételét alkalmazva

Ezek után nézzük meg, hogy rendszer esetén milyen kiszolgálási idő mellett teljesül, hogy a távozási folyamat ugyancsak paraméterű Poisson-folyamat. Először lássuk be, hogy . Mint korábban is megmutattuk stacionárius rendszernél esetben is az átlagos foglaltsági periódus alatt távozó igények száma 1-el nagyobb ezen periódus alatt beérkezett igények átlagos számánál, képletekben ez azt jelenti, hogy

ahol az átlagos beérkezési időköz várható értékét jelöli. Ebből

ahol . Nyilvánvalóan

Így az rendszer kihasználtsága . esetén , ezért a kiszolgálási időre vonatkozó kérdésünk az alábbit jelenti

így

ez viszont az várható értékű exponenciális eloszlás Laplace-transzformáltja. Vagyis csak exponenciális eloszlású kiszolgálási idők esetén lesz a távozási folyamat a beérkezési folyamattal megegyező

 Java-applet a rendszerjellemzők meghatározására 

11.1. Példa. Egy postahivatalban naponta 70 személy fordul meg (a posta mindennap 10 óra hosszat van nyitva) óránként 10 személyt képesek kiszolgálni. Tételezzük fel, hogy a beérkezések megfelelnek a Poisson-folyamat jellegzetességeinek, és a kiszolgálás exponenciális eloszlású. Mekkora lesz a várakozó sor átlagos hossza, mi annak a valószínűsége, hogy sorban 2-nél több személy várakozzék? Mennyi a várható sorbanállási idő? Mennyi annak a valószínűsége, hogy a várakozás 20 percnél több időt vesz igénybe?

Megoldás: Legyen az időegység óra, akkor , ,

11.2. rendszer tétovázó (elriasztott) igények esetében

Tekintsük az rendszert azzal a módosítással, hogy az érkező igények a nagyobb sorhossz láttán egyre kisebb valószínűséggel csatlakoznak a rendszerhez, vagyis állnak sorba. Jelöljük -val a csatlakozás valószínűségét, ha az érkezés pillanatában igény van a rendszerben.

Az eddigiekhez hasonlóan könnyű belátni, hogy ismét születési-halálozási folyamattal írhatjuk le a rendszerben tartózkodó igények számát, de módosulnak a születési intenzitások, mégpedig

Nyilvánvalóan többfajta -t lehet tekinteni, de arra törekedni kell, hogy a rendszert viszonylag egyszerűen tudjuk leírni és a kiszámolt hatékonysági mutatókat is zárt alakban lehessen megadni. Ilyen okok miatt legyen

Ezért

majd a normalizáló feltétel meghatározása után

Ebből láthatjuk, hogy a rendszer stabil, ha , vagyis nem követeljük meg a feltételt!

Vegyük észre, hogy a rendszerben tartózkodó igények száma paraméterű Poisson-eloszlást követ, ezért a rendszerjellemzők is várhatóan egyszerű formában adhatók majd meg.

Ezek után a rendszerjellemzők

1.

melyből

2.

3.

Így

4. A tartózkodási és várakozási idők jellemzőinek meghatározásához ismernünk kell az érkezési pillanatban az eloszlást, pontosabban, hogy a rendszerhez csatlakozó igény igényt talál a rendszerben. Az előzőekhez hasonlóan a Bayes-formula felhasználásával könnyű látni, hogy

Vegyük észre, hogy

Először határozzuk meg -t majd utána !

A teljes várható érték tétele miatt

Mint ahogyan az (10.5) összefüggésnél már bebizonyítottuk

ezért

ami Little-formula erre a rendszerre is.

5. A és eloszlásának a meghatározása már sokkal nehezebb feladat. Az előzőekben használt módszerekhez hasonlóan

amit nem egyszerű meghatározni. Hasonló problémába ütközünk esetében is.

Azonban és már könnyebben kezelhető formában nyerhető.

Nevezetesen

Ellenőrzésképpen a -ből határozzuk meg -t!

Így

amit már előzőekben is megkaptunk. Hasonlóan számolható is.

Formálisan és a megfelelő Laplace-transzformáltak deriváltjainak segítségével megadható. Nézzük meg ezt a módot! Mint láttuk

Ebből

így

Ezért

Továbbá

és véletlen tagszámú összegként áll elő, ezért alkalmazhatjuk az ott megismert képleteket. Nevezetesen

miatt először határozzuk meg -t!

Ezért

Így

\begin{align*} \mathbb{D}^{2}(W) & =\left(\frac{1}{\mu}\right)^{2}\left(\frac{1}{1-e^{-\rho}}(\rho+e^{-\rho}-1)+\frac{\rho-e^{-\rho}(\rho^{2}+\rho)}{(1-e^{-\rho})^{2}}\right)\\ & =\frac{1}{(\mu(1-e^{-\rho}))^{2}}((\rho+e^{-\rho}-1)(1-e^{-\rho})+\rho-e^{-\rho}(\rho^{2}+\rho)).\end{align*}

Ebből

ami ugyanaz, mint amit előzőleg megkaptunk.

11.3. Prioritásos rendszer

A következőkben az rendszer egy olyan módosításával fogunk megismerkedni, ahol két különböző típusú igény van. Mindkét típusú igények független Poisson-eloszlás szerint érkeznek, egyes típusú , a kettes pedig paraméterrel. A kiszolgálási intenzitás típustól függetlenül legyen . A rendszer stabilitása miatt feltételezzük, hogy

ahol .

Tegyük fel, hogy az egyes típusú igényeknek prioritása van a kettes típusúakkal szemben. Az elkövetkezendőekben abszolút és relatív prioritási szabályok mellett határozzuk meg az egyes csoportokba tartozó igények átlagos tartózkodási idejét és várható számát.

Abszolút prioritás

Ezen szabály esetén az egyes típusú igényeknek abszolút prioritása van a kettessel szemben, ami azt jelenti, hogy ha egy kettes típusú kiszolgálás alatt áll és egy egyes típusú érkezik akkor a kettes típusú megszakításra kerül és az egyes típusú kiszolgálása következik. Ha a rendszerben nincs több egyes típusú akkor a kettes típusúak kiszolgálási kezdődik meg attól a ponttól, ahonnan megszakították.

Jelölje a renszerben tartózkodő típusú igények számát, míg az típusú igények tartózkodási idejét. A következőkben az és az mennyiségeket fogjuk meghatározni esetén.

Az egyes típusú igények számára a kettes típusúak tulajdonképpen nem léteznek, így közvetlenül kapjuk, hogy

Mivel típustól függetlenül a kiszolgálási intenzitás megegyezik, így a rendszerben tartózkodó igények száma nem függ a kiszolgálás sorrendjétől. Így ez az érték megegyezik azzal, amikor az érkezési sorrend szerint történik a kiszolgálás. Az rendszernél megismert képletek alapján ezért

majd felhasználva (11.3)-et,

és alkalmazva a Little-törvényt,

11.2. Példa. , és esetén ha érkezési sorrendben történik a kiszolgálás, akkor

míg ha az egyes típusnak prioritása vannak a kettes felett

Relatív prioritás

Ebben az esetben az egyes típusú igényeknek majdnem abszolút prioritása van, ami azt jelenti, hogy az egyes típusú igény érkezésekor a kettes típusú igény kiszolgálása nem szakad meg, de a kiszolgálás befejeződésekor az egyes típusúak kiszolgálása kezdődik. Ebből következően ennek prioritási szabálynak relatív prioritás a neve.

Az egyes típusú igények átlagos tartózkodási idejére a következő képlet írható fel

Az utolsó tag azt jelöli, hogy amikor egy érkező egyes típusú igény kettest típusút talál kiszolgálás közben, akkor mindaddig várnia kell, amíg annak kiszolgálása be nem fejeződik. A Poisson-folyamat szerinti érkezésnek köszönhetően annak a valószínűsége, hogy az egyes típusú beérkező igény kettes típusút talál megegyezik a kettes típusú igényekre vonatkozó kihasználtsággal , amely . A Little-törvényt felhasználva,

kapjuk, hogy

A kettes típus esetében (11.4)-t felhasználva, majd behelyettesítve kapjuk, hogy

és a Little-törvényt alkalmazva

11.3. Példa. Legyen , és , ekkor

 Java-applet a rendszerjellemzők meghatározására 

11.4. Az típusú, véges befogadóképességű rendszer

Tekintsük az rendszert azza a módosítással, hogy a rendszerben egyszerre maximum igény tartózkodhat. Könnyű látni, hogy a rendszerben tartózkodó igények száma ismét születési-halálozási folyamat lesz , és , intenzitásokkal. Ekkor

vagyis

Meg kell jegyezni, hogy a rendszer stabil minden -ra rögzített mellett, de ha -hez, akkor a stabilitás feltétele a reláció és értelemszerűen az rendszer eloszlása az rendszer eloszlásához konvergál.

Ez analitikusan is megmutatható, hiszen -hoz és így -hoz.

Ezek után adjuk meg a szokásos rendszerjellemzőket

1.

2.

3.

4. A tartózkodási és várakozási idő jellemzőinek meghatározásához tudni kell, hogy a rendszerbe érkező igény milyen állapotban találja a rendszert. A Bayes-formula felhasználásával az eddigiekhez hasonlóan könnyű látni, hogy

A következő részben az rendszerhez hasonlóan azt kell észrevenni, hogy a feltételes tartózkodási és várakozási idők illetve paraméterű Erlang-eloszlást követnek, ha a rendszerben igény tartózkodott az új igény rendszerbe érkezésének pillanatában.

Ennek megfelelően írjuk le a várható értéket illetve a sűrűségfüggvényt. Ezért

Így

Szeretnénk megmutatni, hogy ebben az esetben is érvényes a Little-formula, ami egyúttal a formulák helyességét is ellenőrzi.

Látható, hogy a rendszerbe való átlagos beérkezési intenzitás és ezért

Hasonlóan

mivel

Ezek után vizsgáljuk meg a tartózkodási és várakozási idő sűrűség- illetve eloszlásfüggvényét!

Mint, ahogyan eddig is tettük, a teljes valószínűség tétele miatt

ebből

Ezek a formulák a véges összegzés miatt bonyolultabbak, mint az esetben, de könnyű látni, hogy határértéknél

A várakozási idő sűrűségfüggvényére igaz az alábbi összefüggés

Ezek a formulák rögzített esetén szátmítógép segítségével minden további probléma nélkül kiszámíthatók.

Mint látható a valószínűség kiemelt szerepet játszik a képletekben.

Vegyük észre, hogy ez éppen annak a valószínűsége, hogy a rendszerhez érkező igény nem tud csatlakozni a rendszerhez, mert nincs hely. Ezt a valószínűséget „blokkolási” vagy igényvesztési valószínűségnek nevezzük és -vel jelöljük.

A Bayes-formula alkalmazásával

Ha még a -tól és -tól való függést is jelölni szeretnénk, akkor

Vegyük észre, hogy

A kezdőértékből kiindulva az igényvesztés valószínűsége rekurzíven meghatározható. Az is nyilvánvaló, hogy ez a sorozat esetén a -hoz konvergál és ezért rekurzióval biztosan tudunk találni olyan -t, melyre

ahol a egy előre megadott korlát az igényvesztés valószínűségére.

Ha iteráció nélkül szeretnénk meghatározni a -t, akkor a

egyenlőtlenséget kell megoldani -ra, ami nehezebb feladat, mint a rekurzív megközelítés.

Választhatunk egy közelítő megoldást is, ami abban rejlik, hogy az rendszer esetén nézzük meg, mi lesz annak a valószínűsége, hogy a rendszerben legalább igény tartózkodik és ezzel közelítjük a -t. Látható, hogy

így, ha

akkor teljesül a is. Vagyis

Most térjünk rá a tartózkodási idő Laplace-transzformáltjának a meghatározására! Az előzőekhez hasonlóan könnyű látni, hogy

Hasonlóan

ami nyilvánvalóan a

relációból is következik.

A Laplace-transzformáltakra azért van szükség, mert segítségükkel az érintett valószínűségi változók magasabb momentumait is meghatározhatjuk.

 Java-applet a rendszerjellemzők meghatározására 

11.5. Az típusú rendszer

Az előzőekhez hasonlóan könnyű látni, hogy ismét születési-halálozási folyamat

intenzitásokkal.

Így a stacionárius eloszlás

vagyis

ami azt mutatja, hogy paraméterű Poisson-eloszlást követ.

Könnyű látni, hogy a rendszerjellemzők

Be lehet bizonyítani, hogy ezek a formulák érvényesek rendszerre is, ahol

 Java-applet a rendszerjellemzők meghatározására 

11.6. Az típusú Erlang-féle veszteséges rendszer

Ezen modellre csatornás veszteséges rendszerként is szokás hivatkozni az alábbiak miatt. Az csatornás rendszerbe Poisson-folyamat szerint érkeznek az igények. Ha van üres csatorna vagy szerver az igény kiszolgálása exponenciális időtartamú paraméterrel. Ha minden kiszolgáló egység foglalt, akkor az igény elvész, azaz sorbanállás nem megengedett. Ezen probléma a tömegkiszolgálás egyik legrégibb problémája, mellyel a század elején a telefonközpontok kihasználtságával kapcsolatban foglalkozott A. K. Erlang és C. Palm. Hasonló jelenséggel találkozunk például a parkoló helyek esetében is.

A feltételek alapján ez a rendszer is egy születési-kihalási folyamattal modellezhető, melynek intenzitásai a következők

Azt mondjuk, hogy a folyamat az állapotban van, ha kiszolgáló foglalt, azaz ha igény tartózkodik a rendszerben.

Nyilvánvalóan az ergodikus eloszlás létezik, mivel a folyamat véges állapotterű. A stacionárius eloszlás

A normalizáló feltétel miatt

így

A rendszer egyik jellemzője a

valószínűség, melyet először Erlang vezetett be (1917-ben) és Erlang-féle veszteségformula vagy Erlang-féle B-formula néven ismert, általában szimbólummal jelöljük.

A Bayes-formula felhasználásával könnyű látni, hogy annak a valószínűsége stacionárius esetben, hogy egy újonnan érkező igényt nem fogad a rendszer, mert telített, azaz az igény elvész. Kis -re a valószínűség könnyen kiszámolható. Nagy -re és kis -ra , így

azaz a Poisson-eloszlás. Nagy -re és nagy -ra általában

Ebben az esetben a nevező a közepű Poisson-eloszlás első tagjának összege. Elegendő nagy -ra () a centrális határeloszlás-tétel miatt a Poissson-eloszlást közelítjük közepű és szórású normális eloszlással, így

ahol

és

A -ra azonban fel tudunk írni egy nagyon fontos rekurziós összefüggést is, hiszen

A kezdeti feltételből kiindulva bármely -re meg tudjuk határozni a -t. Ez azért fontos, mert nagyobb kiszolgáló számnál a faktoriális nem számolható, de a rekurzió még mindig működik.

Például esetben a pontos képletet nem tudjuk kiszámolni, de a közelítés és a rekurziós képlet értéket ad.

nagyon fontos szerepet játszik a gyakorlati problémák megoldásában ezért külön úgynevezett kalkulátorokat írtak, melyek megtalálhatók a

internet címen. A pontos és közelítő érték összehasonlítására mi is írtunk egy Java Script-et, amely megtalálható az alábbi linken

Az rendszer jellemzői:

1. A rendszerben tartózkodó igények átlagos száma, a foglalt szerverek átlagos száma

így szerverre jutó átlagos igényszám

2. A szerverek kihasználtsága

Mint már láttuk

Jelen esetben

3. Az átlagos tétlenségi idő (egy konkrét kiszolgáló esetén)

A jól ismert összefüggést alkalmazva

ahol az átlagos tétlenségi idő. Így

tehát

Ha az üres szerverek olyan sorrendben kezdik kiszolgálni az érkező igényeket, mint amilyen sorrendben megüresedtek, akkor egy szerver működését a következőképpen írhatjuk le. Ha egy üressé vált szerver másik üres szervert talál megüresedése pillanatában, akkor csak a -edik igény kiszolgálásával kezdődik ismét a foglaltsági periódusa.

Jelölje a szerver átlagos üresjárati periódusa hosszát, pedig a fenti állapotban az átlagos tétlenségi időt. Nyilvánvalóan , pedig a teljes várható érték tétele alapján:

azaz más úton is ugyanarra az eredményre jutunk.

4. A rendszer átlagos foglaltsági periódushossza

Nyilvánvalóan

melyből

 Java-applet a rendszerjellemzők meghatározására 

11.4. Példa. Egy parkolóhoz az autók másodpercenként érkeznek, és átlagosan percig maradnak. A beérkezés Poisson, a kiszolgálás exponenciális.

Milyen nagynak kell lennie a parkolónak, hogy egy autó 1% eséllyel forduljon vissza, mert a parkoló telített?

Megoldás:

A normális eloszlással való approximációt követve

Ebből

A normális eloszlás táblázatából nem nehéz ellenőrizni, hogy .

Ekkor közelítése: ,

a pontos értéke pedig:

11.5. Példa. Egy csatornás telefonközpontba átlagosan percenként érkeznek hívások Poisson-eloszlás szerint. A kiszolgálási idő exponenciális, perc átlaggal.

Határozzuk meg a rendszer jellemzőit!

Megoldás: Esetünkben Poisson-közelítés vehető, így

a Poisson-eloszlás szerint, sőt még -nál is

. Ez azt jelenti, hogy igény szinte sohasem lesz elutasítva.

A foglalt csatornák átlagos száma

így az egy csatornára jutó átlagos igényszám

és ez egyben a csatornák kihasználtsága

ami a rendszer kihasználatsága.

A rendszer átlagos foglaltsági periódushossza

A csatornák átlagos tétlenségi ideje

A csatornák átlagos foglaltsági ideje

Heterogén kiszolgálók esete

Az rendszer esetében feltesszük, hogy az i-edik kiszolgáló intenzitással szolgálja ki az igényeket, melyek érkezésükkor egyenlő valószínűséggel választanak a tétlen kiszolgálók közül. Ekkor nem elég tudni, hogy hány igény van a rendszerben, hanem ismernünk kell a foglalt kiszolgálók indexét is. Ezért nem születési-halálozási folyamattal, hanem általánosabb állapotterű Markov-lánccal van dolgunk.

Ha jelöli a foglalt kiszolgálók indexeit, amelyek nyilvánvalóan az -ad osztályú kombinációi, akkor a Markov-lánc állapotterét a indexhalmazok alkotják.

Jelölje

a folyamat stacionárius eloszlását, amely létezik, mivel az állapottér véges és irreducibilis. A szokásos módon felírhatjuk a stacionárius állapotegyenleteket, amelyek a következő alakot öltik

ahol az indexek növekvő sorrendbe rendezett halmazát jelöli, és pedig nincs értelmezve, ott az összegzést értelem szerint kell venni! Bár látszólag bonyolult egyenletrendszerrel van dolgunk, amelyben az ismeretlenek száma , megmutatjuk, hogy a megoldás viszonylag egyszerű, nevezetesen

ahol , , , amely a

normalizáló feltételből kapható meg.

Először nézzük meg az első állapotegyenletet! Behelyettesítve

Majd a harmadik egyenletnél végezzük el a behelyettesítést

Végül a legbonyolultabb, második esetet nézzük meg!

ami az egyenlőséget mutatja.

Ezek után a szokásos rendszerjellemzők a következők

1. a -edik kiszolgáló kihasználtsága

majd ebből

ahol az -edik kiszolgáló átlagos tétlenségi periódushossza

2.

3. Az igényvesztés, vagy blokkolás valószínűsége pedig .

Ebben az esetben is igaz, hogy .

Homogén esetben, vagyis amikor ,

vagyis a jól ismert képleteket kapjuk.

Meg kell jegyezni, hogy ezek a képletek tetszőleges, véges várható értékű kiszolgálási idők mellett is érvényesek.

11.7. Az típusú rendszer

Ismét olyan állandó beérkezési intenzitású rendszert vizsgálunk, melyben korlátlan hosszúságú sor kialakulása megengedett. A rendszer db kiszolgálóval (szerverrel) van ellátva. Ez az eset is leírható születési-halálozási folyamattal a következők miatt. Először is tekintsünk független, paraméterű exponenciális eloszlású valószínűségi változókat. Jelöljük -val ezen () változók minimumát. Nem nehéz belátni, hogy is exponenciális eloszlású lesz paraméterrel. Ugyanis

Ezt felhasználva kapjuk meg annak valószínűségét, hogy a rendszer a idő alatt a állapotból a állapotba, ill. a állapotból a állapotba kerül. Így

ahol

Könnyen látható, hogy az ergodikusság feltétele .

Amikor hozzákezdünk a mennyiségek kiszámolásához, azt találjuk, hogy a megoldást két részre kell szétbontanunk, mivel a mennyiség kétféle módon függ -tól. Eszerint, ha , akkor

Ha viszont , akkor

Összefoglalva a kapott eredményeket

ahol

Ez az éppen egy kiszolgáló egység kihasználtsága. Továbbá

és így

Annak a valószínűsége, hogy egy újonnan érkező igénynek sorba kell állnia,

Ebből

Ezt a valószínűséget széles körben használják például a telefonrendszerek, call-centerek vizsgálatával kapcsolatban. Itt annak a valószínűségét adja meg, hogy egy újonnan beérkezett hívás (igény) számára nincs szabad vonal (kiszolgáló egység) egy szerveres rendszerben. Ez az ú.n. Erlang-féle C-formula, vagy Erlang-féle várakozásos formula amit többnyire szimbólummal jelölünk.

Az rendszer jellemzői

1. Az átlagos sorhossz

2. A foglalt szerverek átlagos száma

3. A rendszerben tartózkodó igények átlagos száma

ami egyszerű megfontolásokból is adódik, hiszen egy igény vagy várakozik, vagy kiszolgálás alatt van. A kiszolgálás alatt levők száma viszont megegyezik a foglalt kiszolgáló egységek számával. Ha -gal jelöljük a szabad szerverek vagy kiszolgáló egységek átlagos számát, akkor

így

vagyis

4. A várakozási idő eloszlása

Egy érkező igénynek akkor kell várakoznia, ha a rendszerben legalább igény tartózkodik. Mivel ebben az esetben a kiszolgálás paraméterű exponenciális eloszlású valószínűségi változó, az igény várakozási ideje, ha igény tartózkodik a rendszerben Erlang-eloszlású és paraméterekkel. Így a teljes valószínűség tétele alapján a várakozási idő sűrűségfüggvénye

Behelyettesítve a stacionárius eloszlást

Vagyis

A várakozási idő eloszlásfüggvénye

Innen az átlagos várakozási idő

5. A tartózkodási idő eloszlása

A kiszolgálás azonnal elkezdődik, ha a rendszerben -nél kevesebb igény tartózkodik, így stacionárius esetben egy érkező igény rendszerben eltöltött ideje megegyezik a kiszolgálási idővel. Azonban, ha várakoznia kell, akkor a várakozási idő és a kiszolgálási idő összege, vagyis az eloszlás két független eloszlás összege, mely közül az egyik paraméterű exponenciális, a másik pedig a rendszertől függő paraméterű Erlang-eloszlás. A tartózkodási idő sűrűségfüggvényét a következő módon határozzuk meg.

Tudjuk, hogy

Ekkor

Ezért

Így

Innen

Továbbá

mint az várható volt.

Stacionárius esetben a távozó igények átlagos számának meg kell egyeznie az érkező igények átlagos számával, így a rendszerben tartózkodók átlagos száma állandó. Tehát annyi igény tartózkodik átlagosan a rendszerben, amennyi érkezik egy igény tartózkodási ideje alatt, vagyis

továbbá

Ezek az ú.n. Little-formulák, melyeket számolás útján is könnyen bizonyíthatunk. Ugyanis, mint beláttuk

Mivel

így

vagyis

mivel . Továbbá

hiszen

6. A szerverek összkihasználtsága

Egy szerver kihasználtsága nyilvánvalóan

Így az összkihasználtság

7. A foglaltsági periódushosszak

A rendszert akkor nevezzük tétlennek, ha a rendszerben nem tartózkodik igény, minden más esetben foglaltnak nevezzük. Jelölje a a rendszer átlagos foglaltsági periódushosszát. Ekkor (4) miatt a rendszer kihasználtsága

melyből

Ha az egyes kiszolgáló egységeket tekintjük és feltesszük, hogy üres egységnél, szervernél ahhoz érkezik hamarabb igény, amely korábban vált üressé, akkor ha igény tartózkodik a rendszerben, a szabad szerverek száma .

Tekintsünk egy konkrét szervert és tegyük fel, hogy a rendszerben igény tartózkodik a szerver szabaddá válása pillanatában. Ekkor ezen szerver átlagos üresjárati ideje ilyen feltételek mellett

Annak a valószínűsége, hogy ebben az állapotban van

így egy szerver átlagos szabad periódushossza

ahol annak a stacionárius valószínűsége, hogy egy érkező igénynek nem kell várakoznia. Ekkor ismét

melyből

ahol annak stacionárius valószínűsége, hogy a szerver nem üres, pedig az átlagos foglaltsági periódushossza. Így

esetben

így

amely a jól ismert képlet.

A következő sorokban megmutatjuk, hogy milyen kapcsolat van az Erlang-féle veszteséges rendszer és a jelenlegi rendszer között, melyet szokás Erlang-féle várakozásos rendszernek is nevezni.

Először tárjuk fel a két formula közötti kapcsolatot! Nevezetesen

Mint láttuk a , amely a várakozás valószínűségét jelenti nagyon fontos szerepet játszik a jellemzők meghatározásában. Az előző formula átírható az alábbi alakba

sőt azt is be lehet bizonyítani, hogy

amely a kezdőértékből rekurzívan számolható.

Ha minőségi mutatónak -t adjuk meg, akkor mindig létezik olyan , melyre . Ha rendelkezésünkre áll számítógép a feladatot pillanatok alatt meg lehet oldani.

Mi azonban egy olyan eljárást mutatunk be, amit a döntéshozók könnyen használhatnak.

Mint korábban is láttuk

Legyen , így . Ezért

Azaz, ha keresni akarunk olyan -ot, amelyre , akkor az

egyenletet kell megoldani, amely ekvivalens a

egyenlettel. Ha adott , akkor .

Fontos megjegyezni, hogy keresése független a -tól és -től, így különböző -ra előre megadhatók.

Például ha , akkor a hozzájuk tartozó -k rendre . Az képletet négyzetgyök-szabálynak is hívják, és nagyon jó közelítést ad, mint ahogyan a következő táblázat is mutatja.

11.1. ábra - Az Az n^{*} pontos és közelítő értékei pontos és közelítő értékei

Az n^{*} pontos és közelítő értékei

Nézzünk gyorsan egy példát, ahol jelentős többletkiadástól szabadulhatunk meg, ha alkalmazzuk a négyzetgyök-szabályt!

Vegyünk két call-centert, ahová először külön-külön érkeznek az ügyfelek. Ekkor összesen ügyfélfogadót kellene alkalmazni. Ha azonban az ügyfeleket egyesítjük, akkor ugyanolyan szintű szolgáltatáshoz kiszolgálót kell alkalmazni. A megtakarítás

nagyon fontos szerepet játszik a gyakorlati problémák megoldásában ezért külön úgynevezett kalkulátorokat írtak, melyek megtalálhatók a

internet címen.

 Java-applet a rendszerjellemzők meghatározására 

11.6. Példa. Adott egy 4 csatornás telefonközpont, , .

Határozzuk meg a rendszer jellemzőit!

Megoldás:

11.7. Példa. Egy repülőtér kifutópályáinak számát úgy kell meghatároznunk, hogy a leszállni kívánó repülőgép várakozásának valószínűsége 0.1-nél kisebb legyen. A befutások statisztikai vizsgálata megmutatta, hogy megengedhető a repülőgépek érkezését Poisson-eloszlással közelíteni. Óránként átlagosan érkezést mértek. A kifutópálya elfoglaltságának időtartamát exponenciális eloszlásúnak tételezzük felel perc várható értékkel.

Megoldás:

Mivel az idő mértékegysége különböző először is mindkét helyen órára nézzük az intenzitásokat. Így az ismert képleteket értékkel kell alkalmazni. feltétel biztosítására kell, hogy legyen.

Jelölje a várakozási valószínűségét kifutópálya esetén. Számolással a megfelelő képletbe való helyettesítéssel a következő valószínűségeket kapjuk

Így a kívánt valószínűség eléréséhez értéket kell tekinteni. lesz és ekkor a

11.8. Példa. Egy üzlet pénztárához a vevők átlagban 6 másodpercenként érkeznek Poisson-eloszlás szerint. A kiszolgálási idejük exponenciális eloszlású, másodperc átlaggal. Ha egy pénztár fenntartása óránként Ft-ba kerül, és ugyanennyi a várakozási költség is, mennyi pénztárt kell üzemeltetni, hogy a teljes költség várható értéke minimális legyen? (Ez óránkénti költség lesz.)

Megoldás:

Sorba véve az értékeket, az óránkénti minimális várható költség esetben adódik. Ekkor a rendszer jellemzői

11.8. Az rendszer

A következőkben az sorbanállási rendszerrel fogunk foglalkozni, amelynek specialitását az adja, hogy darab kiszolgáló van, és legfeljebb darab igény lehet a rendszerben egyszerre. A modellezés hasonló a végtelen kapacitású rendszeréhez azzal a különbséggel, hogy -nek nullának kell lennie ha . Az előző rendszerekhez hasonlóan könnyű látni, hogy egyensúlyi állapot esetén a rendszerben tartózkodó igények számának az eloszlása a következő

Amint azt láthatjuk a stacionáris valószínűségeknek esetén Poisson-, míg esetén geometria eloszlás alakúak. Felhasználva azt, hogy a valószínűségek összegének 1-nek kell lennie kaphatjuk meg -t, vagyis

Mivel számolásánál mindkét sor véges, így nincs szükség annak feltételezésére, hogy .

Hogy egyszerűsítsük a kapott formulát legyen .

Ekkor

Így

Ezek után határozzuk meg a szokásos rendszerjellemzőket!

1. Átlagos sorhossz

vagy

esetén a L'Hopital szabályt kell alkalmazni kétszer.

2. A rendszerben tartózkodó igények átlagos száma

Az kiszámításohoz vegyük figyelembe, hogy az rendszer esetén . Azonban esetén ezt az eredményt módosítani kell, figyelembe véve azt, hogy az igények egy hányada nem kerül be a rendszerbe, mivel azok akkor érkeznek, amikor már nincs hely a rendszerben. Látható, hogy az átlagos beérkezési intenzitás , ahol a foglalt kiszolgálók átlagos száma. Jól ismert, hogy , így .

3. Átlagos tartózkodási és várakozási idők

Az átlagos idők meghatározáshoz használjuk fel a Little-formulákat, vagyis

esetén az előző eredmények lényegesen leegyszerűsödnek a következőkre

Az utolsó egyenlet abból következik, hogy azaz , amely azt mutatja, hogy a rendszer átlagos kiszolgálási intenzitása megegyezik a tényleges átlagos beérkezési intenzitással, ami egyébként minden stabil születési-halálozási folyamatra igaz.

3. Érkezési pillanatban vett valószínűségek

Az érkezési pillanatban lévő valószínűségek meghatározásánál figyelembe kell venni, hogy -nál lévő vágás miatt a beérkezés nem Poisson már, így . A számolásnál a Bayes-tételt fogjuk felhasználni.

esetén összefüggést kapnánk mivel ebben az esetben 0-hoz tart.

4. A várakozási idő eloszlásfüggvénye

meghatározáshoz használjuk fel, hogy a rendszer már nem fogad igényt ha darab igény van a rendszerben. A szokásos módon, a teljes valószínűség tételét alkalmazva nyerjük

Felhasználva, hogy

és az , helyettesítéseket alkalmazva kapjuk, hogy

így

Hasonlóan határozható meg a tartózkodási idő eloszlásfüggvénye, valamint az érintett idők Laplace-transzformáltjai azzal a módosítással, hogy az Erlang-eloszlások sűrűségfüggvénye helyett azok Laplace-transzformáltjait kell beírnunk.

 Java-applet a rendszerjellemzők meghatározására 

11.9. Az rendszer

Eddig olyan rendszereket vettünk, ahol mind a beérkezési mind a kiszolgálási idők exponenciális eloszlásúak voltak, azonban a gyakorlatban az exponciális eloszlású kiszolgálási idők csak ritkán fordulnak elő, mivel legtöbbször a szóródási együttható értéke kisebb mint 1, így fontos az elméletet kiterjeszteni olyan esetekre is, ahol a kiszolgálás tetszőleges eloszlású. Ebben a fejezetben Poisson érkezéseket alkalmazunk valamint független általános eloszlású kiszolgálási időket.

Hatékonysági mérőszámok mint az átlagos várakozási idő vagy átlagos sorhossz, hasonlóan az rendszerhez a közép értékes módszer segítségével kiszámolhatóak. Egy beérkező igénynek először ki kell várnia az éppen kiszolgálás alatt álló igény kiszolgálásának végét, valamint az összes sorban elhelyezkedő igény kiszolgálását. A PASTA ( Poisson Arrivals See Time Average ), vagyis, hogy az érkezési pillanatban vett eloszlás megegyezik a tetszőleges pillanatban vett eloszlással, tulajdonságból tudjuk, hogy valószínűséggel talál az érkező igény legalább egy másik igényt kiszolgálás alatt.

Little-formula

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 a intervallum alatt beérkezett igények száma, a intervallum alatt a rendszerből kilépett igények száma. -t feltéve nyilvánvalóan .

Jelölje a intervallumban az átlagos beérkezési intenzitást

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

Végül legyen a rendszerben tartózkodó igények átlagos száma a intervallumban:

Az utolsó három egyenletből

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

Így

amelyet Little-formulának nevezünk.

A beágyazott Markov-láncok

A rendszer állapotát a rendszerben tartózkodó igények számaként - - értelmezve megfigyelhetjük a rendszer állapotváltozásait az idő függvényében. Ezek a változások közvetlen szomszéd típusúak, azaz ha igény van éppen a rendszerben, akkor a következő állapotában vagy lesz. A típusú átlépések száma legfeljebb eggyel különbözhet a típusú átlépések számától, ezért ha a rendszer elég sokáig működik, akkor a felfelé irányuló átlépések relatív gyakoriságának meg kell egyeznie a lefelé irányuló átmenetek relatív gyakoriságával. Így arra következtethetünk, hogy a beérkezések időpontjában észlelt rendszerállapot eloszlása meg kell, hogy egyezzen a távozások időpontjában észlelt rendszerállapot határeloszlásával .

Igazak a következő megállapítások

Poisson-folyamatú beérkezések esetén

Ha egy általános rendszerben az értékeit mindig csak eggyel változtatja és létezik a következő határeloszlások egyike, akkor a másik is létezik, és ezen határeloszlások egyenlőek:

Így az rendszerre

azaz a beérkezések, a távozások és a véletlenszerű megfigyelések egyensúlyi állapotban a rendszerbeli igények számának ugyanazt az eloszlását figyelik meg.

Fontosságuk miatt mind a két állítást bebizonyítjuk. Nézzük először az -et.

Vezessük be a következő jelöléseket

Legyen az az esemény, hogy egy beérkezés történik a intervallumban. Ekkor

Felhasználva a feltételes valószínűség definícióját

Az emlékezetnélküliség miatt az esemény nem függ a pillanatban a rendszerben tartózkodó igények számától, ezért

így

azaz

Ez természetesen a stacionárius valószínűségekre is igaz, azaz

-t is bebizonyítjuk, az felhasználásával. Jelölje a állapotban lévő rendszerbe történő beérkezések számát a intervallumban, és a intervallumban azon távozások számát, melyek után a rendszer az állapotba kerül. Feltételünkből következik, hogy

Továbbá, ha az összes távozások számát , az összes beérkezésekét pedig jelöli, akkor

A távozási pontokban észlelt határeloszlás felírható a következőképpen

Ha a számlálóhoz hozzáadunk és le is vonunk belőle -t, és a nevezőt felírjuk a fenti alakban, akkor

Mivel véges és -nek is annak kell lennie a stacionaritás feltétele miatt, (11.6)-ből és abból, hogy , egy valószínűséggel következik

Innen, az pontot is felhasználva kapjuk az állításunkat.

Várható értékes megközelítés

Jelölje az valószínűségi változó a kiszolgálási időt, a fennmaradó ( hátralevő) kiszolgálási időt. Az eddigiekhez hasonlóan könnyű látni, hogy

ahol a hátramaradt kiszolgálási idő várható értéke.

A Little-törvényt felhasználva,

Ezekből pedig az következik, hogy

A(11.7) formulát Pollaczek-Hincsin várható érték formulának nevezzük.

A következő részben megmutatjuk, hogy

amely a következő formában is írható

ahol a kiszolgálási idő relatív szórásnégyzetét jelöli. Fontos észrevétel, hogy az átlagos várakozási idő a kiszolgálási idő első két momentumától függ. Tehát nem elég tudni csak a kiszolgálási idő átlagát, de még a szórását is ismerni kell az átlagos várakozási idő kiszámításához.

Ezek után

Ebből a Little-formulát alkalmazva nyerjük az összefüggést az átlagos sorhosszra, vagyis

Az átlagos tartózkodási idő és a rendszerben tartózkodó igények várható száma nyilvánvalóan

11.9. Példa. Exponenciális kiszolgálási idők esetén , így az örökifjú tulajdonság miatt. Ebben az esetben a következőket kapjuk

11.10. Példa. Állandó kiszolgálási idők esetén , így . Ebben az esetben a következőket kapjuk

Az rendszer esetében láttuk, hogy

ezért a rendszerben tartózkodó igények számának generátorfüggvénye egyenlő a távozási pillanatban vett eloszlás generátorfüggvényével. Az is világos, hogy a rendszerben a távozás pillanatában annyi igény tartózkodik, amennyi bejött az éppen távozó igény tartózkodási ideje alatt. Ezért

Az ehhez tartozó generátorfüggvény

vagyis kifejezhető a tartózkodási idő Laplace-transzformáltjának a segítségével.

A generátorfüggvény és a Laplace-transzformált tulajdonságai miatt

Ebből az első deriváltra éppen a Little-formulát kapjuk, vagyis

A képlet segítségével magasabb momentumait, így a szórásnégyzetét is ki tudjuk számítani, ha ismerjük magasabb momentumait.

Hátralévő kiszolgálási idő

Tegyük fel, hogy egy igény akkor érkezik, amikor egy másik épp kiszolgálás alatt áll és jelölje ennek a teljes kiszolgálási idejét , vagyis ez egy megkülönböztetett kiszolgálási idő, olyan amelyikben igény érkezik. Jelölje az sűrűségfüggvényét,mely kiszámításhoz a kulcs az, hogy nagyobb a valószínűsége annak, hogy az igény akkor érkezik, amikor egy hosszú kiszolgálás van, mint annak, hogy rövid kiszolgálás történik. Tehát annak, hogy ideig tart arányosnak kell lennie -el valamint az hosszúságú kiszolgálási idők gyakoriságával, amelyet jelöl. Így a következőket írhatjuk fel

ahol a normalizáló konstans. Vagyis

ezért

Ebből az következik, hogy

Mivel az új igény beérkezése véletlenszerűen helyezkedik el az kiszolgálási időn belül így a hátralevő kiszolgálási idő várható értéke

11.11. Példa. paraméterű Erlang-eloszlású kiszolgálási idők esetén

így

vagyis

Látható, hogy a fenti módszerrel meg tudjuk határozni a hátralevő kiszolgálási idő sűrűségfüggvényét is, hiszen mivel a beérkezést egyenletesnek tételeztük fel

amelyből behelyettesítés után és szerint integrálva kapjuk, hogy

Így

ebből

Mutassuk meg, hogyan számolhatók az ilyen típusú integrálok !

Legyen egy tetszőleges, nemnegatív valószínűségi változó, amelynek létezik az -dik momentuma, ekkor

így

Mivel

ezért

melyből

azaz

Ezek után parciális integrálást alkalmazva és figyelembe véve az iménti határértéket, kapjuk

Ebből helyettesítést véve nyerjük, hogy

Pollaczek-Hincsin és Takács formulák

A következő összefüggéseket szokás Pollaczek-Hincsin transzformált egyenleteknek is nevezni.

melyekből deriválással a momentumok meghatározhatók és szerencsésebb esetekben a sűrűség- illetve az eloszlásfüggvények is.

Takács Lajos megmutatta, hogy

vagyis, hogy a várakozási idő momentumai a már meghatározott alacsonyabb rendű momentumok és a kiszolgálási idő megfelelő momentumai segítségével áll elő. Azt is láthatjuk, hogy a kiszolgálási időtől -el magasabb momentum létezését tételezzük fel.

Mivel és , függetlenek, ezért

így a tartózkodási idő magasabb momentumai is kiszámíthatók.

Ezen formulák alapján nem nehéz belátni, hogy

Az

alapján hosszadalmas számolással nyerjük, hogy

Mivel

ezért ismét hosszadalmas számolás révén

adódik.

Most vizsgáljuk meg a foglaltsági idő Laplace-transzformáltját!

Takács Lajos bebizonyította, hogy

vagyis explicite nem adható meg, hanem egy függvényegyenletet kell megoldanunk.

Azonban ennek segítségével magasabb momentumai meghatározhatók.

Nézzük meg -t! A jól ismert okok miatt

amit már korábban is megkaptunk az

relációból.

Hosszabb számolás után megmutatható, hogy

Ezek után nézzük meg a foglaltsági idő alatt kiszolgált igények számának a generátorfüggvényét!

Bebizonyítható, hogy

függvényegyenletet nyerjük, amit nehéz megoldani, de ebből deriválással a magasabb momentumok meghatározhatók.

Így

amit az

relációból is nyerhetünk, mint láttuk előzőleg, hiszen

Kissé hosszú számolás után megmutatható, hogy

Érdekességképpen megjegyezzük, hogy a , kiszámolásához nem kellett feltételezni -t, míg , , , -hez szükségünk volt rá.

 Java-applet a rendszerjellemzők meghatározására 

12. fejezet - Véges-forrású rendszerek

Eddig olyan rendszerekkel foglalkoztunk, ahol a beérkezések Poisson-folyamat szerint történnek. Ez más szóval azt is jelenti, hogy a forrásunk végtelen. Azonban a gyakorlatban is találhatók olyan problémák, amelyeknél a forrás véges. Tekintsük az ún. gépkiszolgálási problémát. Tegyük fel, hogy darab gép működik egymástól függetlenül. A gépek működési ideje valószínűségi változó. Miután a gép meghibásodik egy vagy több szerelő kijavítja, ahol a javítási idők is valószínűségi változók. Javítás után a gépek ismét dolgozni kezdenek, és az egész folyamat kezdődik előről. Látható, hogy teljesen hasonló problémával találkozunk a terminál-rendszereknél, ahol a gépek szerepét a terminálok, a szerelő szerepét a CPU veszi át. Mivel az utóbbi időben a számítógépek sztochasztikus modellezésében egyre nagyobb szerepet játszanak a sorbanállási rendszerek, jelen fejezetben gyakran használunk számítástechnikai kifejezéseket is.

Jelen problémakör a sorbanállási elmélet egyik legrégibb alkalmazási területe. Nagyon sok könyv és cikk foglalkozik vele különböző feltételek esetén. Összefoglaló áttekintést nyújt Sztrik János összegyűjtött irodalomjegyzéke, amely megtalálható az alábbi helyen

12.1. Az modell, Engset-féle veszteséges rendszer

Az rendszer esetén előfordulhat, hogy ha nincs szabad kiszolgáló az igényt nem tudjuk kiszolgálni ezért visszatér a forrásba, ahonnan ismét kiszolgálásra jelentkezik majd. A végtelen forrású rendszerekhez képest itt az igény nem vész el, hanem visszatér a forrásba. Könnyű látni, hogy a rendszerben tartózkodó igények száma szintén születési-halálozási folyam lesz a következő intenzitásokkal

ezért

amit csonkított binomiális eloszlásnak vagy Engset-eloszlásnak is neveznek.

Ez a véges forrású veszteséges rendszer, vagy más néven az Engset-féle rendszer eloszlása.

Az esetben, vagyis amikor minden igénynek saját kiszolgálója van, más szóval az igény nem vész el, az alábbi egyszerűbb képletet kapjuk

vagyis paraméterű binomiális eloszlásról van szó.

Ez annak valószínűsége, hogy egy konkrét igény a rendszerben van. Könnyű látni, hogy ez a formula esetben is igaz, hiszen ekkor

ha , ahol a forrásban eltöltött átlagos időt jelenti.

Az eddigiek alapján könnyű látni, hogy a rendszerjellemzők a következők lesznek

1.

2. a forrásban tartózkodó igények átlagos száma

3. a forrás kihasználtsága

melyből

Ebből megmutatjuk, hogy átlagosan hányszor kell próbálkoznia egy igénynek, hogy kiszolgálásra kerüljön, vagyis

így az elutasítások átlagos száma .

Az igény blokkolásának valószínűsége a Bayes-tétel alapján könnyen kiszámítható, nevezetesen

Ezt az következő módon láthatjuk be

Jelölje véges-forrás esetén az igényvesztés valószínűségét, vagyis , melyet szokás Engset-féle veszteség-formulának is nevezni. Mutassuk meg, hogy milyen rekurzió írható fel rá!

A kezdő érték

Nyilvánvaló, hogy

ahol

amit formálisan is láthatunk, továbbá az említett határértéknél -höz és a -ra kapott rekurzív összefüggést kapjuk.

Speciálisan esetben könnyű látni, hogy és így

amint ez várható volt.

Általános esetben

Vizsgáljuk meg, hogy a rendszerbe érkező igény milyen állapotot láthat!

Nyilván

ami Little-formula a veszteséges rendszerre.

12.2. Az modell

Feltesszük, hogy az igények egy elemű véges forrásból érkeznek, ahol a forrásban eltöltött idő minden igény esetén egymástól független paraméterű exponenciális eloszlású valószínűségi változó. A kiszolgálási idők szintén exponenciális eloszlásúak paraméterrel és függetlenek az előbbi valószínűségi változóktól.

Jelölje a időpillanatban a kiszolgáló egységnél tartózkodó igények számát. Az előbbiekhez hasonlóan nem nehéz belátni, hogy is egy születési-kihalási folyamat

születési intenzitásokkal, és

kihalási intenzitással. Így

ahol

és

Az ergodikus eloszlás mindig létezik, de ha akkor az igények torlódnak és több kiszolgáló egységre lenne szükség.

Az előbbi valószínűségekre egy másik kifejezést is megadunk, amely numerikus számításoknál könnyebben alkalmazható.

Legyen a paraméterű Poisson-eloszlás és ennek kummulatív eloszlása, azaz

Megmutatjuk, hogy

ahol

Ugyanis

Ebből

A rendszer jellemzői

1. A szerver kihasználtsága és a rendszer áteresztőképessége

A szerver kihasználtsága

A korábbi rekurzív összefüggést felhasználva

A rendszer áteresztőképessége

2. A rendszerben tartózkodó igények átlagos száma

Másképpen

3. Az átlagos sorhossz

4. Az igény generálásra alkalmas terminálok átlagos száma

5. A szerver átlagos foglaltsági periódushossza

Mivel

ezért

Számítógépes alkalmazásoknál gyakran szükségünk van az alábbi jellemzőkre is.

6. A terminálok kihasználtsága

Véges forrás esetén szükségünk van arra az újabb mérőszámra is , amely a gépkiszolgálási probléma esetén is nagyon fontos. Az indexű terminál kihasználtságán az

határértéket értjük, ha létezik. Ekkor

ahol a stacionárius valószínűséget jelöli.

Nyilvánvaló, hogy a terminálok (az igénygenerálás forrásai) akkor vannak kihasználva, ha működnek, így az összes terminál kihasználtsága

Egy tetszőleges terminál kihasználtsága

Ezt az összefüggést a következőképpen is megkaphatjuk. Látható, hogy

mivel a terminálok azonos kihasználtságúak, így

7. A terminálok átlagos várakozási ideje

A tartózkodási időre ismertetett tétel alapján

Ebből

és

ami az átlagos sorhosszra vonatkozó Little-formula. így

Az átlagos válaszolási idő

Egyszerű számolással könnyű bebizonyítani, hogy

ami ismét egy Little-formula. Ugyanis

8. További összefüggések

melyből

Érkezési pillanatban vett eloszlás

Az alábbiakban megmutatjuk, hogy egy véges forrású rendszernél egyensúlyi állapotban az érkezési pillanatokban mi lesz az eloszlás. Az eddigiekhez hasonlóan a Bayes-formula felhasználásával kapjuk

függetlenül attól, hogy egy vagy több kiszolgálónk van, hiszen láthatóan a kiszolgálási intenzitásoknál nem használtuk ki, hogy hány kiszolgálónk van.

Távozási pillanatban vett eloszlás

Az alábbiakban megmutatjuk, hogy egy véges forrású rendszernél egyensúlyi állapotban a távozási pillanatokban mi lesz az eloszlás. Az eddigiekhez hasonlóan a Bayes-formula felhasználásával kapjuk

abban az esetben, ha marad igény a rendszerben, és

ha a kiszolgáló(k) tétlen(nek) marad(nak) hiszen láthatóan a kiszolgálási intenzitásoknál nem használtuk ki, hogy hány kiszolgálónk van.

Rekurziv összefüggések

Látható, hogy a tartózkodási idő sűrűségfüggvénye az alábbi módon írható fel

Így a várható érték

Hasonlóan, a várakozási idő sűrűségfüggvénye csak abban különbözik, hogy 1 fázissal kevesebbet veszünk az Erlang-eloszlásnál, vagyis

így ennek várható értéke

ami magától érthető.

Az alábbiakban a

képlet helyességét szeretnénk ellenőrizni. Ehhez szükségünk van a következő összefüggésekre. Mint már korábban is láttuk

Azonban használjuk ki az ismert rekurziót

Mivel

így

Behelyettesítés után kapjuk,

Ezt felhasználva

Ebből

mely lényegében a rendszerben tartózkodó igények számára vonatkozó iteráció.

Tekintsük most már az ellenőrizendő rekurziót és végezzük el a behelyettesítést, vagyis

ami a jól ismert Little-formula, melyet korábban már bebizonyítottunk.

Most mutassuk meg, hogyan lehet más módon, kevesebb lépésben, közvetlenül -t ellenőrizni! Könnyű látni, hogy

vagyis egy rekurziót adtunk meg a kiszolgáló kihasználtságára, ha növeljük az igények számát. Ez a későbbiek során fontos szerepet játszik majd ha az egyes rendszerjellemzőkre rekurziót szeretnénk felírni, hiszen ezek a kihasználtságtól függnek.

Ebből

Az előzőek alapján

melybe be fogjuk helyettesíteni az -re kapott kifejezést. Ezek után mutassuk meg, hogy az iterációs formula a már korábban kapott összefüggést eredményezi! Ezért

vagyis a formula helyes.

Ezt követően lássuk, hogyan lehet rekurzív módon kiszámolni a mennyiségeket.

Most szükségünk van arra, hogyan tudjuk meghatározni -et segítségével.

Igazak az alábbi összefüggések

A kezdeti feltételek érthető módon

Ezek után az iteráció lépései

vagyis kettős iterációval haladunk előre a kívánt igény számig. Az iteráció előnye abban rejlik, hogy az említett várható értékek meghatározásához nem kell tudni a rendszerben tartózkodó igények számának stacionárius eloszlását, ami a fellépő faktoriálisok miatt nagyobb igény számnál numerikus problémákhoz vezethet. Hátránya, hogy ezzel a módszerrel csak a várható értékeket tudjuk kiszámolni.

A fentiekben már megmutattuk milyen közvetlen iteráció van -re és így várhatóan minden rendszerjellemzőre is.

A következő fontos rendszerjellemző az a forrásban tartózkodó igények átlagos száma, amely szintén előállítható rekurzió segítségével, nevezetesen

Ezzel az eredménnyel könnyen igazolható a terminálok kihasználtságának rekurzív formulája, mely a következő

A következő jellemző, amit hasonló módon írhatunk fel, az a rendszerben tartózkodó igények átlagos száma. Ezért

mivel érthető módon

ezért behelyettesítés után

Végül vizsgáljuk meg, hogy milyen formula adható az átlagos válaszolási időre! Kiindulva a

összefüggésből és felhasználva, hogy

behelyettesítés és rövidebb számolás után

Könnyű látni, hogy a hiányzó kiinduló értékek

Tartózkodási idő eloszlásfüggvénye

Az alábbi fejezetben a tartózkodási és várakozási idő eloszlásfüggvényét fogjuk meghatározni először a sűrűségfüggvény, majd a feltételes eloszlásfüggvények segítségével.

Nézzük először az egyszerűbb megoldást! Első lépésben a sűrűségfüggvényt határozzuk meg, majd ebből az eloszlásfüggvényt.

Analóg módon

Ebből az eloszlásfüggvény

Legyen , , .

Teljesen hasonlóan

Most határozzuk meg a tartózkodási idő eloszlásfüggvényét a feltételes eloszlásfüggvények segítségével!

Ez eddigiekhez hasonlóan, felhasználva az Erlang-eloszlás eloszlásfüggvényét felírhatjuk az alábbiakat

Eközben felhasználtuk, hogy

és így

az alábbi módon írható fel

Eközben az is látható, hogy deriváltja , melyet jól lehet használni a sűrűségfüggvény meghatározásához, vagyis

A rendszerben tartózkodó igények generárorfüggvénye

Megmutatjuk hogyan határozzuk meg az rendszer esetén a -t.

Közvetlen számolás esetén

Ezt megkaphatjuk az alábbi módon is. Ha -el jelöljük a forrásban tartózkodó igények számát, akkor tudjuk, hogy az forgalmi intenzitású Erlang-féle veszteséges rendszerrel ekvivalens, aminek a generátorfüggvényét már meghatároztuk. Így

Ennek segítségével

ezért

A tartózkodási idő Laplace-transzformáltja

Megmutatjuk hogyan határozhatjuk meg Laplace-transzformáltját!

1. Megoldás.

A Laplace-transzformáltakra az ismert képlet alapján

mivel ekkor a feltételes várakozási idő paraméterű Erlang-eloszlás és ennek kell venni a Laplace-transzformáltját. Behelyettesítve helyébe kapjuk

2. Megoldás.

Most a sűrűségfüggvényből határozzuk meg a -t. Mivel a nevező konstans, csak a számláló Laplace-transzformáltját vezetjük le.

A binomiális tételt alkalmazva valamint észrevéve, hogy egy Erlang-eloszlás Laplace-transzformáltja szerepel az összefüggésben kapjuk, hogy

Mivel

ezért

3. Megoldás.

Szintén csak a számláló Laplace-transzformáltját határozzuk meg először

A helyettesítést véve

majd helyettesítve

Az helyettesítést véve , ezért

így

Vagyis mind a három módon ugyanazt az eredményt kaptuk. Ebből elvben momentumai kiszámolhatók. Mivel , ezért

 Java-applet a rendszerjellemzők meghatározására 

12.1. Példa. Tekintsünk db gépet óra átlagos élettartammal, javítási idejük átlagosan 4 óra. Határozzuk meg a rendszer jellemzőit!

Megoldás: óránként, óránként, , ,

12.1. ábra - A példához tartozó A példához tartozó P_{n} értékek értékek

A példához tartozó P_{n} értékek

12.2. Példa. Az előző példadatban az átlagos élettartamot változtassuk meg órára! Határozzuk meg a rendszer jellemzőit!

Megoldás: , , , , és ebből látható, hogy egy szerelő nem elégséges.

12.2. ábra - A példához tartozó A példához tartozó P_{k} értékek értékek

A példához tartozó P_{k} értékek

Minden adat azt mutatja, amit vártunk, mivel a karbantartási tényező -nél nagyobb. Arra, hogy ezek után mennyi szerelőt kell beállítani, többféle kritérium lehet.

Ezzel a következő fejezetben foglalkozunk. Mindenesetre, hogy ne legyen torlódás, a feltételnek kell teljesülnie, ahol a szerelők számát jelöli.

12.3. Inhomogén modellek

A most ismertetett három inhomogén modell leírása megtalálható Csige László és Tomkó József [11] cikkében. A közölt numerikus eljárásokat egyszerű példákon keresztül szemléltetjük és összehasonlítjuk a különböző kiszolgálási elvekből adódó rendszerjellemzőket.

Adott, számú, gép meghibásodásainak javítását végezze egyetlen szerelő. Feltesszük, hogy a gépek működési időtartama exponenciális eloszlású, a -adik gépre paraméterrel, és a javítási idő is exponenciális eloszlású a paraméterrel. Mind a működési, mind a javítási idők teljesen függetlenek egymástól.

Tetszőleges pillanatban az gép közül néhány működhet, és a többi vagy javítás alatt van, vagy javításra várakozik. Jelölje , a pillanatban nem működő gépek számát. Ez még nem jellemzi kimerítően a rendszert. Meg kell mondanunk azt is, hogy melyek a nem működő gépek, és ezek közül melyiket javítja a szerelő. Tetszőleges -ra egy -dimenziójú vektort vezetünk be, melynek a komponensei a nem működő gépek indexeit jelölik. Ha a javítás a meghibásodás sorrendjében történik, azaz FIFO elv követése esetén a nem működő gépek felsorolása a meghibásodásuk sorrendjének felel meg. Így -ra a javítás alatt lévő gép indexét adja. A Processor Sharing (PS) elv követésekor, amikor az összes hibás gép javítás alatt van, és esetén e javítások mindegyike intenzitással folyik, az vektor elrendezése tetszőleges lehet. Ilyenkor a nagyság szerinti rendezésben állapodunk meg. Prioritásos kiszolgálás (PR) esetén a hibás gépeket indexük nagyságrendje szerint soroljuk fel, mivel az alacsonyabb indexű gép elsőbbséggel rendelkezik a magasabb indexű gépekkel szemben.

A gépkiszolgálás Markov-lánca alatt a

vektorfolyamatot értjük, ahol rendezését a különböző kiszolgálási elvek esetén az előbb elmondottak szerint kell érteni.

A folyamat folytonos idejű, véges állapotterű Markov- lánc. Ha a , , paraméterek mind pozitívak, akkor a lánc ergodikus.

12.3.1. Az rendszer

A gépkiszolgálási probléma esetén ez a diszciplina azt jelenti, hogy a gépek javítása meghibásodásuk után rögtön megkezdődik, melynek intenzitása függ a mindenkori hibás gépek számától, és azzal fordítottan arányos. Ha egy gép javítás alatt van egy olyan idő alatt, amikor rajta kívül még más gép is hibás, akkor ezen idő alatt egy gép javítási ideje csak mennyiséggel halad előre.

Ekkor a folyamat állapotterét az számok kombinációi alkotják, és ezekhez még hozzá kell venni a pontot (minden gép működik). Legyenek a lánc pillanatbeli eloszlását leíró függvények. Ekkor a Kolgomorov-egyenletek a következők

ahol az egészeknek a nagyság szerinti rendezése, és

ahol a megfelelő indexek értelemszerű értékeket vesznek fel.

A stacionárius eloszlás, amely azonos a

, ergodikus eloszlással, a

homogén lineáris egyenletrendszernek a feltételt kielégítő egyértelmű megoldása, ahol az összegzés n elem összes kombinációira terjed ki. Egyszerű helyettesítéssel belátható, hogy ennek az egyenletrendszernek a megoldása a

ahol a normalizáló feltételből határozható meg.

12.3.2. Az rendszer

A gépek javításai történjenek a meghibásodás sorrendjében. Ekkor a folyamat állapotterét elem összes rendű ismétlés nélküli variációi alkotják, amelyekhez még a pontot is csatolni kell ( a pont annak az esetnek a megfelelője, amikor mindegyik gép működik ).

A lánc pillanatbeli eloszlására vezessük be az alábbi függvényeket.

Ha jelöli a időpontban nem működő gépek számát, a nem működő gépek indexét meghibásodásuk sorrendjében, akkor a lánc pillanatbeli eloszlását leíró függvények:

ahol , . Ezek a függvények kielégítik a következő differenciálegyenlet-rendszert

A stacionárius eloszlás, mely azonos a

ergodikus eloszlással, a

homogén lineáris egyenletrendszerneik a feltételt kielégítő egyértelmű megoldása, ahol az összegzés n elem összes variációjára terjed ki.

Az egyenletrendszer könnyebben kezelhetővé válik, ha bevezetjük a következő vektorváltozókat. Legyen dimenziós vektor, amelynek a komponensei az számok -ad osztályú, lexikografikusan rendezett variációihoz tartozó valószínűségek. Ekkor az egyenletrendszer az alábbi differenciaegyenlet-rendszerbe megy át

Itt most -re -es mátrix, -re -es mátrix, és elemeik az egyenletrendszerből könnyen meghatározhatók.

Legyen és tetszőleges esetén . Ekkor , ahol .

Egy tetszőleges értékből a vektorok rendre meghatározhatók. A valószínűségeket a normalizáló feltétel figyelembe vétele után e vektorok komponensei szolgáltatják.

12.3.3. Az rendszer

Abszolút prioritásos kiszolgálási elv esetén a folyamat állapotterét az számok kombinációi alkotják, és ezekhez még hozzá kell venni a pontot (minden gép működik).

Legyenek a lánc pillanatbeli eloszlását leíró függvények. Ekkor a Kolgomorov-egyenletek a következők

A stacionárius eloszlás, amely azonos a

, ergodikus eloszlással, a

homogén lineáris egyenletrendszernek a feltételt kielégítő egyértelmű megoldása, ahol az összegzés elem összes kombinációra terjed ki.

Az egyenletrendszer megoldásához, hasonlóan a meghibásodás sorrendjében történő kiszolgálás esetéhez, vezessük be a következő vektorváltozókat.

Legyen dimenziós vektor, amelynek a komponensei az számok -ad osztályú, lexikografikusan rendezett kombinációhoz tartozó valószínűségek. Ekkor az egyenletrendszer az alábbi differencia egyenletrendszerbe megy át.

Itt most -re -es mátrix, -re -es mátrix, és elemeik egyenletrendszerből kiolvashatók. Ezt a differencia egyenletrendszert ugyanúgy oldhatjuk meg, mint a FIFO kiszolgálás esetén.

12.3.4. Rendszerjellemzők

Könnyű látni, hogy stacionárius esetben

1. A szerelő kihasználtsága

2. A gépek kihasználtsága

Jelölje az -edik gép kihasználtságát. Ekkor

ahol az -edik gép hibás állapotban való tartózkodásának várható értékét jelöli,

azaz annak stacionárius valószínűsége, hogy a gép rossz. Így

valamint FIFO esetben az átlagos várakozási idő

Könnyű látni, hogy a hibás gépek várható száma

Fennáll továbbá a

reláció, amely a Little-tétel egy speciális alakja. Homogén esetben ez nyilvánvalóan az

alakot ölti, ahol a működő gépek átlagos számát jelöli.

Az inhomogén modellek további általánosításával foglalkoznak pl. a Pósafalvi – Sztrik [54], [53] cikkek.

Most nézzünk meg néhány futási eredményt, amelyekkel a különböző kiszolgálási elvek hatását tudjuk demonstrálni.

12.3. ábra - Futási eredmények

Futási eredmények

12.4. Homogén forrású modellek összehasonlítása

Az alábbiakban ismertetett eredmények Asztalos Domonkos [5] cikkében találhatók meg, és olyan véges forrású tömegkiszolgálási rendszerekre vonatkoznak, ahol egy kiszolgáló egység fogyasztót szolgál ki. A forrásnál eltöltött idő minden fogyasztóra nézve azonos paraméterű exponenciális eloszlású változó, és az -edik fogyasztó kiszolgálási ideje paraméterű exponenciális eloszlású valószínűségi változó. Ennél a modellnél vizsgáljuk a kiszolgáló egység foglaltsági periódusait.

Meg lehet mutatni, hogy PS kiszolgálási elv mellett a kiszolgáló egység foglaltsági periódusának várható értéke

ahol .

12.1. Tétel. Exponenciális struktúrájú, véges, homogén forrású rendszerben abszolút prioritásos kiszolgálási diszciplina esetén tetszőleges -re a kiszolgáló egység foglaltsági periódusainak várható értéke , stacionárius esetben független a prioritások kiosztásától.

12.2. Következmény.

A FIFO kiszolgálási diszciplina megfelel a érkezési sorrendben való kiszolgálásnak, a LIFO esetén egy érkezés kiszolgálása rögtön megkezdődik, és az esetleg megszakított fogyasztó kiszolgálása a megszakítás helyétől folytatódik a megszakítást okozó fogyasztó kiszolgálása után.

Bizonyítás. A Következmény bizonyítása. Prioritásos kiszolgálás esetén független a prioritások kiosztásától. A FIFO diszciplinával azonos kiszolgálást kapunk, ha egy érkezéskor az éppen beérkező fogyasztóhoz rendelt prioritás értéke megegyezik azzal a számmal, hogy hányadiknak érkezett a kiszolgáló egységhez, és a korábban már a kiszolgáló egységben lévő fogyasztók prioritását nem változtatjuk meg. Ha egy fogyasztó távozik a kiszolgáló egységből, akkor a kiszolgáló egységnél maradt fogyasztók mindegyikének a prioritását eggyel csökkentjük. A forrásnál tartózkodó fogyasztók között a fennmaradt prioritásértékek tetszőlegesen kioszthatók. A LIFO diszciplinával azonos kiszolgálást kapunk, ha egy érkezéskor az éppen beérkező fogyasztó prioritása egy lesz, és a korábban már a kiszolgáló egységnél tartózkodó fogyasztók prioritását eggyel növeljük, egyébként a prioritások kiosztása megegyezik a FIFO-nál leírtakkal.

12.3. Tétel. Exponenciális struktúrájú, véges, homogén forrású tömegkiszogálási rendszerekben .

A kiszolgálási diszciplinákat két csoportra oszthatjuk. Az első csoportba azok tartoznak, amelyeknél bármely véges intervallum felosztható véges számú diszjunkt intervallumok olyan sorozatára, hogy mindegyik intervallumban csak egy adott fogyasztó részesül kiszolgálásban. Ezeket a kiszolgálási diszciplinákat osztatlan kiszolgálású diszciplináknak nevezzük. Ilyenek a FIFO, a LIFO, az RR és PR diszciplinák. A másik csoportba tartozik az összes többi. Ilyen például a PS elv. Egy kiszolgálási diszciplina konzervatív, ha a kiszolgáló egységnél nem vész el, és nem keletkezik kiszolgálási igény.

12.4. Tétel. Exponenciális struktúrájú, véges, homogén forrású tömegkiszolgálási rendszerben, amely gépet tartalmaz és paraméterekkel, a foglaltsági periódus várható értéke stacionárius esetben azonos minden konzervatív osztatlan kiszolgálású diszciplinára és

Bizonyítás. Könnyen belátható, hogy a prioritásos kiszolgálási diszciplina konzervatív és osztatlan kiszolgálójú, és a tételünk szerint értéke független a prioritások szétosztásától, és attól is, ha a prioritások szétosztása tetszőleges időpontban megváltozik. Az osztatlan kiszolgálású diszciplinák definíciója szerint bármely véges intervallumban véges azoknak az eseteknek a száma, amikor a kiszolgálás átvált egyik fogyasztóról a másikra. Így az a konzervatív osztatlan kiszolgálású rendszer, amelyben az eredeti diszciplina döntésének megfelelően megváltoztatjuk a prioritások eloszlását, ugyanúgy viselkedik, mint az eredeti rendszer.

12.5. Az modell

Az előző modellben adott feltevéseinke<t most csupán annyiban változtatjuk, hogy az számú terminált szerver szolgálja ki . így esetén a állapot azt jelenti, hogy éppen db terminál igénye van kiszolgálás alatt, egyetlen várakozó igény sincs és szerver tétlen. A szerverek tevékenységüket egymástól függetlenül végzik. Ekkor is egy születési-halálozási folyamatot kapunk:

intenzitásokkal.

Az egyensúlyi eloszlás

Természetesen teljesülnie kell a

összefüggésnek. meghatározására ez a képlet túlságosan bonyolult, így egy egyszerűbb rekurzív formulát használunk.

Jelöljük -val a következő hányadost

Ekkor a következő összefüggés alapján számolhatunk

Mivel a

összefüggésnek teljesülnie kell, ezért

Mindkét oldalt -al elosztva

így

Majd

Ezek után a szokásos módon megadhatjuk a rendszerjellemzőket

1. A rendszerben tartózkodó igények átlagos száma

2. A várakozási sor átlagos hossza

3. Az igény generálásra alkalmas terminálok átlagos száma

4. A rendszer kihasználtsága

5. A rendszer átlagos foglaltsági periódushossza

6. A foglalt kiszolgálóegységek átlagos száma

Továbbá

7. A tétlen kiszolgálóegységek átlagos száma

További összefüggés

8. A terminálok kihasználtsága

9. A terminálok átlagos várakozási ideje

amiből

Az átlagos válaszolási idő

innen

ami a jól ismert Little-formula, azaz az átlagos beérkezési intenzitás és a rendszerben töltött átlagos idő szorzata a rendszerben tartózkodó igények átlagos számával egyenlő. Ebből

vagyis

Mutassuk meg, hogy

mert ebből

következik, ami szintén egy Little-formula.

Tudjuk, hogy

ahol

Jól ismert továbbá, hogy

Ekkor

Vagyis

más alakban

azaz

ami várható volt, mivel a rendszer egyensúlyi állapotban van. Ezért

10. A kiszolgálók átlagos tétlenségi periódushossza

Ha a tétlen kiszolgálók olyan sorrendben kezdik kiszolgálni az igényeket, mint amilyen sorrendben előzőleg befejezték a foglaltsági periódusokat, akkor egy szerver tevékenységét a következőképpen írhatjuk le. Ha egy tétlenné vált szerver másik tétlen szervert talál a munka befejeződés pillanatában, akkor csak a -edik igény kiszolgálásával kezdődik ismét a foglaltsági periódusa.

Jelölje a szerver átlagos üresjárati periódusa hosszát, pedig a fenti állapotban az átlagos tétlenségi időt. Nyilvánvalóan

pedig a teljes várható érték tétele alapján

ahol

azaz annak valószínűsége, hogy van tétlen szerver.

11. A szerverek átlagos foglaltsági periódushossza

Mivel

így

Vagyis

12.5.1. A várakozási idő eloszlásfüggvénye

Megmutatjuk hogyan lehet meghatározni rendszer esetén a várakozási és tartózkodási idő sűrűségfüggvényét, majd ebből az eloszlásfüggvényeket.

ha , akkor

melyből

Könnyű látni, hogy

éppen a várakozás valószínűsége. Fejezzük ki -t más alakban is, mert erre később szükségünk lesz! A helyettesítés után

Megmutatjuk, hogy

amiből

ami éppen azt jelenti, hogy nincs várakozás. Ebből deriválással megkapjuk a sűrűségfüggvényt, ami

Ha -t vesszük, vagyis a pontot kihagyjuk belőle, akkor

Ha bevezetjük az helyettesítést, akkor és csak az integrál a következő alakot ölti

vagyis

amint ez várható volt. Ezért

Most határozzuk meg a sűrűségfüggvényt -ra! Vagyis

ugyanazt kapjuk, de tudni kell, hogy

Ebből

Ezért

amit már korábban is megkaptunk. Ellenőrzésképpen vizsgáljuk meg a képletet esetre! Ekkor

de

így

A tartózkodási idő eloszlásfüggvényének a meghatározása hasonló elven történik, mint a várakozási idő esetében tettük, de eléggé hosszadalmas.

Bizonyítható, lásd Allen [2], Kobayashi [42], hogy esetben

ahol

Ebből deriválással

A normalizáló konstansra itt is felírható egy rekurzió, nevezetesen

a

kezdei értékből kiindulva.

12.5.2. A tartózkodási idő Laplace-transzformáltja

Először határozzuk meg a várakozási idő Laplace-transzformáltját!

Az eddigiekhez hasonlóan könnyű látni, hogy

Lépésről-lépésre számítjuk ki a kívánt mennyiségeket

Továbbá

ahol . Ezt tovább folytatva az utolsó egyenlőség így írható

Ezek után

Ellenőrzésképpen vizsgáljuk meg az esetet!

Ekkor

amit korábban is kaptunk.

Ezek után nyilvánvaló, hogy

ami r=1 esetben a

formulát adja.

 Java-applet a rendszerjellemzők meghatározására 

12.3. Példa. Egy üzemben db gép üzemel, egyenként óra átlagos élettartammal. A gép javításának várható értéke óra, a szereléseket fős szerelőgárda végzi. Adjuk meg a rendszer jellemzőit, és hasonlítsuk össze őket az előző példában szereplő jellemzőkkel!

Megoldás:

A rekurzív összefüggéseket használva, -ről indítva a rekurziót,

könnyen meghatározhatjuk az értékeket, pl

és így tovább.

Tudjuk, hogy

Innen

A következő táblázat megadja a különböző állapotok valószínűségét.

, ,

12.4. ábra - A különböző állapotok valószínűségei

A különböző állapotok valószínűségei

Összehasonlítva a megfelelő példában szereplő jellemzőkkel, láthatjuk, hogy az egy javítóra jutó gépek majdnem egyforma száma mellett ( ill. ) a helyzet sokkal jobb gép és szerelő esetében, ugyanis a hatékonysági vizsgálatok az alábbi adatokat szolgáltatták

12.5. ábra - A példához tartozó adatok

A példához tartozó adatok

12.4. Példa. Az előző problémában , volt. Tételezzük fel, hogy az időegység az óra, hogy a gépállás óránkénti költsége Ft, míg a szerelők óránkénti költsége Ft. Mi lesz ebben ez esetben a szerelők optimális száma?

Megoldás: Látható, hogy az óránkénti átlagos költség függvénye.

A következő táblázat megadja a stacionárius eloszlást esetén (tapasztalatból tudjuk, hogy az számra ).

12.6. ábra - Stacionárius eloszlás

Stacionárius eloszlás

A következő táblázat az időegységre jutó költségeket adja meg:

12.7. ábra - időegységre jutó költségek

időegységre jutó költségek

Látható, hogy az optimális szerelőszám ilyen költségtényezők mellett .

Ez a példa is mutatja, hogy rendszerek összehasonlítása többféleképpen értelmezhető.

Az említett példák jól szemléltetik ezt a problémakört.

12.6. Az rendszer

Ennél a rendszereknél a véges forrásból érkező igények még várakozhatnak, ha a rendszerben tartózkodó igények száma érkezésük pillanatában kevesebb, mint vagy egyből visszakerülnek a forrásba, ha a rendszer betelt. Az eddigiek alapján könnyű látni, hogy a rendszer viselkedése

intenzitású születési-halálozási folyamattal írható le.

Ez magában foglalja az eddig vizsgált rendszereket, hiszen , . Az irodalomban kevésbé vizsgált, de értelemszerűen módosításokkal felhasználhatjuk az eddigi módszereket, a lényegi változás a normalizáló konstansban van, vagyis -t úgy kell megválasztani, hogy

teljesüljön. Szintén könnyen látható, hogy

Bár nincsenek zárt alakú formulák, mint az esetben, de számítógép segítségével a rendszerjellemzők könnyen meghatározhatók.

Nem mutatva az paramétereket

Az eddigiekhez hasonlóan könnyű belátni, hogy az igény blokkolási valószínűsége

Speciálisan, ha , akkor

melyből

amint az várható volt.

Egyszerű számolással látható, hogy

vagyis a normalizáló konstansra rekurzió írható fel a K kapacitást illetően rögzített mellett

induló értékkel.

A rendszerhez érkező igény érkezési pillanatában az eloszlás

de ahhoz is szükség van, hogy az érkező igény bejusson a rendszerbe. Így

Ezért a várakozás valószínűsége

Nem nehéz belátni, hogy

így az eddigi lépéseket értelemszerűen ismételve

speciálisan, ha , vagyis minden igény bejöhet a rendszerbe, akkor

és a jól ismert képletet nyerjük vissza.

Értelemszerű módosítások után az eloszlásfüggvény

A Laplace-transzformált

12.7. Az rendszer

Ebben a részben egy újfajta technikát mutatunk meg, mert a kiszolgálási idők már nem lesznek exponenciális eloszlásúak így ennek következtében a működést leíró sztochasztikus folyamat nem lesz folytonos idejű, diszkrét állapotterű Markov-lánc. Az ismertetett modell Yashkov [82] cikkében található meg.

Tekintsünk egy olyan számítógépes rendszert, amely egy központi egységből és periféria-egységből áll. Mindegyik program egy igénynek felel meg, a központi egység a kiszolgáló egységeknek. Tegyük fel, hogy egy adott perifériát csak egy program használhat, és a periféria-egységben eltöltött időtartamok minden programra nézve független, azonos paraméterű exponenciális eloszlású valószínűségi változók. Miután a program bizonyos időt eltöltött a periférián, átkerül a központi egységbe, és itt azonnal megkezdődik a kiszolgálása, amelynek igényelt időtartama várható értékű, eloszlásfüggvényű és sűrűségfüggvényű valószínűségi változó . A központi egységben a programok kiszolgálása Processor Sharing (PS)-elv szerint történik, azaz hogyha a időintervallumban egyidűleg programot szolgálnak ki, akkor az egyes jobok kiszolgálási ideje csak -val halad előre. A programok kiszolgálásuk után abba a perifériába kerülnek vissza, ahonnan érkeztek.

Ebben a modellben a segédváltozók módszerét fogjuk alkalmazni a rendszert leíró sztochasztikus folyamat megadásánál. Vezessük be a következő valószínűségi változókat

: a -edik időpillanatban a CPU-nál tartózkodó igények száma,

: a -edik időpillanatban a CPU-nál tartózkodó igények eltelt kiszolgálási ideje esetben.

Látható, hogy az

sztochasztikus folyamat olyan Markov-folyamat, melynek állapotterét egy diszkrét komponensből és több folytonos komponensből álló vektorok alkotják. Az ilyen típusú folyamatokat szakaszonként lineáris Markov-folyamatoknak nevezzük.

Meg kell jegyeznünk, hogy nagyon sok problémát ilyen folyamattal tudunk hűen leírni. Részletes tanulmányozásra ajánljuk Gnedenko-Kovalenko [23] könyvét.

Legyen

azaz , annak a valószínűsége (sűrűségfüggvénye) , hogy a központi egységnél a időpontban job tartózkodik, és az egyes jobok kiszolgálásából hosszúságú idő telt el. Legyen megfelelően kicsi pozitív szám.

Ekkor -ra a következő összefüggés írható fel

A jobb oldal első tagja azt írja le, hogy a időintervallumban nem fejeződik be egyetlen kiszolgálás sem. A második tag pedig azt, hogy ebben az időintervallumban a egy program közül egy kiszolgálása fejeződik be. Mindkét oldalt -vel osztva, és , határértéket véve kapjuk, hogy

ahol .

-ra és -re hasonlóan nyerjük

Ezek az egyenletek nem írják le teljesen a rendszer működését, mivel nem veszik figyelembe az esetleges ugrásszerű átmeneteket azokban a pillanatokban, amikor a programok a perifériákból a központi egységbe kerülnek. A hiányzó egyenleteket hasonlóan kapjuk meg

A kapott integro-differenciál egyenletek megoldása közvetlen helyettesítéssel adódik, nevezetesen

és

Legyen annak a stacionárius valószínűsége, hogy tetszőleges időpontban a központi egységben program tartózkodik. Nyilvánvalóan

A valószínűséget a normalizáló feltételből kapjuk meg.

Az rendszerben a rendszerjellemzőket értelemszerű módosításokkal kapjuk

amelyből

vagyis

ami a Little-formula.

Nyilvánvalóan, bár nincsen várakozás a teljes kiszolgálási idő, ami megegyezik a rendszerben eltöltött idővel, hosszabb mint az igényelt kiszolgálási idő. A a elvből adódik.

Bár homogén esetben a tartózkodási idő átlagára különböző kiszolgálási elvek mellett is ugyanazokat az értékeket kapjuk, a szórásnégyzetük már lényegesen különbözik egymástól, ha más elvet alkalmazunk.

Meg lehet mutatni, hogy rendszer esetében

Homogén esetben

12.8. A modell

Ennek a modellnek a leírása Sztrik [70] cikkében található meg.

Tekintsünk egy olyan számítógépes rendszert, amely központi egységekből, terminálokból, és jobokból áll. Minden job egy terminállal van kapcsolatban, ahol nincs várakozás. Sorok csak a központi egységeknél fordulhatnak elő. Az ilyen rendszerek elemzéséhez szintén véges forrású sorbanállási modellt használunk.

Legyen a rendszerben lévő jobok száma , és a központi egységek száma . A job bizonyos időt tölt el a terminálnál, ezután a központi egységbe kerül, ahol a job kiszolgálása azonnal megkezdődik, ha az központi egység között van szabad, egyébként sor alakul ki. A jobokat érkezésük sorrendjében szolgálják ki, és kiszolgálási idejük azonos paraméterű exponenciális eloszlású valószínűségi változó. A job kiszolgálásának befejeződése után visszatér a termináljához, ahol véletlen hosszúságú ideig tartózkodik. A -edik job terminálnál eltöltött ideje eloszlásfüggvénnyel és sűrűségfüggvénnyel rendelkező valószínűségi változó. Továbbá feltesszük, hogy a konstrukcióban fellépő valószínűségi változók teljesen függetlenek.

12.8.1. A stacinárius eloszlás meghatározása

Jelölje a valószínűségi változó a időpontban a terminálnál lévő jobok számát, ezeknek a joboknak az indexeit lexikografikus sorrendben, és

a központi egységnél lévő (kiszolgálás alatt lévő vagy sorbanálló) jobok indexeit érkezésük sorrendjében. Az

folyamat csak akkor Markov-folyamat, ha az eloszlásfüggvények exponenciálisak.

Vezessük be a változót, amely azt az időt jelöli, amelyet az job a terminálnál eltöltött a legutolsó központi egységbeli kiszolgálása óta. Az így kapott

folyamat rendelkezik a Markov tulajdonsággal.

Jelölje és az egészek -ad osztályú variációinak illetve a kombinációinak lexikografikusan rendezett halmazát. Ekkor az folyamat állapottere az olyan

pontokból áll, ahol

Az folyamat akkor van az állapotban, ha az

indexű jobok már ideje vannak a termináloknál, és a központi egységnél lévő jobok indexe érkezési sorrendben.

A Kolmogorov-egyenletek levezetéséhez szükségünk van tetszőleges intervallumban lejátszódó átmenetek vizsgálatára. Az átmeneti valószínűségeket a következő módon adhatjuk meg esetére.

ahol az indexeket jelöli lexikografikus sorrendben, és a megfelelő időket.

Ha akkor az átmeneti valószínűségek a következők

Vezessük be a következő függvényeket

Legyen a következőképpen definiálva: .

12.5. Tétel. Ha , , akkor az folyamatnak van egyértelmű ergodikus ( stacionárius ) eloszlása, amely független a kezdeti feltételektől, azaz

A tétel bizonyítása Gnedenko-Kovalenko [23] könyvének 211. oldalán található tételből következik.

A tétel biztosítja a következő határértékek létezését, és egyértelműségét

ahol jelöli az állapotok sűrűségfüggvényét, ha . Feltesszük, hogy rögzített -ra az ergodikus eloszlásoknak létezik a sűrűségfüggvénye. Ehhez elegendő feltenni, hogy az -nek van sűrűségfüggvénye.

Vezessük be a

ún. normált sűrűségfüggvényeket!

12.6. Tétel. A fenti normált sűrűségfüggvények kielégítik a (12.3), (12.5) integro-differenciál-egyenleteket a (12.4), (12.6) határfeltételek mellett.

, esetén,

, esetén,

valamint

A jelentése a bizonyításban szerepel, és

Bizonyítás. Mivel Markov-folyamat, ezért sűrűségfüggvényei kielégítik a Kolgomorov-Chapman egyenleteket. Tekintsük a folyamatot rövid ideig. Ekkor a következő összefüggések igazak:

, esetén.

Hasonlóan

, esetén.

Végül

Ezekből az összefüggésekből a tétel állítását könnyen megkaphatjuk. A felírt összefüggések bal oldalát -val osztva, és figyelembe véve a normált sűrűségfüggvény definícióját, és határértéket véve kapjuk a tétel állítását.

A tétel (12.3)(12.5) egyenlőségeinek bal oldalán a parciális differenciálhányados szokásos jelölését használtuk fel. Ezt általában nem tehetjük meg, mivel a parciális differenciálhányados létezését nem tettük fel. Ezért használtuk a jelölést. Valójában az iránymenti deriváltat jelenti. A

ergodikus eloszlás meghatározásához meg kell oldani a (12.3)(12.5) egyenleteket a (12.4)(12.6) határfeltételek mellett. Legyen

Ekkor behelyettesítéssel ellenőrizhető, hogy kielégítik az , egyenleteket a , határfeltételek mellett, és ezek a értékek rekurzióval kifejezhetők függvényében. Nevezetesen

Ezek az egyenletek teljesen leírják a rendszer működését.

Jelölje annak a stacionárius valószínűségét, hogy a termináloknál az indexű jobok vannak, és a központi egységnél lévő jobok indexei érkezési sorrendben . Továbbá jelölje annak a stacionárius valószínűségét, hogy az indexű jobok tartózkodnak a termináloknál.

Ezek után könnyen igazolható, hogy

A -ra kapott összefüggést felhasználva kapjuk, hogy

Hasonlóan

Jelölje és annak a stacionárius valószínűségét, hogy a termináloknál , illetve a központi egységeknél job tartózkodik. Ekkor világos, hogy

Könnyen belátható, hogy

ahol a normalizáló feltételéből határozható meg.

Homogén esetben a következő eredményekhez jutunk

Ezért

Ezek az eredmények megegyeznek az modell stacionárius valószínűségeire kapott képletekkel. Látható, hogy ezek az eloszlásfüggvény alakjától nem függnek, csak az várható értékektől.

Rendszerjellemzők

1. A terminálok kihasználtsága

Jelölje annak a stacionárius valószínűségét, hogy az -edik job a terminálnál tartózkodik, vagyis

Nyilvánvalóan az -edik terminál kihasználtsága

2. A CPU-k kihasználtsága

Az eddigiekhez hasonlóan egy konkrét CPU kihasználtsága

ahol a foglalt CPU-k átlagos számát jelöli. Így a CPU-k összkihasználtsága .

3. átlagos várakozási és tartózkodási idők

Így az -edik job átlagos várakozási ideje:

Az -edik job központi egységnél eltöltött átlagos ideje ( várakozással és kiszolgálással eltöltött idő )

Mivel

ahol jelöli a központi egységnél levő jobok átlagos számát, megkapjuk a

modellre vonatkozó Little-formulát

Meg kell jegyeznünk, hogy a gépkiszolgálási probléma terminológiáját használva az -edik gép kihasználtságát, az -edik gép várakozási ill. rossz állapotban való átlagos tartózkodási idejét adja.

A modell tovább általánosítható oly módon, hogy pl. a kiszolgálási intenzitások függnek a rendszer állapotától, lásd Sztrik [68], [69].

IV. rész - Feladatgyűjtemény

13. fejezet - Végtelen-forrású rendszerek

Oldjuk meg a

egyenletrendszert differencia-egyenletek segítségével!

Megoldás:

Látható, hogy az iménti egyenlet átírható a

formába, amely tekinthető egy konstans együtthatós másodrendű differencia-egyenletnek. Ennek általános megoldása

ahol megoldása a

egyenletnek. Könnyen kiszámítható, hogy és így

Azonban , így mivel , és .

rendszer esetén a stacionárius állapotegyenletek segítségével határozzuk meg a rendszerben tartózkodó igények generátorfüggvényét, majd ebből az eloszlást!

Megoldás: Kiindulva a

egyenletekből tényezővel megszorozva majd az egyenleteket összeadva kapjuk, hogy

Ebből

Mivel , ezért

Vagyis

ami éppen az paraméterű módosított geometriai eloszlás generátorfüggvénye, amit könnyű ellenőrizni, hiszen

esetén

<\sol>

Határozzuk meg most -t is!

Megoldás:

Nyilván

Ellenőrzésképpen

esetben határozzuk meg a és Laplace-transzformáltját!

Megoldás:

Könnyű látni, hogy

amit vártunk, hiszen paraméterű exponenciális eloszlást követ.

ami láthatóan nem más, mint

hiszen

Számolás útján is megmutatható, hogy

Ebből és ellenőrzésképpen kiszámítható.

így

amit korábban is kaptunk.

Mutassuk meg, hogy egy -rendszer esetén

Megoldás: Közismert, hogy esetén

Mivel ezért elegendő megmutatni, hogy

Ezt a L'Hospital-szabály alkalmazásával bizonyítjuk be.

Mutassuk meg, hogy egy -rendszer esetén az

Laplace-transzformáltra igaz, hogy !

Megoldás:

rendszer esetén a Laplace-transzformált segítségével határozzuk meg a -t!

Megoldás:

képletből kiindulva

vagyis

amit korábban kaptunk. Hosszadalmasabb számolással a magasabb momentumok is megadhatók.

Tekintsünk egy csomópontból álló zárt sorbanállási hálózatot, amelyben igény tartózkodik! Tegyük fel, hogy mindkét helyben a kiszolgálási idők illetve paraméterű exponenciális eloszlású valószínűségi változók. Határozzuk meg mindkét helyben a rendszer jellemzőit!

Megoldás: Könnyű észrevenni, hogy a két csomópont teljesen hasonlóan működik és tekinthető típusú sorbanállási rendszernek. Ennek megfelelően számíthatók ki a rendszerjellemzők illetve paraméterekkel. Az is látható, hogy

ahol , a csomópont kiszolgáló egységének a kihasználtsága.

esetén határozzuk meg a generátorfüggvényt!

Megoldás:

Ellenőrzésképpen számítsuk ki ! , ezért

Így

amit már megmutattunk.

Határozzuk meg az rendszernél -t!

Megoldás:

miatt először az -t számítjuk ki.

Mivel , ezért

Mutassuk meg, hogy mindig monoton csökkenő sorozat és határértéke 0!

Megoldás:

ezért növekedésével -hoz tart. A monoton csökkenés azzal ekvivalens, hogy

vagyis

ami automatikusan teljesül, ha . Ugyanakkor miatt , melyből , , vagyis adódik. Ez együtt az jelenti, hogy monoton csökkenő sorozat, ami várható volt, hiszen ha a kiszolgálók számát növeljük, akkor az igényvesztés valószínűségének csökkeni kell.

Keressünk a -formulára rekurziót!

Megoldás: Legyen , ekkor a

segítségével -ra rekurziót tudunk felírni, hiszen -ra is van. Ezért az eljárás az lesz, hogy megmutatjuk, hogy hogyan fejezhető ki segítségével, majd a

rekurzióba behelyettesítve kapjuk meg a kívánt formulát. Fejezzük ki először -t segítségével, vagyis

ami pozitív mert az rendszer stabilitása miatt, és azt mutatja, hogy

ami várható volt a probléma jellegéből adódóan. Ezért

és kell, hogy legyen! Először -t kifejezzük segítségével, majd elvégezzük a behelyettesítést. Ezért

Ide behelyettesítjük a -t. Írjuk fel egyszerűbben a számlálót és a nevezőt.

Ezért

és kezdőértékből kiindulva a várakozás valószínűségét rekurzive meghatározhatjuk. Ez azért fontos, mert a rendszerjellemzők ettől a mennyiségtől függnek. Látható, hogy

ezért megmutatjuk, hogy

melyből

ami várható volt.

vagyis ha akkor a parabola értékei pozitívak, ami teljesül hiszen a stabilitás feltétele volt. Könnyű látni, hogy a

összefüggésből , ami várható volt. Ezt közvetlenül a

képletből is láthatjuk, hiszen

ami szintén várható volt, hiszen a végtelen kiszolgálós rendszerekben nincs igényvesztés.

Ellenőrizzük, hogy az -rendszerre kapott eloszlásfüggvény az esetben az esetben megismert összefüggést adja!

Megoldás:

Így

Mutassuk meg, hogy az rendszer esetén !

Megoldás:

ezért alkalmazzuk a L'Hospital szabályt. Könnyű látni, hogy

és ebből

Mutassuk meg, hogyha egy -rendszer esetében a hátramaradt kiszolgálási időt jelöli, akkor !

Megoldás:

Parciális integrálással

Ellenőrizzük a határértéket! Látható, hogy

ezért L'Hospital-szabályt alkalmazunk. Így

Az segítségével mutassuk meg, hogy ha , akkor !

Megoldás:

így .

Az -re vonatkozó formulákból rendszerre származtassuk a megfelelő formulákat!

Megoldás:

Ebben az esetben

ezért a tartózkodási idő Laplace-transzformáltja

vagyis , mint láttuk.

A rendszerben tartózkodó igények generátorfüggvénye

mint láttuk az esetben.

Az átlagos várakozási és tartózkodási idők

Most vizsgáljuk meg a szórásnégyzeteket!

így

mint láttuk. Továbbá

mint láttuk korábban.

Végül

Ezekre az ellenőrzésekre azért van szükség, hogy kiderüljön egyszerű esetekben a bonyolult formulák egyszerű eredményt adnak-e.

A

transzformált egyenlet alapján határozzuk meg -t!

Megoldás: Jól ismert, hogy , ezért ki kell számolnunk a jobb oldal deriváltját, amiben az tényező helyen határozatlan értéket ad, ezért alkalmazni fogjuk a L'Hospital-szabályt. Vezessük be az

függvényt!

Így látható, hogy

Az

sorfejtést felhasználva, vegyük észre, hogy

Így és .

Ezek után

és ebből

amit más úton már megkaptunk.

Az segítségével határozzuk meg -t!

Megoldás: Legyen

ami sorba fejtve tovább egyenlő

Ezért

Ebből

Ezek után látható, hogy

miatt

Ebből

hasonlóan

Ebből

Ezek után

A Laplace-transzformált segítségével mutassuk meg, hogy

Megoldás: Mint már láttuk

és az is közismert, hogy

Hasonlóan -re, kapjuk

Ezért

Ebből

Határozzuk meg egy kiszolgálási idő alatt érkező igények számának az eloszlását esetén!

Megoldás: A teljes valószínűség tétele alapján

Generátorfüggvénye

14. fejezet - Véges-forrású rendszerek

Ha és , akkor bizonyítjuk be a következő fontos összefüggést!

Megoldás: Jól ismert, hogy

ezért

ahol az intergálásnál a helyettesítést vettük.

A Laplace-transzformált segítségével az rendszernél határozzuk meg a tartózkodási idő várható értékét!

Megoldás: Jól ismert, hogy , ezért kiszámíthatjuk -t.

Így

ebből

Mivel

így ugyanazt az eredményt kaptuk. A magasabb momentumait is ki tudjuk számítani és további jellemzők adhatók meg. Analóg módon momentumai is meghatározhatók.

A sűrűségfüggvény segítségével az rendszernél határozzuk meg a tartózkodási idő várható értékét, vagyis -t!

Megoldás:

Teljesen hasonló módon határozható meg a várakozási idő átlaga, csak az a különbség, hogy a fellépő Erlang eloszlásnál 1-el kisebb fázist veszünk és az összegzés 1-től indul.

Határozzuk meg az rendszernél a -t!

Megoldás: Jelöljük -el a forrásban tartózkodó igények számát. Így , ezért . Tudjuk azonban, hogy eloszlása a forgalmi intenzitású rendszer eloszlásával egyezik meg. Ezért az ott kapott képlet alapján

Ha a forrásszámot is jelölni szeretnénk, akkor

Ez lehetőséget ad arra, hogy meghatározzuk -t és -t. Mivel tekinthető egy véletlen tagszámú összegnek, ahol az összeadandók a paraméterű exponenciális eloszlású kiszolgálási idők, a számláló folyamat pedig az érkezési pillanatban a rendszerben tartózkodó igények száma, melyet -nel jelölünk, ezért

ahol

Hasonló módon, mivel , így

15. fejezet - Függelék

A függelékben a generátorfüggvény (melyet néha z-transzformáltnak is nevezünk) és a Laplace-transzformált néhány olyan tulajdonságát és rájuk vonatkozó azonosságokat tekintünk át, melyeket a jegyzetbeli levezetések folyamán — és általában a sorbanállási elméletben — használni lehet. Ezen két transzformált alakja és tulajdonságai igen hasonlóak.

15.1. ábra - A generátorfüggvény néhány fontos tulajdonsága

A generátorfüggvény néhány fontos tulajdonsága

15.2. ábra - A Laplace-transzformált néhány fontos tulajdonsága

A Laplace-transzformált néhány fontos tulajdonsága

Irodalomjegyzék

[1] Adan, I. and Resing, J.. Queueing Theory, http://web2.uwindsor.ca/math/hlynka/qonline.html.

[2] Allen, Arnold O.. Probability, statistics, and queueing theory with computer science applications, 2nd ed.. Academic Press, Inc., Boston, MA. 1990.

[3] Anisimov, V. V. and Zakusilo, O. K. and Donchenko, V. S.. Elements of queueing theory and asymptotic analysis of system. Visha Skola, Kiev. 1987.

[4] Artalejo, J. and Gómez-Corral, A.. Retrial queueing syste. Springer, Berlin. 2008.

[5] Asztalos, D.. Véges forrású tömegkiszolgálási modellek alkalmazása számítógépes rendszerekre. Alkalmazott Matemaika Lapok. 1990. 89–101.

[6] Begain, Khalid and Bolch, Gunter and Herold, Helmutiley. Practical perfromance modeling, Application of the MOSEL language. Wiley & Sons., New York. 2001.

[7] Bolch, G. and Greiner, S. and de Meer, H. and Trivedi, K. S.. Queueing networks and Markov chains, 2nd ed. Wiley & Sons, New York. 2006.

[8] Bose, S. K.. An introduction to queueing systems. Kluwer Academic/Plenum Publishers, New York. 2002.

[9] Cee-Hock, N. and Boon-He, S.. Queueing modelling fundamentals, 2nd ed.. Wiley & Son, Chichester. 2002.

[10] Cooper, R. B. Introduction to Queueing Theory, 3-rd Edition. CEE Press, Washington. 1990, http://web2.uwindsor.ca/math/hlynka/qonline.html.

[11] Csige, L. and Tomkó, J.. A gépkiszolgálási probléma exponenciális eloszlások esetén. Alkalmazott Matematika Lapok. 1982. 107–124.

[12] Daigle, J. N.. Queueing theory with applications to packet telecommunication. Springer, New York. 2005.

[13] Daigle, J. N. Queueing theory for telecommunications. Addison-Wesley, Reading, MA. 1992.

[14] Dattatreya, G. R.. Performance analysis of queuing and computer networks. CRC Press, Boca Raton. 2008.

[15] Dshalalow, Jewgeni H.(ed.). Frontiers in queueing. CRC Press, Boca Raton. 1997.

[16] Falin, G. and Templeton, J. G.. Retrial queues. Chapman and Hall, London. 1997.

[17] Fazekas, István. Valószínűségszámítás. Kossuth Egyetemi Kiadó, Debrecen. 2000.

[18] Franken, P. and Konig, D. and Arndt, U. Schmidt, V.. Queues and point processes. Academie Verlag, Berlin. 1981.

[19] Gebali, F.. Analysis of computer and communication networks. Springer, New York. 2008.

[20] Gelenbe, E. and Mitrani, I.. Analysis and synthesis of computer systems. Academic Press, London. 1980.

[21] Gelenbe, E. and Pujolle, G.. Introduction to queueing networks. Wiley & Sons, Chichester. 1987.

[22] Gnedenko, B. V. and Belyayev, Y. K. and Solovyev, A. D.. Mathematical methods of reliability theory. Academic Press, New York, London. 1969.

[23] Gnedenko, B. V. and Kovalenko, I. N.. Introduction to queueing theory. Birkhäuser, Boston, MA. 1991.

[24] Gnyegyenko, B. V. and Beljajev, J. K. and Szolovjev, A. D.. A megbízhatóságelmélet matematikai módszerei. Műszaki Könyvkiadó, Budapest. 1970.

[25] Gross, D. and Shortle, J. F. and Thompson, J. M. and Harris, C. M.. Fundamentals of queueing theory, 4th edition. John Wiley & Sons, New York. 2008.

[26] Györfi, L. and Páli, I.. Tömegkiszolgálás informatikai rendszerekben. Műegyetemi Kiadó, Budapest. 1996.

[27] Haghighi, A. M. and Mishev, D. P.. Queueing models in industry and business. Nova Science Publishers, Inc., New York. (2008).

[28] Hall, Randolph W.. Queueing methods for services and manufacturing. Prentice Hall, Englewood Cliffs, NJ. 1991.

[29] Haribaskaran, G.. Probability, queueing theory and reliability engineering. Laxmi Publications, Bangalore. 2006.

[30] Haverkort, Boudewijn. Performance of computer communication systems, A model-based approach. Wiley & Sons, New York. 1998.

[31] Hlynka, M.. Queueing Theory Page. http://web2.uwindsor.ca/math/hlynka/queue.html.

[32] van Hoorn, M. H.. Algorithms and approximations for queueing systems. Centrum voor Wiskunde en Informatica, Amsterdam. 1984.

[33] Ivcsenko, G. I. and Kastanov, V. A and Kovalenko, I. N.. Theory of queueing systems. Nauka, Moscow. 1982.

[34] Jain, R.. The art of computer systems performance analysis. Wiley & Sons, New York. 1991.

[35] Jaiswal, N.K.. Priority queues. Academic Press, New York. 1969.

[36] Jereb, L. and Telek, M.. Sorbanállásos rendszerek. Oktatási segédlet, BME Híradástechnikai Tanszék, http://webspn.hit.bme.hu/~telek/notes/sokfelh.pdf.

[37] Karlin, S. and Taylor, H. M.. Sztochasztikus folyamatok. Gondolat Kiadó, Budapest. 1985.

[38] KaKhintchine, A. Y.. Mathematical methods in the theory of queueing. Hafner, New York. 1969.

[39] Kleinrock, Leonard. Queueing systems. Vol. II: Computer applications.. John Wiley & Sons, New York. 1976.

[40] Kleinrock, Leonard. Queueing systems. Vol. I: Theory. John Wiley & Sons, New York. 1975.

[41] leinrock, L.. Sorbanállás, kiszolgálás: Bevezetés a tömegkiszolgálási rendszerek elméletébe. Műszaki Kiadó, Budapest. 1975.

[42] Kobayashi, H.. Modeling and Analysis: An Introduction to System Performance Evaluation Methodology. Addison-Wesley, Reading, MA. 1978.

[43] Kobayashi, H. and Mark, B. L.. System modeling and analysis: Foundations of system performance evaluation. Pearson Education Inc., Upper Sadle River. 2008.

[44] Korolyuk, V. S. and Korolyuk, V. V.. Stochastic models of systems. Kluwer Academic Publishers, Dordrecht, London. 1999.

[45] Kovalenko, I. N. and Pegg, P. A. and Kuznetzov, N. Yu.. Mathematical theory of reliability of time dependent systems with practical applications. Wiley & Sons, New York. 1997.

[46] Kulkarni, V.. Modeling, analysis, design, and control of stochastic systems. Springer, New York. 1999.

[47] Lakatos, L. and Szeidl, L. and Telek, M.. Informatikai algoritmusok II. ELTE Eötvös Kiadó. 2005. 1298–1347.

[48] Lavenberg, S.(Ed.. Computer performance modeling handbook. Academic Press, New York. 1983.

[49] Mieghem, P. V.. Performance analysis of communications networks and systems. Cambridge University Press, Cambridge. 2006.

[50] Nelson, Randolph.. Probability, stochastic processes, and queueing theory, The mathematics of computer performance modeling. Springer-Verlag, New York. 1995.

[51] Ovcharov, L. and Wentzel, E.. Applied Problems in Probability Theory. Mir Publishers, Moscow, New York. 1986.

[52] Prékopa, András. Valószínűségelmélet, Műszaki Könyvkiadó, Budapest. 1962.

[53] Pósafalvi, A. and Sztrik, J.. A Numerical Approach to the Repairman Problem with Two Different Types of Machines, Journal of Operational Reseach Society. 40. 1989. 797–803.

[54] Pósafalvi, A. and Sztrik, J.. On the Heterogeneous Machine Interference with Limited Server's Availability, European Journal of Operational Research. 28. 1987. 321–328.

[55] Ravichandran, N.. Stochastic Methods in Reliability Theory. John Wiley and Sons, New York. 1990.

[56] Reimann, J.. Valószínűségelmélet és matematikai statisztika mérnököknek. Tankönyvkiadó, Budapest. 1992.

[57] Rényi, Alfréd. Valószínűségszámítás. Tankönyvkiadó, Budapest. 1973.

[58] Ross, S. M.. Introduction to Probability Models. Academic Press, Boston. 1989.

[59] Saaty, T. L.. Elements of queueing theory with applications, Dover Publications, Inc., New York. 1961.

[60] Sahner, R. and Trivedi, K. and Puliafito, A.. Performance and reliability analysis of computer systems – An example-based approach using the SHARPE software package. Kluwer Academic Publisher, Boston, M.A.. 1996.

[61] Sauer, C. H. and Chandy, K. M.. Computer systems performance modelling. Prentice Hall, Englewood Cliffs, N. J.. 1981.

[62] Stewart , W. J.. Introduction to the numerical solution of Markov chains. Princeton University Press, Princeton. 1995.

[63] Stewart , W. J.. Probability, Markov chains, queues, and simulation. Princeton University Press, Princeton. 2009.

[64] Sztrik, János. Informatikai rendszerek hatékonyságának elemzése. EKF Líceum Kiadó, Eger. 2007.

[65] Sztrik, János. Gyakorlati sorbanállási elmélet. Oktatási segédlet, Debreceni Egyetem, Informatikai Kar. 2005,http://irh.inf.unideb.hu/user/jsztrik/education/09/index.html.

[66] Sztrik, J.. Kulcs a sorbanállási elmélethez és alkalmazásaihoz. Kossuth Egyetemi Kiadó, Debrecen. 2004,http://irh.inf.unideb.hu/user/jsztrik/education/eNotes.htm.

[67] Sztrik, J.. Bevezetés a sorbanállási elméletbe és alkalmazásaiba. 2000, http://irh.inf.unideb.hu/user/jsztrik/education/eNotes.htm.

[68] Sztrik, J.. On the Machine Interference Model with State-Dependent Speeds. Journal of Operational Researc Society. 39. 1988. 201–201.

[69] Sztrik, J.. Some Contribution to the Machine Interference Problem with Heterogeneous Machines. Journal of Information Processing and Cybernetics. 24. 1988. 137–143.

[70] Sztrik, J.. On the finite-source queues. European Journal of Operational Research. 20. 1985. 261–268.

[71] Takagi, Hideaki. Queueing analysis. A foundation of performance evaluation. Volume 2. Finite Systems, North-Holland, Amsterdam. 1993.

[72] Takagi, Hideaki. Queueing analysis. A foundation of performance evaluation. Volume 3. Discrete-Time Systems, North-Holland, Amsterdam. 1993.

[73] Takagi, Hideaki. Queueing analysis. A foundation of performance evaluation. Volume 1. Vacation and priority systems, part 1., North-Holland, Amsterdam. 1991.

[74] Takács, L.. Introduction to the theory of queues. Oxford University Press, New York. 1962.

[75] Tijms, H. C.. A first course in stochastic models. Wiley & Son, Chichester. 2003.

[76] Tijms, H. C.. Stochastic Modelling and Analysis: A Computational Approach. Wiley & Sons, New York. 1986.

[77] Tomkó, J.. Tartózkodási időproblémák Markov-láncokra. Alkalmazott Matematikai Lapok. 1982. 91–106.

[78] Trivedi, K. S.. Probability and Statistics with Reliability, Queuing, and Computer Science Applications, 2-nd edition. Wiley & Son, New York. 2002.

[79] Ushakov, Igor A.(Ed.) and Harrison, Robert A.(Ed.). Handbook of reliability engineering. Transl. from the Russian. Updated ed.. Wiley & Sons, New York, NY. 1994.

[81] Wentzel, E. and Ovcharov, L.. Applied problems in probabbility theory. Mir Publisher, Moscow. 1986.

[82] Yashkov, S. F.. Processor-sharing queues, some progress in analysis, Queueing Systems, Theory and Applications. 2. 1987. 1–17.