1. Vymezení základních pojmů z oblasti modelování a simulace

1. Vymezení základních pojmů z oblasti modelování a simulace Studijní cíl Úvodní blok věnuje pozornost vymezení základních pojmů z oblasti modelování a simulace s cílem zavést příslušnou odbornou terminologii, která bude používána v rámci celé této elektronické opory.

Doba nutná k nastudování

3 hodiny

Až dosud neexistuje všeobecně celosvětově uznávaný a používaný standard terminologie simulace. Stejné pojmy spojené se simulací mají pro různé autory často odlišný význam. V této opoře se při definování následujících základních pojmů vychází zejména z pojmového aparátu uvedeného v publikacích [1], [2] a [3].

1.1

Objekt zkoumání a vymezený systém

Modelování a simulace se věnuje studiu zkoumaných objektů hmotného světa, přičemž tyto objekty buď již v realitě existují (výrobní podnik, nemocnice, burza, železniční stanice, organismus živočicha apod.) nebo by existovat mohly (továrna po rekonstrukci a dobudování, nově projektovaný terminál kontejnerové dopravy, nemocí zasažený organismus atd.). Zmíněné zkoumané objekty (jak existující, tak projektované nebo myšlené) nelze v jejich úplné složitosti popsat, resp. racionálně pochopit a zvládnout. Proto jsou na nich zaváděny abstrakce, jež zanedbávají některé aspekty těchto objektů, které nejsou z pohledu konkrétního typu zkoumání důležité. Nezanedbané aspekty jsou vybírány tak, že jsou příslušným vědeckým, technickým či společenským oborem zvládnutelné. Uvedené abstrakce se v modelování a simulaci nazývají systémy. Alternativně lze předešlou myšlenku též vyjádřit tak, že na objektech zkoumání jsou vymezovány systémy. Různé druhy studia mohou na jednom objektu zkoumání vymezovat odlišné systémy. Například pro nově zřízené klientské oddělení bankovní pobočky (jako KST/IMOSI – Modelování a simulace

blok 1, strana 1 (8)

Antonín Kavička

objektu zkoumání) lze vymezit (i) systém, jenž se soustředí na kvalitu různých provozních režimů obsluhy zákazníků daného oddělení nebo (ii) systém, který se zabývá problematikou kvality konfigurace lokální počítačové sítě využívané pracovníky oddělení. Okolím zkoumaného objektu nazýváme ty objekty reálného světa, které nebyly vybrány pro potřeby zkoumání, nicméně je nutné uvažovat jejich existenci a vlastnosti kvůli vztahům se zkoumaným objektem. Abstrakci okolí zkoumaného objektu potom nazýváme okolím systému. Je-li zkoumaným objektem jisté oddělení banky, do jeho okolí mohou patřit (i) jiná oddělení této banky, která s ním příslušným způsobem komunikují nebo (ii) proudy zákazníků přicházející z ulice do banky. Při vymezování systému na objektu zkoumání se může nebo nemusí zanedbat význam času. Systém, jenž od významu času abstrahuje, se nazývá statickým systémem. Naproti tomu systém, jehož čas není zanedbáván (a je chápán ve smyslu klasické „newtonovské“ a nikoliv kvantové fyziky) se v oboru modelování a simulace nazývá dynamickým systémem. Množina okamžiků, v nichž dynamický systém existuje, se nazývá (časovou) existencí dynamického systému, přičemž tato existence je dána abstrakcí a může ji představovat jakákoliv množina reálných čísel. Zkoumání vymezeného systému na objektu oddělení banky, které je zaměřeno na režimy obsluhy zákazníků, může definovat existenci, která zahrnuje „pouze“ okamžiky, v nichž dochází k zahajování, resp. ukončování činností zahrnutých do systému (např. obslužné činnosti na přepážkách, přemísťování zákazníků uvnitř banky, přemísťování obslužného personálu apod.). Kromě těchto okamžiků nás chování systému nezajímá, a tedy z tohoto pohledu systém v jiných okamžicích neexistuje. Systém je složen z prvků (entit), které představují určité fyzické nebo logické elementy objektu zkoumání. Rozlišujeme permanentní a temporární prvky, přičemž první z nich jsou v dynamickém systému během celé jeho existence, kdežto druhé nikoliv. Temporární entity mohou být exogenní nebo endogenní. Exogenní prvky vznikají vně systému (v jeho okolí), zatímco endogenní vznikají v samotném systému. Analogicky temporární prvky mohou zaniknout tím, že jsou přesunuty do okolí systému (a tím pro systém přestanou existovat) nebo zaniknou přímo v systému. Rozlišujeme též stabilní prvky (nazývané často infrastruktura) a mobilní prvky, které mají schopnost přemísťovat se nebo být přemísťovány v prostoru. KST/IMOSI – Modelování a simulace


Antonín Kavička

Příkladem temporárních exogenních prvků systému jsou zákazníci přicházející do banky. Dokumentace k žádosti o půjčku, která byla vyhotovena pracovníkem oddělení, podepsána zákazníkem a je dále archivována, je příkladem endogenního temporárního prvku. Permanentními prvky v tomto příkladu mohou být stabilní prvky infrastruktury (pevné bariéry vymezující koridory pro fronty čekajících zákazníků, přepážky apod.), či obslužný personál (mobilní prvky). Podle funkce prvku v systému rozlišujeme obsluhující prvky (obslužné zdroje) a obsluhované prvky (zákazníci). Je však nutné mít na paměti, že tyto funkce prvků se mohou v průběhu času měnit. Sledované vybavení bankovní pobočky (přepážky, bankomaty, bariéry), jakož i personál představují obslužné zdroje zkoumaného systému. Klienti přicházející do banky jsou zákazníci systému. Během údržby se však například i bankomat, jako obslužný zdroj sloužící klientům, stává sám zákazníkem. Prvky systému mají své vlastnosti, které se nazývají atributy, které přiřazují prvkům nějaké hodnoty, jež se mohou u prvků dynamického systému v čase měnit. Atributy lze dále členit na standardní a referenční. Standardní atributy přiřazují prvkům „standardní hodnoty“ (např. reálná čísla, booleovské hodnoty, texty) zatímco referenční atributy přiřazují prvkům systému jiné prvky, tj. definují vazby/relace mezi prvky. Stav dynamického systému v čase t je určen prvky, které jsou v čase t v systému přítomny a hodnotami jejich atributů v tomto čase. Stav dynamického systému oddělení banky je v daném čase určen všemi prvky, které se v systému aktuálně nacházejí (zákazníci, personál, infrastruktura apod.) a dále aktuálními hodnotami jejich atributů. Pro názornost uveďme, že například prvek systému – zákazník může disponovat atributy: jméno, příjmení, rodné číslo, čísla účtů, stavy na účtech, reference na přepážku, na níž se aktuálně nachází, nebo dále prvek-bankovní úředník je charakterizován atributy: identifikační číslo, specializace na dané bankovní operace, reference na právě obsluhovaného zákazníka atd.

1.2

Model versus simulační model

Termín model je v oblasti modelování a simulace používán pro analogii mezi dvěma systémy: modelovaným (neboli originálem) a modelujícím. Vztah obou systémů je dán tím, že každému prvku PO originálu je přiřazen prvek PM

KST/IMOSI – Modelování a simulace


Antonín Kavička

modelujícího systému, každému atributu aO prvku PO je přiřazen atribut aM prvku PM , přičemž pro hodnoty atributů aO a aM je dána nějaká relace. Jsou-li modelovaný i modelující systém statické, říkáme, že daný model je statický model. V simulaci se uplatňují pouze tzv. simulační modely, které splňují následující požadavky: 1. Modelovaný systém (originál) i jeho modelující systém jsou dynamické systémy. 2. Existuje zobrazení τ existence originálu do existence modelujícího systému. Je-li tO časový okamžik, v němž existuje modelovaný systém O, je mu přiřazen τ(tO) = tM, v němž existuje modelující systém M, a tak je zobrazením τ přiřazen i stavu SO(tO) systému O stav SM(tM) systému M. 3. Mezi stavy SO(tO) a SM(tM) jsou splněny požadavky na vztahy mezi prvky a jejich atributy, jak již bylo uvedeno při definici modelu. 4. Zobrazení τ je neklesající. Pokud nastane stav SO1 originálu před nějakým jeho jiným stavem SO2, pak stav SM1, který odpovídá v modelujícím systému stavu SO1, nastane před stavem SM2, který odpovídá stavu SO2 (nebo mohou nastat současně). Tento požadavek vyjadřuje nutnost dodržovat vztahy kauzality z originálu i v modelujícím systému. Lze tedy shrnout, že model je struktura, která váže dva systémy, jejich prvky a jejich atributy, a v případě simulačních modelů i existence obou systémů. V běžné praxi je ustáleno, že pod pojmem model se rozumí modelující systém, i když tento pojem není přesný a výstižný. V případě simulačních modelů se raději než pojmy modelovaný a modelující systém používají pojmy simulovaný systém (nebo originál) a simulující systém. Analogicky jako u modelujícího systému se místo termínu simulující systém používá buď méně přesný termín simulační model, nebo též simulátor.

1.3

Modelování versus simulace

Podstatou modelování ve smyslu výzkumné techniky/metody je náhrada zkoumaného systému (originálu) jeho modelujícím systémem (nebo stručněji jeho modelem), jejímž cílem je získat pomocí pokusů (experimentů) s modelem informaci o originálu. V odborné praxi je výše zmíněné modelování obvykle chápáno tak, že zahrnuje jak budování modelu (modelujícího systému), tak provádění experimentů s tímto modelem. KST/IMOSI – Modelování a simulace


Antonín Kavička

Modelující systém (model) může být realizován mnoha různými způsoby, například jako abstraktní matematická struktura (vzorec, systém diferenciálních rovnic apod.) interpretovaná na papíře, v měřítku zmenšená napodobenina (třeba sítě městských vodních kanálů), komplexní datová struktura v paměti číslicového počítače (tento typ modelujícího systému je v poslední době velmi masivně využíván) atd. Simulace je v oblasti aplikované informatiky, resp. kybernetiky chápána jako modelování ve smyslu výzkumné techniky, při němž je použit simulační model. Jedna z vhodných definic simulace je následující. Simulace je výzkumná technika/metoda, jejíž podstatou je náhrada zkoumaného dynamického systému (originálu) jeho simulátorem, s nímž se experimentuje s cílem získat informace o původním zkoumaném dynamickém systému. Nutno zdůraznit, že aby šlo o simulaci, musí být cílem experimentů se simulátorem získání informací o simulovaném systému (originálu). Výše zmíněný simulátor je možné principiálně realizovat na různých speciálních zařízeních a podle nich potom získává pojem simulace příslušné přívlastky např. elektromechanická, hydrodynamická, mechanická, analogová (pomocí analogových počítačů), hybridní (pomocí analogo-číslicových počítačů) apod. V současné době je drtivá většina simulátorů realizována na číslicových počítačích – mluvíme o tzv. číslicové simulaci. V celé opoře se budeme věnovat pouze číslicové simulaci, a proto nebudeme tento přívlastek používat. Program, který řídí výpočet při simulaci, se nazývá simulačním programem.

1.4

Poznámky k metodě Monte Carlo

Jako metodu Monte Carlo označujeme řešení numerických úloh pomocí speciálně organizovaných statistických pokusů. Při použití této metody získáváme řešení pomocí umělých realizací náhodných (stochastických) procesů, jež jsou vytvořeny tak, aby jejich charakteristiky (střední hodnota, pravděpodobnost výskytu jevu apod.) odrážely charakter originálních procesů. Je tedy třeba: formulovat novou úlohu (pravděpodobnostní model), která má shodné řešení s původní úlohou, řešit novou úlohu pomocí statistických experimentů. KST/IMOSI – Modelování a simulace


Antonín Kavička

Metoda Monte Carlo je charakterizována specifickými numerickými postupy (generování hodnot náhodných veličin, metody redukce rozptylu, vyhodnocení přesnosti výsledků) řešení úloh stochastického charakteru (bez nároku zkoumat dynamické systémy), zatímco simulační metody jsou určeny ke studiu výhradně dynamických systémů – z tohoto pohledu tedy nelze klasifikovat metodu Monte Carlo jako metodu simulační. Pozn.: V některé odborné literatuře je možné se setkat s nepřesnou klasifikací metody Monte Carlo jako metody statické simulace.

Příklad aplikace metody Monte Carlo – Buffonova úloha Na desku, na níž jsou nakresleny dvě rovnoběžné přímky, je náhodně vrhána jehla. Označme délku jehly H, vzdálenost dvou sousedních přímek L, vzdálenost středu jehly po dopadu od bližší z přímek y. Úhel α svírá jehla s kolmicí na přímky (obr. 1.1).

H/2

α y

L

Obr. 1.1 Buffonova jehla po dopadu na pracovní desku Podmínka, že jehla protne jednu z přímek je: y ≤ (H/2) . cos α pro 0 ≤ y ≤ (L/2), 0 ≤ α ≤ (π/2) Pravděpodobnost, že jehla při jednom pokusu zůstane ležet na desce tak, že protne jednu z přímek, lze vyjádřit analyticky vztahem (ilustrace na obr. 1.2): π /2

P=

∫ 0

H .cos dα H .[sin α ]π / 2 0 2 2H = 2 = π L πL πL . 2 2 4



Antonín Kavička

Obr. 1.2 Grafická ilustrace podkladu pro výpočet pravděpodobnosti protnutí

Analytické řešení pravděpodobnosti P, že jehla protne jednu z přímek, lze experimentálně ověřit aplikací metody Monte Carlo, tj. prováděním „umělého házení jehly na desku“, které je na počítači realizováno jako série nezávislých pokusů - generování dvojic hodnot [yi,αi] náhodných proměnných y a α. Pro vygenerovanou dvojici hodnot [yi,αi] zkoumáme splnění podmínky protnutí jedné z přímek. V případě, že zkoumaný jev nastal, inkrementujeme proměnnou m (četnost protnutí). Pro daný počet pokusů n potom lze vypočítat požadovanou pravděpodobnost výskytu jevu:

PEXP =

m n

a případně provést experimentální odhad hodnoty čísla π:

π=

2H PEXP L

Úkol Pomocí metody Monte Carlo realizujte série „Buffonových pokusů“ a znázorněte závislost experimentálního odhadu hodnoty čísla π od počtu realizovaných náhodných pokusů.



Antonín Kavička

Otázky k procvičení 1. 2. 3. 4. 5.

Co představuje vymezení systému na objektu zkoumání? Jaké jsou odlišnosti mezi statickým a dynamickým systémem? Čím se liší model od simulačního modelu? V čem se odlišuje modelování od simulace? Čím je charakteristická metoda Monte Carlo?

Odkazy a další studijní prameny [1]

[2] [3]

Křivý, I., Kindler, E.: Simulace a modelování, elektronický učební text Přírodovědecké fakulty Ostravské univerzity, Ostravská univerzita, Ostrava, 2001. Banks, J.: Handbook of simulation, John Wiley and Sons, New York, 1998. Kavička, A., Klima, V., Adamko, N. Agentovo orientovaná simulácia dopravných uzlov. Žilina: EDIS - vydavateľstvo ŽU, 2005.



Antonín Kavička

2. Experimenty se simulačním modelem Studijní cíl Problematika probíraná v tomto bloku se věnuje oblasti simulačních experimentů s cílem přiblížit typy realizací základních akčních jednotek simulace a specifikace scénářů simulačních experimentů. 3 hodiny


2.1

Aktivity a procesy

Věnujme se nyní aktivitám a procesům, které modelují dynamické vlastnosti systému, tj. plynutí času a změny stavu systému v čase. Aktivita představuje základní akční jednotku simulace (obr 2.1), která je obrazem jisté činnosti v simulovaném systému (např. pohyb dopravního prostředku po elementárním volném úseku dopravní infrastruktury, obslužná činnost klienta u přepážky v bance, opracování výrobku na jednom pracovišti výrobního závodu, apod.), přičemž pro ni platí, že: - má jisté časové trvání a - (potenciálně) mění stav systému. Běh simulačního programu je představován vykonáváním jednotlivých aktivit a to ve stejném pořadí, v němž se vykonávají jim odpovídající činnosti v simulovaném systému. aktivita

t1

čas

t2

Obr. 2.1 Aktivita a její časové trvání Stejně jako mluvíme o časové existenci systému, můžeme hovořit i o časové existenci aktivity jako důležité součásti simulovaného systému. Časová existence aktivity je charakterizovaná množinou reálných čísel (časových KST/IMOSI – Modelování a simulace


Antonín Kavička

okamžiků), v nichž aktivita existuje, tedy může měnit stav systému. Z tohoto hlediska rozeznáváme dva druhy aktivit. Spojitá aktivita může měnit stav systému v průběhu celé doby svého trvání. V tomto případě (obr. 2.2) je časová existence aktivity charakterizovaná intervalem reálných čísel 〈t1,t2〉. aktivita

t1

možné změny stavu

t2

Obr. 2.2 Spojitá aktivita Příkladem spojité aktivity může být přesun těžkého dopravního prostředku z pozice A do pozice B v případě, že chceme podrobně respektovat dynamiku pohybu v závislosti na vlastnostech dopravního prostředku a vnějších podmínkách. Charakteristickým znakem spojité aktivity je, že při jejím zahájení nejsme schopni určit čas jejího ukončení. Diskrétní aktivita je charakterizovaná tím, že může změnit stav systému pouze v okamžiku svého ukončení; v průběhu trvání aktivity stav systému změnit nemůže. Tuto situaci lze chápat tak, že aktivita existuje jen v okamžiku svého ukončení a tedy její existence je charakterizovaná jednoprvkovou množinou reálných čísel {t2} (obr. 2.3). Ukončení diskrétní aktivity a následnou změnu stavu systému nazýváme událost (U). aktivita U t2

t1

Obr. 2.3 Diskrétní aktivita Příkladem diskrétní aktivity může být přesun dopravního prostředku z pozice A do pozice B v případě, že nemáme důvod podrobně sledovat dynamiku pohybu. Předpokládáme tedy, že dopředu určíme pevnou dobu přesunu (charakteristický znak diskrétní aktivity) a zajímá nás pouze událost ukončení přesunu. Výskyt diskrétních, resp. spojitých aktivit v simulovaném systému dost podstatně ovlivňuje charakter simulátoru a vede k rozlišování několika typů simulací. KST/IMOSI – Modelování a simulace


Antonín Kavička

V případě, že simulovaný systém obsahuje pouze spojité aktivity, potom mluvíme o spojité simulaci. Jestliže simulovaný systém obsahuje výhradně diskrétní aktivity, pak mluvíme o diskrétní simulaci. V případě, že simulovaný systém obsahuje jak spojité tak i diskrétní aktivity, potom příslušnou simulaci označujeme jako kombinovanou (diskrétně-spojitou) simulaci. Často je užitečné rozšířit pojem aktivita na pojem proces. Proces je posloupnost přirozeně na sebe navazujících aktivit, které spolu tvoří jistý logický celek (například průjezd automobilu částí města, roznesení pošty listonošem apod.). Pro názornost si můžeme proces znázornit graficky (obr. 2.4). Vidíme, že uvedený proces se skládá ze tří aktivit (a1, a2 a a3). Po startu procesu P se nejdříve vykoná aktivita a1, po jejím ukončení aktivita a2 a nakonec aktivita a3, jejíž konec je chápán zároveň jako konec procesu P. a2

a1

t1

t2

a3

t3

t4

Obr. 2.4 Proces P složený ze sekvence aktivit a1,a2,a3

2.2

Simulační experimenty

Dostáváme se k pojmům spojeným s experimentováním se simulačním modelem, což technicky znamená spouštění (provádění) simulačního programu. Nejdříve je nutné nakonfigurovat scénu, na níž se bude odehrávat simulační „děj“. Pod scénou rozumíme množinu všech permanentních prvků systému s hodnotami jejich atributů. Dynamické chování systému je definováno scénářem, přičemž tento je určen: scénou s jejími vlastnostmi, pravidly vstupu, výstupu, generování a zániku temporárních prvků, rozhodovacími a řídicími algoritmy popisujícími procesy obsluhy. Běh simulačního programu podle jednoho definovaného scénáře se nazývá simulační pokus (experiment) se simulátorem. Uskutečněním simulačního KST/IMOSI – Modelování a simulace


Antonín Kavička

pokusu získáme informace o chování systému při aplikovaném scénáři (v literatuře se v této souvislosti někdy uvádí, že simulační pokus dává odpověď na otázku „co se stane, když…“). Scénář definuje množinu hodnot vstupních parametrů a výsledkem pokusu je množina výstupních hodnot charakterizujících chování systému. Vstupní parametry nemusí být deterministické. Naopak, v typických případech je mnoho vstupních parametrů představováno náhodnými proměnnými. V takovém případě jsou samozřejmě i příslušné výstupní hodnoty realizacemi náhodných proměnných (výstupních náhodných proměnných). Proto je nutné uskutečňovat celou sérii pokusů (tzv. replikace pokusu) se stejným scénářem ale různými instancemi hodnot vstupních náhodných proměnných. Na výstupu dostaneme pro každou replikaci množinu výstupních hodnot – instancí výstupních náhodných proměnných. Tyto hodnoty jsou potom statisticky zpracovány (např. výpočtem aritmetického průměru příslušných hodnot ze všech replikací se odhadne střední hodnota výstupní náhodné proměnné). Simulační pokus potom tedy nedává informaci např. o délce fronty (žadatelů o zdroj), nýbrž o střední délce fronty. Scénář může být definován ve zjednodušené formě například takto: (i) scéna zahrnuje jednu konkrétní verzi infrastruktury oddělení banky (počet přepážek a případně automatizovaných míst obsluhy) a dále definované počty a profese uvažovaných pracovníků oddělení, (ii) příchody zákazníků do oddělení jsou generovány na základě měsíčního statistického sledování, (iii) jsou algoritmizována pravidla pro zařazování se zákazníků do front na obsluhy, jakož i pravidla přestupování mezi frontami. Probíhá-li na počítači simulační pokus, je v jeho průběhu evidován i čas, který v dané fázi simulace odpovídá reálnému času (tj. času v simulovaném systému). Čas v rámci simulačního pokusu označujeme jako simulační čas, přičemž tento typicky ubíhá rychleji (výjimečně i pomaleji) než čas reálný. Simulační čas (podobně jako reálný) nemůže klesat. Typické použití simulačních modelů v praxi si klade vyšší ambice, než studium chování systému při jednom scénáři. Ve všeobecnosti může být při studiu příslušného systému cílem nalézt takový scénář, při jehož uplatnění se systém chová nejlépe/optimálně (v souvislosti se zadanými kritérii). Zmíněná motivace vede k návrhu série simulačních pokusů s různými scénáři koncipovanými tak, aby se co nejefektivněji získala odpověď na zadané otázky. Tato série pokusů se nazývá simulační studie nebo simulační projekt.



Antonín Kavička

2.3

Uplatnění simulace

Kdy je vhodné experimentální výzkumnou techniku - simulaci, která nenabízí automaticky optimální řešení daného problému, aplikovat? Metodu simulace je vhodné použít zejména v těch případech, kdy: popis zkoumaného dynamického systému je značně složitý, a tudíž by bylo extrémně složité aplikovat jiné analytické exaktní nebo heuristické metody (např. operačního výzkumu) nebo vyvstává potřeba prozkoumat širokou škálu odlišných (provozních) variant zkoumaného dynamického systému (tedy je často potřeba podstatně měnit konfiguraci vymezeného systému), jejichž zpracování bývá při použití jiných metod obvykle málo flexibilní. Dalším důvodem pro použití simulace může být „akutní“ potřeba poskytnutí on-line animace, která umožní názorně sledovat obrazy procesů vymezeného zkoumaného systému, což se může uplatnit u aplikací typu: „trenažér“, kdy kupříkladu na daném simulátoru experimentuje řídící pracovník pracující v rámci odpovídajícího objektu zkoumání, který je školen (příp. zkoušen) pro řešení jak obvyklých tak neočekávaných provozních problémů nebo „rekonstrukce“, kdy je na základě přesných historických dat např. rekonstruována problémová pracovní směna s cílem věrně demonstrovat celý její průběh a poukázat na kořeny vzniklých problémů.

Otázky k procvičení 1. Jaké jsou základní akční jednotky simulace a jak je lze alternativně realizovat? 2. Čím se od sebe liší aktivity a procesy? 3. Co je charakteristické pro kombinovanou diskrétně spojitou simulaci? 4. Jak je specifikován scénář simulačního experimentu? 5. Jaká je indikace pro nasazení experimentální výzkumné techniky simulace?



Antonín Kavička

3. Základní metody synchronizace výpočtu v rámci simulačních modelů Studijní cíl V rámci tohoto bloku bude věnována pozornost zejména vybraným metodám synchronizace simulačního výpočtu v počítačové simulaci. Cílem je prezentovat základní typy algoritmů, které jsou využitelné pro řízení běhu simulačních programů.


3.1

3 hodiny

Úvodní poznámky

Zaměřme se nejprve na popis základní metodiky algoritmizace simulačního modelu, jejímiž hlavními úkoly jsou: a) navržení datových struktur dat pro reprezentaci stavů simulovaného systému, jakož i operací, které nad touto strukturou pracují (realizují změny stavu systému), b) zobrazení simulačního času a jeho plynutí (průběhu) a c) zajištění synchronizace stavových změn systému tak, aby tyto změny probíhaly v určitém pořadí (při dodržení vztahů kauzality v simulovaném systému) a při určitých hodnotách simulačního času nebo v okamžicích, kdy je splněna určitá podmínka týkající se stavu či konfigurace modelu. Dobrý návrh datových struktur (jak z hlediska paměťové reprezentace, tak z hlediska výpočetní složitosti jejich frekventovaných operací) umožňuje provádět efektivní výpočty během realizace pokusu se simulátorem. V průběhu realizace simulačního experimentu je evidován měnící se čas, který by v dané fázi výpočtu odpovídal času v simulovaném systému (simulační čas), přičemž pro jeho plynutí musí být zabezpečeno, že děje v simulátoru závisejí na simulačním čase stejným způsobem, jako jejich vzory v originálu na toku přirozeného času. Způsoby synchronizace simulačního výpočtu mohou být značně odlišné, a proto alespoň stručně charakterizujme dvě základní metody. KST/IMOSI – Modelování a simulace


Antonín Kavička

3.2

Metoda plánování událostí

Metoda plánování událostí, která je jednou z nejrozšířenějších metod uplatňovaných při realizaci diskrétní simulace, je založena na plánování výskytů událostí do budoucnosti. Ilustrujme si tuto metodu na příkladu realizace aktivity. Pro diskrétní simulaci je charakteristické, že doba trvání aktivity je známá už při jejím odstartování, tedy v okamžiku startu aktivity určíme čas jejího ukončení, na který naplánujeme událost, která bude představovat její konec. Trvání odpovídá časové zpoždění výskytu koncové události (U) aktivity (obr. 2.3 v bloku 2). Při zpracování koncové události jedné aktivity je možné případně odstartovat další aktivitu a to naplánováním její příslušné koncové události s odpovídajícím časovým zpožděním. Informaci o naplánované události je nutno až do okamžiku jejího výskytu v modelu někde uchovávat a to obvykle v příslušné datové struktuře označované jako kalendář událostí (někdy též jako časová osa). Tato datová struktura disponuje kromě jiného základní operací Výběr, která po řídícím příkazu simulačního programu provede odebrání té události z kalendáře, jejíž hodnota času plánovaného výskytu je nejmenší ze všech událostí obsažených v kalendáři. Z tohoto pohledu je vhodné pro implementaci kalendáře využít koncepci prioritní fronty, přičemž priority jejích prvků/událostí určuje čas výskytu. Prakticky bychom tedy mohli událost představit jako datovou strukturu zapouzdřující zejména atribut čas výskytu události (časové razítko) a operace Plánuj a Zpracuj. Metoda Plánuj vykoná naplánování události (vložení do kalendáře) do budoucnosti na jistý čas výskytu a metoda Zpracuj provede v okamžiku výskytu události (výběru z kalendáře) požadované stavové změny, resp. plánování dalších událostí. Běh simulačního programu uplatňující diskrétní simulaci dle zmíněné metody můžeme chápat jako cyklické plánování událostí, jejich vybírání z kalendáře a provádění příslušných výkonných akcí, které jsou spojeny s jejich výskytem. Algoritmus uvedeného cyklu je formálně popsán v Tab. 3.1. Na obrázku 3.1 je stylizovaně graficky znázorněna koncepce konfigurace modulu diskrétní simulace založená na metodě plánování událostí.



Antonín Kavička

Vykonána za podmínek

KROK Činnost 0

1

2 3 4 5

Inicializace simulačního času tS (tS = 0)

Ukončení běhu simulačního programu

Kalendář neobsahuje události nebo je vyčerpán čas pro běh simulace

Výběr události z „vrcholu“ kalendáře (s nejmenší hodnotou /tU / plánovaného času výskytu) Aktualizace simulačního času (tS = tU) Výkon akce spojené s výskytem události (akce provádí stavové změny a případné plánování dalších událostí) Návrat na KROK 1

Tab. 3.1 Algoritmus simulačního výpočtu aplikující metodu plánování událostí

Modul Kalendář událostí (časová osa)

Odebrání události z vrcholu

Zpracování události

Plánování událostí

Pokyn zpracovat další událost

Řídicí algoritmus

Zpracování dokončeno

Provádění změn stavu

Obr. 3.1 Koncepce konfigurace modulu diskrétní simulace

Příklad aplikace metody plánování událostí Aplikaci metody plánování událostí nyní ilustrujme na zjednodušeném příkladu nově plánovaných provozoven „Drive-in občerstvení“ u dálnice (viz obr. 3.2). Zmíněné provozovny mají být vybudovány pro každý jízdní směr, přičemž ke každé z nich bude vést samostatný odbočovací pruh. KST/IMOSI – Modelování a simulace


Antonín Kavička

Obr. 3.2 Ilustrace umístění nových provozoven „Drive-in občerstvení”

Na obrázku 3.2. je stylizovaně znázorněn objekt zkoumání a následně příslušný vymezený systém, který abstrahuje od dopravních proudů na dálnici a postihuje pouze proudy, které směřují do odbočovacích pruhů.

Obr. 3.3 Diagram plánování událostí



Antonín Kavička

INICIALIZACE

STAV A-Obsluha = nepracuje B-Obsluha = nepracuje A-Fronta = prázdná B-Fronta = prázdná

NAPLÁNOVÁNÍ příjezdů prvních zákazníků

ZPĚT na simulační jádro

Obr. 3.4 Logika inicializace simulačního experimentu

V rámci simulace jsou sledovány příjezdy zákazníků do odbočovacích pruhů (na základě zadaných intenzit a charakteru příslušných dopravních proudů). Po uskutečnění příjezdu se příslušný zákazník přesune přímo k výdejnímu okénku (v případě, že před ním není fronta čekatelů) a neprodleně je zahájena obsluha, tj. výdej požadovaného jídla (časové trvání tohoto úkonu se odvíjí od zadaných charakteristik). Není-li možno po příjezdu zákazníka okamžitě zahájit obsluhu, zařadí se dorazivší zákazník do příslušné fronty, z níž později přistoupí k obsluze, až na něj přijde řada. Po dokončení obsluhy zákazníka tento následně opouští systém. Struktura simulujícího systému využívajícího událostně orientovanou architekturu je ilustrována na obrázku 3.3, kde je znázorněn tzv. diagram plánování událostí. Posláním digramu plánování událostí je specifikace jednak všech typů událostí, které se v simulujícím sytému vyskytují, a jednak plánovacích vazeb mezi těmito událostmi. Zmíněný diagram neobsahuje informace o podmínkách, za kterých k příslušným plánováním dochází. Představený diagram sestává ze čtyř typů událostí: Přijel zákazník ze směru A, Přijel zákazník ze směru B, Dokončena obsluha zákazníka ze směru A, Dokončena obsluha zákazníka ze směru B. Plánovací vazby jsou znázorněny orientovanými hranami (inicializační hrany vyjadřují nutnost naplánování prvních dvou událostí do kalendáře ještě před spuštěním simulace.



Antonín Kavička

UDÁLOST "Přijel zákazník ze směru A"

STATISTIKA Zaznamenání času příjezdu zákazníka ze směru A

NAPLÁNOVÁNÍ příjezdu dalšího zákazníka ze směru A

STAV obsluhy A ?

STAV Zařazení zákazníka do A-Fronty

STAV A-Obsluha = pracuje


NAPLÁNOVÁNÍ ukončení obsluhy zákazníka ze směru A


UDÁLOST "Dokončena obsluha zákazníka ze směru A"

STATISTIKA Zaznamenání času odjezdu zákazníka

STAV A-Fronty?

STAV A-Obsluha = nepracuje

STAV Přechod prvního zákazníka z A-Fronty do obsluhy


NAPLÁNOVÁNÍ ukončení obsluhy zákazníka ze směru A


Obr. 3.5 Logika zpracování vybraných událostí KST/IMOSI – Modelování a simulace


Antonín Kavička

Obr. 3.6 Ilustrace evoluce běhu simulačního experimentu KST/IMOSI – Modelování a simulace


Antonín Kavička

Aktuální simulační čas

Probíhající obsluhy zákazníků

Zákazníci ve frontách

Zákazníci v systému

Naplánov. příjezdy zákazníků

Naplánov. konce obsluh zákazníků

A1 B1

-----

Inicializace 0,00

-----

-----

-----

Po zpracování události „Přijel zákazník ze směru A“ (zákazník A1) 1,1

A1 ---

-----

A1 ---

A2 B1

A1 ---

Po zpracování události „Přijel zákazník ze směru B“ (zákazník B1) 1,3

A1 B1

-----

A1 B1

A2 B2

A1 B1

Po zpracování události „Dokončena obsluha zákazníka ze směru B“ (zákazník B1) 10,8

A1 ---

-----

A1 ---

A2 B2

A1 ---


A1 B2

-----

A1 B2

A2 B3

A1 B2


A1 B2

--B3

A1 B2, B3

A2 B4

A1 B2

Po zpracování události „Přijel zákazník ze směru A“ (zákazník A2) 11,4

A1 B2

A2 B3

A1, A2 B2, B3

A3 B4

A1 B2

Po zpracování události „Dokončena obsluha zákazníka ze směru B“ (zákazník B2) 15,2

A1 B3

A2 ---

A1, A2 B3

A3 B4

A1 B3

Tab. 3.2 Ilustrace evoluce běhu simulačního experimentu

Obr. 3.7 Struktura simulačního modelu využívající zobecněné událostí KST/IMOSI – Modelování a simulace


Antonín Kavička

Logika zpracování vybraných událostí (včetně inicializačních úkonů před startem simulace) je zjednodušeně specifikována na obrázcích 3.4−3.6. U operací zaměřených na plánování nových událostí do budoucnosti lze generovat hodnotu časového razítka (udávající okamžik času výskytu příslušné události) buď s uplatněním deterministického, anebo stochastického přístupu. Na obrázku 3.6 a v tabulce 3.2 je ilustrována jedna z možných evolucí běhu simulačního experimentu z pohledu plánování událostí a aktuální zaplněnosti kalendáře. Diagram plánování událostí z obrázku 3.5 by bylo možné dále zobecnit, tj. bylo by možné redukovat model na využívání pouze dvou typů událostí (obr. 3.7), přičemž jeden typ události by zpracovával příjezdy zákazníků z obou směrů a druhý typ události by ošetřoval dokončení všech obsluh. Zobecnění lze dosáhnout vhodnou parametrizací při plánování událostí.

3.3

Metoda snímání aktivit

Metoda snímání aktivit, někdy též označovaná jako dvojfázová metoda, je použitelná jak pro realizaci diskrétní, tak spojité simulace. Princip této metody je založen na principu snímání všech v simulátoru právě „běžících“ aktivit v daných (obvykle pevných – ekvidistantních) přírůstcích simulačního času τ (někdy též mluvíme o snímací periodě). Přesnost této metody je závislá na zvolené velikosti snímací periody. Při každém snímání aktivity dochází k jejímu vyhodnocování, tj. zkoumá se, zda v simulačním čase tS = n*ττ (hodnota n vyjadřuje, o kolikáté snímání od počátku simulace jde) došlo: k ukončení aktivity, ke změně hodnot příslušných dynamických atributů a případně ke splnění aktivační podmínky (například dosažení dané prahové hodnoty atributu nebo výskyt interakce mezi aktivitami) pro vykonání specifické akce. Pro spojitou simulaci je charakteristické, že aktivita je formalizována analytickým popisem (např. soustavou diferenciálních rovnic), přičemž je principiálně možné zjistit hodnotu požadovaných atributů v libovolném simulačním čase. Volba periody snímání může být určena příslušným integračním krokem použité metody numerické integrace. Běh simulačního programu, založený na metodě snímání aktivit, je realizován jako periodické vyhodnocování běžících aktivit simulátoru (tab. 3.3). Je-li při vyhodnocování splněna aktivační podmínka, pak je provedena příslušná akce. KST/IMOSI – Modelování a simulace


Antonín Kavička


KROK Činnost 0

Inicializace simulačního času tS (tS = 0)

1

Ukončení běhu simulačního programu

2

3 4

Je vyčerpán čas pro běh simulace

1. fáze Vyhodnocování všech běžících aktivit vzhledem k času tS a výkon příslušných akcí při splnění aktivačních podmínek 2. fáze Aktualizace simulačního času (tS = tS + τ) Návrat na KROK 1

Tab. 3.3 Algoritmus simulačního výpočtu využívající metodu snímání aktivit

3.4

Poznámky k implementaci

Ukončeme probírané téma poznámkou, že algoritmy (právě uvedených synchronizačních metod) řídící běh simulačního programu jsou obvykle implementovány v samostatných synchronizačních rutinách. Tyto rutiny bývají označovány jako simulační jádro, které dále zahrnují příslušné operace (přístupné konstruktérovi simulátoru) umožňující aktivně ovlivňovat, případně monitorovat simulační experiment (jsou například k dispozici operace na zahájení simulace, zjištění hodnoty aktuálního simulačního času, definování hodnoty snímací periody, apod.).

Otázky k procvičení 1. K čemu slouží kalendář událostí? 2. Jaké jsou vhodné implementace kalendáře událostí. 3. Jaké podmínky musí být splněny pro ukončení simulace synchronizované metodou plánování událostí? 4. Kdy dochází k aktualizaci simulačního času při uplatnění metody snímání aktivit a metody plánování událostí? 5. Pro jaký typ simulace je aplikovatelná metoda plánování událostí a metoda snímání aktivit?



Antonín Kavička

4. Životní cyklus simulačního projektu Studijní cíl Cílem výkladu v tomto bloku je představení základních etap životního cyklu simulačního projektu, jak jsou typicky realizovány v rámci aplikačních projektů v praxi.


2 hodiny

Simulační projekt (jinak též nazývaný jako simulační studie) se zaměřuje na studium zkoumaného (existujícího nebo projektovaného) dynamického systému, vymezeného na objektu zkoumání, s cílem odpovědět na otázky s tímto objektem zkoumání spojené, přičemž je využívána výzkumná metoda – simulace. Simulační projekt sestává ze dvou základních etap a to z etapy návrhu a tvorby simulačního modelu a dále z etapy experimentování s tímto modelem. Uvedené etapy lze dále členit do dílčích fází, které mohou probíhat jak sekvenčně tak paralelně. Životní cyklus zmíněného simulačního projektu je znázorněn na obrázku 4.1.

4.1

Etapa návrhu a tvorby simulačního modelu

1. fáze Na začátku každého projektu, resp. při jeho zadávání jsou formulovány základní problémy, které trápí zákazníka, o nichž si tento myslí, že pro jejich řešení je vhodné nasadit výzkumnou metodu simulace. Jakmile řešitel pochopí podstatu zákazníkových problémů (které je mnohdy nutné ve spolupráci se zákazníkem přeformulovat), musí si nejprve odpovědět (na základě svých zkušeností) na otázku, zda je pro jejich řešení metoda simulace vhodná a zda je schopen ji vzhledem k povaze problému úspěšně aplikovat. Jestliže je odpověď na uvedenou otázku kladná, potom je nutné si na reálném objektu, k němuž zákazník své problémy vztahuje, po provedené analýze vymezit objekt zkoumání, na který bude během celého projektu soustředěna pozornost. KST/IMOSI – Modelování a simulace


Antonín Kavička

Obr. 4.1 Základní životní cyklu simulačního projektu KST/IMOSI – Modelování a simulace


Antonín Kavička

2. fáze Dalším úkolem na začátku projektu je stanovení konkrétních cílů a časového plánu projektu. Cíle projektu vlastně navozují otázky, které mají být během projektu zodpovězeny.

3. fáze Následně je na objekt zkoumání uplatněna abstrakce, tedy je na něm vymezen zkoumaný/simulovaný systém (originál), který zohledňuje ty prvky objektu zkoumání (spolu s jejich vazbami) a ty jejich vlastnosti, které jsou důležité pro řešení problémů projektu v souladu s cílem.

4. fáze Dále je zvolena vhodná koncepce pro tvorbu simulačního modelu tzn. je vybrána metodika tvorby spojená s některou s architektur simulačního modelu (událostní, procesovou, agentovou apod.). V závislosti od zvolené koncepce je možné v jistém (neimplementačním) formalismu vytvořit též konceptuální model, který specifikuje základní funkční a řídicí části budoucího simulačního modelu zatím bez nutnosti definovat jejich detaily. Je nutné, aby do fáze přípravy a tvorby modelu byl též zahrnut zákazník. S volbou uvedené koncepce je obvykle spojen i výběr vhodného implementačního prostředí, resp. simulačního jazyka, v němž bude simulační model později realizován.

5. fáze Paralelně se 4. fází probíhá sběr a analýza dat potřebných pro simulační model, přičemž jejich charakter může být různý. Sbírají se například: data popisující vlastnosti jednotlivých prvků originálu, data popisující povahu procesů (deterministické nebo stochastické), data o pravidlech technologických postupů, dále historická data o vstupech prvků z okolí do systému (na nich může být následně provedena statistická analýza, jež bude podkladem pro parametrizaci generátorů vstupujících prvků), data o rozhodovacích pravidlech pro řešení konfliktů v systému apod. Řešitel projektu by se měl snažit, aby potřebná data sesbíral sám zákazník a dodal je v požadovaném elektronickém formátu (např. s využitím údajů z informačních systémů).

6. fáze Po ukončení výše zmíněných fází se přistupuje k samotné tvorbě tedy implementaci simulačního modelu, která je spojena zejména s navrhováním a implementací vhodných datových struktur, v nichž budou uchovávány prvky simulačního modelu a dále s implementací jak řídicích, tak výkonných KST/IMOSI – Modelování a simulace


Antonín Kavička

komponentů simulátoru. Jak již bylo zmíněno výše, je nutné si vybrat vhodné implementační prostředí, resp. programovací jazyk, který konstruktérovi dovolí budovat model, vzhledem k jeho charakteru, existujícími adekvátními prostředky. Například pro tvorbu modelů, které zahrnují takovou třídu úkolů, pro něž již existují specializované simulační nástroje (zaměřené například na simulaci počítačových sítí, výrobních systémů, elektronických obvodů apod.) je vhodné tyto nástroje použít a neimplementovat takové simulační modely v obecnějších simulačních nebo dokonce obecných vyšších programovacích jazycích. Volba adekvátního realizačního prostředku vždy závisí na zkušenostech a schopnostech řešitelského týmu. Častým požadavkem na implementaci bývá on-line animace, která umožňuje sledovat a kontrolovat důležité simulační pokusy s cílem transparentně posuzovat uplatnitelnost jednotlivých scénářů simulačních pokusů v praxi. Online animace umožňuje experimentátorovo pohodlné sledování evoluce simulačního pokusu a v případě potřeby mu rovněž usnadňuje provádění interaktivních zásahů do simulátoru za běhu simulačního programu. Dalším možným požadovaným výstupem je poskytnutí post-simulačních grafických protokolů, které mohou například zobrazovat nasazení obslužných zdrojů v čase na určité úkoly. Implementační koncepce může stavět buď na (i) klasickém popisu pomocí programového kódu (nevýhodou je, že každý nutný opravný či modifikující zásah je spojen s nutností měnit programový kód příslušné části simulátoru) anebo na (ii) deklarativním přístupu, tj. takovém formálním popisu, který je možné měnit vně simulačního programu pomocí změny struktury řídicích dat – jedná se tedy o značně flexibilnější přístup, který umožňuje mnohem efektivnější práci se simulátorem. Realizace druhého přístupu může být například spojena s použitím Petriho sítě (rozšiřující modelovací možnosti stavových automatů), která představuje vhodný formalismus popisu dynamiky dané části systému, přičemž konkrétní topologie příslušné Petriho sítě může být simulačnímu programu předána jako parametr obsahující aktuální řídicí data (ta mohou být pohodlně editována ve speciálním grafickém editoru), přičemž daná Petriho síť je v simulačním programu interpretována pomocí specializovaného interpreta.

7. fáze Jakmile je implementace simulačního modelu dokončena, je nutné ověřit správnost simulačního programu, resp. model verifikovat. Model je považován za správný, resp. verifikovaný, jestliže průběh simulačního výpočtu odpovídá KST/IMOSI – Modelování a simulace


Antonín Kavička

aktuální představě vyjádřené v konceptuálním modelu neboli je funkčně správný. V procesu verifikace se uplatňují různé metody a přístupy, které umožňují testování funkční správnosti simulátoru, resp. jeho jednotlivých částí/komponentů (testuje se např. korektnost interakce procesů, dodržování vztahů kauzality, korektnost generátorů vstupů apod.). Dobrým „pomocníkem“ v procesu verifikace se taktéž jeví on-line animátor, který umožňuje sledovat, ve vhodné grafické formě, změny ve stavovém prostoru simulátoru. Postupně odhalované závady funkčnosti simulačního odstraňovány opravnými implementačními zásahy.

modelu

jsou

8. fáze Po úspěšném završení verifikace je dále potřebné otestovat pravdivost neboli provést validaci simulačního modelu. V této fázi se vlastně zjišťuje, zda simulátor odráží objekt zkoumání na takové úrovni přesnosti, která se od něj očekává a která byla zadaná v cílech projektu. Nebo jinými slovy, zda simulátor představuje takovou substituci reality, která je způsobilá k experimentování. Validaci lze provádět pomocí různých metodik: (i) metoda srovnávání s realitou porovnává chování simulátoru s chováním (reálného) objektu zkoumání pomocí statistických metod, (ii) metoda srovnávání s jiným modelem na rozdíl od metody předešlé provádí srovnávání s jiným (matematickým) modelem a konečně (iii) empirická metoda je založená na studiu vnějšího chování simulátoru nezávislým odborníkem – expertem z příslušné oblasti, který posuzuje, zda je toto chování dostatečně realistické. První metoda může využívat pro srovnávání historická data (např. statisticky zpracovaná) spojená s objektem zkoumání, která jsou aplikována v jednotlivých simulačních pokusech. Metoda druhá a třetí je aplikována zejména v případech, kdy vůči simulátoru neexistuje originál (je projektovaný nebo jen myšlený), a tudíž srovnání s realitou nelze provést. Nedostatky odhalené při validaci mohou být spojeny s potřebou přehodnotit konceptuální model a pořídit případné nové typy dat nebo je dokonce nutné provést nové vymezení systému na objektu zkoumání. V těchto případech je nezbytné znovu vybudovat (resp. modifikovat) i samotný simulátor a opět ověřit jeho správnost a pravdivost. Fáze verifikace a validace se v praxi mnohdy prolínají a není možné je od sebe striktně oddělovat. Další významnou skutečností je fakt, že v simulačním KST/IMOSI – Modelování a simulace


Antonín Kavička

projektu je velmi důležité přesvědčit zákazníka, že simulátor představuje po ukončené validaci důvěryhodnou substituci reality, neboli že simulátor je kredibilní. Jaké přístupy lze uplatnit pro ověření pravdivosti (již verifikovaného) simulátoru? První možnost je nejdříve sestrojit simulátor tak, aby odrážel stávající stav zkoumaného objektu, a potom jej otestovat pomocí metody srovnávání s realitou a doplňkově též pomocí empirické metody (pro ni je možné využít vhodného specializovaného odborníka, který může v případě úspěchu osvědčit kredibilitu modelu). Metoda srovnávání s realitou může využívat historická data, jež jsou v dnešní době poměrně lehce dostupná například z různých informačních systémů, které v reálném čase monitorují procesy spojené se zkoumaným objektem. Prokáže-li se, že model je věrohodný, lze dále simulátor modifikovat tak, aby odrážel změny v systému, které odpovídají projektovým záměrům. Validace takto modifikovaného a verifikovaného simulátoru je prakticky možná uplatněním empirické metody.

4.2

Etapa simulačních experimentů

9. fáze Na začátku druhé etapy projektu je nutné sestavit plán simulačních experimentů, jejichž postupné provádění povede k dosažení cílů projektu. Samozřejmě není možné očekávat sestavení fixního detailního plánu, kterého je nutno se striktně držet. Postupně získávané výsledky jednotlivých experimentů mohou celý plán i scénáře jednotlivých experimentů korigovat. Simulační studie zaměřené na racionalizaci provozu obslužných systémů často využívají scénářů postavených na počátečním předpokladu nelimitovaných obslužných zdrojů, které jsou postupně v rámci dalších scénářů redukovány až na minimum, které umožní realizaci provozu v požadované kvalitě.

10. fáze Po sestavení plánu experimentů začíná proces provádění samotných simulačních experimentů. Výsledky jednotlivých experimentů jsou statisticky zpracovány, analyzovány a je přijato rozhodnutí o scénářích dalších experimentů. Jestliže byly provedeny experimenty, jejichž rámec byl vymezen v původním plánu a vyvstaly nové problémy, resp. potřeba realizace další série



Antonín Kavička

experimentů, je nutné se vrátit a sestavit další plán experimentů a ty opět provést. Tento iterační proces má za cíl najít dobré (v ideálním případě optimální) řešení problémů, které jsou během projektu zkoumány.

11. fáze Po ukončení experimentování se simulátorem vyvstává úkol vypracovat závěrečnou zprávu, která vyhodnotí celý projekt (na základě doložených podkladů o vyhodnocení provedených experimentů), vyjádří se k dosažení cílů projektu a předloží doporučení řešení problémů spojených s objektem zkoumání. Závěrečná zpráva obvykle obsahuje zdůvodnění navrhovaných řešení zkoumaných problémů na základě důkladného statistického zpracování širokého spektra výsledků simulačních pokusů a dále může pro vybrané pokusy doložit post-simulační grafické časové protokoly. Doporučuje se taktéž zákazníkovi dodat softwarový prohlížeč vybraných simulačních pokusů, který mu umožní tyto reprodukovat (včetně animačních výstupů a vytváření statistik) bez možnosti měnit jejich vstupní data. Zmíněný prohlížeč je v zásadě možné používat během celé doby experimentování, na němž může tímto způsobem zákazník participovat a dávat k jeho průběhu své připomínky.

Otázky k procvičení 1. Jaké jsou základní etapy simulačního projektu/studie? 2. Jaká opatření jsou typicky prováděna pro zabezpečení vstupů simulačního modelu? 3. Jak lze charakterizovat verifikaci simulačního modelu? 4. Jaké postupy lze uplatnit při validaci simulačního modelu? 5. Za jakých podmínek je možné v simulačním projektu přistoupit k provádění naplánovaných simulačních experimentů?



Antonín Kavička

5. Demonstrační simulační projekt – prvotní analýza vstupních dat Studijní cíl Na příkladu simulačního zkoumání zjednodušených variant provozu pokladního oddělení pobočky banky budou postupně ilustrovány jednotlivé fáze simulačního projektu. V rámci tohoto bloku bude věnována pozornost zejména problematice analýzy dat s cílem následně vytvářet generátory vstupních dat pro příslušný simulátor. 3 hodiny


5.1

Motivační poznámky

Centrála EM-Banky plánuje rekonstruovat pobočku, přičemž plán prostorového uspořádání pokladního oddělení pobočky po rekonstrukci odpovídá znázornění na obrázku 5.1. Uvedený plán počítá s: jednou přepážkou vyhrazenou pro informátora, pěti standardními přepážkami pro vyřizování bankovních operací pokladními úředníky a jedním pokladním automatem.

Obr. 5.1 Prostorové uspořádání pokladního oddělení na pobočce banky



Antonín Kavička

8.2

Závěry simulačního projektu

Výše uvedené výsledky simulačních experimentů vedou k následujícím závěrům: Jeden automat není schopen zabezpečit požadovanou kvalitu obsluhy zákazníků. Instalace dvou automatů umožňuje obsluhovat téměř 89 % zákazníků na požadované úrovni kvality, tj. čekací doba ve frontě nepřesáhne 3 minuty. Po instalaci tří automatů je téměř u všech zákazníků započata jejich obsluha do 3 minut po jejich příchodu do banky. Využití automatů je okolo 75 % v případě, jsou-li k dispozici dva automaty a okolo 50 % pro případ instalace tří automatů. Doporučuje se nákup dvou nebo tří automatů, přičemž vylepšení kvality obsluhy při instalaci tří automatů musí být zváženo vzhledem k dodatečným nákladům. Uplatnění společné fronty vede k lepší kvalitě obsluhy (patrné zejména pro případ instalace dvou automatů), a proto lze její využívání managementu banky doporučit. Pro celkové zhodnocení provozu pokladního oddělení by bylo vhodné simulační model dále rozšířit o ostatní obslužná místa (informátora a pokladníků).

Pozn.: Problematika aplikace statistických metod v simulačních projektech byla v rámci této opory zpracována ve spolupráci s Mgr. Věrou Záhorovou, Ph.D. (Katedra informatiky v dopravě, Dopravní fakulta Jana Pernera).

Otázky k procvičení 1. Jakou metodiku lze uplatnit pro určení vhodného, resp. dostatečného počtu replikací simulačního experimentu? 2. Jaké jsou možnosti pro stanovení požadované míry přesnosti hodnot sledovaných typů ukazatelů získávaných statistickým zpracováním výstupních dat simulačních experimentů?



Antonín Kavička

9.

Modelování vstupů simulátoru

Studijní cíl V rámci tohoto bloku jsou shrnuty různé možnosti poskytování vstupních dat simulačnímu modelu v průběhu simulačního výpočtu. Cílem je představit jednak klasifikaci simulačních modelů podle způsobů realizace proudů vstupních dat a jednak stručně přiblížit odlišné techniky tvorby submodelů vstupů.


3 hodiny

Vstupní data, resp. způsoby jejich vytváření a poskytování simulačnímu programu v průběhu jeho výpočtu, představují důležitou součást simulačních modelů (obr. 9.1). Ty části simulačních modelů, které se produkcí vstupní dat (příp. jejich uchováváním) zabývají, jsou často označovány jako submodely vstupů.

9.1

Klasifikace podle vnitřní struktury submodelů

Submodely vstupů lze klasifikovat podle jejich vnitřní struktury. Z tohoto pohledu tedy rozlišujeme dva typy submodelů (obr. 9.2). Standardní submodel je chápán a realizován jako standardní model (pojem je definován v úvodním bloku této opory), tj. každému prvku PO originálu (resp. jeho daného podsystému vstupů) je přiřazen prvek PM simulátoru (resp. jeho odpovídajícího modulu vstupů), každému atributu aO prvku PO je přiřazen atribut aM prvku PM, přičemž pro hodnoty atributů aO, aM je dána nějaká relace. Naproti tomu tzv. metamodel představuje takový submodel, který nemá charakter standardního modelu, nýbrž se chová jako černá skříňka produkující požadovaný typ dat. To tedy znamená, že metamodel nezveřejňuje uživateli svoji vnitřní strukturu, a tudíž nemá smysl rozlišovat jednotlivé prvky submodelu.



Antonín Kavička

Standardní submodel bychom mohli ilustrovat na submodelu vstupů zákazníků do banky. Zmíněný submodel rozlišuje jednotlivé chodce (z nichž někteří vstupují do banky) pohybující se po chodnících vedle banky. Metamodel produkující stejný proud vstupujících zákazníků do banky (jako předešlý typ modelu) je možné realizovat pomocí generátorů pseudonáhodných čísel. Příslušná vygenerovaná data (náhodně vygenerované doby příchodů a typy požadovaných transakcí) jsou následně podkladem k vytvoření entity vstupující do modelu. REÁLNÝ OBJEKT zkoumání REÁLNÝ OBJEKT zkoumání

ABSTRAKCE

VALIDACE

Vymezený systém ORIGINÁL

VERIFIKACE

REALIZACE Analýza Návrh Implementace

Vstupní proces nebo jev ABSTRAKCE Vymezený systém ORIGINÁL Stochastický submodel IMPLEMENTACE SIMULÁTOR

SIMULÁTOR

Generátor pseudonáhodných čísel

Obr. 9.1 Grafická ilustrace příkladu submodelů vstupů jako součásti simulátoru

9.2

Kategorizace podle uplatnění náhodnosti v submodelech

Další možností rozlišování submodelů vstupů je vzhledem k uplatnění či neuplatnění náhodnosti (obr. 9.2 - 9.3). Deterministický submodel je založen na vytváření proudu vstupních dat podle deterministických pravidel (tj. náhodnost není uplatněna). Tato pravidla umožňují a priori určovat, jaká data budou ve vstupním proudu obsažena. Vstupy mohou být například postupně brány ze souboru příslušných sesbíraných historických dat nebo mohou být získávány z apriorních plánů (např. jízdních řádů, pracovních rozvrhů apod.) anebo produkovány softwarovými generátory založenými na deterministických předpisech. KST/IMOSI – Modelování a simulace


Antonín Kavička

Stochastické submodely typicky využívají generátory pseudonáhodných čísel. Zmíněné generátory jsou konstruovány, resp. parametrizovány buď na základě statistického zpracování reálných historických dat (využívají se empirická nebo standardní statistická rozdělení pravděpodobnosti) anebo jsou použity na základě expertního doporučení. Jako příklad deterministického submodelu můžeme uvést generátor příjezdů vlaků do osobní železniční stanice, přičemž každý příjezd vlaku je realizován na čas přesně podle jízdního řádu. S využitím stochastického submodelu je možné příjezdy vlaků do stanice zatížit náhodnými zpožděními (příp. dřívějším příjezdem) vzhledem k časům pravidelných příjezdů uvedeným v jízdním řádu.

Externí interagující standardní model "fyzicky předávající " entity ZÁKAZNÍCI

ZÁKLADNÍ SIMULAČNÍ MODEL Interní metamodel Náhodná doba obsluhy zákazníka na lince obsluhy

NEBO

Interní metamodel Deterministické časy příchodů zákazníků

Interní metamodel Náhodné poruchy linky obsluhy

Externí metamodel Deterministické časy příchodů zákazníků

ALTERNATIVNÍ REALIZACE

Obr. 9.2 Grafická ilustrace interních a externích realizací submodelů vstupů vzhledem k danému základnímu simulačnímu modelu

9.3

Iniciativní versus reaktivní charakter submodelů

Submodely vstupů mohou být v rámci simulačního programu využívány buď jako iniciativní anebo reaktivní komponenty. V prvním případě pracuje submodel vstupu iniciativně bez situačních pobídek ze strany simulačního programu (např. iniciativně mohou být neustále postupně náhodně plánovány časy příchodů zákazníků do banky). Druhý případ je založen na produkci vstupu jako reakci na určitý požadavek simulátoru při splnění jistých aktivačních podmínek (např. při přistoupení zákazníka k přepážce na podávání balíků na KST/IMOSI – Modelování a simulace


Antonín Kavička

poště je ze strany simulátoru vyvolán reaktivní submodel vstupu, který náhodně vygeneruje množinu balíků, které následně vstoupí do simulujícího sytému systému).

Obr. 9.3 Grafická ilustrace aspektů ovlivňujících konstrukci metamodelů a možností jejich využívání

9.4

Příklady technik generování pseudonáhodných čísel

Generátory pseudonáhodných čísel jsou obvykle důležitou součástí simulačních modelů založených na aplikaci stochastického přístupu typicky v rámci submodelů vstupů. Zmíněné generátory různých typů bývají standardní součástí simulačních nástrojů, resp. vyšších programovacích jazyků. Generátory mohou být konstruovány/programovány s využitím odlišných technik resp. přístupů, přičemž této problematice se věnuje řada specializovaných publikací. Obecně lze formulovat následující základní požadavky kladené na generátory pseudonáhodných čísel: KST/IMOSI – Modelování a simulace


Antonín Kavička

dlouhá perioda, po níž se proud pseudonáhodných začne opakovat, nežádoucí korelace mezi jednotlivými vygenerovanými čísly (tzv. autokorelace), efektivita z časového i paměťového hlediska, reprodukovatelnost vygenerovaného proudu čísel (při použití stejné násady), uskutečnitelnost realizací nezávislých proudů (při použití odlišných nastavení tzv. násad). Uvedeme alespoň jeden přístup využitý při konstrukci generátoru (reálných) pseudonáhodných čísel rovnoměrně rozdělených na intervalu 〈0,1〉.

Příklad lineárního kongruenčního generátoru Lineární kongruenční generátor lze založit na aritmetickém rekurentním předpisu: xn = (a xn - 1 + c) mod m přičemž význam použitých symbolů je následující: m – modulus a – multiplikativní konstanta c – aditivní konstanta x0 – násada Pro i-té vygenerované číslo (i = 0,1,… ) je využíván předpis: ui = xi / m přičemž 0 ≤ xi ≤ m – 1, m > 0, a < m, c < m, x0 < m a perioda je maximálně m (např. m = 231-1, m = 232). Ukázka konkrétního vygenerování čísla u1 pro zadané parametry: m = 231-1 = 2147483647, c = 0, a = 16807, x0 = 12345 x1 = (16807 x 12345) mod m = 207482115 u1 = 207482415 / m = 0,0966165285

Příklad obecné techniky generování pseudonáhodných čísel Pro konstrukce generátorů pseudonáhodných čísel (obecně produkujících čísla, která nejsou rovnoměrně rozdělená např. na intervalu 〈0,1〉) lze využít různé techniky. Stručně komentujme jednu z možných technik, která je založena na metodě inverzní transformace. Tato metoda využívá znalost inverzní funkce (F-1) k dané distribuční funkci (F) určitého typu teoretického rozdělení pravděpodobnosti. Techniku konkrétního generování pseudonáhodného čísla ilustrujme na příkladu pro exponenciální rozdělení. KST/IMOSI – Modelování a simulace


Antonín Kavička

Distribuční funkce pro exponenciální rozdělení (s parametrem a = 1 / μ) má tvar:

1 − e − x / a pro x > 0 F ( x) =  pro x ≤ 0 0 přičemž příslušnou inverzní funkci lze zapsat jako:

x = F −1 ( u ) = − a ln (1 − u ) Pro výpočet konkrétního čísla, které vyprodukuje generátor exponenciálního rozdělení, je nejdříve generátorem rovnoměrného rozdělení na intervalu 〈0,1〉 vygenerováno číslo u (ve vyšších programovacích jazycích je pro tento účel obvykle k dispozici rutina random). Číslo u je následně dosazeno do vztahu příslušné inverzní funkce, a tím dostaneme pseudonáhodné číslo x daného typu rozdělení. Z programátorského hlediska jsou tedy realizovány v podstatě dva řádky kódu: u := random x := -a × ln (1-u)

Metodu inverzní transformace můžeme demonstrovat i graficky (obr. 9.4). Na ose y jsou zvýrazněny dvě hodnoty vygenerovaného čísla u (0,145 a 0,751), pro něž jsou zjištěny hodnoty příslušných čísel x (0,157 a 1,388). U=1

F(x)=1-exp(-x) U=0,751

U=0,145

U=0

x

X=0 X=0,157 X=1,388

Obr. 9.4 Ilustrace metody inverzní transformace pro exp. rozd. (param. a=1)



Antonín Kavička

9.5

Závěrečné poznámky

Příklady přípravy různých submodelů vstupů (zejména stochastických metamodelů) byly přiblíženy v rámci prezentovaného demonstračního projektu hlavně v pátém a šestém bloku této opory. V příloze tohoto bloku jsou uvedeny příklady často využívaných teoretických rozdělení pravděpodobnosti. Pro každé rozdělení je graficky ilustrována funkce hustoty pravděpodobnosti, distribuční funkce a nakonec jsou graficky představeny průběhy funkce hustoty pravděpodobnosti pro tři odlišné hodnoty parametru (resp. sad parametrů) příslušného rozdělení.

Otázky k procvičení 1. Podle jakých kritérií lze klasifikovat submodely vstupů simulátorů? 2. Jaké techniky lze využít pro konstrukci generátorů pseudonáhodných čísel? 3. Jaký je základní rozdíl mezi deterministickým a stochastickým submodelem vstupu? 4. Čím je charakteristický submodel vstupu realizovaný jako metamodel? 5. V jakých typických případech lze doporučit používání iniciativních submodelů vstupu?



Antonín Kavička

Příloha - příklady teoretických rozdělení pravděpodobnosti f(x)

Rovnoměrné rozdělení - hustota pravděpodobnosti

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

0.5

1

F(x)

1.5

2

2.5

3

3.5

4

4.5

5

x

4

4.5

5

x

Rovnoměrné rozdělení - distribuční funkce

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

0.5

1

1.5

2


2.5

3

3.5


Antonín Kavička

f(x)

Rovnoměrné rozdělení - hustota pravděpodobnosti

0.5 a = -2 a=0 a=3

0.45

b=1 b=5 b = 12

0.4

0.35

0.3

0.25

0.2

0.15

0.1

0.05

0 -5

0


5

10


15

x

Antonín Kavička

f(x)

Normální rozdělení - hustota pravděpodobnosti

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0 -5

0

F(x)

5

10

15

x

15

x

Normální rozdělení - distribuční funkce

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0 -5

0


5

10


Antonín Kavička

f(x)

Normální rozdělení - hustota pravděpodobnosti

1

µ=0 σ=1 µ = 2 σ = 0,5 µ=5 σ=3

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0 -5

0


5

10


15

x

Antonín Kavička

f(x)

Trojúhelníkové rozdělení - hustota pravděpodobnosti

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0 -5

F(x)

0

5

10

x

10

x

Trojúhelníkové rozdělení - distribuční funkce

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0 -5

0


5


Antonín Kavička

f(x)

Trojúhelníkové rozdělení - hustota pravděpodobnosti

1 a= 0 m=1 b=2 a = -3 m = 1 b = 1,5 a= 2 m=3 b=9

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0 -5

0


5


10

x

Antonín Kavička

f(x)

Exponenciální rozdělení - hustota pravděpodobnosti

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

F(x)

5

10

15

x

15

x

Exponenciální rozdělení - distribuční funkce

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

5


10


Antonín Kavička

f(x)

Exponenciální rozdělení - hustota pravděpodobnosti

2

µ=2 µ = 0,5 µ = 0,2

1.8

1.6

1.4

1.2

1

0.8

0.6

0.4

0.2

0

0

5


10


15

x

Antonín Kavička

f(x)

Gama rozdělení - hustota pravděpodobnosti

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

5

10

15

x

15

x

Gama rozdělení - distribuční funkce

F(x) 1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

5


10


Antonín Kavička

f(x)

Gama rozdělení - hustota pravděpodobnosti

0.8 a = 0,8 b = 4 a=4 b = 0,8 a=4 b=2

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

5


10


15

x

Antonín Kavička

f(x)

Beta rozdělení - hustota pravděpodobnosti

2.5

2

1.5

1

0.5

0

0

0.1

0.2

0.3

F(x)

0.4

0.5

0.6

0.7

0.8

0.9

1

0.9

1

x

Beta rozdělení - distribuční funkce

2.5

2

1.5

1

0.5

0

0

0.1

0.2

0.3

0.4


0.5

0.6

0.7

0.8


x

Antonín Kavička

f(x)

Beta rozdělení - hustota pravděpodobnosti

7 a = 2, b = 2 a = 2, b = 5 a = 15, b = 2

6

5

4

3

2

1

0

0

0.1

0.2

0.3

0.4


0.5

0.6

0.7

0.8

0.9


1

x

Antonín Kavička

f(x)

Erlangovo rozdělení - hustota pravděpodobnosti

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

F(x)

5

10

15

x

15

x

Erlangovo rozdělení - distribuční funkce

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

5


10


Antonín Kavička

f(x)

Erlangovo rozdělení - hustota pravděpodobnosti

1 b= b= b= b=

0.9

1 2 1 5

k k k k

= = = =

2 1 5 2

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

5


10


15

x

Antonín Kavička

f(x)

Weibullovo rozdělení - hustota pravděpodobnosti

1.4

1.2

1

0.8

0.6

0.4

0.2

0

0

0.5

1

F(x)

1.5

2

2.5

3

3.5

4

4.5

5

x

4

4.5

5

x

Weibullovo rozdělení - distribuční funkce

1.2

1

0.8

0.6

0.4

0.2

0

0

0.5

1

1.5

2


2.5

3

3.5


Antonín Kavička

f(x)

Weibullovo rozdělení - hustota pravděpodobnosti

5 a=1 a=1 a=5

4.5

b = 0,5 b = 1,2 b=5

4

3.5

3

2.5

2

1.5

1

0.5

0

0

0.5

1

1.5

2


2.5

3

3.5

4

4.5


5

x

Antonín Kavička

f(x)

Logaritmicko-normální rozdělení - hustota pravděpodobnosti

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

F(x)

5

10

15

x

15

x

Logaritmicko-normální rozdělení - distribuční funkce

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

5


10


Antonín Kavička

f(x)

Logaritmicko-normální rozdělení - hustota pravděpodobnosti

1.4

µ=0 σ=1 µ = 2 σ = 0,5 µ=2 σ=3

1.2

1

0.8

0.6

0.4

0.2

0

0

5


10


15

x

Antonín Kavička

P(x)

Poissonovo rozdělení - rozdělení pravděpodobnosti

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

F(x)

5

10

15

x

15

x

Poissonovo rozdělení - distribuční funkce

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

5


10


Antonín Kavička

P(x)

Poissonovo rozdělení - rozdělení pravděpodobnosti

1

λ=2 λ=5 λ = 10

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

5


10


15

x

Antonín Kavička

10. Analýza výstupních dat simulačních pokusů Studijní cíl Výklad v tomto bloku se soustředí na shrnutí základních možností analýzy a zpracování výstupních dat simulačních experimentů. Cílem je prezentovat různé typy simulací podle charakteru podmínek ukončení simulačního pokusu a s tím související odlišné přístupy ke zpracování výstupních dat. 3 hodiny


V ST

UP 1 VÝST UP 1

2 VÝSTU P

VSTUP 2

SIMULÁTOR VÝS TU P 3

3 UP VST

VÝST UP 4

Výstupní stochastické procesy (náhodné realizace)

Vstupní umělé náhodné procesy (náhodné výběry )

V průběhu simulačního pokusu lze monitorovat měnící se stavy simulátoru, resp. hodnoty příslušných stavových proměnných/ukazatelů, které je možné postupně ukládat pro pozdější (post-simulační) zpracování. Takto uchovaná data je možné po skončení simulačních experimentů různými způsoby analyzovat a zpracovávat s cílem získat hodnoty relevantních statistických ukazatelů vypovídajících o charakteru zkoumaného systému, resp. objektu zkoumání. V dalším budeme předpokládat, že jsou simulátorem realizovány umělé náhodné procesy, tedy je uplatňován stochastický přístup.

Obr. 10.1 Grafická ilustrace vstupů a výstupů simulátoru

10.1 Výstupní stochastický proces Pro práci simulátoru v průběhu simulačního experimentu je charakteristické, že jsou postupně přijímána data ze vstupních umělých náhodných procesů, která KST/IMOSI – Modelování a simulace


Antonín Kavička

jsou následně zpracovávána podle vnitřní logiky simulátoru, přičemž lze z hlediska sledovaných typů výstupů monitorovat příslušné stavové proměnné, resp. lze sledovat výstupy entit do okolí simulátoru (obr. 10.1). Monitorováním měnících se hodnot vybraných stavových proměnných, resp. výstupů entit ze simulátoru získáváme jisté posloupnosti (výstupních) dat. Tyto posloupnosti lze uspořádat podle údaje/atributu o pořadí od počátku simulace, kdy byla příslušná data pořízena. Nechť Y1,Y2,... je výstupní stochastický proces z jednoho běhu simulačního programu (jedné replikace). Symbol Yj , j∈〈1,2, …〉 označuje náhodnou proměnnou, přičemž hodnota indexu j vyjadřuje pořadí sesnímání (pozorování) instance příslušné náhodné proměnné od začátku běhu simulačního programu. Uveďme příklady výstupních stochastických procesů. Instance/hodnoty náhodné proměnné Yj mohou vyjadřovat například: (i) produkci továrny v j-té hodině pracovní směny, (ii) délku fronty klientů před přepážkou v bance v okamžiku její j-té změny, (iii) výšku hladiny ropy v tankeru v čase j × τ (hodnota τ představuje velikost periody vzorkování), (iv) dobu pobytu j-tého zákazníka ve zkoumaném systému apod. V následující tabulce (tab. 10.1) jsou symbolicky zachyceny výstupy z n nezávislých replikací simulačního experimentu, přičemž v každé z replikací bylo uskutečněno m pozorování (sesnímání stavových proměnných). Symbol instance náhodné proměnné y ij i∈〈1,2, …, n〉, j∈〈1,2, …, m〉 vyjadřuje výsledek j-tého pozorování v rámci i-té replikace. Symbol instance náhodné proměnné uij i∈〈1,2, …, n〉, j∈〈1,2, …〉 vyjadřuje hodnotu j-tého vstupu v rámci i-té replikace. Pseudonáhodná čísla (vstupy)

Náhodné realizace (výstupy)

u11, u12, ... . . . un 1, un 2, ...

y11, y12, ..., y1m . . . . . . . . . . . . yn 1, yn 2, ..., yn m

Tab. 10.1 Ilustrace náhodných výstupů pro m pozorování v n replikacích Jednotlivá pozorování v jedné replikaci (řádku tabulky) nejsou nezávislá. Naproti tomu j-tá pozorování v rámci odlišných replikací (sloupec tabulky) jsou nezávislá. KST/IMOSI – Modelování a simulace


Antonín Kavička

Základním úkolem analýzy výstupních dat je na základě pozorování y ij i∈〈1,2, …, n〉, j∈〈1,2, …, m〉 odhadnout pravděpodobnostní rozdělení a parametry náhodných proměnných Y1, ... ,Ym. Odhad střední hodnoty E(Yj) náhodné proměnné Yj lze zjistit dle vztahu: n

y j (n) =

∑y

ij

i =1

n přechodové hustoty

E(Yj)

a=E(y)

× ×

yi2

×

yi 3

ustálený stav

×

yi4

×

yi5

×

y i6

Odhady středních hodnot náhodných proměnných

y i1

j 0

1

2

3

4

5

6

Diskrétní časové okamžiky (tj. jednotlivá pozorování )

Obr. 10.2 Stylizovaná grafická ilustrace konvergence daného výstupního stochastického procesu k ustálenému stavu

Přechodové a ustálené chování stochastického procesu Studujme výstupní stochastický proces Y1,Y2,… Přechodová rozdělení pravděpodobnosti výstupního procesu v diskrétních časových okamžicích j∈〈1,2,…〉 označujeme jako Fj , přičemž tato jsou podmíněna počátečními podmínkami (počátečním stavem) I0 : Fj (y / I0) = P(Yj ≤ y / I0) Ve všeobecnosti jsou Fj různá pro různá pozorování j a různé počáteční podmínky I0. I0 může například odrážet počet a stavy rozpracovanosti výrobků a stavy výrobních a obslužných zařízení ve zkoumaném výrobním provozu továrny. KST/IMOSI – Modelování a simulace


Antonín Kavička

Jestliže Fj(y/I0) → F(y) pro j → ∞ a všechna y a I0 , pak F(y) představuje ustálené pravděpodobnostní rozdělení výstupního procesu Y1,Y2,… Tedy F(y) nezávisí na počátečních podmínkách I0 , avšak rychlost konvergence Fj (y / I0) → F(y) na počátečních podmínkách závisí. Výše uvedené tedy teoreticky platí, pokud j konverguje k nekonečnu. V praxi však používáme jisté zjednodušení – pokud dosáhne j určitou hodnotu k, pak rozdělení Fk+1, Fk+2,... již považujeme za shodná (obr. 10.2).

Příklad systému hromadné obsluhy typu M/M/1 V systémech hromadné obsluhy (resp. systémech front) jsou zkoumány proudy zákazníků, kteří vstupují do systému s cílem realizace obsluhy prostřednictvím tzv. zdrojů, resp. linek obsluhy. Jakmile jsou příslušné obsluhy daného zákazníka dokončeny, zákazník opouští systém. Systém typu M/M/1 je charakterizován (i) jedinou linkou obsluhy, (ii) Poissonovským vstupním tokem zákazníků (tj. doby mezi příchody/příjezdy zákazníků mají exponenciální rozdělení) a (iii) charakterem dob obsluh zákazníků, jež se řídí exponenciálním rozdělením. V případě, že je linka obsluhy volná, je zákazníkova obsluha zahájena okamžitě po jeho příchodu do systému. V opačném případě se zákazník zařazuje do fronty na obsluhu, z níž přistupuje k lince obsluhy, jakmile na něj přijde řada (tedy v režimu FIFO). Pro zmíněný systém nabízí teorie hromadné obsluhy exaktní řešení pro výpočet jistých provozních charakteristik: Intenzita vstupního proudu: Intenzita obsluhy: Využití linky obsluhy: Průměrný počet zákazníků v systému: Průměrný pobyt zákazníka v systému: Průměrný pobyt zákazníka ve frontě:

λ [zákazn./jedn. času] µ [zákazn./jedn. času] ρ = (λ λ / µ) x 100 [%] L = λ/(µ µ - λ) [zákazníků] w = 1/(µ µ - λ) [čas. jednotek] wQ = λ/(µ µ(µ µ - λ)) [čas. jednotek]

Pro konkrétní vstupní data λ = 1 zákazník/min. µ = 10 / 9 zákazníků/min. získáme použitím výše zmíněného exaktního postupu následující výsledky: ρ = (λ λ / µ) x 100 = 90 % L = λ / (µ µ - λ) = 9 zákazníků w = 1 / (µ µ - λ) = 9 minut wQ= λ / (µ µ (µ µ - λ)) = 8,1 minuty Výše zmíněné provozní charakteristiky systému M/M/1 lze získat i alternativním postupem, tj. s využitím experimentální výzkumné metody počítačové simulace. Jako příklad uveďme výstupní stochastický proces KST/IMOSI – Modelování a simulace


Antonín Kavička

WQ1,WQ2,... , kde náhodná proměnná WQ j , j∈〈1,2,…〉 vyjadřuje dobu pobytu j-tého zákazníka ve frontě na linku obsluhy. Počáteční podmínky I0 vyjadřují počet zákazníků v systému na počátku zkoumání (simulace). Pomocí simulace tedy lze zjistit, zda platí: E(WQ j ) → E(W) = d, kde hodnota d představuje střední dobu pobytu zákazníka ve frontě. S pomocí simulačních experimentů prověřte, zda lze pro různé počáteční podmínky (stavy fronty) finálně dosáhnout stejné hodnoty střední doby pobytu zákazníka ve frontě. Nechť inicializační stavy fronty (počáteční podmínky) nabývají hodnot: 0, 2, 4, 6, 8, 10, 12,1 4, 16, 18 a 20 zákazníků.

10.2 Klasifikace simulace podle podmínek ukončení Simulaci lze klasifikovat podle podmínek ukončení. Z tohoto hlediska rozlišujeme tak zvanou: simulaci s ukončením simulaci bez ukončení, jejíž výstupní parametry mohou být: - ustálené - ustálené cyklické - neustálené (resp. odlišného charakteru než předešlé případy) Pro simulaci s ukončením platí, že existuje určitá událost U, která přirozeným způsobem ohraničuje délku každého běhu simulačního programu. Po výskytu události U již nejsou informace produkované simulátorem potřebné, resp. zajímavé, anebo je simulující systém „vyprázdněný“. V případě simulace s ukončením rovněž hrají důležitou roli počáteční podmínky. Uveďme několik příkladů simulací s ukončením. (i) Zkoumáme-li provoz klientského oddělení banky v rámci osmihodinové pracovní doby, potom můžeme ukončovací událost definovat buď jako okamžik ukončení pracovní doby anebo jako okamžik odchodu posledního zákazníka po ukončení pracovní doby. Počáteční podmínky I0 vyjadřují přirozenou situaci na začátku pracovní doby klientského oddělení banky, tj. v oddělení nejsou žádní zákazníci. (ii) Pro simulační studii zaměřenou na zkoumání realizovatelnosti výroby sta lokomotiv za určité časové období je přirozenou ukončovací událostí okamžik dokončení výroby sté lokomotivy. Počáteční podmínky I0 lze popsat jako prázdný výrobní systém před spuštěním výroby lokomotiv. (iii) Simulační zkoumání strategie týdenního doplňování továrního skladu v horizontu jednoho měsíce (s cílem plynule uspokojovat požadavky z výroby) definuje jako ukončovací událost uplynutí alespoň jednoho měsíce simulačního času. Počáteční podmínky I0 vyjadřují stav zásob ve skladu na počátku zkoumaného období. KST/IMOSI – Modelování a simulace


Antonín Kavička

Pro simulaci bez ukončení nelze jednoznačně specifikovat událost, která by určila konec běhu simulačního pokusu. Typickým očekáváním ohledně charakteru výstupů tohoto typu simulace je ustálenost pravděpodobnostních rozdělení pro většinu výstupních stochastických procesů: Y1,Y2,... ; Z1,Z2,... atd. Praktickým problém je, že charakteristiky originálu se mnohdy mohou měnit v čase, a tudíž zmíněná ustálená rozdělení nelze prokázat. Navzdory této skutečnosti často uplatňujeme abstrakci, která připouští časově se neměnící charakteristiky simulujícího systému. Jako příklad simulace bez ukončení uveďme zkoumání projektované výrobní linky továrny. Cílem zkoumání je zjištění hodinové produkce v potenciálně ustáleném stavu. Výrobní linka a další příslušné zdroje pracují 16 hodin denně 5 dní v týdnu bez přestávek, přičemž navazování směn je realizováno bez ztráty produkce. Z uvedeného vyplývá, že simulace může zanedbat volné pracovní dny. Má-li výstupní stochastický proces N1,N2,... (Nj je produkce továrny v j-té hodině) ustálené pravděpodobnostní rozdělení s odpovídající náhodnou proměnnou N, pak řešením může být odhad střední hodnoty a=E(N).

10.3 Poznámky k simulacím s ukončením U simulací s ukončením může hrát významnou roli vhodné nastavení počátečních podmínek, resp. počátečního stavu simulačního modelu. Hlavně u experimentů, jejichž doba simulace je relativně krátká, je vyhovující nastavení počátečního stavu důležité. Demonstrujme tento problém na příkladu. Chceme-li zkoumat provoz v klientském oddělení banky (zaměřený na sledování čekacích dob klientů na obsluhu) pouze v čase provozní špičky mezi 12.00 hod. a 13.00 hod., pak je nevhodné nastavení počátečního stavu tak, že se v bance nenacházejí žádní klienti. Nejčastěji se můžeme setkat se dvěma přístupy k řešení uvedeného problému: Simulaci zahájíme s prázdným systémem v časovém předstihu před provozní špičkou (např. v 9.00 hod. simulačního času). Do sledování zahrneme čekání pouze těch klientů, kteří přišli a ukončili čekání v intervalu 〈12.00 , 13.00〉. Tedy pro získání realistických počátečních podmínek byl aplikován tzv. náběh neboli zahřívací fáze simulace. Buď na základě zkušeností s porovnatelným systémem, nebo dle expertního posouzení odhadneme pravděpodobnost pi , že je v bance ve 12.00 hod. i klientů (i=1,2,…). Simulační experiment potom realizujeme od 12.00 hod. simulačního času. Počáteční počet klientů vygenerujeme na základě odhadu { pi | i=1,2,…,k,k+1 }. Odhad pk+1 můžeme interpretovat jako pravděpodobnost, že je v bance ve 12.00 hod. více než k klientů. KST/IMOSI – Modelování a simulace


Antonín Kavička

Typické statistické zpracování výstupů ze simulace s ukončením vyžaduje provedení n nezávislých běhů/replikací simulačního experimentu se stejnými počátečními podmínkami a různými proudy (resp. násadami generátorů) pseudonáhodných čísel. Nechť X i je náhodná proměnná spojená s i-tým během - X i například odpovídá střední době čekání klienta v bance v i-tém běhu: m

Xi =

∑T j =1

j

m

kde m je celkový počet klientů, kteří prošli systémem a Tj představuje dobu čekání j-tého klienta. Odhad střední hodnoty doby čekání klienta získaný z n replikací potom vyjádříme jako: n

X (n) =

∑X i =1

i

n

příslušná směrodatná odchylka je:

1 n sx = ∑  X i − X (n)  n − 1 i =1 

2

a interval spolehlivosti:

X ( n) ±

sx t α n 1− 2 ; n −1

který platí pro normální rozdělení X i - pro ostatní rozdělení platí pouze přibližně, přičemž lze použít přesnější metody. Počet replikací

Využití linky obsluhy [%]

. . 4

. .

8 16 . .

80,8 ± 9,4 81,1 ± 6,8 81,3 ± 3,2 . .

Tab. 10.2 Ukázka zvyšování přesnosti (snižování šířky intervalu spolehlivosti) vybraného výsledku simulace se zvyšujícím se počtem replikací KST/IMOSI – Modelování a simulace


Antonín Kavička

Doporučení potřebného počtu replikací je závislé od požadované přesnosti sledovaných typů výsledků - nikdy se však nedoporučuje provádět méně než 3 - 5 replikací ! Jako příklad můžeme uvést sledování ukazatele míry využití linky obsluhy (obslužného zdroje) v rámci studovaného systému, přičemž je aplikována simulace s ukončením. Se zvyšujícím se počtem replikací dosahujeme vyšší přesnosti výsledku spojeného se zmíněným ukazatelem (tab. 10.2). Uplatnění intervalu spolehlivosti při statistickém vyhodnocování výstupů simulačních experimentů je rovněž podrobně ilustrováno v rámci výkladu v osmém bloku této opory.

10.4 Poznámky ke zpracování výstupů simulací bez ukončení Jak již bylo výše naznačeno, pro simulaci bez ukončení obvykle očekáváme ustálená pravděpodobnostní rozdělení (resp. ustálené výstupní parametry) pro většinu výstupních stochastických procesů. Praktickým problémem tedy je nalézt pro výstupní stochastický proces Y1,Y2,… takové hraniční k, že pro Yk+1,Yk+2,… je již příslušné pravděpodobnostní rozdělení ustálené. To znamená, že při statistickém zpracovávání výstupů ze simulace nejsou pozorování Y1,...,Yk pro odhad výstupních parametrů zohledňována. Odhad je proveden na základě Yk+1, resp. Yk+1,Yk+2,…, Ym ., což lze vyjádřit například takto: m

Y (m, k ) =

∑Y

j = k +1

j

m−k

Úvodní část simulace, jejíž pozorování nejsou při statistickém vyhodnocování výstupů zohledňována, je nazývána jako náběh, resp. zahřívání simulujícího systému za účelem eliminace přechodových stavů. Pro volbu hraniční hodnoty k (doby náběhu) lze aplikovat například Welchovu metodu využívající počítání klouzavých průměrů pro různě definovaná pozorovací okna. Výsledkem jsou různá vyhlazení původní křivky proložené „body“, které vyjadřují odhady středních hodnot E(Yj), kde j=1,2,...,k,k+1,...,m představují diskrétní časové okamžiky. Vybrané k představuje „počátek ploché křivky“. V praxi je možné se rovněž setkat s tzv. ustálenými výstupními cyklickými parametry. Zjistíme-li, že Y1,Y2,... pro simulaci bez ukončení nemá ustálené KST/IMOSI – Modelování a simulace


Antonín Kavička

pravděpodobností rozdělení, můžeme se pokusit zjistit, zda nejsou výstupy ze simulace zatíženy jistým cyklickým chováním simulujícího sytému. Na základě znalosti zkoumaného systému je možné se pokusit rozdělit simulační čas na intervaly zvané cykly (odpovídající například pracovním směnám). Nechť CYj je náhodná proměnná definovaná na j-tém cyklu. Předpokládejme, že proces C Y1,CY2,... má ustálené rozdělení CF s odpovídající náhodnou proměnnou CY. Potom mírou chování jsou ustálené cyklické výstupní parametry jako charakteristiky CY, například odhad střední hodnoty Ca = E(CY). Jako příklad můžeme uvést výrobní provoz továrny s osmihodinovými pracovními směnami, přičemž v polovině každé směny je půlhodinová přestávka s případným výběhem a náběhem. Stochastický proces hodinových produkcí N1,N2,... nemá ustálené rozdělení. Proces osmihodinových (středních) produkcí 8N1,8N2,... může mít ustálená rozdělení a nás může zajímat odhad střední hodnoty 8a = E(8N), tj. ustálený cyklický parametr.

Otázky k procvičení 1. Jak lze charakterizovat výstupní stochastický proces? 2. Jaké typy simulací rozlišujeme podle podmínek ukončení simulačního pokusu? 3. Jak lze charakterizovat náběh neboli zahřívací fázi simulace? 4. Jakým způsobem lze objektivizovat určení dostatečného počtu replikací simulačního experimentu? 5. Jaké důsledky mohou mít odlišné počáteční podmínky (resp. počáteční stav) simulujícího systému před zahájením simulačního pokusu?



Antonín Kavička

11. Kombinovaná simulace – synchronizace výpočtu Studijní cíl Cílem výkladu v tomto bloku je vysvětlení koncepce kombinované diskrétněspojité simulace a přiblížení jedné z možných technik synchronizace simulačního výpočtu. 3 hodiny


Jsou-li budovány simulační modely, jejichž aktivity jsou specifikovány jak způsobem charakteristickým pro diskrétní simulaci (pomocí událostí), tak pro spojitou simulaci (např. pomocí soustavy diferenciálních rovnic), potom je nutné disponovat simulačním jádrem schopným řídit, resp. synchronizovat simulační výpočet kombinované diskrétně-spojité simulace.

11.1 Výchozí předpoklady Simulační jádro, určené k řízení kombinované simulace, může být například složeno ze dvou základních částí/modulů: jádra diskrétní simulace a jádra spojité simulace, jejichž činnost je nutné vhodným způsobem synchronizovat. Možné způsoby algoritmizace jádra diskrétní simulace byly již popsány v předešlých částech opory, a proto se nyní zaměříme na zbývající moduly kombinovaného simulátoru. Základním úkolem jádra spojité simulace je zabezpečit a synchronizovat činnost všech paralelně v čase běžících spojitých aktivit (tj. takových aktivit, jejichž popis umožňuje sledovat hodnoty příslušných atributů v libovolném okamžiku simulačního času). Za tímto účelem je možné použít metodu snímání aktivit. Zvolenou snímací periodu, se kterou pracuje jádro spojité simulace, značíme jako τC. Připomeňme, že pro spojité aktivity zpravidla platí, že v okamžiku jejich startu nejsme schopni jednoznačně určit čas jejich ukončení. Proto je nutné při každém snímání takové aktivity testovat, zda hodnoty příslušných atributů dosáhly v daném simulačním čase jistých požadovaných (prahových) hodnot, které indikují ukončení aktivity. KST/IMOSI – Modelování a simulace


Antonín Kavička

Uživatel simulačního modelu často požaduje, aby mohl průběh vykonávání aktivit (bez ohledu na to, zda mají spojitý či diskrétní charakter) plynule sledovat na obrazovce počítače (např. v čase se měnící polohu mobilního objektu apod.). Zaveďme dále pro potřeby dalšího výkladu kategorizaci procesů podle charakteru popisu a zpracování jednotlivých aktivit v průběhu výpočtu. Diskrétní proces obsahuje výhradně diskrétní aktivity. Zpracovává je tedy tak, že v okamžiku jejich zahájení je naplánován jejich konec na určitý okamžik simulačního času, v němž dojde k provedení všech stavových změn, které jsou důsledkem jejich činnosti. Spojitý proces obsahuje výhradně spojité aktivity, přičemž je ošetřuje pomocí metody snímání aktivit. Kombinovaný proces obsahuje diskrétní i spojité aktivity a každou z nich zpracuje příslušnou metodou. Pozn.: Pro potřeby dalšího výkladu budeme předpokládat, že základní akční jednotkou simulace je autonomní proces (chápaný jako sériová sekvence aktivit), který nelze po jeho spuštění zásahem „zvenčí“ ani pasivovat ani předčasně ukončit – na rozdíl od filosofie klasické metody interakce procesů. Elementárním procesem nazýváme proces složený pouze z jedné aktivity. Dále budeme předpokládat, že jádro diskrétní simulace provádí synchronizaci simulačního výpočtu na základě uplatňování metody plánování událostí.

11.2 Struktura kombinovaného simulátoru Při navrhování architektury kombinovaného simulátoru je tedy nutné vytvořit takovou strukturu, která by umožňovala provádět synchronizaci diskrétní a spojité simulace. Strukturu kombinovaného simulátoru lze rozdělit do modulů (obr. 11.1). Jedná se o modul diskrétní simulace a modul spojité simulace, jejichž posláním je technicky zabezpečovat vykonávání aktivit diskrétního, resp. spojitého charakteru.

11.3 Synchronizace simulačních modulů Je nutno zdůraznit, že ústředním synchronizačním modulem popisovaného kombinovaného simulátoru je modul diskrétní simulace. To znamená, že tento KST/IMOSI – Modelování a simulace


Antonín Kavička

modul, (resp. jádro diskrétní simulace) v určitých situacích odevzdává řízení simulátoru ostatním modulům pro definované úseky simulačního času, po jejichž uplynutí si řízení bere nazpět.

Modul spojité simulace Registrované spojité aktivity

Modul diskrétní simulace Naplánování události

Kalendář událostí (časová osa)

Jádro spojité simulace


Registrace aktivity



Pokyn zpracovat další událost Zpracování dokončeno

Změny stavu simulátoru

Jádro diskrétní simulace


Obr. 11.1 Modulární struktura řízení kombinované simulace

a) Zahájení každého procesu je spojeno s výskytem události typu Start a jejím následným zpracováním. Při zpracování této události je zahájena první aktivita procesu. Pro libovolnou aktivitu procesu (lhostejno, zda má diskrétní či spojitý charakter) platí, že její ukončení se projeví jako výskyt události typu Konec, při jejímž zpracování dojde k zahájení následující aktivity procesu (pouze v případě, že se nejednalo o ukončení poslední aktivity procesu). Nyní poukážeme na rozdílné ošetření diskrétních a spojitých aktivit. b) Zahájení diskrétní aktivity (uskutečněné buď při zpracování Konec-události signalizující ukončení předchozí aktivity procesu anebo při zpracování Start-události, jedná-li se o první aktivitu procesu) chápeme jako naplánování okamžiku jejího budoucího ukončení, neboli vložení Konecudálosti do kalendáře událostí. Časovému trvání této aktivity odpovídá časový interval mezi okamžikem naplánování a okamžikem výskytu této události, kdy jsou provedeny všechny stavové změny, které jsou důsledkem činnosti této aktivity. c) Zahájení spojité aktivity je chápáno jako její registrace u modulu spojitého simulátoru. V intervalech simulačního času, v nichž je aktivní spojitý simulátor, se tento postará o běh této aktivity, která své ukončení ohlásí prostřednictvím naplánování příslušné Konec-události do kalendáře událostí modulu diskrétní simulace. KST/IMOSI – Modelování a simulace


Antonín Kavička

Nyní si vysvětleme mechanismus aktivace simulačního jádra spojité simulace. Simulační jádro diskrétní simulace pracuje tak, že vyjme z kalendáře událost s nejmenším časovým razítkem a následně iniciuje její zpracování, přičemž tento cyklus se neustále opakuje. Při kombinované simulaci má jádro diskrétní simulace tu vlastnost, že dokáže ještě před výběrem události z kalendáře identifikovat časový interval (Δt1) mezi posledním výběrem z kalendáře (v čase tD) a výběrem, který bude následovat (v čase tV). Je-li tento časový interval Δt1 = 0, pak pokračuje jádro diskrétní simulace ve své práci způsobem, jak již bylo výše popsáno. V případě, že je Δt1 ≠ 0, potom je tento časový interval přidělen simulačnímu jádru spojité simulace, čímž se odevzdá řízení kombinované simulace modulu spojité simulace. Po vyčerpání časového intervalu Δt1 se vrátí řízení kombinované simulace zpět jádru diskrétní simulace, které vybere z kalendáře další událost a pokračuje ve svém cyklu. Je tedy možné konstatovat, že spojitá simulace probíhá v těch intervalech simulačního času, v nichž se v rámci diskrétní simulace „nic neděje“.

Modul spojité simulace Registrované spojité aktivity

Jádro spojité simulace τC

Modul diskrétní simulace Δt1

Kalendář událostí

tE

tD

tV

Δt1 Δt2


Obr. 11.2 Ilustrace synchronizace simulačních modulů

11.4 Modul spojité simulace Modul spojité simulace je zodpovědný za simulaci spojitých aktivit procesů. Proto, aby bylo možno tyto aktivity začít simulovat, je nutné, aby je proces nejdříve zaregistroval u modulu spojité simulace. Samotná registrace probíhá KST/IMOSI – Modelování a simulace


Antonín Kavička

tak, že modul spojité simulace, na požadavek procesu o registraci konkrétní aktivity, tuto zanese do své evidence právě běžících spojitých aktivit. Registrace jsou iniciovány z diskrétní části modelu a to konkrétně při zpracovávání události. Všechny zaregistrované aktivity (od každého procesu může být vždy současně registrována pouze jedna aktivita) jsou potom v jádru spojité simulace ošetřovány metodou snímání aktivit v těch intervalech simulačního času, kdy je jádro spojité simulace aktivní. Jádro spojité simulace je aktivováno výše uvedeným způsobem v daném aktuálním simulačním čase tD. Přidělený časový interval Δt1 může být jádrem spojité simulace zcela využit pouze v případě, že v průběhu jeho práce nedošlo k naplánování události (do kalendáře) s časovým razítkem tE

Antonín Kavička

Vždy na závěr 2. fáze metody snímání aktivit (běžící v rámci jádra spojité simulace) se testuje, zda má být činnost jádra spojité simulace přerušena. Podmínkou přerušení je, že využitelný časový interval Δt2 byl vyčerpán (tj. tC - tD=Δt2). V případě, že podmínka přerušení není splněna, pokračuje snímací metoda dále ve své činnosti, v opačném případě je vráceno řízení simulačního výpočtu jádru diskrétní simulace.

Otázky k procvičení 1. 2. 3. 4.

Jak lze charakterizovat kombinovanou diskrétně-spojitou simulaci? Jak lze dekomponovat jádro kombinované diskrétně-spojité simulace? V jakém intervalu simulačního času může pracovat spojitá simulace? Za jakých podmínek nelze zcela vyčerpat časový interval, který byl přidělen spojité simulaci? 5. Jakým způsobem může jádro spojité simulace aktivně předávat informace jádru diskrétní simulace?



Antonín Kavička

12. Kombinovaná simulace – podpora animace Studijní cíl V rámci tohoto bloku je dále rozpracována problematika kombinované simulace s cílem prezentovat jeden z možných přístupů zahrnujících on-line animaci.


3 hodiny

Jak již bylo uvedeno v předešlém bloku, modulární architektura jádra kombinované simulace umožňuje efektivní dekompozici systémového řízení simulačního výpočtu na část zaměřenou na snímání spojitých aktivit a část ošetřující diskrétní aktivity. Pozornost byla rovněž věnována technice vzájemné sychronizace spojité a diskrétní simulace. Je-li potřeba při simulaci využívat tzv. on-line animaci, tj. animaci která je prováděna v průběhu simulace, potom je nutné modulární stavbu jádra kombinované simulace rozšířit o další moduly, jakož i upravit postup synchronizace simulačního výpočtu.

12.1 Modul rozhraní Modul rozhraní (obr. 12.1 - 12.2) tvoří předěl mezi simulačním modelem a jeho animačními výstupy na obrazovku. V tomto modulu existuje vyrovnávací paměť, která je naplňována informacemi od aktivit procesů, a to jak od aktivit diskrétních, tak spojitých. Aktivity, u nichž požadujeme animaci, ukládají chronologicky v čase do vyrovnávací paměti údaje, které obsahují informace potřebné pro grafické zobrazování. Vyrovnávací paměť je využívána jádrem animace (z modulu animace, jak bude níže uvedeno), které z ní průběžně čerpá informace potřebné pro animaci.

12.2 Modul animace Úkolem modulu animace (obr. 12.1 - 12.2) je vykonáváním registrovaných animačních aktivit prezentovat průběh simulačního výpočtu, resp. jeho jednotlivých procesů na obrazovce. Jádro animace může, podobně jako jádro spojité simulace, využívat metodu snímání (animačních) aktivit, přičemž po KST/IMOSI – Modelování a simulace


Antonín Kavička

uplynutí každé animační snímací periody τA dochází k aktualizaci grafického znázornění, které odráží aktuální průběh příslušné běžící aktivity simulátoru. Modul spojité simulace Registrované spojité aktivity

Modul diskrétní simulace Naplánování události

Kalendář událostí (časová osa)



Registrace aktivity



Pokyn zpracovat další událost Zpracování dokončeno

Zápis


Modul animace

Jádro animace

Modul rozhraní Vyrovnávací paměť


Zápis


Registrace animační aktivity

Animace

Registrované animační aktivity

Obr. 12.1 Obohacení architektury o moduly rozhraní a animace Pod pojmem animační aktivita, chápeme programovou rutinu (proceduru), která provádí animační zobrazování daného objektu na obrazovce. Modul animace obsahuje jednak jádro animace, které řídí animaci, a jednak registrované animační aktivity, které postupně vykonávají dílčí animační úkony s animovanými objekty. Podobně jako u modulu spojité simulace, i u modulu animace musí dojít k jeho aktivaci ze simulačního jádra diskrétní simulace. Tedy v případě, že spustíme simulační běh s nastavenou volbou požadující animaci, potom vypadá cyklus práce jádra diskrétní simulace následovně. Nechť pro daný aktuální simulační čas diskrétní simulace (tD) jsou již zpracovány všechny události, které se v tomto čase vyskytly. Je-li časový interval Δt1 (odpovídající časovému intervalu mezi aktuálním simulačním časem tD a hodnotou nejmenšího časového razítka tV ze všech událostí aktuálně obsažených v kalendáři) nulový, tj. Δt1=tV-tD=0, pak pokračuje jádro diskrétní simulace ve své obvyklé činnosti. V případě, že Δt1 ≠ 0, pak je tento interval Δt1 přidělen modulu spojité simulace. Poté probíhá spojitá simulace, po jejímž ukončení se předá řízení zpět jádru diskrétní simulace, které opět KST/IMOSI – Modelování a simulace


Antonín Kavička

zjišťuje velikost časového intervalu (Δt2) mezi aktuálním časem diskrétní simulace (tD) a aktuální hodnotou nejmenšího časového razítka (tE) ze všech událostí aktuálně naplánovaných v kalendáři. Za této situace je tedy Δt2=tE-tD. Modul spojité simulace Registrované spojité aktivity

Jádro spojité simulace τC

Modul diskrétní simulace Δt1

Kalendář událostí

tD

tE

tV

Δt1

Modul animace

Δt2 Jádro diskrétní simulace

Δt2 Jádro animace τA Registrované animační aktivity

Obr. 12.2 Ilustrace modifikované synchronizace simulačního výpočtu V případě, že spojitá simulace zcela vyčerpala původně přidělený časový interval Δt1 (to znamená, že v jejím průběhu nedošlo k plánování žádné události s časovým razítkem tE < tD+Δt1), pak Δt2=Δt1 a tE ≡ tV. V opačném případě je Δt2=Δt1–(tV – tE). V tomto okamžiku jsou všechny děje (části aktivit) probíhající v časovém intervalu 〈tD,tE) již odsimulovány a ve vyrovnávací paměti modulu rozhraní jsou příslušné údaje určené pro jejich animaci, které tam byly uloženy diskrétními i spojitými aktivitami v tomto časovém intervalu. Zjištěný časový interval Δt2 je přidělen modulu animace a řízení simulačního modelu je předáno jádru animace, které bude provádět animaci „ex-post“ pro interval simulačního času 〈tD,tE). Jádro animace si nejdříve vybere z vyrovnávací paměti modulu rozhraní všechny informace, které jsou určeny pro animaci. KST/IMOSI – Modelování a simulace


Antonín Kavička

KROK

Vykonává


Činnost Inicializace simulačního času diskrétní simulace tD (tD = 0) Zjištění stavu kalendáře nK ≤ 0 - prázdný, >0 - neprázdný)

0 1 Jádro diskrétní simulace

2

3 4

5


6


7 Jádro animace 8

9

10

11


Platí (nK = 0) nebo je vyčerpán čas pro běh simulačního programu.

Ukončení simulace

Vydání pokynu k výběru události z vrcholu kalendáře a k jejímu okamžitému zpracování Zjištění časového intervalu Δt1 Aplikace metody snímání C Δt1 ≠ 0 a počet aktivit se snímací periodou τ zaregistrovaných na všechny zaregistrované spojité aktivity až do výskytu spojitých aktivit nC ≠ 0 přerušení Zjištění časového intervalu Δt2 Provedení registrace animačních aktivit na základě údajů z vyrovnávací paměti Aplikace metody snímání animačních aktivit se snímací A periodou τ až do vyčerpání svého časového intervalu Δt2 Vydání pokynu k vyprázdnění vyrovnávací paměti Aktualizuje simulačního času diskrétní simulace tD = tV , kde tV je hodnota nejmenšího časového razítka ze všech událostí aktuálně obsažených v kalendáři Návrat na KROK 1

Δt2 ≠ 0 Δt2 ≠ 0 a počet zaregistrovaných animačních aktivit nA≠0 Vyrovnávací paměť je neprázdná

nK > 0

Tab. 12.1 Algoritmus výpočtu kombinované simulace včetně animace

Údaje ve vyrovnávací paměti určené pro modul animace se skládají z názvu animační aktivity, kterou bude třeba vykonat a z údaje o intervalu simulačního času, který má tato animační aktivita trvat (popř. z dalších přídavných údajů). Ještě připomeňme, že požadavek na vykonání animační aktivity mohl být do vyrovnávací paměti uložen libovolnou aktivitou (diskrétní či spojité povahy) KST/IMOSI – Modelování a simulace


Antonín Kavička

některého z právě probíhajících procesů. Výběrem všech informací o požadovaných animačních aktivitách je každá z nich u modulu animace zaregistrována (vzata do evidence právě probíhajících animačních aktivit). Jádro animace potom, podobně jako jádro spojité simulace, využívá metodu snímání aktivit se zadanou snímací periodou τA. Ve vyhodnocovací fázi této metody je každou ze zaregistrovaných animačních aktivit proveden odpovídající dílčí animační úkon. V případě, že je v daném intervalu některá z animačních aktivit ukončena, jádro animace jí automaticky zruší registraci. Po úplném vyčerpání časového intervalu Δt2 je práce jádra animace přerušena a řízení se odevzdá zpět jádru diskrétní simulace. V tomto okamžiku je možné, aby jádro diskrétní simulace vyslalo pokyn k vyprázdnění vyrovnávací paměti modulu rozhraní. Po tomto úkonu pokračuje jádro diskrétní simulace ve svém obvyklém pracovním cyklu. Pro kombinovanou simulaci, při níž je požadovaná animace, je její řídicí algoritmus souhrnně popsán v tabulce 12.1.

12.3 Závěrečné poznámky Využívání on-line animace je nezbytné pro simulátory uplatňující tzv. vizuální interaktivní simulaci, tj. simulaci umožňující experimentátorovi přepínání mezi automatickým a interaktivním režimem simulačního výpočtu. Interaktivní režim může například sloužit pro navrhování alternativních řešení problémů identifikovaných v průběhu simulačního výpočtu samotným experimentátorem a nikoliv pouze předdefinovaným automatickým algoritmem. On-line animace je pro uplatnění interaktivního režimu zcela nezbytná, neboť je nutné, aby měl experimentátor (pro potřeby rozhodování) k dispozici vždy aktuální grafický odraz stavového prostoru simulátoru na obrazovce počítače. Komentujme situaci, kdy požadavek na animaci vzešel od diskrétní aktivity. V tomto případě je nutné, aby údaje o této aktivitě, resp. její animaci byly uloženy do vyrovnávací paměti již v okamžiku jejího zahájení – nestačí tedy, aby se tato aktivita „pouze projevila“ v okamžiku svého ukončení (tak jak je to typické pro diskrétní simulaci), kdy jsou uskutečněny stavové změny v simulátoru jakožto důsledky proběhlé aktivity. V této souvislosti ještě poznamenejme, že zmíněná diskrétní aktivita je pro potřeby animace snímána s periodou τA, a tudíž její animační zpracování technicky připomíná ošetřování spojitých aktivit. Principiální rozdíl však spočívá v tom, že spojité aktivity jsou ošetřovány metodou periodického snímání proto, že není v okamžiku jejich zahájení znám čas jejich ukončení a po každé periodě je testováno, zda KST/IMOSI – Modelování a simulace


Antonín Kavička

nenastaly ukončovací podmínky. Naproti tomu periodické animační snímání se aplikuje z toho důvodu, aby bylo na obrazovce počítače možno po uplynutí každé animační periody sledovat grafickou změnu vážící se k animovanému objektu spojenému s příslušnou aktivitou.

Otázky k procvičení 1. Jak lze charakterizovat on-line animaci? 2. Jakým způsobem lze zabezpečit korektní synchronizaci kombinované simulace s on-line animací? 3. Jak lze charakterizovat vizuální interaktivní simulaci? 4. Pro jaké účely lze využívat interaktivní režim v průběhu evoluce simulačního výpočtu? 5. Jaká je technika animace diskrétní aktivity?



Antonín Kavička

13. Úvod do Petriho sítí Studijní cíl Závěrečný blok se věnuje úvodu do problematiky Petriho sítí, které rozšiřují modelovací možnosti stavových automatů, s cílem představit formalismus využitelný pro modelování dynamiky systémů.


3 hodiny

13.1 Úvodní motivační příklad Na úvod uvedeme prvotní motivační příklad, na němž budeme dále vysvětlovat elementární principy základního typu Petriho sítě.

Příklad aplikace Petriho sítě Předkládaný příklad se zabývá modelem přípravy automobilového závodu před startem (obr. 13.1). Pro jednoduchost jsou uvažováni pouze dva účastníci závodu, kteří disponují auty A a B. Závod je startován pracovníkem závodiště startérem (S). Závodníci nejdříve přijedou svými auty na příslušná vyhrazená místa v rámci sektoru startu, kde musí svá vozidla podrobit krátké kontrole před startem prostřednictvím palubní diagnostiky. Když je kontrola provedena, závodníci fyzicky signalizují startérovi svoji připravenost ke startu. Jakmile startér zaregistruje připravenost všech závodníků, tak závod odstartuje. Poté se auta dávají do pohybu a začínají závodit. Model startu závodu (využívající formalismus tzv. P/T Petriho sítě) je graficky reprezentován na obrázku 13.1. Z grafické reprezentace je patrné, že model využívá orientovaný graf, jehož množina vrcholů sestává ze dvou disjunktních podmnožin zahrnujících vrcholy odlišných typů. Každá z hran má tu vlastnost, že je orientovaná a vždy spojuje dva vrcholy odlišného typu. Vrcholy graficky znázorněné pomocí kružnice nazýváme jako místa (places) a pomocí obdélníků přechody (transitions). Přechody jsou určeny k modelování akcí, zatímco místa slouží k uchovávání informací o stavu systému. V rámci statické infrastruktury je dále možné sledovat dynamické elementy - tzv. značky (tokens), které se mohou vyskytovat v místech sítě. Značky jsou graficky znázorňovány vyplněnými kruhovými objekty (na obrázku 13.1 jsou zobrazeny tři značky, jež se postupně vyskytují v místech p1, p2 a p3). KST/IMOSI – Modelování a simulace


Antonín Kavička

Auto A čeká na znamení ke startu

Auto A signalizuje připravenost na start

Auto A se připravuje na start

Auto A jede

p1

p2

t1 Auto A je připraveno na start

p4

Startér S dává znamení ke startu

Startér S čeká na připravenost aut

Auto B se připravuje na start

Auto A se dává do pohybu

p6

Auto B je připraveno na start

p10

t4

t2

Vydáno znamení ke startu Vydáno znamení ke startu

t3

p8

p5

p9 p11

p3

Startér S vydal znamení ke startu

p7

t5 Auto B jede

Auto B signalizuje připravenost na start

Auto B čeká na znamení ke startu

Auto B se dává do pohybu

p12

Obr. 13.1 Model startu závodu formalizovaný pomocí P/T Petriho sítě Dynamické chování (evoluce) sítě je založeno na postupně se měnících výskytech značek v rámci míst – každý z aktuálních výskytů lze zachytit v tzv. globálním stavovém vektoru. Uvedený vektor, aktuálně odrážející situaci z obrázku 13.1, můžeme stylizovaně zapsat jako: M0 = [p1=1, p2=0, p3=0, p4=0, p5=0, p6=1, p7=0, p8=0, p9=0, p10=1, p11=0, p12=0]

Provedení změny výskytů značek v místech lze provádět prostřednictvím provádění přechodů (někdy označovaným jako odpalování, resp. otevírání přechodů), které lze zjednodušeně popsat následovně. Přechod t může být proveden, jestliže se v každém z jeho vstupních míst (tj. všech míst grafu incidentních s hranami, které jsou do přechodu/vrcholu t zaústěny) vyskytuje alespoň jedna značka. Je-li tedy splněna podmínka provedení přechodu, je tento proveden, a to tak, že z každého jeho vstupního místa je odebrána jedna značka a do každého jeho výstupního místa (tj. místa grafu incidentního s hranou vycházející z přechodu/vrcholu t) je jedna značka přidána. Je-li podmínka proveditelnosti splněna pro více přechodů sítě současně, je náhodně vybrán jeden z těchto přechodů a je proveden. Posloupnost provádění přechodů tedy představuje evoluci sítě. Pro inicializační stav jsou proveditelné dva přechody/akce (t1, t4). Je-li k provedení vybrán přechod/akce t1 , pak auto A ukončí předstartovní přípravu (p1=0), dále již bude čekat na start (p2=1) a tuto skutečnost signalizuje znamením (p4=1). Změnu stavu sítě můžeme zapsat jako: M0 = [p1=1, p2=0, p3=0, p4=0, p5=0, p6=1, p7=0, p8=0, p9=0, p10=1, p11=0, p12=0] ↓ t1 (auto A signalizuje připravenost na start) __↓ ↓_______________________________________________________ ↓ ↓ ↓ M1 = [p1=0, p2=1, p3=0, p4=1, p5=0, p6=1, p7=0, p8=0, p9=0, p10=1, p11=0, p12=0]



Antonín Kavička

Uskutečněnou změnu stavu můžeme zachytit rovněž graficky (obr. 13.2). Z místa p1 byla jedna značka odebrána a do míst p2 a p4 bylo po jedné značce přidáno.

Auto A čeká na znamení ke startu

Auto A signalizuje připravenost na start Auto A se př ipravuje na start

Auto A jede

p1

p2

t1 Auto A je připraveno na start

p4

p6

Auto B je připraveno na start

p10

t4 Auto B signalizuje připravenost na start

p5

t2

p3

Startér S dává znamení ke start u Vydáno znamení ke startu

St artér S čeká na připravenost aut

Auto B se připravuje na start

Auto A se dává do pohybu

Vydán o znamení ke startu

t3

p8

p11

p9

Startér S vydal znamení ke startu

p7

t5 Auto B jede

Auto B se dává do pohybu

Auto B čeká na znamení ke startu

p12

Obr. 13.2 Grafické znázornění změny stavu sítě provedením přechodu t1 Uvedeným způsoben tedy můžeme sledovat evoluci sítě, která je pro náš příklad ukončena dosažením koncového/terminálního stavu: M7 = [p1=0, p2=0, p3=1, p4=0, p5=0, p6=0, p7=1, p8=0, p9=0, p10=0, p11=0, p12=1]

13.2 Základní charakteristiky Petriho sítí Po prvotním zjednodušeném přiblížení elementárních principů základního typu Petriho sítě přistoupíme k představení základních charakteristik Petriho sítí.

Princip duality Petriho sítí Petriho sítě disponují dvěma disjunktními množinami elementů: P-elementy (stavové elementy, místa) a T-elementy (přechodové elementy, přechody). Entity reálného světa, chápané jako pasivní elementy, jsou reprezentovány místy (podmínky, zdroje, fronty atd.). Naproti tomu entity, interpretované jako aktivní elementy, jsou reprezentovány pomocí přechodů (události, akce, vykonání příkazů, vysílání zpráv apod.).

Princip lokálnosti Petriho sítí Chování každého přechodu závisí výhradně na jeho okolí, jež je definováno jako souhrn jeho vstupních a výstupních míst (vstupní a výstupní podmínky). KST/IMOSI – Modelování a simulace


Antonín Kavička

Princip souběžnosti Petriho sítí Přechody, jejichž okolí jsou disjunktní, jsou prováděny nezávisle (souběžně, paralelně). Pozn.: Technicky jsou tyto „nezávislé“ přechody v případě jejich současné proveditelnosti prováděny sekvenčně – náhodně je vybrán jeden přechod (tj. evoluci sítě je možné obecně klasifikovat jako nedeterministickou) a je proveden. Následující zápis ukazuje konečný výsledek sekvenčního provedení (souběžně proveditelných) přechodů t1 a t4 v libovolném pořadí: M0 = [p1=1, p2=0, p3=0, p4=0, p5=0, p6=1, p7=0, p8=0, p9=0, p10=1, p11=0, p12=0] ↓ ↓ t1 (auto A signalizuje ...) (auto B signalizuje...) t4 __↓ ↓___________________________________________↓ ↓____________ ↓ ↓ ↓ ↓ ↓ ↓ M3 = [p1=0, p2=1, p3=0, p4=1, p5=0, p6=1, p7=0, p8=1, p9=0, p10=0, p11=1, p12=0]

Princip grafické reprezentace Petriho sítí P-elementy jsou reprezentovány kruhovými grafickými symboly a T-elementy obdélníkovými grafickými symboly. Hrany spojující každý T-element s jeho okolím se znázorňují pomocí úseček opatřených šipkou určující jejich orientaci. Navíc mohou být použity popisky, jako jsou identifikátory, značky apod.

Princip algebraické reprezentace Petriho sítí Ke každé grafické reprezentaci existuje algebraická reprezentace obsahující ekvivalentní informaci o množině míst, přechodů, hran a případně další přídavné informace (popisky).

13.3 Algebraický popis P/T Petriho sítě a její evoluce Zaveďme nyní algebraický popis P/T Petriho sítě a formalizaci pravidel její evoluce. Trojici PN = (P,T,F) nazýváme sítí, jestliže: a) P a T jsou disjunktní množiny a b) F ⊆ (P×T) ∪ (T×P). Množina P se nazývá množinou míst sítě PN, množina T množinou přechodů sítě PN a relace F tokovou relací sítě PN. Grafem sítě nazýváme bipartitní orientovaný graf, který vznikne grafovou reprezentací relace F. Množina P∪T je množinou vrcholů grafu sítě – místa jsou obvykle kreslena ve tvaru kružnic, přechody ve tvaru obdélníků. KST/IMOSI – Modelování a simulace


Antonín Kavička

Nechť pro síť PN = (P,T,F) dále platí: a)

∀ x ∈ (P ∪ T) x = {y | yFx} se nazývá vstupní množinou prvku x x• = {y | xFy} se nazývá výstupní množinou prvku x

•

Pro X ⊆ (P ∪ T) je • X = ∪•x a X• = ∪ x• x∈X x∈X Zřejmě pro každé x, y ∈ (P ∪ T) platí: x ∈ •y ⇔ y ∈ x• b) Uspořádaná dvojice ∈P×T se nazývá vlastní cyklus, jestliže pFt ∧ tFp. Neobsahuje-li PN vlastní cyklus, pak se nazývá čistou sítí. c) Prvek x ∈ (P ∪ T) se nazývá izolovaný, jestliže •x ∪ x• = ∅ Šestici PN = (P, T, F, W, K, M0) nazýváme P/T Petriho sítí, jestliže: a)

(P,T,F) je konečná síť,

b)

W: F → N \ {0} je ohodnocení hran grafu sítě určující váhu každé hrany,

c)

K: P → N ∪ {ω} je zobrazení specifikující kapacitu (i neomezenou) každého místa,

d)

M0: P → N ∪ {ω} je počáteční značení míst sítě respektující kapacity míst, tj. M0(p) ≤ K(p) pro všechna p∈P.

Evoluční pravidla Petriho sítě Pro Petriho síť PN = (P, T, F, W, K, M0) zaveďme zobrazení M : P → N ∪ {ω}, které nazveme značení Petriho sítě PN, jestliže pro všechna p∈P : M(p) ≤ K(p). a) Přechod t∈T je proveditelný (je otevřen) při značení M (stručněji Mproveditelný) jestliže: − pro každé p∈•t : M(p) ≥ W(p,t), − pro každé p∈t• : M(p) ≤ K(p) - W(t,p). b) Je-li přechod t∈T proveditelný při značení M, pak jeho provedením získáme následné značení M’ ke značení M, které je definováno takto: Pro všechna p∈P platí: M(p) - W(p,t) M(p) + W(t,p) M’(p) = M(p) - W(p,t) + W(t,p) M(p)

jestliže p∈ •t \ t• jestliže p∈ t• \ •t jestliže p∈ •t ∩ t• jinak

Provedení (otevření) přechodu t∈T ze značení M do značení M’ symbolicky zapisujeme: M [t > M’. KST/IMOSI – Modelování a simulace


Antonín Kavička

c) Označme symbolem [M > nejmenší množinu různých značení sítě PN takovou, že platí: − M∈[M >, − je-li M1∈[M > a pro nějaké t∈T platí M1 [t >M2, pak M2∈[M >. Množina [M > se nazývá množinou dosažitelných značení ze značení M. Množina [M0 > dosažitelných značení z počátečního značení M0 sítě se nazývá množina dosažitelných značení sítě PN.

Z výše uvedené formalizace pravidla evoluce Petriho sítě je patrné, že výklad evoluce podaný v rámci uvedeného prvotního motivačního příkladu, komentoval pouze speciální případ, kdy váhy všech hran byly jednotkové a kapacity všech míst neomezené. Zobecněné pravidlo evoluce pracuje se dvěma podmínkami, které musí být současně splněny, aby byl přechod t∈T proveditelný. První podmínkou je, že v každém prvku/místě ze vstupní množiny přechodu t se vyskytuje alespoň tolik značek, jaká je váha hrany spojující příslušné místo s přechodem t. Druhá podmínka stanovuje, že pro každý prvek/místo z výstupní množiny přechodu t musí platit, že nesmí být překročena jeho kapacita po potenciálním přidání nových značek, jejichž počet určuje váha příslušné výstupní hrany přechodu t.

p4

K(p5 )=2 3

p6

p14 3

1 4

2

t1

K(p 20 )=10 p7

p16

4

2

2

p8

2

t2

p9

p17

p19

Obr. 13.3 Ukázky neproveditelných přechodů pro aktuální značení

p4

p5 3

p6

4

2

t3

p8

p4

p5 3

1

p7

p6

2

1 4

2

t3

p9

p7

2

p8

p9

Obr. 13.4 Ukázka úspěšného provedení přechodu pro aktuální značení KST/IMOSI – Modelování a simulace


Antonín Kavička

Obr. 13.5 Grafická prezentace množiny dosažitelných značení Ilustrační obrázky 13.3 a 13.4 postupně demonstrují proveditelnost, resp. neproveditelnost odlišných přechodů (u neoznačených hran se předpokládá implicitní jednotková váha a u neoznačených míst implicitní neomezená KST/IMOSI – Modelování a simulace


Antonín Kavička

kapacita). Přechod t1 je neproveditelný, neboť jeho provedením by byla překročena kapacita místa p5 (ta je již pro aktuální značení zcela vyčerpána). Přechod t2 je neproveditelný, protože místo p14 nedisponuje vzhledem k váze hrany [p14,t2] dostatečným počtem značek. Kompletní množinu dosažitelných značení (resp. kompletní stavový prostor) pro síť uvedenou v prvním příkladu lze graficky prezentovat (obr. 13.5) .

13.4 Zobecnění motivačního příkladu Motivační příklad z úvodu tohoto bloku lze dále zobecnit, pokud životní cykly automobilů na startu závodu sdružíme a příslušným způsoben upravíme váhy relevantních hran (obr. 13.6). p2 p1

p3 t1

t2 p4 2

2

p5

p6

p7 t3

Obr. 13.6 Zobecněný model startu závodu Ilustraci evoluce zobecněného modelu lze vyjádřit zápisem: M0 = [2,0,0,0,0,1,0] ↓ t1 ↓ M1 = [1,1,0,1,0,1,0] ↓ t1 ↓ M2 = [0,2,0,2,0,1,0] ↓ t3 ↓ M3 = [0,2,0,0,2,0,1] ↓ t2 ↓ M4 = [0,1,1,0,1,0,1] ↓ t2 ↓ M5 = [0,0,2,0,0,0,1]



Antonín Kavička

13.6 Závěrečné poznámky Výhodou použití Petriho sítí je skutečnost, že je možné tyto analyzovat, resp. formálně verifikovat (problematika verifikace však přesahuje rámec této opory). Použití různých typů Petriho sítí (v oblasti modelování a simulace) umožňuje verifikovat příslušné (simulační) modely, což přispívá ke zvýšení bezpečnosti vyvíjených softwarových produktů. Blíže se problematice Petriho sítí (včetně příslušných aplikací) věnuje předmět Pokročilé techniky modelování a simulace v navazujícím magisterském studiu.

Otázky k procvičení 1. K čemu lze využívat formalismus Petriho sítí? 2. Jak lze v Petriho síti identifikovat stavové změny? 3. Jaká jsou pravidla evoluce (proveditelnosti přechodů) P/T Petriho sítě?



Antonín Kavička

1. Vymezení základních pojmů z oblasti modelování a simulace

Recommend Documents