Najjednoduchšie toky sú Markovove procesy a reťazce riešení. Prúdy udalostí Markov náhodne spracováva prúdy udalostí. Základné vlastnosti neplánovaného faktora

Proces QS je náhodný proces. Náhodný (pravdepodobnostný alebo stochastický) proces sa chápe ako proces zmeny stavu systému v čase v súlade s pravdepodobnostnými zákonmi.

Proces sa nazýva proces s diskrétnymi stavmi, ak je možné vopred vypísať jeho možné stavy S1, S2, S3... a prechody systému zo stavu do stavu nastávajú okamžite (skokové). Proces sa nazýva proces so spojitým časom, ak momenty možných prechodov systému zo stavu do stavu nie sú vopred pevne dané, ale sú náhodné.

Proces operácie QS je náhodný proces s diskrétnymi stavmi a nepretržitým časom.

Náhodný proces sa nazýva Markov alebo náhodný proces bez následkov, ak pre ktorýkoľvek časový okamih t0 pravdepodobnostné charakteristiky procesu v budúcnosti závisia iba od jeho stavu v danom okamihu t0 a nezávisia od toho, kedy a ako systém prišiel do tohto stavu.

Príklad Markovovho procesu: systém S je taxametr. Stav systému v momente t je charakterizovaný počtom kilometrov, ktoré auto predtým prešlo v tejto chvíli. Nech počítadlo ukazuje S0 v čase t0. Pravdepodobnosť, že v okamihu t>t0 bude počítadlo ukazovať ten alebo ten počet kilometrov (presnejšie zodpovedajúci počet rubľov) S1, závisí od S0, ale nezávisí od toho, v ktorých časových bodoch sa hodnoty počítadla zmenili pred moment t0.

V niektorých prípadoch možno prehistóriu uvažovaných procesov jednoducho zanedbať a na ich štúdium použiť Markovove modely.

Pri analýze náhodné procesy vhodné na použitie s diskrétnymi stavmi geometrická schéma- takzvaný stavový graf. Stavy systému sú zvyčajne znázornené obdĺžnikmi (kruhmi) a možné prechody zo stavu do stavu sú znázornené šípkami (orientovanými oblúkmi) spájajúcimi stavy (obr. 1).

Obrázok 1 - Stavový graf

Pre matematický popis Markovovho náhodného procesu s diskrétnymi stavmi a spojitým časom plynúcim v QS sa zoznámime s jedným z dôležitých konceptov teórie pravdepodobnosti – konceptom toku udalostí.

Tok udalostí sa chápe ako sled homogénnych udalostí, ktoré nasledujú za sebou v určitých náhodných časových okamihoch

Príklady môžu byť:

• - tok hovorov v telefónnej ústredni;
• - tok zapínania zariadení v domácej elektrickej sieti;
• - tok nákladných vlakov prichádzajúcich do železničnej stanice:
• - tok porúch počítača (poruchy);
• - prúd striel zameraných na cieľ.

Tok je charakterizovaný intenzitou n - frekvenciou výskytu udalostí alebo priemerným počtom udalostí vstupujúcich do QS za jednotku času.

Tok udalostí sa nazýva pravidelný, ak udalosti nasledujú po sebe v určitých intervaloch. Takýto tok je v praxi relatívne zriedkavý, ale je zaujímavý ako extrémny prípad.

Tok udalostí sa nazýva stacionárny, ak jeho pravdepodobnostné charakteristiky nezávisia od času. Najmä intenzita stacionárneho prúdenia je konštantná hodnota: .

Tok udalostí sa nazýva tok bez následného účinku, ak pre akékoľvek dva neprekrývajúce sa úseky času a _ počet udalostí pripadajúcich na jeden z nich nezávisí od počtu udalostí pripadajúcich na ostatné. Napríklad prúd cestujúcich vstupujúcich do metra nemá prakticky žiadny vplyv. A povedzme tok zákazníkov, ktorí odchádzajú od pultu s nákupmi, už má svoje dôsledky (už len preto, že časový interval medzi jednotlivými zákazníkmi nemôže byť kratší ako minimálny čas obsluhy každého z nich).

Tok udalostí sa nazýva obyčajný, ak je pravdepodobnosť výskytu dvoch alebo viacerých udalostí v malom (elementárnom) časovom intervale zanedbateľná v porovnaní s pravdepodobnosťou výskytu jednej udalosti. Inými slovami, prúd udalostí je obyčajný, ak sa v ňom udalosti vyskytujú jednotlivo a nie v skupinách.

Prúd udalostí sa považuje za najjednoduchší (alebo stacionárny Poisson), ak je zároveň stacionárny, obyčajný a bez následkov.

Najjednoduchší tok ako limita vzniká v teórii náhodných procesov rovnako prirodzene, ako v teórii pravdepodobnosti normálne rozdelenie získame superpozíciou (superpozíciou) dostatočne veľkého počtu n nezávislých, stacionárnych a obyčajných tokov (vzájomne porovnateľných v r. intenzita), výsledkom je prietok blízky najjednoduchšiemu s intenzitou l, ktorá sa rovná súčtu intenzít privádzaných tokov:

Uvažujme najjednoduchší tok udalostí na časovej osi ako neobmedzenú postupnosť náhodných bodov. (obr. 2)

Obrázok 2 - Priebeh udalostí

Dá sa ukázať, že pre najjednoduchší tok je počet m udalostí (bodov) dopadajúcich na ľubovoľný časový úsek φ rozdelený podľa Poissonovho zákona

pre ktorú sa matematické očakávanie náhodnej premennej rovná jej rozptylu:

Najmä pravdepodobnosť, že počas času φ (m = 0) nenastane žiadna udalosť, sa rovná

Nájdite rozdelenie časového intervalu T medzi ľubovoľné dve susediace udalosti najjednoduchšieho toku.

V súlade so vzorcom sa pravdepodobnosť, že počas časového obdobia t nenastane žiadna z nasledujúcich udalostí, rovná

a pravdepodobnosť opačnej udalosti, t.j. distribučná funkcia náhodnej premennej T, je

Hustota pravdepodobnosti náhodnej premennej je deriváciou jej distribučnej funkcie:

Rozdelenie dané hustotou pravdepodobnosti alebo distribučnou funkciou sa nazýva exponenciálne (alebo exponenciálne). Časový interval medzi dvoma susednými ľubovoľnými udalosťami má teda exponenciálne rozdelenie, pre ktoré sa matematické očakávanie rovná štandardnej odchýlke náhodnej premennej

a naopak podľa intenzity prietoku l.

Najdôležitejšia vlastnosť exponenciálneho rozdelenia (vlastná iba exponenciálnemu rozdeleniu) je nasledovná: ak časový úsek rozdelený podľa exponenciálneho zákona už nejaký čas φ trval, potom to nijako neovplyvňuje zákon rozdelenia. zostávajúcej časti intervalu (T-φ): bude to isté, ako aj zákon rozdelenia celého intervalu T.

Inými slovami, pre časový interval T medzi dvoma po sebe idúcimi susednými udalosťami toku, ktorý má exponenciálne rozdelenie, akákoľvek informácia o tom, ako dlho tento interval trval, neovplyvní distribučný zákon zostávajúcej časti.

Pre najjednoduchšie prúdenie s intenzitou l je pravdepodobnosť výskytu aspoň jednej prúdovej udalosti v elementárnom (malom) časovom intervale?t rovná

Výpočtové technológie

Ročník 13, špeciálne vydanie 5, 2008

Štúdium toku semimarkovských udalostí

A. A. Nazarov, Štátna univerzita S. V. Lopukhova Tomsk, Rusko e-mail: nazarov@f pmk. tsu. ru, lopuchovasv@mail. ru

I.R. Garaishina

pobočka Kemerovo štátna univerzita v Anzhero-Sudzhensk, Rusko e-mail: [e-mail chránený]

V predloženej práci je uvažovaný semimarkovský proces. Zvažuje sa limitujúci model. Výsledky analytického spracovania limitného modelu sú porovnané s výsledkami získanými asymptotickou metódou.

Úvod

Vzniká problém rozšírenia triedy matematických modelov tokov homogénnych dejov. Klasické modely náhodných tokov udalostí často nemôžu byť adekvátne skutočným informačným a telekomunikačným tokom. Poissopove modely a najjednoduchšie toky často nestačia na vierohodnejší a realistickejší popis prichádzajúcich tokov pre systémy. radenie. Napriek skutočnosti, že existujú toky fázového typu a modulované Poissonove toky, ktoré sú vhodnejšie pre reálne situácie, sú veľmi zaujímavé semimarkovské modely tokov, ktorých špeciálnym prípadom sú toky Markovovej obnovy a všetky vyššie uvedené toky. Metódy na štúdium takýchto modelov sú pomerne zložité a vedú k významným matematickým problémom. Preto spolu s úlohou rozširovania tried tokov vzniká problém vývoja metód na ich štúdium.

1. Matematický model

Náhodný tok homogénnych udalostí (tok) sa bude nazývať usporiadaná sekvencia

t\< ¿2 < ■ ■ ■

náhodné veličiny tm - momenty výskytu udalostí v toku.

Nech je daná semi-Markovova matica A(x) s prvkami Aklk2 (x) Matica P = lim A(x) je preto pre dané počiatočné rozdelenie stochastická.

definuje určitý Markovov reťazec k (tm) s diskrétnym časom, ktorý budeme nazývať Markovov reťazec vnorený do semimarkovského toku,

© Ústav výpočtových technológií sibírskej pobočky Ruskej akadémie vied, 2008.

A. A. Nazarov, S. V. Lopukhova, I. R. Garaishina

Náhodný tok homogénnych dejov budeme nazývať semimarkovský, ak je pravdepodobnostný zákon vzniku postupnosti (1) určený počiatočným rozdelením a rovnosťami.

Ak1k2 (x) = P (k(bm+1) = k2, bm+1 - bm< х ^^т) = к\ }

pre všetky m > 1.

Označme n(b) počet udalostí semimarkovovského toku, ktoré nastali v čase b v intervale .

Výskumným cieľom tejto práce je stanoviť rozdelenie pravdepodobnosti P(n, b) = P(n(b) = n) pre stacionárnu operáciu ergodického Markovovho reťazca k (1m). Je zrejmé, že proces n(b) nie je markovovský, takže definujeme ďalšie dva náhodné procesy: r(b) je dĺžka intervalu od času b do okamihu ďalšej udalosti v uvažovanom toku, k(b). ) je ľavobežný kontinuálny proces so spojitým časom, ktorého hodnota na intervale (bm,bm+1] je konštantná a je definovaná rovnosťami k(b) = k(bm+1). Na základe vytvorených definícií náhodný proces (k(b), n(b), r(b)) je trojrozmerný Markovov proces so spojitým časom.

Všimnite si, že náhodný proces k(b) nie je v klasickej definícii semimarkovovský, pretože semimarkovovský proces B(b) je priamo kontinuálny a ako je uvedené v, pre jeho pravdepodobnosti prechodu neexistujú žiadne Kolmogorovove diferenciálne evolučné rovnice, kým vyššie navrhnutý proces (k(b), n(b), r(b)) je markovovský, preto pre jeho rozdelenie pravdepodobnosti

P (k, n, r, b) = P (k (b) = k, n (b) = n, r (b)< г} (2)

nie je ťažké zostaviť systém Kolmogorovových diferenciálnych rovníc dP (k,n,z,b) dP (k,n,z,b) dP (k,n, 0,b) ^ dP (u,n - 1 ,0,b)

^ dG (u,1b - 1, 0,b) A (\2-^-

db dg dg ^ dg

Označme

H(k, u, z, z) = ^ e "uPR(k, n, z, b),

kde ] = ¡~ ~~ imaginárna jednotka. Pre tieto funkcie môžeme písať z Kolmogorovovho systému diferenciálnych rovníc

dN (k,u,r,b) dN (k,u,r,b) dN (k,u,0,b) ,u ^ dN (u,u,0,b)

db dg dg ^ dg

Označme H (u,r,b) = (H (1,u,r,b) ,H (2,u,r,b),...) čiaru vektorovej funkcie, potom prepíšeme sústavy rovníc (3) do maticového tvaru

dN(i,g,g) _ dN(i,g,g) dN(i,0,g) Mts,g h p t

dg dg + dg 1 [) "" [ )

ktorého riešenie spĺňa počiatočnú podmienku H(u,z, 0) = R(z), kde I je matica identity a stacionárny rozvod R(z) dvojrozmerného Markovovho procesu (k(t), z(t)) je riešením Cauchyho problému

<Ш = <Ш(1-Мг)),

a je určená rovnosťou R(z) = seiт / (Р - A(x))dx, kde aei = Tu r je vektor-

reťazec stacionárneho rozdelenia pravdepodobnosti hodnôt vnoreného Markovovho reťazca

k(tm); E je jednotkový stĺpcový vektor a matica A = (P - A(x))dx.

2. Predlimitný model

Majme diferenciálnu rovnicu (4), ktorej riešenie H (u,z,t) spĺňa počiatočnú podmienku H(u, z, 0) = R(z). Potom Fourierova - Stieltjessova transformácia

f>(u,a,t) = / ejaz dz H (u, z, t) vektorová funkcia H (u,z,t) vyhovuje rovnici

df(u,a,b) . . dN (u, 0, b), .*. . gL, .

t = ~zaf(sh a, + - (e? uA*(a) - /) (5)

a počiatočný stav

φ(u,a, 0) = R*(a) = ^ e>a2

kde A*(a) = J e>a"2dA(z). Riešenie rovnice (5) má tvar

f(u, a,1) = e~zab [II*(a) + I (¿>uA*(a) - I) dt]. (6)

Necháme b ísť do nekonečna vo výraze (6), dostaneme Fourierovu transformáciu v m

dN (u, 0,t) ^ ^ "l

z vektorovej funkcie ---. Po vykonaní inverznej Fourierovej transformácie určíme

Ja e-j *A*(aj) 1 da.

A. A. Nazarov, S. V. Lopukhova, I. R. Raraishshia

Teraz možno rovnosť (6) zapísať do tvaru

f(a,g) = e-ab I*(a) +

+ - / e]at I e~zutK*(y) (/ - e>uA*(y)) 1 Ау (е "уА*(а) - /)<*г). (7)

Keď vieme, že H(u, w,g) = H(u,g) = φ(u, 0,1), dostaneme výraz pre vektorovú funkciu H(u,g):

Potom rozdelenie pravdepodobnosti P(n, r) počtu udalostí vyskytujúcich sa počas času r je

tion H(u,b) = MeEin(b = H(u,b)E, má tvar

1 Ca1 G1 - e-™b

P(n,1) = - e~zipNSh)E(1u = - / -^-5

I - A* (y) A*(y)n-1Eyu, (8)

I – A* (y) E<1у

Záver

Uskutočnením asymptotických štúdií semimarkovovského toku udalostí, podobne ako pri štúdiu tokov Markovovej obnovy, zistíme, že asymptotiku tretieho rádu pre charakteristickú funkciu možno zapísať v tvare

MeGan(1) = ^«(ge^+^ae^+^aez*)

kde koeficienty 831, a2, az3 pre semimarkovský prietok sa stanovia podobne, ako sa to robilo v prac. Výsledné rovnosti (8) určujú rozdelenie pravdepodobnosti P(n,r) počtu udalostí vyskytujúcich sa v stacionárnom semi-Markovovom toku špecifikovanom semi-Markovovou maticou A(x) a jej Fourier-Stieltjessovou transformáciou A*(x). Numerická implementácia vzorcov (8) nám umožňuje nájsť číselné hodnoty pravdepodobností P(n, r) pre pomerne širokú triedu matíc A* (x) a hodnoty r. implementácia je obmedzená výpočtovými zdrojmi. Pre dostatočne veľké hodnoty r je prirodzené použiť metódu asymptotickej analýzy semi-Markovovho toku rovnakým spôsobom, ako sa to urobilo pre Markovov obnovovací tok v práci a preosiaty Markovov obnovovací tok v práci. Prítomnosť numerického algoritmu (8) nám umožňuje určiť rozsah použitia asymptotických výsledkov. Pre uvažované toky s tromi stavmi vnoreného Markovovho reťazca je vzdialenosť Kolmogorov - Smirnov medzi rozvodmi,

získané asymptoticky a podľa vzorcov (8), nepresahuje 2-3% pre určité hodnoty t = T, to nám umožňuje konštatovať, že pre t > T je použitie asymptotických výsledkov efektívne a pre t< Т целесообразно использовать формулы (8), полученные в данной работе.

Bibliografia

Korolyuk B.C. Stochastické modely systémov. Kyjev: Nauk, Dumka, 1989. 208 s.

Nazarov A.A., Lopukhova S.B. Štúdium Markovovho regeneračného toku pomocou asymptotickej metódy druhého rádu // Mater. Intl. vedecký conf. "Matematické metódy na zvýšenie efektívnosti telekomunikačných sietí." Grodno, 2007. S. 170-174.

Lopukhova S.B. Štúdium semi-Markovovho toku pomocou asymptotickej metódy tretieho rádu // Mater. VI Int. vedecko-praktické conf. "Informačné technológie a matematické modelovanie." Tomsk: Vydavateľstvo Tom. Univ., 2007. Časť 2. S. 30-34.

Cieľ prednášky: osvojenie si pojmov tok udalostí, najjednoduchší tok udalostí, Markovov proces.

1. Tok udalostí. Vlastnosti streamu udalostí. Najjednoduchší tok udalostí. Poissonov vzorec.

2. Servisný proces ako Markovov proces.

3. Jednokanálové QS s čakaním.

Tok udalostí je sled homogénnych udalostí, ktoré nasledujú po sebe v náhodných časoch.

Príklady môžu byť:

Tok hovorov v telefónnej ústredni;

Priebeh zlyhaní počítača;

Prúd výstrelov zameraných na cieľ atď.

Pravidelný tok je tok, v ktorom udalosti nasledujú za sebou v pravidelných intervaloch (deterministický sled udalostí).

Tento tok udalostí sa v praxi vyskytuje len zriedka. V telekomunikačných systémoch sa častejšie vyskytujú toky, pri ktorých sú tak momenty výskytu udalostí, ako aj časové intervaly medzi nimi náhodné.

Uvažujme také vlastnosti tokov udalostí ako stacionárnosť, obyčajnosť a nedostatok následkov.

Prúd je stacionárny ak pravdepodobnosť výskytu určitého počtu udalostí v časovom intervale τ závisí len od dĺžky tohto intervalu a nezávisí od jeho umiestnenia na časovej osi. Pre stacionárny tok je priemerný počet udalostí za jednotku času konštantný.

Obyčajný tok je tok, pre ktorý je pravdepodobnosť výskytu dvoch alebo viacerých požiadaviek v danom krátkom časovom období zanedbateľne malá v porovnaní s pravdepodobnosťou výskytu jednej požiadavky.

V telekomunikačných systémoch sa tok považuje za obyčajný.

Tok bez následkov vyznačujúci sa tým, že pre dva neprekrývajúce sa časové intervaly

pravdepodobnosť výskytu počtu udalostí v druhom intervale nezávisí od počtu výskytov udalostí v prvom intervale.

Parameter prietok sa nazýva limit

kde je pravdepodobnosť, že sa objednávky objavia v intervale.

Intenzita toku μ je priemerný počet udalostí za jednotku času.

Pri stacionárnom toku jeho parameter nezávisí od času.

Pre stacionárny a obyčajný prietok λ=μ.

Najjednoduchšie alebo Poissonov tok nazývaný stacionárny, obyčajný tok bez následných efektov.

Najjednoduchší tok sa riadi Poissonovým distribučným zákonom

kde je intenzita prúdenia;

Počet udalostí vyskytujúcich sa v priebehu času.

Najjednoduchší tok môže byť špecifikovaný funkciou rozdelenia intervalu medzi susedné hovory

F(t)=P(z t),

P(z>t) je ekvivalentné pravdepodobnosti, že v intervale dĺžky t nepríde viac ako jeden hovor.

F(t)=P(z>t)=1-(t)=1-

Tento zákon rozdelenia náhodnej premennej sa nazýva exponenciálny.

Vlastnosti a charakteristiky najjednoduchšieho toku:

a) pre najjednoduchší tok sa matematické očakávanie a štandardná odchýlka hodnoty medzery z navzájom rovnajú MZ= σz=1/λ;

b) Očakávaná hodnota a rozptyl počtu hovorov i za časové obdobie t sa rovnajú Mi=Di= λt.

Zhoda týchto hodnôt sa v praxi používa pri kontrole skutočného prietoku, aby zodpovedal jeho najjednoduchšiemu.

QS je systém, ktorý zahŕňa prítomnosť 2 procesov v ňom: príjem žiadostí a servis aplikácií.

Konvenčne je schéma znázornená vo forme

A Drive K

Servisné zariadenie

Proces podávania žiadostí je proces založený na čase.

Tok udalostí je sled momentov v čase, keď nastanú nejaké udalosti.

S akýmkoľvek QS sú spojené 3 toky:

1) vstupný tok. Postupnosť časov prijatia žiadostí

2) výstupný tok. Postupnosť bodov v čase, keď odchádzajú obsluhované požiadavky.

3) tok služieb. Postupnosť koncových časov pre servisné požiadavky za predpokladu, že servis sa vykonáva nepretržite.

Charakteristický je prietok intenzita - priemerný počet udalostí za jednotku času.

Tok sa nazýva pravidelné, ak sú časové intervaly medzi udalosťami v ňom rovnaké. Nepravidelný– ak sú časové intervaly medzi udalosťami náhodné premenné.

Prietok opakujúci, ak časové intervaly medzi udalosťami sú náhodné premenné rozdelené podľa rovnakého zákona.

Tok sa nazýva homogénne, ak he x je len množina (ti) udalostí, ktoré sa vyskytli. Heterogénne– ak je opísaná množinou (ti,fi), kde ti sú časové okamihy výskytu udalostí, fi je znak aplikácie.

Samotné QS sa delia na QS s poruchami a QS s frontami. QS s frontami sa delí na tie s obmedzeným frontom a tie s neobmedzeným frontom. Špeciálnym prípadom je obmedzená doba čakania v rade.

V systémoch posledného typu sú aplikácie, ktoré nie je možné okamžite obsluhovať, zaradené do frontu a pomocou určitej servisnej disciplíny sú z neho vybrané. Niektoré z najpoužívanejších disciplín:

1) FIFO (first in – first out) – v prijatom poradí;

2) LIFO (posledný dovnútra – prvý von) – posledný prichádzajúci je obsluhovaný ako prvý;

3) SIRO (služba v náhodnom poradí) - v náhodnom poradí;

4) – prioritné systémy. (absolútne a relatívne priority. Pri relatívnych sú aplikácie usporiadané podľa hodnoty priority - najprv vysoká, potom nižšia.)

Stručný popis QS D. Kendall zaviedol symboliku (notáciu)

m - počet obslužných kanálov;

n – počet čakacích miest (skladovacia kapacita).

k – počet zdrojov.

A a B charakterizujú vstupný tok a servisný tok, špecifikujú distribučnú funkciu intervalov medzi požiadavkami vo vstupnom toku a distribučnú funkciu servisných časov.

A a B môžu nadobúdať nasledujúce hodnoty:

D – deterministické rozdelenie;

M – orientačné;

E r – Erlangovo rozdelenie;

H r - hyperindikatívne;

G – všeobecné rozdelenie.

To predpokladá, že toky sú opakujúci, t.j. intervaly medzi udalosťami sú nezávislé a majú rovnaké rozdelenie. Prvé 3 pozície sú v zápise povinné. V predvolenom nastavení, ak chýba n, máme systém s poruchami; ak chýba k, potom je predvolene jeden zdroj.

9. Najjednoduchšie prúdenie, jeho vlastnosti a význam pri štúdiu smo.

Prúd, ktorý spĺňa nasledujúce tri požiadavky, sa nazýva najjednoduchší.

1) Prietok stacionárne, ak pravdepodobnosť príchodu daného počtu udalostí počas časového intervalu pevnej dĺžky závisí len od trvania intervalu a nezávisí od jeho umiestnenia na časovej osi.

2) Prietok obyčajný, ak pravdepodobnosť výskytu dvoch alebo viacerých udalostí počas elementárneho časového intervalu
→0 je veličina nekonečne malá v porovnaní s pravdepodobnosťou výskytu jednej udalosti v tomto intervale.

3) Prúd sa nazýva prúd bez následného účinku, 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 ostatné. Niekedy je táto vlastnosť formulovaná nasledovne: rozdelenie času do najbližšej udalosti nezávisí od času pozorovania, t.j. v závislosti od toho, koľko času uplynulo od poslednej udalosti.

Prúd, ktorý spĺňa tieto tri podmienky, sa nazýva najjednoduchšie.

Pre neho sa počet udalostí spadajúcich do akéhokoľvek pevného časového intervalu riadi Poissonovým zákonom, a preto sa nazýva aj stacionárny Poisson.

pravdepodobnosť, že počas časového intervalu τ sa stane presne m diania.

Pre najjednoduchší tok je najdôležitejšia podmienka bez následkov (aplikácie prichádzajú nezávisle od seba).

Poissonovo rozdelenie.

Pravdepodobnosť, že nestane sa ani jedna udalosť

Pravdepodobnosť, že počas doby uskutoční sa aspoň jedna udalosť

Niekedy je vhodnejšie analyzovať systém s ohľadom na intervaly medzi udalosťami T:

Toto je exponenciálny zákon s intenzitou .

Očakávanie a stredná štvorec pre T:

Vlastnosť absencie následného efektu umožňuje použitie aparátu Markovových reťazcov na štúdium najjednoduchšieho toku.

Stavy systému predstavíme takto: systém považujeme za stav S, ak v čase t je v systéme S aplikácií.

Určme pravdepodobnosť pre systém, ktorého stav je určovaný iba príjmom žiadostí, ktoré v súčasnosti
systém zostane v rovnakom stave. Je zrejmé, že táto pravdepodobnosť je určená skutočnosťou, že počas intervalu
neboli doručené žiadne prihlášky

(S=0, 1, 2…)

Rozšírením v sérii dostaneme:

Pravdepodobnosť prijatia aspoň jednej žiadosti

Podobné vzťahy možno získať zvážením procesu servisu aplikácií.

V praxi sa často stretávame s najjednoduchšími alebo im blízkymi tokmi.

Pri sčítaní dostatočne veľkého počtu tokov s následným účinkom sa získa tok s následným účinkom. V najjednoduchšom toku približne 68 % malých intervalov

Pravdepodobné preosievanie najjednoduchšieho toku vedie k najjednoduchšiemu toku

10. Spojité-stochastické modely (Q- schéma). Jednokanálový QS s blokovaním. Stavebníctvostavový graf.

Pri konštrukcii modelov tohto druhu sa spravidla používajú úvahy o modelovaných objektoch, ako sú systémy frontových služieb (QS).

Takto možno znázorniť procesy rôzneho fyzikálneho charakteru – ekonomické, technické, výrobné a pod.

V QS možno rozlíšiť dva stochastické procesy:

Príjem žiadostí o službu;

Servis aplikácií.

Stream udalosti– sled udalostí, ktoré sa vyskytujú jedna po druhej v určitých časových bodoch. V QS budeme rozlišovať dva toky:

Vstupný tok: sada časov, kedy sú aplikácie prijaté do systému;

Tok služieb: množina momentov, kedy systém dokončí spracovanie žiadostí.

Vo všeobecnosti môže byť elementárny typ QS reprezentovaný nasledovne

Servisné zariadenie

I – zdroj;

O – front;

K – servisný kanál.

Jednokanálový QS s blokovaním. systémM / M/ 1/ n

Uvažujme dvojfázový systém, pre ktorý sa pri štúdiu P-schém predpokladal deterministický vstup a tok preosiatych služieb.

Predpokladáme, že teraz je vstupný tok Poisson s intenzitou a tok služieb je Poisson s intenzitou .

Ako predtým, disciplína služby FIFO s blokovaním zdroja.

Stav – počet aplikácií v systéme.

Úplne možné n+3 stavy: od 0 do n+2 .

Označme
- pravdepodobnosť príchodu pre
i aplikácie;

- pravdepodobnosť služby pre
i aplikácie.

kvôli obyčajnému

Podobne

+
=

1-
+

Systém rovníc:
A
- pravdepodobnosti stavu.

pri
dostaneme

Vzhľadom na stacionárny charakter tokov máme:

A
,

Podobne pre zvyšné riadky systému.

Nakoniec tu máme:

Získa sa systém algebraických rovníc.

Transformujeme ju, počnúc druhou a končiac predposlednou - získame novú rovnicu sčítaním starej s novou.

V dôsledku toho sa nová predposledná rovnica zhoduje so starou poslednou rovnicou:

i=0, 1,….n+1

Označme

,

Používame normalizačnú rovnicu

;

;

Toto je súčet geometrickej progresie:

Priemerný čas pozorovania aplikácie

Uvažujme nejaký fyzikálny systém S=(S 1 ,S 2 ,…S n ), ktorý sa pohybuje zo stavu do stavu vplyvom nejakých náhodných udalostí (hovory, zlyhania, výstrely). Predstavme si to tak, že udalosti, ktoré prenášajú systém zo stavu do stavu, sú akýmsi prúdom udalostí.

Nech je systém S v čase t v stave S i a môže sa z neho pod vplyvom nejakého Poissonovho toku udalostí s intenzitou ij presunúť do stavu S j: akonáhle sa objaví prvá udalosť tohto toku, systém okamžite presúva z S i do S j . Ako vieme, pravdepodobnosť tohto prechodu za elementárne časové obdobie (prvok pravdepodobnosti prechodu) je rovnaká, z toho vyplýva, že hustota pravdepodobnosti prechodu ij v súvislom Markovovom reťazci nie je nič iné ako intenzita toku udalostí, ktoré sa pohybujú systému pozdĺž príslušnej šípky. Ak všetky toky udalostí, ktoré prenášajú systém S zo stavu do stavu, sú Poissonove, potom proces vyskytujúci sa v systéme bude markovovský.

Označme intenzity Poissonových tokov (hustoty pravdepodobnosti prechodov) na grafe stavov sústavy pri príslušných šípkach. Získame označený stavový graf. Na jej základe môžete napísať Kolmogorovove rovnice a vypočítať pravdepodobnosti stavov.

Príklad. Technický systém S pozostáva z dvoch uzlov I a II, z ktorých každý môže zlyhať nezávisle od druhého. Poruchový tok prvého uzla je Poisson s intenzitou I, druhý je tiež Poisson s intenzitou II. Každý uzol sa ihneď po poruche začne opravovať (obnovovať). Tok opráv (dokončenie opráv uzlov) pre oba uzly je Poissonovo s intenzitou. Vytvorte stavový graf systému a napíšte Kolmogorovovu rovnicu. Stavy systému: S 11 - oba uzly sú funkčné; S 21 - prvý blok je v oprave, druhý je v prevádzke; S 12, S 22.

t=0 p11=1 p21=p22=p12=0

p 11 + p 12 + p 21 + p 22 =1.

Limitné pravdepodobnosti stavov pre súvislý Markovov reťazec

Nech existuje fyzikálny systém S=(S 1 ,S 2 ,…S n ), v ktorom dochádza k Markovovmu náhodnému procesu so spojitým časom (nepretržitý Markovov reťazec). Predpokladajme, že ij =const, t.j. všetky toky udalostí sú najjednoduchšie (stacionárny Poisson). Zapísaním systému Kolmogorovových diferenciálnych rovníc pre pravdepodobnosti stavov a integráciou týchto rovníc za daných počiatočných podmienok dostaneme p 1 (t), p 2 (t), ... p n (t), pre ľubovoľné t. Položme si nasledujúcu otázku: čo sa stane so systémom S pri t. Budú funkcie p i (t) inklinovať k nejakým limitom? Tieto limity, ak existujú, sa nazývajú limitujúce pravdepodobnosti stavov. Môžeme dokázať vetu: ak je počet stavov S konečný a z každého stavu možno prejsť (v určitom počte krokov) k sebe, potom limitné pravdepodobnosti stavov existujú a nezávisia od počiatočného stavu systém. Predpokladajme, že uvedená podmienka je splnená a existujú obmedzujúce pravdepodobnosti (i=1,2,…n), .

Pri t je teda v systéme S nastolený určitý limitujúci stacionárny režim. Význam tejto pravdepodobnosti: nie je nič iné ako priemerný relatívny čas, počas ktorého systém zostáva v danom stave. Na výpočet pi v systéme Kolmogorovových rovníc popisujúcich pravdepodobnosti stavov je potrebné nastaviť všetky ľavé strany (deriváty) na 0. Systém výsledných lineárnych algebraických rovníc je potrebné riešiť spolu s rovnicou.

Schéma smrti a reprodukcie

Vieme, že ak dostaneme označený stavový graf, môžeme ľahko písať Kolmogorovove rovnice pre stavové pravdepodobnosti a tiež písať a riešiť algebraické rovnice pre konečné pravdepodobnosti. V niektorých prípadoch je možné vyriešiť posledné rovnice vopred, v podobe písmen. Dá sa to urobiť najmä vtedy, ak je stavovým grafom systému takzvaná „schéma smrti a reprodukcie“.

Stavový graf pre schému smrti a reprodukcie má podobu znázornenú na obr. 19.1. Zvláštnosťou tohto grafu je, že všetky stavy systému je možné nakresliť do jedného reťazca, v ktorom je každý zo stredných stavov (S 1, S 2, ..., S n-1) spojený priamou a spätnou šípkou. s každým zo susedných štátov - vpravo a vľavo, a krajné štáty (S 0 , S n) - len s jedným susedným štátom. Pojem „schéma smrti a reprodukcie“ pochádza z biologických problémov, kde podobná schéma popisuje zmeny veľkosti populácie.

Schéma smrti a reprodukcie sa veľmi často vyskytuje v rôznych praktických problémoch, najmä v teórii radenia, takže je užitočné raz a navždy nájsť pre ňu konečné pravdepodobnostištátov.

Predpokladajme, že všetky toky udalostí, ktoré pohybujú systémom po šípkach grafu, sú najjednoduchšie (pre stručnosť budeme systém S aj proces v ňom vyskytujúci sa nazývať najjednoduchšími).

Pomocou grafu na obr. 19.1 budeme skladať a riešiť algebraické rovnice pre konečné pravdepodobnosti stavov (ich existencia vyplýva z toho, že z každého stavu sa dá ísť k sebe a počet stavov je konečný). Pre prvý stav S 0 máme:

Pre druhý stav S 1:

Na základe (8.1) sa posledná rovnosť zredukuje na tvar

kde k nadobúda všetky hodnoty od 0 do n. Takže konečné pravdepodobnosti p 0 , p 1 ,..., p n spĺňajú rovnice

okrem toho je potrebné vziať do úvahy normalizačný stav

p 0 + p 1 + p 2 +…+ p n = 1 (8,3)

Poďme vyriešiť tento systém rovníc. Z prvej rovnice (8.2) vyjadríme p 1 až p 0 .

Z druhého, berúc do úvahy (8.4), získame:

od tretieho, berúc do úvahy (8.5),

a vo všeobecnosti pre akékoľvek k (od 1 do N):

Venujme pozornosť vzorcu (8.7). Čitateľ je súčinom všetkých intenzít pri šípkach smerujúcich zľava doprava (od začiatku po daný stav S k) a menovateľ je súčinom všetkých intenzít pri šípkach smerujúcich sprava doľava (od začiatku po S k).

Všetky pravdepodobnosti stavov p 1, p 2, ..., p n sú teda vyjadrené prostredníctvom jedného z nich (p 0). Dosaďte tieto výrazy do podmienky normalizácie (8.3). Vyberieme p 0 zo zátvoriek:

odtiaľ dostaneme výraz pre p 0.

(zátvorku sme zdvihli na mocninu -1, aby sme nepísali dvojposchodové zlomky). Všetky ostatné pravdepodobnosti sú vyjadrené prostredníctvom p 0 (pozri vzorce (8.4) - (8.7)). Všimnite si, že koeficienty pre p 0 v každom z nich nie sú ničím iným ako postupnými členmi radu po jednom vo vzorci (8.8). To znamená, že výpočtom p 0 sme už našli všetky tieto koeficienty.

Výsledné vzorce sú veľmi užitočné pri riešení najjednoduchších problémov teórie radenia.

Problémy teórie radenia. Klasifikácia systémov radenia a ich hlavné charakteristiky

Pri skúmaní operácií sa často stretávame s prevádzkou svojráznych systémov nazývaných queuing systems (QS). Príkladmi takýchto systémov sú: telefónne ústredne, opravovne, pokladne, informačné pulty, obchody, kaderníctva atď. Každý servisný systém pozostáva z určitého počtu servisných jednotiek (alebo „zariadení“), ktoré budeme nazývať servisné kanály. Kanály môžu byť: komunikačné linky, pracovné miesta, pokladníci, predajcovia, výťahy, autá atď. QS môže byť jednokanálové a viackanálové.

Každý QS je navrhnutý tak, aby slúžil určitému toku aplikácií (alebo „požiadaviek“), ktoré prichádzajú v určitých náhodných okamihoch v čase. Obsluha požiadavky pokračuje nejaký, všeobecne povedané, náhodný čas T, po ktorom je kanál uvoľnený a pripravený prijať ďalšiu požiadavku. Náhodná povaha toku aplikácií a servisných časov vedie k tomu, že počas určitých časových období sa na vstupe QS nahromadí nadmerne veľký počet aplikácií (buď sa zaradia do frontu, alebo nechajú QS neobslúžený); v ostatných obdobiach bude SOT pracovať s nedostatočným zaťažením alebo bude úplne nečinná.

V QS je nejaký druh SP s diskrétnymi stavmi a spojitým časom; stav QS sa náhle zmení v momente výskytu nejakej udalosti (alebo príchodu novej požiadavky, alebo ukončenia služby, alebo momentu, keď z radu odíde požiadavka, ktorá je unavená z čakania). Aby bolo možné dať odporúčania pre racionálnu organizáciu tohto procesu a klásť primerané nároky na QS, je potrebné preštudovať si SP a matematicky ho popísať. Toto robí teória IR.

Predmetom teórie radenia je konštrukcia matematických modelov, ktoré spájajú dané prevádzkové podmienky QS (počet kanálov, ich produktivita, prevádzkové pravidlá, charakter toku požiadaviek) s charakteristikami, ktoré nás zaujímajú - indikátory efektívnosť QS, ktorý z jedného alebo druhého hľadiska popisuje jeho schopnosť vyrovnať sa s tokom aplikácií. Ako takéto ukazovatele (v závislosti od situácie a cieľov štúdie) možno použiť rôzne hodnoty, napríklad: priemerný počet aplikácií obsluhovaných QS za jednotku času; priemerný počet obsadených kanálov; priemerný počet žiadostí vo fronte a priemerný čas čakania na službu; pravdepodobnosť, že počet žiadostí vo fronte prekročí určitú hodnotu a pod. Rozsah aplikácie matematických metód teórie ML sa neustále rozširuje a čoraz viac presahuje úlohy spojené so „servisnými organizáciami“ v doslovnom zmysle slova. . Za druh samoobslužných systémov možno považovať: počítače, systémy na zber a spracovanie informácií, automatizované výrobné prevádzky, výrobné linky, dopravných systémov, systémy protivzdušnej obrany atď.

Matematická analýza operácie QS je značne uľahčená, ak je proces tejto operácie markovovský. Na to stačí, aby všetky toky udalostí, ktoré prenášajú systém zo stavu do stavu (toky požiadaviek, toky „služieb“), boli jednoduché. Ak je táto vlastnosť porušená, potom sa matematický popis procesu stáva oveľa komplikovanejším a je možné ho doviesť do explicitných, analytických vzorcov len v ojedinelých prípadoch. Avšak aparát najjednoduchšej, Markovovej teórie radenia môže byť stále užitočný pre približný popis činnosti QS aj v prípadoch, keď toky udalostí nie sú najjednoduchšie. V mnohých prípadoch sa na prijatie rozumného rozhodnutia o organizácii práce QS vôbec nevyžaduje presná znalosť všetkých jeho charakteristík - často stačí približná, približná znalosť. Okrem toho, čím je QS komplexnejší, čím viac servisných kanálov má, tým presnejšie sú tieto približné vzorce.