Matematický model příkladu systému hromadné obsluhy. Simulační modelování systémů hromadné obsluhy

Chetverikov S. Yu., Popov M.A.

Rusko, Institut ekonomiky a podnikání (Moskva)

Teorie systémů hromadné obsluhy je aplikovaná matematická disciplína, která studuje číselné charakteristiky jevů vyskytujících se v ekonomice. Patří mezi ně fungování telefonního centra, středisek spotřebitelských služeb, pokladny v supermarketu atd.

Matematické modely takových objektů jsou systémy řazení do front (QS) popsané následovně: požadavky (aplikace na obsluhu) vstupují do systému, z nichž každý je nějakou dobu obsluhován a poté systém opouští. Kvůli omezeným zdrojům (počet obsluhujících pokladen, rychlost obsluhy atd.) je však systém schopen obsloužit pouze určitý počet pohledávek současně. Matematické modely jsou v tomto případě navrženy tak, aby řešily problém výpočtu numerických ukazatelů kvality fungování QS.

Při konstrukci QS modelů se zásadně rozlišují dva systémy: deterministický a stochastický, které vlastně určují typ matematický model.

Zvažte nejjednodušší deterministický systém sestávající z P identická zařízení, ve kterých požadavky přicházejí v deterministických (konstantních) časových intervalech a čas na obsluhu každého požadavku je také konstantní. Je zřejmé, že pokud požadavky přicházejí v intervalech

a servisní doba pro každý požadavek je

pak nutnou a postačující podmínkou pro normální fungování systému je splnění nerovnosti

V opačném případě se časem požadavky v systému nahromadí.

Parametry X a q mají jednoduchý fyzikální význam:

X- průměrný počet požadavků přicházejících za jednotku času nebo intenzita příchozího toku;

q je průměrný počet požadavků, které je každé zařízení schopno obsloužit za jednotku času, nebo intenzita požadavků na obsluhu jedním zařízením;

/ 7ts - průměrný počet požadavků, které jsou schopny obsloužit P spotřebičů, nebo požadavek náročnosti údržby celého systému.

Podmínka (1) tedy znamená, že intenzita příchozího toku by neměla překročit intenzitu servisních požadavků celého systému. Zvažte množství

Takzvané spouštění systému.

Pak lze nerovnost (1) přepsat jako:

V tomto případě lze zátěž interpretovat jako průměrný zlomek času, během kterého jsou zařízení zaneprázdněna obsluhou požadavků, a hodnotu 1 - p - jako průměrný zlomek času, během kterého jsou zařízení nečinná.

Na závěr ještě jedna poznámka k fungování systému s deterministickými charakteristikami:

pokud je v počátečním okamžiku systém volný a podmínka (2) je splněna, pak se každý požadavek vstupující do systému okamžitě stane servisním zařízením;

v případě p

konečně, pokud p > 1, pak za jednotku času se fronta zvýší v průměru o Mr-1).

Ve skutečných systémech řazení hrají významnou roli prvky náhodnosti:

za prvé, doby mezi příchody žádostí nejsou deterministické;

za druhé, doby obsluhy požadavků nejsou deterministické.

Kromě toho se prvky náhodnosti mohou objevit z jiných důvodů, například selhání prvků systémů hromadné obsluhy.

Ukazuje se, že prvky nahodilosti výrazně ovlivňují kvalitu fungování systémů služeb. Pokud tedy zatížení p = 1, pak, na rozdíl od deterministických systémů, ve stochastických systémech má fronta v průměru tendenci k nekonečnu v čase. Fronty ve stochastických systémech se tvoří i v případě p

Zvažte formalizovaný popis QS. Hlavní parametry QS jsou:

příchozí proud požadavků;

struktura systému;

časové charakteristiky požadavků na služby;

služební kázeň.

Pojďme se na tyto možnosti podívat.

Příchozí proud vyznačující se náhodnými okamžiky příjmu požadavků v jednoduchý systém a pro složité systémy – a typy požadavků, které v těchto chvílích přicházejí.

Při specifikaci náhodného proudu se obvykle předpokládá, že vstupní proud je rekurentní a nejčastěji Poissonův.

Udělejme několik poznámek ke správnosti popisu toků požadavků vstupujících do reálných systémů Poissonovou a rekurentních. Je zřejmé, že vlastnost absence následného efektu v reálných systémech je extrémně vzácná, protože tok s takovou vlastností může obdržet libovolně velký počet požadavků s nenulovou (i když extrémně malou) pravděpodobností v libovolném libovolně krátkém období. čas. Praxe však ukazuje, že popis příchozího proudu Poissonem je ve většině případů legitimní s dostatečnou mírou přesnosti. Dalším matematickým potvrzením této skutečnosti je Khinchinův teorém, který říká, že spojení velkého počtu „vzácných“ toků za velmi slabých omezení dává Poissonův tok.

Druhá vlastnost Poissonova toku - stacionárnost - také nepřitahuje kritiku. Intenzita příchozího toku zpravidla závisí na denní době, roce atd. Pokud jsou zachovány vlastnosti nepřítomnosti následného účinku a obyčejnosti, pak se získá nestacionární Poissonův tok. V řadě případů je možné vyvinout matematické modely pro výpočet ekonomických systémů s takovýmto příchozím tokem, ale výsledné vzorce jsou velmi těžkopádné a těžko aplikovatelné v praxi. Z tohoto důvodu jsou výpočty omezeny na určitý časový interval, ve kterém se intenzita příchozího proudění mění jen málo.

Pokud se opustí pouze vlastnost ordinality, pak se získá neobyčejný Poissonův tok, ve kterém okamžiky příchodu požadavků tvoří běžný Poissonův tok, ale v každém takovém okamžiku přichází náhodný počet požadavků. Většina výsledků, které jsou platné pro systémy s Poissonovým tokem, se prakticky nezmění na systémy s neobyčejným Poissonovým tokem.

Nastavení struktury QS je nutné uvést seznam všech prvků dostupných v systému a uvést, jaké typy požadavků nebo dokonce v jakých fázích služby může každý prvek sloužit. V tomto případě může jeden prvek obsluhovat požadavky několika typů a naopak požadavky stejného typu lze obsluhovat na několika prvcích. V následujícím budeme předpokládat, že QS má jeden nebo více identických prvků a každý požadavek lze obsloužit na kterémkoli z nich. Systémy tohoto typu se nazývají jednořádkový(jeden prvek) popř víceřádkový(více položek).

Servisní systémy mohou mít prvky pro požadavky na čekání na zahájení služby. Pokud je takových prvků nekonečně mnoho, pak se mluví o systémech s čekáním, pokud je jejich počet konečný - o systémech s konečným počtem čekacích míst, pokud vůbec chybí (požadavek, kvůli kterému byly všechny prvky v daném okamžiku obsazeny ztratí vstup do systému, příkladem jsou běžné telefonní systémy) - o systémech se ztrátami.

Načasování požadavky na služby jsou také komplexním objektem pro formalizovaný popis. Obvykle se předpokládá, že servisní časy všech zákazníků jsou na sobě nezávislé a jsou rovnoměrně rozložené náhodné veličiny. Pokud QS přijímá požadavky několika typů, může rozložení doby služby záviset na typu požadavku.

Servisní disciplína spočívá v pravidle řazení požadavků do fronty a pořadí, ve kterém jsou vybírány z fronty na obsluhu, rozdělení prvků mezi požadavky a ve vícefázových systémech - mezi fázemi obsluhy. Budeme předpokládat, že v systému je implementována nejjednodušší disciplína - obsluha požadavku v pořadí příjezdu (FIFO). Ve víceřádkových systémech je vytvořena společná fronta pro všechny prvky a první nárok ve frontě jde na libovolný uvolněný prvek.

QS však využívá i složitější servisní disciplíny. Nejjednoduššími příklady takových disciplín jsou inverzní (obrácené) pořadí obsluhy (LIFO), ve kterém je obsluhován požadavek, který do systému vstoupil jako poslední.

Disciplína jednotného oddělení prvků systému, ve kterém každý z P požadavky v systému jsou obsluhovány stejnou rychlostí 1/p. Někdy, v okamžiku, kdy požadavek vstoupí do systému, se zjistí čas jeho obsluhy (práce, která má být vykonána). Pak je možné použít disciplíny závislé na zbytkových dobách obsluhy požadavků. Zejména disciplína obsluhy prvního požadavku s minimálním zbývajícím servisním časem vám umožňuje kdykoli získat minimální délku fronty. Využití komplexních servisních disciplín velmi často umožňuje bez dodatečných nákladů výrazně zlepšit kvalitu fungování QS.

Speciální třídou QS jsou prioritní systémy, které přijímají proudy požadavků několika priorit a požadavků více vysoké priority mají přednost před požadavky na nižší prioritu, tzn. sloužil dříve. Priority mohou být relativní, když požadavky s vyšší prioritou nepřeruší služby požadavků s nižší prioritou na prvcích, a absolutní, když k takovému přerušení dojde.

V případě absolutních priorit jsou možné i různé modifikace: nedostatečně obsluhovaní zákazníci s přerušenou službou opouštějí systémy (systémy s výpadkem), jsou nadále obsluhováni poté, co systém opustí všichni zákazníci s vyšší prioritou (systémy s následnou péčí), jsou obsluhováni znovu.

Servisní disciplíny by také měly zahrnovat takové faktory jako přípravná fáze před zahájením obsluhy dalšího požadavku nebo po příchodu požadavku do volného systému, fáze přepnutí prvku na obslužné požadavky jiného typu, obsluha požadavků nespolehlivými prvky systému atd. Konečně lze omezit dobu, kterou požadavek stráví v systému, nebo dobu, kterou trvá čekání na zahájení služby.

Pojďme si nyní popsat ty vlastnosti QS, které uživatele zajímají. Někdy se jim v praxi říká pravděpodobnostně-časové charakteristiky. Nejdůležitější z nich jsou délka fronty(tj. počet požadavků čekajících na obsluhu) a čekací dobu, než se žádost začne zobrazovat. Vzhledem k tomu, že jak délka fronty, tak i doba čekání na zahájení služby jsou náhodné proměnné, jsou přirozeně popsány svými vlastními distribucemi. Navíc rozložení délky fronty a čekací doby závisí na aktuálním čase.

V systémech se ztrátami nebo konečným počtem čekacích míst patří mezi nejdůležitější charakteristiky také pravděpodobnost ztráty nároku. Někdy spolu s délkou fronty zvažují celkový počet požadavků v systému, a spolu s čekací dobou spuštění služby - doba setrvání požadavku v systému.

V systémech se ztrátami nebo konečným počtem čekacích míst, stejně jako v systémech s čekáním a načítáním p

Většina prací o teorii front je věnována hledání stacionárních charakteristik, ačkoli nestacionární charakteristiky byly studovány dostatečně podrobně.

Literatura

• 1. Gnedenko B.V. Pravděpodobnostní kurz. Moskva: Fizmatgiz, 1961.
• 2. Feller W.Úvod do teorie pravděpodobnosti a její aplikace.T.I. M.: Mir,
• 1984.
• 3. Gnedenko B.V., Kovalenko I.N.Úvod do teorie front. Moskva: Nauka, 1966.
• 4. Saaty T.L. Základy teorie hromadné obsluhy a její aplikace. M.: Sov. rádio, 1965.

Práce na kurzu

"Simulace systému řazení"

v kurzu "Operační výzkum"

Úvod

V operačním výzkumu se často setkáváme se systémy navrženými pro opakované použití při řešení stejného typu problémů. Procesy, které v tomto případě vznikají, se nazývají servisní procesy a systémy se nazývají queuing systems (QS). Každý QS se skládá z určitého počtu servisních jednotek (přístrojů, zařízení, bodů, stanic), které se nazývají servisní kanály. Kanály mohou být komunikační linky, operační body, počítače, prodejci atd. Podle počtu kanálů se QS dělí na jednokanálové a vícekanálové.

Aplikace obvykle přicházejí na QS ne pravidelně, ale náhodně a tvoří tzv. náhodný tok aplikací (požadavky). Služba aplikací také pokračuje nějakou náhodnou dobu. Náhodná povaha toku aplikací a servisního času vede k tomu, že QS je zatěžován nerovnoměrně: v některých časových obdobích se hromadí velmi velké množství aplikací (buď se řadí do fronty, nebo nechávají QS neobsloužené), zatímco v jiných intervalech QS pracuje s nedostatečným zatížením nebo nečinností.

Předmětem teorie hromadné obsluhy je konstrukce matematických modelů, které spojují dané provozní podmínky QS (počet kanálů, jejich výkon, povaha toku aplikací atd.) s výkonnostními ukazateli QS, které popisují jeho schopnost vyrovnat se s tokem aplikací. Jako ukazatele výkonnosti QS se používají následující:

– Absolutní propustnost systému ( A

Q

- pravděpodobnost odmítnutí obsloužit aplikaci ();

k);

- průměrný počet žádostí ve frontě ();

QS se dělí na 2 hlavní typy: QS s poruchami a QS s čekáním (fronta). V QS s odmítnutím je požadavek, který dorazí v době, kdy jsou všechny kanály obsazeny, odmítnut, opustí QS a neúčastní se dalšího servisního procesu (například požadavek na telefonický rozhovor v době, kdy jsou všechny kanály obsazeny). obsazeno obdrží odmítnutí a nechá QS neobslouženo) . V QS s čekáním požadavek, který přijde v době, kdy jsou všechny kanály obsazené, neodejde, ale čeká se ve frontě na službu.

Jednou z metod výpočtu ukazatelů výkonnosti QS je metoda simulace. Praktické využití počítačového simulačního modelování zahrnuje konstrukci vhodného matematického modelu, který zohledňuje faktory neurčitosti, dynamické charakteristiky a celý komplex vztahů mezi prvky zkoumaného systému. Simulační modelování provozu systému začíná určitým konkrétním počátečním stavem. Díky implementaci různých událostí náhodného charakteru přechází model systému v následujících okamžicích do dalších možných stavů. Tento evoluční proces pokračuje až do konce plánovacího období, tzn. až do konce simulace.

1. Hlavní charakteristiky CMO a ukazatele jejich účinnosti

1.1 Koncept Markovova stochastického procesu

Nechť existuje nějaký systém, který mění svůj stav náhodně v průběhu času. V tomto případě říkáme, že v systému probíhá náhodný proces.

Proces se nazývá proces s diskrétními stavy, pokud lze jeho stavy předem vyčíslit a přechod systému z jednoho stavu do druhého probíhá skokově. Proces se nazývá proces se spojitým časem, jestliže k přechodům systému ze stavu do stavu dochází okamžitě.

Operační proces QS je náhodný proces s diskrétními stavy a spojitým časem.

Náhodný proces se nazývá Markovův proces nebo náhodný proces bez následného efektu, pokud pravděpodobnostní charakteristiky procesu v budoucnu závisejí v jakýkoli okamžik pouze na jeho stavu v tento moment a nezávisí na tom, kdy a jak se systém do tohoto stavu dostal.

Při analýze provozních procesů QS je vhodné použít geometrické schéma - stavový graf. Obvykle jsou stavy systému znázorněny obdélníky a možné přechody ze stavu do stavu jsou znázorněny šipkami. Příklad stavového grafu je na Obr. jeden.

Proud událostí je sled stejnorodých událostí, které následují jedna po druhé v náhodných časech.

Proudění je charakterizováno intenzitou λ - četností výskytu událostí nebo průměrným počtem událostí vstupujících do QS za jednotku času.

Proud událostí se nazývá pravidelný, pokud události následují po sobě v pravidelných intervalech.

Proud událostí se nazývá stacionární, pokud jeho pravděpodobnostní charakteristiky nezávisí na čase. Zejména intenzita stacionárního proudění je konstantní hodnota: .

Proud událostí se nazývá běžný, pokud pravděpodobnost, že dvě nebo více událostí zasáhne malé časové období, je malá ve srovnání s pravděpodobností jedné události, tj. pokud se v něm události objeví jedna po druhé, a nikoli ve skupinách.

Proud událostí se nazývá proud bez následného účinku, pokud pro libovolné dva nepřekrývající se časové intervaly počet událostí připadajících na jeden z nich nezávisí na počtu událostí připadajících na ostatní.

Proud událostí se nazývá nejjednodušší (neboli stacionární Poisson), pokud je zároveň stacionární, obyčejný a nemá žádný následný účinek.

1.2 Kolmogorovovy rovnice

Všechny přechody v systému ze stavu do stavu probíhají za určitého toku událostí. Nechť je systém v nějakém stavu , ze kterého je možný přechod do stavu, pak můžeme předpokládat, že na systém působí nejjednodušší proudění s intenzitou , převádějící ho ze stavu do . Jakmile dojde k první události vlákna, dojde k jeho přechodu. Pro názornost je na stavovém grafu každá šipka odpovídající přechodu označena intenzitou . Takto označený stavový graf umožňuje sestavit matematický model procesu, tzn. najít pravděpodobnosti všech stavů jako funkci času. Pro ně se sestavují diferenciální rovnice, nazývané Kolmogorovovy rovnice.

Pravidlo pro sestavení Kolmogorovových rovnic: Na levé straně každé z rovnic je časová derivace pravděpodobnosti daného stavu. Na pravé straně je součet součinů všech stavů, ze kterých je možný přechod do daného stavu, intenzitou odpovídajících toků událostí mínus celková intenzita všech toků, které systém z tohoto stavu vyvedou, vynásobený podle pravděpodobnosti tohoto stavu.

Například pro stavový graf znázorněný na Obr. 1 mají Kolmogorovovy rovnice tvar:

Protože na pravé straně systému každý člen zadá 1krát se znaménkem a 1krát se znaménkem , poté sečtením všech rovnic dostaneme, že

,

,

Proto lze jednu z rovnic soustavy zahodit a nahradit ji rovnicí (1.2.1).

Pro získání konkrétního řešení je potřeba znát výchozí podmínky, tzn. pravděpodobnosti v počátečním okamžiku.

1.3 Konečné pravděpodobnosti a stavový graf QS

Pro dostatečně dlouhou dobu procesů v systému (at ) lze stanovit pravděpodobnosti stavů, které nezávisí na čase, které se nazývají konečné pravděpodobnosti, tzn. systém je ve stacionárním režimu. Pokud je počet stavů soustavy konečný a z každého z nich v konečném počtu kroků lze přejít do libovolného jiného stavu, pak existují konečné pravděpodobnosti, tzn.

Význam konečných pravděpodobností je ten, že se rovnají průměrnému relativnímu času strávenému systémem v daném stavu.

Protože ve stacionárním stavu jsou časové derivace rovny nule, potom rovnice pro konečné pravděpodobnosti získáme z Kolmogorovových rovnic přirovnáním jejich pravé strany k nule.

Stavové grafy používané v modelech systémů řazení se nazývají schéma smrti a plemene. Tento název je způsoben tím, že se toto schéma používá v biologických problémech souvisejících se studiem velikosti populace. Jeho zvláštnost spočívá v tom, že všechny stavy systému lze znázornit jako řetězec, ve kterém je každý ze stavů spojen s předchozím a následujícími (obr. 2).

Rýže. 2. Graf stavů v modelech QS

Předpokládejme, že všechny toky, které převádějí systém z jednoho stavu do druhého, jsou ty nejjednodušší. Podle grafu na Obr. 2 sestavíme rovnice pro konečné pravděpodobnosti soustavy. Vypadají jako:

Systém je získán z ( n +1) rovnice, která se řeší eliminační metodou. Tato metoda spočívá v tom, že postupně všechny pravděpodobnosti systému jsou vyjádřeny pomocí pravděpodobnosti.

,

.

Dosazením těchto výrazů do poslední rovnice soustavy najdeme , pak najdeme zbývající pravděpodobnosti stavů QS.

1.4 Ukazatele výkonnosti QS

Účelem modelování QS je vypočítat výkon systému prostřednictvím jeho charakteristik. Jako ukazatele výkonnosti QS se používají následující:

je absolutní kapacita systému ( A), tj. průměrný počet aplikací obsluhovaných za jednotku času;

je relativní propustnost ( Q), tj. průměrný podíl přijatých požadavků obsluhovaných systémem;

je pravděpodobnost selhání (), tzn. pravděpodobnost, že aplikace ponechá QS bez obsluhy;

- průměrné číslo obsazené kanály (k);

- průměrný počet aplikací v QS ();

– průměrná doba setrvání aplikace v systému ();

- průměrný počet žádostí ve frontě () - délka fronty;

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

- průměrná doba, po kterou aplikace zůstává ve frontě ();

- průměrná doba, po kterou aplikace zůstává v systému ()

– stupeň zatížení kanálu (), tzn. pravděpodobnost, že je kanál obsazený;

je průměrný počet aplikací obsluhovaných za jednotku času;

– průměrná doba čekání na servis;

– pravděpodobnost, že počet aplikací ve frontě překročí určitou hodnotu atd.

Je prokázáno, že pro jakoukoli povahu toku žádostí, pro jakékoli rozložení doby služby, pro jakoukoli disciplínu služby se průměrná doba zdržení aplikace v systému (frontě) rovná průměrnému počtu žádostí v systému. (fronta) děleno intenzitou toku aplikací, tzn

(1.4.1)

Vzorce (1.4.1) a (1.4.2) se nazývají malé vzorce. Vyplývají ze skutečnosti, že v omezujícím stacionárním režimu se průměrný počet škod přicházejících do systému rovná průměrnému počtu škod, které z něj odcházejí, tzn. oba proudy aplikací mají stejnou intenzitu.

Vzorce pro výpočet výkonnostních ukazatelů jsou uvedeny v tabulce. jeden.

Stůl 1.

Ukazatele	Jednokanálový QS s omezená fronta	Vícekanálové QS s omezená fronta
Finále pravděpodobnosti
Pravděpodobnost
Absolutní propustnost schopnost
Relativní propustnost schopnost
Průměrný počet aplikací na
Průměrný počet aplikací pod servis
Průměrný počet aplikací v systému

1.5 Základní pojmy simulace

Hlavním cílem simulačního modelování je reprodukovat chování studovaného systému na základě analýzy nejvýznamnějších vztahů jeho prvků.

Počítačová simulace by měla být považována za statický experiment.

Z teorie funkcí náhodných veličin je známo, že k modelování náhodné veličiny s libovolnou spojitou a monotónně rostoucí distribuční funkcí stačí umět modelovat náhodnou veličinu rovnoměrně rozloženou na intervalu . Poté , co jsme získali realizaci náhodné veličiny , můžeme najít odpovídající realizaci náhodné veličiny , protože jsou spojeny rovností

Předpokládejme, že v nějakém systému hromadné obsluhy je doba obsluhy jednoho zákazníka rozdělena podle exponenciálního zákona s parametrem , kde je intenzita toku služeb. Pak má funkce rozdělení času obsluhy tvar

Nechť je realizace náhodné veličiny , rovnoměrně rozložené na intervalu , a nechť jí odpovídá realizace náhodného servisního času jednoho požadavku. Poté podle (1.5.1)

1.6 Stavební simulační modely

První fází při vytváření jakéhokoli simulačního modelu je fáze popisu reálného systému z hlediska charakteristik hlavních událostí. Tyto události jsou zpravidla spojeny s přechody studovaného systému z jednoho možného stavu do druhého a jsou označeny jako body na časové ose. K dosažení hlavního cíle modelování postačí sledování systému v okamžicích realizace hlavních událostí.

Zvažte příklad jednokanálového systému řazení do fronty. Účelem simulačního modelování takového systému je určit odhady jeho hlavních charakteristik, jako je průměrný čas strávený aplikací ve frontě, průměrná délka fronty a podíl prostojů systému.

Charakteristiky samotného procesu řazení do fronty mohou změnit své hodnoty buď v okamžiku přijetí nového požadavku na službu, nebo na konci obsluhy dalšího požadavku. QS může okamžitě začít obsluhovat další požadavek (obslužný kanál je volný), ale není vyloučena nutnost čekat, až se požadavek má zařadit do fronty (QS s frontou, obslužný kanál je obsazený). Po dokončení obsluhy dalšího požadavku může QS okamžitě začít obsluhovat další požadavek, pokud existuje, ale může také zůstat nečinný, pokud žádný neexistuje. Potřebné informace lze získat pozorováním různých situací, které nastanou při realizaci hlavních akcí. Když tedy požadavek dorazí do QS s frontou s obsazeným kanálem služeb, délka fronty se zvýší o 1. Podobně se délka fronty sníží o 1, pokud je dokončena obsluha dalšího požadavku a sada požadavků ve frontě není prázdný.

Pro fungování jakéhokoli simulačního modelu je nutné zvolit jednotku času. V závislosti na povaze modelovaného systému může být takovou jednotkou mikrosekunda, hodina, rok atd.

Protože je počítačová simulace ve své podstatě výpočtovým experimentem, její pozorované výsledky v agregaci musí mít vlastnosti implementace náhodného vzorku. Pouze v tomto případě bude zajištěna správná statistická interpretace simulovaného systému.

V počítačovém simulačním modelování jsou hlavním zájmem pozorování získaná poté, co studovaný systém dosáhne stacionárního režimu provozu, protože v tomto případě se rozptyl vzorku prudce snižuje.

Doba potřebná k tomu, aby systém dosáhl stacionárního režimu provozu, je dán hodnotami jeho parametrů a výchozím stavem.

Protože hlavním cílem je získat pozorovací data s co nejmenší chybou, můžete k dosažení tohoto cíle:

1) prodloužit dobu trvání simulačního modelování procesu fungování studovaného systému. V tomto případě se zvyšuje nejen pravděpodobnost, že systém dosáhne stacionárního režimu provozu, ale také se zvyšuje počet použitých pseudonáhodných čísel, což také pozitivně ovlivňuje kvalitu získaných výsledků.

2) na pevně stanovenou dobu T provádět simulační modelování N výpočetní experimenty, nazývané také běhy modelů, s různými sadami pseudonáhodných čísel, z nichž každý poskytuje jedno pozorování. Všechny běhy začínají se stejným počátečním stavem simulovaného systému, ale používají různé sady pseudonáhodných čísel. Výhodou této metody je nezávislost získaných pozorování, ukazatelů účinnosti systému. Pokud číslo N je dostatečně velký, pak jsou hranice symetrického intervalu spolehlivosti pro parametr určeny následovně:

, , tj. , kde

opravený rozptyl, ,

N– počet spuštění programu, – spolehlivost, .

2. Analytické modelování QS

2.1 Stavový graf soustavy a Kolmogorovova rovnice

Uvažujme dvoukanálový systém řazení do fronty (n = 2) s omezenou frontou rovnou šesti (m = 4). QS přijímá nejjednodušší tok aplikací s průměrnou intenzitou λ = 4,8 a exponenciálním zákonem rozdělení času mezi příchody aplikací. Tok požadavků obsluhovaných v systému je nejjednodušší s průměrnou intenzitou μ = 2 a exponenciálním zákonem rozložení času obsluhy.

Tento systém má 7 stavů, které označujeme:

S 0 - systém je volný, nejsou žádné požadavky;

S 1 - 1 požadavek na službu, fronta je prázdná;

S 2 - 2 požadavky na službu, fronta je prázdná;

S 3 - 2 požadavky na službu, 1 požadavek ve frontě;

S 4 - 2 požadavky na obsluhu, 2 požadavky ve frontě;

S 5 - 2 požadavky na službu, 3 požadavky ve frontě;

S 6 - 2 požadavky na službu, 4 požadavky ve frontě;

Pravděpodobnosti vstupu systému do stavů S 0 , S 1 , S 2 , …, S 6 jsou rovna Р 0 , Р 1 , Р 2 , …, Р 6 .

Stavový graf systému řazení je schéma smrti a reprodukce. Všechny stavy systému lze znázornit jako řetězec, ve kterém je každý ze stavů spojen s předchozím a následujícím.

Rýže. 3. Graf stavů dvoukanálového QS

Pro sestrojený graf napíšeme Kolmogorovovy rovnice:

Pro vyřešení tohoto systému nastavíme počáteční podmínky:

Kolmogorovův systém rovnic (systém diferenciální rovnice) řešíme numerickou Eulerovou metodou pomocí softwarového balíku Maple 11 (viz Příloha 1).

Eulerova metoda

kde - v našem případě se jedná o správné části Kolmogorovových rovnic, n=6.

Zvolme časový krok. Předpokládejme kde T je doba, kterou systém potřebuje k dosažení ustáleného stavu. Odtud získáme počet kroků . Důsledně N po výpočtu podle vzorce (1) získáme závislosti pravděpodobností stavů soustavy na čase, znázorněné na Obr. 4.

Hodnoty pravděpodobností QS jsou rovny:

Rýže. 4. Závislosti pravděpodobností stavů soustavy na čase

P0

P5

P4

P3

P2

P1

2.2 Konečné pravděpodobnosti systému

Při dostatečně dlouhé době pro procesy v systému () lze stanovit pravděpodobnosti stavů, které nejsou závislé na čase, které se nazývají konečné pravděpodobnosti, tzn. systém je ve stacionárním režimu. Pokud je počet stavů soustavy konečný a z každého z nich lze v konečném počtu kroků přejít do libovolného jiného stavu, pak existují konečné pravděpodobnosti, tzn.

Protože ve stacionárním stavu jsou časové derivace rovny 0, pak rovnice pro konečné pravděpodobnosti získáme z Kolmogorovových rovnic přirovnáním pravých stran k 0. Zapišme rovnice pro konečné pravděpodobnosti pro naše QS.

Pojďme vyřešit tento systém lineární rovnice pomocí softwarového balíku Maple 11 (viz Příloha 1).

Dostaneme konečné pravděpodobnosti systému:

Porovnání pravděpodobností získaných ze systému Kolmogorovových rovnic pro , s konečnými pravděpodobnostmi ukazuje, že chyby jsou rovny:

Tito. dost malý. To potvrzuje správnost získaných výsledků.

2.3 Výpočet ukazatelů výkonu systému podle konečných pravděpodobností

Pojďme najít ukazatele výkonu systému řazení.

Nejprve vypočítáme sníženou intenzitu toku aplikací:

1) Pravděpodobnost odmítnutí obsluhy aplikace, tzn. pravděpodobnost, že zákazník opustí systém neobsluhován V našem případě je zákazníkovi odepřena služba, pokud jsou všechny 2 kanály obsazeny a fronta je maximálně zaplněna (tj. 4 lidé ve frontě), to odpovídá stavu systému S 6 . Protože pravděpodobnost vstupu systému do stavu S 6 je P 6 , pak

4) Průměrná délka fronty, tzn. průměrný počet požadavků ve frontě je roven součtu součinů počtu požadavků ve frontě a pravděpodobnosti odpovídajícího stavu.

5) Průměrný čas, který aplikace stráví ve frontě, je určen Littleovým vzorcem:

3. Simulační modelování QS

3.1 Algoritmus simulační metody QS (přístup krok za krokem)

Uvažujme dvoukanálový systém řazení do fronty (n = 2) s maximální délkou fronty šest (m = 4). QS přijímá nejjednodušší tok aplikací s průměrnou intenzitou λ = 4,8 a exponenciálním zákonem rozdělení času mezi příchody aplikací. Tok požadavků obsluhovaných v systému je nejjednodušší s průměrnou intenzitou μ = 2 a exponenciálním zákonem rozložení času obsluhy.

K simulaci QS použijeme jednu z metod statistického modelování - simulační modelování. Použijeme postup krok za krokem. Podstatou tohoto přístupu je, že stavy systému jsou uvažovány v následujících časových okamžicích, přičemž krok mezi nimi je dostatečně malý, aby během jeho doby nenastala více než jedna událost.

Zvolme časový krok (). Mělo by to být mnohem méně než průměrná doba přijetí žádosti () a průměrná doba jejího doručení (), tzn.

Kde (3.1.1)

Na základě podmínky (3.1.1) určíme časový krok .

Čas přijetí žádosti do QS a doba její obsluhy jsou náhodné veličiny. Proto se při simulaci QS počítají pomocí náhodných čísel.

Zvažte přijetí žádosti v CMO. Pravděpodobnost, že objednávka dorazí do QS během intervalu, je rovna: . Vygenerujme náhodné číslo a if , pak budeme uvažovat, že požadavek v tomto kroku vstoupil do systému, pokud , pak nevstoupil.

To se provádí v programu isRequested () . Vezmeme časový interval konstantní a rovný 0,0001, pak bude poměr roven 10000. Pokud je požadavek přijat, pak nabývá hodnotu "true", jinak je hodnota "false".

bool isRequested()

double r = R.NextDouble();

pokud (r< (timeStep * lambda))

Podívejme se nyní na službu aplikace v QS. Doba obsluhy aplikace v systému je určena výrazem , kde je náhodné číslo. V programu je pomocí funkce určen servisní čas GetServiceTime () .

double GetServiceTime()

double r = R.NextDouble();

return(-1/mu*Math. Log(1-r, Math.E));

Algoritmus simulační metody lze formulovat následovně. Provozní doba QS ( T) je rozdělena do časových kroků dt, každý z nich provádí řadu akcí. Nejprve se určí stavy systému (obsazené kanály, délka fronty) a poté pomocí funkce isRequested () , je určeno, zda byl požadavek v tomto kroku přijat či nikoliv.

Pokud jsou přijímány a zároveň jsou k dispozici volné kanály, použijte funkci GetServiceTime () vygenerujeme dobu zpracování aplikace a zprovozníme ji. Pokud jsou všechny kanály obsazené a délka fronty je menší než 4, zařadíme požadavek do fronty, pokud je délka fronty 4, bude požadavek zamítnut.

V případě, že v tomto kroku nebyl požadavek přijat a servisní kanál byl volný, zkontrolujeme, zda existuje fronta. Pokud existuje, pak z fronty vložíme požadavek na servis na bezplatný kanál. Po provedených operacích se doba obsluhy pro obsazené kanály zkrátí o hodnotu kroku dt .

Po uplynutí času T, tj. po namodelování provozu QS se vypočítají výkonnostní ukazatele systému a výsledky se zobrazí na obrazovce.

3.2 Vývojový diagram programu

Blokové schéma programu, který implementuje popsaný algoritmus, je znázorněno na Obr. 5.

Rýže. 5. Vývojový diagram programu

Pojďme si některé bloky napsat podrobněji.

Blok 1. Nastavení počátečních hodnot parametrů.

Náhodné R; // Generátor náhodných čísel

public uint maxQueueLength; // Maximální délka fronty

počet kanálů veřejné jednotky; // Počet kanálů v systému

veřejná dvojitá lambda; // Intenzita toku příchozích požadavků

veřejné dvojité mu; // Intenzita toku obsluhy požadavku

veřejný dvojitý časStep; // Časový krok

public double timeOfFinishProcessingReq; // Čas ukončení obsluhy požadavku ve všech kanálech

veřejný dvojitý timeInQueue; // Čas strávený QS ve státech s frontou

public double processingTime; // Doba běhu systému

public double totalProcessingTime; // Celková doba pro obsluhu požadavků

public uint requestEntryCount; // Počet přijatých požadavků

public uint zamítnutaPočet požadavků; // Počet zamítnutých žádostí

public uint acceptRequestCount; // Počet vyřízených požadavků

uint queueLength; // Délka fronty //

Typ popisující stavy QS

enum SysCondition(SO, S1, S2, S3, S4, S5, S6);

SysCondition currentSystemCondition; // Aktuální stav systému

Nastavení stavů systému. Vyberme 7 různých stavů pro tento 2kanálový systém: S 0 , S 1 . S 6. QS je ve stavu S 0, když je systém volný; S 1 – alespoň jeden kanál je volný; ve stavu S2, kdy jsou všechny kanály obsazeny a ve frontě je místo; ve stavu S 6 jsou všechny kanály obsazeny a fronta dosáhla maximální délky (queueLength = 4).

Pomocí funkce zjistíme aktuální stav systému GetCondition()

SysCondition GetCondition()

SysCondition p_currentCondit = SysCondition.S0;

int busyChannelCount = 0;

for (int i = 0; i< channelCount; i++)

if (timeOfFinishProcessingReq[i] > 0)

busyChannelCount++;

p_currentCondit += k * (i + 1);

if (busyChannelCount > 1)

(p_currentCondit++;)

return p_currentCondit + (int) QueueLength;

Změna doby zdržení QS ve státech s délkou fronty 1, 2, 3, 4. To je implementováno následujícím kódem:

if (queueLength > 0)

timeInQueue += timeStep;

if (queueLength > 1)

(timeInQueue += timeStep;)

Existuje taková operace, jako je umístění požadavku na službu na bezplatný kanál. Když je splněna podmínka timeOfFinishProcessingReq, prohledají se všechny kanály, počínaje prvním kanálem [ i ] <= 0 (kanál je zdarma), odešle se na něj přihláška, tzn. je vygenerován čas ukončení pro obsluhu požadavku.

for (int i = 0; i< channelCount; i++)

if (timeOfFinishProcessingReq[i]<= 0)

timeOfFinishProcessingReq[i] = GetServiceTime();

totalProcessingTime+= timeOfFinishProcessingReq[i];

Obsluha aplikací v kanálech je modelována kódem:

for (int i = 0; i< channelCount; i++)

if (timeOfFinishProcessingReq[i] > 0)

timeOfFinishProcessingReq[i] -= timeStep;

Algoritmus simulační metody je implementován v programovacím jazyce C#.

3.3 Výpočet QS ukazatele výkonnosti založené na výsledky její simulace

Nejdůležitější ukazatele jsou:

1) Pravděpodobnost odmítnutí obsloužit aplikaci, tzn. pravděpodobnost, že zákazník opustí systém neobsluhován. V našem případě je zákazníkovi odepřena služba, pokud jsou všechny 2 kanály obsazeny a fronta je maximálně zaplněná (tj. 4 lidé ve frontě). Pro zjištění pravděpodobnosti selhání vydělíme dobu, po kterou QS zůstane ve stavu s frontou 4, celkovým časem systému.

2) Relativní propustnost je průměrný podíl příchozích požadavků obsluhovaných systémem.

3) Absolutní propustnost je průměrný počet aplikací obsluhovaných za jednotku času.

4) Délka fronty, tzn. průměrný počet aplikací ve frontě. Délka fronty se rovná součtu součinů počtu lidí ve frontě a pravděpodobnosti odpovídajícího stavu. Pravděpodobnosti stavů zjistíme jako poměr doby QS v tomto stavu k celkové době provozu systému.

5) Průměrnou dobu, kterou aplikace stráví ve frontě, určuje Littleův vzorec

6) Průměrný počet obsazených kanálů je definován takto:

7) Procento aplikací, kterým byla služba odepřena, se zjistí podle vzorce

8) Procento obsluhovaných požadavků se zjistí podle vzorce

3.4 Statistické zpracování výsledků a jejich porovnání s výsledky analytického modelování

Protože výkonnostní ukazatele se získávají jako výsledek modelování QS na omezenou dobu, obsahují náhodnou složku. Pro získání spolehlivějších výsledků je proto nutné provést jejich statistické zpracování. Za tímto účelem pro ně odhadujeme interval spolehlivosti na základě výsledků 20 běhů programu.

Hodnota spadá do intervalu spolehlivosti, pokud je nerovnost

, kde

matematické očekávání (průměrná hodnota), se zjistí pomocí vzorce

opravený rozptyl,

,

N =20 - počet jízd

- spolehlivost. V a N =20 .

Výsledek programu je na obr. 6.

Rýže. 6. Typ programu

Pro usnadnění porovnání výsledků získaných různými metodami modelování je uvádíme ve formě tabulky.

Tabulka 2

Ukazatele Účinnost QS	Výsledek analytická modelování	Výsledek simulační modelování (poslední krok)	Výsledky simulace
			Sečteno a podtrženo svěřenec interval	Horní hranice svěřenec interval
Pravděpodobnost selhání		0,174698253017626	0,158495148639101	0,246483801571923
Relativní šířka pásma		0,825301746982374	0,753516198428077	0,841504851360899
Absolutní šířka pásma		3,96144838551539	3,61687775245477	4,03922328653232
Průměrná délka fronty		1,68655313447018	1,62655862750852	2,10148609204869
Průměrný čas, který aplikace stráví ve frontě	0,4242558575	0,351365236347954	0,338866380730942	0,437809602510145
Průměrně obsazené kanály		1,9807241927577	1,80843887622738	2,01961164326616

Od stolu. Obrázek 2 ukazuje, že výsledky získané při analytickém modelování QS spadají do intervalu spolehlivosti získaného z výsledků simulace. To znamená, že výsledky získané různými metodami jsou konzistentní.

Závěr

V tomto článku jsou zvažovány hlavní metody pro modelování QS a výpočet jejich výkonnostních ukazatelů.

Pomocí Kolmogorovových rovnic byla provedena simulace dvoukanálového QS s maximální délkou fronty 4 a byly zjištěny konečné pravděpodobnosti stavů systému. Vypočítají se ukazatele jeho účinnosti.

Byla provedena simulace provozu takového QS. V programovacím jazyce C# byl sestaven program, který simuluje jeho činnost. Byla provedena řada výpočtů, na jejichž základě byly zjištěny hodnoty ukazatelů účinnosti systému a bylo provedeno jejich statistické zpracování.

Výsledky získané během simulačního modelování jsou v souladu s výsledky analytického modelování.

Literatura

1. Wentzel E.S. Operační výzkum. – M.: Drop, 2004. – 208 s.

2. Volkov I.K., Zagoruiko E.A. Operační výzkum. - M .: Vydavatelství MSTU im. N.E. Bauman, 2002. - 435 s.

3. Volkov I.K., Zuev S.M., Tsvetkova G.M. náhodné procesy. - M .: Vydavatelství MSTU im. N.E. Bauman, 2000. - 447 s.

4. Gmurman V.E. Průvodce řešením problémů v teorii pravděpodobnosti a matematické statistice. - M.: Vyšší škola, 1979. - 400 s.

5. Ivnitsky V.L. Teorie frontových sítí. – M.: Fizmatlit, 2004. – 772 s.

6. Výzkumné operace v ekonomice / ed. N.Sh. Kremer. - M.: Jednota, 2004. - 407 s.

7. Takha H.A. Úvod do operačního výzkumu. - M.: Nakladatelství "Williams", 2005. - 902 s.

8. Kharin Yu.S., Malyugin V.I., Kirlitsa V.P. aj. Základy simulace a statistického modelování. - Minsk: Design PRO, 1997. - 288 s.

V průběhu posledních desetiletí se v různých oblastech národního hospodářství stalo nutností řešit pravděpodobnostní problémy související s provozem systémů hromadné obsluhy. Příklady takových systémů jsou telefonní ústředny, opravny, maloobchodní prodejny, pokladny a tak dále. práce jakéhokoli systému front spočívá v obsluze příchozího toku požadavků (hovory od předplatitelů, tok zákazníků do prodejny, požadavky na práci v dílně atd.).
Matematická disciplína, která studuje modely skutečných systémů hromadné obsluhy, se nazývá teorie front. Úkolem teorie hromadné obsluhy je stanovit závislost výsledných ukazatelů výkonnosti systému hromadné obsluhy (pravděpodobnost, že požadavek bude obsloužen; matematické očekávání počtu obsloužených požadavků atd.) na vstupních ukazatelích (počet zařízení v systému, parametry příchozího toku požadavků atd.) .) je možné tyto závislosti ve formě vzorce stanovit pouze pro jednoduché systémy hromadné obsluhy. Studium reálných systémů se provádí imitací, případně modelováním jejich práce na počítači metodou statistických testů.
Systém řazení do fronty je považován za daný, pokud jsou definovány následující:
1) příchozí tok požadavků, nebo jinými slovy distribuční zákon, který charakterizuje časové okamžiky, kdy požadavky vstupují do systému. Základní příčina požadavků se nazývá zdroj. V následujícím souhlasíme s předpokladem, že zdroj má neomezený počet požadavků a že požadavky jsou homogenní, to znamená, že se liší pouze v okamžicích svého výskytu v systému;
2) servisní systém sestávající z pohonu a servisního uzlu. Posledně jmenované je jedno nebo více servisních zařízení, která budou označována jako zařízení. Každý požadavek musí jít do jednoho z přístrojů, aby mohl být servisován. Může se ukázat, že požadavky budou muset počkat, až budou zařízení volná. V tomto případě jsou požadavky v obchodě a tvoří jednu nebo více front. Předpokládejme, že k přechodu požadavku z úložiště do obslužného uzlu dojde okamžitě;
3) doba obsluhy požadavku každým zařízením, která je náhodnou veličinou a vyznačuje se určitým distribučním zákonem;
4) vyčkávací disciplína, tedy soubor pravidel upravujících počet požadavků, které jsou současně v systému. Systém, ve kterém je příchozí požadavek odmítnut, když jsou všechna zařízení zaneprázdněna, se nazývá systém bez čekání. Pokud požadavek, který udržoval všechna zařízení zaneprázdněná, vstoupí do fronty a čeká, dokud
dokud se jedno ze zařízení neuvolní, pak se takový systém nazývá čistý čekací systém. Systém, ve kterém zákazník, který zaměstnával všechny servery, vstupuje do fronty pouze v případě, že počet zákazníků v systému nepřekročí určitou úroveň (jinak je zákazník ztracen), se nazývá smíšený systém front;
5) služební kázeň, tedy soubor pravidel, podle kterých se požadavek vybírá z fronty na obsluhu. V praxi se nejčastěji používají následující pravidla:
- žádosti jsou přijímány k doručení v pořadí podle priority;
- Žádosti jsou přijímány k doručení podle minimální doby pro přijetí odmítnutí;
- žádosti jsou přijímány do služby v náhodném pořadí podle daných pravděpodobností;
6) frontová kázeň, tzn. sada pravidel, podle kterých požadavek upřednostňuje jednu nebo druhou frontu (pokud jich je více) a nachází se ve vybrané frontě. Například příchozí reklamace může být umístěna v nejkratší frontě; v této frontě může být umístěn jako poslední (taková fronta se nazývá objednaná), nebo může přejít do služby mimo pořadí. Jiné možnosti jsou také možné.

Simulační modelování systémů hromadné obsluhy

Modelka - je to jakýkoli obraz, analog, mentální nebo ustálený, obraz, popis, schéma, kresba atd. jakéhokoli předmětu, procesu nebo jevu, který v procesu poznávání (studia) nahrazuje původní, zachovává si některé typické vlastnosti důležité pro toto studium .
Modelování je studium jakéhokoli objektu nebo systému objektů budováním a studiem jejich modelů. A také – jde o využití modelů k určení nebo zpřesnění charakteristik a racionalizaci způsobů konstrukce nově konstruovaných objektů.
Model je nástrojem pro studium složitých systémů.
Obecně komplexní systém je prezentován jako víceúrovňová konstrukce vzájemně se ovlivňujících prvků spojených do subsystémů různých úrovní. Mezi komplexní systémy patří informační systémy. Návrh takových složitých systémů se provádí ve dvou fázích.

1 Vnější provedení

V této fázi se provádí výběr struktury systému, jeho hlavních prvků, organizace interakce mezi prvky, zohlednění vlivu vnějšího prostředí a vyhodnocení ukazatelů výkonnosti systému.

2 Vnitřní provedení - provedení jednotlivých prvků
systémy

Typickou metodou pro studium složitých systémů v první fázi je jejich simulace na počítači.
Výsledkem modelování jsou závislosti, které charakterizují vliv struktury a parametrů systému na jeho účinnost, spolehlivost a další vlastnosti. Tyto závislosti slouží k získání optimální struktury a parametrů systému.
Nazývá se model formulovaný v jazyce matematiky pomocí matematických metod matematický model.
Simulační modelování se vyznačuje reprodukcí jevů popsaných matematickým modelem, se zachováním jejich logické struktury, posloupnosti střídání v čase. Jakékoli vhodné informace kolující v modelu mohou být použity k odhadu požadovaných hodnot, pokud jsou dostupné pro registraci a následné zpracování.
Požadované hodnoty při studiu procesů pomocí simulace jsou obvykle určeny jako průměrné hodnoty z dat velkého počtu implementací procesů. Pokud je počet realizací N použitých k odhadu hledaných hodnot dostatečně velký, pak díky zákonu velkých čísel získávají získané odhady statistickou stabilitu a lze je brát jako přibližné hodnoty hledaných hodnot s dostatečná přesnost pro praxi.
Podstata metody simulačního modelování aplikované na úlohy řazení do fronty je následující. Algoritmy jsou sestaveny
s jejichž pomocí lze vyvíjet náhodné realizace daných toků homogenních událostí a také modelovat procesy fungování obslužných systémů. Tyto algoritmy se používají k opakované reprodukci implementace procesu náhodné služby za pevných podmínek problému. Výsledné informace o stavu procesu jsou podrobeny statistickému zpracování pro vyhodnocení hodnot, které jsou ukazateli kvality služby.

3 Tvorba implementací náhodného toku požadavků

Při studiu složitých systémů metodou simulace je věnována značná pozornost zohlednění náhodných faktorů.
Náhodné události, náhodné veličiny a náhodné procesy (funkce) se používají jako matematická schémata sloužící k formalizaci působení těchto faktorů. Tvorba realizací náhodných objektů jakékoli povahy na počítači je redukována na generování a transformaci náhodných čísel. Zvažte metodu pro získání možných hodnot náhodných veličin s daným distribučním zákonem. Pro vytvoření možných hodnot náhodných veličin s daným distribučním zákonem jsou výchozím materiálem náhodné veličiny, které mají rovnoměrné rozdělení v intervalu (0, 1). Jinými slovy, možné hodnoty xi náhodné veličiny t, která má rovnoměrné rozdělení v intervalu (0, 1), lze transformovat na možné hodnoty yi náhodné veličiny r), jejíž distribuční zákon je daný. Metoda transformace spočívá v tom, že náhodná čísla jsou vybrána z rovnoměrně rozdělené populace, která splňují určitou podmínku takovým způsobem, že vybraná čísla splňují daný distribuční zákon.
Předpokládejme, že je nutné získat posloupnost náhodných čísel yi s funkcí hustoty 1^(y). Není-li definiční obor funkce f^y) omezen na jednu nebo obě strany, je nutné přejít na odpovídající zkrácené rozdělení. Nechť rozsah možných hodnot pro zkrácené rozdělení je (a, b).
Z náhodné veličiny r) odpovídající funkci hustoty f → y) přejdeme k f.
Náhodná hodnota b, bude mít rozsah možných hodnot (0, 1) a funkci hustoty f ^ (z) danou výrazem.
Nechť je maximální hodnota f^(z) rovna f m . Stanovme rovnoměrná rozdělení v intervalech (0, 1) náhodných čísel x 2 i-1 a x 2 i. Postup pro získání posloupnosti yi náhodných čísel s funkcí hustoty ^(y) se redukuje na následující:
1) dvojice náhodných čísel x2i-1 jsou vybrány z počáteční populace,
2) u těchto čísel se kontroluje platnost nerovnosti
x 21<-- ^[а + (Ъ-а)х 2М ] (3)
m
3) pokud je splněna nerovnost (3), pak se ze vztahu určí další číslo yi
yi \u003d a + (b-a) x 21 (4)
Při modelování servisních procesů se stává nutností tvořit realizace náhodného toku homogenních událostí (aplikací). Každá toková událost je charakterizována časem tj, ve kterém nastane. K popisu náhodného toku homogenních událostí jako náhodného procesu postačí specifikovat distribuční zákon, který charakterizuje posloupnost náhodných proměnných tj. Abychom získali realizaci proudu homogenních událostí t1, t2..., tk, je nutné vytvořit realizaci zbz 2 ,...,zk k-rozměrného náhodného vektoru £2,... , Sk a vypočítejte hodnoty ti v souladu s následujícími poměry:
t2 =
Nechť stacionární obyčejné proudění s omezeným následným účinkem je dáno funkcí hustoty f(z). Podle Palmova vzorce (6) najdeme funkci hustoty f1(z1) pro první interval z1.
1-Jf(u)du
Nyní můžeme vygenerovat náhodné číslo z b, jak je ukázáno výše, odpovídající funkci hustoty f1(z1), a získat okamžik objevení se prvního požadavku t1 = z1. Dále utvoříme řadu náhodných čísel odpovídajících funkci hustoty f(z) a pomocí vztahu (4) vypočteme hodnoty veličin t2, t3 ,.., tk.
4 Zpracování výsledků simulace
Při implementaci modelovacích algoritmů na počítači jsou generovány informace o stavech studovaného systému. Tyto informace jsou výchozím materiálem pro stanovení přibližných hodnot hledaných veličin, nebo, jak se říká, odhadů hledaných veličin.
Odhad pravděpodobnosti události A se vypočítá podle vzorce
p(A) = mN. (7)
Odhad střední hodnoty x náhodné veličiny b, počítáno podle
vzorec
_ 1n
k=1
Odhad S 2 pro rozptyl náhodné veličiny ^ se vypočítá podle vzorce
1 N 1 ( N L 2
S2=1 ano xk 2-5> J (9)
Odhad korelačního momentu K^ pro náhodné veličiny b, a C s možnými hodnotami x k a y k se vypočítá podle vzorce
1 N 1 N
Y> [ Páni

5 Příklad modelování QS
Zvažte následující systém:
1 Požadavky přicházejí v náhodných časech, zatímco
časový interval Q mezi libovolnými dvěma po sobě jdoucími požadavky má exponenciální zákon s parametrem já, tj. distribuční funkce má tvar
>0. (11) Systém řazení do front se skládá z identických, očíslovaných serverů.
3 Čas T o bsl - náhodná veličina se zákonem o rovnoměrném rozdělení na segmentu.
4 Systém bez čekání, tzn. požadavek, aby byla všechna zařízení zaneprázdněna, opustí systém.
5 Obslužná kázeň je následující: je-li v okamžiku přijetí k -tého požadavku první server volný, začne požadavek obsluhovat; pokud je tento server zaneprázdněn a druhý je volný, pak je požadavek obsluhován druhým serverem a tak dále.
Je požadováno odhadnout matematická očekávání počtu požadavků obsluhovaných systémem v čase T a zamítnutých.
Pro počáteční okamžik výpočtu zvolíme okamžik příchodu prvního požadavku Т1=0. Zaveďme následující zápis: Tk je okamžik přijetí k-tého požadavku; ti - čas ukončení služby požadavku i-té zařízení, i=1, 2, 3, ...,s.
Předpokládejme, že v čase T 1 jsou všechna zařízení volná.
První poptávka přichází na server 1. Obslužný čas tohoto serveru má rovnoměrné rozložení v segmentu. Proto konkrétní hodnotu t obl této doby zjistíme vzorcem
(12)
kde r je hodnota náhodné veličiny R rovnoměrně rozložené na segmentu . Zařízení 1 bude během doby t o bsl obsazeno. Časový bod t 1 ukončení obsluhy požadavku zařízením 1 by proto měl být považován za rovný: t 1 = T1+ t o obsl.
Poté přidejte jeden do počítadla vyřízených požadavků a přejděte k dalšímu požadavku.
Předpokládejme, že k požadavkům již bylo zváženo. Definujme okamžik Т k+1 přijetí (k+1)-tého požadavku. K tomu zjistíme hodnotu t časového intervalu mezi po sobě jdoucími požadavky. Protože tento interval má exponenciální zákon, pak
12
x \u003d - V r (13)
| Ll
kde r je další hodnota náhodné veličiny R . Potom okamžik příchodu (k + 1) požadavku: T k +1 = Tk + T.
Je v tuto chvíli první zařízení zdarma? Pro zodpovězení této otázky je nutné zkontrolovat stav ti< Tk + i - Если это условие выполнено, то к моменту Т k +1 первый прибор освободился и может обслуживать требование. В этом случае t 1 заменяем на (Т k +1 + t обсл), добавляем единицу в счетчик об служенных требований и переходим к следующему требованию. Если t 1>Tk +1, pak je první zařízení v čase Tk +1 obsazeno. V tomto případě zkontrolujeme, zda je druhé zařízení volné. Pokud podmínka i 2< Tk + i выполнено, заменяем t2 на (Т k +1+ t о бсл), добавляем единицу в счетчик обслуженных требований и переходим к следующему требованию. Если t 2>Т k +1, pak zkontrolujeme podmínku 1з<Тк+1 и т. д. Eсли при всех i от 1 до s имеет ti >T k +1, pak jsou v tuto chvíli T k +1 všechna zařízení obsazena. V tomto případě přidáme jedničku do počítadla poruch a přejdeme k dalšímu požadavku. Pokaždé, po výpočtu T k + 1, musíme také zkontrolovat podmínku ukončení realizace: Tk + i< T . Если это условие выполнено, то одна реализация процесса функционирования системы воспроизведена и испыта ние заканчивается. В счетчике обслуженных требований и в счетчике отказов находятся числа n обсл и n отк.
Po zopakování takového testu nkrát (s použitím různých r) a zprůměrování výsledků experimentů určíme odhady matematických očekávání počtu obsluhovaných zákazníků a počtu zákazníků, kteří byli odmítnuti:
(14)
(Ji
nj=1
kde (n obl) j a (n obl) j jsou hodnoty n obl a n obl v j-tém experimentu.
13

Seznam použitých zdrojů
1 Emeljanov A.A. Simulační modelování ekonomických procesů [Text]: Proc. příspěvek na vysoké školy / A.A. Emelyanov, E.A. Vlasová, R.V. Myslel. - M. : Finance a statistika, 2002. - 368s.
2 Buslenko, N.P. Modelování komplexních systémů [Text] / N.P. Buslenko.- M.: Nauka, 1978. - 399s.
3 Sověti B.Ya. Modelovací systémy [Text]: Proc. pro univerzity / B.Ya. Sove tov, S.A. Jakovlev. -M. : Nejvyšší. škola, 1985. - 271 s.
4 Sověti B.Ya. Modelovací systémy [Text]: Laboratorní dílna: Proc. příspěvek pro vysoké školy v oboru: "Automatizovaný systém pro zpracování informací a řízení." / B.Ya. Sovetov, S.A. Jakovlev. -M. : Nejvyšší. škola, 1989. - 80 s.
5 Maximei I.V. Simulační modelování na počítači [Text] / Maksimey, I.V. -M: ROZHLAS A KOMUNIKACE, 1988. - 231s.
6 Wentzel E.S. Teorie pravděpodobnosti [Text]: učebnice. pro univerzity / E.S. Branka ventilace - M. : Vyšší. škola, 2001. - 575 s.
7 Gmurman, V.E. Teorie pravděpodobnosti a matematická statistika [Text]: učebnice. příspěvek / V.E. Gmurman. - M.: Vyšší. škola, 2001. - 479 s.
Příloha A
(povinné)
Přibližná témata sídlištních a grafických prací
1 Na pohotovosti pracuje jeden lékař. Délka léčby pacienta
a časové intervaly mezi přijetím pacientů jsou náhodné veličiny rozdělené podle Poissonova zákona. Podle závažnosti poranění jsou pacienti rozděleni do tří kategorií, přijetí pacienta libovolné kategorie je náhodná událost s ekvipravděpodobným rozdělením. Lékař se nejprve věnuje pacientům s nejtěžším poraněním (v pořadí, v jakém jsou přijímáni), poté, nejsou-li žádní, pacientům střední závažnosti a teprve poté pacientům s lehkým poraněním. Simulujte proces a odhadněte průměrné čekací doby ve frontě pacientů každé kategorie.
2 V městském vozovém parku jsou dvě opravárenské zóny. První slouží k opravám krátkého a středního trvání, druhý - střední a dlouhý. Jako poruchy jsou vozidla dodána do vozového parku; časový interval mezi dodávkami je náhodná Poissonova proměnná. Délka opravy je náhodná veličina s normálním rozdělením. Modelujte popsaný systém. Odhadněte průměrné čekací doby v přepravní frontě, vyžadující krátkodobé, střednědobé a dlouhodobé opravy, resp.
3 Minimarket s jedním kontrolorem - pokladní obsluhuje zákazníky, jejichž příchozí tok se řídí Poissonovým zákonem s parametrem 20 zákazníků/hod. Proveďte simulaci popsaného procesu a určete pravděpodobnost prostoje kontrolora - pokladní, průměrnou délku fronty, průměrný počet zákazníků na minimarketu, průměrnou dobu čekání na obsluhu, průměrnou dobu strávenou zákazníků na minimarketu a hodnotit jeho práci.
4 ATS přijímá žádosti o meziměstské hovory. Tok požadavků je Poissonův. Průměrně je za hodinu přijato 13 žádostí. Zjistěte průměrný počet žádostí přijatých za den, průměrnou dobu mezi zobrazením žádostí. Na telefonní ústředně se poruchy objevují, pokud je během půl hodiny přijato více než 50 požadavků. Najděte pravděpodobnost selhání stanice.
5 Na stanici Údržba přijde to nejjednodušší
tok aplikací s intenzitou 1 auto za 2 hod. Ve frontě na dvoře nesmí stát více než 3 auta. Průměrná doba opravy - 2 hodiny. Vyhodnoťte práci CMO a vypracujte doporučení pro zlepšení služeb.
6 Jeden tkadlec obsluhuje skupinu tkalcovských stavů a ​​podle potřeby provádí krátkodobý zásah, jehož trvání je náhodná veličina. Simulujte popsanou situaci. Jaká je pravděpodobnost odstávky dvou strojů najednou. Jak dlouhá je průměrná doba odstávky na stroj.
7 Na meziměstské telefonní ústředně obsluhují dva telefonní operátoři společnou frontu objednávek. Další objednávku obsluhuje telefonní operátor, který byl uvolněn jako první. Pokud jsou oba v době přijetí objednávky zaneprázdněni, hovor bude zrušen. Simulujte proces za předpokladu, že vstupní proudy jsou Poissonovy.
8 Na pohotovosti pracují dva lékaři. Délka léčby bolí
a časové intervaly mezi přijetím pacientů jsou náhodné veličiny rozdělené podle Poissonova zákona. Podle závažnosti poranění jsou pacienti rozděleni do tří kategorií, přijetí pacienta libovolné kategorie je náhodná událost s ekvipravděpodobným rozdělením. Lékař se nejprve věnuje pacientům s nejtěžším poraněním (v pořadí, v jakém jsou přijímáni), poté, nejsou-li žádní, pacientům střední závažnosti a teprve poté pacientům s lehkým poraněním. Simulujte proces a odhadněte průměrné čekací doby ve frontě pacientů každé kategorie.
9 Na meziměstské telefonní ústředně obsluhují dva telefonní operátoři
vytvořit společnou frontu objednávek. Další objednávku vyřídí tento telefonní operátor,
který byl vydán jako první. Pokud jsou oba v době přijetí objednávky obsazené, tak se tvoří fronta. Simulujte proces za předpokladu, že vstupní proudy jsou Poissonovy.
10 V systému přenosu dat se datové pakety vyměňují mezi uzly A a B přes duplexní komunikační kanál. Pakety přicházejí do systémových bodů od účastníků s časovými intervaly mezi nimi 10 ± 3 ms. Přenos paketu trvá 10 ms. Body mají vyrovnávací registry, které mohou ukládat dva pakety, včetně jednoho přenášeného. Pokud paket dorazí v okamžiku obsazenosti registrů, je bodům systému poskytnut přístup k satelitní poloduplexní komunikační lince, která přenáší datové pakety za 10 ± 5 ms. Když je satelitní linka obsazená, paket je odmítnut. Simulujte výměnu informací v systému přenosu dat po dobu 1 min. Určete frekvenci volání na satelitní linku a její zatížení. Pokud jsou možné poruchy, určete objem vyrovnávací paměti nezbytných k tomu, aby systém fungoval bez poruch.
11 U telefonní ústředny s jedním vchodem budiž použit standardní systém: pokud je účastník obsazený, tak se fronta netvoří a je nutné volat znovu. Simulujte situaci: tři předplatitelé se pokoušejí oslovit stejného vlastníka čísla a v případě úspěchu s ním nějakou dobu (náhodně dlouhou dobu) mluvit. Jaká je pravděpodobnost, že někdo, kdo se snaží dostat přes telefon, to za určitou dobu T nezvládne.
12 Obchodní společnost plánuje vyřizovat objednávky na nákup zboží telefonicky, k čemuž je nutné nainstalovat příslušnou miniautomatickou telefonní ústřednu s několika telefonními přístroji. Pokud objednávka dorazí v době, kdy jsou všechny linky obsazeny, klient obdrží odmítnutí. Pokud je v době přijetí požadavku alespoň jeden řádek volný, dojde k přepnutí na tento řádek a zadání objednávky. Intenzita příchozího toku aplikací je 30 objednávek za hodinu. Délka aplikace je v průměru 5 minut. Určit optimální počet servisních kanálů pro zajištění stavu stacionárního provozu QS.
13 V samoobsluze je 6 kontrolorů - pokladních. Příchozí proud kupujících se řídí Poissonovým zákonem s intenzitou 120 osob za hodinu. Jedna pokladní může obsloužit 40 osob za hodinu. Určete pravděpodobnost nečinnosti pokladního, průměrný počet zákazníků ve frontě, průměrnou dobu čekání, průměrný počet vytížených pokladních. Uveďte hodnocení práce QS.
14 Poissonův tok 200 zákazníků za hodinu vstupuje do samoobslužného obchodu. Přes den je obsluhují 3 pokladní kontroloři s intenzitou 90 zákazníků za hodinu. Intenzita vstupního toku kupujících ve špičce stoupá na hodnotu 400 kupujících za hodinu a v době recese dosahuje 100 kupujících za hodinu. Určete pravděpodobnost vytvoření fronty v obchodě a průměrnou délku fronty během dne a také požadovaný počet pokladních kontrolorů v době špičky a recese, za předpokladu stejné délky fronty a pravděpodobnosti jejího vytvoření jako v nominálním režimu.
15 Průměrný počet zákazníků přicházejících do vypořádacího uzlu v samoobsluze je 100 osob za hodinu. Pokladní může obsloužit 60 osob za hodinu. Simulujte proces a určete, kolik pokladníků je potřeba, aby pravděpodobnost fronty nepřesáhla 0,6.
16 Simulujte frontu v obchodě s jedním prodejcem s ekvipravděpodobnými zákony distribuce náhodných proměnných: příchod zákazníků a trvání služby (s určitou pevnou sadou parametrů). Získejte stabilní charakteristiky: průměrné hodnoty čekání kupujícího ve frontě a doba nečinnosti prodávajícího v očekávání příchodu kupujících. Posuďte jejich důvěryhodnost.
17 Simulujte frontu v obchodě s jedním prodejcem s Poissonovými zákony distribuce náhodných proměnných: příchod zákazníků a trvání služby (s určitou pevnou sadou parametrů). Získejte stabilní charakteristiky: průměrné hodnoty čekání kupujícího ve frontě a doba nečinnosti prodávajícího v očekávání příchodu kupujících. Posuďte jejich důvěryhodnost.
18 Vytvořte model čerpací stanice. Najděte ukazatele kvality požadavků na služby. Určete počet stojanů tak, aby se fronta nezvyšovala.
19 Průměrný počet zákazníků přicházejících k pokladnímu uzlu v samoobsluze, 60 osob za hodinu. Pokladní může obsloužit 35 osob za hodinu. Simulujte proces a určete, kolik pokladníků je potřeba, aby pravděpodobnost fronty nepřesáhla 0,6.
20 Modelujte autobusovou trasu s n zastávkami. Stanovte výkonnostní ukazatele pro použití QS.

Výkres 0 - 2 Streamy událostí (a) a nejjednodušší stream (b)

10.5.2.1. stacionárnost

Proudění se nazývá stacionární , pokud pravděpodobnost zasažení jednoho nebo druhého počtu událostí v elementárním časovém období délka τ (

Obrázek 0-2 , A) závisí pouze na délce úseku a nezávisí na tom, kde přesně na ose t tato oblast se nachází.

Stacionaritou toku se rozumí jeho rovnoměrnost v čase; pravděpodobnostní charakteristiky takového toku se s časem nemění. Zejména takzvaná intenzita (nebo "hustota") toku událostí, průměrný počet událostí za jednotku času pro stacionární tok, musí zůstat konstantní. To samozřejmě neznamená, že skutečný počet událostí objevujících se za jednotku času je konstantní, tok může mít lokální koncentrace a vzácnosti. Je důležité, aby u stacionárního toku nebyly tyto koncentrace a řídkost pravidelného charakteru a průměrný počet událostí spadajících do jednoho časového intervalu zůstal konstantní po celé uvažované období.

V praxi často dochází k tokům událostí, které (alespoň po omezenou dobu) lze považovat za stacionární. Například tok hovorů přicházejících na telefonní ústřednu řekněme v intervalu 12 až 13 hodin lze považovat za stacionární. Stejný tok už nebude stát celý den (v noci je intenzita toku hovorů mnohem menší než ve dne). Všimněte si, že totéž je případ většiny fyzikálních procesů, které nazýváme „stacionární“, ve skutečnosti jsou stacionární pouze po omezenou dobu a prodloužení této doby do nekonečna je jen pohodlný trik používaný pro účely zjednodušení. .

10.5.2.2. Žádný následný efekt

Tok událostí se nazývá tok bez následného účinku , jestliže u jakýchkoli nepřekrývajících se časových intervalů počet událostí připadajících na jeden z nich nezávisí na počtu událostí připadajících na druhý (nebo jiné, pokud jsou uvažovány více než dva úseky).

V takových tocích se události, které tvoří tok, objevují v postupných bodech času nezávisle na sobě. Například tok cestujících vstupující do stanice metra lze považovat za tok bez následků, protože důvody, které způsobily příchod jednotlivého cestujícího v tomto konkrétním okamžiku, a nikoli v jiném, zpravidla nesouvisí s podobnými důvody. pro ostatní cestující. Objeví-li se taková závislost, je porušena podmínka nepřítomnosti následného účinku.

Vezměme si například tok nákladních vlaků jedoucích po železniční trati. Pokud se z bezpečnostních důvodů nemohou následovat za sebou častěji než v časových intervalech t0 , pak existuje závislost mezi událostmi ve streamu a je porušena podmínka bez následků. Pokud však interval t0 je malý ve srovnání s průměrným intervalem mezi vlaky, pak je takové porušení bezvýznamné.

Výkres 0 - 3 Poissonovo rozdělení

Uvažujte na ose t nejjednodušší tok dějů s intenzitou λ. (Obrázek 0-2 b) . Nás bude zajímat náhodný časový interval T mezi sousedními událostmi v tomto proudu; najít jeho distribuční zákon. Nejprve najdeme distribuční funkci:

F(t) = P(T ( 0-2)

tj. pravděpodobnost, že hodnota T bude mít hodnotu menší nežt. Oddělte od začátku intervalu T (body t0) segment t a najděte pravděpodobnost, že interval T bude méně t . K tomu je nutné, aby pro úsek délky t , sousedící s bodem t0 , alespoň jeden zásah do události vlákna. Pojďme si spočítat pravděpodobnost tohoto F(t) prostřednictvím pravděpodobnosti opačné události (na segment t nedojde k žádné události streamu):

F (t) \u003d 1 - P 0

Pravděpodobnost P 0 najdeme podle vzorce (1), za předpokladum = 0:

odkud distribuční funkce hodnoty T bude:

(0-3)

Chcete-li zjistit hustotu distribuce f(t) náhodná proměnná T, je nutné odlišit výraz (0‑1).t:

0-4)

Distribuční zákon s hustotou (0-4) se nazývá exponenciální (nebo exponenciální ). Hodnota λ se nazývá parametr exemplární zákon.

Obrázek 0-4 Exponenciální distribuce

Najděte číselné charakteristiky náhodné veličiny T- matematické očekávání (průměrná hodnota) M[t] = mt , a disperze Dt. My máme

( 0-5)

(integrace po částech).

Rozptyl hodnoty T je:

(0-6)

Extrahováním druhé odmocniny rozptylu najdeme směrodatnou odchylku náhodné veličiny T.

Takže pro exponenciální rozdělení jsou matematické očekávání a směrodatná odchylka navzájem stejné a jsou inverzní k parametru λ, kde λ. intenzita proudění.

Tedy vzhled m události v daném časovém intervalu odpovídají Poissonovu rozdělení a pravděpodobnost, že časové intervaly mezi událostmi budou menší než nějaké předem určené číslo, odpovídá exponenciálnímu rozdělení. To vše jsou jen různé popisy stejného stochastického procesu.

QS Příklad-1 .

Jako příklad uveďme bankovní systém v reálném čase obsluhující velký počet zákazníků. Ve špičce tvoří požadavky bankovních pokladních, kteří pracují s klienty, Poissonův tok a přicházejí v průměru dva za 1 s (λ = 2) Tento tok se skládá z požadavků přicházejících rychlostí 2 požadavky za sekundu.

Vypočítejte pravděpodobnost P ( m ) výskyty m zprávy za 1 s. Protože λ = 2, z předchozího vzorce máme

Dosazením m = 0, 1, 2, 3, získáme následující hodnoty (až čtyřidesetinná místa):

Obrázek 0-5 Nejjednodušší příklad toku

Je také možných více než 9 zpráv za 1 s, ale pravděpodobnost je velmi malá (asi 0,000046).

Výsledné rozdělení lze znázornit jako histogram (zobrazeno na obrázku).

Příklad CMO-2.

Zařízení (server), které zpracovává tři zprávy za 1s.

Nechť existuje zařízení, které dokáže zpracovat tři zprávy za 1 s (µ=3). V průměru jsou dvě zprávy přijaty za 1 s a v souladu C Poissonovo rozdělení. Jaká část těchto zpráv bude zpracována ihned po obdržení?

Pravděpodobnost, že rychlost příchodu bude menší nebo rovna 3 s, je dána

Pokud systém dokáže zpracovat maximálně 3 zprávy za 1 s, pak je pravděpodobnost, že nebude přetížen

Jinými slovy, 85,71 % zpráv bude doručeno okamžitě a 14,29 % s určitým zpožděním. Jak vidíte, ke zpoždění při zpracování jedné zprávy po dobu delší, než je doba zpracování 3 zpráv, dojde jen zřídka. Doba zpracování 1 zprávy je v průměru 1/3 s. Zpoždění větší než 1 s bude tedy vzácné, což je pro většinu systémů celkem přijatelné.

Příklad CMO 3

· Pokud je bankovní pokladník zaneprázdněn během 80 % své pracovní doby a zbytek času tráví čekáním na zákazníky, lze jej považovat za zařízení s faktorem využití 0,8.

· Pokud je komunikační kanál použit pro přenos 8bitových symbolů rychlostí 2400 bps, tj. za 1 s se přenese maximálně 2400/8 symbolů a budujeme systém, ve kterém je celkové množství odeslaných dat 12000 symbolů z různých zařízení přes kanál za rušnou minutu (včetně synchronizace, znaků konce zprávy, řídicích znaků atd.), pak se míra využití vybavení komunikačního kanálu během této minuty rovná

· Pokud modul pro přístup k souborům v zaneprázdněné hodině provede 9 000 přístupů k souboru a doba na jeden přístup je v průměru 300 ms, pak je využití hardwaru modulu pro přístup k souborům

Pojem využití zařízení bude používán poměrně často. Čím více se využití zařízení blíží 100 %, tím větší je zpoždění a delší fronta.

Pomocí předchozího vzorce můžete sestavit tabulky hodnot Poissonovy funkce, ze kterých můžete určit pravděpodobnost přijetím nebo více zpráv v daném časovém období. Pokud je například průměr 3,1 zprávy za sekundu [tj. e. λ = 3.1], pak pravděpodobnost přijetí 5 nebo více zpráv za danou sekundu je 0,2018 (např.m = 5 v tabulce). Nebo v analytické formě

Pomocí tohoto výrazu může systémový analytik vypočítat pravděpodobnost, že systém nesplní dané kritérium zatížení.

Často lze provést počáteční výpočty pro hodnoty zatížení zařízení.

p ≤ 0,9

Tyto hodnoty lze získat pomocí Poissonových tabulek.

Nechť opět průměrná rychlost příchodu zprávy λ = 3,1 zprávy/s. Z tabulek vyplývá, že pravděpodobnost přijetí 6 a více zpráv za 1 s je 0,0943. Proto lze toto číslo brát jako zátěžové kritérium pro počáteční výpočty.

10.6.2. Designové výzvy

Vzhledem k náhodné povaze příchodu zpráv na zařízení stráví zařízení část času zpracováním nebo obsluhou každé zprávy, což vede k vytváření front. Fronta v bance čeká na uvolnění pokladníka a jeho počítače (terminálu). Fronta zpráv ve vstupní vyrovnávací paměti počítače čeká na zpracování procesorem. Fronta požadavků na datová pole čeká na uvolnění kanálů atd. Fronty se mohou tvořit ve všech úzkých hrdlech systému.

Čím vyšší je míra využití zařízení, tím delší jsou výsledné fronty. Jak bude ukázáno níže, je možné navrhnout systém, který uspokojivě funguje s faktorem využití ρ = 0,7, ale faktor větší než ρ > 0,9 může mít za následek špatnou kvalitu služeb. Jinými slovy, pokud má hromadný datový spoj 20% zatížení, je nepravděpodobné, že na něm bude fronta. Při načítání; je 0,9, pak se zpravidla budou tvořit fronty, někdy velmi velké.

Koeficient využití zařízení se rovná poměru zatížení zařízení k maximálnímu zatížení, které toto zařízení snese, nebo se rovná poměru doby obsazení zařízení k celkové době jeho provozu.

Při návrhu systému je běžné odhadnout faktor využití pro různé druhy zařízení; příslušné příklady budou uvedeny v dalších kapitolách. Znalost těchto koeficientů vám umožňuje vypočítat fronty pro odpovídající zařízení.

· Jaká je délka fronty?

· Kolik času to zabere?

Na otázky tohoto typu lze odpovědět pomocí teorie front.

10.6.3. Systémy hromadné obsluhy, jejich třídy a hlavní charakteristiky

U QS jsou toky událostí toky požadavků, toky „obslužných“ požadavků atd. Pokud tyto toky nejsou Poissonův (Markovův proces), matematický popis procesů probíhajících v QS se stává nesrovnatelně složitější a vyžaduje těžkopádnější aparát, převedení do analytických vzorců je možné pouze v nejjednodušších případech.

Aparát „markovovské“ teorie front může být užitečný i v případě, kdy proces probíhající v QS je odlišný od Markova, s jeho pomocí lze přibližně odhadnout charakteristiky účinnosti QS. Je třeba poznamenat, že čím složitější je QS, čím více servisních kanálů obsahuje, tím přesnější jsou přibližné vzorce získané pomocí Markovovy teorie. Navíc v řadě případů není pro informovaná rozhodnutí o řízení provozu QS vůbec nutné mít přesné znalosti o všech jeho charakteristikách, často zcela přibližné, orientační.

QS jsou klasifikovány do systémů s:

selhání (se ztrátami). V takových systémech požadavek, který dorazí v okamžiku, kdy jsou všechny kanály obsazeny, obdrží „odmítnutí“, opustí QS a neúčastní se dalšího procesu obsluhy.

čekání (s frontou). V takových systémech se požadavek, který přijde, když jsou všechny kanály obsazené, zařadí do fronty a čeká, dokud se jeden z kanálů neuvolní. Když je kanál volný, jedna z aplikací ve frontě je přijata ke službě.

Služba (disciplína ve frontě) v čekacím systému může být

spořádaný (přihlášky se doručují v pořadí přijetí),

· neuspořádaný(přihlášky jsou podávány v náhodném pořadí) popř

zásobník (poslední aplikace je vybrána jako první z fronty).

Přednost

Ó se statickou prioritou

Ó s dynamickou prioritou

(v druhém případě a priori tet se může například prodlužovat s čekací dobou na požadavek).

Systémy s frontou se dělí na systémy

· s neomezeným čekáním a

· s omezeným čekání.

V systémech s neomezeným čekáním se každý požadavek, který přijde v okamžiku, kdy nejsou volné kanály, dostane do fronty a „trpělivě“ čeká na uvolnění kanálu, který jej přijme do služby. Každá žádost, kterou CMO obdrží, bude dříve nebo později doručena.

V systémech s omezeným čekáním jsou uvalena určitá omezení na setrvání aplikace ve frontě. Tato omezení mohou platit

· délka fronty (počet aplikací současně ve frontovém systému s omezenou délkou fronty),

· doba setrvání aplikace ve frontě (po určité době setrvání ve frontě aplikace frontu opustí a systém odejde s omezenou čekací dobou),

· celkový čas strávený aplikací v QS

atd.

V závislosti na typu QS lze při hodnocení jeho účinnosti použít určité hodnoty (ukazatele výkonnosti). Například u QS s poruchami je jednou z nejdůležitějších charakteristik jeho produktivity tzv absolutní šířka pásma průměrný počet požadavků, které může systém obsloužit za jednotku času.

Spolu s absolutním se často uvažuje relativní propustnost CMO je průměrný podíl příchozích požadavků obsluhovaných systémem (poměr průměrného počtu požadavků obsluhovaných systémem za jednotku času k průměrnému počtu požadavků přijatých během této doby).

Kromě absolutní a relativní propustnosti při analýze QS s poruchami nás mohou v závislosti na zadání studie zajímat i další charakteristiky, například:

· průměrný počet obsazených kanálů;

· průměrné relativní prostoje systému jako celku a jednotlivého kanálu

atd.

Očekávané QS mají mírně odlišné vlastnosti. Je zřejmé, že u QS s neomezenou čekací dobou ztrácí absolutní i relativní propustnost smysl, protože každý požadavek dorazí brzy.nebo později bude doručeno. Pro takový QS jsou důležité vlastnosti:

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

· průměrný počet aplikací v systému (ve frontě a ve službě);

· průměrná doba čekání na žádost ve frontě;

· průměrný čas strávený aplikací v systému (ve frontě a ve službě);

stejně jako další charakteristiky očekávání.

Pro QS s omezeným čekáním jsou zajímavé obě skupiny charakteristik: jak absolutní, tak relativní propustnost a charakteristiky čekání.

Pro analýzu procesu probíhajícího v QS je nezbytné znát hlavní parametry systému: počet kanálů P, intenzita aplikačního prouduλ , výkon každého kanálu (průměrný počet požadavků μ obsluhovaných kanálem za jednotku času), podmínky pro vytvoření fronty (omezení, pokud existují).

V závislosti na hodnotách těchto parametrů jsou vyjádřeny charakteristiky účinnosti provozu QS.

10.6.4. Vzorce pro výpočet QS charakteristik pro případ servisu s jedním zařízením

Obrázek 0-6 Model systému hromadné obsluhy s frontou

Takové fronty mohou být vytvořeny zprávami na vstupu procesoru, které čekají na zpracování. Mohou nastat během provozu účastnických stanic připojených k vícebodovému komunikačnímu kanálu. Podobně se tvoří fronty aut na čerpacích stanicích. Pokud však existuje více než jeden vstup do služby, máme frontu s mnoha zařízeními a analýza se stává složitější.

Zvažte případ nejjednoduššího toku servisních požadavků.

Účelem zde prezentované teorie front je přiblížit se průměrné velikosti fronty a také průměrné době strávené zprávami čekajícími ve frontách. Je také žádoucí odhadnout, jak často fronta překročí určitou délku. Tyto informace nám umožní vypočítat například potřebné množství vyrovnávací paměti pro ukládání front zpráv a souvisejících programů, požadovaný počet komunikačních linek, požadované velikosti vyrovnávací paměti pro huby atd. Bude možné odhadnout doby odezvy.

Každá z charakteristik se liší v závislosti na použitých prostředcích.

Zvažte frontu s jedním serverem. Při návrhu výpočetního systému se většina front tohoto typu počítá pomocí výše uvedených vzorců. variační faktor doby provozu

Khinchin-Polachekův vzorec se používá k výpočtu délek fronty při návrhu informačních systémů. Aplikuje se v případě exponenciálního rozdělení času příchodu pro libovolné rozdělení času služby a jakékoli kontrolní disciplíny, pokud volba další zprávy pro službu nezávisí na době služby.

Při projektování systémů dochází k situacím, kdy vznikají fronty, kdy kontrolní disciplína nepochybně závisí na době obsluhy. V některých případech se například můžeme rozhodnout použít pro službu nejdříve kratší zprávy, abychom získali rychlejší průměrnou dobu služby. Při správě komunikační linky je možné přiřadit vyšší prioritu vstupním zprávám než výstupním zprávám, protože první jsou kratší. V takových případech již není nutné používat Khinchinovu rovnici

Většina servisních dob v informačních systémech leží někde mezi těmito dvěma případy. Konstantní servisní časy jsou vzácné. Ani doba přístupu na pevný disk není konstantní kvůli rozdílné poloze datových polí na povrchu. Jedním příkladem ilustrujícím případ konstantní servisní doby je obsazení komunikační linky pro přenos zpráv pevné délky.

Na druhé straně není rozptyl servisního času tak velký jako v případě libovolného nebo exponenciálního rozdělení, tj.σs zřídka dosahuje hodnott s. Tento případ je někdy považován za „nejhorší případ“, a proto se používají vzorce, které odkazují na exponenciální rozložení servisních časů.Takový výpočet může poskytnout poněkud nadhodnocené velikosti fronty a čekací doby, ale tato chyba přinejmenším není nebezpečná.

Exponenciální rozložení servisních časů rozhodně není tím nejhorším případem, se kterým se člověk musí ve skutečnosti vypořádat. Pokud se však časy služeb získané výpočtem front ukáží být distribuovány hůře než časy s exponenciální distribuce, je to často varovný signál pro vývojáře. Pokud je směrodatná odchylka větší než střední hodnota, pak je obvykle potřeba výpočty opravit.

Zvažte následující příklad. Existuje šest typů zpráv s dobou služby 15, 20, 25, 30, 35 a 300. Počet zpráv pro každý typ je stejný. Směrodatná odchylka těchto časů je poněkud vyšší než jejich průměr. Hodnota poslední servisní doby je mnohem větší než ostatní. To způsobí, že zprávy budou ve frontě mnohem déle, než kdyby byly doby služby ve stejném pořadí. V tomto případě je vhodné při projektování provést opatření ke snížení délky fronty. Pokud například tato čísla souvisejí s délkami zpráv, pak by možná měly být velmi dlouhé zprávy rozděleny na části.

10.6.6. Příklad výpočtu

Při návrhu bankovního systému je žádoucí znát počet zákazníků, kteří budou muset ve špičce čekat ve frontě na jednu pokladní.

Doba odezvy systému a její směrodatná odchylka jsou vypočteny s přihlédnutím k době vstupu dat z pracovní stanice, tisku a zpracování dokumentu.

Akce pokladní byly načasovány. Doba obsluhy ts se rovná celkové době strávené pokladní u klienta. Míra využití pokladního ρ je úměrná době jeho zaměstnání. Je-li λ počet zákazníků ve špičce, pak ρ pro pokladníka je

Řekněme, že ve špičce je 30 zákazníků za hodinu. V průměru stráví pokladní 1,5 minuty na zákazníka. Pak

ρ = (1,5 x 30) / 60 = 0,75

tj. pokladna je využívána ze 75 %.

Počet lidí ve frontě lze rychle odhadnout pomocí grafů. Z nich vyplývá, že pokud ρ = 0,75, pak průměrný počet nq osobv řadě na pokladně leží mezi 1,88 a 3,0 v závislosti na standardní odchylce pro t s .

Předpokládejme, že měření směrodatné odchylky pro ts udává hodnotu 0,5 min. Pak

σ s = 0,33 t s

Z grafu na prvním obrázku zjistíme, že nq = 2,0, tj. v průměru budou u pokladny čekat dva zákazníci.

Celkový čas, který zákazník stráví u pokladny, lze nalézt jako

t ∑ = t q + t s = 2,5 min + 1,5 min = 4 min

kde t s se vypočítá pomocí Khinchin-Polachekova vzorce.

10.6.7. faktor zisku

Při analýze křivek na obrázcích vidíme, že když je zařízení obsluhující frontu využito z více než 80 %, křivky začnou narůstat alarmujícím tempem. Tato skutečnost je velmi důležitá při návrhu systémů přenosu dat. Pokud navrhujeme systém s více než 80% využitím hardwaru, pak mírné zvýšení provozu může vést k drastickému poklesu výkonu systému nebo dokonce způsobit jeho zhroucení.

Nárůst příchozího provozu o malý počet x %. vede ke zvýšení velikosti fronty přibližně o

Pokud je míra využití zařízení 50 %, pak se toto zvýšení rovná 4 ts % pro exponenciální rozložení doby provozu. Ale pokud je využití zařízení 90 %, pak nárůst velikosti fronty je 100 ts %, což je 25krát více. Mírné zvýšení zátěže při 90% využití zařízení vede k 25násobnému nárůstu velikosti fronty ve srovnání s případem 50% využití zařízení.

Podobně se prodlouží doba fronty

Při exponenciálně rozloženém servisním čase má tato hodnota hodnotu 4 t s2 pro vytížení zařízení 50 % a 100 t s2 pro koeficient 90 %, tedy opět 25krát horší.

Navíc pro malé faktory využití zařízení je vliv změn σs na velikost fronty nevýznamný. Pro velké koeficienty však změna σ s výrazně ovlivňuje velikost fronty. Proto je při navrhování systémů s vysokým vytížením zařízení žádoucí získat přesné informace o parametruσ s. Nepřesnost předpokladu ohledně exponenciality rozdělení tsje nejvíce patrný při velkých hodnotách ρ. Navíc, pokud se doba služby náhle zvýší, což je možné v komunikačních kanálech při přenosu dlouhých zpráv, pak v případě velkého ρ se vytvoří významná fronta.

Moskevská státní technická univerzita

pojmenovaný po N.E. Bauman (pobočka Kaluga)

Katedra vyšší matematiky

Práce na kurzu

v kurzu "Operační výzkum"

Simulační modelování systému hromadné obsluhy

Zadání úlohy: Sestavte simulační model a vypočítejte výkonnostní ukazatele systému hromadné obsluhy (QS) s následujícími charakteristikami:

Počet servisních kanálů n; maximální délka fronty t;

Tok požadavků vstupujících do systému je nejjednodušší s průměrnou intenzitou λ a exponenciálním zákonem rozdělení času mezi příchody požadavků;

Tok požadavků obsluhovaných v systému je nejjednodušší s průměrnou intenzitou µ a exponenciálním zákonem rozložení času obsluhy.

Porovnejte zjištěné hodnoty ukazatelů s výsledky. získané numerickým řešením Kolmogorovovy rovnice pro pravděpodobnosti stavů soustavy. Hodnoty parametrů QS jsou uvedeny v tabulce.

Úvod

Kapitola 1. Hlavní charakteristiky CMO a ukazatele jejich účinnosti

1.1 Koncept Markovova stochastického procesu

1.2 Streamy událostí

1.3 Kolmogorovovy rovnice

1.4 Konečné pravděpodobnosti a stavový graf QS

1.5 Ukazatele výkonnosti QS

1.6 Základní pojmy simulace

1.7 Stavební simulační modely

Kapitola 2

2.1 Stavový graf soustavy a Kolmogorovova rovnice

2.2 Výpočet ukazatelů výkonnosti systému podle konečných pravděpodobností

Kapitola 3

3.1 Algoritmus simulační metody QS (přístup krok za krokem)

3.2 Vývojový diagram programu

3.3 Výpočet ukazatelů výkonnosti QS na základě výsledků jeho simulace

3.4 Statistické zpracování výsledků a jejich porovnání s výsledky analytického modelování

Závěr

Literatura

Příloha 1

V operačním výzkumu se často setkáváme se systémy navrženými pro opakované použití při řešení stejného typu problémů. Procesy, které v tomto případě vznikají, se nazývají servisní procesy a systémy se nazývají queuing systems (QS).

Každý QS se skládá z určitého počtu servisních jednotek (přístrojů, zařízení, bodů, stanic), které se nazývají servisní kanály. Kanály mohou být komunikační linky, operační body, počítače, prodejci atd. Podle počtu kanálů se QS dělí na jednokanálové a vícekanálové.

Aplikace obvykle přicházejí na QS ne pravidelně, ale náhodně a tvoří tzv. náhodný tok aplikací (požadavky). Služba aplikací také pokračuje nějakou náhodnou dobu. Náhodná povaha toku aplikací a servisního času vede k tomu, že QS je zatěžován nerovnoměrně: v některých časových obdobích se hromadí velmi velké množství aplikací (buď se řadí do fronty, nebo nechávají QS neobsloužené), zatímco v jiných intervalech QS pracuje s nedostatečným zatížením nebo nečinností.

Předmětem teorie hromadné obsluhy je konstrukce matematických modelů, které spojují dané provozní podmínky QS (počet kanálů, jejich výkon, povaha toku aplikací atd.) s výkonnostními ukazateli QS, které popisují jeho schopnost vyrovnat se s tokem aplikací.

Jako ukazatele výkonnosti QS se používají následující:

Absolutní propustnost systému (A), tzn. průměrný počet aplikací obsluhovaných za jednotku času;

Relativní propustnost (Q), tzn. průměrný podíl přijatých požadavků obsluhovaných systémem;

Pravděpodobnost selhání služby požadavku (

);

Průměrný počet obsazených kanálů (k);

Průměrný počet žádostí v SOT (

);

Průměrná doba zdržení aplikace v systému (

);

Průměrný počet aplikací ve frontě (

);

Průměrný čas, který aplikace stráví ve frontě (

);

Průměrný počet aplikací obsluhovaných za jednotku času;

Průměrná doba čekání na službu;

Pravděpodobnost, že počet požadavků ve frontě překročí určitou hodnotu atd.

QS se dělí na 2 hlavní typy: QS s poruchami a QS s čekáním (fronta). V QS s odmítnutím je požadavek, který dorazí v době, kdy jsou všechny kanály obsazeny, odmítnut, opustí QS a neúčastní se dalšího servisního procesu (například požadavek na telefonický rozhovor v době, kdy jsou všechny kanály obsazeny). obsazeno obdrží odmítnutí a nechá QS neobslouženo) . V QS s čekáním požadavek, který přijde v době, kdy jsou všechny kanály obsazené, neodejde, ale čeká se ve frontě na službu.

Jednou z metod výpočtu ukazatelů výkonnosti QS je metoda simulace. Praktické využití počítačového simulačního modelování zahrnuje konstrukci vhodného matematického modelu, který zohledňuje faktory neurčitosti, dynamické charakteristiky a celý komplex vztahů mezi prvky zkoumaného systému. Simulační modelování provozu systému začíná určitým konkrétním počátečním stavem. Díky implementaci různých událostí náhodného charakteru přechází model systému v následujících okamžicích do dalších možných stavů. Tento evoluční proces pokračuje až do konce plánovacího období, tzn. až do konce simulace.

Nechť existuje nějaký systém, který mění svůj stav náhodně v průběhu času. V tomto případě říkáme, že v systému probíhá náhodný proces.

Proces se nazývá proces s diskrétním stavem, pokud jsou jeho stavy

lze vypsat předem a přechod systému z jednoho stavu do druhého nastává náhle. Proces se nazývá proces se spojitým časem, jestliže k přechodům systému ze stavu do stavu dochází okamžitě.

Operační proces QS je náhodný proces s diskrétními stavy a spojitým časem.

Náhodný proces se nazývá Markov nebo náhodný proces bez následného efektu, pokud pro jakýkoli okamžik

pravděpodobnostní charakteristiky procesu v budoucnu závisí pouze na jeho aktuálním stavu a nezávisí na tom, kdy a jak se systém do tohoto stavu dostal.

1.2 Streamy událostí

Proud událostí je sled stejnorodých událostí, které následují jedna po druhé v náhodných časech.

Proudění je charakterizováno intenzitou λ - četností výskytu událostí nebo průměrným počtem událostí vstupujících do QS za jednotku času.

Proud událostí se nazývá pravidelný, pokud události následují po sobě v pravidelných intervalech.

Proud událostí se nazývá stacionární, pokud jeho pravděpodobnostní charakteristiky nezávisí na čase. Zejména intenzita stacionárního proudění je konstantní hodnota:

.

Proud událostí se nazývá běžný, pokud pravděpodobnost zasáhne malé časové období

dvě nebo více událostí je malá ve srovnání s pravděpodobností zasažení jedné události, tj. pokud se v ní události objevují jednotlivě a ne ve skupinách.

Proud událostí se nazývá proud bez následného efektu, pokud pro jakékoli dva nepřekrývající se časové intervaly