Príklady riešenia problémov systémov radenia. Smo s zlyhaniami definícií a vzorcov

Príklady riešenia problémov systémov radenia

Musíte vyriešiť problémy 1-3. Počiatočné údaje sú uvedené v tabuľke. 2–4.

Niektoré zápisy používané v teórii radenia pre vzorce:

n – počet kanálov v QS;

λ – intenzita prichádzajúceho toku požiadaviek P in;

v – intenzita odchádzajúceho toku požiadaviek P out;

μ – intenzita obslužného toku P ob;

ρ – indikátor zaťaženia systému (premávka);

m – maximálny počet miest v rade, obmedzujúci dĺžku radu žiadostí;

i – počet zdrojov aplikácie;

p k – pravdepodobnosť k-tého stavu systému;

p o – pravdepodobnosť nečinnosti celého systému, t.j. pravdepodobnosť, že všetky kanály sú voľné;

p sys – pravdepodobnosť prijatia žiadosti do systému;

p zamietnuť – pravdepodobnosť odmietnutia prijatia žiadosti do systému;

p ob – pravdepodobnosť, že aplikácia bude obsluhovaná;

A je absolútna kapacita systému;

Q – relatívna kapacita systému;

Och – priemerný počet žiadostí vo fronte;

O – priemerný počet vybavovaných žiadostí;

Syst – priemerný počet aplikácií v systéme;

Och – priemerná doba čakania na žiadosť vo fronte;

O – priemerný čas na obsluhu aplikácie, týkajúci sa iba obsluhovaných aplikácií;

sys je priemerný čas, počas ktorého aplikácia zostáva v systéme;

Ож – priemerný časový limit čakania na žiadosť vo fronte;

– priemerný počet obsadených kanálov.

Absolútna priepustnosť QS A je priemerný počet požiadaviek, ktoré môže systém obslúžiť za jednotku času.

Relatívna kapacita QS Q je pomer priemerného počtu aplikácií obsluhovaných systémom za jednotku času k priemernému počtu aplikácií prijatých počas tohto času.

Pri riešení problémov s radom musíte dodržiavať nasledujúcu postupnosť:

1) určenie typu QS podľa tabuľky. 4,1;

2) výber vzorcov podľa typu QS;

3) riešenie problémov;

4) formulovanie záverov o probléme.

1. 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 sú možné posledné rovnice

rozhodnúť vopred formou listu. 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 možno nakresliť do jedného reťazca, v ktorom každý z priemerných stavov ( S 1 , S 2 ,…,S n-1) je prepojená priamou a spätnou šípkou s každým zo susedných štátov - vpravo a vľavo a krajnými štátmi (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, preto je užitočné raz a navždy nájsť pre ňu konečné pravdepodobnosti stavov.

Predpokladajme, že všetky toky udalostí, ktoré prenášajú systém pozdĺž šípok grafu, sú najjednoduchšie (pre stručnosť budeme systém nazývať aj S a proces v ňom prebiehajúci sú najjednoduchšie).

Pomocou grafu na obr. 19.1 budeme skladať a riešiť algebraické rovnice pre konečné pravdepodobnosti stavu), existencia vyplýva z toho, že z každého stavu možno prejsť k sebe, v konečnom počte stavov). Za prvý štát S 0 máme:

(19.1)

Pre druhý štát S1:

Na základe (19.1) je posledná rovnosť zredukovaná na formu

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

(19.2)

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

p 0 + p 1 + p 2 +…+ p n = 1. (19.3)

Poďme vyriešiť tento systém rovníc. Z prvej rovnice (19.2) vyjadríme p 1 cez R 0 :

p 1 = p 0. (19.4)

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

(19.5)

Od tretieho, berúc do úvahy (19.5),

(19.6)

a vo všeobecnosti pre kohokoľvek k(od 1 do n):

(19.7)

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

Teda všetky stavové pravdepodobnosti R 0 , s 1 , ..., р n vyjadrené prostredníctvom jedného z nich ( R 0). Dosaďte tieto výrazy do podmienky normalizácie (19.3). Chápeme, vyberáme to zo zátvoriek R 0:

odtiaľto dostaneme výraz pre R 0 :

(zátvorku sme zdvihli na mocninu -1, aby sme nepísali dvojposchodové zlomky). Všetky ostatné pravdepodobnosti sú vyjadrené prostredníctvom R 0 (pozri vzorce (19.4) - (19.7)). Všimnite si, že koeficienty pre R 0 v každom z nich nie sú nič iné ako postupné členy radu po jednom vo vzorci (19.8). Takže, počítať R 0 , všetky tieto koeficienty sme už našli.

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

^ 2. Littleov vzorec. Teraz odvodíme jeden dôležitý vzorec týkajúci sa (pre obmedzujúci, stacionárny režim) priemerného počtu aplikácií L systémy umiestnené v systéme zaraďovania (t. j. obsluhované alebo stojace vo fronte) a priemerný čas, počas ktorého žiadosť zostáva v systéme W syst.

Uvažujme o akomkoľvek QS (jednokanálový, viackanálový, Markov, nemarkovský, s neobmedzeným alebo obmedzeným frontom) a dva toky udalostí s tým spojené: tok požiadaviek prichádzajúcich na QS a tok požiadaviek odchádzajúcich. QS. Ak je v systéme zavedený obmedzujúci stacionárny režim, potom sa priemerný počet aplikácií prichádzajúcich do QS za jednotku času rovná priemernému počtu aplikácií, ktoré ho opúšťajú: oba toky majú rovnakú intenzitu λ.

Označme: X(t) - počet žiadostí, ktoré doteraz prišli na QS t. Y(t) - počet žiadostí, ktoré opustili SOT

do momentu t. Obe funkcie sú náhodné a menia sa náhle (zvýšenie o jednu), keď prídu objednávky (X(t)) a späťvzatí žiadostí (Y(t)). Typ funkcií X(t) a Y(t) znázornené na obr. 19,2; obe čiary sú stupňovité, horná je X(t), nižšie- Y(t). Samozrejme, na každú chvíľu t ich rozdiel Z(t)= X(t) - Y(t) nie je nič iné ako počet žiadostí v SOT. Keď linky X(t) A Y(t) sú zlúčené, v systéme nie sú žiadne aplikácie.

Zvážte veľmi dlhé časové obdobie T(mentálne pokračujúc v grafe ďaleko za kresbou) a vypočítajte preň priemerný počet aplikácií v QS. Bude sa rovnať integrálu funkcie Z(t) na tomto intervale vydelenom dĺžkou intervalu T:

L syst. = . (19,9) o

Tento integrál však nie je nič iné ako oblasť obrázku vytieňovaná na obr. 19.2. Pozrime sa dobre na tento výkres. Obrázok pozostáva z obdĺžnikov, z ktorých každý má výšku rovnajúcu sa jednej a základňu rovnajúcu sa času, ktorý zodpovedajúca požiadavka (prvá, druhá atď.) strávila v systéme. Označme tieto časy t 1, t 2,... Pravda, na konci intervalu T niektoré obdĺžniky vstúpia do tieňovaného obrázku nie úplne, ale čiastočne, ale s dostatočne veľkým T na týchto maličkostiach nezáleží. Môžeme teda predpokladať, že

(19.10)

kde sa suma vzťahuje na všetky žiadosti prijaté v danom čase T.

Vydeľte pravú a ľavú stranu (.19.10) dĺžkou intervalu T. Získame, berúc do úvahy (19.9),

L syst. = . (19.11)

Vydeľte a vynásobte pravú stranu (19.11) intenzitou X:

L syst. = .

Ale veľkosť Tλ nie je nič iné ako priemerný počet žiadostí prijatých v priebehu času ^ T. Ak vydelíme súčet všetkých časov t i priemerným počtom aplikácií získame priemerný čas, počas ktorého aplikácia zostáva v systéme W syst. takže,

L syst. = λ W syst. ,

W syst. = . (19.12)

Toto je Littleov úžasný vzorec: pre akýkoľvek QS, pre akúkoľvek povahu toku požiadaviek, pre akékoľvek rozloženie servisného času, pre akúkoľvek servisnú disciplínu priemerný čas, počas ktorého aplikácia zostane v systéme, sa rovná priemernému počtu aplikácií v systéme vydelenému intenzitou toku aplikácie.

Presne rovnakým spôsobom je odvodený aj druhý Littleov vzorec, ktorý vyjadruje priemerný čas, počas ktorého aplikácia zostáva vo fronte ^W veľmi dobré a priemerný počet aplikácií vo fronte L Body:

W och = . (19.13)

Pre výstup stačí namiesto spodného riadku na obr. 19.2 prevziať funkciu U(t)- počet zostávajúcich aplikácií t nie zo systému, ale z frontu (ak sa aplikácia, ktorá príde do systému, nedostane do frontu, ale okamžite prejde do prevádzky, stále môžeme predpokladať, že sa dostane do frontu, ale strávi v ňom nulový čas).

Veľkú úlohu v teórii radenia zohrávajú Littleove vzorce (19.12) a (19.13). Bohužiaľ, vo väčšine existujúcich príručiek tieto vzorce (overené vo všeobecnej forme relatívne nedávno) nie sú uvedené 1).

§ 20. Najjednoduchšie systémy radenia a ich charakteristiky

V tejto časti sa pozrieme na niektoré z najjednoduchších QS a odvodíme výrazy pre ich charakteristiky (ukazovatele výkonnosti). Zároveň predvedieme hlavné metodologické techniky charakteristické pre elementárnu, „Markovovu“ teóriu radenia. Nebudeme naháňať počet vzoriek QS, pre ktoré budú odvodené konečné vyjadrenia charakteristík; Táto kniha nie je referenčnou knihou o teórii radenia (túto úlohu oveľa lepšie plnia špeciálne príručky). Naším cieľom je predstaviť čitateľovi niekoľko „malých trikov“, ktoré uľahčujú cestu cez teóriu radenia, ktorá sa v mnohých existujúcich (dokonca sa tváriacich populárnych) knihách môže zdať ako nesúrodý súbor príkladov.

V tejto časti budeme považovať všetky toky udalostí, ktoré prenášajú QS zo stavu do stavu, za najjednoduchšie (bez toho, aby sme to zakaždým konkrétne stanovili). Medzi nimi bude takzvaný „tok služieb“. Vzťahuje sa na tok požiadaviek obsluhovaných jedným nepretržite zaneprázdneným kanálom. V tomto toku má interval medzi udalosťami, ako vždy v najjednoduchšom toku, exponenciálne rozdelenie (v mnohých príručkách namiesto toho hovoria: „čas služby je exponenciálny“; my sami budeme tento výraz používať v budúcnosti).

1) V populárnej knihe je uvedený mierne odlišný odvodený vzorec Littleovho vzorca v porovnaní s vyššie uvedeným. Vo všeobecnosti je oboznámenie sa s touto knihou („Druhá konverzácia“) užitočné na prvé oboznámenie sa s teóriou radenia.

V tejto časti bude samozrejmosťou exponenciálne rozdelenie servisného času, ako vždy pre „najjednoduchší“ systém.

Postupne predstavíme výkonnostné charakteristiky posudzovaného QS.

^ 1. P-kanálový systém radenia s poruchami(Erlangov problém). Tu sa budeme zaoberať jedným z prvých, „klasických“ problémov teórie radenia;

tento problém vznikol z praktických potrieb telefonovania a začiatkom tohto storočia ho vyriešil dánsky matematik Erlant. Problém je uvedený takto: existuje P kanály (komunikačné linky), ktoré prijímajú tok požiadaviek s intenzitou λ. Servisný tok má intenzitu μ (prevrátená hodnota priemerného servisného času t o). Nájdite konečné pravdepodobnosti stavov QS, ako aj charakteristiky jeho účinnosti:

^A - absolútna priepustnosť, t. j. priemerný počet aplikácií obsluhovaných za jednotku času;

Q- relatívna priepustnosť, t. j. priemerný podiel prichádzajúcich aplikácií obsluhovaných systémom;

^ P otvorené- pravdepodobnosť odmietnutia, t. j. že aplikácia ponechá QS neobslúženú;

k- priemerný počet obsadených kanálov.

Riešenie. Stavy systému ^S(SMO) bude očíslované podľa počtu požiadaviek v systéme (v tomto prípade sa zhoduje s počtom obsadených kanálov):

S 0 - v SOT nie je ani jedna aplikácia,

S 1 - v QS je jedna požiadavka (jeden kanál je obsadený, ostatné sú voľné),

S k - nachádza sa v SMO k aplikácie ( k kanály sú obsadené, zvyšok je voľný),

S n - nachádza sa v SMO P aplikácie (všetky n kanály sú obsadené).

Stavový graf SMO zodpovedá vzoru úhynu počas reprodukcie (obr. 20.1). Označme tento graf - označte intenzitu tokov udalostí vedľa šípok. Od S 0 palcov S 1 systém sa prenáša tokom požiadaviek s intenzitou λ (akonáhle príde požiadavka, systém skočí z S 0 V S 1). Prekladá sa rovnaký tok aplikácií

Systém z ľubovoľného ľavého stavu do susedného pravého (pozri horné šípky na obr. 20.1).

Dajme intenzity na spodné šípky. Nech je systém v stave ^S 1 (jeden kanál funguje). Produkuje μ služby za jednotku času. Umiestnite ho na šípku S 1 →S 0 intenzita μ. Teraz si predstavte, že systém je v stave S 2(fungujú dva kanály). Aby mohla ísť do S1, je potrebné, aby buď prvý kanál alebo druhý skončil servis; celková intenzita ich obslužných tokov je 2μ; Položíme ho vedľa zodpovedajúcej šípky. Celkový servisný tok poskytovaný tromi kanálmi má intenzitu 3μ, k kanály - kμ. Tieto intenzity označíme v spodných šípkach na obr. 20.1.

A teraz, keď poznáme všetky intenzity, použijeme hotové vzorce (19.7), (19.8) na konečné pravdepodobnosti v schéme smrti a reprodukcie. Pomocou vzorca (19.8) dostaneme:

Podmienky rozšírenia budú koeficienty pre p 0 vo výrazoch pre p 1

Všimnite si, že vo vzorcoch (20.1), (20.2) nie sú intenzity λ a μ zahrnuté samostatne, ale len vo forme pomeru λ/μ. Označme

λ/μ = ρ (20,3)

Hodnotu p budeme nazývať „znížená intenzita toku aplikácií“. Jeho význam je priemerný počet požiadaviek prijatých počas priemerného času obsluhy jednej požiadavky. Pomocou tohto zápisu prepíšeme vzorce (20.1), (20.2) do tvaru:

Vzorce (20.4), (20.5) pre konečné pravdepodobnosti stavov sa nazývajú Erlangove vzorce - na počesť zakladateľa teórie radenia. Väčšina ostatných vzorcov tejto teórie (dnes ich je v lese viac ako húb) nenesie žiadne špeciálne názvy.

Takto sa našli konečné pravdepodobnosti. Pomocou nich vypočítame výkonnostné charakteristiky QS. Najprv nájdeme ^ P otvorené. - pravdepodobnosť, že prichádzajúca žiadosť bude zamietnutá (nebude obsluhovaná). Na to je potrebné, aby všetko P kanály boli zaneprázdnené, čo znamená

R otvorené = R n =. (20.6)

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

Q = 1 – P OTVORENÉ = 1 – (20,7)

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

A = λQ = λ. (20.8)

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

k = 0 · p 0 + 1 · p 1 + 2 · p 2 + ... + p · pn.

Nahradenie výrazov (20.5) tu za R k, (k = 0, 1, ..., P) a vykonaním príslušných transformácií by sme nakoniec získali správny vzorec pre k. Ale odvodíme to oveľa jednoduchšie (tu je to jeden z „malých trikov“!) V skutočnosti poznáme absolútnu priepustnosť A. Nejde o nič iné ako o intenzitu toku aplikácií obsluhovaných systémom. Každá zaneprázdnená i.sal obsluhuje v priemere |l požiadaviek za jednotku času. To znamená, že priemerný počet obsadených kanálov je

k = A/μ, (20.9)

alebo, berúc do úvahy (20.8),

k = (20.10)

Odporúčame, aby si čitateľ príklad vyriešil sám. K dispozícii je komunikačná stanica s tromi kanálmi ( n= 3), intenzita toku aplikácií λ = 1,5 (aplikácie za minútu); priemerný čas na obsluhu jednej požiadavky t rev = 2 (min.), všetky toky udalostí (ako v celom tomto odseku) sú najjednoduchšie. Nájdite konečné pravdepodobnosti stavov a charakteristiky účinnosti QS: A, Q, P OTVORENÉ, k. Pre každý prípad tu sú odpovede: p 0 = 1/13, p 1 = 3/13, p 2 = 9/26, p 3 = 9/26 ≈ 0,346,

A≈ 0,981, Q ≈ 0,654, P otk ≈ 0,346, k ≈ 1,96.

Z odpovedí je mimochodom zrejmé, že naše QS je značne preťažené: z troch kanálov sú v priemere asi dva obsadené a z prichádzajúcich aplikácií zostáva asi 35 % neobslúžených. Pozývame čitateľa, ak je zvedavý a nie lenivý, aby zistil: koľko kanálov bude potrebných na uspokojenie aspoň 80% prichádzajúcich požiadaviek? A aký podiel kanálov bude nečinný?

Už je tu nejaký náznak optimalizácia. V skutočnosti údržba každého kanála za jednotku času stojí určitú sumu. Každá obsluhovaná aplikácia zároveň generuje nejaký príjem. Vynásobením tohto príjmu priemerným počtom žiadostí A, obsluhované za jednotku času, dostaneme priemerný príjem z CMO za jednotku času. Prirodzene, so zvyšujúcim sa počtom kanálov sa tento príjem zvyšuje, ale zvyšujú sa aj náklady spojené s údržbou kanálov. Čo preváži - zvýšenie príjmov alebo výdavkov? Závisí to od podmienok prevádzky, „poplatku za obsluhu aplikácie“ a nákladov na údržbu kanála. Keď poznáte tieto hodnoty, môžete nájsť optimálny počet kanálov, ktoré sú cenovo najefektívnejšie. Takýto problém nevyriešime a necháme na toho istého „nelenivého a zvedavého čitateľa“, aby vymyslel príklad a vyriešil ho. Vo všeobecnosti sa vymýšľanie problémov rozvíja viac ako riešenie tých, ktoré už niekto nastolil.

^ 2. Jednokanálový QS s neobmedzeným frontom. V praxi je celkom bežné nájsť jednokanálové lekárske služby s radom (lekár obsluhujúci pacientov; telefónny automat s jednou kabínkou; počítač vykonávajúci príkazy používateľov). V teórii radenia zaujímajú osobitné miesto aj jednokanálové QS s radom (k takýmto QS patrí väčšina doteraz získaných analytických vzorcov pre nemarkovské systémy). Preto budeme venovať osobitnú pozornosť jednokanálovým QS s frontom.

Nech existuje jednokanálový QS s radom, na ktorý nie sú kladené žiadne obmedzenia (ani na dĺžku radu, ani na čakaciu dobu). Tento QS prijíma tok požiadaviek s intenzitou λ ; servisný tok má intenzitu μ, inverznú k priemernému servisnému času požiadavky t o. Je potrebné nájsť konečné pravdepodobnosti stavov QS, ako aj charakteristiky jeho účinnosti:

L syst. - priemerný počet aplikácií v systéme,

W syst. - priemerný čas, počas ktorého aplikácia zostáva v systéme,

^ L och- priemerný počet žiadostí vo fronte,

W veľmi dobre - priemerný čas, ktorý aplikácia strávi vo fronte,

P zan - pravdepodobnosť, že kanál je zaneprázdnený (zaťaženie kanála).

Čo sa týka absolútnej priepustnosti A a relatívne Q, potom ich nie je potrebné počítať:

Vzhľadom na to, že front je neobmedzený, každá aplikácia bude skôr či neskôr obslúžená A = λ, z rovnakého dôvodu Q = 1.

Riešenie. Ako doteraz, stavy systému očíslujeme podľa počtu aplikácií v QS:

S 0 - kanál je zadarmo,

S 1 - kanál je zaneprázdnený (vybavuje požiadavku), nie je tu žiadny front,

S 2 - kanál je zaneprázdnený, jedna požiadavka je vo fronte,

S k - kanál je zaneprázdnený, k- 1 prihláška je v poradí,

Teoreticky je počet stavov neobmedzený (nekonečný). Stavový graf má tvar znázornený na obr. 20.2. Toto je schéma smrti a reprodukcie, ale s nekonečným počtom stavov. Pozdĺž všetkých šípok tok požiadaviek s intenzitou λ pohybuje systémom zľava doprava a sprava doľava - tok služieb s intenzitou μ.

V prvom rade si položme otázku, existujú v tomto prípade konečné pravdepodobnosti? Koniec koncov, počet stavov systému je nekonečný a v zásade kedy t → ∞ Fronta môže rásť donekonečna! Áno, je to tak: konečné pravdepodobnosti takéhoto QS neexistujú vždy, ale iba vtedy, keď systém nie je preťažený. Dá sa dokázať, že ak je ρ striktne menšie ako jedna (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t→ ∞ rastie bez obmedzenia. Tento fakt sa javí obzvlášť „nepochopiteľný“, keď ρ = 1. Zdalo by sa, že na systém nie sú kladené žiadne nesplniteľné požiadavky: za čas obsluhy jednej požiadavky príde v priemere jedna požiadavka a všetko by malo byť v poriadku, no v skutočnosti nie je to tak. Keď ρ = 1, QS sa vyrovná s tokom požiadaviek iba vtedy, ak je tento tok pravidelný a čas služby tiež nie je náhodný, rovný intervalu medzi požiadavkami. V tomto „ideálnom“ prípade nebude vôbec žiadny rad, kanál bude neustále zaneprázdnený a bude pravidelne vydávať servisné požiadavky. Ale akonáhle sa tok aplikácií alebo tok služieb stane čo i len trochu náhodným, front sa bude neobmedzene zvyšovať. V praxi sa to nedeje len preto, že „nekonečný počet aplikácií vo fronte“ je abstrakcia. Toto sú hrubé chyby, ktoré môžu vyplynúť z nahradenia náhodných premenných ich matematickými očakávaniami!

Ale vráťme sa k nášmu jednokanálovému QS s neobmedzeným frontom. Presne povedané, vzorce pre konečné pravdepodobnosti v schéme smrti a reprodukcie sme odvodili len pre prípad konečného počtu stavov, ale dovoľme si ich použiť pre nekonečný počet stavov. Vypočítajme konečné pravdepodobnosti stavov pomocou vzorcov (19.8), (19.7). V našom prípade bude počet členov vo vzorci (19.8) nekonečný. Získame výraz pre p 0:

p 0 = -1 =

= (1 + р + р 2 + ... + р k +….) -1 . (20.11)

Séria vo vzorci (20.11) je geometrická postupnosť. Vieme, že pre ρ< 1 ряд сходится - это бесконечно убывающая геометрическая прогрессия со знаменателем р. При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний p 0 , p 1 , ..., p k , ... existujú len u p<1). Теперь предположим, что это условие выполнено, и ρ <1. Суммируя прогрессию в (20.11), имеем

1 + ρ + ρ 2 + ... + ρ k + ... = ,

p 0 = 1 - ρ. (20.12)

Pravdepodobnosti r 1, r 2, ..., r k,... nájdete pomocou vzorcov:

p 1 = ρ p 0, p 2= ρ 2 p 0,…,p k = ρ p 0, ...,

Odkiaľ, berúc do úvahy (20.12), nakoniec nájdeme:

p 1= ρ (1 - ρ), p2= ρ2 (1 - ρ), . . . , p k =ρ k(1 - ρ), . . .(20.13)

Ako vidíte, pravdepodobnosti p 0, p 1, ..., pk,... tvoria geometrickú postupnosť s menovateľom p. Napodiv ich maximum p 0 - pravdepodobnosť, že kanál bude úplne voľný. Bez ohľadu na to, ako je systém zaťažený frontom, či sa vôbec dokáže vyrovnať s tokom požiadaviek (ρ<1), самое вероятное число заявок в системе будет 0.

Poďme zistiť priemerný počet žiadostí do CMO ^ L syst. . Tu budete musieť trochu pohrať. Náhodná hodnota Z- počet aplikácií v systéme - má možné hodnoty 0, 1, 2, .... k, ... s pravdepodobnosťami p 0, p 1, p 2, ..., p k, ... Jeho matematické očakávanie je

L systém = 0 · p 0 + 1 · p 1+2 p 2 +…+k · p k +…= (20,14)

(súčet sa neberie od 0 do ∞, ale od 1 do ∞, pretože nulový člen sa rovná nule).

Dosadíme do vzorca (20.14) výraz pre p k (20.13):

L syst. =

Teraz vezmime ρ (1-ρ) zo znamienka súčtu:

L syst. = ρ (1-ρ)

Tu opäť použijeme „malý trik“: kρ k-1 nie je nič iné ako derivácia vzhľadom na ρ z výrazu ρ k; znamená,

L syst. = ρ (1-ρ)

Obrátením operácií diferenciácie a sčítania dostaneme:

L syst. = ρ (1-ρ) (20,15)

Ale súčet vo vzorci (20.15) nie je nič iné ako súčet nekonečne klesajúcej geometrickej postupnosti s prvým členom ρ a menovateľom ρ; túto sumu

sa rovná , a jeho derivát . Nahradením tohto výrazu do (20.15) dostaneme:

L systém = . (20.16)

Teraz použijeme Littleov vzorec (19.12) a zistíme priemerný čas, počas ktorého aplikácia zostáva v systéme:

W systém = (20,17)

Poďme zistiť priemerný počet žiadostí vo fronte L veľmi dobre Budeme uvažovať takto: počet aplikácií vo fronte sa rovná počtu aplikácií v systéme mínus počet aplikácií v službe. To znamená (podľa pravidla pridávania matematických očakávaní), priemerný počet žiadostí vo fronte L och sa rovná priemernému počtu požiadaviek v systéme L syst mínus priemerný počet žiadostí v rámci služby. Počet žiadostí v rámci služby môže byť buď nula (ak je kanál voľný) alebo jedna (ak je obsadený). Matematické očakávanie takejto náhodnej premennej sa rovná pravdepodobnosti, že kanál je obsadený (označili sme to R zan). samozrejme, R zan sa rovná jednej mínus pravdepodobnosť p 0že kanál je zadarmo:

R zan = 1 - R 0 = ρ. (20.18)

Preto je priemerný počet žiadostí v rámci služby

^L asi= ρ, (20,19)

L och = L syst – ρ =

a nakoniec

L och = (20,20)

Pomocou Littleovho vzorca (19.13) zistíme priemerný čas, počas ktorého aplikácia zostáva vo fronte:

(20.21)

Boli teda nájdené všetky charakteristiky účinnosti QS.

Vyzývame čitateľa, aby si sám vyriešil príklad: jednokanálová QS je železničná zoraďovacia stanica, ktorá prijíma najjednoduchší prúd vlakov s intenzitou λ = 2 (vlaky za hodinu). Služba (rozpustenie)

zloženie trvá náhodný (orientačný) čas s priemernou hodnotou t rev = 20(min.). Príchodový park stanice má dve koľaje, na ktorých môžu prichádzajúce vlaky čakať na obsluhu; ak sú obe koľaje vyťažené, vlaky sú nútené čakať na vonkajších koľajach. Je potrebné nájsť (pre obmedzujúci, stacionárny prevádzkový režim stanice): priemer, počet vlakov l systémy spojené so stanicou, priemerný čas W systém prítomnosti vlaku v stanici (na vnútorných koľajach, na vonkajších koľajach a v údržbe), priemerný počet L Počet vlakov čakajúcich v rade na rozpustenie (bez ohľadu na to, na ktorých koľajach), priemerný čas W Pts zotrvanie vlaku v rade. Skúste tiež nájsť priemerný počet vlakov čakajúcich na rozpustenie na vonkajších koľajach L vonkajší a priemerný čas tohto čakania W ext (posledné dve veličiny súvisia podľa Littleovho vzorca). Nakoniec nájdite celkovú dennú pokutu Sh, ktorú bude musieť stanica zaplatiť za prestoje vlaku na vonkajších koľajach, ak stanica zaplatí pokutu a (ruble) za jednu hodinu prestoja jedného vlaku. Pre každý prípad tu sú odpovede: L syst. = 2 (zloženie), W syst. = 1 (hodina), L och = 4/3 (zloženie), W och = 2/3 (hodiny), L ext = 16/27 (zloženie), W ext = 8/27 ≈ 0,297 (hodín). Priemerná denná pokuta Ш za čakanie na vlaky na vonkajších koľajach sa získa vynásobením priemerného počtu vlakov prichádzajúcich do stanice za deň, priemerného času čakania na vlaky na vonkajších koľajach a hodinovej pokuty A: W ≈ 14.2 A.

^ 3. re-channel QS s neobmedzeným frontom. Celkom podobný problému 2, ale trochu komplikovanejší, problém n-kanál QS s neobmedzeným frontom. Číslovanie štátov je opäť založené na počte aplikácií v systéme:

S 0- v SMO nie sú žiadne požiadavky (všetky kanály sú bezplatné),

S 1 - jeden kanál je obsadený, zvyšok je voľný,

S 2 - dva kanály sú obsadené, zvyšok je voľný,

S k- zaneprázdnený k kanály, ostatné sú zadarmo,

S n- všetci sú zaneprázdnení P kanály (žiadny rad),

S n+1- všetci sú zaneprázdnení n kanály, jedna aplikácia je vo fronte,

S n+r - rušná váha P kanály, r aplikácie sú v rade,

Stavový graf je znázornený na obr. 20.3. Vyzývame čitateľa, aby sa zamyslel a zdôvodnil hodnoty intenzít označených šípkami. Graf Obr. 20.3

λ λ λ λ λ λ λ λ λ

μ 2μ kμ (k+1)μ nμ nμ nμ nμ nμ

existuje vzorec smrti a reprodukcie, ale s nekonečným počtom stavov. Uveďme bez dôkazu prirodzenú podmienku existencie konečných pravdepodobností: ρ/ n<1. Если ρ/n≥ 1, rad rastie do nekonečna.

Predpokladajme, že podmienka ρ/ n < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для p 0 bude séria členov obsahujúcich faktoriály plus súčet nekonečne klesajúcej geometrickej postupnosti s menovateľom ρ/ n. Keď to zhrnieme, nájdeme

(20.22)

Teraz poďme nájsť výkonnostné charakteristiky QS. Najjednoduchší spôsob, ako zistiť priemerný počet obsadených kanálov, je k== λ/μ, = ρ (všeobecne to platí pre akékoľvek QS s neobmedzeným frontom). Poďme zistiť priemerný počet aplikácií v systéme L systém a priemerný počet aplikácií vo fronte L veľmi dobre Z nich je jednoduchšie vypočítať druhú pomocou vzorca

L och =

vykonaním príslušných transformácií podľa príkladu úlohy 2

(s diferenciáciou radu) dostaneme:

L och = (20.23)

Pripočítaním priemerného počtu požiadaviek v službe (je to aj priemerný počet obsadených kanálov) k =ρ, dostaneme:

L systém = L och + ρ. (20,24)

Deliace výrazy pre L veľmi dobre L syst na λ , Pomocou Littleovho vzorca získame priemerný čas, počas ktorého aplikácia zostane vo fronte a v systéme:

(20.25)

Teraz poďme vyriešiť zaujímavý príklad. Železničná pokladňa s dvoma okienkami je dvojkanálový QS s neobmedzeným radom umiestneným pri dvoch okienkach naraz (ak sa uvoľní jedno okienko, berie ho cestujúci najbližšie v rade). Pokladňa predáva vstupenky do dvoch miest: A a IN. Intenzita toku žiadostí (cestujúcich, ktorí si chcú kúpiť lístok) pre oba body A a B je rovnaký: λ A = λ B = 0,45 (cestujúcich za minútu) a celkovo tvoria celkový tok požiadaviek s intenzitou λ A + A B = 0,9. Pokladník obsluhuje cestujúceho v priemere dve minúty. Skúsenosti ukazujú, že pri pokladniach sa hromadia rady, cestujúci sa sťažujú na pomalosť obsluhy Bol prijatý návrh racionalizácie: namiesto jednej predajne cestovných lístkov a A a v IN, vytvoriť dve špecializované pokladne (jedno okno v každej), predaj vstupeniek, jednu - len do bodky A, druhý - len k veci IN. Múdrosť tohto návrhu je kontroverzná – niektorí tvrdia, že rady zostanú rovnaké. Je potrebné preveriť užitočnosť návrhu výpočtom. Keďže môžeme vypočítať charakteristiky iba pre najjednoduchšie QS, predpokladajme, že všetky toky udalostí sú najjednoduchšie (neovplyvní to kvalitatívnu stránku záverov).

No, poďme na vec. Zvážme dve možnosti organizácie predaja vstupeniek - existujúce a navrhované.

Možnosť I (existujúca). Dvojkanálový QS prijíma tok požiadaviek s intenzitou λ = 0,9; intenzita prevádzkového toku μ = 1/2 = 0,5; ρ = λ/μ = 1,8. Pretože ρ/2 = 0,9<1, финальные вероятности существуют. По первой формуле (20.22) находим р 0 ≈ 0,0525. Priemerný počet žiadostí vo fronte sa zistí pomocou vzorca (20.23): L och ≈ 7,68; priemerný čas strávený aplikáciou vo fronte (podľa prvého zo vzorcov (20.25)) sa rovná W och ≈ 8,54 (min.).

Možnosť II (navrhovaná). Je potrebné zvážiť dva jednokanálové QS (dve špecializované okná); každý dostane tok aplikácií s intenzitou λ = 0,45; μ . stále sa rovná 0,5; p = λ/μ = 0,9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) L och = 8,1.

Toľko pre vás! Ukazuje sa, že dĺžka frontu sa nielen neznížila, ale zväčšila! Možno sa priemerná doba čakania v rade znížila? Pozrime sa. Zdieľanie L och pri λ = 0,45, dostaneme W veľmi ≈ 18 (minút).

Toľko k racionalizácii! Namiesto znižovania sa zvýšila priemerná dĺžka frontu aj priemerná doba čakania v ňom!

Skúsme hádať, prečo sa to stalo? Keď sa nad tým zamyslíme, dôjdeme k záveru: stalo sa to preto, lebo pri prvej možnosti (dvojkanálové QS) je priemerný podiel času, počas ktorého je každý z dvoch pokladníkov nečinný, kratší: ak nie je zaneprázdnený obsluhou cestujúceho kupujúceho lístok k veci A, môže sa do určitej miery zapojiť do obsluhy cestujúceho, ktorý si kupuje lístok IN, a naopak. Pri druhej možnosti takáto zameniteľnosť nie je: neobsadený pokladník len sedí so založenými rukami...

Dobre , dobre,“ čitateľ je pripravený súhlasiť, „nárast sa dá vysvetliť, ale prečo je taký významný? Je tu chyba vo výpočte?

A na túto otázku odpovieme. Nie je tam žiadna chyba. Vec je , že v našom príklade obe QS fungujú na hranici svojich možností; Akonáhle mierne zvýšite servisný čas (t. j. znížite μ), už nebudú zvládať prúd cestujúcich a rad sa začne neobmedzene zvyšovať. A „prestoje navyše“ pokladníka sú v istom zmysle ekvivalentné zníženiu jeho produktivity μ.

Výsledok výpočtov, ktorý sa na prvý pohľad zdá paradoxný (alebo dokonca jednoducho nesprávny), sa teda ukazuje ako správny a vysvetliteľný.

Teória radenia je bohatá na takéto paradoxné závery, ktorých dôvod nie je v žiadnom prípade zrejmý. Samotný autor bol opakovane „prekvapený“ výsledkami výpočtov, ktoré sa neskôr ukázali ako správne.

Keď sa zamyslíme nad posledným problémom, čitateľ si môže položiť otázku takto: koniec koncov, ak pokladňa predáva lístky len do jedného bodu, potom by sa, prirodzene, mal servisný čas skrátiť, dobre, nie na polovicu, ale aspoň trochu, ale mysleli sme si, že aj tak je to priemer 2 (min.). Pozývame takého vyberavého čitateľa, aby odpovedal na otázku: o koľko by sa malo znížiť, aby sa „návrh racionalizácie“ stal ziskovým? Opäť narážame na, síce elementárny, ale predsa len optimalizačný problém. Pomocou približných výpočtov, dokonca aj na najjednoduchších Markovových modeloch, je možné objasniť kvalitatívnu stránku javu - ako je výhodné konať a ako je nerentabilné. V ďalšej časti predstavíme niektoré základné nemarkovské modely, ktoré ďalej rozšíria naše možnosti.

Po oboznámení sa s metódami výpočtu konečných pravdepodobností stavov a výkonových charakteristík pre najjednoduchší QS (osvojil si schému smrti a reprodukcie a Littleov vzorec), možno mu na samostatné zváženie ponúknuť ďalšie dva jednoduché QS.

^ 4. Jednokanálový QS s obmedzeným frontom. Problém sa líši od problému 2 iba tým, že počet požiadaviek vo fronte je obmedzený (nesmie prekročiť určitú špecifikovanú T). Ak nová žiadosť príde v čase, keď sú všetky miesta v poradí obsadené, QS nechá neobslúžené (prijaté odmietnutie).

Potrebujeme nájsť konečné pravdepodobnosti stavov (mimochodom, v tejto úlohe existujú pre ľubovoľné ρ - koniec koncov, počet stavov je konečný), pravdepodobnosť zlyhania R otvorená, absolútna priepustnosť A, pravdepodobnosť, že kanál je obsadený R zaneprázdnený, priemerná dĺžka frontu L veľmi dobrý, priemerný počet žiadostí o SOT L sestrička , priemerná doba čakania v rade W veľmi dobre , priemerný čas, počas ktorého aplikácia zostáva v SOT W syst. Pri výpočte charakteristík frontu môžete použiť rovnakú techniku, akú sme použili v Probléme 2, s tým rozdielom, že musíte sčítať nie nekonečnú, ale konečnú postupnosť.

^ 5. Uzavreté QS s jedným kanálom a m zdrojov aplikácií. Aby sme boli konkrétni, položme problém v nasledujúcej forme: jeden pracovník slúži T stroje, z ktorých každý si z času na čas vyžaduje úpravu (opravu). Intenzita dopytového toku každého prevádzkového stroja je λ . Ak sa stroj pokazí, keď je pracovník voľný, okamžite sa uvedie do prevádzky. Ak zlyhá, keď je pracovník zaneprázdnený, zaradí sa do radu a čaká, kým sa pracovník uvoľní. Priemerný čas nastavenia stroja t otáčky = 1/μ. Intenzita toku požiadaviek prichádzajúcich k pracovníkovi závisí od toho, koľko strojov pracuje. Ak to funguje k stroje, je to rovnaké kλ. Nájdite pravdepodobnosti konečného stavu, priemerný počet pracovných strojov a pravdepodobnosť, že pracovník bude zaneprázdnený.

Všimnite si, že v tomto QS sú konečné pravdepodobnosti

bude existovať pre všetky hodnoty λ a μ = 1/ t asi, keďže počet stavov systému je konečný.

Úloha 1. Ovládací panel prijíma prúd požiadaviek, čo je prúd Erlang druhého rádu. Intenzita toku aplikácií je 6 aplikácií za hodinu. Ak dispečer náhodou opustí diaľkové ovládanie, tak pri prvej ďalšej požiadavke sa musí vrátiť k diaľkovému ovládaču. Nájdite distribučnú hustotu čakacej doby na ďalšiu aplikáciu a vytvorte jej graf. Vypočítajte pravdepodobnosť, že dispečer bude neprítomný 10 až 20 minút. Riešenie. Keďže Erlangov tok druhého rádu je stacionárny tok s obmedzeným následným účinkom, platí preň Palmov vzorec

Kde f1(θ)- hustota rozdelenia pravdepodobnosti pre čas čakania na prvú najbližšiu udalosť;
λ - intenzita prúdenia;
- poradie toku;
(θ) - funkcia rozdelenia pravdepodobnosti pre čas medzi dvoma susednými udalosťami Erlangovho toku - prvého rádu (E).
Je známe, že distribučná funkcia pre tok E má tvar

. (2)

Podľa podmienok problému je tok požiadaviek Erlangov poriadok =2. Potom z (1) a (2) dostaneme
.
Z posledného vzťahu pre λ=6 budeme mať

f1(6) = 3å-60 (1+6θ), θ≥0. (3)

Nakreslíme funkciu f1(θ) . O θ <0 máme f1(θ) =0 . O θ =0 , f1(0)=3. Zvážte limit

Pri výpočte limitu na odhalenie typovej neistoty sa použilo L'Hopitalovo pravidlo. Na základe výsledkov výskumu zostavíme graf funkcie f1(θ) (obr. 1).

Venujme pozornosť časovým rozmerom v texte úlohy: pre intenzitu sú to požiadavky za hodinu, pre čas - minúty. Prejdime na jednu časovú jednotku: 10 min = 1/6 hodiny, 20 min = 1/3 hodiny. Pre tieto hodnoty môžeme vypočítať f1(θ) a objasniť povahu krivky

Tieto súradnice sú vyznačené v grafe nad príslušnými bodmi na krivke.
Z kurzu teórie pravdepodobnosti vieme, že pravdepodobnosť zásahu náhodnej premennej X do segmentu [α, β] sa numericky rovná ploche pod krivkou rozdelenia hustoty pravdepodobnosti f(x). Táto plocha je vyjadrená určitým integrálom

Preto sa požadovaná pravdepodobnosť rovná

Tento integrál sa dá ľahko vypočítať po častiach, ak dáme
U = 1 + 60 A dV=e-60d6. Potom dU=6d6 A V= .
Pomocou vzorca dostaneme

Odpoveď: pravdepodobnosť, že dispečer bude neprítomný od 10 do 20 minút, je 0,28.

Úloha 2. Výstavná miestnosť má 5 vitrín. Tok používateľov je jednoduchý. Priemerný počet používateľov, ktorí navštívia výstavnú miestnosť za deň, je 140. Čas spracovania informácií jedným používateľom na jednej obrazovke je rozdelený podľa exponenciálneho zákona a je v priemere 40 minút. Zistite, či existuje stacionárny prevádzkový režim pre halu; pravdepodobnosť, že používateľ bude považovať všetky displeje za obsadené; priemerný počet používateľov vo výstavnej miestnosti; priemerný počet používateľov vo fronte; priemerná doba čakania na bezplatné zobrazenie; priemerný čas, ktorý používateľ strávi vo výstavnej miestnosti. Riešenie. QS uvažovaný v probléme patrí do triedy viackanálových systémov s neobmedzeným frontom. Počet kanálov = 5. Nájdite λ-intenzitu toku aplikácií: kde (hodiny) – priemerný čas medzi dvoma po sebe nasledujúcimi požiadavkami z toku prichádzajúceho používateľa. Potom užívateľ/hod

Poďme zistiť intenzitu toku služieb: , kde M[T serv.]=40 min=0,67 hodiny je priemerný čas na obsluhu jedného používateľa s jedným displejom,

Potom užívateľ/hod

Klasifikátor tohto systému má teda tvar QS (5, ∞; 5,85; 1,49).
Vypočítajme faktor zaťaženia QS . Je známe, že pre QS tejto triedy existuje stacionárny režim, ak je pomer faktora zaťaženia systému k počtu kanálov menší ako jedna. Tento vzťah nájdeme
.
Preto existuje stacionárny režim. Limitné rozdelenie pravdepodobnosti stavov sa vypočíta pomocou vzorcov

Od =5 máme

Vypočítajme P* – pravdepodobnosť, že používateľ bude považovať všetky displeje za obsadené. Je zrejmé, že sa rovná súčtu pravdepodobností takýchto udalostí: všetky displeje sú zaneprázdnené, nie je tam žiadny front (p5); všetky displeje sú zaneprázdnené, jeden používateľ je vo fronte (p6); všetky displeje sú zaneprázdnené, dvaja používatelia sú vo fronte (p7) atď. Keďže pre celú skupinu udalostí je súčet pravdepodobností týchto udalostí rovný jednej, potom platí rovnosť

P*=p5+p6+p7+…=1 - po - p1 - p2 - p3 - p4.

Poďme nájsť tieto pravdepodobnosti: ro=0,014; p1=3,93*0,014; p2=7,72*0,014; p3=10,12*0,014; p4=9,94*0,014.
Keď vypustíme spoločný faktor zo zátvoriek, dostaneme
P*=1-0,0148*(1+3,93+7,72+10,12+9,94)=1-0,014*32,71=1-0,46=0,54.
Používate vzorce na výpočet ukazovateľov výkonnosti? poďme nájsť:

• 1. priemerný počet používateľov vo fronte

2. priemerný počet používateľov vo výstavnej miestnosti

3. priemerná doba čakania na bezplatné zobrazenie

4. priemerný čas, ktorý používateľ strávi vo výstavnej miestnosti

Odpoveď: existuje stacionárny režim prevádzky výstavnej miestnosti a je charakterizovaný nasledujúcimi indikátormi R*= 0,54; užívateľ; užívateľ; ; .

Úloha 3. Dvojkanálový zaraďovací systém (QS) s poruchami prijíma stacionárny Poissonov tok požiadaviek. Čas medzi príchodom dvoch po sebe nasledujúcich požiadaviek je rozdelený podľa exponenciálneho zákona s parametrom λ=5 požiadaviek za minútu. Doba obsluhy každej požiadavky je 0,5 minúty. Pomocou metódy Monte Carlo nájdite priemerný počet doručených žiadostí za 4 minúty. Smer: Vykonajte tri testy. Riešenie. Znázornime štatistické modelovanie prevádzky daného QS pomocou časových diagramov. Uveďme nasledujúce označenie pre časové osi:
In-prichádzajúci tok aplikácií, tu ti- okamihy prijatia žiadostí; Ti- časové intervaly medzi dvoma po sebe nasledujúcimi aplikáciami. To je zrejmé ti=ti-1 +Ti.
K1 je prvý obslužný kanál;
K2-sekundový servisný kanál; tu hrubé čiary na časovej osi označujú intervaly obsadenosti kanálov. Ak sú obidva kanály voľné, potom sa požiadavka obslúži na kanáli K1, ak je obsadený, požiadavka je obsluhovaná kanálom K2.
Ak sú obidva kanály obsadené, požiadavka ponechá QS bez obsluhy.
Out OB - odchádzajúci tok obsluhovaných požiadaviek.
Out PT - odchádzajúci tok stratených požiadaviek v dôsledku porúch QS (prípad obsadenosti oboch kanálov).
Štatistické testovanie pokračuje počas časového intervalu. Je zrejmé, že akýkoľvek prebytok času tmax znamená vloženie žiadosti do výstupného toku Výstup PT. Takže na obr. 3 prihlášky č. 10, ktorá v súčasnosti prišla do systému t10, nestihne byť doručená do tejto chvíle tmax, pretože t10+Tol.>tmax. V dôsledku toho nie je akceptovaný voľným kanálom K1 pre službu a je resetovaný na výstup PT, pričom dostane odmietnutie.

Ryža. 3

Z časových diagramov je zrejmé, že je potrebné naučiť sa modelovať intervaly Ti. Aplikujme metódu inverzných funkcií. Keďže náhodná premenná Ti rozdelené podľa exponenciálneho zákona s parametrom λ = 5, potom má hustota rozloženia tvar f(τ)=5å-5τ. Potom hodnota F(Ti) funkcia rozdelenia pravdepodobnosti je určená integrálom

.

Je známe, že rozsah distribučnej funkcie F(T) existuje segment. Vyberieme číslo z tabuľky náhodných čísel a určíme Ti z rovnosti, odkiaľ. Ak však . Preto môžete okamžite získať implementácie z tabuľky náhodných čísel. teda
e-5Ti= RI, alebo -5Ti= lnri, kde . Je vhodné zadať výsledky výpočtu do tabuľky.
Na vykonanie testu č. 1 boli vybrané náhodné čísla z Prílohy 2, počnúc prvým číslom prvého riadku. Ďalej sa výber uskutočnil podľa riadkov. Urobme ďalšie dva testy.
Venujte pozornosť výberu náhodných čísel z tabuľky v prílohe 2, ak v teste č.1 bolo posledné náhodné číslo pre aplikáciu č.16 0,37 (prvé náhodné číslo v druhom riadku), tak test č.2 začína nasledujúce náhodné číslo 0,54 . Pokus 2 obsahuje posledné náhodné číslo 0,53 (piate číslo v treťom riadku). Preto sa tretí pokus začne s číslom 0,19. Vo všeobecnosti sa v rámci jednej série testov vyberú náhodné čísla z tabuľky bez medzier alebo vložení v určitom poradí, napríklad po riadkoch.

Tabuľka 1. TEST č.1

Prihláška č. i	Sl. číslo RI		-V ri Ti	Okamih prijatia prihlášky ti=ti-1+Ti	Moment konca služby. ti + 0,50		Počítadlo aplikácií
					K1

Tabuľka 2 TEST č.2

Prihláška č. i	Sl. číslo RI		-V ri Ti	Okamih prijatia prihlášky ti=ti-1+Ti	Moment konca služby. ti + 0,50		Počítadlo aplikácií

Tabuľka č.3 TEST č.3

Prihláška č. i		Sl. číslo RI		-V ri Ti	Okamih prijatia prihlášky ti=ti-1+Ti	Moment konca služby. ti + 0,50		Počítadlo aplikácií
						K1

Na základe výsledkov troch testov bol teda počet doručených aplikácií: x1=9, x2=9, x3=8. Poďme zistiť priemerný počet doručených žiadostí:

Odpoveď: Priemerný počet aplikácií obsluhovaných QS za 4 minúty je 8,6(6).

Pri riešení problémov riadenia, vrátane velenia a riadenia jednotiek, často vzniká množstvo podobných problémov:

• posúdenie kapacity komunikačného smeru, železničného uzla, nemocnice a pod.;
• posúdenie účinnosti opravnej základne;
• určenie počtu frekvencií pre rádiovú sieť a pod.

Všetky tieto úlohy sú podobné v tom zmysle, že zahŕňajú obrovský dopyt po službách. Na uspokojení tohto dopytu sa podieľa určitý súbor prvkov tvoriacich systém radenia (QS) (obr. 2.9).

Prvky QS sú:

• vstup (prichádzajúci) dopytový tok(žiadosti) o službu;
• servisné zariadenia (kanály);
• rad aplikácií čakajúcich na službu;
• deň voľna ( odchádzajúci) tok spracované žiadosti;
• tok neobsluhovaných aplikácií;
• front voľných kanálov (pre viackanálové QS).

Prichádzajúci tok je zbierka servisných požiadaviek. Aplikácia je často identifikovaná s jej nositeľom. Napríklad tok chybných rádiových zariadení vstupujúcich do dielne združenia predstavuje tok požiadaviek - požiadaviek na servis v tomto QS.

Spravidla sa v praxi zaoberáme takzvanými rekurentnými tokmi - tokmi, ktoré majú tieto vlastnosti:

• stacionárnosť;
• obyčajný;
• obmedzený následný efekt.

Prvé dve vlastnosti sme definovali skôr. Čo sa týka obmedzeného následného efektu, ten spočíva v tom, že intervaly medzi prichádzajúcimi aplikáciami sú nezávislé náhodné premenné.

Existuje veľa opakujúcich sa vlákien. Každý zákon rozdelenia intervalov generuje svoj vlastný opakujúci sa tok. Opakujúce sa toky sa inak nazývajú palmové toky.

Tok s úplnou absenciou následného účinku, ako už bolo uvedené, sa nazýva stacionárny Poisson. Jeho náhodné intervaly medzi objednávkami majú exponenciálne rozdelenie:

tu je intenzita prúdenia.

Názov toku - Poisson - pochádza zo skutočnosti, že pre toto pravdepodobnosť toku vzhľad objednávok počas intervalu je určený Poissonovým zákonom:

Tok tohto typu, ako už bolo uvedené vyššie, sa tiež nazýva najjednoduchší. To je presne tok, ktorý dizajnéri predpokladajú pri vývoji QS. Je to spôsobené tromi dôvodmi.

Po prvé, tok tohto typu v teórii radenia je podobný zákonu normálneho rozdelenia v teórii pravdepodobnosti v tom zmysle, že najjednoduchší tok sa dosiahne prechodom na limit pre tok, ktorý je súčtom tokov s ľubovoľnými charakteristikami s nekonečným nárastom v a zníženie ich intenzity. To znamená, že súčet ľubovoľných nezávislých (bez dominancie) tokov s intenzitou je najjednoduchší tok s intenzitou

Po druhé, ak sú obslužné kanály (zariadenia) navrhnuté pre najjednoduchší tok požiadaviek, potom bude obsluha iných typov tokov (s rovnakou intenzitou) zabezpečená rovnako efektívne.

Po tretie, je to práve tento tok, ktorý určuje Markovov proces v systéme a následne jednoduchosť analytickej analýzy systému. Pre ostatné toky je analýza fungovania QS zložitá.

Často existujú systémy, v ktorých tok vstupných požiadaviek závisí od počtu obsluhovaných požiadaviek. Takéto SMO sa nazývajú ZATVORENÉ(inak - OTVORENÉ). Napríklad práca asociačného komunikačného workshopu môže byť reprezentovaná modelom QS s uzavretou slučkou. Nech je tento workshop určený na obsluhu rozhlasových staníc, ktoré sú v asociácii. Každý z nich má poruchovosť. Vstupný tok zlyhaného zariadenia bude mať nasledujúcu intenzitu:

kde je počet rádiostaníc, ktoré sú už v dielni na opravu.

Aplikácie môžu mať rôznu oprávnenosť na spustenie služby. V tomto prípade hovoria, že aplikácie heterogénne. Výhody niektorých aplikačných tokov oproti iným sú určené stupnicou priority.

Dôležitou charakteristikou vstupného toku je variačný koeficient:

kde je matematické očakávanie dĺžky intervalu;

Smerodajná odchýlka náhodnej premennej (dĺžka intervalu).

Pre najjednoduchší tok

Pre väčšinu skutočných vlákien.

Keď je tok pravidelný, deterministický.

Variačný koeficient- charakteristika odrážajúca stupeň nerovnomernosti v prijímaní žiadostí.

Servisné kanály (zariadenia). QS môže mať jedno alebo viac servisných zariadení (kanálov). Podľa toho sa QS nazývajú jednokanálové alebo viackanálové.

Viackanálové QS môže pozostávať z rovnakých alebo rôznych typov zariadení. Servisné zariadenia môžu byť:

• komunikačné linky;
• opravári;
• pristávacie dráhy;
• vozidlá;
• kotviská;
• kaderníci, predajcovia a pod.

Hlavnou charakteristikou kanála je servisný čas. Obslužný čas je spravidla náhodná hodnota.

Odborníci sa zvyčajne domnievajú, že čas služby má exponenciálny distribučný zákon:

kde je intenzita služby, ;

Matematické očakávanie servisného času.

To znamená, že servisný proces je markovský, a to, ako teraz vieme, poskytuje značné pohodlie pri analytickom matematickom modelovaní.

Okrem exponenciálneho rozdelenia existujú Erlangove rozdelenia, hyperexponenciálne rozdelenia, trojuholníkové rozdelenia a niektoré ďalšie. To by nás nemalo zmiasť, pretože sa ukázalo, že hodnota kritérií účinnosti QS málo závisí od typu zákona o rozdelení pravdepodobnosti pre čas služby.

Pri štúdiu QS sa podstata služby stráca z úvahy, kvalita služby.

Kanály môžu byť absolútne spoľahlivé, teda nezlyhať. Alebo skôr to možno akceptovať počas výskumu. Kanály môžu mať maximálna spoľahlivosť. V tomto prípade je model QS oveľa komplikovanejší.

Fronta aplikácií. Kvôli náhodnej povahe toku požiadaviek a služieb môže prichádzajúca požiadavka nájsť kanál (kanály) zaneprázdnený obsluhou predchádzajúcej požiadavky. V tomto prípade buď nechá QS neobsluhovaný, alebo zostane v systéme a čaká na spustenie jeho služby. V súlade s tým rozlišujú:

• QS s poruchami;
• SMO s očakávaním.

CMO s očakávaním charakterizované prítomnosťou frontov. Front môže mať obmedzenú alebo neobmedzenú kapacitu: .

Výskumníka zvyčajne zaujímajú nasledujúce štatistické charakteristiky spojené s pobytom žiadostí v poradí:

• priemerný počet žiadostí vo fronte počas študijného intervalu;
• priemerný čas strávený (čakaním) na aplikáciu vo fronte. QS s obmedzenou kapacitou frontu označované ako QS zmiešaného typu.

Často existujú CMO, v ktorých majú aplikácie obmedzený čas v rade bez ohľadu na jeho kapacitu. Takéto QS sú tiež klasifikované ako QS zmiešaného typu.

Výstupný prúd je tok obsluhovaných aplikácií opúšťajúcich QS.

Existujú prípady, keď požiadavky prechádzajú cez niekoľko QS: tranzitná komunikácia, výrobný dopravník atď. V tomto prípade je výstupný tok prichádzajúci pre ďalší QS. Vyvolá sa súbor sekvenčne prepojených QS viacfázový systém radenia alebo QS siete.

Prichádzajúci tok prvého QS, ktorý prechádza cez nasledujúce QS, je skreslený a to komplikuje modelovanie. Treba však mať na pamäti, že s najjednoduchším vstupným tokom a exponenciálnou službou (to znamená v Markovových systémoch) je aj výstupný tok najjednoduchší. Ak má servisný čas neexponenciálne rozdelenie, odchádzajúci tok nielenže nie je najjednoduchší, ale ani sa neopakuje.

Všimnite si, že intervaly medzi požiadavkami odchádzajúceho toku nie sú rovnaké ako servisné intervaly. Môže sa totiž ukázať, že po skončení ďalšej služby je QS nejaký čas nečinný pre nedostatok aplikácií. V tomto prípade

Tok objednávok je Poisson, ak sú splnené 3 podmienky:

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

Pozrime sa na niektoré vlastnosti (typy) tokov udalostí.

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

Konštantná je najmä intenzita stacionárneho prúdenia. Tok udalostí má nevyhnutne kondenzácie alebo zriedkavosti, 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 akékoľvek dva neprekrývajúce sa časové úseky 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 tok, sa objavujú v určitých časových bodoch nezávisle od seba a každý je spôsobený svojimi vlastnými príčinami.

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

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

Pravdepodobnosť udalosti (príchodu aplikácie) v krátkom časovom intervale je úmerná dĺžke tohto intervalu.

Pravdepodobnosť 2 udalostí v malom intervale je zanedbateľná.

Viera, že žiadosť je prijatá, nezávisí od predchádzajúcich udalostí.

Najjednoduchší tok má najjednoduchší matematický popis. Medzi tokmi hrá rovnakú osobitnú úlohu ako zákon normálneho rozdelenia medzi inými distribučnými zákonmi. Konkrétne, pri superponovaní dostatočne veľkého počtu nezávislých, stacionárnych a obyčajných tokov (vzájomne porovnateľných v intenzite) sa získa tok blízky najjednoduchšiemu.

Najjednoduchšie QS a ich charakteristiky. Viackanálové a jednokanálové bezstratové systémy s neobmedzenou latenciou a zdrojom s nekonečným množstvom požiadaviek. Podmienka existencie konečného priemerného radu pre viackanálové systémy.

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

Každý QS pozostáva z určitého počtu servisných jednotiek, ktoré sa volajú servisné kanály(sú to stroje, transportné vozíky, roboty, komunikačné linky, pokladníci, predajcovia a pod.). Každý QS je navrhnutý tak, aby slúžil nejakému druhu tok aplikácií(požiadavky) prichádzajúce v niektorých náhodných okamihoch v čase.

Obsluha 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á povaha toku aplikácií a servisného času vedie k tomu, že v niektorých časových úsekoch 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 systém pracovať s nedostatočným zaťažením alebo bude úplne nečinný.

Najjednoduchší QS s čakaním je jednokanálový systém, ktorý prijíma tok požiadaviek so špecifickou intenzitou Požiadavka, ktorá príde v čase, keď je kanál obsadený, je zaradená do frontu a čaká na obsluhu.

MCU sa používajú na simuláciu niekoľkých paralelných prevádzkových objektov. Modelovanie MCU je podobné ako modelovanie zariadenia: transakcia vstúpi do zariadenia, zaberie určitý počet kanálov, je nejaký čas obsluhovaná a potom opustí MCU, čím sa uvoľnia kanály, ktoré obsadila.

Podmienky v reálnom objekte potrebné na použitie MKU na ich reprezentáciu v modeli:

Objekty musia mať rovnakú funkciu distribúcie času obsluhy

Rovnaké parametre pre túto funkciu.

Na rozdiel od prístroja je kapacita mačky vždy rovná jednej, kapacita MKU d.b. definované programátorom. Na to použite špeciálny príkaz STORAGE (DEFINE MCU).

Názov tímu STORAGE A

Pole CommandName je symbolický názov MCU a pole A je jeho kapacita (počet servisných kanálov), operand A môže byť špecifikované len ako kladné celé číslo.

Príklad: MKU1 STORAGE 5 TRAKT STORAGE 30 (kapacita MKU s názvom MKU1 je definovaná ako 5, MKU s názvom TRAKT je 30).

Udalosť spojená s obsadením obslužných kanálov je modelovaná blokom ENTER a udalosť spojená s uvoľnením kanálov je modelovaná blokom LEAVE.

A je názov MKU. B – počet jednotiek kapacity MCU, ktoré musí mačka obsadiť (uvoľniť) transakciu. Predvolená hodnota = 1.

Príklad: 1) ENTER BLOK3 (zadajte MCU s názvom BLOK3);

2)LEAVE SEANS,3 (uvoľnite 3 jednotky kapacity MCU s názvom SEANS).

Medzi blokmi ENTER a LEAVE môže byť ľubovoľný počet blokov. Najmä oneskorenie počas servisného času v MCU je simulované pomocou bloku ADVANCE.

Ak počet jednotiek kapacity špecifikovaný operandom B bloku LEAVE prekročí počet aktuálne obsadených kanálov MCU, tlmočník zastaví simuláciu a zobrazí chybové hlásenie.

Pre transakcie, ktoré čakajú na obsadenie MCU, platí pravidlo „first to match with pass“.

Keď transakcia vstúpi do bloku LEAVE, tlmočník pozastaví jej priebeh, čím umožní ďalšej transakcii z reťazca oneskorenia tohto MCU vstúpiť do bloku ENTER a až potom postúpi transakciu, ktorá opustila MCU v modeli. Transakcia, ktorá opustí reťazec oneskorenia MCU, sa prenesie do DTS a stane sa poslednou vo svojej prioritnej triede.

MCU majú nasledovné NAV: S - aktuálny obsah MCU; R je voľná kapacita MCU; SR - miera využitia v zlomkoch 1000; SA - celá časť priemerného obsahu MKU; SM - maximálny obsah MCU; SC - počet tried MKU; ST je celá časť priemerného času obsadenia MKU.

Bloky Seize a Release sa používajú na navrhovanie jednokanálových zariadení

CHYTIŤA(occupy) - obsadenie zariadenia transakciou. A- názov vstupného bodu zariadenia.

UVOĽNIŤA(vydanie) – uvoľnenie zariadenia transakciou po uplynutí servisného času.