Poissonov dátový tok klasickej a. Stacionárny Poissonov tok zlyhania. Distribúcia udalostí v Poissonovom toku

V praxi sa najčastejšie obmedzujú na zváženie najjednoduchšieho (Poissonovho) toku aplikácií.

Definícia. Prúd udalostí, ktorý má vlastnosti obyčajnosť, stacionárnosť a nedostatok následných efektov, volal najjednoduchšie ( alebo stacionárny Poissonov tok. Pre najjednoduchší prúd udalostí má pravdepodobnosť, že v časovom intervale dĺžky t nastane presne k udalostí, Poissonovo rozdelenie a je určená vzorcom:

Р(X(t,t) = k) = a k e -a /k! (k=0, 1, 2,...),

Kde a = lt, l – intenzita prúdenia.

Fyzikálny význam intenzity toku udalostí je priemerný počet udalostí za jednotku času (počet aplikácií za jednotku času), dimenzia je 1/čas.

Tento tok sa nazýva najjednoduchší, pretože štúdium systémov pod vplyvom najjednoduchších tokov sa vykonáva najjednoduchším spôsobom.

Rozdelenie intervalov medzi požiadavkami na najjednoduchší tok bude exponenciálne (exponenciálne) s distribučnou funkciou a hustotou , kde je intenzita príjmu požiadaviek do QS.

Uvažujme o základných vlastnostiach najjednoduchšieho toku:

Stacionarita;

Obyčajnosť;

Žiadny následný efekt.

Stacionárnosť. Vlastnosť stacionárnosti sa prejavuje v tom, že pravdepodobnosť určitého počtu udalostí, ktoré sa vyskytnú v určitom časovom období, závisí len od dĺžka úseku A nezávisí od jeho umiestnenia na osi . Inými slovami, stacionárnosť znamená nemennosť pravdepodobnostného režimu toku udalostí v čase. Prúd, ktorý má vlastnosť stacionárnosti, sa nazýva stacionárne. Pri stacionárnom toku zostáva priemerný počet udalostí ovplyvňujúcich systém za jednotku času konštantný. Reálne toky udalostí v ekonomike podniku sú v skutočnosti stacionárne iba počas obmedzených časových období.

Obyčajnosť. Vlastnosť bežného toku je prítomná, ak je pravdepodobnosť dvoch alebo viacerých udalostí vyskytujúcich sa v elementárnom časovom segmente zanedbateľná v porovnaní s dĺžkou tohto segmentu. Vlastnosť obyčajnosti znamená, že v krátkom časovom období je prakticky nemožné, aby došlo k viacerým udalostiam. Prúd, ktorý má vlastnosť byť obyčajný, sa nazýva obyčajný. Reálne toky udalostí v rôznych ekonomické systémy buď sú obyčajné, alebo sa dajú celkom jednoducho zredukovať na obyčajné.

Žiadny následný efekt. Táto vlastnosť toku spočíva v tom, že pre akékoľvek neprekrývajúce sa časové segmenty počet udalostí, ktoré spadajú do jedného z nich, nezávisí od toho, koľko udalostí spadá do iných časových segmentov. Nazýva sa tok, ktorý nemá vlastnosť žiadneho následného účinku tok bez následných efektov.

Nazýva sa tok udalostí, ktorý má súčasne vlastnosti stacionárnosti, obyčajnosti a nedostatku následkov najjednoduchší tok udalostí.

2.6. Komponenty a klasifikácia

modely systémov radenia (QS)

Prvými problémami teórie čakacích systémov (TSMS) sa zaoberali pracovníci Copenhagen Telephone Company, dánsky vedec A. K. Erlang (1878–1929) v rokoch 1908 až 1922. Tieto úlohy priviedla k životu túžba zefektívniť prevádzku telefónnej siete a vyvinúť metódy, ktoré by umožnili proaktívne skvalitňovať služby zákazníkom v závislosti od počtu používaných zariadení. Ukázalo sa, že situácie, ktoré vznikajú na telefónnych ústredniach, sú typické nielen pre telefonickú komunikáciu. V rámci TSMO možno opísať prácu letísk, prácu námorných a riečnych prístavov, obchodov, terminálových tried, radarových komplexov, radarových staníc atď., atď.

Systémy radenia– ide o systémy, ktoré prijímajú požiadavky na službu v náhodných časoch a prijaté požiadavky sú obsluhované pomocou servisných kanálov, ktoré má systém k dispozícii.

Z hľadiska modelovania procesu zaraďovania do front vznikajú situácie, kedy sa tvoria fronty aplikácií (požiadavky) na obsluhu. nasledujúcim spôsobom. Po príchode do obslužného systému sa požiadavka zaradí do frontu iných (predtým prijatých) požiadaviek. Servisný kanál vyberie požiadavku z tých, ktoré sú vo fronte, aby ju začal obsluhovať. Po dokončení procedúry na obsluhu ďalšej požiadavky začne obslužný kanál obsluhovať ďalšiu požiadavku, ak je v čakacom bloku jedna.

Prevádzkový cyklus systému radenia tohto druhu sa mnohokrát opakuje počas celej doby prevádzky servisného systému. Predpokladá sa, že prechod systému na obsluhu ďalšej požiadavky po dokončení obsluhy predchádzajúcej požiadavky nastane okamžite, v náhodných časoch.

Príklady systémov radenia zahŕňajú príspevky Údržba autá; akýkoľvek podnik poskytujúci služby; osobné počítače obsluhujúce prichádzajúce aplikácie alebo požiadavky na riešenie určitých problémov; audítorské firmy; oddelenia daňové inšpekcie tí, ktorí sa podieľajú na prijímaní a overovaní aktuálnych výkazov podnikov; telefónne ústredne a pod.

Reálne systémy, ktorým sa v praxi venujeme, sú väčšinou veľmi zložité a zahŕňajú množstvo krokov údržby (etáp). Okrem toho v každom štádiu môže existovať možnosť nesplnenia alebo môže nastať situácia prioritnej služby vo vzťahu k iným požiadavkám. V tomto prípade môžu jednotlivé servisné jednotky prestať fungovať (kvôli opravám, úpravám atď.) alebo môžu byť spojené dodatočné finančné prostriedky. Môžu nastať okolnosti, kedy sa zamietnuté požiadavky vrátia do systému (to sa môže stať v informačných systémoch).

Hlavné komponenty systému radenia akéhokoľvek typu sú:

Vstupný tok prichádzajúcich požiadaviek alebo žiadostí o službu;

Disciplína vo fronte;

Servisný mechanizmus.

Vstupné požiadavky Stream. Pre popis vstupného toku je potrebné špecifikovať pravdepodobnostný zákon, ktorý určuje postupnosť momentov prijatia žiadostí o službu a uvádzať počet takýchto žiadostí pri každom nasledujúcom príchode. V tomto prípade spravidla pracujú s pojmom „pravdepodobné rozloženie momentov prijatia požiadaviek“. Tu je možné prijímať individuálne aj skupinové požiadavky (požiadavky sa do systému prijímajú v skupinách). V druhom prípade zvyčajne hovoríme o systéme radenia so servisom v paralelných skupinách.

Disciplína v rade- ide o dôležitý komponent systému radenia, určuje princíp, podľa ktorého sa požiadavky prichádzajúce na vstup obslužného systému spájajú z radu do obslužnej procedúry. Najčastejšie používané disciplíny fronty sú definované nasledujúcimi pravidlami:

– kto prv príde, ten prv melie (FIFO);

– posledný príde, ten prv melie (LIFO);

– náhodný výber aplikácií (RANDOM);

– výber žiadostí podľa prioritného kritéria (PR);

– obmedzenie čakacej doby na obsluhu (existuje rad s obmedzenou dobou čakania na obsluhu alebo počet miest, čo súvisí s pojmom „prípustná dĺžka radu“).

Je potrebné poznamenať, že čas na servis aplikácie závisí od charakteru samotnej aplikácie alebo požiadaviek klienta a od stavu a možností servisného systému. V niektorých prípadoch je potrebné brať do úvahy aj pravdepodobnosť odchodu obslužného zariadenia po určitom obmedzenom časovom intervale.

Štruktúra obslužného systému je určená počtom a relatívnou polohou obslužných kanálov (mechanizmy, zariadenia atď.). Servisný systém môže mať viac ako jeden obslužný kanál, ale niekoľko - systém tohto druhu je schopný obsluhovať niekoľko požiadaviek súčasne. V tomto prípade, ak všetky servisné kanály ponúkajú rovnaké služby, možno tvrdiť, že existuje paralelná služba - viackanálový systém.

Servisný systém môže pozostávať z niekoľkých rôznych typov obslužných kanálov, cez ktoré musí prejsť každá obsluhovaná požiadavka, t.j. v obslužnom systéme sú postupy obsluhy požiadaviek implementované postupne.

Po zvážení hlavných komponentov servisných systémov možno tvrdiť, že funkčnosť každý systém radenia je určený nasledujúcimi hlavnými faktormi:

Pravdepodobné rozdelenie momentov prijatia žiadostí o službu (jednotlivé alebo skupinové);

Pravdepodobné rozdelenie času trvania služby;

Konfigurácia obslužného systému (paralelná, sériová alebo paralelná sériová údržba);

Počet a výkonnosť obslužných kanálov;

Disciplína vo fronte;

Požiadavka na napájanie zdroja.

Na systémoch s obmedzené očakávanie Dĺžka frontu a čas strávený vo fronte môžu byť obmedzené.

V systémoch s neobmedzeným čakaním čaká aplikácia stojaca vo fronte na obsluhu neobmedzený čas, t. j. kým príde rad.

Daná klasifikácia QS je podmienená. V praxi systémy radenia najčastejšie fungujú ako zmiešané systémy. Napríklad požiadavky čakajú na spustenie služby do určitého bodu, po ktorom systém začne fungovať ako systém s poruchami.

Predmet teórie radenia je vytvoriť vzťah medzi faktormi, ktoré určujú funkčnosť systému radenia a efektívnosť jeho prevádzky. Vo väčšine prípadov sú všetky parametre popisujúce systémy radenia náhodné premenné alebo funkcie, preto tieto systémy patria medzi stochastické systémy.

Ako hlavné kritériá účinnosti systémov radenia V závislosti od povahy riešeného problému sa môže objaviť nasledovné:

Pravdepodobnosť okamžitého servisu prichádzajúcej aplikácie;

Pravdepodobnosť odmietnutia obsluhy prichádzajúcej aplikácie;

Relatívne a absolútne priepustnosť systémy;

Priemerné percento aplikácií, ktorým bola odmietnutá služba;

Priemerná doba čakania vo fronte;

Priemerná dĺžka frontu;

Priemerný príjem z prevádzky systému za jednotku času.

Náhodná povaha toku požiadaviek a trvanie služby vedie k tomu, že v systéme radenia sa vyskytuje náhodný proces. Na základe povahy náhodného procesu vyskytujúceho sa v systéme radenia (QS) sa rozlišuje medzi Markovom a nemarkovom. Bez ohľadu na povahu procesu, ktorý sa vyskytuje v systéme radenia, existujú dva hlavné typy QS:

· systémy s poruchami, v ktorých je aplikácia vstupujúca do systému v čase, keď sú všetky kanály obsadené, odmietnutá a opúšťa frontu;

· systémy s čakaním (zoraďovaním), v ktorých sa požiadavka, ktorá príde v čase, keď sú všetky obslužné kanály obsadené, zaradí do radu a čaká, kým sa jeden z kanálov neuvoľní.

Na označenie typu QS sa používajú všeobecne akceptované zápisy Kendall-Bash: X/Y/Z/m,

Kde X - druh zákona o rozdelení intervalov prijímania žiadostí;
Y – druh zákona o distribúcii na obsluhu požiadaviek;
Z – počet kanálov;

m – počet miest v rade.

V označení druhu distribučného zákona sa uvádza písm M zodpovedá exponenciálnemu rozdeleniu (od slov Markovian), list E– distribúcia Erlang, R– rovnomerné rozloženie a D– deterministická hodnota.

Napríklad záznam M/M/1 znamená jednokanálový systém s exponenciálnym rozložením času prijatia a obsluhy požiadaviek ( M– Markovskaya) bez frontu.

2.7. Výpočet hlavných charakteristík QS

na základe použitia ich analytických modelov

Uvažujme také systémy QS, v ktorých možné stavy systému tvoria reťazec a každý stav, okrem počiatočného a posledného, ​​je spojený priamkou a spätná väzba s dvoma susednými štátmi. Tento diagram procesu prebiehajúceho v systéme sa nazýva schéma „smrť a reprodukcia“. Termín pochádza z biologických problémov, proces popisuje zmeny veľkosti populácie.

Ak v takomto systéme sú všetky toky, ktoré prenášajú systém zo stavu do stavu, Poisson, potom sa volá proces Markovian náhodný proces„smrť a rozmnožovanie“.

Všimnite si, že v takýchto systémoch sú všetky stavy nevyhnutné, čo znamená, že existujú konečné pravdepodobnostištátov, z ktorých možno nájsť lineárny systém Erlangove rovnice.

V praxi možno významnú časť systémov (SMS) popísať v rámci procesu „smrť a rozmnožovanie“.

Pozrime sa na niektoré typy takýchto systémov:

a) jednokanálový s poruchami (žiadny rad);

b) jednokanálový s obmedzeným radom;

c) viackanálový s poruchami (žiadny rad);

d) viackanálový s obmedzeným radom.

Medzi prúdmi udalostí má osobitné miesto takzvaný „Poissonov prúd“, ktorý má oproti iným množstvo vlastností, ktoré výrazne uľahčujú riešenie problémov.

Poissonov tok udalostí sa nazýva tok, ktorý má dve vlastnosti – obyčajnosť a absenciu následkov.

Prúd sa volá tok bez následných efektov, ak pre ktorékoľvek dva neprekrývajúce sa úseky t 1 a t 2 počet udalostí pripadajúcich na jeden z nich nezávisí od toho, koľko udalostí pripadá na druhý.

Náhodný počet udalostí, ktoré nastali v časovom intervale t 1 sme označili X 1 a na intervale t2, cez X 12. Pre tok bez následného efektu, náhodné premenné X 1 a X 2 sú nezávislé, t.j. pravdepodobnosť, že na úseku t 2 bola určitý počet diania m 2 nezávisí od počtu udalostí m 1 došlo na úseku t 1.

P(X 2 =m 2 ½ X 1 =m 1) = P(X 2 =m).

(m 1 =0, 1, 2,…)

(m 2 =0, 1, 2,…). (2.47)

Z teórie pravdepodobnosti je známe, že pre Poissonov tok je počet udalostí X 1 pripadajúce na ľubovoľný interval dĺžky t susediaci s bodom t, rozdelené podľa Poissonovho zákona (obr. 2.5.):

Kde ( a×(t× t)) m– priemerný počet udalostí vyskytujúcich sa v časovom intervale t susediacom s časovým okamihom t. Preto sa tok nazýva „Poisson“.

Priemerný počet udalostí pre obyčajný prietok sa rovná intenzite prietoku l( t). Preto je priemerný počet udalostí vyskytujúcich sa v časovom intervale t susediacim s časovým bodom t sa bude rovnať:

Ak je Poissonov tok udalostí stacionárny, potom množstvo A nebude závisieť od t:

V tomto prípade pravdepodobnosť, že v ľubovoľne zvolenom časovom úseku trvania t nastane m udalosti sa určujú podľa vzorca:

Stacionárny tok sa často nazýva najjednoduchší tok, pretože použitie najjednoduchších tokov pri analýze rôznych systémov radenia vedie k najjednoduchším riešeniam. Nájdite zákon rozdelenia časového intervalu medzi dvoma udalosťami v najjednoduchšom toku (obr. 2.6.):

Pravdepodobnosť, že v oblasti t, po jednej udalosti nebude viac ako jedna udalosť:

Ale táto pravdepodobnosť sa rovná pravdepodobnosti náhodných premenných T bude väčšia ako hodnota t. teda

F(t)=P(T<1)=1 - p×( T>t)=1 - e - l t , t>0. (2.54)

Kde F(t) – distribučná funkcia náhodnej premennej T.

Diferencovaním tohto výrazu získame hustotu distribúcie náhodnej premennej T:

f( t)=l e - l t , (t>0). (2.55)

V najjednoduchšom toku sú teda intervaly medzi dvoma susednými udalosťami rozdelené podľa dôkazného zákona s parametrom l.

Kvôli absencii následného efektu sú všetky intervaly medzi susednými udalosťami nezávislými náhodnými premennými. Preto je najjednoduchším tokom stacionárny tok Palm.

Očakávanie a rozptyl náhodnej premennej T-Časové intervaly medzi dvoma udalosťami v najjednoduchšom toku sa rovnajú:

teda

Pravidelný stream podujatí:

Kde T* oblasť, kde náhodná udalosť dopadne.

Pravidelný tok predstavuje sled udalostí oddelených striktne rovnakými intervalmi.

Hustota distribúcie intervalu medzi akýmikoľvek udalosťami môže byť prezentovaná ako:

f(t)=d( t-m t), (2.59)

kde d( t) je dobre známa delta funkcia.

Pretože interval medzi susednými bodmi je striktne konštantný a rovnaký m t, potom je to jasné očakávaná hodnota tento interval sa rovná m t, A D t= 0.

Nájdite zákon rozdelenia času Q od náhodného bodu po začiatok nasledujúcej udalosti:

Charakteristická funkcia intervalu medzi susednými udalosťami v pravidelnom toku bude mať tvar:

g(X)= e - imt x. (2.61)

Pravidelný tok udalostí sa pri riešení aplikovaných problémov používa pomerne zriedka. Vysvetľuje to skutočnosť, že takýto prúd udalostí má veľmi veľký (neobmedzený) následný účinok, pretože pri poznaní iba jedného okamihu výskytu udalostí v pravidelnom prúde je možné obnoviť celú minulosť tohto prúdu a predpovedať budúcnosť.

Hlavnou úlohou TSMO je stanoviť vzťah medzi charakterom toku požiadaviek na vstupe systému radenia, výkonom jedného kanála, počtom kanálov a efektívnosťou služby.

Ako kritériá účinnosti možno použiť rôzne funkcie a veličiny:

• priemerné prestoje systému;
• priemerná doba čakania v rade;
• zákon o rozdelení čakacej doby na žiadosť v rade;
• priemerné % zamietnutých žiadostí; atď.

Výber kritéria závisí od typu systému. Napríklad, pre systémy s poruchami hlavnou charakteristikou je absolútna priepustnosť QS; menej dôležité kritériá- počet obsadených kanálov, priemerné relatívne prestoje jedného kanála a systému ako celku. Pre bezstratové systémy(s neobmedzeným čakaním) najdôležitejšie sú priemerný čas nečinnosti vo fronte, priemerný počet požiadaviek vo fronte, priemerný čas strávený požiadavkami v systéme, faktor nečinnosti a faktor zaťaženia obsluhujúceho systému.

Moderné TSMO je súbor analytických metód na štúdium uvedených odrôd QMS. V budúcnosti budú zo všetkých pomerne zložitých a zaujímavých metód na riešenie problémov s radením načrtnuté metódy opísané v triede Markovove procesy typu „smrť a rozmnožovanie“. Vysvetľuje to skutočnosť, že ide o metódy najčastejšie používané v praxi inžinierskych výpočtov.

2. Matematické modely tokov udalostí.

2.1. Pravidelné a náhodné toky.

Jednou z ústredných otázok organizácie QS je objasnenie vzorov, ktoré riadia okamihy, keď do systému vstupujú požiadavky na službu. Zoberme si najbežnejšie používané matematické modely vstupných tokov.

Definícia: Tok požiadaviek sa nazýva homogénny, ak spĺňa tieto podmienky:

1. všetky požiadavky na tok sú z hľadiska služby rovnaké;

namiesto požiadaviek toku (udalostí), ktoré môžu byť svojou povahou odlišné, len kým prídu.

Definícia: Tok sa nazýva pravidelný, ak udalosti v toku nasledujú po sebe v prísnych časových intervaloch.

Funkcia f (x) hustota rozdelenia pravdepodobnosti náhodnej premennej T - časový interval medzi udalosťami má tvar:

Kde - delta funkcia, Mt - matematické očakávanie a Mt = T, rozptyl Dt = 0 a intenzitu dejov vyskytujúcich sa v toku = 1/Mt = 1/T.

Definícia: Prúd sa nazýva náhodný, ak sa jeho udalosti vyskytujú v náhodných časoch.

Náhodný tok možno opísať ako náhodný vektor, ktorý, ako je známe, môže byť jednoznačne špecifikovaný distribučným zákonom dvoma spôsobmi:

Kde, zi- hodnoty Ti(i=1,n),V tomto prípade možno momenty výskytu udalostí vypočítať nasledovne

ti = to +z1

t2 = ti + z2

………,

2.2. Najjednoduchší Poissonov tok.

Na vyriešenie veľkého množstva aplikovaných problémov často stačí použiť matematické modely homogénnych tokov, ktoré spĺňajú požiadavky stacionárnosti, bez následkov a obyčajnosti.

Definícia: Tok sa nazýva stacionárny, ak pravdepodobnosť výskytu je nudalosti na časovom intervale (t,t+T) závisí od jeho polohy na časovej osi t.

Definícia: Tok udalostí sa nazýva obyčajný, ak je pravdepodobnosť výskytu dvoch alebo viacerých udalostí počas elementárneho časového intervalu D tje veličina nekonečne malá v porovnaní s pravdepodobnosťou výskytu jednej udalosti v tomto intervale, t.j. pri n=2,3,…

Definícia: Prúd udalostí je tzv plynúť bez následkov, ak pre žiadne neprekrývajúce sa časové intervaly počet udalostí pripadajúcich na jeden z nich nezávisí od počtu udalostí pripadajúcich na druhý.

Definícia: Ak tok spĺňa požiadavky stacionárnosti, obyčajnosti a bez následkov, je tzv najjednoduchší Poissonov tok.

Je dokázané, že pre najjednoduchší tok je číslo nudalosti spadajúce do ľubovoľného intervalu zrozdelené podľa Poissonovho zákona:

(1)

Pravdepodobnosť, že v časovom intervale z nenastane žiadna udalosť, je:

(2)

potom pravdepodobnosť opačnej udalosti:

kde podľa definície P(T toto je funkcia rozdelenia pravdepodobnosti T.Odtiaľto dostaneme, že náhodná premenná T je rozdelená podľa exponenciálneho zákona:

(3)

parameter sa nazýva hustota toku. navyše

2.3.1. Zadáme hodnotu a= X. V súlade s vlastnosťami Poissonovho rozdelenia atusiluje sa o normalitu. Preto pre veľké a, na výpočet P(X(a) je menšie alebo rovné n), kde X(a) je náhodná premenná distribuovaná podľa Poissona s očakávaním a, môžete použiť nasledujúcu približnú rovnosť:

Dôkaz: nech je T rozdelené podľa exponenciálneho zákona: Predpokladajme, že interval a už nejaký čas trvá a< T. Nájdite podmienený zákon rozdelenia zvyšnej časti intervalu T 1 = T-a

Odtiaľ,

je ekvivalentná udalosti a , pre ktoré P(a ; na druhej strane

P(T>a)=l-F(a), teda

V predchádzajúcich prednáškach sme sa naučili, ako simulovať výskyt náhodných udalostí. To znamená, že môžeme hrať ktoré dôjde k možným udalostiam a v ktorom množstvo. Aby ste to mohli určiť, potrebujete poznať štatistické charakteristiky výskytu udalostí, napríklad takouto hodnotou môže byť pravdepodobnosť výskytu udalosti alebo rozdelenie pravdepodobnosti rôznych udalostí, ak existuje nekonečne veľa typov týchto udalostí.

Často je však dôležité aj vedieť Kedy tá alebo ona udalosť konkrétne nastane v čase.

Keď je udalostí veľa a nadväzujú na seba, tvoria sa tok. Všimnite si, že udalosti musia byť homogénne, teda do istej miery si navzájom podobné. Napríklad objavenie sa vodičov na čerpacích staniciach, ktorí chcú natankovať svoje auto. To znamená, že homogénne udalosti tvoria určitý rad. V tomto prípade sa predpokladá, že štatistická charakteristika tohto javu (intenzita toku udalostí) je daná. Intenzita toku udalostí udáva koľko priemer takéto udalosti sa vyskytujú za jednotku času. Ale kedy presne nastane každá konkrétna udalosť, musí sa určiť pomocou metód modelovania. Dôležité je, že keď vygenerujeme napríklad 1000 udalostí za 200 hodín, ich počet sa bude približne rovnať priemernej intenzite výskytu udalostí 1000/200 = 5 udalostí za hodinu, čo je štatistická hodnota charakterizujúca tento tok ako celý.

Intenzita toku je v istom zmysle matematickým očakávaním počtu udalostí za jednotku času. Ale v skutočnosti sa môže ukázať, že v jednej hodine sa objavia 4 udalosti, v druhej 6, hoci v priemere je 5 udalostí za hodinu, takže jedna hodnota na charakterizáciu toku nestačí. Druhou veličinou, ktorá charakterizuje, aké veľké je rozšírenie udalostí v porovnaní s matematickým očakávaním, je rovnako ako predtým rozptyl. V skutočnosti je to táto hodnota, ktorá určuje náhodnosť výskytu udalosti, slabú predvídateľnosť okamihu jej výskytu. O tejto hodnote si povieme v ďalšej prednáške.

Prúd udalostí je sled homogénnych udalostí, ktoré sa vyskytujú jedna po druhej v náhodných intervaloch. Na časovej osi tieto udalosti vyzerajú ako na obr. 28.1.

Príkladom toku udalostí je sled okamihov, keď sa lietadlá prilietajúce na letisko dotknú pristávacej dráhy.

Intenzita prúdenia λ toto je priemerný počet udalostí za jednotku času. Intenzitu prúdenia je možné vypočítať experimentálne pomocou vzorca: λ = N/T n, Kde N počet udalostí, ktoré sa vyskytli počas pozorovania T n.

Ak je interval medzi udalosťami τ j rovná konštante alebo definovaná nejakým vzorcom v tvare: t j = f(t j 1), potom sa volá tok deterministický. Inak sa tok nazýva náhodný.

Existujú náhodné streamy:

• obyčajný: pravdepodobnosť súčasného výskytu dvoch alebo viacerých udalostí je nulová;
• stacionárne: frekvencia výskytu udalostí λ (t) = const( t) ;
• bez následného účinku: pravdepodobnosť výskytu náhodnej udalosti nezávisí od okamihu výskytu predchádzajúcich udalostí.

Poissonov tok

V modelovaní je zvykom brať Poissonov prúd ako štandard prúdenia..

Poissonov tok toto je obyčajný tok bez následných efektov.

Ako už bolo uvedené, pravdepodobnosť, že počas časového intervalu (t 0 , t 0 + τ ) stane sa m udalosti sa určujú z Poissonovho zákona:

Kde a Poissonov parameter.

Ak λ (t) = const( t) , teda stacionárny Poissonov tok(najjednoduchšie). V tomto prípade a = λ · t . Ak λ = var( t), tj nestabilný Poissonov tok.

Pre najjednoduchší tok pravdepodobnosť výskytu m udalosti počas τ rovná sa:

Pravdepodobnosť, že sa nevyskytne (t. j. žiadna, m= 0 ) udalosti v priebehu času τ rovná sa:

Ryža. 28.2 znázorňuje závislosť P 0 od času. Je zrejmé, že čím dlhší je čas pozorovania, tým je menšia pravdepodobnosť, že nenastane žiadna udalosť. Navyše, čím vyššia je hodnota λ , čím je graf strmší, teda tým rýchlejšie klesá pravdepodobnosť. To zodpovedá skutočnosti, že ak je intenzita výskytu udalostí vysoká, potom pravdepodobnosť, že udalosť nenastane, rýchlo klesá s časom pozorovania.

Pravdepodobnosť výskytu aspoň jednej udalosti ( PХБ1С) sa vypočíta takto:

pretože P HB1S+ P 0 = 1 (buď sa objaví aspoň jedna udalosť, alebo sa neobjaví žiadna, druhá nie je daná).

Z grafu na obr. 28.3 je zrejmé, že pravdepodobnosť výskytu aspoň jednej udalosti má v čase tendenciu k jednote, to znamená, že pri zodpovedajúcom dlhodobom pozorovaní udalosti k nej skôr či neskôr určite dôjde. Čím dlhšie udalosť pozorujeme (tým viac t), tým väčšia je pravdepodobnosť, že udalosť nastane; graf funkcie monotónne rastie.

Čím väčšia je intenzita výskytu udalosti (tým viac λ ), čím rýchlejšie k tejto udalosti dôjde a tým rýchlejšie má funkcia tendenciu k jednote. Parameter na grafe λ reprezentovaný strmosťou priamky (sklonom dotyčnice).

Ak zvýšite λ , potom pri sledovaní udalosti v rovnakom čase τ , zvyšuje sa pravdepodobnosť výskytu udalosti (pozri obr. 28.4). Je zrejmé, že graf začína od 0, pretože ak je čas pozorovania nekonečne malý, potom je pravdepodobnosť, že udalosť nastane počas tohto času, zanedbateľná. A naopak, ak je čas pozorovania nekonečne dlhý, udalosť sa určite vyskytne aspoň raz, čo znamená, že graf má tendenciu k hodnote pravdepodobnosti rovnajúcej sa 1.

Preštudovaním zákona môžete určiť, že: m X = 1/λ , σ = 1/λ , teda pre najjednoduchší tok m X = σ . Rovnosť matematického očakávania so štandardnou odchýlkou ​​znamená, že tento tok je tok bez následných účinkov. Rozptyl (presnejšie štandardná odchýlka) takéhoto toku je veľký. Fyzicky to znamená, že čas výskytu udalosti (vzdialenosť medzi udalosťami) je zle predvídateľný, náhodný a leží v intervale m X – σ < τ j < m X + σ . Aj keď je zrejmé, že v priemere sa približne rovná: τ j = m X = T n/ N . Udalosť môže nastať kedykoľvek, ale v rámci tohto okamihu τ j pomerne m X do [ σ ; +σ ] (veľkosť následného účinku). Na obr. Obrázok 28.5 ukazuje možné polohy udalosti 2 vzhľadom na časovú os pre danú vec σ . V tomto prípade hovoria, že prvá udalosť neovplyvňuje druhú, druhá neovplyvňuje tretiu atď., To znamená, že neexistuje žiadny následný účinok.

V zmysle P rovná sa r(pozri prednášku 23. Modelovanie náhodnej udalosti. Modelovanie úplnej skupiny nezlučiteľných udalostí), teda vyjadr τ z vzorca (*) Nakoniec, aby sme určili intervaly medzi dvoma náhodnými udalosťami:

τ = 1/ λ Ln( r) ,

Kde r náhodné číslo rovnomerne rozdelené od 0 do 1, ktoré je prevzaté z RNG, τ interval medzi náhodnými udalosťami (náhodná premenná τ j ).

Príklad 1 Uvažujme tok produktov prichádzajúcich do technologickej operácie. Produkty prichádzajú náhodne v priemere osem kusov za deň (prietok λ = 8/24 [jednotky/hodinu]). Tento proces je potrebné v rámci simulovať T n = 100 hodín. m = 1/λ = 24/8 = 3 , teda v priemere jeden diel za tri hodiny. Všimni si σ = 3. Na obr. Obrázok 28.6 predstavuje algoritmus, ktorý generuje tok náhodných udalostí.

Na obr. Obrázok 28.7 zobrazuje výsledok algoritmu: časové okamihy, keď súčiastky dorazili na operáciu. Ako vidno, práve v období T n = 100 spracovaných výrobných jednotiek N= 33 produktov. Ak znova spustíme algoritmus N sa môže ukázať ako rovné, napríklad 34, 35 alebo 32. Ale v priemere za K algoritmus beží N sa bude rovnať 33,33 Ak vypočítate vzdialenosti medzi udalosťami t s i a časové body definované ako 3 i, potom sa v priemere bude hodnota rovnať σ = 3 .

Modelovanie mimoriadnych tokov udalostí

Ak je známe, že tok nie je obyčajný, tak je potrebné modelovať okrem momentu vzniku udalosti aj počet udalostí, ktoré by sa v tomto momente mohli objaviť. Napríklad autá prichádzajú na železničnú stanicu ako súčasť vlaku v náhodných časoch (pravidelný tok vlakov). Ale zároveň môže mať vlak iný (náhodný) počet vozňov. V tomto prípade sa o prúde vozňov hovorí ako o prúde mimoriadnych udalostí.

Predpokladajme, že M k = 10 , σ = 4 (teda v priemere v 68 prípadoch zo 100 je vo vlaku od 6 do 14 vozňov) a ich počet je rozdelený podľa bežného zákona. Na miesto označené (*) v predchádzajúcom algoritme (pozri obr. 28.6) je potrebné vložiť fragment znázornený na obr. 28.8.

Príklad 2 Riešenie nasledujúceho problému je veľmi užitočné vo výrobe. Aká je priemerná denná odstávka zariadenia technologického uzla, ak uzol spracováva každý výrobok v náhodnom čase určenom intenzitou toku náhodných udalostí λ 2? Zároveň sa experimentálne zistilo, že produkty sa privážajú na spracovanie aj v náhodných časoch určených tokom λ 1 v dávkach po 8 kusoch a veľkosť dávky náhodne kolíše podľa bežného zákona s m = 8 , σ = 2 (pozri prednášku 25). Pred modelovaním T= 0 neboli žiadne produkty na sklade. Tento proces je potrebné v rámci simulovať T n = 100 hodín.

Na obr. Obrázok 28.9 predstavuje algoritmus, ktorý náhodne generuje tok príchodov sérií produktov na spracovanie a tok náhodných udalostí výstupov dávok produktov zo spracovania.

Na obr. Obrázok 28.10 zobrazuje výsledok algoritmu: časové okamihy, keď súčiastky dorazili do prevádzky, a časové okamihy, keď súčiastky opustili prevádzku. Tretí riadok zobrazuje, koľko dielov bolo vo fronte na spracovanie (ležiacich v sklade uzla) v rôznych časových okamihoch.

Zaznamenávaním časov, kedy bol pre spracovateľský uzol nečinný a čakal na ďalšiu časť (pozri na obr. 28.10 časové úseky zvýraznené červenou farbou), môžeme vypočítať celkový prestoj uzla za celý čas pozorovania a potom vypočítať priemerné prestoje počas dňa. Pre túto implementáciu sa tento čas vypočíta takto:

T atď. Stred. = 24 · ( t 1 priem. + t 2 am. + t 3 am. + t 4 ave ++ t N atď.)/ T n.

Cvičenie 1. Zmena hodnoty σ , nainštalovať závislosť T atď. Stred. ( σ ) . Stanovením nákladov na prestoje uzla na 100 eur/hodinu určíte ročné straty podniku z nezrovnalostí v práci dodávateľov. Navrhnite znenie klauzuly zmluvy podniku s dodávateľmi „Výška pokuty za omeškanie s dodaním produktov“.

Úloha 2. Zmenou množstva počiatočného plnenia skladu určite, ako sa zmenia ročné straty podniku z nezrovnalostí v práci dodávateľov v závislosti od množstva zásob prijatých v podniku.

Simulácia nestacionárnych tokov udalostí

V niektorých prípadoch sa intenzita prúdenia môže časom meniť λ (t). Takéto prúdenie sa nazýva nestabilné. Napríklad priemerný počet sanitiek za hodinu opúšťajúcich stanicu v reakcii na volania obyvateľov veľkého mesta sa môže počas dňa meniť. Je napríklad známe, že najväčší počet hovorov pripadá na intervaly od 23. do 01. hodiny a od 05. do 07. hodiny, pričom v ostatných hodinách je to o polovicu menej (pozri obr. 28.11).

V tomto prípade distribúcia λ (t) môže byť špecifikovaný buď grafom, vzorcom alebo tabuľkou. A v algoritme znázornenom na obr. 28.6, na miesto označené (**), budete musieť vložiť fragment znázornený na obr. 28.12.

Informatika, kybernetika a programovanie

Definícia Poissonovho toku. Poissonov tok je obyčajný tok bez následkov. Klasickým modelom prevádzky v informačných sieťach je Poissonov najjednoduchší tok. Je charakterizovaná množinou pravdepodobností Pk prijatia k správ za časový interval t: kde k=01 počet správ; λ intenzita prúdenia.

1. Definícia Poissonovho prúdenia. Vlastnosti.

Poissonov tok je obyčajný tok bez následkov.

Klasickým modelom prevádzky v informačných sieťach je Poissonov (najjednoduchší) tok. Je charakterizovaná množinou pravdepodobností P(k) príchodu k správ za časový interval t:

kde k=0,1,... - počet správ; λ - intenzita prúdenia.

Všimnite si, že časový interval na meranie počtu správ t a intenzita toku λ sú konštantné hodnoty.

Rodina Poissonových rozdelení P(k) v závislosti od λ je znázornená na obr. Väčšia hodnota λ zodpovedá širšiemu a symetrickejšiemu grafu hustoty pravdepodobnosti.

Ryža. 1. Poissonove rozdelenia. Hustoty pravdepodobnosti.

Očakávaná hodnota (priemer) a rozptyl Poissonovho toku sa rovnajú λ t.

Keď poznáme pravdepodobnosť príchodu údajov za určité obdobie, môžeme získať rozdelenie intervalu τ medzi susedné udalosti:

Z toho vyplýva záver: Poissonov tok je charakterizovaný exponenciálnym rozložením intervalov medzi udalosťami.

Hlavná vlastnosť Poissonovho toku, ktorý určuje jeho široké použitie v modelovaní, je aditívnosť: výsledný tok súčtu Poissonových tokov je tiež Poisson s celkovou intenzitou:

Pri modelovaní možno Poissonov tok získať multiplexovaním súboru ON/OFF zdrojov, ktoré sa nazývajú Markovove procesy (obr. 2.).

Ryža. 2. Získanie Poissonovho rozdelenia

2. QS s poruchami (klasický systém Erlang)

Tu sa budeme zaoberať jedným z prvých, „klasických“ problémov teórie radenia; tento problém vznikol z praktických potrieb telefonovania a vyriešil ho v roku 1909 dánsky matematický inžinier A.K. Erlang. Problém je formulovaný nasledovne: existuje n kanálov (komunikačných liniek), ktoré prijímajú tok požiadaviek s intenzitou λ. Servisný tok každého kanála má intenzitu μ. Nájdite limitujúce pravdepodobnosti stavov systému a ukazovatele jeho účinnosti.

Systém S (SMO) má tieto stavy (číslujeme ich podľa počtu aplikácií v systéme): S 0, S1,…, Sn, kde S k stav systému, keď je k požiadavkám, t.j. k kanálov je obsadených.

Stavový graf SMO zodpovedá procesu odumierania a rozmnožovania (obr. 3).

Ryža. 3. Stavový graf QS

Tok požiadaviek postupne prenáša systém z ľubovoľného ľavého stavu do susedného pravého s rovnakou intenzitou λ. Intenzita toku služieb, ktoré prenášajú systém z akéhokoľvek pravého stavu do susedného ľavého, sa neustále mení v závislosti od stavu. V skutočnosti, ak je QS v stave S 2 (dva kanály sú obsadené), potom môže prejsť do stavu S 1 (jeden kanál je obsadený), keď buď prvý alebo druhý kanál skončí servis, t.j. celková intenzita ich obslužných tokov bude 2μ. Podobne celkový tok služieb prenášajúcich QS zo stavu S 3 (obsadené tri kanály) v S 2 , bude mať intenzitu 3μ, t.j. ktorýkoľvek z troch kanálov sa môže stať voľným atď.

Vo vzorci (1) pre schému smrti a reprodukcie dostaneme pre maximálnu pravdepodobnosť stavu:

(1)

kde sú podmienky rozšírenia- koeficienty pre p 0 vo výrazoch pre hraničné pravdepodobnosti p 1, p 2,..., p n.

Všimnite si, že vo vzorci (1) nie sú intenzity λ a μ zahrnuté samostatne, ale iba vo forme pomeru μ/λ. Označme: μ/λ = p a hodnotu ρ budeme nazývať znížená intenzita toku požiadaviek alebo intenzita zaťaženia kanála. Vyjadruje priemerný počet žiadostí prichádzajúcich počas priemerného času obsluhy jednej aplikácie. Pomocou tohto zápisu prepíšeme vzorec (1) do tvaru:

(2)

kde:

(3)

Vzorce (2) a (3) pre hraničné pravdepodobnosti sa nazývajú Erlangove vzorce na počesť zakladateľa teórie radenia.

Pravdepodobnosť zlyhania QS je maximálna pravdepodobnosť, že bude obsadených všetkých n kanálov systému, t.j.

Odtiaľ nájdeme relatívnu priepustnosť, pravdepodobnosť, že požiadavka bude doručená:

Absolútnu priepustnosť získame vynásobením intenzity toku požiadaviek λ Q:

(4)

Zostáva len nájsť priemerný počet obsadených kanálov k. Túto hodnotu možno nájsť „priamo“, ako matematické očakávanie diskrétnej náhodnej premennej s možnými hodnotami 0,1,..., n a pravdepodobnosti týchto hodnôt p 0 , p 1 , ..., p n :

Nahradením výrazov (3) za str k a vykonaním príslušných transformácií by sme nakoniec dostali vzorec pre k. Priemerný počet obsadených kanálov však možno zistiť ľahšie, ak vezmeme do úvahy absolútnu priepustnosť A systém nie je nič iné ako intenzita toku aplikácií obsluhovaných systémom (za jednotku času). Keďže každý obsadený kanál obsluhuje v priemere μ požiadaviek (za jednotku času), potom priemerný počet obsadených kanálov:

alebo vzhľadom na (4):