Modelování hodnotového toku MHTOK, 3. Pravděpodobnost a algoritmy David Kruml 30.10. 2024 Nahodilost a pravděpodobnost Cvičení: Zkuste nematematikovi definovat náhodný jev a pravděpodobnost. řístupy k nahodilosti ► Stoický přístup: svět je deterministický, náhoda je jen nedostatek informací. ► Odfiltrování části informací může být záměrné. ► Filozofie často řeší jen nahodilost důsledků, nejistota se ale může týkat i příčin. ► Pravděpodobnost vyjadřuje míru očekávání, že se něco stane. (To se ale určitě stane, nebo určitě nestale — klasická logika.) ► L. Zadeh, nespokojenost s pojetím náhody a rigidností teorie pravděpodobnosti — fuzzy logika, víc „míra platnosti" než „míra jistoty". Přístupy k nahodilosti ► Klasická pravděpodobnost: poměr počtu příznivých instancí jevu k celkovému počtu. Musí se předpokládat konečnost, stejná váha, atp. ► Pokročilá pravděpodobnost: geometrická, abstraktně zadaná mírou, podmíněná, atd. ► Statistika — náhoda se týká sběru vzorku, řeší se oprávněnost závěrů. ► Frekventismus vs. bayesiánství. ■v ► Číselná parametrizace jevového prostoru — náhodná veličina, výzkum typových pravděpodobnostních rozdělení. Cvičení: Co je průměrná mzda a co mediánová mzda? Jak se určují? Co jsou zde náhodné jevy, veličiny, pravděpodobnost? Procesní pojetí náhody — příklad s náhodným výstupem deterministické procesy nedeterministický proces ► p lze chápat jako agregaci (deterministických) procesů pi,P2- ► Nahodilost výstupu = vznikla ztotožněním procesů při pokračujícím rozlišování zdrojů. Spor o ideje Platón Aristoteles P Pl P2 P3 >• Pl P2 •i P3 ► Platón: Instance jsou (nedokonalé) obrazy idejí. ► Aristoteles: Ideje jsou zobecnění instancí. ► Kopírování a specifikace vs. zobecňování a slučování. Agregace procesů a zdrojů ► Nahodilost je produktem agregace událostí. ► Agregace je dvojího typu: ► podle blízkosti (navazující nebo souběžné procesy, zboží pro stejnou zakázku), ► podle podobnosti. ► Rozdíl mezi typy lze zrelativizovat — i blízkost lze chápat jako druh podobnosti. ► Podobnost lze definovat různými hledisky, agregace pak může probíhat postupně a různými cestami. ► Místo rozpadové struktury je pak lepší uvažovat nestromová uspořádání. Příklad s kostkou Entropie I ► Entropie vyjadřuje míru nejistoty nebo neuspořádanosti. ► Příklad (1) A ... 80%, B ... 10%, C ... 10% — hodně věřím A, varianty 6, C jsou marginální. (2) A ... 40%, B ... 30%, C ... 30% — všechy tři varianty jsou docela podobně možné, nevím, čemu věřit. Situace (2) má větší entropii než (1). ► Morseova abeceda — četná písmena mají krátký kód a vysílaj se tak rychleji. U běžného textu dochází (oproti méně promyšlenému kódování) ke komprimační úspoře. ► Princip lze užít obecněji než na písmena a rozšířit na podřetězce atd., kódovat polyalfabeticky, atd. (jazyk „ptydepe" V. a I. Havlových). ► V teorii informace entropie vyjadřuje nepřekonatelnou minimální velikost kódu (velikost v „dokonalé morseovce"). Entropie II ► V příkladu (1) potřebujeme „méně než bit" na kódování A. Naproti tomu pro 6, C by bylo dobré volit 3-4 bity, protože 1/24 < 1/10 < 1/23. ► Entropie se počítá vzorcem E = -YJP; "ogz h, i kde základ logaritmu z vychází z typu aplikace (pravděpodobnost, informace, fyzika). ► Výpočet pro příklad (s logaritmem log2): Ei « 0.58, E2 « 1.25 Udává průměrnou spotřebu bitů na 1 znak. Entropie, závěry ► Entropie je velmi univerzální charakteristika nahodilosti současně velikosti informace. ► Nepotřebujeme jev transformovat na náhodnou veličinu. ► Může být vodítkem pro propojení datového skladu se statistickými nástroji. Typická rozdělení ve výrobě ► Alternativní rozdělení— dobrý výrobek/zmetek. ► Normální rozdělení— „přírodní" variabilita procesů (nebo materiálu) ► Exponenciální rozdělení— nehody a jiné katastrofy, událost se někdy stane, ale nevíme kdy. Jiné typ — méně závažné nehody jsou časté, závažnější se stávají řidčeji (černé labutě). ► Skládání efektů — obecnější rozdělení s pozitivní šikmostí, typicky unimodální (s jedním hrbem). ► Rozdělení vzniklá „prohozením os", např. Poissonovo. Cvičení: Připomeňte si pojmy hustota, distribuční funkce, kvantil. řipomenutí hustoty a distribuční funkce ► U spojitých veličin pravděpodobnost znázorňujeme hustotou. (Samotná bodová pravděpodobnost je nulová.) ► Distribuční funkce udává „celkový nárůst" pravděpodobnosti, vidíme z ní kvantity. ► Jedno z druhého dostaneme derivací/integrací. ► Interpretace distribuční funkce pro procesní čas: je-li v bodě x hodnota F(x) = p, očekáváme, že z N běhů procesu bude p/V rychlejších a (1 — p)N pomalejších. ► Jinými slovy, proces se stihne do času x se spolehlivostí p. ► Boxplot— pětibodová charakteristika, všechny tři kvartily a dva okrajové kvantily (např. 5%, 95%). Případy za okraji se pokládají za nepodstatné. Projev nahodilosti v časo hmotové m diagramu hmota 75% čas Typický průběh opakovaného náhodného procesu hmota 25% 50% 75% Komentáře k opakovanému náhodnému procesu ► Průběh lze modelovat metodou Monte Carlo — přičítání generovaných náhodných čísel pro dané rozdělení. ► Kvantily snadno vytěžíme ze vzorků (reálných dat nebo simulovaných): hodnoty seřadíme podle velikosti a podíváme se proporčně na p/c-tou hodnotu, kde k je počet běhů. ► Kvantil nemusí odpovídat žádnému běhu — na některém výrobku může jeden běh předběhnout jiný. Pro každé n potřebujeme samostatné řazení. ► Kvantily se nemohou „překroutit" — pro p < q bude průběh p-tého kvantilu rychlejší/menší než q-tého (porovnávání jako 2-morfismus). ► Průběh kvantilových „schodišť" lze aproximovat parabolickými křivkami — pro p < 1/2 konkávni, pro p > 1/2 konvexní. Brzy vysvětlíme. Výměna os ► Našim cílem je výpočet zásob v zásobníku v pravděpodobnostním prostředí. ► Připomeňme, že zásobník je souběžně napájen kladnými (vstupními) a zápornými (výstupními) signály a tyje třeba efektivně sečíst. ► Sčítáme hmotu (zásoby), nikoli čas. Nahodilost časovou potřebujeme převést na nahodilost hmotovou. Místo „kdy bude hotovo n kusů?" se ptáme „kolik vyrobíme do času ŕ?" ► Druhé z rozdělení je diskrétní (pokud je výroba diskrétní). Nicméně aproximace nahrazují schodiště spojitými křivkami a vedou tak ke spojitému popisu hmotové nahodilosti. ► Banální, ale důležité pozorování— rychlost výroby lze porovnávat dvěma ekvivalentními způsoby: ► stejný objem vyrobíme v kratším čase, ► za stejný čas vyrobíme více. ► V důsledku toho horizontální a vertikální náhodné veličiny „sdílí kvantily". Sdílení kvantilů Modelářovo dilema ► V matematickém modelování často stojíme před dilematem, zda volit model ► jednoduchý, ale nepřesný, ► nebo přesný, ale složitý. ► Ve druhém případě složitost může způsobit nepřesnost jiného typu. ► Příklad: Reálná výrobní dat velmi pečlivě „rozškatulkujeme", čímž dostaneme jemné členění na všechny myslitelné případy. Tím se ovšem zmenší vzorky a vzroste statistická chyba. Např. místo abych počítal všechny běhy procesu p, zaměřím se jen na běhy ve čtvrtek a v listopadu, protože dnes je čtvrtek a je listopad „a co kdyby to mělo nějaký vliv". ► S ohledem na kvalitu dat je na místě uvážit i zjednodušení kalkulu pro práci s náhodnými veličinami. Klasické sčítaní náhodných veličin ► Nechť X, Y jsou nezávislé spojité náhodné veličiny s hustotami f, g. Pak je hustota h veličiny X + Y dána konvolucí /oo f(x)g(z - x)dx. -oo ► Príklad s diskrétními rozděleními — hod dvěma kostkami: P(X + Y = 7) = P(X = 1)P{Y = 6)+ + P(X = 2)P(y = 5)+ + ••• + + P(x = 6)P(r = i). ► Spočítat integrál se často neumí, výsledkem součtu nemusí být „pěkné" pravděpodobnostní rozdělení. ► Rezignujme na přesnost a počítejme součet přibližně a jednodušeji. omenty náhodné veličiny ► střední hodnota E(X) — ve statistice a diskrétním rozdělení vážený průměr, u spojitých ► rr?2 je rozptyl. ► 1113/1712 je šikmost. ► Označme si střední hodnotu ji, rozptyl a2 a třetí centrální moment 7. Je-li je třeba rozlišit pro různé náhodné veličiny, napíšeme veličinu do indexu. ► n-tý centrální moment ► :a momentů /i, a2,7 Všechny tři sledované momenty jsou aditivní, tj. pro nezávislé náhodné veličiny X, Y máme: Tato vlastnost se bohužel pro momenty vyšších řádů pokazí, pokračovat lze s tzv. kumulanty (viz teorie momentových vytvořujících a charakteristických funkcí v teorii pravděpodobnosti). Pokud sčítáme n stejných nezávislých kopií téže veličiny X, označme výsledek n * X. Dostáváme: Mx+v 2 ax+v 7x+v fix + Vy 2 , 2 ax +cry- 7x + 7v- Mr?*X 2 °n*X 7n*X Vztahy mezi momenty a kvantily ► Pro normální (Gaussovo) rozdělení je známo, že kvantily jsou tvaru ji + ka pro vhodné k (/c < 0 pro p < 1/2 a /c> 0 pro p > 1/2, ji splývá s mediánem). ► Pro opakovaný proces máme ~ nax' a 0"n*x = ^fň&x- To je ono slibované vysvětlení parabolického vývoje kvantilů. ► Experimentálním pozorováním jsme také zjistili, že rozdíl střední hodnoty a mediánu se s n nemění. Rozdíl souvisí se šikmostí, což je v souladu s rovností 7n*X °n*X 7x na Pseudomomenty g s -^- QÍ/4 QÍ/2 m Qä/4 ► Zavedeme si náhrady za momenty m, s, g podle vzorců: Q1/4 + Q3/4 O3/4 - Q1/4 Q1/4 + Q3/4 ~ m =-2-' s =-2-' g =-2--/2' ► Tvařme se, že se chovají jako 7/a2, tj. položme / 2 , 2 Sxsx + ^4 V + Sy ► Pro iterovaný proces zřejmě dostaneme ™n*X = ^^X, Sn*x = V^5X? S"n*X = ŽX- Komentáře k pseudomomentům I ► Převod kvantilů na pseudomomenty je lineární, inverzní převod je dán vzorci: Q1/4 = m-s, Q3/4 = m + s, Q1/2 = m + g. ► Odvodili jsme zjednodušený „fuzzy" kalkulus pro sčítání náhodných veličin. ► Připomínáme předpoklady „rozumnosti" uvažovaných veličin ► Pro ně experimenty ukázaly překvapivě výborné výsledky (rozdíl v jednotkách procent vzhledem k a). ► Nepřekvapivě horší jsou výsledky na extrémně odlišných rozděleních, např. alternativních, tvar U. Problémy jsou i na okrajích kampaní. ► U opakovaných procesů rozdělení velmi rychle tíhne k normálnímu (centrální limitní věta). Kdybychom zanedbali šikmost, asi by se nic hrozného nestalo a v praxi se to běžně dělá. Komentáře k pseudomomentům II ► Metodu lze zobecnit a místo mediánu řešit obecný kvantil Qp (třeba pro požadovanou spolehlivost), myšlenka je pořád podobná. ► Připomínáme, že s,g se kromě principiální nepřesnosti od původních momentů liší i násobkem. ► Pro odhad m (náhražka za střední hodnotu ji) se v popisné statistice někdy používá přesnější odhad Q1/4 + 2Qi/2 + Q3/4 m = —----—. 4 Zatím jsme nevyužili. Nepřesnosti se transformacemi tam a zpět částečně vykompenzují. ► Transformují se 3 kvantily na 3 pseudomomenty a zpět. Co je vhodným protějškem pro pětibodovou charakteristiku? rategie výpočtu stavu zásobníku v čase t 1. Signály modelujeme trojicí kvartilů. 2. Pro čas t překlopíme osy, tj. zjistíme hodnoty kvartilů na hmotové ose. 3. Kvartily transformujeme na pseudomomenty. 4. Sečteme pseudomomenty. 5. Pseudomomenty transformujeme na kvartily a odhadneme z nich kvantil = spolehlivost zásobníku pro čas t. Lineární validace zásobníku ► Jak bylo dříve naznačeno, signály perfektních opakovaných procesů lze shora i zdola aproximovat lineární funkcí. ► Aproximace může být i víceúrovňová (heijunka). ► Z takto aproximovaných signálů odhadujeme i signál na zásobníku. ► Přitom je třeba: ► Rozdělit studovaný časový intervaly na úseky tak, aby na všech podintervalech byly všechny signály lineární, tj. hledáme společné zjemnění se všemi zlomovými body (událostmi). ► Horní odhad počítat jako součet horních aproximací. ► Dolní odhad počítat jako součet dolních aproximací. Lineární validace zásobníku ► Dále sledujeme zásoby ve zlomových bodech. Mohou nastat tyto situace: ► Dolní odhad přeteče horní mez — zásobník jistě přetéká. ► Horní odhad přeteče horní mez, ale dolní odhad ne — nevíme nic, musíme zpřesnit odhad další iterací. ► Horní odhad nepřeteče horní mez — zásobník jistě nepřetéká. ► Duálně řešíme situaci na dolní mezi. ► Na sousedním bodu dělení může nastat: ► stejná situace, pak se stejně chovají i všechny body uvnitř intervalu, ► jiná situace, pak dochází k protnutí některého nebo obou odhadů s přímkou mezní zásoby. ► Případné průsečíky určí nové dělení a další (přesnější) iteraci provádíme jen na podintervalech, kde neznáme odpověď. Lineární validace — komentáre ► Čím je výroba pravidelnější, tím víc aproximace šetří výpočetní čas. ► Iterace algoritmu (hlavní cyklus) by měla být navržena tak, aby přidávala (dříve přeskakované) události, a to jen ty nezbytné. ► Výsledkem algoritmu je rozčlenění studovaného intervalu na úseky, kde je zásobník funkční (v mezích) a kde selhává (mimo meze). ► V realitě selhání zásobníku může znamenat blokování nebo hladovění navazujících procesů. ► Průsečíky se počítají snadno, protože veškeré objekty jsou spojnice událostí, tedy úsečky. ► Přetečení a podtečení zásobníku je vhodné validovat samostatně, v souběžné validaci by bylo třeba diskutovat velké množství různých situací a vytvářet zbytečně jemné dělení intervalu. Validace zásobníku s nahodilostí ► Připomeňme, že u náhodných procesů dochází k „rozmazání" signálu. Není jasné, jak přesně výroba proběhne. ► Prostor všech možných průběhů popisujeme pomocí křivek kvantilů, což jsou hranice pomalejších a rychlejších průběhů pro danou pravděpodobnost. ► Kvantil stále „vypadá jako signál", tj. (v diskrétní výrobě) jde o lomenou čáru definovanou událnostmi. ► Aproximací kvantilu pro opakovaný proces je parabola (až na medián, kde je to přímka). V dalším se zaměříme i na úlohu, jak parabolu lineárně aproximovat. ► Rozšířený validační algoritmus tedy zohledňuje: ► Místo jednoho (determinovaného) průběhu bereme v potaz několik význačných kvantilů — zatím nám stačí kvartily. ► Pro každý kvantil uvažujeme horní i dolní odhad. ► Lineární aproximace parabol vyžaduje další zjemnění členění intervalu na události. (Kombinaci tohoto členění s iteracemi algoritmu jsme zatím neřešili — pěkné téma pro BP.) Simulace opakovaného náhodného procesu hmota čas 15 běhů, vybíráme 4., 8. a 12. v pořadí. Co vyjde? I Pro každý bod dělení intervalu převádíme odhady kvantilů na odhady pseudomomentů, sečteme je pro všechny signály zásobníku a výsledek můžeme zpětně převést na kvantily. Pro kvartily pak bychom mohli obdržet odpověď typu: „Zásobník v čase t nepodtéká s pravděpodobností větší než 50%, ale menší než 75%." „Přesnou" spolehlivost si můžeme vymodelovat podle vzdálenosti meze od kvantilů, např. pomocí lichoběžníkového rozdělení. Co vyjde? II ► Lichoběžníkové rozdělení dobře vypadá, ale trochu hůř se s ním počítá, protože distribuční funkce (integrál) je kvadratická, potřebujeme znát celou pětibodovou charakteristiku a levá a pravá polovina se nemusí potkat . ► Někdo by proto mohl dát přednost obdélníkovému rozdělení. To má lineární distribuční funkci a stačí nám znát jen okolní kvantily: X 4 □ ► >0 Q,o Změna dotazu ► Jinou možností je už od začátku počítat s jinou množinou kvantilů, např. Q1/4, Q3/4, Qp, kde p je požadovaná spolehlivost. ► Místo doplňovací otázky „Jaká je spolehlivost v čase ŕ?" řešíme otázku zjišťovací „Je spolehlivost v čase t aspoň p?" ► Obě otázky mají své opodstatnění, zjišťovací forma má jednodušší výpočet. Odmocninová rovnice ► Z dřívějších úvah jsme dostali, že při výrobě n kusů v opakovaném procesu předpokládáme všechny kvantily procesního času ve tvaru: kde a, b jsou vhodné konstanty pro danou pravděpodobnost a zvolený způsob modelování rozdělení. ► Výměna os odpovídá obrácení otázky „Kolik výrobků bude hotovo v čase ŕ?", tj. řešíme rovnici v n pro parametr t. ► Po úpravách dostáváme: t = nm + ay^ns + bg m2n2 + {t- bg)2 - 2m(t - bg)n, {{as)2 + 2m{t - bg))n + {t - bg)2 = 0. Odmocninová rovnice ► Substitucí a2 t - bg A=^, B =-^ mz m rovnici zjednodušíme na tvar n2 - (A + 2B)n+ B2 = 0. ► Diskriminant je D = (A + 2B)2 - 462 = A2 + AAB = A{A + 46) mocninová rovnice ► Dostáváme kořeny (A + 2B)±^/A(A + AB) "1,2 =-j-' ► Zajímá nás jeden z kořenů, druhý nedává smysl. Výběr kořene určuje konstanta a, tj. zda řešíme konvexní/konkávní parabolickou funkci (tj. kvantil pro p < 1/2 resp. p > 1/2). ► Všimneme si, že A + 2B je aritmetický průměr čísel A a A + 46, zatímco \[Ď — \J'A(A + 46). je jejich geometrický průměr. ► Připomeňme, že mezi průměry platí nerovnost GP< AP a podle Eukleidovy věty o výšce je náš GP roven výšce pravoúhlého trojúhelníku, v němž pata výšky dělí přeponu právě na úseky délek A a A + 46. Eukleidova věta o výšce a AG nerovnost Lineární aproximace paraboly ► Kvůli kombinaci požadavků na horní/dolní odhad a konvexnosť/konkávnost potřebujeme umět parabolu aproximovat zvenku i zevnitř. ► Z mnoha možností dáme přednost řešení, kde ► zpřesnění aproximace se provede zjemněním dělení— chceme jen přidat nové události a nezahazovat výpočty pro staré, ► koeficienty aproximačních přímek budou racionální — tím se odbourá část problémů s počítačovým zaokrouhlováním u reálného typu. ► Vnější aproximace je náročnější— po nalezení dotykových bodů musíme ještě počítat tečny a jejich průsečíky. Vnitřní a vnější aproximace hmota ionální aproximace ► Druhý požadavek je konkrétněji položen takto: místo výpočtu odmocninou _ (A + 2B)±^/A(A + AB) n~ 2 hledáme přibližné řešení ve tvaru n « kiA + k2B, kde /ci, /c2 jsou racionální. ► K tomu je zřejmě dostatečné a nutné, abychom našli hustou podmnožinu bodů na Thaletově kružnici, v níž bude poměr výšky (GP) k přeponě (2AP) racionální. Pythagorejské trojice ► Pythagorejskou trojicírozumíme trojici přirozených čísel (a, b, c) splňujících Pythagorovu větu: a2 + b2 = c2. ► Pythagorejské trojice lze triviálně množit vynásobením přirozeným číslem. ► Nesoudělné trojice se nazývají primitivní, tj. nejsou výsledkem netriviálního násobení jiné PT. Je známo, že i primitivních trojic je nekonečně mnoho. ► Pokud prvočíslo p dělí dvě strany, musí dělit i stranu třetí. Nesoudělnost v PT tedy stačí testovat na libovolných dvou stranách. ► Eukleides dokázal, že pro x,y G N,x > y je trojice (x2 - y2,2xy,x2 +y2) pythagorejská a všechny PT vzniknou tímto způsobem. Posloupnosti pythagorejských trojic ► V Eukleidově klasifikaci můžeme volit speciální x, y a tvořit posloupnosti PT, např. ► Pythagorova posloupnost, x = y + 1: (3,4,5), (5,12,13), (7,24,25), (9,40,41), ... ► Platónova posloupnost, y = 1: (3,4,5), (8,6,10), (15,8,17), (24,10,26), ... ► Pythagorovu posloupnost lze až na násobek zadat volbou y = 1/2. ► Zaměříme se na posloupnosti s konstantním y a ještě konkrétněji na posloupnosti s y = 2k. Lze ukázat, že zvýšením k — 1 —z- k „půlíme" předchozí iteraci y = 2/c_1, tj. pro stávající PT zdvojnásobíme index v posloupnosti a nové PT vkládáme na liché pozice. ► V každé posloupnosti se zmenšuje úhel při jednom z vrcholů (a u druhého zvětšuje). Jedná se tak o pohyb po oblouku Thaletovy kružnice (a potažmo po parabole v původní úloze). Topologie pythagorejských trojic ► Lze klasifikovat dvojice (x,y), které generují primitivní PT. ► Nás primitivita moc nezajímá, potřebujeme hlavně nějak generovat vzájemně nepodobné PT. ► Distribuce reprezentací PT na kružnici, v Gaussově celočíselné rovině, atp. nápadně připomínají konstrukci množiny racionálních čísel a její vložení do IR. Krácení zlomků odpovídá redukci PT na primitivní. V rámci teorie PT jsou známy různé zajímavé reprezentace a transformace. ► Pro nás je podstatné, že pravoúhlý vrchol skutečně vykresluje pro PT na Thaletově kružnici hustou podmnožinu, jak jsme potřebovali. Jinými slovy, každý pravoúhlý trojúhelník je v určitém smyslu limitou pythagorejských. ► Hustá je i množina získaná speciálními volbami y = 2^, kN. (To je analogie faktu, že zlomky tvaru z/(2k) tvoří hustou podmnožinu v IR.) Komentáře k validaci ► Kombinací odhadů kvantilů a lineárních aproximací paraboly bychom měli získat algoritmus pro validaci zásobníku v pravděpodobnostním prostředí. Strategie výpočtu založená na přidávání událostí v neobjasněných intervalech zůstává stejná. (Problém čeká na dokončení.) ► Ve srovnání se simulací Monte Carlo má lineární validace výhody: ► Poskytuje stále stejné výsledky a neprojevuje se efekt statistické chyby generovaných dat. ► Pro rozsáhlejší kampaně a/nebo větší rozptyl očekáváme rychlejší výpočet. A nevýhody: ► Nevidíme skutečný projev kolizí na celkové zpomalení toku — nepočítáme LT. ► Pro menší dávky/rozptyl může být rychlejší zkusit MC. ► Téma k zamyšlení/práci: kde je ta hranice? Komentáře k validaci ► Připomeňme, že validace zásobníků lineárními aproximacemi se vyplácí pro výrobu se „střední pravidelností". Vysoce pravidelná výroba (linky, nepřetržitý provoz) nezná kolize, kusová výroba nezná opakované procesy. ► V kusové výrobě se nahodilost často vyskytuje. Součet veličin na hmotové ose se popsanou metodou určitě nevyplatí (a navíc je nepřesný), rozumné je použít diskrétní konvoluci. ► Stejná poznámka se může týkat i situací, kde rozptyl a/nebo velikost kampaně je menšia hmotové rozdělení tak má malý nosič. ► V praxi se často řeší obrácená úloha „zjistit minimální kapacitu zásobníku / počáteční zásoby". V našem pojetí odpovídá stanovení mezí tak, aby se simulovaný signál (s požadovanou spolehlivostí) mezi ně vešel. 44 ► Validací zásobníky jsme schopni měřit i míru selhání — velikost plochy v čase a hmotě. Opět se můžeme spokojit i s prostým odhadem aproximacemi. ► Přiřazením váhy příslušnému selhání (kolize) definujeme defekt. ► Defekt tedy číselně vyjadřuje míru problému, tj. jak moc nám kolize vadí. ► Defekty jsou sice nežádoucí, ale mohou být nevyhnutelné a stanou se předmětem úvah typu „něco za něco". ► Je tedy vhodné rozmyslet si co nejširší váhové ohodnocení zásobníků. ► Souhrnný defekt je součet všech defektů. Je možné ho považovat za účelovou funkci pro optimalizaci plánu. lustrace defektů s2 čas hmota meze Si i/i/i Si + W2S2 Příklady defektu ► „Základní" příklad — podtečení nebo přetečení zásobníku s materiálem. Nelze vyrábět kvůli hladovění nebo blokování procesu. ► Nevyužitá kapacita zařízení— pokutujeme stav vyčkávání (idle), tj. vytvoříme pro stroj zásobník, v němž je stav 0 horní mezí a stav 1 je už vnímán jako „přetečení". ► Kolize procesů na zařízení— stejný zásobník jako výše, ale kolizí z něj odebíráme stroj „dvakrát". Ve výsledku je tak v zásobníku „ — 1 připravených strojů". Stav pokutujeme jako nežádoucí podtečení dolní meze 0. ► Nesprávný režim stroje — pro proces můžeme vytvořit virtuální zásobník, kam si proces „odplivuje", abychom nemuseli měnit způsob výpočtu defektu. ► Nedodržení termínu expedice — kolize posledního výrobního procesu a procesu expedice na zásobníku se zakázkou. ► Bonifikace rychlé výroby — stanovíme si nesplnitelný„vnitřní deadline" a řešíme stejně jako předchozí. Obecnější způsoby definice defektu ► V pravděpodobnostním prostředím můžeme defekt rozčlenit podle kvantilů a přirozeně tak navíc vážit pravděpodobnostní mírou, což vyjadřuje průměrný příspěvek jednoho náhodného běhu k defektu. ► Pokutování za defekt může být progresivní — tj. malé překročení vadí málo, větší překročení je průšvih. Princip výpočtu je podobný jako u předchozího. ► Při agregaci nemusí být „celková nelibost" prostým součtem přispívajících defektů. Lze vytvořit pomocný zásobník pro sdružený stav a stanovit pro něj váhu. Příklad: Úloha o vlku, koze a zelí. Čtyři konstelace jsou přijatelné, čtyři nejsou. Defekt není možné vyjádřit prostým součtem „po zvířatech". ► Pokud si představíme tok rozložený na jednotlivé výrobky, odpovídající zásobníky, pravděpodobnostní běhy, atd., zjistíme, že stále řešíme tentýž obecný problém. Souhrnný defekt plánu ► Podle předchozího získáme souhrnný defekt jako součet všech dílčích defektů (vážené plochy), tj. předpokládaných ztrát. ► Pro všechny myslitelné kolize je třeba stavit váhu, což může být nesnadné a pracné. ► Za předpokladu stejného zisku za vyhotovení smluvené zakázky je tak souhrnný defekt rozdílovým kriteriem pro výběr lepšího plánu. plán 1 plán 2 1 > > plán 3 >0 Q,o Optimalizace I ► Cílem optimalizace je minimalizace účelové funkce při dodržení omezení. ► Omezeníjsou pevná, jejich překročením bychom se dostali mimo prostor přípustných řešení ► Neštěstí optimalizace: Globální optimum obvykle není „sjednocením" lokálních optim. Nicméně v některých případech lze předpokládat určitou nezávislost komponent a úlohu rozdělit. ► Optimalizační metody obvykle postupují prostorem přípustných řešení a snižují účelovou funkci. ► Spoustu práce může ušetřit vhodná volba počátečního plánu. Optimalizace II ► Úspěšnost metody lze vyjádřit počtem cyklů — čím méně, tím lépe. ► Užitečná je schopnost vědět „kam jít" — volba pivota v simplexovém algoritmu lineárního programování, metoda největšího spádu, atd. ► Pokud množina přípustných řešení není rozumně parametrizovatelná, volba slibného směru nemusí být možná. ► Optimalizace pak probíhá metodou pokus/omyl, je zdlouhavá a nabízí se ukončení v suboptimálním řešení. Simulované žíhaní ► Podstatou simulovaného žíhaníje „ochota" provádět velké (a riskantní) změny spíš na začátku optimalizace. Postupně se tato ochota zmenšuje — chlazení. ► Změnou v plánu rozumíme např. přesun úkolu v čase (vodorovný posun v Ganttovi), výměnu úkonů ve frontě, velkou změnou může být obdoba pro složený proces (např. výměna celého středečního rozvrhu za úterní). ► Ochotou ke změně rozumíme pravděpodobnost, algoritmus je náhodný. ► Pokud je nalezené řešení lepší než předchozí, určitě jej bereme. Pokud je horší, pokračujeme v průzkumu s aktuální pravděpodobností. ► Po čase se pravděpodobnost sníží natolik, že už se žádná změna téměř jistě nestane — zamrznutí. ► Velké skoky jsou užitečné jako možnost opustit oblast prostoru řešení směřující k „méně optimálnímu" lokálnímu minimu. Metrizace prostoru plánů ► Pro potřeby simulovaného žíhání je vhodné zavést metriku na prostoru plánů měřící jejich odlišnost. ► Nabízí se měřit vzdálenosti odpovídajících událostí v časoprostorohmotě, tedy velikost souhrnné deformace měnící jeden plán na druhý. ► Problém může být zajímavý v kategória I ním u vyjádření — plány jsou funktory, události jsou propojeny morfismy přirozené transformace. ► Není doděláno, prostor pro výzkum. ► U simulovaného žíhání mohou pomoci „zjevné korekční tahy", např. posunutí procesů ve frontě, aby k sobě přiléhali podle procesních časů. (Při vyšší složitosti sítě ale mohou něco rozbít jinde.) Shrnutí řešené problematiky ► Validace — hledání kolizí v toku, odpovědi typu ano/ne, případně pravděpodobnost. ► Evaluace — kolize jsou měřeny a je jim přisouzena váha, výsledek nazýváme defekt. Součet všech defektů dává hodnocení toku. ► Optimalizace — změnou plánu se snažíme snižovat celkový defekt a najít (sub)optimální řešení. Jazyk toku ► Pokusíme se přepsat tok do kódu. ► Kód je současně datovým záznamem i jistým „programem" — lze podle něj naplánovat a spustit výrobu, nebo aspoň její simulaci. ► Kód může být předmětem dalšího zpracování— rozvinutí, zobecnění, optimalizace, atd. Princip funkcionálního programování. ► Potřebujeme popsat procesy i zásobníky. Připomeňme, že tok lze konstruovat jako diagram D : V /C, kde /C je kategorie zdrojů spojených procesy. ► Skládání lze dobře vystihnout značkovacím jazykem, pro rychlé vyhledávání jsou vhodné relační databáze. ► Pro vodorovné/svislé oddělovače položek použijeme csv notaci, tj. čárky/středniky. ncipy přepisu ► Programujeme „objektově", tj. uděláme si základní kostru, pak rozepisujeme detaily. ► Rozmysleme si, kdy procesy probíhají nebo zdroje se spotřebovávají v daném poradia kdy je pořadí zaměnitelné. ► Každý proces „nahlíží" na zdroje určitým typem a úrovní agregace. Vzniká u něj složený zásobník (vysvětlíme na příkladech). ► Opakované procesy vyjádříme cyklem (s počtem opakování příslušnému velikosti kampaně). Označení pro kompozice {a, b, c}, n * {a} — typ (multi)množina, složky jsou nezávislé, zaměnitelné, proveditelné paralelně, je asociativní i komutativní: {a,b} = {b,a}, {{a,b},c} = {ai{blC}} (a, b, c), r? * (a) — typ uspořádaná r?-tice/seznam, pevné řazení složek, sériové provedení v daném pořadí, jen asociativní: ((a,b),c) = (a,(b, c)) [a, b, c], r? * [a] — podobné jako kulatá závorka, ale není ani asociativní, složky jsou zpracovány nerozbalené, závorka chrání svůj obsah před „rozpuštěním" do nadřazeného výrazu. Příklad s virtuálním supermarketem I Příklad s virtuálním supermarketem II Příklad s nezávislými procesy (R. Koutenský) ► Uvažujeme dvojici procesů, kde na celek (např. auto □) je třeba přimontovat dva doplňky (např. volant O a zrcátko A) ► Procesy mohou být provedeny: 1. zcela nezávisle (klidně i souběžně), 2. v libovolném pořadí (ale jeden po druhém). > 1—1 > 1— +o > 1—1 > 1— +A Naivní řešení 1. verze Chování složeného procesu nemáme pod kontrolou, nic nespočítáme. Dvouštěrbinové řešení 1. verze Dvou čestné řešení 2. verze Nepodařilo se sloučit stejné procesy. Složitost schématu rychle roste s počtem procesů. Schródingerovsko-kočkovité řešení 2. verze Databáze procesů vstup proces výstup (A3*[ß]) C (A; 3* [B]) P q (P. 9) C (D: f) (D: f) ► Jazyk zatím v náznaku, zrejme bude ještě nutné rozlišit horizontální a vertikální skládání. ► „Přepážkový" proces ve schématech je obousměrný a jen překládači (analogie s polními částicemi). ► Závorky odpovídají standardním databázovém operacím sjednocení a spojení. ► Vše směřuje k relačnímu popisu toku. Kategorie Rel je dagger kompaktní stejně jako konečné vektorové prostory. ► Propojení s jazykem kvantových protokolů vypadá velmi nadějně.