Úkoly frontových systémů (QS). Nejjednodušší systémy řazení do fronty, příklady použití při řešení ekonomických problémů

Matematický (abstraktní) objekt, jehož prvky jsou (obr. 2.1):

vstupní (příchozí) tok požadavků (požadavků) na službu;
servisní zařízení (kanály);
fronta požadavků čekajících na doručení;
výstupní (odchozí) tok obsluhovaných požadavků;
tok požadavků na další službu po přerušení služby;
tok neobsazených objednávek.

Žádost (požadavek, požadavek, volání, klient, zpráva, balíček) - objekt přicházející do QS a vyžadující servis v zařízení. Sada postupných objednávek distribuovaných v časové formě vstupní proud aplikací.

Postava: 2.1.

Servisní zařízení (zařízení, zařízení, kanál, linka, nástroj, auto, router atd.) - prvek QS, jehož účelem je obsluhovat požadavky.

Servis - zpoždění aplikace v servisním zařízení po určitou dobu.

Doba trvání služby je doba zpoždění (služby) požadavku v zařízení.

Úložné zařízení (buffer, input buffer, output buffer) - sada míst pro čekající příkazy před serverem. Počet míst čekání - kapacita skladu.

Žádost přijatá SOT může být ve dvou státech:

1) servis (v zařízení);
2) očekávání (v úložišti), pokud jsou všechna zařízení zaneprázdněna obsluhou jiných zákazníků.

Požadavky, které jsou v jednotce a čekají na formulář služby otáčet se aplikace. Počet požadavků v jednotce čekajících na službu - délka fronty.

Vyrovnávací kázeň (disciplína řazení do fronty) - pravidlo pro zadávání příchozích požadavků do jednotky (vyrovnávací paměti).

Servisní disciplína - pravidlo pro výběr požadavků z fronty na službu v zařízení.

Priorita - preventivní právo (zabavit zdroje) vstoupit do mechaniky nebo vybrat z fronty pro servis v zařízení nároky jedné třídy ve vztahu k nárokům jiných tříd.

Existuje mnoho systémů čekání ve frontě, lišící se strukturální a funkční organizací. Vývoj analytických metod pro výpočet indikátorů fungování QS současně v mnoha případech předpokládá přítomnost řady omezení a předpokladů, které zužují soubor zkoumaného QS. proto neexistuje žádný obecný analytický model pro libovolný QS složité struktury.

Analytický model QS je soubor rovnic nebo vzorců, které umožňují určit pravděpodobnosti stavů systému v průběhu jeho provozu a ukazatelů výkonu podle známých parametrů příchozích toků a servisních kanálů, vyrovnávacích pamětí a servisních disciplín.

Analytické modelování QS je značně usnadněno, pokud jsou procesy vyskytující se v QS Markov (toky aplikací jsou nejjednodušší, časy služeb jsou distribuovány exponenciálně). V tomto případě lze všechny procesy v QS popsat obyčejně diferenciální rovnice, a v mezním případě - pro stacionární stavy - lineární algebraické rovnice a poté, co je vyřešíme pomocí metod dostupných v matematických softwarových balíčcích, určíme vybrané výkonnostní ukazatele.

V systémech IM jsou při implementaci QS přijímána následující omezení a předpoklady:

příchozí aplikace okamžitě dostane servis, pokud ve frontě nejsou žádní zákazníci a zařízení je zdarma;
zařízení, které je kdykoli opravováno, může obsahovat pouze sama žádost;
po ukončení obsluhy jakéhokoli zákazníka na serveru je okamžitě vybrán další zákazník z fronty na službu, tj. zařízení není nečinný, pokud je ve frontě alespoň jeden požadavek;
příjem aplikací v QS a doba trvání jejich služby nezávisí na počtu aplikací již v systému nebo na jiných faktorech;
doba trvání servisních požadavků nezávisí na intenzitě požadavků přicházejících do systému.

Pojďme se podrobněji zabývat některými prvky QS.

Vstupní (příchozí) tok aplikací. Tokem událostí se nazývá sled homogenních událostí, které následují po sobě a vyskytují se v některých, obecně řečeno, náhodný okamžiky v čase. Pokud událost spočívá ve vzhledu objednávek, máme tok aplikací. K popisu toku aplikací je obecně nutné určit časové intervaly t \u003d t k - t k-1 mezi sousedními momenty t k _ k a t k příjem žádostí s pořadovými čísly do - 1 a na resp (k - 1, 2, ...; t 0 - 0 je počáteční časový okamžik).

Hlavní charakteristikou toku aplikací je jeho intenzita X je průměrný počet aplikací vstupujících do vstupu QS za jednotku času. Množství m \u003d 1 / X definuje průměrný časový interval mezi dvěma po sobě jdoucími aplikacemi.

Stream se nazývá deterministický, pokud časové intervaly t do mezi sousedními aplikacemi nabývají určitých předem určených známých hodnot. Pokud jsou intervaly stejné (x k \u003d t pro všechny k \u003d 1, 2, ...), pak je tok volán pravidelný. Pro úplný popis pravidelného toku požadavků stačí nastavit rychlost toku Xnebo hodnota intervalu t \u003d 1 / X.

Stream, ve kterém jsou časové intervaly x až mezi sousedními deklaracemi jsou náhodné proměnné, tzv náhodný. Pro úplný popis náhodného toku pohledávek je obecně nutné určit zákony rozdělení F fc (x fc) každého z časových intervalů x k, k \u003d 1,2, ....

Náhodný stream, ve kterém jsou všechny časové intervaly x b x 2,... mezi sousedními po sobě následujícími nároky jsou nezávislé náhodné proměnné popsané distribučními funkcemi FjCij), F 2 (x 2), ... se nazývá tok s omezený následný účinek.

Volá se náhodný stream opakující se, pokud jsou všechny časové intervaly x b m 2, ... jsou přiděleny mezi aplikace podle stejného zákona F (t). Existuje mnoho opakujících se streamů. Každý zákon o distribuci generuje svůj vlastní opakující se tok. Opakované toky se také nazývají palmové toky.

Pokud intenzita X a distribuční zákon F (t) intervalů mezi po sobě následujícími nároky se nemění s časem, pak se volá proud požadavků stacionární Jinak je tok aplikací nestacionární.

Pokud v každém okamžiku t k na vstupu do QS se může objevit pouze jeden požadavek, poté je vyvolán tok požadavků obyčejný. Pokud se může kdykoli objevit více než jedna objednávka, pak tok objednávek je mimořádný, nebo skupina.

Tok aplikací se nazývá tok bez následků, pokud aplikace dorazí to je jedno od sebe navzájem, tj. okamžik přijetí další žádosti nezávisí na tom, kdy a kolik žádostí bylo do této chvíle přijato.

Volá se stacionární obyčejný tok bez následného účinku nejjednodušší.

Časové intervaly t mezi nároky v nejjednodušším toku jsou distribuovány exponenciální (orientační) zákon: s distribuční funkcí F (t) \u003d 1 - e ~ m; hustota distribuce / (f) \u003d Heh ~ "l, Kde X\u003e 0 - distribuční parametr - intenzita toku aplikací.

Nejjednodušší tok se často nazývá jed. Název pochází ze skutečnosti, že pro tento tok je pravděpodobnost P fc (At) vzhledu přesně na jsou stanoveny nároky za určitý časový interval At poissonův zákon:

Je třeba poznamenat, že Poissonův proud, na rozdíl od nejjednoduššího, může být:

stacionární, pokud intenzita X se v průběhu času nemění;
nestacionární, pokud průtok závisí na čase: X \u003d\u003e. (t).

Současně je nejjednodušší tok podle definice vždy stacionární.

Analytické studie modelů zařazování do fronty se často provádějí za předpokladu nejjednoduššího toku pohledávek, a to kvůli řadě inherentních pozoruhodných rysů.

1. Shrnutí (sjednocení) proudů. Nejjednodušší tok v teorii QS je podobný zákonu normálního rozdělení v teorii pravděpodobnosti: nejjednodušší tok se získá přechodem k limitu toku, který je součtem toků s libovolnými charakteristikami s nekonečným nárůstem počtu členů a snížením jejich intenzity.

Množství N nezávislé stacionární běžné toky s intenzitami X b X 2 ,..., X N tvoří nejjednodušší tok s intenzitou

X \u003d Y, ^ i za předpokladu, že přidané toky mají více nebo

menší stejně malý dopad na celkový průtok. V praxi je celkový tok blízký nejjednoduššímu pro N\u003e 5. Proto při sčítání nezávislých nejjednodušších toků bude celkový tok nejjednodušší pro jakoukoli hodnotu N.

2. Pravděpodobnostní zředění toku. Pravděpodobnostní (ale není deterministický) zředění nejjednodušší tok nároky, u nichž je jakýkoli nárok náhodně s určitou pravděpodobností rvyloučeno ze streamu, ať už jsou nebo nejsou vyloučeny jiné aplikace, má za následek nejjednodušší tok s intenzitou X * = pX, Kde X - intenzita počátečního toku. Tok vyloučených objednávek s intenzitou X ** \u003d (1 - p) X - taky nejjednoduššítok.
3. Účinnost. Pokud jsou obslužné kanály (zařízení) navrženy pro nejjednodušší tok požadavků s intenzitou X, pak bude zajištěna obsluha dalších typů proudů (se stejnou intenzitou) s neméně efektivní účinností.
4. Jednoduchost. Předpoklad nejjednoduššího toku aplikací umožňuje mnoha matematickým modelům získat explicitně závislost indikátorů QS na parametrech. Největší počet analytických výsledků byl získán pro nejjednodušší tok aplikací.

Analýza modelů s toky aplikací, které se liší od těch nejjednodušších, obvykle komplikuje matematické výpočty a ne vždy umožňuje získat explicitní analytické řešení. Název „nejjednodušší“ stream dostal své jméno právě díky této funkci.

Žádosti mohou mít různá práva k zahájení služby. V tomto případě říkají, že nabídky heterogenní. Výhody některých toků požadavků nad ostatními na začátku služby jsou stanoveny podle priorit.

Důležitá vlastnost vstupní proud je variační koeficient

kde t int je matematické očekávání délky intervalu; o je směrodatná odchylka délky intervalu x int (náhodná proměnná).

Pro nejjednodušší tok (a \u003d -, m \u003d -) máme v \u003d 1. Pro většinu

reálné toky 0

Servisní kanály (zařízení). Hlavní charakteristikou kanálu je doba trvání služby.

Doba trvání služby - čas strávený objednávkou v zařízení - v obecném případě je hodnota náhodná. V případě nerovnoměrného zatížení QS se doby trvání reklamací různých tříd mohou lišit podle zákonů distribuce nebo pouze průměrnými hodnotami. V tomto případě se obvykle předpokládá, že doba trvání služby deklarací každé třídy je nezávislá.

Odborníci často předpokládají, že doba trvání požadavků na servis je distribuována exponenciální zákon, což výrazně zjednodušuje analytické výpočty. To je způsobeno skutečností, že procesy probíhající v systémech s exponenciálním rozdělením časových intervalů jsou markov procesy:

kde q - intenzita služby, zde p \u003d _--; t 0 bsl - matematika

technické čekání na servisní dobu.

Kromě exponenciální distribuce existují Erlangovy fc-distribuce, hyperexponenciální, trojúhelníkové a některé další. To by nás nemělo zmást, protože se ukázalo, že hodnota kritérií účinnosti QS závisí jen málo na formě zákona o distribuci času služby.

Při zkoumání QS vychází z úvahy podstata služby, kvalita služby.

Kanály mohou být absolutně spolehlivý, ty. nezapomeňte. To lze ve výzkumu spíše přijmout. Kanály mohou mít maximální spolehlivost. V tomto případě je model QS mnohem komplikovanější.

Účinnost QS závisí nejen na parametrech vstupních toků a servisních kanálech, ale také na pořadí, ve kterém jsou obsluhovány příchozí reklamace, tj. ze způsobů řízení toků požadavků, když vstupují do systému a jsou odesílány do služby.

Metody řízení toku aplikací jsou určeny disciplínami:

ukládání do vyrovnávací paměti;
servis.

Vyrovnávací paměti a servisní disciplíny lze klasifikovat podle následujících kritérií:

přítomnost priorit mezi aplikacemi různých tříd;
způsob přesunu požadavků z fronty (pro vyrovnávací paměti disciplín) a přiřazení požadavků na službu (pro servisní disciplíny);
pravidlo pro preempci nebo výběr požadavků na službu;
schopnost měnit priority.

Varianta klasifikace disciplín ukládání do vyrovnávací paměti (řazení do fronty) v souladu s uvedenými funkcemi je uvedena na obr. 2.2.

Záleží na dostupnost nebo nedostatek priorit všechny disciplíny ukládání do vyrovnávací paměti lze rozdělit do dvou skupin mezi požadavky různých tříd: neprioritní a prioritní.

Podle způsob přemisťování objednávek z pohonu lze rozlišit následující třídy nárazníkových disciplín:

bez přesouvání objednávek - objednávky, které vstoupily do systému a zjistily, že disk je zcela zaplněn, jsou ztraceny;
vytěsňování této třídy, tj. stejná třída jako podaná přihláška;
vytlačování aplikace z třídy s nejnižší prioritou;
s přemístěním aplikace ze skupiny tříd s nízkou prioritou.

Postava: 2.2.

Ukládání do vyrovnávací paměti disciplín může využívat následující pravidla pro vytlačování objednávek z mechaniky:

náhodné vytěsnění;
vytěsnění poslední objednávky, tj. vstoupil do systému později než kdokoli jiný;
vytěsnění „dlouhé“ objednávky, tj. umístěné v jednotce déle než všechny dříve přijaté aplikace.

Na obr. 2.3 ukazuje klasifikaci oborů pro servisní požadavky podle stejných kritérií jako pro nárazníkové disciplíny.

Někdy je kapacita úložiště v modelech považována za neomezenou, i když ve skutečném systému je omezená. Tento předpoklad je oprávněný, když je pravděpodobnost ztráty požadavku ve skutečném systému v důsledku přetečení kapacity jednotky menší než 10 _3. V tomto případě nemá disciplína prakticky žádný vliv na výkon služeb aplikací.

Záleží na dostupnost nebo nedostatek priorit Mezi požadavky různých tříd lze všechny servisní disciplíny, stejně jako disciplíny s vyrovnávací pamětí, rozdělit do dvou skupin: neprioritní a prioritní.

Podle způsob přiřazování požadavků na službu servisní disciplíny lze rozdělit na disciplíny:

jednoduchý režim;
skupinový režim;
kombinovaný režim.

Postava: 2.3.

Ve služebních disciplínách jeden režim pokaždé pro servis jen jeden aplikace, u které jsou fronty skenovány po ukončení služby předchozí aplikace

Ve služebních disciplínách skupinový režim pokaždé pro servis je přiřazena skupina aplikací jedna fronta, u které se fronty zobrazují až po obsloužení všech požadavků dříve přiřazené skupiny. Nově přiřazená skupina deklarací může zahrnovat všechny deklarace této fronty. Přiřazené skupinové jízdenky jsou postupně vybírány z frontya jsou obsluhovány zařízením, po kterém je další skupina nároků jiné fronty přiřazena ke službě v souladu s danou servisní disciplínou.

Kombinovaný režim - kombinace jednoduchého a skupinového režimu, kdy je část front aplikací zpracována v jednom režimu, a druhá část - ve skupině.

Servisní disciplíny mohou používat následující pravidla výběru požadavků na služby.

Neprioritní (požadavky nemají oprávnění včasné služby - chytání prostředků):

prvotřídní služby FIFO (první v - první, první dovnitř - první ven);
zpětná služba - aplikace je vybrána z fronty v režimu LIFO (poslední v - nejprve ven, poslední zadaný - první vlevo);
náhodná služba - aplikace je vybrána z fronty v režimu RAND (náhodný - náhodně);
cyklická služba - objednávky jsou vybírány v procesu cyklického dotazování pohonů v pořadí 1, 2, HZ H - počet jednotek), po kterém se zadaná sekvence opakuje;

Přednost (požadavky mají oprávnění pro včasnou službu - zachycení prostředků):

z relativní priority - pokud v procesu aktuální obsluhy požadavku systém přijímá požadavky s vyššími prioritami, pak obsluha aktuálního, i neprioritního požadavku, není přerušena a přijaté požadavky jsou odeslány do fronty; relativní priority hrají roli pouze na konci aktuální služby požadavku, když je z fronty vybrán nový požadavek na službu.
z absolutní priority - když přijde požadavek s vysokou prioritou, služba požadavku s nízkou prioritou je přerušena a přijatý požadavek je odeslán do služby; přerušená aplikace může být vrácena do fronty nebo odstraněna ze systému; pokud je aplikace vrácena do fronty, lze její další obsluhu provádět z přerušeného místa nebo znovu;
s smíšené priority - přísná omezení čekací doby ve frontě na obsluhu jednotlivých aplikací vyžadují, aby jim byly přiřazeny absolutní priority; v důsledku toho se čekací doba na objednávky s nízkými prioritami může ukázat jako nepřijatelně dlouhá, ačkoli jednotlivé objednávky mají čekací dobu; ke splnění omezení u všech typů aplikací, spolu s absolutními prioritami, lze některým aplikacím přiřadit relativní priority a zbytek lze obsluhovat v neprioritním režimu;
z střídavé priority - analog relativních priorit, priorita je zohledněna až v okamžiku, kdy je dokončena aktuální obsluha skupiny aplikací jedné fronty a je přidělena nová skupina pro obsluhu;
plánovaná služba - pohledávky různých tříd (umístěné v různých akumulátorech) jsou vybrány pro údržbu podle určitého rozpisu specifikujícího posloupnost dotazovacích front pohledávek, například v případě tří tříd pohledávek (akumulátory) může mít rozpis formu (2, 1, 3, 3, 1, 2) nebo (1, 2, 3, 3, 2, 1).

V počítačových systémech IM je disciplína zpravidla implementována standardně FIFO. Mají však nástroje, které uživateli poskytují možnost organizovat požadované servisní disciplíny, a to i podle plánu.

Aplikace přicházející do SOT jsou rozděleny do tříd. V SOT, což je abstrakt matematický model, aplikace odkazují na různé třídy v případě, že se liší v simulovaném reálném systému alespoň v jedné z následujících funkcí:

doba služby;
priority.

Pokud se deklarace neliší v době trvání služby a prioritách, mohou být reprezentovány deklaracemi stejné třídy, včetně případů, kdy přicházejí z různých zdrojů.

Pro matematický popis služebních disciplín se smíšenými prioritami se používá prioritní matice, což je čtvercová matice Q \u003d (q ,;), i, j - 1, ..., R, R - počet tříd aplikací vstupujících do systému.

Živel q (j matice nastavuje prioritu objednávek třídy i ve vztahu ke skupinovým nárokům; a může nabývat následujících hodnot:

0 - žádná priorita;
1 - relativní priorita;
2 - absolutní priorita.

Prvky prioritní matice musí splňovat následující požadavky:

q n \u003d 0, protože priority nelze nastavit mezi aplikacemi stejné třídy;
Pokud q (j \u003d 1 nebo 2 q^ \u003d 0, protože pokud jsou nároky třídy i mít přednost před třídními nároky j, pak tento nemůže mít přednost před nároky třídy i (i, j \u003d 1, ..., Z).

Záleží na příležitosti ke změně priorit V procesu provozu systému jsou disciplíny prioritního ukládání do vyrovnávací paměti a údržby rozděleny do dvou tříd:

1) s statické priority, které se časem nemění;
2) s dynamické priority, které se mohou během provozu systému měnit v závislosti na různých faktorech, například když je dosaženo určité kritické hodnoty délky fronty aplikací třídy, která nemá žádnou nebo nízkou prioritu, může jí být přidělena vyšší priorita.

V počítačových systémech IM existuje nutně jediný prvek (objekt), kterým se do modelu zadávají aplikace pouze prostřednictvím něj. Ve výchozím nastavení jsou všechny zadané objednávky neprioritní. Existují však možnosti přiřazení priorit v posloupnosti 1, 2, ..., a to i během provádění modelu, tj. v dynamice.

Odchozí stream je tok obsluhovaných aplikací opouštějících QS. Ve skutečných systémech procházejí aplikace několika QO: tranzitní komunikace, výrobní dopravník atd. V tomto případě je odchozí stream příchozí stream pro další QS.

Příchozí tok prvního QS, procházející následujícím QS, je zkreslený, což komplikuje analytické modelování. Je však třeba mít na paměti, že s nejjednodušším vstupním tokem a exponenciální službou (ty. v systémech Markov) je výstupní proud také nejjednodušší. Pokud má čas služby neexponenciální rozdělení, pak odchozí tok je nejen nejen jednoduchý, ale také ne opakující se.

Všimněte si, že časové intervaly mezi odchozími deklaracemi nejsou stejné jako servisní intervaly. Nakonec se může ukázat, že po skončení další služby bude QS nějakou dobu nečinný kvůli nedostatku aplikací. V tomto případě se interval odchozího toku skládá z doby nečinnosti QS a servisního intervalu pro prvního zákazníka přicházejícího po době nečinnosti.

V QS kromě odchozího toku obsluhovaných nároků může být tok neobsazených objednávek. Pokud takový QS obdrží opakující se tok a služba je exponenciální, pak je tok opakovaných nevyřízených deklarací také opakovaný.

Fronty kanálu zdarma. Ve vícekanálovém QS lze vytvářet fronty volných kanálů. Počet volných kanálů je náhodná hodnota. Výzkumníka by to mohlo zajímat různé vlastnosti tato náhodná proměnná. Obvykle se jedná o průměrný počet kanálů obsazených službou během intervalu průzkumu a jejich faktory zatížení.

Jak jsme si poznamenali dříve, v reálných objektech jsou aplikace postupně obsluhovány v několika CMO.

Volá se konečná sada sekvenčně propojených aplikací pro zpracování QS, které v nich cirkulují síť pro řazení do fronty (SeMO) (obr. 2.4, a).

Postava: 2.4.

SeMO se také nazývá vícefázová společná organizace trhu.

Později zvážíme příklad konstrukce IM SeMO.

Hlavními prvky SEMO jsou uzly (U) a zdroje (generátory) aplikací (D).

Uzel sítě jsou systémem čekání na fronty.

Zdroj - generátor nároků vstupujících do sítě a vyžadujících určité fáze služby v uzlech sítě.

Pro zjednodušené znázornění SeMO se používá graf.

Hrabě SeMO - směrovaný graf (digraf), jehož vrcholy odpovídají uzlům CEMO a oblouky představují přechody nároků mezi uzly (obr. 2.4, b).

Prozkoumali jsme tedy základní pojmy QS. Ale při vývoji počítačových systémů IM a jejich zlepšování se jistě využívá obrovský tvůrčí potenciál obsažený v analytickém modelování QS.

Pro lepší vnímání tohoto tvůrčího potenciálu se v první aproximaci zaměříme na klasifikaci modelů QS.

Poměrně často je při analýze ekonomických systémů nutné řešit tzv. Problémy ve frontě, které nastanou v následující situaci. Nechte systém analyzovat Údržba auta, skládající se z řady stanic různých kapacit. Na každé ze stanic (prvky systému) mohou nastat nejméně dvě typické situace:

počet požadavků je pro tuto stanici příliš velký, vznikají fronty a za zpoždění služby musíte platit;
stanice přijímá příliš málo požadavků a nyní je nutné počítat se ztrátami způsobenými prostojem stanice.

Je zřejmé, že účelem systémové analýzy je v tomto případě určit určitý poměr mezi ztrátami z důvodu fronty a ztráty v důsledku jen já stanic.

Teorie řazení - speciální sekce teorie systémů - jedná se o sekci teorie pravděpodobnosti, ve které jsou systémy čekání na kolosy studovány pomocí matematických modelů.

Queuing system (QS) - Toto je model, který zahrnuje: 1) náhodný tok požadavků, hovorů nebo zákazníků, kteří potřebují servis; 2) algoritmus pro implementaci této služby; 3) kanály (zařízení) pro službu.

Příkladem SOT jsou pokladny, čerpací stanice, letiště, prodejci, kadeřnictví, lékaři, telefonní ústředny a další zařízení, která slouží určitým aplikacím.

Problém teorie front spočívá ve vypracování doporučení pro racionální konstrukci QS a racionální organizace jejich práci, aby byla zajištěna vysoká účinnost služeb za optimální cenu.

Hlavním rysem úkolů této třídy je výslovná závislost výsledků analýzy a přijatých doporučení na dvou vnějších faktorech: frekvenci příjmu a složitosti objednávek (a tedy času jejich provedení).

Předmětem teorie řazení do fronty je stanovení vztahu mezi povahou toku požadavků, výkonem jednotlivého kanálu služby, počtem kanálů a účinností služby.

Tak jako charakteristiky společné organizace trhu považováno:

průměrné procento zamítnutých žádostí a ponechání systému nezpracovaných;
průměrný „prostoj“ jednotlivých kanálů a systému jako celku;
průměrná čekací doba ve frontě;
pravděpodobnost, že přijatá žádost bude okamžitě doručena;
zákon o distribuci délky fronty a další.

Dodáváme, že tvrzení (tvrzení) přicházejí k QS náhodným způsobem (v náhodných dobách) s body koncentrace a expanze. Čas služby pro každý požadavek je také náhodný, po kterém je servisní kanál uvolněn a je připraven splnit další požadavek. Každý QS, v závislosti na počtu kanálů a jejich výkonu, má určitou šířku pásma. Propustná kapacita SOT možná absolutní (průměrný počet žádostí vyřízených za jednotku času) a relativní (průměrný poměr počtu vyřízených žádostí k počtu podaných žádostí).

3.1 Modely frontových systémů.

Každou společnou organizaci trhu lze charakterizovat výrazem: (a B c d e f) kde

a - distribuce vstupního toku aplikací;

b - distribuce výstupního proudu aplikací;

c - konfigurace servisního mechanismu;

d - fronta disciplína;

e - čekající blok;

f - kapacita zdroje.

Nyní se podrobněji podívejme na každou charakteristiku.

Vstupní tok aplikací - počet žádostí přijatých do systému. Charakterizovaná intenzitou vstupního toku l.

Výstupní tok aplikací - počet aplikací obsluhovaných systémem. Charakterizovaná intenzitou výstupního toku m.

konfigurace systému odkazuje na celkový počet kanálů a uzlů služeb. SOT může obsahovat:

jeden kanálslužby (jedna dráha, jeden prodejce);
jeden servisní kanál, včetně několik po sobě jdoucích uzlů(jídelna, klinika, dopravník);
několik kanálů stejného typuslužby propojené paralelně (čerpací stanice, informační služba, stanice).

Lze tedy rozlišit jednokanálový a vícekanálový QS.

Na druhou stranu, pokud jsou všechny servisní kanály v QS zaneprázdněny, pak může příchozí požadavek zůstat ve frontě nebo může opustit systém (například spořitelna a telefonní ústředna). V tomto případě mluvíme o systémech s frontou (čekáním) a o systémech s poruchami.

Otáčet se Je sada požadavků, které vstoupily do systému pro servis a čekání na servis. Fronta se vyznačuje délkou fronty a její disciplínou.

Kázeň fronty Je pravidlem pro obsluhu požadavků z fronty. Mezi hlavní typy front patří následující:

PERPPO (kdo dřív přijde - je dřív na řadě) - nejběžnější typ;
POSPPO (poslední přišel - první sloužil);
POP (náhodný výběr aplikací) - z databáze.
PR - prioritní služba.

Délka fronty možná

neomezený - pak se mluví o systému s čistým očekáváním;
rovno nule - pak mluví o systému s poruchami;
omezená délka (smíšený systém).

Čekající blok - „kapacita“ systému - celkový počet požadavků v systému (ve frontě a ve službě). Takto, e \u003d c +d.

Kapacita zdrojegenerování požadavků na službu je maximální počet požadavků, které mohou vstoupit do QS. Například na letišti je kapacita zdroje omezena počtem všech existujících letadel a kapacita zdroje telefonní ústředny se rovná počtu obyvatel Země, tj. lze to považovat za neomezené.

Počet modelů QS odpovídá počtu možných kombinací těchto komponent.

3.2 Vstupní proud požadavků.

S každým časovým intervalem [ a, a+ T ], přiřadíme náhodnou proměnnou Xstejný jako počet požadavků přijatých systémem v daném čase T.

Volá se proud požadavků stacionárnípokud distribuční zákon nezávisí na počátečním bodě intervalu a, ale záleží pouze na délce tohoto intervalu T... Například tok požadavků na telefonní ústřednu během dne ( T\u003d 24 hodin) nelze považovat za stacionární, ale od 13 do 14 hodin ( T\u003d 60 minut) - můžete.

Stream se nazývá bez následkůpokud historie toku neovlivní příchod žádostí v budoucnu, tj. požadavky jsou na sobě nezávislé.

Stream se nazývá obyčejnýpokud ve velmi krátkém časovém období nemůže systém přijmout více než jeden požadavek. Například tok do kadeřnictví je běžný, ale ne do matriky. Ale pokud jako náhodná proměnná X vezměte v úvahu dvojici aplikací, které přicházejí do matriky, pak bude takový tok obyčejný (tj. někdy lze mimořádný tok zredukovat na obyčejný).

Stream se nazývá nejjednodušší , pokud je stacionární, bez následků a běžné.

Hlavní věta. Pokud je tok nejjednodušší, pak r.v. X [a. a + T ] je distribuován podle Poissonova zákona; ...

Dodatek 1... Nejjednodušší tok se také nazývá Poisson.

Důsledek 2. M(X)= M(X [ a , a + T ] )= lT, tj. po dobu T lT aplikace. V důsledku toho za jednu jednotku času systém přijme v průměru l aplikace. Toto množství se nazývá intenzita vstupní proud.

Zvažte PŘÍKLAD .

Studio přijímá v průměru 3 žádosti denně. Vzhledem k tomu, že je tok nejjednodušší, zjistěte pravděpodobnost, že během následujících dvou dnů bude počet aplikací alespoň 5.

Rozhodnutí.

Podle stavu problému l=3, T\u003d 2 dny, vstupní proud je Poisson, n ³5. při řešení je vhodné zavést opačnou událost, která spočívá ve skutečnosti, že v čase Tbude přijato méně než 5 žádostí. Proto podle Poissonova vzorce získáme

^

3.3 Stav systému. Maticový a přechodový graf.

V náhodném okamžiku přejde QS z jednoho stavu do druhého: čísla obsazené kanály, počet aplikací a front atd. QS tedy s n kanály a délka fronty rovná m, může být v jednom z následujících stavů:

E 0 - všechny kanály jsou zdarma;

E 1 - jeden kanál je zaneprázdněn;

E n - všechny kanály jsou obsazené;

E n +1 - všechny kanály jsou obsazené a jeden požadavek ve frontě;

E n + m - všechny kanály a všechna místa ve frontě jsou obsazena.

Podobný systém s poruchami může být ve státech E 0 – E n .

Pro čisté očekávání QS existuje nekonečné množství stavů. Takto, stát E n CMO v čase t Je to částka n aplikace (požadavky), které jsou v systému v tento moment čas, tj. n= n(t) - náhodná hodnota, E n (t) Jsou výsledky této náhodné proměnné a P n (t) Je pravděpodobnost, že systém bude ve stavu E n .

Již jsme obeznámeni se stavem systému. Všimněte si, že ne všechny stavy systému jsou stejné. Stav systému se nazývá zdrojpokud systém může tento stav opustit, ale nemůže se do něj vrátit. Stav systému se nazývá izolovaný, pokud systém nemůže opustit nebo vstoupit do tohoto stavu.

Pro přehlednost reprezentace stavů systému využívá schémata (tzv. Přechodové grafy), ve kterých šipky označují možné přechody systému z jednoho stavu do druhého, jakož i pravděpodobnosti těchto přechodů.

Obrázek 3.1 - přechodový graf

Comp.	E 0	E 1	E 2
E 0	P 0,0	P 0,1	P 0,2
E 1	P 1.0	P 1.1	P 1.2
E 2	P 2.0	P 2.2	P 2.2

Někdy je také vhodné použít přechodovou matici. V tomto případě znamená první sloupec počáteční stavy systému (aktuální) a poté jsou uvedeny pravděpodobnosti přechodu z těchto stavů do ostatních.

Protože systém nutně projde od jednoho

stavu do druhého, pak je součet pravděpodobností v každém řádku vždy roven jedné.

3.4 Jednokanálový QS.

3.4.1 Jednokanálový QS s poruchami.

Zvažujeme systémy, které splňují požadavky:

(P / E / 1): (- / 1 / ¥). Předpokládejme také, že doba služby zákazníka nezávisí na počtu zákazníků vstupujících do systému. Dále „P“ znamená, že vstupní tok je distribuován podle Poissonova zákona, tj. nejjednodušší „E“ znamená, že výstup je distribuován exponenciálně. Také zde a níže jsou uvedeny základní vzorce bez důkazu.

U takového systému jsou možné dva stavy: E 0 - systém je zdarma a E 1 - systém je zaneprázdněn. Vytvořme přechodovou matici. Pojďme vzít Dt - nekonečně malé časové období. Nechte událost A být tím do systému včas Dt byla tam jedna žádost. Událost B spočívá ve skutečnosti, že během Dt jedna žádost vyřízena. událost A i , k - po dobu Dt systém přejde do stavu E i ve stavu E k ... Protože l Je intenzita vstupního toku, pak během Dt systém přijímá v průměru l * Dt požadavky. To znamená pravděpodobnost přijetí jedné žádosti P (A) \u003djá * Dta pravděpodobnost opačné události P (Ā) \u003d 1-l * Dt. P (B) \u003dF(Dt)= P(b< D t)=1- e - m D t = m Dt - pravděpodobnost včasného vyřízení žádosti Dt... Pak A 00 - aplikace nedorazí nebo bude přijata, ale bude doručena. A 00 \u003d Ā + A * B. R 00 \u003d 1 - l * Dt... (to jsme vzali v úvahu (Dt) 2 - nekonečně malá hodnota)

01 - žádost bude přijata, ale nebude doručena. A 01 \u003d A * ... R 01 = l * Dt.

A 10 - aplikace bude doručena a nebude žádná nová. A 10 \u003d B * A. R 10 = m * Dt.

A 11 - aplikace nebude doručena nebo dorazí nová, která ještě nebyla doručena. A 11 \u003d + B * A. R 01 \u003d 1- m * Dt.

Získáme tedy přechodovou matici:

Comp.	E 0	E 1
E 0	1-l * Dt	l * Dt
E 1	m * Dt	1 m * Dt

Pravděpodobnost prostoje a selhání systému.

Pojďme nyní zjistit pravděpodobnost nalezení systému ve stavu E 0 kdykoliv t (ty. r 0 ( t) ). Funkční graf
znázorněno na obrázku 3.2.

Asymptota grafu je přímka
.

Je zřejmé, že začíná v určitém okamžiku t,

Obrázek 3.2

Konečně to chápeme
a
kde r 1 (t) Je pravděpodobnost, že v daném okamžiku t systém je zaneprázdněn (tj. je ve stavu E 1 ).

Je zřejmé, že na začátku operace QS nebude probíhající proces stacionární: bude to „přechodný“ nestacionární režim. Po nějaké době (která závisí na intenzitách vstupních a výstupních toků) tento proces vyprší a systém přejde do stacionárního provozního režimu v ustáleném stavu a pravděpodobnostní charakteristiky již nebudou záviset na čase.

Stacionární provoz a faktor vytížení systému.

Pokud je pravděpodobnost nalezení systému ve stavu E k , tj. R k (t), nezávisí na čase t, pak to říkají stacionární režim práce. V tomto případě hodnota
volal faktor zatížení systému (nebo snížená hustota toku aplikací). Pak pro pravděpodobnosti r 0 (t) a r 1 (t) dostaneme následující vzorce:
,
... Můžete také uzavřít: čím vyšší je faktor zatížení systému, tím pravděpodobnější bude selhání systému (tj. pravděpodobnost, že je systém zaneprázdněn).

U myčky je jedna jednotka údržby. Auta přijíždějí v Poissonově vzoru s intenzitou 5 aut za hodinu. Průměrná doba služby pro jeden stroj je 10 minut. Zjistěte pravděpodobnost, že přijíždějící vozidlo zjistí, že je systém zaneprázdněn, pokud QS pracuje ve stacionárním režimu.

Rozhodnutí. Podle stavu problému l=5, m y \u003d 5/6. Musíme zjistit pravděpodobnost r 1 - pravděpodobnost selhání systému.
.

3.4.2 Jednokanálový QS s neomezenou délkou fronty.

Budeme uvažovat o systémech, které splňují požadavky: (P / E / 1) :( d / ¥ / ¥). Systém může být v jednom ze států E 0 , …, E k ,… Analýza ukazuje, že po určité době začne takový systém pracovat ve stacionárním režimu, pokud výstupní průtok překročí vstupní průtok (tj. Činitel zatížení systému je menší než jeden). Vezmeme-li v úvahu tuto podmínku, získáme soustavu rovnic

řešení, které jsme zjistili, že. Tedy za předpokladu, že y<1, получим
Konečně,
a
- pravděpodobnost nalezení QS ve stavu E k v náhodném okamžiku.

Průměrný výkon systému.

Kvůli nerovnoměrnému příjmu požadavků do systému a výkyvům v době služby se v systému vytváří fronta. U takového systému můžete prozkoumat:

n - počet reklamací v SOT (ve frontě a ve službě);
proti - délka fronty;
w - čekací doba na zahájení provozu;
w 0 - celková doba strávená v systému.

Bude nás zajímat průměrné charakteristiky (tj. vezmeme matematické očekávání uvažovaných náhodných proměnných a zapamatujeme si to y<1).

- průměrný počet aplikací v systému.

Je průměrná délka fronty.

Je průměrná čekací doba na zahájení služby, tj. čekací doba ve frontě.

- průměrná doba, kterou aplikace stráví v systému - ve frontě a v provozu.

Myčka má jeden servisní blok a místo pro frontu. Auta přijíždějí v Poissonově vzoru s intenzitou 5 aut za hodinu. Průměrná doba služby pro jeden stroj je 10 minut. Najděte všechny průměrné charakteristiky společné organizace trhu.

Rozhodnutí. l=5, m \u003d 60min / 10min \u003d 6. Faktor zatížení y \u003d 5/6. Pak průměrný počet aut v systému
, průměrná délka fronty
, průměrná čekací doba na zahájení služby
hodin \u003d 50 minut a nakonec průměrná doba strávená v systému
hodina.

3.4.3 Jednokanálový QS smíšeného typu.

Předpokládejme, že délka fronty je m požadavky. Pak pro všechny s£ m, pravděpodobnost nalezení QS ve stavu E 1+ s , počítáno podle vzorce
, tj. jedna žádost je doručena a druhá s aplikace - ve frontě.

Pravděpodobnost výpadku systému je
,

a pravděpodobnost selhání systému je
.

Pro každý jsou uvedeny tři jednokanálové systémy l=5, m \u003d 6. Ale první systém je s poruchami, druhý s čistým čekáním a třetí s omezenou délkou fronty, m\u003d 2. Najděte a porovnejte pravděpodobnost prostojů pro tyto tři systémy.

Rozhodnutí. Faktor zatížení pro všechny systémy y \u003d 5/6. Pro systém s poruchami
... Pro systém s čistým čekáním
... Pro systém s omezenou délkou fronty
... Závěr je zřejmý: čím více aplikací je ve frontě, tím menší je pravděpodobnost výpadku systému.

3.5 Vícekanálový QS.

3.5.1 Vícekanálový QS s poruchami.

Budeme uvažovat o systémech (P / E / s): (- / s / ¥) za předpokladu, že doba provozu nezávisí na vstupním toku a všechny linky fungují samostatně. Vícekanálové systémy lze kromě faktoru zatížení charakterizovat také faktorem
kde s - počet servisních kanálů. Zkoumáním vícekanálového QS získáme následující vzorce (Erlangovy vzorce) pro pravděpodobnost nalezení systému ve stavu E k v náhodném okamžiku v čase:

, k \u003d 0, 1, ...

Nákladová funkce.

Stejně jako u jednokanálových systémů vede zvýšení faktoru zatížení ke zvýšení pravděpodobnosti selhání systému. Na druhé straně zvýšení počtu linek služeb zvyšuje pravděpodobnost odstávky systému nebo jednotlivých kanálů. Je tedy nutné najít optimální počet servisních kanálů pro daný QS. Průměrný počet linek bezplatné služby lze zjistit podle vzorce
... Představujeme С ( s) – nákladová funkce CMO v závislosti na z 1 - náklady na jedno odmítnutí (pokuta za nesplněnou žádost) a od z 2 - náklady na výpadek jedné linky za jednotku času.

Chcete-li najít optimální možnost, musíte najít (a to lze provést) minimální hodnotu nákladové funkce: Z(s) \u003d s 1* l * str s + s 2* , jehož graf je znázorněn na obrázku 3.3:

Obrázek 3.3

Hledání minimální hodnoty nákladové funkce spočívá v tom, že nejprve najdeme její hodnoty pro s \u003d 1, pak pro s \u003d 2, pak pro s \u003d 3 atd. dokud v určitém kroku nebude hodnota funkce C ( s) nebude větší než předchozí. To znamená, že funkce dosáhla svého minima a začala růst. Odpovědí bude počet servisních kanálů (hodnota s) u nichž je nákladová funkce minimální.

PŘÍKLAD .

Kolik servisních linek by měl QS s poruchami obsahovat, pokud l\u003d 2 žádosti / hodinu, m \u003d 1reb / \u200b\u200bhod., Pokuta za každé odmítnutí je 7 tisíc rublů, náklady na výpadek jedné linky jsou 2 tisíce rublů. za hodinu?

Rozhodnutí. y = 2/1=2. z 1 =7, z 2 =2.

Předpokládejme, že QS má dva servisní kanály, tj. s \u003d 2. Pak
... Proto, C (2) \u003d c 1 * l *str 2 + s 2 *(2- y *(1-str 2 )) = =7*2*0.4+2*(2-2*0.6)=7.2.

Pojďme to předstírat s \u003d 3. Pak
, С (3) \u003d с 1 * l *str 3 + s 2 *
=5.79.

Předpokládejme, že existují čtyři kanály, tj. s \u003d 4. Pak
,
, С (4) \u003d с 1 * l *str 4 + s 2 *
=5.71.

Předpokládejme, že QS má pět servisních kanálů, tj. s \u003d 5. Pak
, C (5) \u003d6,7 - více než předchozí hodnota. Optimální počet servisních kanálů je proto čtyři.

3.5.2 Vícekanálový QS s frontou.

Budeme uvažovat o systémech (P / E / s) :( d / d + s / ¥) za předpokladu, že doba provozu nezávisí na vstupním toku a všechny linky fungují samostatně. Řekneme, že systém nainstalován stacionární provozpokud je průměrný počet příchozích zákazníků menší než průměrný počet zákazníků obsluhovaných na všech linkách systému, tj. l

P (w\u003e 0) - pravděpodobnost čekání na zahájení provozu,
.

Druhá charakteristika umožňuje vyřešit problém stanovení optimálního počtu obslužných kanálů tak, aby pravděpodobnost čekání na zahájení služby byla menší než dané číslo. K tomu stačí vypočítat pravděpodobnost postupného čekání na s =1, s =2, s\u003d 3 atd.

PŘÍKLAD .

SMO je stanice záchranné služby pro malé sousedství. l\u003d 3 hovory za hodinu a m \u003d 4 hovory za hodinu pro jeden tým. Kolik posádek musíte mít na stanici, aby byla pravděpodobnost čekání na odjezd menší než 0,01?

Rozhodnutí. Faktor zatížení systému y \u003d 0,75. Předpokládejme, že jsou k dispozici dva týmy. Zjistíme pravděpodobnost čekání na zahájení služby pro s =2.
,
.

Předpokládejme, že existují tři brigády, tj. s \u003d 3. Podle vzorců to dostaneme r 0 \u003d 8/17, P (w>0)=0.04>0.01 .

Předpokládejme, že na stanici jsou čtyři brigády, tj. s \u003d 4. Pak to pochopíme r 0 \u003d 416/881, P (w>0)=0.0077<0.01 ... Proto by stanice měla mít čtyři brigády.

3.6 Dotazy k vlastní kontrole

Předmět a úkoly teorie řazení.
SOT, jejich modely a označení.
Vstupní proud požadavků. Vstupní průtok.
Stav systému. Maticový a přechodový graf.
Jednokanálový QS s poruchami.
Jednokanálový QS s frontou. Vlastnosti.
Stacionární provozní režim. Faktor zatížení systému.
Vícekanálový QS s poruchami.
Optimalizace nákladové funkce.
Vícekanálový QS s frontou. Vlastnosti.

3.7 Cvičení pro samostatnou práci

Snack bar čerpací stanice má jeden pult. Auta přijíždějí podle Poissonova rozdělení, průměrně 2 auta za 5 minut. V průměru k dokončení objednávky stačí 1,5 minuty, i když doba trvání služby je rozdělena exponenciálně. Najít: a) pravděpodobnost odstávky v protiopatření; b) průměrný výkon; c) pravděpodobnost, že počet přijíždějících vozidel bude alespoň 10.
Rentgenový přístroj dokáže vyšetřit v průměru 7 lidí za hodinu. Intenzita návštěvníků je 5 osob za hodinu. Za předpokladu stacionárního provozního režimu určete průměrné charakteristiky.
Doba služby v QS se řídí exponenciálním zákonem,
m \u003d 7 požadavků za hodinu. Najděte pravděpodobnost, že a) doba služby je v rozmezí od 3 do 30 minut; b) žádost bude doručena do jedné hodiny. Použijte tabulku hodnot funkcí e x .
Říční přístav má jedno kotviště, intenzita přítoku je 5 plavidel denně. Intenzita nakládacích a vykládacích operací je 6 plavidel denně. Mějte na paměti stacionární režim provozu a určete všechny průměrné charakteristiky systému.
l=3, m \u003d 2, pokuta za každou poruchu je 5 a cena prostojů pro jednu linku je 2?
Jaký je optimální počet servisních kanálů, pokud by QS měl, pokud l=3, m \u003d 1, pokuta za každou poruchu je 7 a cena prostoje jedné linky je 3?
Jaký je optimální počet servisních kanálů, pokud by QS měl, pokud l=4, m \u003d 2, pokuta za každou poruchu je 5 a cena prostoje jedné linky je 1?
Určete počet drah pro letouny s přihlédnutím k požadavku, aby pravděpodobnost čekání byla menší než 0,05. Současně je intenzita vstupního toku 27 letadel denně a intenzita jejich provozu 30 letadel denně.
Kolik ekvivalentních nezávislých dopravních linek by měla mít dílna, aby zajistila pracovní rytmus, při kterém by pravděpodobnost čekání na zpracování produktů měla být menší než 0,03 (každý produkt je vyráběn jednou linkou). Je známo, že intenzita příjmu objednávek je 30 položek za hodinu a intenzita zpracování produktu v jednom řádku je 36 položek za hodinu.
Spojitá náhodná proměnná X je distribuována exponenciálně s parametrem l \u003d 5. Najděte distribuční funkci, charakteristiky a pravděpodobnost zasažení r.v. X v rozmezí od 0,17 do 0,28.
Průměrný počet hovorů přicházejících na pobočkovou ústřednu za minutu je 3. Považujeme-li tok za Poissonův, určíme pravděpodobnost, že za 2 minuty přijde toto: a) dva hovory; b) méně než dva hovory; c) nejméně dva hovory.
V krabici je 17 dílů, z nichž 4 jsou vadné. Sběratel náhodně extrahuje 5 částí. Najděte pravděpodobnost, že a) všechny extrahované části jsou kvalitní; b) mezi obnovenými částmi jsou 3 vadné.
Kolik kanálů by měl mít QS s poruchami, pokud l\u003d 2 žádosti / hodinu, m\u003d 1 žádost / hodinu, pokuta za každé odmítnutí je 8 t rublů, cena výpadku jedné linky je 2 t. za hodinu?

Příklady řešení problémů frontových systémů

Je nutné řešit úkoly 1–3. Počáteční údaje jsou uvedeny v tabulce. 2-4.

Některá notace používaná v teorii řazení front pro vzorce:

n je počet kanálů v QS;

λ je intenzita příchozího toku požadavků P in;

v je intenzita odchozího toku požadavků P out;

μ je intenzita servisního toku P asi;

ρ - indikátor zatížení systému (provoz);

m je maximální počet míst ve frontě, který omezuje délku fronty aplikací;

i je počet zdrojů aplikací;

p k - pravděpodobnost k-tého stavu systému;

p о - pravděpodobnost nečinnosti celého systému, tj. pravděpodobnost, že jsou všechny kanály volné;

p sist - pravděpodobnost přijetí žádosti do systému;

p open - pravděpodobnost odmítnutí přijetí žádosti do systému;

p about - pravděpodobnost, že bude žádost doručena;

A je absolutní propustnost systému;

Q je relativní propustnost systému;

och - průměrný počet aplikací ve frontě;

o - průměrný počet požadavků v rámci služby;

sist je průměrný počet požadavků v systému;

och - průměrná čekací doba na požadavek ve frontě;

o - průměrná doba doručení žádosti, která se týká pouze obsluhovaných požadavků;

sis je průměrná doba strávená požadavkem v systému;

aw je průměrná doba omezující čekání na požadavek ve frontě;

Je průměrný počet obsazených kanálů.

Absolutní propustnost QS A je průměrný počet aplikací, ĸᴏᴛᴏᴩᴏᴇ systém může sloužit za jednotku času.

Relativní propustnost QS Q je poměr průměrného počtu aplikací obsluhovaných systémem za jednotku času k průměrnému počtu aplikací přicházejících během této doby.

Při řešení problémů ve frontě je nesmírně důležité dodržovat následující posloupnost:

1) určení typu SOT podle tabulky. 4,1;

2) výběr vzorců podle typu QS;

3) řešení problému;

4) formulace závěrů k problému.

1. Schéma smrti a reprodukce. Víme, že když máme k dispozici označený stavový graf, můžeme snadno psát Kolmogorovovy rovnice pro pravděpodobnosti stavu a také psát a řešit algebraické rovnice pro konečné pravděpodobnosti. Je třeba říci, že pro některé případy poslední rovnice

rozhodnout předem, formou dopisu. To lze provést zejména v případě, že stavový graf systému je tzv. „Schéma smrti a reprodukce“.

Stavový graf pro schéma smrti a reprodukce má formu zobrazenou na obr. 19.1. Zvláštností tohoto grafu je, že všechny stavy systému lze nakreslit do jednoho řetězce, ve kterém každý ze středních stavů ( S 1 , S. 2 , ..., S n-1) je spojen šipkou vpřed a vzad s každým ze sousedních stavů - pravým a levým a extrémními stavy (S. 0 , S. n) - pouze s jedním sousedním státem. Termín „schéma smrti a reprodukce“ pochází z biologických problémů, kde je změna velikosti populace popsána podobným schématem.

Se schématem smrti a reprodukce se velmi často setkáváme v různých praktických problémech, zejména v teorii řazení do fronty, v této souvislosti je užitečné pro ni jednou provždy najít konečné pravděpodobnosti stavů.

Předpokládejme, že všechny toky událostí, které pohybují systémem podél šipek v grafu, jsou nejjednodušší (pro stručnost budeme také nazývat systém S a proces v něm probíhající - nejjednodušší).

Pomocí grafu na obr. 19.1, budeme skládat a řešit algebraické rovnice pro konečné pravděpodobnosti stavu), existence vyplývá ze skutečnosti, že z každého stavu lze přecházet do sebe, do počtu stavů je konečný). Pro první stát S 0 máme:

(19.1)

Pro druhý stát S 1:

Na základě (19.1) je poslední rovnost redukována do formy

kde k bere všechny hodnoty od 0 do p. Takže konečné pravděpodobnosti p 0, p 1,..., р n splňují rovnice

(19.2)

navíc je nutné vzít v úvahu normalizační podmínku

str 0 + str 1 + str 2 +…+ str n \u003d 1. (19,3)

Vyřešme tento systém rovnic. Z první rovnice v (19.2) vyjádříme str 1 až r 0 :

str 1 = str 0. (19.4)

Od druhého, s přihlédnutím k (19.4), dostaneme:

(19.5)

‣‣‣ od třetího, s přihlédnutím k (19.5),

(19.6)

a obecně pro kohokoli k (od 1 do n):

(19.7)

Věnujme pozornost vzorci (19.7). Čitatel obsahuje součin všech intenzit stojících u šipek vedoucích zleva doprava (od začátku do tohoto stavu S k) a jmenovatel je součinem všech intenzit na šipkách vedoucích zprava doleva (od začátku do S k).

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, všechny pravděpodobnosti stavů r 0 , str 1 , ..., р n vyjádřeno prostřednictvím jednoho z nich ( r 0). Dosadíme tyto výrazy do normalizační podmínky (19.3). Dostáváme, vyndáme držáky r 0:

odtud dostaneme výraz pro r 0 :

(zvedli jsme závorky na sílu -1, abychom nepísali dvoupodlažní zlomky). Všechny ostatní pravděpodobnosti jsou vyjádřeny jako r 0 (viz vzorce (19.4) - (19.7)). Všimněte si, že koeficienty na r 0 v každém z nich není nic jiného než po sobě jdoucí členy řady za jednotkou ve vzorci (19.8). Proto výpočet r 0 , všechny tyto koeficienty jsme již našli.

Získané vzorce jsou velmi užitečné při řešení nejjednodušších problémů teorie front.

^ 2. Malý vzorec. Nyní odvodíme jeden důležitý vzorec vztahující se (pro omezující, stacionární režim) k průměrnému počtu aplikací L systémy, které jsou v systému zařazování do fronty (tj. obslouženy nebo zařazeny do fronty), a průměrná doba reklamačního pobytu v systému Ž sist.

Zvažte jakýkoli QS (jednokanálový, vícekanálový, Markov, nemarkovský, s neomezenou nebo omezenou frontou) a dva toky událostí s ním spojené: tok nároků přicházejících do QS a tok nároků opouštějících QS. Pokud je v systému zaveden omezující stacionární režim, pak se průměrný počet deklarací přicházejících na QS za jednotku času rovná průměrnému počtu deklarací opouštějících: oba toky mají stejnou intenzitu λ.

Označujeme: X (t) - počet žádostí, které na CMO dorazily dříve t. Y(t) - počet aplikací, které opustily SOT

až do chvíle t. Obě funkce jsou náhodné a v okamžiku příchodu požadavků se náhle změní (zvýší se o jednu) (X(t)) a opuštění aplikací (Y (t)). Typ funkce X (t) a Y (t) znázorněno na obr. 19,2; oba řádky jsou stupňovité, horní je X (t),dno- Y (t). Je zřejmé, že na každou chvíli t jejich rozdíl Z(t) \u003d X (t) - Y (t) není nic jiného než počet aplikací v SOT. Když řádky X (t) a Y (t) sloučit, v systému nejsou žádné aplikace.

Zvažte velmi dlouhou dobu T(mentálně pokračovat v grafu daleko za hranicemi výkresu) a vypočítat pro něj průměrný počet aplikací v QS. Bude se rovnat integrálu funkce Z (t) na tomto intervalu děleno délkou intervalu T:

L sist. = . (19.9) o

Ale tento integrál není nic jiného než oblast postavy zastíněná na obr. 19.2. Pojďme se na tento obrázek dobře podívat. Obrázek se skládá z obdélníků, z nichž každý má výšku rovnou jedné a základnu rovnou době pobytu v systému příslušné aplikace (první, druhý atd.). Pojďme si tyto časy označit t 1, t 2, ... Je pravda, že na konci intervalu T některé obdélníky nevstoupí do stínované postavy úplně, ale částečně, ale s dostatečně velkým T na těchto maličkostech nezáleží. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, můžeme to předpokládat

(19.10)

kde částka platí pro všechny objednávky, které přišly v daném čase T.

Pravou a levou část (.19.10) vydělte délkou intervalu T. Získáváme s přihlédnutím k (19.9),

L sist. \u003d. (19.11)

Vydělte a vynásobte pravou stranu (19.11) intenzitou X:

L sist. \u003d.

Ale velikost Tλ není nic víc než průměrný počet žádostí přijatých během ^ T. V případě, že rozdělíme součet všech časů t i pro průměrný počet žádostí získáme průměrnou dobu pobytu aplikace v systému Ž sist. Tak,

L sist. \u003d λ Ž sist. ,

Ž sist. \u003d. (19.12)

Toto je úžasný vzorec Little: pro jakýkoli QS, pro jakoukoli povahu toku požadavků, pro jakékoli rozložení servisního času, pro jakoukoli servisní disciplínu průměrná doba pobytu požadavku v systému se rovná průměrnému počtu požadavků v systému dělenému intenzitou toku požadavků.

Přesně stejným způsobem je odvozen druhý vzorec Little, který spojuje průměrnou dobu pobytu požadavku ve frontě ^ W och a průměrný počet aplikací ve frontě L och:

Ž och \u003d . (19.13)

Pro výběr místo spodního řádku na obr. 19.2 převzít funkci U (t) - počet aplikací, které zbývaly dříve t ne ze systému, ale z fronty (pokud zákazník přijíždějící do systému nestojí ve frontě, ale okamžitě přejde na servis, stále můžeme předpokládat, že je ve frontě, ale byl v něm nulový čas).

Littleovy vzorce (19.12) a (19.13) hrají důležitou roli v teorii řazení do fronty. Bohužel ve většině stávajících příruček nejsou tyto vzorce (prokázané v obecné podobě relativně nedávno) uvedeny 1).

§ 20. Nejjednodušší systémy řazení do fronty a jejich vlastnosti

V této části budeme uvažovat o některých nejjednodušších QS a odvodit výrazy pro jejich charakteristiky (ukazatele účinnosti). Zároveň si ukážeme základní metodické techniky charakteristické pro základní „Markovovu“ teorii front. Nebudeme pronásledovat počet vzorků QS, pro které budou odvozeny konečné výrazy charakteristik; tato kniha není příručkou o teorii řazení do fronty (k této roli se mnohem lépe hodí speciální příručky). Naším cílem je seznámit čtenáře s některými „malými triky“, které usnadňují průchod teorií front, což se v řadě dostupných (i když předstírá, že jsou populární) knih může zdát jako nesouvislý soubor příkladů.

Všechny proudy událostí, které přenášejí QS ze státu do stavu, v této části budeme uvažovat o nejjednodušších (aniž bychom to pokaždé specifikovali). Mezi nimi bude i takzvaný „tok služeb“. To znamená tok nároků obsluhovaných jedním nepřetržitě obsazeným kanálem. V tomto proudu má interval mezi událostmi, jako vždy v nejjednodušším proudu, exponenciální rozdělení (v mnoha příručkách se místo toho říká: „čas služby je exponenciální“, my sami tento termín v budoucnu použijeme).

1) V populární knize je ve srovnání s výše uvedenou mírně odlišnou derivací Littleova vzorce. Obecně je seznámení s touto knihou („Konverzace dva“) užitečné pro počáteční seznámení s teorií řazení do fronty.

V tomto odstavci bude exponenciální rozdělení servisních časů chápáno samo o sobě, jako vždy pro „nejjednodušší“ systém.

V průběhu prezentace představíme charakteristiky efektivity uvažovaného QS.

^ 1. p -kanálový SMO s poruchami (Erlang problém). Zde budeme uvažovat o jednom z prvních v čase, „klasických“ problémech v teorii čekání ve frontě;

tento problém vyplynul z praktických potřeb telefonování a byl vyřešen na začátku tohoto století dánským matematikem Erlantem. Problém je kladen následovně: existuje p kanály (komunikační linky), které přijímají tok požadavků s intenzitou λ. Tok služby má intenzitu μ (převrácená hodnota průměrné doby služby t o). Najděte konečné pravděpodobnosti stavů QS a charakteristiky jeho účinnosti:

^ A - absolutní propustnost, tj. průměrný počet požadavků vyřízených za jednotku času;

Q - relativní propustnost, tj. průměrný podíl příchozích aplikací obsluhovaných systémem;

^ P otevřeno - pravděpodobnost odmítnutí, to znamená, že aplikace ponechá QS bez obsluhy;

k - průměrný počet obsazených kanálů.

Rozhodnutí. Stavy systému ^ S. (QS) bude očíslován podle počtu požadavků v systému (v tomto případě se shoduje s počtem obsazených kanálů):

S 0 - v SOT není jediná aplikace,

S 1 - v QS je jeden požadavek (jeden kanál je zaneprázdněn, ostatní jsou zdarma),

S k - v CMO je k aplikace ( k kanály jsou obsazené, ostatní jsou zdarma),

S n - v CMO je p aplikace (všechny n kanály jsou obsazené).

Stavový graf CMO odpovídá schématu smrti v reprodukci (obr. 20.1). Označme tento graf - u šipek uveďte intenzitu proudů událostí. Z S 0 palců S 1 systém přenáší tok požadavků s intenzitou λ (jakmile přijde požadavek, systém vyskočí z S 0v {!LANG-636328c62736538749f9b0e025e2ed18!}{!LANG-9509504aa191500dd8b0d4f813418efd!}

{!LANG-a8d01fca13f450d5590affc9e80b71ed!}

{!LANG-e54efa50f6ea4c9ff77bd6dda8f35f0a!} ^ S.{!LANG-b9fce4650281400803bb03c7a0a45d8c!} S 1 →{!LANG-06aa61f93ec08cd374e86be4cf5a57b7!}{!LANG-da2e6d7d7a2efa26b55926eb2f83a19c!} {!LANG-756853b80d3f84489779bb0f4e84d230!}{!LANG-a511556b849ead7aa39c41723df55ae4!} {!LANG-984e6f87f5f85740900a9f7a2019c23e!}{!LANG-21428fd4ff53394e7f95167bf94b3127!} k{!LANG-b008f57f24d18a4b2bdbd5f22a97e2c5!} {!LANG-ad5b0a2aec73f0350b16e8e0664afefe!}{!LANG-1be849a82bdcb31ce2033bbb0c4a22ff!}

{!LANG-93ebb52936b3239df79fff6a01bc76a4!}

{!LANG-250f9e53b9f0d3b9889e215444c8519e!} {!LANG-978c240ae698e86126d0d16fe01b9d82!} {!LANG-065a57da7c1cb996353bebaa24dab4f5!}{!LANG-1f4760fde6686b7275001e3c6723480b!} {!LANG-9497e985d1fe91554dc0dcaac3d33aec!}

{!LANG-3af916c38cf2dfa05cf1350d3739dd09!}

{!LANG-243fa4c856d42c0c580b59c120b1eba3!}

{!LANG-5172231af78ba7a6382e31075da199f0!}

{!LANG-d14487848e7de7eaffd2cbce23adc8a4!}

{!LANG-148f2e1acb2ba035db75a4e2adbefd77!} ^ P otevřeno{!LANG-b975045c1c39d318096e3622dfafc29c!} p{!LANG-30bfab39ab56392d8fe1832e73a165b8!}

R{!LANG-c42986fce6ea1c0e2d5d575df3dbdd95!} r{!LANG-207661109ca8104d729dc179db70b14a!}

{!LANG-39a64c1a221b66f15d3dba0334a6905c!}

{!LANG-149a401180e089c540ddcf400f03112c!} P{!LANG-fbf5256df1e60fc2ad23f848dfe4d438!}

{!LANG-9f941e8153f56cef2b65ddcd1a8f9b94!} {!LANG-cb98e55b975db7c4496809bff4434ca7!}

{!LANG-b15ac8e2eb9eab5d6be20b1b882f30a3!} (20.8)

{!LANG-368b7be1f4b6abadb901cc910eb1d229!} {!LANG-672b18c716840a8384a8b143e6e90459!}{!LANG-95b04a4e219e3d5d4715e463a29828d0!} p{!LANG-2f6694df7e1a15cd433e1a8b086f71d2!} {!LANG-5182a9263d72a5a3506d14eac41c3634!}

k = 0 · {!LANG-603f96592878d9d8b76f5e7bdc7a1cdc!}{!LANG-6abf9359d379f2b1477bc22933b1d0a9!} {!LANG-12547ca5d9ec8744beb2638ef74518f1!}{!LANG-7c8a43dd7e87b45f6a344115ced14ad4!} {!LANG-bfa699561009f68b044201573129440e!} · {!LANG-1e8e1e172975ffdb783ee5a7e1bd4167!}

{!LANG-d2850fd889238b68265e5318d51faecf!} r{!LANG-8a2acf526de364f85f3d301f0c327579!} {!LANG-9f37ba421f04a9e2de82be470f0b9fbd!}0, 1, ..., {!LANG-fd152bd328847f29282ac3d9ab298a5d!}{!LANG-55c6ba36a41e6574bd3c94930aa68e2f!} {!LANG-672b18c716840a8384a8b143e6e90459!}{!LANG-c01f02cb3f23bd81191fbb147c16176c!} {!LANG-379991589a958b5295ff4ccb6fca25c3!}{!LANG-395c9ed5a920dcae3495229feec3a778!}

{!LANG-dfd32552b7cd08d0f6717c3a5de55e16!} (20.9)

{!LANG-694608f62c6ae440e78dbdd377a9b49e!}

{!LANG-263495c3fc2ba12d9d88a533d42f54a0!} (20.10)

{!LANG-5907eb1d234b199ab4c1b90645a43a52!}
{!LANG-62148b3cb29a4691a1ecf17dd6f53146!}
{!LANG-05786db4f3210f358244781520d8dadb!} n{!LANG-c4b646d6bc085bf4c82692afe0ebfa7e!} t{!LANG-4bfbae34badc6a08e39e6351a57466fc!} {!LANG-f53719ed51c82d011716ee6062a48f3e!}{!LANG-f8f7a54ca24a5d5a46b16afdfa0e2704!} {!LANG-672b18c716840a8384a8b143e6e90459!}{!LANG-62d769f788f3f66d92be9f46c413e7e8!} str 0 = 1/13, str 1 = 3/13, str 2 = 9/26, {!LANG-0339bae4f833d9b7909a6cef834ddc74!} = 9/26 ≈ 0,346,

A≈ 0,981, {!LANG-132bf2be3e39bd19ca8b930e92e955ad!} ≈ 0,654, P{!LANG-e20692c944c891f648a53d68951250d5!} {!LANG-7e5ac76aa9888547d4ef51dca6369471!} 1,96.

{!LANG-d30408ce0f810bafd35a94a224f8e05b!}

{!LANG-8976b06c826c787c440f68ce06c671d0!} {!LANG-af3f246e660b4f6ddb22e9d48910a87b!}{!LANG-6af1d40a103c5b20064d044077370398!} {!LANG-1ad471ec4e3014cea8317a6496210f28!}{!LANG-aca54b5cfaf82a5fd2afc9268bebec53!}

{!LANG-8e945b9ec1ce1e71096a83ae003798f2!}{!LANG-69a825959d05a8011fc628487ca9f2e5!}

{!LANG-2e5a67e405b70f21c1714f586e4f4949!} ; {!LANG-70e5d46723a8e1401b0bae87b48b845c!} t{!LANG-ac2a69e917ac9c75e934e1d2c04822bd!}

L sist. - {!LANG-631f274228bf4b0552c73cede41d3487!}

Ž{!LANG-efed2f245b3832808d75164491f8c160!}

{!LANG-d86fd1731c5714c1fd124b611bb27255!}{!LANG-6806af3d5936fbbfb1a710ca3480ba36!}

Ž{!LANG-1f242b4ddcff9fce324999b884ea98d5!} - {!LANG-1b18bd4820b9118f4ab350136bdc2269!}

P{!LANG-638400b2e3c1086237064a630467ad37!} - {!LANG-a6ad472fc18200693a1e36e5ec1474a5!}

{!LANG-dc0b272ff8189963fc9a65379ce9a0d0!} A{!LANG-0fbda163e1b9a81421e40aa7daac82cb!} {!LANG-68d2b09e3f3e77d20810ae80ae611922!}{!LANG-a5d1477788884fb3fdb9c231eb16b0e4!}

{!LANG-99910d2d35ff7fd7b0c10397f3fe2640!} {!LANG-8f9c190c7f381ea877b5dc19368cf76d!}{!LANG-63d9163a55865dda3f8fb2259efb3585!} {!LANG-5f4f8984d951cd3f252cc79358941f65!} 1.

{!LANG-59bffe77337deeb410c9e9a6650e9e2b!}

S 0 - {!LANG-f69cebf9147d696658129681c4747ee5!}

S{!LANG-516d5342ab04eb7f72d12a70e4f67ccf!}

S{!LANG-f9de9ffb8b3dc2446199d8ba6ae4fd4f!}

S{!LANG-caaea052e7659d41660198a7022673be!} k -{!LANG-c2115414470a17542d5e3de4a0482ae0!}

{!LANG-2b03b27c8c7e5e27ef8a920a2e291873!}

{!LANG-c7c928b5bdad14edfb4119b480822413!} {!LANG-49fe87a0ef9a0ef03c2a484e585da671!}{!LANG-a9be0a39b06c05e1fcc0a7ad46a7e6ee!}< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t{!LANG-e69651dc4d30df9ba5faac5492f74fe1!}

{!LANG-c1294930f46c4a65ef6642d72ddbdf3f!} {!LANG-03bcbb489b5137bd445d4007771167c1!}

str 0 = -1 =

{!LANG-f1f66ae998dd0538033cf50e6acb2d30!}

{!LANG-20d680f92b63768f9df9aac563be593d!}< 1 ряд сходится - это бесконечно убывающая геометрическая прогрессия со знаменателем р.
{!LANG-62148b3cb29a4691a1ecf17dd6f53146!}
{!LANG-4db7f2d4c2c98e9d23b6ac88204345a5!} {!LANG-3c892e826f6207cb81c721f2d6dc9a37!}{!LANG-0a9a4164dbf9ab3f66d3578eda37ba19!}<1). Теперь предположим, что это условие выполнено, и ρ <1. Суммируя прогрессию в (20.11), имеем

{!LANG-55c5295141e9ef8614deb8b3c1e54bd9!}

str{!LANG-1e79f803ca62dfb95c40b4da80d521b5!}

{!LANG-3c9dceacba4816a2b39e66df8f3414ae!} {!LANG-63d825862cae9d186c7109cabdb3a9e9!}{!LANG-859a6caee5e7711584c5407c81ea3598!}

{!LANG-9497e985d1fe91554dc0dcaac3d33aec!} = ρ {!LANG-eb2f621e0fcf680a3f6dc1d44e125b42!}{!LANG-dc5fb83bc1b8fcd70bbcdec0feba286e!} {!LANG-a87e235abb040ef4faf2787dd51bfa77!} ρ {!LANG-20f9e0868ba44a28d8e20178e0987a6c!}, ...,

{!LANG-43e16600b693f8829f0df8fccd7baed5!}

{!LANG-9497e985d1fe91554dc0dcaac3d33aec!}{!LANG-a694387d17372b372fdff95313235d23!} {!LANG-6c3a9e29f9d1db53009c9ee217ee9cfc!}{!LANG-4430849fdddc74739c8b43b93b5d096f!} {!LANG-08f5cc28ea2ea53d4f7f150bc1186c43!}ρ {!LANG-b5b78ea4a4ded2d6d906b6a055958844!}{!LANG-fbf873a07e72cb8713c4ca16495a7ddb!}

{!LANG-82332a2e512e427cb586e1fa4dce2c8a!} {!LANG-20f9e0868ba44a28d8e20178e0987a6c!}, {!LANG-9497e985d1fe91554dc0dcaac3d33aec!}, ..., {!LANG-51b9ad8d5796b47ed8eb804798ef96fa!}{!LANG-0de2b4baac33cf96047720c05faa4087!}
{!LANG-62148b3cb29a4691a1ecf17dd6f53146!}
{!LANG-53cdcf10ec4e3092d21eb6def6f67853!} {!LANG-40ce6b5b87b6b8331cb8adff6e0057db!}{!LANG-c3401f303e49e4b51055200a00aebba1!}<1), самое вероятное число заявок в системе будет 0.

{!LANG-4dc7b0ddb9541b69e220c05e96bf0767!} {!LANG-d1505d3356afbdf681a44f474d1040df!}{!LANG-1cc5279815c41a0c3256027ccf6ae711!} {!LANG-c2bd13c15a5e5a51cc514e102bf43ae6!}{!LANG-2075bc466ab24af8d5b0cf7be9b33b77!} {!LANG-96cf96eb7554e8fe3d1cff4ca4717cca!}{!LANG-1f9b529df447b612d8727e9d89dbaa53!} {!LANG-20f9e0868ba44a28d8e20178e0987a6c!}, {!LANG-320b759f11097a8370746be14eff8f9f!}{!LANG-54fe951f32d819f56c0a131fd8922a6b!}

L{!LANG-80b2a0fa5dc2f399651975a0d61091cc!} {!LANG-76e5707a6016e35f45b3ee3ad66ff3fe!}{!LANG-08186adbb475a39613466c4b4bcb0549!} str{!LANG-360247dd1dde268ce73c3e9db20bdcd5!} str 2 +…+k · str{!LANG-56f6b96354546cff91c1721d2af5fd11!}

{!LANG-74aa6ca1d07b22f9d7ad7355342939d4!}

{!LANG-30e7c4f0c0b99e4258becc179c37318b!} {!LANG-ab21d4c6eaf9df2eb9e427aac3492b00!} (20.13):

L{!LANG-f4ba1c254801890a38992c4dd9c6b38a!}

{!LANG-0bd4e93cb6a0bec06eee9ff92f508bf4!}

L{!LANG-d497030f848a615a3dfc8cb7b7ccd251!}

{!LANG-7927aeaa95f2101120b54e7cc6ca555c!} kρ {!LANG-b5b78ea4a4ded2d6d906b6a055958844!}{!LANG-88212d63111e7861cf45da6aeffb78f7!} {!LANG-b5b78ea4a4ded2d6d906b6a055958844!}{!LANG-8e7cb03b3bb88aacb1896662ba4aad61!}

L{!LANG-d497030f848a615a3dfc8cb7b7ccd251!}

{!LANG-9e9533a0f1d5d878e428e55669cb2fe9!}

L{!LANG-42a3edc63ad9d551236f926a51bf27fe!}

{!LANG-68740bd2c23f0a3a149cb5631dda9ae4!}

{!LANG-02c2cb994796aadf821167ea94ca7f01!}

L{!LANG-2e360aa00dd84c40fa150b9731127453!}

{!LANG-6ba34ff0d7af0db3721d74e98074fabf!}

Ž{!LANG-fad40f093c4b9799d483123b87ba3798!}

{!LANG-cc5cefd86dc7aa91692c252bd82d3de3!} L{!LANG-7c054eca8451cc3fd13ca26d486ad855!} L{!LANG-f80bcdc4721f5c277dbe47c8602879c0!} L{!LANG-8fa32827dbd7ef0ef0a6f5586271c609!} R{!LANG-1cc688bacfc6d8962baf2bbc29fd001d!} R{!LANG-40f526779ebd97df9ce86f09454bc74d!} {!LANG-065a57da7c1cb996353bebaa24dab4f5!}{!LANG-3ddde5c852012da966b7331db4442c3b!} Ž{!LANG-372dd86017a0253cb2dc79e7cd2ca78c!} L{!LANG-142966e5177d5f956b79777af750d61f!} Ž{!LANG-f77fc6ee0d77256c861af00e0d3a8b97!} L{!LANG-b6d25a732ba1643612b3239d40ebee6b!} Ž{!LANG-1811b55900a790bffacca34dd55e2fd6!} L{!LANG-2a977325f7f2b8a70ed1237845a0f45c!} Ž{!LANG-997d1360023160944115b2ca040b9ef2!} a{!LANG-4d6a4a2a76c316f11bf61ff30d83aaec!} a.

{!LANG-aaa844408d5dfbd3d5aea374f64da27b!}{!LANG-e8a16f84277a94d1cdebc7aede338622!} n{!LANG-7bcb462a9a19909f6fc504b142a5b5ac!}

N<1. В случае если ρ/n{!LANG-0c3562fd109469714602c5b7c7faa937!}

{!LANG-bef4990289647528434add93b4d7180d!} n < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для {!LANG-065a57da7c1cb996353bebaa24dab4f5!}{!LANG-6d7ab1723841473bea3f27c9092f1366!} n{!LANG-c3598a83759b5394caa5b43a962c55ea!}

(20.22)

{!LANG-1d1665bd58828c2a848a69e694fb2e47!} k{!LANG-66a183b12241c3b3f031e677639a708b!} L{!LANG-bba728b5a162706d9c846a53e37871af!} L{!LANG-2b154998e18cacf22be1627428d123ac!}

L och \u003d

{!LANG-184940bf3a21b13d29bff85a90dbe6fe!}

{!LANG-9fee7dc48708c838c5dc449c631b94c1!}

L och \u003d (20.23)

{!LANG-7457c841ba828dc76c40cdd8f75b4332!} {!LANG-8ce1a12a9fc4287a3b85ba79e1ed8957!}{!LANG-bd23e97d874ffb1621f3b60b593ddc38!}

L{!LANG-174cdc86b60f1ff7cd35b27c4c23a2d8!} L{!LANG-aaa42214e4b25401c2f26d4dfd8600e2!}

{!LANG-fbadf91611907d599faabb0df1aa4ae9!} L{!LANG-05de53229b760e5cf5f8ee9b1d2a28ac!} L{!LANG-83a0b28bf706ad8cc7cce09c6e35989b!} , {!LANG-e3706f87011aa0c9877b1975c15bd2f4!}

(20.25)

{!LANG-2c22e9de50033b30b10e70930a7c14a2!}
{!LANG-62148b3cb29a4691a1ecf17dd6f53146!}
{!LANG-1d637ebdbbb8b7f02221e40433d6ab49!} {!LANG-6fb2b10fec9e4e3bc68de273d9be1a73!}{!LANG-9b609d30db63d9a058da55be95a5f56b!} {!LANG-090210d49625dd7aaece0552b72bca24!}{!LANG-93a0288fa027b2176d28c652b8dce6d0!} + {!LANG-01bd2d069495da4d945ac4eae13a6015!} A{!LANG-ca83deb3e790c3f40451a476b4ad6835!} {!LANG-1fbd942aa6137900ed07b65f7c9d5a08!}{!LANG-95037418d506a8e32b0347b6f056bc27!} A{!LANG-a9810694ed1eedbe1102e8d80ed6d0a8!} {!LANG-6fb2b10fec9e4e3bc68de273d9be1a73!}{!LANG-1a59af1c5e4214806413c5b1bab0e5a4!}

{!LANG-dec1f4f7bb8074c3e0cf1da945a5b2ff!}

{!LANG-825cdf3ddb2ed81ba957409875cd6d2d!}<1, финальные вероятности существуют. По первой формуле (20.22) находим {!LANG-78a97dd5bd8d6cd9b0cd10a7a18e5c4f!}{!LANG-31bac04efdab1cda325cc0db31066b61!} Ž{!LANG-341a51072ca0113e87c78e9b2ccdb11b!}

{!LANG-d4ef5b996a3e11e7532a0eeb0f31fa6a!} . {!LANG-ef01456515d729c5fc1d4d78897194aa!}<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) L{!LANG-0c145116fd05c0252525f2e772495e2a!}

{!LANG-99bf339dd1c51e88b2617aa0370831c8!} L{!LANG-07498a7b5c5a683c03ab2e66d44920ef!} Ž{!LANG-3522da79fedfc33caaf7fc388b9d64fd!}

{!LANG-78fd667e5a677f8c65684a6fa1d6ff4d!}

{!LANG-2eef793ace5bddc5ea98b8e1b0ae57b7!}

{!LANG-2bd10c0f36fc1d8c2e4f7b2fc7e3eecc!}

{!LANG-181956d0e1b3b1c6ad8cc31195210e70!}

{!LANG-bb0d9a8c62846d41838de6eef8b45269!}

{!LANG-bff26face3c1669d824411acca87b673!}{!LANG-23d81e18b3777f92f8d71b702309ddea!}

{!LANG-2460534e7b626f0b8837ed007ab286b5!}{!LANG-78932368f710f534920b67cf438a26e1!}

{!LANG-acb4c4d35e8b0a90bcfdd10f71013dd8!} t{!LANG-2959d19f36f842e05be2bdca9674e560!} S{!LANG-45f7b443bb06471512d139461d13ffce!} S{!LANG-9587ef234bb28c96b7f986e47f677150!} S{!LANG-b8f50b44a64cebf19bf98f1c0b259847!} S{!LANG-63a37140ba6ca52c6660769a03744cd8!} S{!LANG-6f9fdbff71ee4979312d0af3991c8c2e!} S{!LANG-dbf4ad266d5cbf583a5db0cc97091394!}

{!LANG-ce8415dbcbae42d06990c3d6be8a3948!}

{!LANG-f4a7c69ca0434df277193c88abd59504!}

{!LANG-914ebe8823d60b1a37e77011504b35fc!}{!LANG-8b556b0ef6dcd951a25cde57c6d157f2!}

{!LANG-a78650ab0175fccdb1900e3f8fc16450!}

{!LANG-2cd4027e2ea4ef9d11bdb6a48f267f72!}

{!LANG-91a2577fbb8387e98a0eb6e2166cf62b!}{!LANG-5652306bf38904a33b848cfb7d92e53c!}

{!LANG-d050e9c63a35ce7743a611da835b3ea2!}{!LANG-62b6f4358da17b3bc369bf020da5419c!}

{!LANG-12f5845b49901cd899aba2e26ca91963!}

{!LANG-a6383b5f1cc078aca09740ae133c1b29!}{!LANG-b717bb718b5223a04a529e6068384ebb!}

{!LANG-6a5d28244fc0c27a38711c032f6e4223!}

{!LANG-8ce68c345289b5081140bb65599ba7b2!}

{!LANG-1f2d017c80f7e2b2ac171bd76d483c05!}

{!LANG-19411132206387790619ac3a854d6111!}

{!LANG-bff26face3c1669d824411acca87b673!}{!LANG-ee16a63b732561ac82656c8147a28274!} n{!LANG-f0306191479ac3ecdf658a4212bf45be!}

{!LANG-2460534e7b626f0b8837ed007ab286b5!}{!LANG-d8f31201d3616e859f1d2f79e8d99923!} t{!LANG-fb6ac3e8cad791d6b1794ff27f62a2cf!}

{!LANG-e6e7fac13bb5d58be8ad206bc41518ae!}{!LANG-d1e4549319c006e27d54c5343981057a!} S{!LANG-658e13f090615f91ff522b788f0caff0!}

S{!LANG-770d397a618494c6a23303cadf8fe5ef!}

S{!LANG-fe808b6d0a22d61a7be56ed4589c02e0!}

S{!LANG-bec8d26434dd0d1aafefa84750b83b41!}

S{!LANG-adbdc8e15b70a56f0d0a8b99d4327dca!} n{!LANG-6d257d5e95af73b4559238f6faf983d9!} n{!LANG-dc44d90ed506ca3674207add458a1f3b!}

{!LANG-056301f3028836db97d6de0b7fc8836b!}

{!LANG-6649118b626fb4d6ae13f2bf046f3762!}

{!LANG-3e3c8cdf160116d960be53abb16adc69!} S{!LANG-ac2e4580b68887051483e6e63ed720c4!} S{!LANG-4036287ccab1b4c345017a7ad741876e!} S{!LANG-b8f50b44a64cebf19bf98f1c0b259847!} S{!LANG-828342dff9b334edd4192aa892ceb702!} S{!LANG-ef9e470236ad8a680f95cd0ea993f919!} S{!LANG-812c89be265ad4215aa602ffa80bcd50!}

{!LANG-8063390688a90b5070eb3bb8a0ae090c!} S{!LANG-8a1612ab63b3ac8926b4ed5807825c5a!} S{!LANG-a4f339aa1aacad1ad682257bf0cdf9c0!} S{!LANG-5ae768d806d47272f250abe38762dec3!} S{!LANG-0827cbb91ebd30fb690600a908f94f6d!} S{!LANG-534717dc9fe881151dabe33331a826a1!}

{!LANG-6e5c8dfc4c71be2900ac07d97b903d9f!}

{!LANG-898a719a8d8eab6dfcbb54e57a7528d5!}{!LANG-e254ac1847095f3559782fca634be9f5!}{!LANG-e4d851cbfdc292a4954c1ac7b3182c3e!}:

kde n{!LANG-0e3b8448869d0dc3a1d73df0c63e0bfc!}

{!LANG-1ac01edf7bdb670019fb374e45e63a15!} S 0);

{!LANG-e3acaca24cf9ef4a8d9b37dda4a55485!}

{!LANG-86325dd5cf8cd0552922e0421306c57b!}

{!LANG-6656c93f5c799e8e0dc59bee0c6e1c00!}

{!LANG-9b0291deae518482a8162e8d15d0b86e!}

S{!LANG-6ce381c86b6eb9d9452d0bb0095f65c6!}

{!LANG-9813aa9af218389bf84b18567832f61a!} S{!LANG-6240b82baaaea1b7748a981de360b94c!}

{!LANG-9813aa9af218389bf84b18567832f61a!} S{!LANG-284a7ec5f0b1e1c422c7b6d9eded300c!}

{!LANG-ecc61fe22fed0a2c54ab23740ec7764c!}

{!LANG-bfd750d1e06f5e14a09091b3d696af7b!}

{!LANG-8e0b21e7a5b450f94d6fd74075e0c539!}

{!LANG-1ecfb62e2f3696f840e3b70de725e156!}{!LANG-a915cd75f7d48ba4e887143ce45862ae!}:

{!LANG-8a25d8a213f2a8416ce9aeea251f591d!}

{!LANG-034009ad14378a742e4c09f691498432!}

{!LANG-4a8cefeb76e8275608a11fd290adb364!}

{!LANG-cb9921b6a798226b75f455ea6452bb2a!}

{!LANG-16cea4e2b08e23215565f6ce02335c46!}

{!LANG-81151ff2372cef06b16f195f2be4061f!}

{!LANG-1f2c5e53d68596a06b6073817ea8e2f6!}

{!LANG-3b6a163a853a6d84110353f5402ae8db!}

{!LANG-5223202fedccb85aa7dea150950f1c82!}

{!LANG-a720724a35f8d0701cef08cdf553b9a8!}

{!LANG-3f3c38acfd240f5830c5dcf119b08ac9!}

{!LANG-0b3f464dc5016476b11db73005b599db!}

{!LANG-72632fe11e027df514868f2be5061639!}

{!LANG-22f2799d3ffeab9086ae4d520950be8c!}

{!LANG-e4406351daaf60713c5cdc863cfa7458!}

{!LANG-9b72be3ac9a5a75e5c23451dea9f1de6!}

{!LANG-8bef37d045a4767bb6bf927833cb694e!}

{!LANG-abc383024947f7ce52799353806ed625!}

{!LANG-5e3a3cc62c90bc41597bf67c9ea8a845!}

{!LANG-49b44991453451ffaafc27e85480446e!}

{!LANG-f6ed38b565afbae7d8f6015531211b5b!}

{!LANG-cd44b6fe2f1fc3e5a2d1776d54567ded!}

{!LANG-9c0024e04b6d08cbf5dae5e1093d7a1d!}

{!LANG-22387953b975a5172951f79bdd1f74d9!}

{!LANG-878ac8d037c5bed4aa08303165fa8cee!}

{!LANG-5a462a742c16c8076d1fa7d48dd3e321!}

{!LANG-97c22e2dbd07a09ff5aa8106ab38aafe!}

{!LANG-b1f8d1e04cc9d4faad1c9e3dc9acc370!}

{!LANG-198b9089fcc62a529b50f29d161ab782!}

{!LANG-0600bc0eb97b98f3d9e9bce04394bdc6!}

2) výběr vzorců podle typu QS;

3) řešení problému;

4) formulace závěrů k problému.

{!LANG-86ef49f2b939d81d2a570144598904e1!}

{!LANG-a70999fef740479cb979e40c620e8021!}

{!LANG-b155f56f6b6e27ff98d554ad45030a60!} S 1 , S. 2 {!LANG-7c0e2a1add1277b010b0b373bd4ddc1a!}{!LANG-cbe565d81d65e429d1b545bbbaef5c50!} (S. 0 , S.{!LANG-bbade86e744fd2546b0d74d12e53bbc1!}

{!LANG-0d6cd78c7c8b57c171510c105b6ba145!}

{!LANG-f67f396606ead3cced7de4f2caa14ae5!} S{!LANG-ce12db41d8ddaec92d1cf6bfd7a5530e!}

{!LANG-9ba190bcbe3852444ee150be01970b5f!}

{!LANG-847402f38139c35ca9cbd4e9e021bcb4!} S 0 máme:

(19.1)

Pro druhý stát S 1:

Na základě (19.1) je poslední rovnost redukována do formy

kde k{!LANG-da9b8fd09f666128223fd1ae4632b899!} p. Takže konečné pravděpodobnosti p 0, p 1,..., р n splňují rovnice

(19.2)

{!LANG-3d90899e060dc18d08f05b96581d6f38!}

str 0 + str 1 + str 2 +…+ str n \u003d 1. (19,3)

{!LANG-dfb52cc2b9273453f366c656b642cd74!} str 1 až r 0 :

str 1 = str 0. (19.4)

Od druhého, s přihlédnutím k (19.4), dostaneme:

(19.5)

{!LANG-35067351f25b02bec76cbd52106883fe!}

(19.6)

a obecně pro kohokoli k (od 1 do n):

(19.7)

{!LANG-e30f0a4c7f7be6d77785d08bfb014181!} S{!LANG-2fd93fd016cf63abb332f3c830c14ef1!} S k).

{!LANG-989f18f37445ab0f67ebf36573d56a2e!} r 0 , str 1 , ..., р n vyjádřeno prostřednictvím jednoho z nich ( r 0). Dosadíme tyto výrazy do normalizační podmínky (19.3). Dostáváme, vyndáme držáky r 0:

odtud dostaneme výraz pro r 0 :

(zvedli jsme závorky na sílu -1, abychom nepísali dvoupodlažní zlomky). Všechny ostatní pravděpodobnosti jsou vyjádřeny jako r{!LANG-e014b788c9699a3e36f2ef03aee495e1!} r{!LANG-14a3d05052afe295c5904b54785d3377!} r 0 , {!LANG-2e0480315178daebff375eb9423f373e!}

Získané vzorce jsou velmi užitečné při řešení nejjednodušších problémů teorie front.

{!LANG-2454096472c334ec25128889cad2dd6c!}

{!LANG-18a921eccc43065f949584e0832061fd!} L systémy, které jsou v systému zařazování do fronty (tj. obslouženy nebo zařazeny do fronty), a průměrná doba reklamačního pobytu v systému Ž sist.

{!LANG-941033e9f44a2d3c4882a0abbcd8dbee!}

Označujeme: {!LANG-02029d6f8468784c55fc266c02d2f51d!} počet žádostí, které na CMO dorazily dříve t. Y(t) — počet aplikací, které opustily SOT

až do chvíle t.{!LANG-3c6f2baaa08c1ad6d53c50cc882f5aae!} (X(t)) a opuštění aplikací (Y (t)). Typ funkce X (t) a Y (t){!LANG-fbc45a7361e2a63691b8cc1be10921a5!} X (t),{!LANG-b20b9b2a86cc531caf48b4211f4067ed!} Y (t). Je zřejmé, že na každou chvíli t jejich rozdíl Z(t){!LANG-1cf0dcd4ccf7a18783f4ef40cfd37dac!} není nic jiného než počet aplikací v SOT. Když řádky X (t) a Y (t) sloučit, v systému nejsou žádné aplikace.

Zvažte velmi dlouhou dobu T(mentálně pokračovat v grafu daleko za hranicemi výkresu) a vypočítat pro něj průměrný počet aplikací v QS. Bude se rovnat integrálu funkce Z (t){!LANG-5c0f5a725b7972b2e16aa444154d3da3!} T:

L sist. = . (19.9) o

{!LANG-66b7d97dc4f497e19888eebd48b23a92!} t 1, t 2, ... Je pravda, že na konci intervalu T některé obdélníky nevstoupí do stínované postavy úplně, ale částečně, ale s dostatečně velkým T{!LANG-574c81960a3a6b3303a726d70adbb030!}

(19.10)

{!LANG-958ded2a64c2e649ba462961b2c25d4b!} T.

Pravou a levou část (.19.10) vydělte délkou intervalu T. Získáváme s přihlédnutím k (19.9),

L sist. \u003d. (19.11)

Vydělte a vynásobte pravou stranu (19.11) intenzitou X:

L sist. \u003d.

Ale velikost Tλ není nic víc než průměrný počet žádostí přijatých během ^ T.{!LANG-b597497df23d438d7e74e8d583aaab6b!} t i pro průměrný počet žádostí získáme průměrnou dobu pobytu aplikace v systému Ž sist. Tak,

L sist. \u003d λ Ž sist. ,

Ž sist. \u003d. (19.12)

{!LANG-f78c618b8894eb566b9613472a66f2d2!} {!LANG-60490afcffa9e21d41716901e37aefb6!}

Přesně stejným způsobem je odvozen druhý vzorec Little, který spojuje průměrnou dobu pobytu požadavku ve frontě ^ W och a průměrný počet aplikací ve frontě L och:

Ž och \u003d . (19.13)

Pro výběr místo spodního řádku na obr. 19.2 převzít funkci U (t){!LANG-32e46f749a1f54714786244fe43aaf5a!} t{!LANG-5da52da76c8ba3f3aa125e2313741d1b!}

{!LANG-f469dab58ecded9fa8bf8bcdb377733c!}

{!LANG-998ecfee1bb3c58735bc69627cc9f7be!}

{!LANG-ef6769050c2d2ad67ef48aef2986fc40!}

{!LANG-ddd10a04a02d53557ea2281d4f8c3196!}

{!LANG-a68f0c2cb56df09bb6032c2f16ffd6eb!}

{!LANG-4efb079fcce25ecc5e953edc8a90a8a6!}

V průběhu prezentace představíme charakteristiky efektivity uvažovaného QS.

1. p{!LANG-a8d73966b59ad742d2a3e8a6f65b0fda!}{!LANG-42b02b8e75a6182f14227951382df68f!} p kanály (komunikační linky), které přijímají tok požadavků s intenzitou λ. Tok služby má intenzitu μ (převrácená hodnota průměrné doby služby t{!LANG-ed16e1d3269a314419749cc342c98fc1!}

{!LANG-eaa0d598cded990340ca310383d7487a!}

{!LANG-f6b71c37dd6033e7869127a3b0a13537!} absolutní propustnost, tj. průměrný počet požadavků vyřízených za jednotku času;

{!LANG-01e4059f46ece9fc28f51eae8d348f26!} relativní propustnost, tj. průměrný podíl příchozích aplikací obsluhovaných systémem;

^ P otevřeno{!LANG-9d61dd8b45789b68a425518fd52b1a82!}

{!LANG-a54e4ccf6836ec7274c344b8712254d1!} průměrný počet obsazených kanálů.

Rozhodnutí. Stavy systému ^ S. (QS) bude očíslován podle počtu požadavků v systému (v tomto případě se shoduje s počtem obsazených kanálů):

{!LANG-fa177d6cf18eef71e92459561ace0d15!} v SOT není jediná aplikace,

{!LANG-b8f3dad9df04466175ad26aa17c2e02b!} v QS je jeden požadavek (jeden kanál je zaneprázdněn, ostatní jsou zdarma),

{!LANG-da402324f9440d787f0d20698134f0d4!} v CMO je k aplikace ( k kanály jsou obsazené, ostatní jsou zdarma),

{!LANG-50e13c4adfb72290316cd07329c6f012!} v CMO je p{!LANG-6ead226f2dd7501c453baa2147d628ea!} n kanály jsou obsazené).

{!LANG-8ec925cd2f7995da2033ba961ff1cb48!} S 0 palců S 1 systém přenáší tok požadavků s intenzitou λ (jakmile přijde požadavek, systém vyskočí z S 0v {!LANG-636328c62736538749f9b0e025e2ed18!}{!LANG-de916589001bd83e4477f8269a0d5407!}

{!LANG-e54efa50f6ea4c9ff77bd6dda8f35f0a!} ^ S.{!LANG-b9fce4650281400803bb03c7a0a45d8c!} S 1 →{!LANG-06aa61f93ec08cd374e86be4cf5a57b7!}{!LANG-da2e6d7d7a2efa26b55926eb2f83a19c!} {!LANG-756853b80d3f84489779bb0f4e84d230!}{!LANG-a511556b849ead7aa39c41723df55ae4!} {!LANG-984e6f87f5f85740900a9f7a2019c23e!}{!LANG-21428fd4ff53394e7f95167bf94b3127!} k{!LANG-7296ce8cd5f148c2377d5dcd66015680!} {!LANG-ad5b0a2aec73f0350b16e8e0664afefe!}{!LANG-1be849a82bdcb31ce2033bbb0c4a22ff!}

{!LANG-20003da01b98259af376f70cdc11b26e!}

{!LANG-fcb00feb5f74d6d90c8acefb95d23960!}

{!LANG-3af916c38cf2dfa05cf1350d3739dd09!}

{!LANG-7c5411d51b6ab07983c6eef4af5552de!}

{!LANG-bf2994b6876c05be3203f232f18f9c98!}

{!LANG-19d5f231690bf4420eaa69ddecf39bdd!}

{!LANG-74c8faa190fc203303a5a4478d0fae57!} ^ P otevřeno{!LANG-3ed3ead09438e7dc6df981351e3afa2b!} p{!LANG-30bfab39ab56392d8fe1832e73a165b8!}

R{!LANG-c42986fce6ea1c0e2d5d575df3dbdd95!} r{!LANG-207661109ca8104d729dc179db70b14a!}

{!LANG-8254bfef9fa52ea187fff22fb155ed1a!}

{!LANG-32ccdb8e109515852737d84b49b7720c!} P{!LANG-fbf5256df1e60fc2ad23f848dfe4d438!}

{!LANG-9f941e8153f56cef2b65ddcd1a8f9b94!} {!LANG-cb98e55b975db7c4496809bff4434ca7!}

{!LANG-b15ac8e2eb9eab5d6be20b1b882f30a3!} (20.8)

{!LANG-368b7be1f4b6abadb901cc910eb1d229!} {!LANG-672b18c716840a8384a8b143e6e90459!}{!LANG-28211b06caa8ff4dc493bbb7513e32b4!} p{!LANG-2f6694df7e1a15cd433e1a8b086f71d2!} {!LANG-5182a9263d72a5a3506d14eac41c3634!}

{!LANG-d2850fd889238b68265e5318d51faecf!} r{!LANG-8a2acf526de364f85f3d301f0c327579!} {!LANG-9f37ba421f04a9e2de82be470f0b9fbd!}0, 1, ..., {!LANG-fd152bd328847f29282ac3d9ab298a5d!}{!LANG-55c6ba36a41e6574bd3c94930aa68e2f!} {!LANG-672b18c716840a8384a8b143e6e90459!}{!LANG-7ac0e78b6df7f9734e0c69055713ef78!} {!LANG-379991589a958b5295ff4ccb6fca25c3!}{!LANG-d07c8b2d96bc863f4a2cf04f72599bab!}

{!LANG-dfd32552b7cd08d0f6717c3a5de55e16!} (20.9)

{!LANG-694608f62c6ae440e78dbdd377a9b49e!}

{!LANG-263495c3fc2ba12d9d88a533d42f54a0!} (20.10)

{!LANG-8bf124b3c005722ae3ae32b753a53573!} n{!LANG-c4b646d6bc085bf4c82692afe0ebfa7e!} t{!LANG-1e0b29f8c4655d3828616e9545670ea8!} {!LANG-f53719ed51c82d011716ee6062a48f3e!}{!LANG-f8f7a54ca24a5d5a46b16afdfa0e2704!} {!LANG-672b18c716840a8384a8b143e6e90459!}{!LANG-62d769f788f3f66d92be9f46c413e7e8!} str 0 = 1/13, str 1 = 3/13, str 2 = 9/26, {!LANG-0339bae4f833d9b7909a6cef834ddc74!} = 9/26 ≈ 0,346,

A≈ 0,981, {!LANG-132bf2be3e39bd19ca8b930e92e955ad!} ≈ 0,654, P{!LANG-e20692c944c891f648a53d68951250d5!} {!LANG-7e5ac76aa9888547d4ef51dca6369471!} 1,96.

{!LANG-e5e2dad94b309dda0f4c270c07d641d2!}

{!LANG-8976b06c826c787c440f68ce06c671d0!} {!LANG-af3f246e660b4f6ddb22e9d48910a87b!}{!LANG-5cdc608505cc47bf31632acc6c51bb16!} {!LANG-1ad471ec4e3014cea8317a6496210f28!}{!LANG-cd4fe2340d3732709c396810803f96bf!}

{!LANG-a50114cb7978904adebf99326423180b!}

{!LANG-eaaf0e936691f00b40f6d1d1146ab233!}

{!LANG-f1b99b459ece9ec04ac397a94653b381!}

{!LANG-87ba9e0fbdb63bd70046556a9b7a0a7a!} ; {!LANG-70e5d46723a8e1401b0bae87b48b845c!} t{!LANG-e359060f019ccd8a0c774ebe3db72cca!}

{!LANG-ce9c08ffabdb827ae05f3ef86ac8dfa9!}

L sist. — {!LANG-631f274228bf4b0552c73cede41d3487!}

Ž{!LANG-6e0c97ba4c2332c5989983517568418b!}

{!LANG-d86fd1731c5714c1fd124b611bb27255!}{!LANG-5312f2018aac491a428b1f28bd0d902d!}

Ž{!LANG-1f242b4ddcff9fce324999b884ea98d5!} — {!LANG-1b18bd4820b9118f4ab350136bdc2269!}

P{!LANG-638400b2e3c1086237064a630467ad37!} — {!LANG-a6ad472fc18200693a1e36e5ec1474a5!}

{!LANG-dc0b272ff8189963fc9a65379ce9a0d0!} A{!LANG-0fbda163e1b9a81421e40aa7daac82cb!} {!LANG-68d2b09e3f3e77d20810ae80ae611922!}{!LANG-3202f2254e5276f893f59fdf88ed8da1!}

{!LANG-65a39f17fc86dcf1d717b3b15627459c!} {!LANG-8f9c190c7f381ea877b5dc19368cf76d!}{!LANG-1605d67d9f0d4427a3286e3f30c306a5!} {!LANG-5f4f8984d951cd3f252cc79358941f65!} 1.

{!LANG-18027336f7b0cbcb8d4ab8f7cafa2ca4!}

S 0 — {!LANG-f69cebf9147d696658129681c4747ee5!}

S{!LANG-586369b153a5841cb00acdeca1fbe7ba!}

S{!LANG-ae4d8a79c4442051580e81273327f429!}

S{!LANG-fac05bcfe0d70baef33c56cc84b1b979!} {!LANG-a54e4ccf6836ec7274c344b8712254d1!}{!LANG-c2115414470a17542d5e3de4a0482ae0!}

{!LANG-c212b2c68c016daaf979340f36df2532!}

{!LANG-ecc34484eda8f8243de5db5a2164272b!} {!LANG-49fe87a0ef9a0ef03c2a484e585da671!}{!LANG-f1fdb5499b8978452ee79906befb1f38!}< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t{!LANG-e3dd25f2ad0e5b669df4b45772df6c99!}

{!LANG-36e2c90a40af0bde31fe4a77cf9e57f6!}

{!LANG-9a9a863db835f6577d614b0e23af4cb3!}

{!LANG-e3cacbcd883b1f33858a9a3ba4822394!} {!LANG-03bcbb489b5137bd445d4007771167c1!}

str{!LANG-d0c1f45e25ac38ed89f605fa54a1ff99!}

{!LANG-20d680f92b63768f9df9aac563be593d!}< 1 ряд сходится — это бесконечно убывающая геометрическая прогрессия со знаменателем р. При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний {!LANG-3c892e826f6207cb81c721f2d6dc9a37!}{!LANG-0a9a4164dbf9ab3f66d3578eda37ba19!}<1).

{!LANG-6736b05ff0d281c03d5e7308fa985c43!}

str{!LANG-1e79f803ca62dfb95c40b4da80d521b5!}

{!LANG-3c9dceacba4816a2b39e66df8f3414ae!} {!LANG-63d825862cae9d186c7109cabdb3a9e9!}{!LANG-859a6caee5e7711584c5407c81ea3598!}

{!LANG-cc6cb6a9eacb75e7adac4ca2b9d1f7be!}

{!LANG-82332a2e512e427cb586e1fa4dce2c8a!} {!LANG-20f9e0868ba44a28d8e20178e0987a6c!}, {!LANG-9497e985d1fe91554dc0dcaac3d33aec!}, ..., {!LANG-51b9ad8d5796b47ed8eb804798ef96fa!}{!LANG-24a77eaaa279214825395bd1d5bad7f1!} {!LANG-3c46e32436b5cce7143fbcfc79e5b3ff!}{!LANG-09fb01b73be5fc01d95e807a7fa1f716!}<1), самое вероятное число заявок в системе будет 0.

{!LANG-4dc7b0ddb9541b69e220c05e96bf0767!} {!LANG-d1505d3356afbdf681a44f474d1040df!}{!LANG-1cc5279815c41a0c3256027ccf6ae711!} {!LANG-503a280c4b8217c1caf4f3d70982e7c1!}{!LANG-3d5a05da9cbb7b2924b6a0e5f5bd0181!} {!LANG-96cf96eb7554e8fe3d1cff4ca4717cca!}{!LANG-1f9b529df447b612d8727e9d89dbaa53!} {!LANG-20f9e0868ba44a28d8e20178e0987a6c!}, {!LANG-320b759f11097a8370746be14eff8f9f!}{!LANG-54fe951f32d819f56c0a131fd8922a6b!}

L{!LANG-d0a6613387de3ce59ab96e4bffc2e546!} {!LANG-76e5707a6016e35f45b3ee3ad66ff3fe!}1 ? str 1 + 2 ? str 2 +…+k ? str{!LANG-56f6b96354546cff91c1721d2af5fd11!}

{!LANG-5ee60ab7bce8e94c198258d190d535a1!}

{!LANG-30e7c4f0c0b99e4258becc179c37318b!} {!LANG-ab21d4c6eaf9df2eb9e427aac3492b00!} (20.13):

L{!LANG-f4ba1c254801890a38992c4dd9c6b38a!}

{!LANG-0bd4e93cb6a0bec06eee9ff92f508bf4!}

L{!LANG-d497030f848a615a3dfc8cb7b7ccd251!}

{!LANG-d6e3c346e7cd584b18793cdf620d42db!} kρ {!LANG-b5b78ea4a4ded2d6d906b6a055958844!}{!LANG-88212d63111e7861cf45da6aeffb78f7!} {!LANG-b5b78ea4a4ded2d6d906b6a055958844!}{!LANG-8e7cb03b3bb88aacb1896662ba4aad61!}

L{!LANG-d497030f848a615a3dfc8cb7b7ccd251!}

{!LANG-9e9533a0f1d5d878e428e55669cb2fe9!}

L{!LANG-42a3edc63ad9d551236f926a51bf27fe!}

{!LANG-bfc7fcf7aad4ead51d460532f136f34e!}

{!LANG-a2662b68a4251a5e9177d18dca157f87!}

L{!LANG-2e360aa00dd84c40fa150b9731127453!}

{!LANG-6ba34ff0d7af0db3721d74e98074fabf!}

Ž{!LANG-fad40f093c4b9799d483123b87ba3798!}

{!LANG-cc5cefd86dc7aa91692c252bd82d3de3!} L{!LANG-7c054eca8451cc3fd13ca26d486ad855!} L{!LANG-f80bcdc4721f5c277dbe47c8602879c0!} L{!LANG-a819144ff9b0f8d43225342b55883af3!}

{!LANG-6846212d56b5025ca0808acc67c4ef46!} R{!LANG-1cc688bacfc6d8962baf2bbc29fd001d!} R{!LANG-40f526779ebd97df9ce86f09454bc74d!} {!LANG-065a57da7c1cb996353bebaa24dab4f5!}{!LANG-e3d1f6bbca133bb0830bb7c41f3384f7!}

R{!LANG-f79f3fcfb053ffeff142e949c5abe789!} r{!LANG-0663857524acf3ee98549ea567f2fdc1!}

{!LANG-b52388446c0ccda36a09a5a3c7add163!}

{!LANG-ed345f381420f7de11b2d04e438c41b1!}{!LANG-ccd151977dd4f5dbcebc7a675d3d96a6!}

L och \u003d L{!LANG-fb209c0075cf4216268f6187ad50e852!}

{!LANG-113a1c41ff8566ef9783f4575fba332f!}

L{!LANG-5336cbaa00c2d35a23cc357f03b29f61!}

{!LANG-3b8d0a814d4f54ca54fda7c770b0c727!}

(20.21)

{!LANG-247d0c8042af0e8bb65ac0c85286bfd6!}

{!LANG-5d3dbb62591ea638b44ab9d8a9a4ae8b!}

{!LANG-3ca1ad92087e7bc4d5f47d4f887ef181!} {!LANG-8204cb5c0ef4e5ecbe266ea27608055d!}{!LANG-f69c65d7a752ecffb1d63e52a6015fac!}

{!LANG-5c0fa7737f8dbb12a85d3b6fb061ffd7!} l{!LANG-518c4e0063975d5651e303de1be5cc03!} Ž{!LANG-02779dc209a1693a411508e6ccecf277!} L{!LANG-b8bda232060ea6dd765ce680fc855ced!} Ž{!LANG-9c2ecb0f3a4c110967d2ce9e33b8542c!} L{!LANG-2d557b8293a6543d7c59bd403ffb455c!} Ž{!LANG-9d93dfd988a4c591b6fbe8293a54a9e1!}

{!LANG-92facfb8a729e78ddb344f27cc3fb0cc!} L{!LANG-142966e5177d5f956b79777af750d61f!} Ž{!LANG-f77fc6ee0d77256c861af00e0d3a8b97!} L{!LANG-b6d25a732ba1643612b3239d40ebee6b!} Ž{!LANG-1811b55900a790bffacca34dd55e2fd6!} L{!LANG-2a977325f7f2b8a70ed1237845a0f45c!} Ž{!LANG-997d1360023160944115b2ca040b9ef2!} a{!LANG-4d6a4a2a76c316f11bf61ff30d83aaec!} a.

{!LANG-1ed560c66766dbdf8a041306e43e1e1b!}

{!LANG-e8a16f84277a94d1cdebc7aede338622!} n{!LANG-6f382afbd30a2aafe1963872c3f9ea89!}

{!LANG-bb09798dec1de8bd2831d5c27c4516be!}

{!LANG-d12a26f4337dbca3b834678f03e5b462!} n{!LANG-93e6d584aeefd2588aa39f27d19f92f6!}

{!LANG-bef4990289647528434add93b4d7180d!} n < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для {!LANG-065a57da7c1cb996353bebaa24dab4f5!}{!LANG-f2b57505b9c835b3df630b6eda4a224f!} n{!LANG-c3598a83759b5394caa5b43a962c55ea!}

(20.22)

{!LANG-2a4247b0a3446ee5101f0aa27e627dfd!} k{!LANG-75f7e28d156a6a26a485484bed46f638!} L{!LANG-bba728b5a162706d9c846a53e37871af!} L{!LANG-2b154998e18cacf22be1627428d123ac!}

L och \u003d

{!LANG-184940bf3a21b13d29bff85a90dbe6fe!}

{!LANG-9fee7dc48708c838c5dc449c631b94c1!}

L och \u003d (20.23)

{!LANG-39d9f200f68fbd0350087d9860db2676!} {!LANG-8ce1a12a9fc4287a3b85ba79e1ed8957!}{!LANG-bd23e97d874ffb1621f3b60b593ddc38!}

L{!LANG-174cdc86b60f1ff7cd35b27c4c23a2d8!} L{!LANG-aaa42214e4b25401c2f26d4dfd8600e2!}

{!LANG-fbadf91611907d599faabb0df1aa4ae9!} L{!LANG-05de53229b760e5cf5f8ee9b1d2a28ac!} L{!LANG-83a0b28bf706ad8cc7cce09c6e35989b!} , {!LANG-e3706f87011aa0c9877b1975c15bd2f4!}

(20.25)

{!LANG-be63bc6f33b2b470f3986962c7fcf581!} {!LANG-6fb2b10fec9e4e3bc68de273d9be1a73!}{!LANG-9b609d30db63d9a058da55be95a5f56b!} {!LANG-090210d49625dd7aaece0552b72bca24!}{!LANG-93a0288fa027b2176d28c652b8dce6d0!} + {!LANG-e3764fb642ff2499190dc36ebe65cd15!}

{!LANG-472e32ca54539520cfaabfb11e19c17a!} A{!LANG-ca83deb3e790c3f40451a476b4ad6835!} {!LANG-1fbd942aa6137900ed07b65f7c9d5a08!}{!LANG-3929906b50127268ee7e5981ea54ed2c!} A{!LANG-1b92581cf64e037583c5e56ca2e63114!} {!LANG-6fb2b10fec9e4e3bc68de273d9be1a73!}{!LANG-62a0f51ba030815923199f2942e4e1ec!}

{!LANG-6c844e915870a6c99d0d523f2edc9371!}

{!LANG-99bf339dd1c51e88b2617aa0370831c8!} L{!LANG-07498a7b5c5a683c03ab2e66d44920ef!} Ž{!LANG-3522da79fedfc33caaf7fc388b9d64fd!}

{!LANG-78fd667e5a677f8c65684a6fa1d6ff4d!}

{!LANG-ef497310459ff71e79421a73d2f37f29!} {!LANG-1ad471ec4e3014cea8317a6496210f28!}{!LANG-25509073bda93ac3725b5bf0c322a13f!} {!LANG-1fbd942aa6137900ed07b65f7c9d5a08!}{!LANG-b0b213337c220b61baaae9e0e2bcbf8b!}

{!LANG-45fd9632ddb68f6f680d6bfbc704ef0e!} , {!LANG-f6c6f062cc917759d739254f760dfd79!}

{!LANG-5a00f895e4101b2eeb9090057fd5b0e1!} , {!LANG-1371d340897816ab4c936156e6ef2358!}

{!LANG-1d6afd541600be3d65c0e974745ed667!}

{!LANG-c38fac6657310c0370ad8f098ddfd9b0!}

{!LANG-cfb81157fe97bcab7d82a39795c0b747!}

{!LANG-f431e1fb07fe1a297feccf4c8415dc95!}

{!LANG-c519c45df4c5051f128c8f2e7522b118!}

{!LANG-39454352c6835795e0a789a5563f3a0b!}{!LANG-073fa99cae80d0dbd71abd4e7626c131!} {!LANG-11194a930d666cf255acbc5ee04f50c7!}{!LANG-545a1b57bb0dc0e4fd85fce9dd91f2c7!}

{!LANG-140f5ef22949fb6df48da3e705b0330d!} R{!LANG-21da603f7dcfec3db70ac0b00c5744c1!} {!LANG-1ad471ec4e3014cea8317a6496210f28!}{!LANG-5bc9ccbbe9d00b1619218d56e52e5618!} R{!LANG-120c8442c002ec3f2e69fecb4e04d2cc!} L{!LANG-a8555ca778cb537a59497b82882ddca0!} L{!LANG-669f41b1915f9865921bfe7b9c7ab6dd!} , {!LANG-ffc3188b13c156d5f357cf9db7d828fc!} Ž{!LANG-1f242b4ddcff9fce324999b884ea98d5!} , {!LANG-7dcf3d74c9cfb6c6a667b9b039e38e03!} Ž{!LANG-44a7789ca6d44166e11a75942fa1cbc6!}

{!LANG-d7e515a9783f29066d34551986aa5ea6!} m{!LANG-991dc43eb6a80fda919234110f256f37!}{!LANG-635c4ceb97007cd2224ca35107c90ea4!} {!LANG-537ac3fd61e64b26ee8f05ad7d15aafa!}{!LANG-d473c7e7da982ce5f2ecb6213b7b8369!} . {!LANG-8c048541d009d0bdf3990086d4b13c40!}

{!LANG-73949760875036533c765bf7192be931!} t{!LANG-547407fe161230fb1dafbd5a5797e779!} k{!LANG-60048facbca2860a698d44cdff4c841d!} k{!LANG-d796e27bd945596c453a8daaffbd5be0!}

{!LANG-2dc5ee1d66cf4468366cafa93a186767!} t{!LANG-4b9c65fd13c7986303bec88ff038ef59!}

Úkoly frontových systémů (QS). Nejjednodušší systémy řazení do fronty, příklady použití při řešení ekonomických problémů

3.1 Modely frontových systémů.

3.2 Vstupní proud požadavků.

3.3 Stav systému. Maticový a přechodový graf.

3.4 Jednokanálový QS.

3.4.1 Jednokanálový QS s poruchami.

3.4.2 Jednokanálový QS s neomezenou délkou fronty.

3.4.3 Jednokanálový QS smíšeného typu.

3.5 Vícekanálový QS.

3.5.1 Vícekanálový QS s poruchami.

3.5.2 Vícekanálový QS s frontou.

3.6 Dotazy k vlastní kontrole

3.7 Cvičení pro samostatnou práci

{!LANG-bb0d9a8c62846d41838de6eef8b45269!}

{!LANG-1f2d017c80f7e2b2ac171bd76d483c05!}

{!LANG-86ef49f2b939d81d2a570144598904e1!}

{!LANG-2454096472c334ec25128889cad2dd6c!}

{!LANG-f469dab58ecded9fa8bf8bcdb377733c!}

{!LANG-eaaf0e936691f00b40f6d1d1146ab233!}

{!LANG-1ed560c66766dbdf8a041306e43e1e1b!}

{!LANG-6bc8d2fe18abb67700153bb7a0d2a733!}

{!LANG-907af812295e74df12c5e6626975f9b2!}