SYSTÉMOVÁ
METODOLOGIE (VIII) Operační výzkum
Ak. rok 2011/2012
© vbP
1
Operační výzkum DEFINICE Operační výzkum je prostředek pro nalezení optimálního řešení daného problému při respektování celé řady různorodých omezení, která mají vliv na chod systému. FÁZE ŘEŠENÍ PROBLÉMŮ V OPERAČNÍM VÝZKUMU (1) • Rozpoznání problému v rámci reálného systému a jeho definice • schopnost managementu rozpoznat problém • schopnost odhadnout potřebu modelového přístupu • schopnost vytvořit tým příslušných odborníků
Ak. rok 2011/2012
© vbP
2
Operační výzkum FÁZE ŘEŠENÍ PROBLÉMŮ V OPERAČNÍM VÝZKUMU (2) • Formulace ekonomického modelu daného problému • části ekonomického modelu • cíl analýzy (určení cílového stavu modelovaného systému (např. maximalizace zisku)) • popis procesů, které v systému probíhají • popis činitelů ovlivňujících provádění procesů (čas, energie, …) • popis vztahů mezi procesy, činiteli a cílem analýzy • Formulace matematického modelu daného problému • formalizace ekonomického modelu • cíl zpravidla vyjádřen ve formě lineární nebo nelineární funkce o n proměnných Ak. rok 2011/2012
© vbP
3
Operační výzkum FÁZE ŘEŠENÍ PROBLÉMŮ V OPERAČNÍM VÝZKUMU (3) • Řešení matematického modelu • vyuţití kvalitního software • MS Excel • Matlab • řešiče: Mathematica, Maple, Derive, (Fluent) • Interpretace výsledků a následná verifikace • POZOR na moţnou nepouţitelnost „optimálních“ řešení • Implementace výsledků • zavedení výsledků do praxe • cílem implementace (a celého řešení v rámci operačního výzkumu) je příspěvek ke zlepšení fungování daného systému Ak. rok 2011/2012
© vbP
4
Operační výzkum DISCIPLÍNY OPERAČNÍM VÝZKUMU (1) • Matematické programování • řešení optimalizačních úloh • lineární programování (kriteriální fce, rov. i nerov. lineární) • nelineární programování • Vícekriteriální rozhodování • nutné řešit konflikt mezi navzájem protikladnými kritérii • Teorie grafů • Řízení zásob • strategie řízení zásobovacího procesu • optimalizace objemu skladovaných zásob
Ak. rok 2011/2012
© vbP
5
Operační výzkum DISCIPLÍNY OPERAČNÍM VÝZKUMU (2) • Teorie hromadné obsluhy • téţ teorie front • poţadavky, které do systému přicházejí • obsluţné linky, které obsluhu realizují • Modely obnovy • zkoumání jednotek systému, které selţou; nutnost opravy (náhrady) • predikce jednotek, které v jednotlivých časových obdobích selţou • Markovovy rozhodovací procesy • obecný prostředek pro popis chování dynamických systémů (mají konečný počet stavů a jejich změna je náhodná) • Teorie her Ak. rok 2011/2012
© vbP
6
Operační výzkum DISCIPLÍNY OPERAČNÍM VÝZKUMU (3) • Simulace • většinou jde o modelování chování systému na počítači • experimentování s tímto modelem
Ak. rok 2011/2012
© vbP
7
Operační výzkum LINEÁRNÍ PROGRAMOVÁNÍ (SMĚŠOVACÍ PROBLÉM) (Úloha o vytvoření směsi s poţadovanými vlastnostmi)
(1)
• Úlohy výrobního plánování • problém alokace zdrojů
• proměnné: objem produkce jednotlivých výrobků • omezující podmínky: limitující objem výroby, doba provozu výrobní linky • Úlohy finančního plánování • optimalizace portfolia • proměnné: objemy investic • omezující podmínky: investiční strategie
Ak. rok 2011/2012
© vbP
8
Operační výzkum LINEÁRNÍ PROGRAMOVÁNÍ (SMĚŠOVACÍ PROBLÉM) (2) (Úloha o vytvoření směsi s poţadovanými vlastnostmi) • Plánování reklamy • alokace rozpočtu na reklamu do jednotlivých médií • proměnné: např. počet opakování v daném médiu • omezující podmínky: rozpočet, reklamní strategie, cílová skupina • Nutriční problém • problém denní dávky výţivy pro příslušného jedince • proměnné: jednotlivé komponenty (voda, vápník, vitamíny) • omezující podmínky: min., max. úroveň výţivových komponent (např. člověk a maximální množství vitamínu denně)
Ak. rok 2011/2012
© vbP
9
Operační výzkum LINEÁRNÍ PROGRAMOVÁNÍ (další moţné úlohy)
(3)
• Úloha o dělení materiálu • dělení větších celků na menší tak, aby byl minimální odpad • omezující podmínky: poměr malých částí, jejich počet, …
• Rozvrhování pracovníků (směny) • omezující podmínky: kvalifikace zaměstnanců, počet pracovníků na směně (minimální, resp. pevně stanovený)
• Distribuční úlohy • optimalizace distribuce zboţí mezi dodavateli a odběrateli
Ak. rok 2011/2012
© vbP
10
Operační výzkum MODELY ŘÍZENÍ ZÁSOB (základní charakteristiky) (1) • Charakter poptávky • poptávka deterministická • poptávka stochastická • Vznik případného nedostatku zásoby • vede k nutnosti vytvořit určité mnoţství tzv. pojistné zásoby • Pořizovací lhůta dodávky • doba od vystavení objednávky aţ po uloţení zásoby na sklad • spojité sledování zásob • periodické sledování zásob
Optimalizační kritérium: MINIMALIZACE nákladů na zásobování
Ak. rok 2011/2012
© vbP
11
Operační výzkum DRUHY NÁKLADŮ
(2)
• Skladovací náklady (c1) • povaţovány za variabilní (závisejí na objemu skladových zásob) • náklady na skladovací prostory, pojištění, manipulace, energie)
• Pořizovací náklady (c2) • povaţovány za fixní (nesouvisejí s velikostí objednávky) • Náklady z nedostatku zásoby (c3)
• náklady v důsledku neuspokojení poptávky • penále za pozdní dodávku • ušlý zisk při neuskutečněném obchodě
• ztráta při přerušení výroby
Ak. rok 2011/2012
© vbP
12
Operační výzkum MODELY ŘÍZENÍ ZÁSOB • Economic Order Quantity (EOQ)
(1)
• Předpoklady • poptávka je známá a konstantní (Q) • čerpání zásob ze skladu je rovnoměrné • pořizovací lhůta dodávek je známá a konstantní • velikost všech dodávek je konstantní (q) • nákupní cena je nezávislá na velikosti objednávky • není připuštěn vznik nedostatku zásoby • k doplnění skladu dochází v jednom časovém okamţiku
Ak. rok 2011/2012
© vbP
13
Operační výzkum MODELY ŘÍZENÍ ZÁSOB • Production Order Quantity (POQ)
(2)
• Předpoklady • stejné předpoklady jako EOQ • doplnění skladu není jednorázové ! • dodávkový cyklus má 2 intervaly (výrobní a spotřební cyklus)
Ak. rok 2011/2012
© vbP
14
Operační výzkum MODELY HROMADNÉ OBSLUHY Systémy, ve kterých se vytvářejí fronty
(1)
obslužné linky 1
příchod do systému
2
Zdroj poţadavků
…
odchod ze systému
fronta – čekání požadavků n
realizace obsluhy
Ak. rok 2011/2012
© vbP
15
Operační výzkum MODELY HROMADNÉ OBSLUHY • Příklady
(2)
SYSTÉM
OBSLUŢNÉ LINKY
POŢADAVKY
telefonní centrála nádraţí pojišťovna výrobní linka ordinace lékaře benzínová pumpa dopravní systém lyţařské středisko
telefonní linky pokladny úředníci místa na výrobní lince lékař čerpací stojany křiţovatka se semafory vleky
volající cestující pojistné případy výrobky pacienti vozidla vozidla lyţaři
Ak. rok 2011/2012
© vbP
16
Operační výzkum MODELY HROMADNÉ OBSLUHY (3) • Charakteristiky • Struktura systému • paralelní uspořádání sítě obsluţných linek • Zdroj poţadavků • konečný (hala s konečným počtem strojů) • nekonečný (auta, která jezdí k pumpě) • Příchod poţadavků do systému • deterministický (intervaly mezi příchody jsou fixní – výr. linka) • stochastický (intervaly mezi příchody jsou proměnlivé) • Doba trvání obsluhy • deterministická • stochastická Ak. rok 2011/2012
© vbP
17
Operační výzkum MODELY HROMADNÉ OBSLUHY (4) • Charakteristiky • Reţim (řád) fronty • způsob přechodu poţadavku z fronty do obsluhy • FIFO = First In First Out • LIFO = Last In First Out • SIRO = Selection In Random Order • HVF = Higher Value First
Ak. rok 2011/2012
© vbP
18
Operační výzkum MODELY HROMADNÉ OBSLUHY (5) • Charakteristiky • Speciální rysy systému hromadné obsluhy • systémy bez čekacích míst (počet míst ve frontě je 0, např. parkoviště, kde se nečeká) • neomezená trpělivost (poţadavky čekají tak dlouho, dokud nejsou řešeny) • omezená trpělivost (pravděpodobnost zařazení do fronty závisí na počtu poţadavků ve frontě) • obsluha ve skupinách (výtah, městská doprava) • příchod vyšší priority (záchranná sluţba, spoolink I/O)
Ak. rok 2011/2012
© vbP
19
Operační výzkum VÍCEKRITERIÁLNÍ ROZHODOVÁNÍ
• Úlohy dělíme do dvou skupin • Úlohy vícekriteriálního rozhodování (VHV) • varianty jsou zde určeny konkrétním seznamem nebo výčtem • Úlohy vícekriteriálního programování (VLP) • varianty jsou zde určeny soustavou omezujících podmínek stejně jako u lineárního programování
Ak. rok 2011/2012
© vbP
20
Operační výzkum VÍCEKRITERIÁLNÍ ROZHODOVÁNÍ • Při řešení jednotlivých úloh musíme určit VÁHY jednotlivých kritérií • VÁHY můžeme získat od rozhodovatele přímo v numerické podobě • Metoda pořadí (od nejdůleţitějšího po nejméně důleţité) • Bodovací metoda (důleţitost kritérií hodnotíme dle předem zvolené stupnice) • Fullerův trojúhelník (Vytvoříme trojúhelníkové schéma (dvojice jednotlivých kritérií tak, ţe kaţdá dvojice se ve schématu vyskytuje pouze jednou). U kaţdé dvojice volíme to kritérium, které je důleţitější) • Saatyho metoda (opět porovnáme všechny moţné dvojice kritérií (důleţitost jednoho kritéria hodnotíme stupnicí 1-9) a informace sestavíme do Saatyho matice (sii = 1, sij = 1/sji) Ak. rok 2011/2012
© vbP
21
Operační výzkum MARKOVOVY PROCESY A ŘETĚZCE Čas nebo přechody mezi stavy jsou spojité (v případě Markovových řetězců se jedná o diskrétní stavy a diskrétní časové úseky) • Vlastnosti Markovových řetězců • systém se nachází v některém z • konečných stavů S1, S2, …, Sm => konečný Markovův řetězec • nekonečných, ale spočetných, stavů S1, S2, …=>nekonečný MŘ • stavy i čas jsou diskrétní • Všechny pravděpodobnosti přechodu můţeme vyjádřit pomocí jedné stochastické matice, tzv. matice pravděpodobností přechodu P
Ak. rok 2011/2012
© vbP
22
Operační výzkum MARKOVOVY PROCESY A ŘETĚZCE • Absorpční MŘ • sleduje se střední doba a rozptyl přechodu • sleduje se střední doba strávená v transientních stavech • sleduje se pravděpodobnost absorpce (přechod do absorpčního stavu) • Regulární MŘ • matice pravděpodobnosti přechodu P je regulární, jestliţe pro určité n je matice Pn bez nulových prvků
Ak. rok 2011/2012
© vbP
23
Operační výzkum MODELY OBNOVY • popisují proces postupného opotřebování a vyřazování uzavřené třídy jednotek z procesu a jejich nahrazování novými prvky • prostá obnova = počet vyřazených a nahrazených prvků je stejný • rozšířená obnova = nových prvků je doplněn větší počet
Ak. rok 2011/2012
© vbP
24
Operační výzkum MODELY OBNOVY • PŘEDPOKLADY modelů obnovy • sledují stejně dlouhá období • existuje maximální doba ţivotnosti • technicky homogenní prvky • buď prvky stejného druhu • nebo pravděpodobnost vyřazení právě na konci k-tého období je pro všechny prvky v daném období stejná a závisí pouze na stáří prvků • na začátku procesu jsou všechny prvky věkově homogenní • neuvaţuje se morální nebo částečné opotřebení • …
Ak. rok 2011/2012
© vbP
25
Děkuji za pozornost
Ak. rok 2011/2012
© vbP
26