Najjednoduchšie toky sú Markovove procesy a rozhodovacie reťazce. Toky udalostí Markovovo náhodné procesy sú toky udalostí. Ergodické a absorbujúce reťaze

Prúdy udalostí Ide o sled udalostí, ktoré sa vyskytujú jedna po druhej v určitých časových intervaloch. T je priemerný čas medzi susednými udalosťami. Ak T=konšt., potom sú udalosti v streame rovnomerne rozdelené. - intenzita toku, t.j. priemerný počet udalostí vyskytujúcich sa za jednotku času.

Toky udalostí Stacionárne Počet udalostí spadajúcich do ľubovoľného časového intervalu nezávisí od polohy na číselnej osi, ale závisí iba od jej šírky Žiadny následný efekt Pre ľubovoľné dva neprekrývajúce sa časové intervaly počet udalostí spadajúcich do jedného z nich nezávisí od toho, koľko udalostí sa stalo v inom intervale Pravidelný Opačný tok bez následného účinku (s následným účinkom)

Prúdy udalostí Obyčajný V každom časovom okamihu nastane jedna a len jedna udalosť, t. j. pravdepodobnosť výskytu dvoch alebo viacerých udalostí v nekonečne malom časovom intervale je zanedbateľná v porovnaní s pravdepodobnosťou výskytu jednej udalosti Poissonovo Nestacionárne, bežné prúdenie bez následného účinku Najjednoduchší stacionárny, obyčajný tok bez následného účinku, pre ktorý je počet udalostí, ktoré sa objavia za určité časové obdobie, rozdelený podľa Poissonovho zákona a časové intervaly medzi dvoma po sebe nasledujúcimi udalosťami sú charakterizované exponenciálnym rozdelením. Toto je stacionárny Poissonov tok.

Ekonomické uplatnenie Moderné finančno - bankové operácie zahŕňajú splácanie dlhu v splátkach, periodický príjem príjmov z investícií. Tento druh postupnosti alebo série platieb možno nazvať tokom platieb. Tok platieb, ktorých všetky členy sú kladné hodnoty a časové intervaly medzi platbami sú rovnaké, sa nazýva finančná renta. Nájomné je postupnosť prijímania úrokov z dlhopisov, platieb zo spotrebiteľského úveru, platieb v splátkach poistného. Charakteristika toku platieb: interval medzi dvoma susednými platbami, pravdepodobnosti platby, sa široko používajú v rôznych finančných výpočtoch. Bez nich nie je možné vypracovať plán dôsledného splácania dlhov, merať finančnú efektívnosť projektu, porovnávať či dokonca meniť zmluvné podmienky.

Výzva Aby bolo možné analyzovať zmenu veľkosti bežného fondu banky poskytujúcej dlhodobé úvery v čase, je dôležité mať informácie o procese, akým banka prijíma platby za úvery. Pozorovanie banky v predchádzajúcom období ukázalo, že počet platieb prijatých bankou za akékoľvek časové obdobie nezávisí od okamihu, od ktorého sa začalo odpočítavanie časového obdobia, ale závisí len od jeho trvania. Predpokladaný počet platieb banke za týždeň sú 2. Skúmajme pravdepodobnosť, že banka dostane 7 platieb za mesiac a nájdime pravdepodobnosť, že časový interval medzi dvoma susednými platbami je kratší ako 2 dni.

Riešenie Podľa stavu problému možno tok platieb považovať za najjednoduchší s intenzitou = 2 (za týždeň). Preto je počet prijatých platieb za časový interval = 4 týždne (1 mesiac) rozdelený podľa Poissonovho zákona. Časové intervaly medzi dvoma po sebe nasledujúcimi platbami v najjednoduchšom toku majú exponenciálny distribučný zákon.

Riešenie Nech X() je diskrétna náhodná premenná predstavujúca počet platieb prijatých za určité časové obdobie. Rozdeľuje sa podľa Poissonovho zákona. M(X)=D(X)= Potom - pravdepodobnosť, že v toku za určité obdobie nastane presne m udalostí je Preto pri intenzite toku platieb = 2 je pravdepodobnosť prijatia bankou za mesiac (=4) zo 7 platieb (m=7 ) sa rovná

Riešenie Nech je spojitá náhodná premenná T časový interval medzi akýmikoľvek dvoma susednými platbami (udalosti najjednoduchšieho toku). Má zákon o exponenciálnom rozdelení. M(T)=1/ , D(T)=1/ 2 Potom pravdepodobnosť P(T

Úlohy na samostatné riešenie 1. Študent zvyčajne prichádza na autobusovú zastávku presne o 8:00 a po nastúpení do prvého autobusu, ktorý prišiel smerom k univerzite, príde včas na vyučovanie, ktoré začína presne o 9:00. Intervaly autobusov sú v priemere 10 minút a čas jazdy autobusom je 30 minút. Nech je tok autobusov čo najjednoduchší. Nájdite pravdepodobnosť, že študent bude stále meškať na vyučovanie.

Problémy pre samostatné riešenie 2. Tok aplikácií vstupujúcich do určitého systému radenie, je dostatočne modelovaný tým najjednoduchším. Pri štúdiu experimentálnych údajov bolo uvažovaných 200 náhodne vybraných časových intervalov v dĺžke 2 minúty. Ukázalo sa, že počet tých, v ktorých neboli zaregistrované žiadne prihlášky, je 27. Nájdi očakávaná hodnota a štandardná odchýlka počtu aplikácií za 1 hodinu.

Základné pojmy Pod systémom S rozumieme akúkoľvek ucelenú množinu vzájomne prepojených prvkov, ktoré nemožno rozdeliť na samostatné podmnožiny. Ak systém S v priebehu času t zmení svoje stavy S(t) náhodne, potom hovoríme, že v sústave S prúdi náhodný proces. V každom čase je systém len v jednom zo stavov, to znamená, že pre každý čas t existuje jedinečný stav Si taký, že S(t) = Si. Množina stavov môže byť diskrétna (technický stav objektu: prevádzkyschopný - chybný, zaťažený - nečinný; počet personálu; počet objektov čakajúcich na obsluhu v rade) alebo nepretržitý (príjem, objem výroby).

Základné pojmy V prípade diskrétnej množiny stavov systém mení svoje stavy náhle (okamžite). V prípade súvislej množiny stavov dochádza k prechodu systému nepretržite (hladko). V závislosti od času, ktorý systém strávi v každom stave, sa procesy rozlišujú na diskrétny čas (umelá numerická časová mriežka) a na spojitý čas (fyzický čas, prechod systému z jedného stavu do druhého je možné uskutočniť kedykoľvek). Náhodný proces v systéme S sa nazýva Markov, ak má vlastnosť bez následkov, čo znamená, že pre každý čas t 0 závisí pravdepodobnosť akéhokoľvek stavu S(t) systému S v budúcnosti (pre t>t 0) len na jeho stave S(t 0) v súčasnosti (v t=t 0) a nezávisí od toho, ako a ako dlho sa tento proces vyvíjal v minulosti (v t>t 0).

A. A. Markov (1856 - 1922) Andrej Andrejevič Markov, starší, je vynikajúci ruský matematik, ktorý vytvoril základy teórie náhodných procesov bez následkov, ktoré sa v matematike na jeho počesť nazývajú Markovove procesy. A. A. Markov, starší, je známy aj ako ten, kto dal pravdepodobnostné zdôvodnenie metódy najmenších štvorcov (LSM), jedného z dôkazov limitnej vety teórie pravdepodobnosti a mnoho ďalších.

Typy Markovových procesov Diskrétne stavy a diskrétny čas (Markovov reťazec) Spojité stavy a diskrétny čas (Markovove postupnosti) Diskrétne stavy a spojitý čas (spojitý Markovov reťazec) Spojité stavy a spojitý čas. V praxi je väčšina problémov na Markovových procesoch popísaná pomocou Markovových reťazcov s diskrétnym alebo spojitým časom.

Markovove reťazce Markovov reťazec je postupnosť náhodných udalostí, v ktorých pravdepodobnosť každej udalosti závisí len od stavu, v ktorom sa proces práve nachádza, a nezávisí od skorších stavov.

Nastavenie Markovovho reťazca množinou stavov S = (s 1, ..., sn), udalosťou je prechod z jedného stavu do druhého ako výsledok náhodného testu vektorom počiatočných pravdepodobností (počiatočné rozdelenie) p (0) = (p(0)(1), ... , p(0)(n)), ktoré určujú pravdepodobnosť p(0)(i), že v počiatočnom čase t = 0 bol proces v stave si maticou pravdepodobností prechodu P = (pij), charakterizujúcej pravdepodobnosť prechodu procesu s aktuálnym stavom si do nasledujúceho stavu sj, pričom súčet pravdepodobností prechodov z jedného stavu je 1.

Typy Markovových reťazcov Markovov reťazec sa nazýva homogénny, ak pravdepodobnosti prechodu nezávisia od času, to znamená, že sa nemenia z kroku k na krok (k + 1). Rozložiteľné Markovove reťazce obsahujú ireverzibilné stavy nazývané pohlcovanie. Nie je možné prejsť z absorbujúceho stavu do iného. Absorbujúci stav na grafe zodpovedá vrcholu, z ktorého neodchádza žiadny oblúk. Ergodické Markovove reťazce sú popísané silne prepojeným grafom. V takomto systéme je možný prechod z akéhokoľvek stavu do akéhokoľvek stavu v konečnom počte krokov.

Účelom simulácie je určiť pravdepodobnosť, že systém bude v j-tom stave po k-tom kroku. Označte túto pravdepodobnosť - homogénny Markovov reťazec - nehomogénny Markovov reťazec

Úloha č. 1 Určitý súbor pracujúcich rodín je rozdelený do troch skupín: 1 - rodiny, ktoré nemajú auto a neplánujú si ho kúpiť; 2 - rodiny, ktoré nemajú auto, ale chystajú sa ho kúpiť a nakoniec 3 - rodiny, ktoré auto majú. Štatistické zisťovania umožnili odhadnúť pravdepodobnosť prechodu rodín z jednej skupiny do druhej v priebehu roka. V tomto prípade sa ukázalo, že prechodová matica je:

Úloha číslo 1 Nájdite: a) pravdepodobnosť, že rodina, ktorá nemala auto a nechystala sa ho kúpiť, bude o 2 roky v rovnakej situácii; b) pravdepodobnosť, že rodina, ktorá nemala auto a mieni si ho kúpiť, bude mať auto o 2 roky. (riešenie odseku (b) tejto úlohy vykonajte sami)

Riešenie úlohy č.1 zo stavov za 1 rok (vynásobenie vektora počiatočných pravdepodobností 1 stĺpcom matice pravdepodobností prechodu) (vynásobenie vektora počiatočných pravdepodobností 2 stĺpcami matice pravdepodobností prechodu) (vynásobenie vektora počiatočné pravdepodobnosti o 3 stĺpce matice pravdepodobností prechodu)

Riešenie úlohy č. 1 Vektor pravdepodobnosti dostaneme za 1 rok V našom prípade ide o 1. riadok matice pravdepodobnosti prechodu Nájdime pravdepodobnosti sústavy byť v 1. stave po 2 rokoch do 1. stĺpca matice pravdepodobnosti prechodu. matica pravdepodobnosti prechodu)

Riešenie úlohy číslo 1 Výpočty: Odpoveď: Pravdepodobnosť, že rodina, ktorá nemala auto a nechystala sa ho kúpiť, bude o 2 roky v rovnakej situácii je 0,64

Úloha č. 2 Predpokladajme, že určitá firma dodáva v Moskve zariadenia: do severného obvodu (označme A), južného (B) a centrálneho (C). Firma má skupinu kuriérov, ktorí obsluhujú tieto oblasti. Je jasné, že pri ďalšom doručení kuriér cestuje do oblasti, ktorá je tento moment bližšie k nemu. Štatisticky sa určilo nasledovné: po dodaní do A je ďalšie dodanie 30-krát do A, 30-krát do B a 40-krát do C; po doručení do B je ďalšie doručenie v 40 prípadoch do A, v 40 prípadoch do B a 20 prípadov do C; po doručení do C je ďalšia dodávka 50-krát do A, 30-krát do B a 20-krát do C. Oblasť nasledujúcej dodávky je teda určená iba predchádzajúcou dodávkou.

Úloha 2 Ak kuriér začína z centrálneho okresu, aká je pravdepodobnosť, že po vykonaní dvoch dodávok bude v južnom okrese? Vyriešte problém sami: Vytvorte maticu pravdepodobností prechodu Nakreslite graf tohto procesu Vypočítajte požadovanú pravdepodobnosť

Obmedzené pravdepodobnosti Pre ergodické reťazce s dostatočne dlhou dobou prevádzky (t smeruje k nekonečnu) nastupuje stacionárny režim, v ktorom pravdepodobnosti stavov systému nezávisia od času a nezávisia od rozdelenia pravdepodobnosti v počiatočnom momente čas. Takéto pravdepodobnosti sa nazývajú limitné (alebo konečné, stacionárne) pravdepodobnosti stavov; ukazujú priemerný relatívny čas, ktorý systém strávi v určitom stave. Napríklad, ak je hraničná pravdepodobnosť i-tého stavu pi=0. 5, to znamená, že v priemere je systém polovicu času v i-tom stave.

Limitné pravdepodobnosti Nech xi sú limitné pravdepodobnosti (i=1. . n), kde n je počet stavov. Potom sú xi jediným riešením systému lineárnych rovníc. IN tento systém obsahuje rovnice:

Príklad Matica pravdepodobnosti prechodu (počet stavov n=2) a grafický obrázok Markovov proces: Hraničné pravdepodobnosti x 1 a x 2 možno nájsť riešením sústavy

Problém č. 3 Dve autá A a B sa prenajímajú za rovnakú cenu. Tieto stroje majú nasledujúce matice pravdepodobnosti prechodu: kde 1 je stav, keď stroj funguje dobre; 2 - stav, keď stroj vyžaduje nastavenie. Určte pravdepodobnosti pre oba stroje. Aké auto by ste si mali požičať?

Úloha č. 4 Návštevník banky s úmyslom získať úver absolvuje niekoľko kontrol (uvedie): e 1 - papierovanie; e 2 - úverová história; e 3 - opakovanie; e 4 - platobná schopnosť. Podľa výsledkov kontroly sú možné dva výsledky: odmietnutie poskytnutia úveru (e 6) a získanie úveru (e 5).

Úloha č. 4 Povinná: a) opíšte tento proces ako Markovov reťazec a vytvorte prechodovú maticu (urobte to sami); b) nájdite priemerný čas na získanie pozitívneho a negatívneho výsledku (riešenie v Exceli).

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

Podmienečne je schéma prezentovaná vo formulári

A akumulátor K

servisné zariadenie

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

Prúd udalostí je sled časových momentov výskytu akýchkoľvek udalostí.

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

1) vstupný tok. Postupnosť časových bodov prijímania žiadostí

2) výstupný tok. Postupnosť časových bodov odchodu obsluhovaných požiadaviek.

3) tok služieb. Postupnosť časových bodov pre ukončenie servisných požiadaviek za predpokladu, že servis je nepretržitý.

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

Stream volaný 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.

Stream volaný homogénne, ak je x-Xia len množinou (ti) vzniknutých udalostí. Heterogénne– ak je opísaná množinou (ti, fi), kde ti sú časové momenty výskytu udalostí, fi je atribút požiadavky.

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

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

1) FIFO (prvý dovnútra - prvý von) - v poradí prijatia;

2) LIFO (posledný dnu - prvý von) - posledný prijatý je doručený ako prvý;

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

4) - prioritné systémy. (absolútne a relatívne priority. V prípade relatívnej priority sú prihlášky zoradené podľa hodnoty priority - najprv vysoká, potom nižšia.)

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

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

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

k je počet zdrojov.

A a B charakterizujú vstupný tok a obslužný tok nastavením distribučnej funkcie intervalov medzi požiadavkami vo vstupnom toku a distribučnej funkcie servisných časov.

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

D - deterministické rozdelenie;

M - orientačné;

E r je Erlangovo rozdelenie;

H r - hyper-indikatívne;

G je 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 štandardne - jeden zdroj.

9. Najjednoduchší tok, jeho vlastnosti a význam pri štúdiu sm.

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 nekonečne malá hodnota v porovnaní s pravdepodobnosťou výskytu jednej udalosti na tomto intervale.

3) Prúd sa nazýva prúd žiadny následný efekt, 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. koľko času uplynulo od poslednej udalosti.

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

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

pravdepodobnosť, že v časovom intervale τ stať sa presne m diania.

Podmienka absencie následkov (žiadosti prichádzajú nezávisle od seba) je pre najjednoduchší tok najpodstatnejšia.

Poissonovo rozdelenie.

Pravdepodobnosť, že pre žiadna udalosť nenastane

Pravdepodobnosť, že v čase nastane 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 .

Matematické očakávanie a odmocnina pre T:

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

Uveďme si stavy systému takto: systém považujeme za v stave S, ak je v systéme v čase t S zákazníkov.

Určme pravdepodobnosť pre systém, ktorého stav je určovaný iba príchodom požiadaviek, že momentálne
systém zostane v rovnakom stave. Je zrejmé, že táto pravdepodobnosť je určená skutočnosťou, že pre interval
nebudú prijímané ž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 obsluhy požiadaviek.

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

Pri pravdepodobnostnom preosievaní najjednoduchšieho toku sa získa najjednoduchší tok

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

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

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

V QS existujú dva stochastické procesy:

Príjem servisných požiadaviek;

Aplikačná služba.

Prúd udalostí- sled udalostí vyskytujúcich sa jedna po druhej v určitom časovom bode. V QS budeme rozlišovať dva prúdy:

Vstupný tok: súbor časových momentov požiadaviek vstupujúcich do systému;

Tok služby: súbor momentov, kedy systém dokončí spracovanie požiadaviek.

Vo všeobecnom prípade môže byť elementárny QS znázornený 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ý sme pri štúdiu P-schém predpokladali deterministický vstup a preosial tok služieb.

Uvažujeme, že teraz je vstupný prúd 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 požiadaviek v systéme.

Celkom možné n+3 stavy: 0 až n+2 .

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

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

vzhľadom na obyčajné

Podobne

+
=

1-
+

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

pri
dostaneme

Vzhľadom na stacionárnosť tokov máme:

A
,

Podobne pre ostatné linky systému.

Nakoniec tu máme:

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

Transformujme ju, začnime od druhej a končiac predposlednou - novú rovnicu získame pridaním starej k novej predchádzajúcej.

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

i=0, 1,….n+1

Označiť

,

Používame normalizačnú rovnicu

;

;

Toto je súčet geometrickej progresie:

Priemerný servisný čas aplikácie

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 vzormi.

Proces sa nazýva proces s diskrétnymi stavmi, ak je možné vopred vyčísliť 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 v akomkoľvek čase t0 pravdepodobnostné charakteristiky procesu v budúcnosti závisia len od jeho aktuálneho stavu t0 a nezávisia od toho, kedy a ako systém do tohto stavu prišiel.

Príklad Markovovho procesu: systém S je počítadlo v taxíku. Stav systému v čase t je charakterizovaný počtom kilometrov, ktoré automobil do tohto okamihu najazdil. Nech počítadlo ukazuje S0 v čase t0. Pravdepodobnosť, že v okamihu t>t0 bude merač ukazovať jeden alebo iný počet kilometrov (presnejšie zodpovedajúci počet rubľov) S1 závisí od S0, ale nezávisí od času, v ktorom sa hodnoty merača zmenili pred týmto okamihom. 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ých procesov s diskrétnymi stavmi je vhodné použiť geometrická schéma- takzvaný stavový graf. Zvyčajne sú stavy systému reprezentované 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, vyskytujúceho sa v QS, sa zoznámime s jedným z dôležitých konceptov teórie pravdepodobnosti – konceptom prúdu udalostí.

Prúd udalostí sa chápe ako sled homogénnych udalostí, ktoré nasledujú za sebou v určitých náhodných bodoch v čase.

Príklady môžu byť:

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

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

Prúd udalostí sa nazýva pravidelný, ak udalosti nasledujú za sebou v pravidelných intervaloch. Takýto tok je v praxi relatívne zriedkavý, ale je obzvlášť zaujímavý ako obmedzujúci prípad.

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

Prúd udalostí sa nazýva prúd bez následkov, ak pre ľubovoľné dva nepretínajúce sa časové intervaly 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 má malý až žiadny vplyv. A povedzme tok zákazníkov, ktorí odchádzajú z pultu so svojimi 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).

Prúd udalostí sa nazýva obyčajný, ak pravdepodobnosť, že dve alebo viac udalostí zasiahne malý (elementárny) časový interval?t, je zanedbateľne malá v porovnaní s pravdepodobnosťou zasiahnutia jednej udalosti. Inými slovami, prúd udalostí je obyčajný, ak sa v ňom udalosti objavujú jedna po druhej, a nie v skupinách.

Prúd udalostí je považovaný za najjednoduchší (alebo stacionárny Poisson), ak je zároveň stacionárny, obyčajný a nemá žiadne dôsledky.

Najjednoduchší tok ako limitujúci tok vzniká v teórii náhodných procesov rovnako prirodzene ako v teórii pravdepodobnosti, normálne rozdelenie sa získa 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 intenzitách). ), prietok blízky najjednoduchšiemu s intenzitou l, ktorá sa rovná súčtu intenzít prichádzajúcich 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ý interval φ 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 φ nenastane žiadna udalosť (m = 0).

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

V súlade so vzorcom sa pravdepodobnosť, že sa v časovom intervale dĺžky t neobjaví ž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 z hľadiska intenzity prietoku l.

Najdôležitejšia vlastnosť exponenciálneho rozdelenia (vlastná iba exponenciálnemu rozdeleniu) je nasledovná: ak časový interval rozdelený podľa exponenciálneho zákona už trvá nejaký čas φ, potom to nemá vplyv na zákon rozdelenia zvyšnej časti intervalu (T-φ): bude rovnaký, ako aj zákon rozdelenia celého intervalu T.

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

Pre najjednoduchší prietok s intenzitou l je pravdepodobnosť zasiahnutia aspoň jednej udalosti prietoku na elementárnom (malom) časovom intervale?t podľa

federálna agentúra podľa vzdelania Ruskej federácie

FGOU SPO "Perevozsky stavebná vysoká škola"

Práca na kurze

v disciplíne "Matematické metódy"

na tému „QS s obmedzenou čakacou dobou. Uzavreté QS»

Úvod ................................................. ................................................. .. ...... 2

1. Základy teórie radenia ...................................................... ....... 3

1.1 Pojem náhodného procesu ................................................ ............................. 3

1.2 Markov stochastický proces ................................................. ................................. 4

1.3 Streamy udalostí............................................................ ...................................................... ....... 6

1.4 Kolmogorovove rovnice pre stavové pravdepodobnosti. Konečné pravdepodobnosti stavov ................................................................ ................................................................. ...................... 9

1.5 Úlohy z teórie radenia................................................. .............. 13

1.6 Klasifikácia systémov radenia................................................................ .. 15

2. Systémy čakania v rade ................................................ ........... 16

2.1 Jednokanálová latencia QS............................................ ........................... 16

2.2 Viackanálová latencia QS ...................................... ........................... 25

3. Uzavreté QS ................................................. ............................................................. 37

Riešenie problému ................................................. .................................................... 45

Záver................................................. ................................................. 50

Bibliografia................................................... ............................................. 51

V tomto kurze sa budeme zaoberať rôznymi systémami radenia (QS) a sieťami radenia (QNS).

Systém radenia (QS) sa chápe ako dynamický systém navrhnutý tak, aby efektívne obsluhoval tok aplikácií (požiadavky na obsluhu) pri obmedzeniach systémových zdrojov.

Modely QS sú vhodné na popis jednotlivých subsystémov moderných výpočtových systémov, ako je procesor subsystému – hlavná pamäť, vstupno-výstupný kanál atď. Výpočtový systém ako celok je súborom vzájomne prepojených subsystémov, ktorých interakcia je pravdepodobnostná. Aplikácia na riešenie určitého problému, ktorý vstupuje do výpočtového systému, prechádza sekvenciou etáp počítania, prístupu k externým pamäťovým zariadeniam a vstupno-výstupným zariadeniam. Po dokončení určitej postupnosti takýchto etáp, ktorých počet a trvanie závisí od zložitosti programu, sa požiadavka považuje za obslúženú a opúšťa výpočtový systém. Výpočtový systém ako celok teda môže byť reprezentovaný súborom QS, z ktorých každý zobrazuje proces fungovania samostatného zariadenia alebo skupiny zariadení rovnakého typu, ktoré sú súčasťou systému.

Súbor vzájomne prepojených QS sa nazýva čakacia sieť (stochastická sieť).

Na začiatok zvážime základy teórie QS, potom prejdeme k oboznámeniu sa s podrobným obsahom QS s očakávaním a uzavretým QS. Súčasťou kurzu je aj praktická časť, v ktorej sa podrobne zoznámime s tým, ako aplikovať teóriu v praxi.

Teória radenia je jedným z odvetví teórie pravdepodobnosti. Táto teória uvažuje pravdepodobnostný problémy a matematické modely (predtým sme uvažovali o deterministických matematických modeloch). Pripomeňme si, že:

Deterministický matematický model odráža správanie objektu (systému, procesu) z hľadiska úplná istota v prítomnosti a budúcnosti.

Pravdepodobný matematický model berie do úvahy vplyv náhodných faktorov na správanie objektu (systému, procesu), a preto hodnotí budúcnosť z hľadiska pravdepodobnosti určitých udalostí.

Tie. tu, ako napríklad v teórii hier, sa uvažuje o problémoch v podmienkach neistota .

Uvažujme najskôr o niektorých pojmoch, ktoré charakterizujú „stochastickú neistotu“, keď neisté faktory zahrnuté do problému sú náhodné premenné (alebo náhodné funkcie), ktorých pravdepodobnostné charakteristiky sú buď známe, alebo sa dajú získať zo skúseností. Takáto neistota sa nazýva aj „priaznivá“, „benígna“.

Presne povedané, náhodné poruchy sú vlastné každému procesu. Je jednoduchšie uviesť príklady náhodného procesu ako „nenáhodného“ procesu. Dokonca aj napríklad proces chodu hodiniek (zdá sa, že ide o prísnu, dobre premyslenú prácu - „funguje ako hodiny“) podlieha náhodným zmenám (pokračovanie, zaostávanie, zastavenie). Ale pokiaľ sú tieto poruchy nevýznamné a majú malý vplyv na parametre, ktoré nás zaujímajú, môžeme ich zanedbať a považovať proces za deterministický, nenáhodný.

Nech existuje nejaký systém S(technické zariadenie, skupina takýchto zariadení, technologický systém - obrábací stroj, sekcia, dielňa, podnik, priemysel a pod.). V systéme Súniky náhodný proces, ak časom mení svoj stav (prechody z jedného stavu do druhého), navyše náhodne neznámym spôsobom.

Príklady:

1. Systém S– technologický systém (strojová časť). Stroje sa z času na čas pokazia a opravia. Proces prebiehajúci v tomto systéme je náhodný.

2. Systém S- lietadlo letiace v danej výške po určitej trati. Rušivé faktory – poveternostné podmienky, chyby posádky a pod., následky – „brblanie“, porušenie letového poriadku a pod.

Náhodný proces v systéme sa nazýva Markovského ak na akúkoľvek chvíľu t 0 pravdepodobnostné charakteristiky procesu v budúcnosti závisia len od jeho momentálneho stavu t 0 a nezávisia od toho, kedy a ako sa systém dostal do tohto stavu.

Nech je systém v určitom stave v súčasnosti t 0 S 0 Poznáme charakteristiku stavu systému v súčasnosti a všetko, čo sa počas neho udialo t <t 0 (história procesu). Dokážeme predvídať (predpovedať) budúcnosť, t.j. čo sa stane keď t >t 0? Nie presne, ale niektoré pravdepodobnostné charakteristiky procesu možno nájsť v budúcnosti. Napríklad pravdepodobnosť, že po určitom čase systém S bude schopný S 1 alebo zostať v stave S 0 atď.

Príklad. Systém S- skupina lietadiel zapojených do vzdušného boja. Nechaj X- počet „červených“ lietadiel, r- počet "modrých" lietadiel. Kým t 0 počet preživších (nezostrelených) lietadiel, resp. X 0 , r 0 Zaujíma nás pravdepodobnosť, že momentálne bude početná prevaha na strane „Červených“. Táto pravdepodobnosť závisí od stavu systému v danom čase t 0 , a nie o tom, kedy a v akom poradí zostrelení zomreli až do momentu t 0 lietadiel.

V praxi Markov spracováva v čistej forme zvyčajne nenájdené. Ale sú procesy, pri ktorých možno vplyv „praveku“ zanedbať. A pri štúdiu takýchto procesov sa dajú použiť Markovove modely (v teórii radenia sa uvažuje aj o nemarkovských systémoch radenia, ale matematický aparát, ktorý ich popisuje, je oveľa komplikovanejší).

V operačnom výskume majú veľký význam Markovove stochastické procesy s diskrétnymi stavmi a spojitým časom.

Proces sa nazýva proces diskrétneho stavu ak sú jeho možné stavy S 1 , S 2 , ... je možné určiť vopred a prechod systému zo stavu do stavu nastáva „skokom“, takmer okamžite.

Proces sa nazýva nepretržitý časový proces, ak momenty možných prechodov zo stavu do stavu nie sú vopred pevne dané, ale sú neurčité, náhodné a môžu nastať kedykoľvek.

Príklad. Technologický systém (sekcia) S pozostáva z dvoch strojov, z ktorých každý môže v náhodnom čase zlyhať (zlyhať), po čom okamžite začne oprava jednotky, ktorá tiež pokračuje neznámy, náhodný čas. Možné sú nasledujúce stavy systému:

S 0 - oba stroje fungujú;

S 1 - prvý stroj sa opravuje, druhý je prevádzkyschopný;

S 2 - druhý stroj sa opravuje, prvý je prevádzkyschopný;

S 3 - oba stroje sú v oprave.

Systémové prechody S zo stavu do stavu sa vyskytujú takmer okamžite, v náhodných okamihoch zlyhania jedného alebo druhého stroja alebo dokončenia opráv.

Pri analýze náhodných procesov s diskrétnymi stavmi je vhodné použiť geometrickú schému - stavový graf. Vrcholy grafu sú stavy systému. Oblúky grafu sú možné prechody zo stavu do stavu. Pre náš príklad je stavový graf znázornený na obr. 1.

Ryža. 1. Graf stavov systému

Poznámka. Prechod štátu S 0 palcov S 3 nie je na obrázku vyznačená, pretože predpokladá sa, že stroje zlyhajú nezávisle od seba. Zanedbáme pravdepodobnosť súčasného zlyhania oboch strojov.

Prúd udalostí- sled homogénnych dejov nasledujúcich po sebe v určitom náhodnom čase.

V predchádzajúcom príklade ide o tok zlyhania a tok obnovy. Ďalšie príklady: tok hovorov v telefónnej ústredni, tok zákazníkov v predajni atď.

Tok udalostí je možné vizualizovať pomocou série bodov na časovej osi O t- ryža. 2.

Ryža. 2. Obraz toku udalostí na časovej osi

Poloha každého bodu je náhodná a je tu zobrazená iba jedna implementácia toku.

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

Uvažujme o niektorých vlastnostiach (typoch) tokov udalostí.

Prúd udalostí je tzv stacionárne, ak jeho pravdepodobnostné charakteristiky nezávisia od času.

Najmä intenzita stacionárneho prúdenia je konštantná. Tok udalostí má nevyhnutne koncentrácie alebo zriedkavosť, ale nie sú pravidelného charakteru a priemerný počet udalostí za jednotku času je konštantný a nezávisí od času.

Prúd udalostí je tzv plynúť bez následkov, ak pre ľubovoľné dva nepretínajúce sa časové intervaly a (pozri obr. 2) počet udalostí, ktoré pripadajú na jeden z nich, nezávisí od toho, koľko udalostí pripadá na druhý. Inými slovami to znamená, že udalosti, ktoré tvoria prúd, sa objavujú v určitých časových bodoch. nezávisle od seba a každý zo svojich dôvodov.

Prúd udalostí je tzv obyčajný, ak sa udalosti v ňom objavujú jednotlivo, a nie v skupinách viacerých naraz.

Prúd udalostí je tzv najjednoduchšie (alebo stacionárne Poisson), ak má tri vlastnosti naraz:

1) stacionárne;

2) obyčajný;

3) nemá žiadne následky.

Najjednoduchší tok má najjednoduchší matematický popis. Medzi tokmi hrá rovnakú osobitnú úlohu, ako aj zákon normálneho rozdelenia medzi inými zákonmi rozdelenia. Totiž, keď sa superponuje dostatočne veľký počet nezávislých, stacionárnych a obyčajných tokov (vzájomne porovnateľných v intenzite), získa sa tok blízky tomu najjednoduchšiemu.

Pre najjednoduchšie prúdenie s intervalom intenzity T medzi susednými podujatiami má tzv exponenciálne (exponenciálne) rozdelenie s hustotou:

kde je parameter exponenciálneho zákona.

Pre náhodnú premennú T, ktorá má exponenciálne rozdelenie, matematické očakávanie je prevrátená hodnota parametra a štandardná odchýlka sa rovná matematickému očakávaniu:

Vzhľadom na Markovove procesy s diskrétnymi stavmi a nepretržitým časom sa rozumie, že všetky prechody systému S zo stavu do stavu sa vyskytujú pod vplyvom najjednoduchších tokov udalostí (toky hovorov, toky porúch, toky obnovy atď.). Ak všetky prúdy udalostí prekladajú systém S zo stavu do stavu najjednoduchšieho, potom proces vyskytujúci sa v systéme bude markovovský.

Takže systém v štáte je ovplyvnený najjednoduchším tokom udalostí. Hneď ako sa objaví prvá udalosť tohto toku, systém „skočí“ zo stavu do stavu (na grafe stavu pozdĺž šípky ).

Pre prehľadnosť je na grafe stavov systému každý oblúk označený intenzitou toku udalostí, ktorá prenáša systém pozdĺž tohto oblúka (šípka). - intenzita toku udalostí, prenášajúcich systém zo stavu do . Takýto graf je tzv označené. Pre náš príklad je označený graf znázornený na obr. 3.

Ryža. 3. Označený graf stavu systému

Na tomto obrázku - intenzita toku porúch; - intenzita regeneračného toku.

Predpokladáme, že priemerný čas opravy stroja nezávisí od toho, či sa opravuje jeden stroj alebo oba naraz. Tie. Každý stroj opravuje samostatný špecialista.

Nech je systém v stave S 0 V stave S 1 je preložený prúdom porúch prvého stroja. Jeho intenzita je:

kde je priemerná doba prevádzky prvého stroja.

Mimo štátu S 1 palec S 0 sa systém prenesie tokom „koncov opráv“ prvého stroja. Jeho intenzita je:

kde je priemerný čas opravy prvého stroja.

Podobne sa vypočítajú intenzity tokov udalostí, ktoré prenášajú systém pozdĺž všetkých oblúkov grafu. Majúc k dispozícii označený graf stavov systému, a matematický model tento proces.

Nechajte zvažovaný systém S má -možné stavy . Pravdepodobnosť tého stavu je pravdepodobnosť, že v danom čase bude systém v stave. Je zrejmé, že v každom časovom okamihu sa súčet všetkých pravdepodobností stavu rovná jednej:

Aby sme našli všetky pravdepodobnosti stavov ako funkcie času, skladáme a riešime Kolmogorovove rovnice – zvláštny druh rovnice, v ktorých sú neznáme funkcie pravdepodobnosti stavov. Uvádzame tu pravidlo na zostavenie týchto rovníc bez dôkazu. Ale predtým, ako ho predstavíme, vysvetlíme tento pojem pravdepodobnosť konečného stavu .

Čo sa stane s pravdepodobnosťami stavov pri ? Budú sa snažiť o nejaké limity? Ak tieto limity existujú a nezávisia od počiatočného stavu systému, potom sa volajú pravdepodobnosti konečného stavu .

kde je konečný počet stavov systému.

Pravdepodobnosti konečného stavu už nie sú premenné (funkcie času), ale konštantné čísla. Je zrejmé, že:

Pravdepodobnosť konečného stavu je v podstate priemerný relatívny čas, ktorý systém strávi v tomto stave.

Napríklad systém S má tri štáty S 1 , S 2 a S 3. Ich konečná pravdepodobnosť je 0,2; 0,3 a 0,5. To znamená, že systém v hraničnom stacionárnom stave strávi v priemere 2/10 času v stave S 1 , 3/10 - schopný S 2 a 5/10 - schopný S 3 .

Pravidlo na zostavenie sústavy Kolmogorovových rovníc: v každej rovnici systému na jeho ľavej strane je konečná pravdepodobnosť tohto stavu vynásobená celkovou intenzitou všetkých tokov, vedúci z tohto stavu, A v jeho pravici časti je súčtom súčinov intenzít všetkých tokov, zahrnuté v -tý štát, o pravdepodobnosti tých štátov, z ktorých tieto toky pochádzajú.

Pomocou tohto pravidla napíšeme sústavu rovníc pre náš príklad :

.

Zdalo by sa, že tento systém štyroch rovníc so štyrmi neznámymi sa dá úplne vyriešiť. Ale tieto rovnice sú homogénne (nemajú voľný člen), a preto určujú neznáme len do ľubovoľného faktora. Môžete však použiť podmienku normalizácie: a použiť ho na riešenie systému. V tomto prípade môže byť jedna (ktorákoľvek) z rovníc vyradená (nasleduje ako dôsledok ostatných).

Pokračovanie príkladu. Nech sa hodnoty intenzít prúdenia rovnajú: .

Štvrtú rovnicu zahodíme a namiesto toho pridáme podmienku normalizácie:

.

Tie. v obmedzujúcom, stacionárnom režime systému S v priemere strávi 40 % času v štáte S 0 (oba stroje sú v dobrom stave), 20% - v dobrom stave S 1 (prvý stroj je v oprave, druhý funguje), 27% - v dobrom stave S 2 (druhý stroj je v oprave, prvý funguje), 13% - v stave S 3 (oba stroje sú v oprave). Znalosť týchto konečné pravdepodobnosti môže pomôcť odhadnúť priemernú účinnosť systému a zaťaženie reparačných orgánov.

Nechajte systém S schopný S 0 (plne prevádzkyschopný) prináša za jednotku času príjem 8 konvenčných jednotiek, v stave S 1 - príjem 3 konvenčné jednotky, schopný S 2 – príjem 5 konvenčných jednotiek, schopných S 3 - nevytvára príjem. Potom sa v obmedzujúcom, stacionárnom režime bude priemerný príjem za jednotku času rovnať: konvenčným jednotkám.

Stroj 1 sa opravuje na zlomok času, ktorý sa rovná: . Stroj 2 sa opravuje za zlomok času, ktorý sa rovná: . Vyvstáva optimalizačný problém. Predpokladajme, že môžeme znížiť priemerný čas opravy prvého alebo druhého stroja (alebo oboch), ale bude nás to stáť určitú sumu. Otázkou je, či zvýšenie príjmov spojené s rýchlejšími opravami zaplatí zvýšené náklady na opravy? Bude potrebné vyriešiť sústavu štyroch rovníc so štyrmi neznámymi.

Príklady systémov radenia (QS): telefónne ústredne, opravovne, pokladne, informačné pulty, obrábacie stroje a iné technologické systémy, flexibilné systémy riadenia výrobných systémov atď.

Každý QS pozostáva z určitého počtu servisných jednotiek, ktoré sa volajú servisné kanály(ide o obrábacie stroje, transportné vozíky, roboty, komunikačné linky, pokladníkov, predajcov a pod.). Každý QS je navrhnutý tak, aby slúžil niektorým aplikačný tok(požiadavky) prichádzajúce v určitom náhodnom čase.

Služba požiadavky pokračuje nejaký, všeobecne povedané, náhodný čas, po ktorom sa kanál uvoľní a je pripravený prijať ďalšiu požiadavku. Náhodný charakter toku požiadaviek a servisného času vedie k tomu, že v niektorých časových úsekoch sa na vstupe QS nahromadí zbytočne veľa požiadaviek (buď vstúpia do frontu, alebo nechajú QS neobslúžené). V iných obdobiach bude QS pracovať s nízkym zaťažením alebo dokonca nečinne stáť.

Proces operácie QS je náhodný proces s diskrétnymi stavmi a nepretržitým časom. Stav QS sa náhle mení v momentoch výskytu niektorých udalostí (príchod novej požiadavky, ukončenie služby, moment, keď požiadavka, ktorá je unavená z čakania, opustí front).

Predmet teórie radenia– konštrukcia matematických modelov, ktoré spájajú dané prevádzkové podmienky QS (počet kanálov, ich výkonnosť, prevádzkové pravidlá, charakter toku požiadaviek) s charakteristikami, ktoré nás zaujímajú - ukazovatele výkonnosti QS. Tieto ukazovatele opisujú schopnosť SOT vyrovnať sa s tokom žiadostí. Môžu to byť: priemerný počet aplikácií obsluhovaných QS za jednotku času; priemerný počet obsadených kanálov; priemerný počet žiadostí vo fronte; priemerná doba čakania na obsluhu atď.

Matematická analýza práce QS je značne uľahčená, ak je proces tejto práce markovovský, t.j. toky udalostí, ktoré prenášajú systém zo stavu do stavu, sú najjednoduchšie. V opačnom prípade sa matematický popis procesu veľmi skomplikuje a len zriedka je možné priviesť ho do špecifických analytických závislostí. V praxi sa nemarkovské procesy redukujú na markovovské procesy s aproximáciou. Nasledujúci matematický aparát popisuje Markovove procesy.

Prvá divízia (podľa prítomnosti radov):

1. QS s poruchami;

2. CMO s radom.

V CMO s poruchami požiadavka, ktorá príde v momente, keď sú všetky kanály obsadené, je odmietnutá, opustí QS a nie je ďalej obsluhovaná.

V CMO s radom aplikácia, ktorá príde v čase, keď sú všetky kanály obsadené, neodíde, ale zaradí sa do frontu a čaká na príležitosť.

QS s frontami sú rozdelené na odlišné typy v závislosti od toho, ako je usporiadaný rad - obmedzené alebo neobmedzené. Obmedzenia sa môžu týkať ako dĺžky radu, tak čakacej doby, „obslužnej disciplíny“.

Do úvahy sa teda berú napríklad tieto QS:

· QS s netrpezlivými požiadavkami (dĺžka frontu a servisný čas sú obmedzené);

· QS s prednostnou službou, t.j. niektoré aplikácie sú podávané mimo poradia atď.

Okrem toho sa QS delia na otvorené QS a uzavreté QS.

V otvorenom CMO charakteristiky toku aplikácií nezávisia od stavu samotného QS (koľko kanálov je obsadených). V uzavretom QS- závisieť. Ak napríklad jeden pracovník obsluhuje skupinu strojov, ktoré si z času na čas vyžadujú úpravu, potom intenzita toku „požiadaviek“ zo strojov závisí od toho, koľko z nich je už v poriadku a čaká na úpravu.

Klasifikácia SOT sa zďaleka neobmedzuje na vyššie uvedené odrody, ale to stačí.

Zvážte najjednoduchší QS s očakávaním - jednokanálový systém (n - 1), ktorý prijíma tok požiadaviek s intenzitou; intenzita služby (t.j. v priemere nepretržite obsadený kanál bude vydávať obsluhované požiadavky na jednotku (čas). Požiadavka, ktorá prišla v momente, keď je kanál zaneprázdnený, sa zaradí do frontu a čaká na obsluhu.

Systém s obmedzenou dĺžkou frontu. Predpokladajme najskôr, že počet miest v rade je obmedzený počtom m, t.j. ak zákazník príde v čase, keď je v rade už m-zákazníkov, nechá systém bez obsluhy. V budúcnosti, ak m smeruje k nekonečnu, získame charakteristiky jednokanálového QS bez obmedzenia dĺžky frontu.

Stavy QS očíslujeme podľa počtu požiadaviek v systéme (obsluhovaných aj čakajúcich na obsluhu):

Kanál je bezplatný;

Kanál je zaneprázdnený, nie je tam žiadny front;

Kanál je zaneprázdnený, jedna aplikácia je vo fronte;

Kanál je zaneprázdnený, vo fronte je k-1 požiadaviek;

Kanál je zaneprázdnený, t-aplikácie sú vo fronte.

GSP je znázornený na obr. 4. Všetky intenzity tokov udalostí, ktoré sa prenášajú do systému pozdĺž šípok zľava doprava, sú rovnaké a sprava doľava - . V skutočnosti sa podľa šípok zľava doprava systém prenáša tokom požiadaviek (hneď ako príde požiadavka, systém prejde do ďalšieho stavu), sprava doľava - tok „uvoľnení“ obsadený kanál, ktorý má intenzitu (akonáhle bude doručená ďalšia požiadavka, kanál sa buď uvoľní, alebo zníži počet aplikácií vo fronte).

Ryža. 4. Jednokanálové QS s čakaním

Znázornené na obr. 4 schéma je schéma reprodukcie a smrti. Napíšme výrazy pre limitné pravdepodobnosti stavov:

(5)

alebo pomocou: :

(6)

Posledný riadok v (6) obsahuje geometrickú postupnosť s prvým členom 1 a menovateľom p, z čoho dostaneme:

(7)

v súvislosti s ktorými majú okrajové pravdepodobnosti tvar:

(8).

Výraz (7) platí len pre< 1 (при = 1 она дает неопределенность вида 0/0). Сумма геометрической прогрессии со знаменателем = 1 равна m+2, и в этом случае:

Definujme charakteristiky QS: pravdepodobnosť zlyhania, relatívna priepustnosť q, absolútna priepustnosť A, priemerná dĺžka frontu, priemerný počet aplikácií spojených so systémom, priemerná doba čakania vo fronte, priemerný čas zotrvania aplikácie v QS.

Pravdepodobnosť zlyhania. Je zrejmé, že požiadavka je zamietnutá iba v prípade, keď je kanál zaneprázdnený a všetky m-miesta vo fronte sú tiež:

(9).

Relatívna priepustnosť:

(10).

Priemerná dĺžka frontu. Nájdite priemerný počet -aplikácií vo fronte ako matematické očakávanie diskrétnej náhodnej premennej R-počet aplikácií vo fronte:

S pravdepodobnosťou je jedna aplikácia vo fronte, s pravdepodobnosťou - dve aplikácie, vo všeobecnosti s pravdepodobnosťou existuje k-1 aplikácií vo fronte atď., odkiaľ:

(11).

Keďže súčet v (11) možno považovať za derivát vzhľadom na súčet geometrickej progresie:

Nahradením tohto výrazu do (11) a použitím z (8) nakoniec dostaneme:

(12).

Priemerný počet nárokov v systéme. Ďalej získame vzorec pre priemerný počet požiadaviek spojených so systémom (vo fronte aj v prevádzke). Keďže , kde je priemerný počet aplikácií v prevádzke, ak je známe k, zostáva určiť . Keďže existuje iba jeden kanál, počet obsluhovaných požiadaviek môže byť 0 (s pravdepodobnosťou ) alebo 1 (s pravdepodobnosťou 1 - ), odkiaľ:

.

a priemerný počet aplikácií spojených s QS je:

(13).

Priemerná doba čakania na žiadosť vo fronte. Označme to; ak zákazník príde do systému v určitom okamihu, potom pravdepodobne servisný kanál nebude obsadený a nebude musieť stáť v rade (čakacia doba je nula). Je pravdepodobné, že príde do systému počas obsluhy nejakej požiadavky, ale nebude pred ňou fronta a požiadavka bude čakať na spustenie svojej služby určitý čas (priemerný čas na obsluhu jednej žiadosť). Je pravdepodobné, že pred uvažovanou žiadosťou bude v rade ešte jeden a priemerná doba čakania sa bude rovnať , atď.

Ak k=m+1, t.j. keď novo prichádzajúci zákazník zistí, že obslužný kanál je obsadený a vo fronte je m-zákazníkov (pravdepodobnosť je ), potom v tomto prípade zákazník nestojí v rade (a nie je obsluhovaný), takže čakacia doba je nulová. Priemerná čakacia doba bude:

ak tu dosadíme výrazy za pravdepodobnosti (8), dostaneme:

(14).

Tu sú použité vzťahy (11), (12) (derivácia geometrickej postupnosti), ako aj z (8). Porovnaním tohto výrazu s (12) si všimneme, že inými slovami, priemerný čas čakania sa rovná priemernému počtu žiadostí vo fronte vydelenému intenzitou toku žiadostí.

(15).

Priemerný čas zotrvania požiadavky v systéme. Označme - očakávanie náhodnej veličiny - čas zotrvania aplikácie v QS, ktorý je súčtom priemerného času čakania v rade a priemerného času obsluhy . Ak je zaťaženie systému 100 %, samozrejme, inak:

.

Príklad 1 Čerpacia stanica(AZS) je QS s jedným servisným kanálom (jeden stĺpec).

Miesto na stanici umožňuje, aby v rade na tankovanie zostali naraz maximálne tri autá (m = 3). Ak sú v rade už tri autá, ďalšie auto, ktoré príde na stanicu, sa do radu nezaradí. Tok áut prichádzajúcich na tankovanie má intenzitu = 1 (auto za minútu). Proces tankovania trvá v priemere 1,25 minúty.

Definuj:

pravdepodobnosť zlyhania;

relatívna a absolútna kapacita čerpacích staníc;

priemerný počet áut čakajúcich na doplnenie paliva;

priemerný počet áut na čerpacej stanici (vrátane servisovaných);

priemerná doba čakania na auto v rade;

priemerný čas, počas ktorého auto stojí na čerpacej stanici (vrátane servisu).

Inými slovami, priemerná čakacia doba sa rovná priemernému počtu žiadostí vo fronte vydelenému intenzitou toku žiadostí.

Najprv zistíme zníženú intenzitu toku aplikácií: =1/1,25=0,8; = 1/0,8 = 1,25.

Podľa vzorcov (8):

Pravdepodobnosť zlyhania je 0,297.

Relatívna kapacita QS: q=1-=0,703.

Absolútna priepustnosť QS: A==0,703 auta za minútu.

Priemerný počet áut v rade sa zistí podľa vzorca (12):

tie. priemerný počet áut čakajúcich v rade na čerpaciu stanicu je 1,56.

K tejto hodnote sa pripočíta priemerný počet áut v prevádzke:

dostaneme priemerný počet áut spojených s čerpacou stanicou.

Priemerná doba čakania na auto v rade podľa vzorca (15):

Pripočítaním tejto hodnoty dostaneme priemerný čas, ktorý auto strávi na čerpacej stanici:

Systémy s neobmedzeným čakaním. V takýchto systémoch nie je hodnota m obmedzená, a preto hlavné charakteristiky možno získať prechodom na limit v predtým získaných výrazoch (5), (6) atď.

Všimnite si, že v tomto prípade je menovateľ v poslednom vzorci (6) súčtom nekonečného počtu členov geometrickej postupnosti. Tento súčet konverguje, keď progresia nekonečne klesá, t.j. pri<1.

Dá sa to dokázať<1 есть условие, при котором в СМО с ожиданием существует предельный установившийся режим, иначе такого режима не существует, и очередь при будет неограниченно возрастать. Поэтому в дальнейшем здесь предполагается, что <1.

Ak, potom vzťahy (8) majú tvar:

(16).

Ak neexistujú žiadne obmedzenia týkajúce sa dĺžky frontu, každá požiadavka, ktorá príde do systému, bude obsluhovaná, preto q=1, .

Priemerný počet žiadostí vo fronte sa získa z (12) pomocou:

Priemerný počet aplikácií v systéme podľa vzorca (13) pre:

.

Priemerný čas čakania získame zo vzorca (14) pre:

.

Napokon, priemerný čas zotrvania aplikácie v QS je:

Systém s obmedzenou dĺžkou frontu. Zvážte kanál QS s čakaním, ktorý prijíma tok požiadaviek s intenzitou; intenzita služby (pre jeden kanál) ; počet miest v rade.

Stavy systému sú očíslované podľa počtu požiadaviek pripojených systémom:

žiadny rad:

Všetky kanály sú bezplatné;

Jeden kanál je obsadený, ostatné sú voľné;

Obsadené kanály, ostatné nie sú;

Všetky kanály sú obsadené, nie sú žiadne voľné;

je tam rad:

Všetky n-kanály sú obsadené; jedna aplikácia je vo fronte;

Všetky n-kanály sú obsadené, r-požiadavky vo fronte;

Všetky n-kanály sú obsadené, r-objednávky sú vo fronte.

GSP je znázornený na obr. 17. Každá šípka má zodpovedajúce intenzity tokov udalostí. Podľa šípok zľava doprava sa systém prenáša vždy rovnakým tokom požiadaviek s intenzitou , podľa šípok sprava doľava sa systém prenáša servisným tokom, ktorého intenzita sa rovná, násobená podľa počtu obsadených kanálov.

Ryža. 17. Viackanálové QS s čakaním

Graf je typický pre procesy reprodukcie a smrti, pre ktoré bolo predtým získané riešenie. Napíšme výrazy pre limitné pravdepodobnosti stavov pomocou zápisu : (tu používame výraz pre súčet geometrickej postupnosti s menovateľom ).

Takto sú nájdené všetky pravdepodobnosti stavu.

Definujme charakteristiky účinnosti systému.

Pravdepodobnosť zlyhania. Prichádzajúca požiadavka je odmietnutá, ak sú všetky n-kanály a všetky m-miesta vo fronte obsadené:

(18)

Relatívna priepustnosť dopĺňa pravdepodobnosť zlyhania na jednu:

Absolútna priepustnosť QS:

(19)

Priemerný počet obsadených kanálov. V prípade CMO s poruchami sa zhodoval s priemerným počtom žiadostí v systéme. Pre QS s frontom sa priemerný počet obsadených kanálov nezhoduje s priemerným počtom požiadaviek v systéme: posledná hodnota sa líši od prvej o priemerný počet požiadaviek vo fronte.

Označme priemerný počet obsadených kanálov. Každý obsadený kanál obsluhuje v priemere - požiadavky za jednotku času a QS ako celok obsluhuje v priemere A - žiadostí za jednotku času. Rozdelením jedného druhým dostaneme:

Priemerný počet požiadaviek vo fronte možno vypočítať priamo ako matematické očakávanie diskrétnej náhodnej premennej:

(20)

Aj tu (výraz v zátvorkách) nastáva derivácia súčtu geometrickej progresie (pozri vyššie (11), (12) - (14)), pomocou pomeru dostaneme:

Priemerný počet aplikácií v systéme:

Priemerná doba čakania na žiadosť vo fronte. Uvažujme o niekoľkých situáciách, ktoré sa líšia v tom, v akom stave systém nájde nová požiadavka a ako dlho bude musieť čakať na obsluhu.

Ak zákazník nenájde všetky kanály obsadené, nebude musieť vôbec čakať (zodpovedajúce výrazy v matematickom očakávaní sú rovné nule). Ak požiadavka príde v momente, keď sú všetky n-kanály obsadené a nie je tam žiadny front, bude musieť čakať v priemere rovnajúci sa čas (pretože „tok uvoľnenia“ -kanálov má intenzitu ). Ak zákazník zistí, že všetky kanály sú obsadené a jeden zákazník pred ním v rade, bude musieť čakať v priemere určitý čas (na každého ďalšieho zákazníka) atď. Ak zákazník nájde - zákazníkov v rade, bude musieť v priemere počkať. Ak novo prichádzajúci zákazník nájde vo fronte už m-zákazníkov, tak nepočká vôbec (ale ani nebude obsluhovaný). Priemerný čas čakania zistíme vynásobením každej z týchto hodnôt zodpovedajúcimi pravdepodobnosťami:

(21)

Rovnako ako v prípade jednokanálového QS s čakaním poznamenávame, že tento výraz sa od výrazu pre priemernú dĺžku frontu (20) líši len faktorom , t.j.

.

Priemerný čas zotrvania požiadavky v systéme, ako aj pre jednokanálový QS, sa líši od priemerného času čakania priemerným časom služby vynásobeným relatívnou priepustnosťou:

.

Systémy s neobmedzenou dĺžkou frontu. Uvažovali sme o kanálovom QS s čakaním, kedy v rade nemôže byť súčasne viac ako m zákazníkov.

Rovnako ako predtým, pri analýze systémov bez obmedzení je potrebné uvažovať získané vzťahy pre .

Pravdepodobnosti stavov získame zo vzorcov prechodom k limite (v ). Všimnite si, že súčet zodpovedajúcej geometrickej progresie konverguje a diverguje pri >1. Za predpokladu, že<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:

(22)

Pravdepodobnosť poruchy, relatívna a absolútna priepustnosť. Keďže každá požiadavka bude doručená skôr alebo neskôr, charakteristiky priepustnosti QS budú:

Priemerný počet žiadostí vo fronte sa získa z (20):

,

a priemerná doba čakania je od (21):

.

Priemerný počet obsadených kanálov, ako predtým, sa určuje z hľadiska absolútnej priepustnosti:

.

Priemerný počet zákazníkov priradených k QS je definovaný ako priemerný počet zákazníkov v rade plus priemerný počet zákazníkov v službe (priemerný počet vyťažených kanálov):

Príklad 2. Čerpacia stanica s dvoma výdajnými stojanmi (n = 2) obsluhuje tok áut s rýchlosťou = 0,8 (vozov za minútu). Priemerný servisný čas na stroj:

Iná čerpacia stanica sa v okolí nenachádza, takže rad áut pred čerpacou stanicou sa môže zväčšovať takmer donekonečna. Nájdite vlastnosti QS.

Pretože<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:

atď.

Priemerný počet obsadených kanálov zistíme vydelením absolútnej priepustnosti QS A==0,8 intenzitou služby=0,5:

Pravdepodobnosť, že na čerpacej stanici nebude žiadny rad, bude:

Priemerný počet áut v rade:

Priemerný počet áut na čerpacích staniciach:

Priemerná doba čakania v rade:

Priemerný čas, kedy auto stojí na čerpacej stanici:

CMO s obmedzenou čakacou dobou. Predtým sme uvažovali o systémoch s čakaním obmedzeným len dĺžkou frontu (počet m-zákazníkov súčasne vo fronte). V takomto QS nárok, ktorý sa rozrástol do radu, ho neopustí, kým nečaká na službu. V praxi existujú QS iného typu, pri ktorých aplikácia po určitom čase môže opustiť rad (tzv. „netrpezlivé“ aplikácie).

Zvážte QS tohto typu za predpokladu, že obmedzenie čakacej doby je náhodná premenná.

Predpokladajme, že máme n-kanálový čakací QS, kde počet miest v rade nie je obmedzený, ale čas, keď zákazník zostane v rade, je náhodná premenná s priemernou hodnotou, takže každý zákazník v rade je vystavený druh Poissonovho "toku starostlivosti" s intenzitou:

Ak je tento tok Poisson, potom proces vyskytujúci sa v QS bude Markov. Nájdite pre to pravdepodobnosti stavov. Číslovanie stavov systému je spojené s počtom požiadaviek v systéme – obsluhovaných aj vo fronte:

žiadny rad:

Všetky kanály sú bezplatné;

Jeden kanál je obsadený;

Dva kanály sú obsadené;

Všetky n-kanály sú obsadené;

je tam rad:

Všetky n-kanály sú obsadené, jedna aplikácia je vo fronte;

Všetky n-kanály sú zaneprázdnené, r-požiadavky sú vo fronte atď.

Graf stavov a prechodov sústavy je na obr. 23.

Ryža. 23. QS s obmedzenou čakacou dobou

Označme tento graf ako predtým; všetky šípky vedúce zľava doprava budú mať intenzitu toku aplikácií. Pre stavy bez frontu budú mať šípky vedúce z nich sprava doľava, ako predtým, celkovú intenzitu obslužného toku všetkých vyťažených kanálov. Pokiaľ ide o stavy s radom, šípky vedúce z nich sprava doľava budú mať celkovú intenzitu toku služieb všetkých n-kanálov plus zodpovedajúcu intenzitu toku opúšťania radu. Ak sú vo fronte r-objednávky, potom sa celková intenzita toku odchodov bude rovnať .

Ako je možné vidieť z grafu, existuje vzor reprodukcie a smrti; aplikovaním všeobecných výrazov pre obmedzujúce pravdepodobnosti stavov v tejto schéme (použitím skrátenej notácie píšeme:

(24)

Všimnime si niektoré vlastnosti QS s obmedzeným čakaním v porovnaní s predtým zvažovanými QS s požiadavkami „pacientov“.

Ak dĺžka frontu nie je obmedzená a zákazníci sú „trpezliví“ (neopúšťajú front), potom režim stacionárneho limitu existuje iba v prípade (pre , sa príslušná nekonečná geometrická progresia rozchádza, čo fyzicky zodpovedá neobmedzenému rastu v rade na ).

Naopak, pri QS s „netrpezlivými“ zákazníkmi, ktorí skôr či neskôr opustia rad, sa vždy dosiahne ustálený režim služby, bez ohľadu na zníženú intenzitu toku zákazníkov. Vyplýva to zo skutočnosti, že rad pre v menovateli vzorca (24) konverguje pre akékoľvek kladné hodnoty a .

Pre CMO s „netrpezlivými“ aplikáciami koncept „pravdepodobnosti zlyhania“ nedáva zmysel – každá aplikácia sa dostane do radu, ale nemusí čakať na službu a odíde v predstihu.

Relatívna priepustnosť, priemerný počet aplikácií vo fronte. Relatívna priepustnosť q takéhoto QS sa môže vypočítať nasledovne. Je zrejmé, že všetky aplikácie budú doručené, s výnimkou tých, ktoré opustia front v predstihu. Vypočítajme priemerný počet žiadostí, ktoré opustia front v predstihu. Na tento účel vypočítame priemerný počet žiadostí vo fronte:

Pre každú z týchto požiadaviek existuje „tok výstupov“ s intenzitou . To znamená, že z priemerného počtu -aplikácií vo fronte v priemere -aplikácie odídu bez čakania na obsluhu, -aplikácie za jednotku času a -aplikácie sa obslúžia v priemere za jednotku času. Relatívna priepustnosť QS bude:

Priemerný počet obsadených kanálov sa stále získa vydelením absolútnej priepustnosti A:

(26)

Priemerný počet aplikácií vo fronte. Vzťah (26) nám umožňuje vypočítať priemerný počet požiadaviek vo fronte bez sčítania nekonečného radu (25). Z (26) dostaneme:

a priemerný počet obsadených kanálov zahrnutých v tomto vzorci možno nájsť ako matematické očakávanie náhodnej premennej Z, ktorá nadobúda hodnoty 0, 1, 2,..., n s pravdepodobnosťami ,:

Na záver poznamenávame, že ak vo vzorcoch (24) prejdeme na limit pri (alebo, ktorý je rovnaký, pri ), získajú sa vzorce (22), t. j. „netrpezlivé“ požiadavky sa stanú „trpezlivými“.

Doteraz sme uvažovali o systémoch, v ktorých nie je prichádzajúci tok nijako prepojený s odchádzajúcim. Takéto systémy sa nazývajú otvorené. V niektorých prípadoch obsluhované požiadavky po oneskorení opäť vstupujú na vstup. Takéto QS sa nazývajú uzavreté. Príkladom uzavretých systémov je poliklinika obsluhujúca danú oblasť, tím pracovníkov priradených k skupine strojov.

V uzavretom QS cirkuluje rovnaký konečný počet potenciálnych požiadaviek. Kým sa potenciálna požiadavka nerealizuje ako požiadavka na službu, považuje sa za v oneskorenom bloku. V čase implementácie vstupuje do samotného systému. Napríklad pracovníci obsluhujú skupinu strojov. Každý stroj je potenciálnou požiadavkou, ktorá sa v momente, keď sa pokazí, zmení na skutočný. Kým stroj beží, nachádza sa v oneskorovacej jednotke a od okamihu poruchy až do konca opravy je v samotnom systéme. Každý pracovník je servisným kanálom.

Nechaj n- počet servisných kanálov, s- počet potenciálnych aplikácií, n <s , - intenzita toku aplikácií pre každú potenciálnu požiadavku, μ - intenzita služby:

Pravdepodobnosť výpadku systému je určená vzorcom

R 0 = .

Konečné pravdepodobnosti stavov systému:

P k= pri k = o .