www.cz-milka.net
1. Základní pojmy Systém – neprázdná, účelově definovaná množina prvků a vazeb mezi nimi, která se zachycením vstupů a výstupů vykazuje kvantifikovatelné chování v čase. Model – formalizovaný systém. Formalizace – matematická, modely jsou matematické. Vektor – uspořádaná soustava reálných čísel, orientovaná úsečka, je dán bodem a směrem. Jednotkový vektor – vektor, která má na jednom místě jedničku a na ostatních nuly, například (0, 1, 0). Lineární kombinace vektorů – vyjadřuje, že vektory lze kombinovat. Závislost vektorů – vektory mohou být lineárně závislé nebo lineárně nezávislé. Vektorový prostor – udává počet čísel v příslušném vektoru, je tvořen vektory a operacemi, které lze s vektory dělat: ü Musí být definován nulový vektor (0, 0, 0). ü Sčítání vektorů a násobení skalárem. ü Vektorový prostor má dimenzi. Báze vektorového prostoru – jakákoliv skupina vektorů, která splňuje určité podmínky: ü Lineární nezávislost. ü Přidáme-li jakýkoli další vektor, je možné ho pomocí báze vyjádřit. Podmnožina vektoru, pomocí které lze vyjádřit jakýkoli vektor z daného prostoru, vektory musí být nezávislé. Matice – uspořádaná n-tice čísel.
-1-
www.cz-milka.net
2. Lineární modely (programování) Lineární modely – zobrazují systém s určitou mírou nepřesnosti, vyplývající z předpokladu linearity zobrazovaných procesů a deterministického charakteru parametrů modelu. Cíl modelu lineárního programování – nalézt řešení splňující omezující podmínky, v němž kriteríální funkce nabývá požadovaného extrému. Prvky lineárního optimalizačního modelu: ü Vektor proměnných, který popisuje jednotlivé složky hledaného rozhodnutí. ü Omezující podmínky, které popisují reálná omezení hledaných rozhodnutí. ü Účelová nebo kriteriální funkce, která popisuje cíl, kritérium hledaného rozhodnutí. Úlohy řešitelné lineárním optimalizačním modelem: ü Optimalizace výrobní struktury – optimální rozsahy výrobních procesů. ü Alokační problémy – rozdělení zdrojů na pořízení určitých objektů. ü Směšovací problémy – nalezení optimálních množství jednotlivých složek směsi. ü Problémy dělení materiálů = úlohy o řezných plánech – optimální volba způsobu dělení materiálu. ü Distribuční problémy – optimalizace distribuce zboží. Typy omezujících podmínek: ü Exogenní (vnější) vazby systému: • Kapacitní • Požadavkové • Určení ü Endogenní (vnitřní) vazby systému: • Bilanční: o Vyrovnaná bilance o Bilance s neúplným krytím o Bilance s přebytkem • Poměrové
Grafické řešení lineárního programování: Postup grafického řešení: ü Formulace matematického modelu – proměnné, omezující podmínky, podmínky nezápornosti, účelová a kriteriální funkce. ü Grafické vyjádření množiny přípustných řešení. ü Grafické vyjádření účelové funkce. ü Nalezení extrému. Prostor řešení – prostor, ve kterém leží všechny přípustná řešení problému. Množina přípustných řešení – průnik poloprostorů. Poloprostor je konvexní množina a průnik je tedy také konvexní množina. Konvexní množina – množina bodů, pro kterou platí, že s každými jejími dvěma různými body do ní patří také všechny body úsečky určené těmito body. ü Konvexní polyedr – omezení konvexní množina. ü Polyedrický kužel – neomezená konvexní množina. Případy řešení úloh lineárního programování: ü Množina přípustných řešení je prázdná – model nemá řešení. ü Množina přípustných řešení je konvexní polyedr – model má optimální řešení. ü Množina přípustných řešení je neomezená = polyedrický kužel – účelová funkce může v jednom směru nabývat libovolně velkých nebo malých hodnot. -2-
www.cz-milka.net Prostor požadavků – prostor, ve kterém je možno zobrazit vektory koeficientů jednotlivých parametrů.
Simplexový algoritmus: Simplexová metoda – univerzální metoda pro řešení úloh lineárního programování, metoda iterační, která využívá Jordanovu eliminační metodu doplněnou o dvě kritéria umožňující nalézt optimální řešení. Frobeniova věta – soustava lineárních rovnic je řešitelná, je-li hodnost matice soustavy rovna hodnosti rozšířené matice soustavy. Je-li tato hodnost rovna počtu proměnných, je řešení jediné, je-li počet proměnných větší, je řešení nekonečně mnoho. Frobeniova věta se zabývá hodností matic Jordanova eliminační metoda – obecná metoda řešení soustavy lineárních rovnic. Eliminační metoda, která k původní soustavě vytvoří ekvivalentní soustavu rovnic, jejíž matice soustavy je diagonální s jedničkami na diagonále. Pivot – klíčový nebo řídící prvek sloužící pro další úpravy rovnice. Řídící rovnice – rovnice, v níž je pivot. Řídící proměnná – proměnná, která má pivota jako jeden ze svých koeficientů. Povolené eliminační úpravy: ü Násobení řídící rovnice převrácenou hodnotou řídícího prvku. ü Přičtení vhodného násobku řídící rovnice k upravované rovnici. Bázické proměnné – kanonické proměnné, jejichž koeficienty vytvářejí jednotkovou matici – soustava musí být převedena do kanonického tvaru. Nebázické proměnné – ostatní proměnné, které nejsou bázické. Bázické (základní) řešení – vektor, jehož nenulové složky odpovídají bázickým vektorům. Nebázické (nezákladní) řešení – řešení, kdy za nebázické proměnné se položí určité hodnoty a získají se konkrétní hodnoty i pro bázické proměnné. Degenerované řešení – takové řešení, kde alespoň jedna z bazických proměnných má nulovou hodnotu. Takové řešení obsahuje více jak (n-m) nulových složek. Nedegenerované řešení – obsahuje právě (n-m) nulových složek. Parametrické řešení – hodnoty nebázických proměnných jsou považovány za parametry Matice transformace = inverzní matice – matice, kterou po aplikaci Jordanovy eliminační metody získáme na místě jednotkové matice. Kritérium optimality řešení – založeno na zjišťování, zda lze k danému řešení soustavy omezujících podmínek najít řešení jiné, které bude mít lepší hodnotu kritéria – účelové funkce. Alternativní optimální řešení – takové optimální řešení, které není jediné. Kritérium přípustnosti řešení – při změně báze říká, že v daném kroku ve sloupci, který je vektorem transformovaných koeficientů zařazované proměnné vyhledáme všechny kladné koeficienty a určíme podíly. Nezápornost pravých stran – lze zajistit tak, že rovnice či nerovnice se zápornou stranou vynásobíme -1, v případě nerovnice se změní její smysl.
-3-
www.cz-milka.net Transformace libovolného typu omezujících podmínek do rovnicového kanonického tvaru – rozšíření počtu proměnných modelu tak, aby nové proměnné vytvořily požadovaný kanonický tvar soustavy omezujících podmínek Doplňková proměnná typu rezerva – omezující podmínka je nerovnice typu ≤ – kapacitní podmínka, která může být převedena do kanonického tvaru doplněním nezáporné proměnné, jejímž cílem je vyrovnat rozdíl pravé a levé strany. Doplňková proměnná typu překročení – omezující podmínka je nerovnice typu ≥ – požadavková podmínka, která může být převedena do rovnicového tvaru doplněním nezáporné proměnné vyjadřující překročení požadavku. Pomocná proměnná – omezující podmínka je rovnice, ale není v kanonickém tvaru – podmínky, které byly v rovnicovém tvaru už při formulaci modelu, nebo požadavkové podmínky, které byly do rovnicového tvaru upraveny doplněním doplňkových proměnných typu překročení. Pomocné proměnné je během výpočtu potřeba vyřadit z řešení tak, aby byly v optimálním řešení nebázické, tedy rovny nule. Řešení s pomocnou proměnnou v bázi považujeme za řešení nepřípustné. Optimální řešení – získá se z výsledné simplexové tabulky. Alternativní řešení – z hlediska hodnoty účelové funkce je řešením optimálním, získá se zařazením nebázické proměnné xj s nulovou duální hodnotou (zj-cj=0) do řešení. Je to takové řešení, které je rovnocenné z hlediska hodnoty účelové funkce, získá se zařazením příslušné nezákladní strukturní proměnné do řešení. V řádku (zj-cj) mají tyto proměnné 0. Suboptimální řešení – řešení, které získáme, jestliže alespoň jedné z nebázických proměnných xj přiřadíme nenulovou hodnotu. Je to takové řešení, které vznikne zařazením nezákladní strukturní proměnné do řešení, ale hodnota účelové funkce se zhorší. Analýza citlivosti – zabývá se určováním takového rozsahu změn výchozích údajů lineární optimalizační úlohy, v rámci kterých nedochází ke změně optimální báze. Analýza citlivosti vzhledem ke změně jedné složky vektoru pravých stran b – změna hodnot pravých stran vyjádřená pomocí b(λ ) = b + λ . Řešením je interval stability řešení, respektive interval přípustných hodnot parametrů λ . Analýza citlivosti vzhledem ke změně jedné složky vektoru cen c – změna hodnot cen vyjádřená pomocí c(λ ) = c + λ . V případě maximalizační úlohy musí zůstat parametrické hodnoty nezáporné, v případě minimalizační úlohy musí zůstat nekladné. Získáme interval stability pro změnu ceny nebázické proměnné a interval stability pro změnu ceny bázické proměnné.
Teorie duality: Dualita – vzájemný vztah dvojice přesně definovaných úloh lineárního programování. Je vzájemným symetrickým vztahem obou úloh. Duální úloha – ke každé úloze lineárního programování lze zformulovat jinou úlohu lineárního programování – první úloha je primární, druhá duální. Postup převodu primární úlohy na duální: ü Transponovat matici A – jestliže má primární model m omezujících podmínek a n proměnných, potom duální model bude mít n omezujících podmínek a m proměnných. ü Určit vektor pravých stran duálního modelu – vektor bude mít n složek, vždy jim budou odpovídat cenové koeficienty primárního modelu. ü Určit vektor cen duálního modelu – vektor bude mít m složek, vždy jim budou odpovídat složky vektoru pravých stran primárního modelu. ü Určit směr optimalizace duálního modelu – jestliže je primární model minimalizační, bude duální model maximalizační a naopak. -4-
www.cz-milka.net ü Určit typ nerovnic u duálních omezujících podmínek – typ i-té omezující podmínky duálního modelu stanovíme podle povahy podmínky nezápornosti i-té proměnné primárního modelu. ü Určit podmínky nezápornosti duálního modelu – podmínku nezápornosti i-té duální proměnné stanovíme podle typu i-té omezující podmínky primárního modelu ve vztahu ke směru optimalizace primárního modelu.
-5-
www.cz-milka.net
3. Obecné optimalizační modely – kvadratické programování Optimalizační model = optimalizační úloha = model matematického programování – řešení, které je omezeno řadou podmínek a které zároveň nejlépe vyhovuje uvažovaným kritériím. Dělení optimalizačních modelů: ü Lineární – model, který ve své formulaci využívá pouze lineární funkce. ü Nelineární: • Konvexní – minimalizace účelové funkce obsahuje pouze konvexní funkce, účelová funkce je konvexní funkce a množina přípustných řešení je konvexní množina. Nejrozšířenějším typem je model kvadratický, jehož množina přípustných řešení je definována pomocí lineárních funkcí a kritérium je definováno pomocí kvadratické funkce. • Nekonvexní
Metody řešení optimalizačních modelů: Úloha na volný extrém – úloha o nalezení extrému funkce na celém jejím definičním oboru. Klasická úloha na vázaný extrém – úloha nalezení extrému funkce na části jejího definičního oboru.
Konvexní optimalizační model Konvexní optimalizační model – úloha najít minimum konvexní účelové funkce pro všechny vektory z konvexní množiny. Lagrangeova funkce – funkce proměnných seskupených do dvou vektorů. Kuhn-Tuckerova věta o sedlovém bodě – účelová funkce nabývá minima v bodě z konvexní množiny právě tehdy, když existuje příslušný vektor a platí příslušné vztahy. Sedlový bod – bod splňující podmínky Kuhn-Tuckerovy věty.
Kvadratický optimalizační model: Kvadratický optimalizační model – úloha nalezení minimální hodnoty kvadratické účelové funkce na množině přípustných řešení vyjádřené lineárními nerovnostmi. Wolfeho algoritmus – založen na řešení příslušných podmínek postupem známým ze simplexového algoritmu.
-6-
www.cz-milka.net
4. Dopravní modely Distribuční modely – speciální případ lineárních optimalizačních modelů. Typy distribučních modelů: ü Dopravní modely – cílem je nalézt optimální způsob přepravy materiálu nebo zboží od dodavatelů ke spotřebitelům. • Jednostupňová dopravní úloha – jednostupňový dvouindexový systém, obsahuje dodavatele, spotřebitele, nerozlišuje dopravní prostředky. • Dvoustupňová dopravní úloha – obsahuje dodavatele, spotřebitele a navíc mezisklady. ü Zobecněný distribuční model – umožňuje pomocí vhodných koeficientů přepočítávat rozdělované objemy na různé jednotky. ü Přiřazovaní problém – úloha se stejným počtem zdrojů jako spotřebitelů, jednomu spotřebiteli je možno přiřadit pouze jeden zdroj. ü Okružní problémy
Jednostupňová dopravní úloha: Jednostupňová dopravní úloha – nejjednodušší z distribučních modelů, cílem je najít takový plán přepravy mezi m dodavateli a n spotřebiteli, při kterém budou celkové přepravní náklady minimální a budou vyčerpány kapacity dodavatelů a uspokojeny požadavky spotřebitelů. Prvky jednostupňového dopravního modelu: ü Dodavatelé a jejich kapacity. ü Spotřebitelé a jejich požadavky. ü Dopravní náklady – ohodnocení každé trasy. Podmínky řešitelnosti: ü Úplná zastupitelnost přepravovaného produktu a dělitelnost materiálu – každý dodavatel musí být schopen dodávat každému spotřebiteli libovolné množství produktu a uspokojit tak jeho požadavek. ü Předpoklad vyváženosti úlohy – všichni dodavatelé dohromady musí být schopni uspokojit všechny požadavky spotřebitelů a nic nesmí přebývat a nic nesmí chybět. Vyváženost dopravní úlohy: ü Vyvážená – součet kapacit se rovná součtu požadavků. ü Nevyvážená – součet kapacit se nerovná součtu požadavků. Řešení dopravní úlohy: ü Nalezení výchozí bazického přípustného řešení pomocí takzvaných aproximačních metod. ü Test optimality – zjištění, zda je možno najít jiné základní řešení s lepší hodnotou účelové funkce. ü Přechod k lepšímu řešení pomocí takzvaných Dantzigových uzavřených obvodů.
Metody nalezení výchozího bazického řešení: Metoda severozápadního rohu SZR – nejjednodušší metoda, která umožňuje konstruovat bázické nezáporné řešení doprvní úlohy, výchozí řešení jsou však vzdálené od optimálního řešení modelu. Postup: ü V dopravní tabulce se vybere neobsazené pole s nejnižšími možnými indexy = severozápadní pole v tabulce. ü Vybrané proměnné se přiřadí hodnota maximálního možného převáženého množství zboží. ü Dodavatel nebo spotřebitel s vyčerpanou kapacitou nebo požadavkem se vyškrtne, dopravní tabulka se zmenší a postup se opakuje. ü Algoritmus končí, když jsou vyčerpány kapacity všech dodavatelů a uspokojeny požadavky všech spotřebitelů. Indexová metoda IM = metoda ceny – při konstrukci výchozího řešení se bere v úvahu sazba tras, je založena na porovnání absolutní výše sazeb tras. Postup: -7-
www.cz-milka.net ü Od metody severozápadního rohu se liší pouze tím, že se v prvním kroku vybere neobsazené volné pole, které má nejnižší sazbu. Vogelova aproximační metoda VAM – nejpoužívanější metoda, poskytuje řešení velmi blízká řešení optimálnímu, rozhodující je relativní výhodnost vzhledem k možnému zvýšení dopravních nákladů, tato relativní výhodnost se zjišťuje pomocí rozdílu mez nejvýhodnější a druhou nejvýhodnější sazbou od dodavatele (v řádku) ke spotřebiteli (ve sloupci). Postup: ü Vypočtou se diference mezi nejvýhodnější a druhou nejvýhodnější sazbou (při minimalizaci mezi nejnižší a druhou nejnižší sazbou) pro každý řádek a sloupec. ü Určí se maximální diference a ve vybraném řádku nebo sloupci se vybere trasa s nejvýhodnější sazbou ü Při výskytu několika stejně vysokých maximálních diferencí se obsazuje přednostně pole s nejvýhodnější sazbou z hlediska všech sazeb v matici sazeb = sedlové pole. ü Existuje-li několik sedlových polí, obsazuje se přednostně to pole, pro které je součet řádkové a sloupcové diference maximální. ü Neexistuje-li v řadách s maximální diferencí ani jediné sedlové pole, pak se stanovíme pro tyto řady druhé diference. Druhá diference je rozdíl mezi druhou nejvýhodnější sazbou v řadě s maximální první diferencí a mezi nejvýhodnější sazbou v kolmé řadě procházející uvažovanou druhou nejvýhodnější sazbou. Habrova frekvenční metoda
Test optimality: Test optimality – zjištění, zda neexistuje lepší řešení, založen na porovnání sazeb jednotlivých nebázických tras a příslušných nepřímých sazeb. Modifikovaná distribuční metoda MODI – slouží k rychlému nalezení nepřímých sazeb, je odvozena z teorie duality, princip spočívá v tom, že lze najít takové hodnoty duálních proměnných (řádková a sloupcová čísla), že pro všechny bázické proměnné platí rovnice u i + v j = cij . Postup: ü Z rovnic u i + v j = cij spočítáme neznámé ui a vj. ü Z rovnice u i + v j = z ij spočítáme nepřímé sazby. ü Pro bázické trasy jsou přímé sazby rovny nepřímým. ü Pro nebázické trasy slouží rozdíl z ij − cij k určení optimality řešení. ü V každém kroku vypočítáme pro nebázické proměnné všechny rozdíly z ij − cij a z nich vybereme největší. Je-li největší hodnota větší než 0, není nalezené řešení optimální.
Přechod na lepší řešení: Dantzigovy uzavřené obvody – uzavřená posloupnost (cyklus) na sebe navazujících tras, která obsahuje v řešení již po užité trasy a právě jednu trasu novou, jejíž každé dvě sousední trasy mají vždy buď stejného dodavatele nebo stejného spotřebitele. Dantzigovy uzavřené obvody představují grafické schéma v distribuční tabulce, naznačují, jak provést úpravu řešení a jak přesunout převážené zboží z jedné trasy na jinou. Množství převáženého materiálu se označuje střídavě znaménky + a –. Grafické schéma Dantzigova obvodu – lomená čára, která vychází z vybraného pole distribuční tabulky, prochází po řádcích nebo sloupcích, lomí se v obsazených polích a končí v původním poli.
Analýza řešení: Nedegenerované řešení – obsahuje právě m + n – 1 kladných hodnot m + n –1 = Počet obsazených polí (m + n –1 = Počet dodavatelů + počet spotřebitelů – 1) -8-
www.cz-milka.net Degenerované řešení – možnosti vzniku: ü Ve výchozím řešení, jestliže v některém kroku jeho konstrukce byla současně vyčerpána kapacita dodavatelů i naplněn požadavek spotřebitelů – je nutné trochu pozměnit požadavky, ale zároveň zajistit, aby nebyl změně původní dopravní systém, například úpravou o malé fiktivní množství materiálu ve výši ε. ü Při přechodu na nové bázické řešení, jestliže nové hodnoty alespoň dvou proměnných tvořících uzavřený okruh budou nulové – je nutné vyřadit z báze pouze jednu z nich a ostatní i nadále ponechat v bázi, například tak, že jim bude přiřazena dostatečně malá hodnota ε. Propustnost tras – maximální objem materiálu, který lze přepravit po dané trase. ü Pro optimální trasu je zřejmé, že její propustnost se rovná množství materiálu po ní převáženého. ü Pro neoptimální trasu lze propustnost charakterizovat jako maximální objem materiálu, který by bylo možno touto trasou přepravit, kdyby byla v řešení použita. Typy tras podle míry propustnosti: ü Vysoce propustné – relativně vysoká propustnost. ü Propustné – průměrné hodnoty. ü Málo propustné – propouštějí malé množství materiálu. Perspektiva tras – vliv použití trasy na hodnotu dopravních nákladů, hodnota, podle níž jsou testovány jednotlivé trasy v testu optimality. Typy tras podle míry perspektivy: ü Vysoce perspektivní – trasy, u nichž je zhoršení účelové funkce relativně malé. ü Perspektivní – trasy s větším zhoršením. ü Neperspektivní – trasy, u nichž dochází k velkému zhoršení hodnoty účelové funkce.
-9-
www.cz-milka.net
5. Vícekriteriální optimalizační modely Vícekriteriální lineární programování = vektorová optimalizace – modely, které mají množinu variant vyjádřenou soustavou omezujících podmínek a množinu kritérií vyjádřenou kriteriálními funkcemi. Postup řešení: ü Parciální optimalizace. ü Převod účelové funkce a omezující podmínky. ü Agregace účelových funkcí. ü Cílové programování. Dominance řešení – jsou-li xi a xj dvě přípustná řešení, potom říkáme, že řešení xi dominuje řešení xj, jestliže platí Cxi ≥ Cxj. Přípustné řešení xi je nedominovaným (efektivním) řešením úlohy, pokud neexistuje žádné jiné přípustné řešení, které by jej dominovalo. Ideální řešení – hypotetické nebo reálné řešení, reprezentované ve všech kritériích současně nejlepšími možnými hodnotami. Bazální řešení – hypotetické nebo reálné řešení, reprezentované nejhorším ohodnocením podle všech kritérií. Kompromisní řešení – řešení, které má od ideálního řešení nejmenší vzdálenost podle vhodné metriky. Prvky lineárního vícekriteriálního optimalizačního modelu: ü Vektor proměnných, který popisuje jednotlivé složky hledaného rozhodnutí. ü Omezující podmínky, které popisují reálná omezení hledaných rozhodnutí. ü Vektor účelových nebo kriteriálních funkcí, který popisuje cíle, kritéria hledaného rozhodnutí. Metody řešení úloh vícekriteriální optimalizace: ü Metody, při kterých se vychází z dílčí optimalizace a pak se vhodně zvolenými postupy pokračuje ve výpočtu vyhovujícího kompromisního řešení. ü Metody, kdy se jednotlivé kriteriální funkce pomocí vhodně zvoleného operátoru agregují do jediné globální kriteriální funkce, čímž se úloha převede na klasickou úlohu s jedinou účelovou funkcí. ü Metody využívající vztahu mezi definicí kritéria a vlastním omezením v modelu, využívá se možnosti zajistit požadovanou úroveň kritéria formou jeho převodu na omezující podmínku. ü Metody vedoucí k řešení specifických úloh cílového programování, pro každou kriteriální funkci se předem zadává požadovaná cílová úroveň. ü Interaktivní iterační metody vícekriteriální optimalizace, založeny na dialogu mezi vyhodnocovatelem a řešitelem. Dílčí optimální řešení – řešení, které splňuje všechny omezující podmínky a optimalizuje jedno z kritérií modelu, většinou se nejedná o kompromisní řešení a mají hlavně analytický význam. Agregace kriteriálních funkcí – sloučení všech kritérií pomocí vhodného operátoru do jediného kritéria. Základní formy agregace: ü Součinová či podílová ü Součtová či rozdílová Úprava kriteriálních funkcí na omezující podmínky – kteroukoli omezující podmínku lze formulovat jako kriteriální funkci a naopak. Požadavek maximalizace kritéria lze formuovat jako požadavkovou podmínku, požadavek minimalizace kritéria jako kapacitní podmínku. Cílové programování – postup výpočtu vychází z kompromisního řešení z minimalizace odchylek od cílových hodnot jednotlivých kritérií zadaných uživatelem. Způsoby vyjádření: ü Splnění cílů ohodnotit pomocí vah – váhy umožňují rozlišit důležitost odchylek od jednotlivých cílových hodnot. ü Lexikografická metoda – vyjádřit preference jednotlivých kritérií pomocí jejich pořadí na základě důležitosti. - 10 -
www.cz-milka.net
Metody řešení vícekriteriálních optimalizačních modelů: Metoda ALOP – založena na principu prohledávání množiny hodnot kriteriálních funkcí, výsledkem je trajektorie aspiračních úrovní a získání kompromisního řešení, spočívá v řešení vhodných pomocných modelů založených na myšlence cílového programování. Metoda STEM – použitelná pro situace, které umožňují kompenzaci hodnot kritérií.
- 11 -
www.cz-milka.net
6. Vícekriteriální analýza variant Vícekriteriální analýza variant – množina variant zadána ve formě konečného seznamu variant, které jsou ohodnoceny podle jednotlivých kritérií. Kritéria: ü Maximalizační – čím vyšší hodnota, tím lepší hodnocení. ü Minimalizační – čím nižší hodnota, tím lepší hodnocení. Typy informací: ü Žádná informace – preferenční informace neexistuje, přípustná pouze pro preference kritérií mezi sebou. ü Nominální informace – informace přípustná pouze pro preference kritérií mezi sebou, je vyjádřena pomocí aspiračních úrovní – nejhorších možných hodnot, při nichž může být varianta akceptována. ü Ordinální informace – vyjadřuje uspořádání kritérií podle důležitosti nebo uspořádání variant podle toho, jak jsou hodnoceny kritériem. Určí pouze pořadí. ü Kardinální informace – má kvantitativní charakter, v případě preference se jedná o váhy, v případě hodnocení variant podle kritéria o konkrétní nejčastěji číselné vyjádření hodnocení. Určí pořadí i o kolik je co lepší. Dominovaná varianta – předpokládejme, že všechna kritéria jsou maximalizační => varianta ai dominuje variantu aj, jestliže platí (yi1, yi2, …, yik) ≥ (yj1, yj2, …, yjk) a existuje alespoň jedno kritérium, že yi1 > yj1. Dominovaná varianta je ve všech ohledech stejná nebo horší než ta, která ji dominuje. Nedominovaná varianta = Paretovská varianta = efektivní varianta – varianta, která není dominovaná žádnou jinou variantou. Ideální varianta – varianta, která dosahuje ve všech kritériích nejlepší možné hodnoty. Je to hypotetická nebo reálná varianta, která dosahuje ve všech kritériích současně nejlepší možné hodnoty. Bazální varianta – varianta, která má všechny hodnoty kritérií nejhorší. Je to hypotetická nebo reálná varianta, jejíž ohodnocení je nejhorší podle všech kritérií. Kompromisní varianta – varianta, která má od ideální varianty nejmenší vzdálenost podle vhodné metriky. Prvky modelu vícekriteriální analýzy variant: ü Alternativy rozhodnutí – možná rozhodnutí. ü Kritéria podle nichž jsou varianty hodnoceny. ü Ohodnocení či preference variant podle jednotlivých kritérií. ü Informace o důležitosti jednotlivých kritérií. Grafické znázornění dominované varianty – polygonální zobrazení dominující varianty v sobě zahrnuje polygon dominované varianty. Grafické znázornění nedominované varianty – polygonální zobrazení dvou variant se protínají.
Metody řešení modelů vícekriteriální analýzy variant: Bodovací metoda – nejprve stanovíme bodovou stupnici, poté hodnocení každé z variant vyjádříme určitým počtem bodů. Při maximalizačním typu bude varianta ohodnocena tím větším počtem bodů, čím lépe je hodnocena, při minimalizaci je hodnocení opačné. Metoda pořadí – informaci můžeme vyjádřit pořadím variant. Pro maximalizační kritérium ohodnotíme nejlepší variantu číslem p, což je počet variant, druhou nejlepší číslem p-1 atd. Pro minimalizační kritérium postupujeme od čísla 1 k číslu p. Metoda párového porovnávání – vztah mezi každou dvojící hodnocených prvků, porovnávání se provádí pomocí Fullerova trojúhelníku. - 12 -
www.cz-milka.net Saatyho metoda – metoda kvantitativního párového porovnávání – slouží k určení vah kritérií v případě, že hodnotí pouze jeden expert. Metoda aspiračních úrovní – použitelná, pokud je známá nominální informace o kritériích a kardinální hodnocení variant podle jednotlivých kritérií. Určí se množina akceptovaných variant – připustíme pouze varianty, které splňují aspirační úrovně. ü Jsou-li požadavky příliš vysoké, bude množina akceptovatelných variant prázdná a je nutno snížit požadavky. ü Jsou-li požadavky příliš volné, bude množina akceptovatelných variant příliš rozsáhlá a je nutno zpřísnit požadavky. Metoda váženého součtu – je založena na výpočtu lineární funkce užitku, minimalizační kritéria se převedou na maximalizační, určí se ideální a bazální varianta, podle vzorce rij =
y ij − d j
hj − d j
se určí standardizovaná kriteriální
matice R, pro jednotlivé váhy se vypočte funkce užitku a varianty se seřadí sestupně podle hodnot. Metoda TOPSIS – posuzuje varianty z hlediska jejich vzdálenosti od ideální a bazální varianty.
- 13 -
www.cz-milka.net
7. Rozhodovací modely Rozhodování – obecný postup výběru jednoho z možných řešení, které při realizaci určitých podmínek zajistí nejlepší výsledek. Rozhodovací proces – proces volby nejvýhodnější rozhodnutí z několika možných alternativ rozhodnutí. Rozhodovací situace – proces volby z alespoň dvou možných variant (alternativ) řešení. Alternativa – možné rozhodnutí pro řešení problému, jednotlivé alternativy se navzájem vylučují, zvolí-li rozhodovatel jednu z nich, nemůže zvolit současně i jinou alternativu. Stavy okolností – situace, které ovlivňují výsledky jednotlivých alternativ, vyjadřují situace, za nichž se uskutečňuje rozhodnutí. Výplata – efekt, kdy je každá alternativa ohodnocena výsledkem, kterým je výnos či zisk nebo náklad či ztráta. Výplatní (rozhodovací) tabulka – matice rozměru m x n, jejímiž prvky jsou jednotlivé výplaty. Jsou maticovou formou rozhodovací ho modelu. Rozhodování z hlediska budoucích situací = stupeň jistoty: ü Rozhodování za podmínek jistoty – rozhodovateli je známo, jaký stav okolností nastane, má k dispozici informaci o tom, který stav okolností se realizuje, a informaci o výši výplat. Pravděpodobnost: P blízká 1,0 ü Rozhodování za podmínek nejistoty – rozhodovatel nemá žádnou představu o tom, jaký bude aktuální stav okolností. Pravděpodobnost: 0 < P < 1,0 ü Rozhodování za podmínek rizika – rozhodovatel neví s jistotou, jaký bude aktuální stav okolností, ale na základě různých poznatků a zpráv soudí, který stav okolností to pravděpodobně bude. Riziko je tím větší, čím menší je pravděpodobnost realizace určitého stavu. Pravděpodobnost: P blízká 0,0 Pravděpodobnost: ü Objektivní – určována na základě minulých statistických údajů. ü Subjektivní – vyjadřuje míru toho, že jev nastane, na základě osobního přesvědčení rozhodovatele.
Dominance alternativ: Dominance – převaha jedné alternativy nad druhou, je vztahem mezi dvěma alternativami, jedna alternativa je definována jako lepší a druhá jako horší. Formy dominance: ü Dominance podle výplat – nejostřejší forma dominance, založena na požadavku, aby dominující alternativa poskytovala všechny výplaty lepší nebo stejně dobré jako alternativa dominovaná, aby nejhorší výplata dominující alternativy byla lepší nebo stejná jako nejlepší výplata alternativy dominované. ü Dominance podle stavu okolností – slabší forma dominance, založena na požadavku, aby dominující alternativa poskytovala pro každý stav okolností výplaty lepší nebo stejné jako alternativa dominovaná. ü Dominance podle pravděpodobností – nejslabší a nejsložitější forma dominance, založena na kumulativní pravděpodobnosti.
Nejvýhodnější alternativa: Nejvýhodnější alternativa – alternativa slibující nejlepší výplatu. Nejvýhodnější alternativa při rozhodování za jistoty: ü EPC – očekávaná hodnota výplaty za podmínek jistoty - 14 -
www.cz-milka.net Nejvýhodnější alternativa při rozhodování za úplné nejistoty: ü Maximaxový přístup – rozhodovatel přesvědčený, že „odvážnému štěstí přeje“, je ochotný riskovat, pomíjí skutečnost, že stav okolností může být jiný a výsledek rozhodnutí podstatně odlišný, řešením je alternativa, která přinese maximální zisk. Rozhodovatel vybere maximální výplatu pro každou alternativu a z nich poté opět maximum. ü Waldovo kritérium = maximinový přístup – rozhodovatel je konzervativní pesimista přesvědčený, že „je lepší něco než nic“, hledá mezi nízkými výplatami a vybírá z nich tu nejméně špatnou. Rozhodovatel vybere minimální výplatu pro každou alternativu a z nich poté maximální. ü Hurwiczovo kritérium – založeno na očekávání nejlepších a nejhorších výsledků každé z nich, je stanoven takzvaný optimisticko-pesimistický index (míra optimismu). ü Savageovo kritérieum = princip minimaxové ztráty – posuzuje, kolik je možnost ztratit vzhledem k nejlepší výplatě, využívá pomocné matice ztrát výplat jednotlivých alternativ vzhledem k maximální výplatě pro každý stav okolností. V každém sloupci matice se vyhledají maximální výplaty a od nich se odečtou ostatní výplaty ve sloupci. ü Laplaceovo kritérium s použitím výplatní tabulky ü Laplaceovo kritérium s použitím tabulky ztrát Nejvýhodnější alternativa při rozhodování za rizika: ü EMV – očekávaná hodnota výplaty = Bayesův princip – představuje vážený aritmetický průměr výplat odpovídajících každé alternativě, kde vahami jsou pravděpodobnosti každého stavu okolností, používají se očekávané hodnoty a pomocí nich se odhadují důsledky rozhodnutí. ü EOL – očekávaná hodnota ztráty – představuje vážený aritmetický průměr ztrát odpovídajících každé alternativě, kde vahami jsou pravděpodobnosti každého stavu okolností. ü EMV = EOL – maximalizace výplat je ekvivalentní minimalizaci ztrát ü Pravděpodobnost dosažení aspirační úrovně – nejvýhodnější alternativa vybrána podle toho, že její výplata bude lepší než požadovaná úroveň výplat. Dodatečné informace: ü EVPI – očekávaná hodnota spolehlivé informace – dodatečná informace je spojena s dodatečnými náklady, rozhodovatel uvažuje, zda se mu náklady vyplatí. EVPI = EPC – EMV ü EMVS – očekávaná hodnota výplaty při uplatnění dodatečné výběrové informace ü EVSI – očekávaná hodnota výběrové informace – představována zpřesněným vektorem rizika. EVSI = EMVS – EMV.
Rozhodovací a pravděpodobnostní stromy: Rozhodovací strom – grafická forma rozhodovacího modelu. Popisuje průběh rozhodovací situace pomocí prostředků teorie grafů. Rozhodovací stromy obsahují uzly a hrany zobrazující postup rozhodování. Uzly: ü Rozhodovací – zobrazují se čtverečky. ü Situační – zobrazují se kroužky. Hrany: ü Z rozhodovacích uzlů – zobrazují alternativy. ü Ze situačních uzlů – zobrazují stavy okolností. Vlastnosti rozhodovacích stromů: ü Ukazují důsledky a kombinace okolností, které mohou nastat, když zvolíme určitou cestu. ü Nutí promýšlet každou variantu do všech důsledků. ü Podněcují k vyhledávání faktorů nejistoty ovlivňujících důsledky jednotlivých variant. Pravděpodobnostní strom – zobrazuje průběh realizace rizikového rozhodnutí.
- 15 -
www.cz-milka.net
8. Teorie her Teorie her – zabývá se matematickým zobrazením a řešením konfliktních situací, kterých se účastní alespoň dva účastníci s různými nebo dokonce protichůdnými zájmy. Konfliktní situace – všechna situace, ve kterých jde o střet zájmů účastníků konfliktu. Antagonistický konflikt – dosažní cíle jedním z účastníků zamezí pozitivnímu výsledku ostatních, úspěch jednoho z hráčů je možný pouze na úkor úspěšnosti ostatních hráčů. Neantagonistický konflikt – všichni účastníci mají možnost více či méně realizovat svoje cíle. Hráč – každý účastník konfliktu v teorii her, jedná se o souhrn určitých zájmů a cílů, ne o určitou osobu. Inteligentní hráč – hráč, který je na výsledku hry zainteresován a hraje tak, aby vyhrál. Neinteligentní hráč = příroda – hráč, který se hry účastní, ale výsledek hry ho nezajímá.. Hra – model konfliktní situace. Partie – jednotlivá část hry. Strategie – určitý způsob hráčova chování v průběhu jedné partie hry, posloupnost určitých kroků v průběhu hry. Tah – určitý krok v průběhu hry, je součástí strategie. Výplata hry = platba hry – výsledek hry jednotlivých hráčů v závislosti na jimi vybraných strategiích, každý hráč volí takovou strategii, aby maximalizoval svůj zisk. Model hry v rozvinutém tvaru – zobrazuje strategie jako posloupnost tahů, lze zobrazit pomocí stromu, kdy hrana představuje tah, úroveň hran možné tahy jednoho hráče a uzel zobrazuje pozici hry. Model hry v normálním tvaru – pro každého hráče je formulována množina jeho strategií.
Maticové hry: Maticové hry – hry dvou hráčů s konečným počtem strategií a nulovým součtem. Nulový součet – součet výplat obou hráčů je roven nule. Optimální strategie – dva hráči, kteří hrají cílevědomě, se snaží maximalizovat svou výplatu, první hráč maximalizuje svojí výhru a druhý hráč minimalizuje svoji prohru. Řešení hry v oboru čistých strategií – hráč dosáhne svého cíle pouze pomocí jediné své strategie. ü Maximinová strategie – výběr nejlepšího z nejhorších výsledků, zaručená minimální výhra prvního hráče, odpovídající výplata je dolní cena hry. ü Minimaxová strategie – odpovídající výplata je horní cena hry. Maticová hra má řešení v oboru čistých strategií právě tehdy, když má sedlový bod. Řešení hry v oboru smíšených strategií – hráč nemůže řídit pouze jedinou ze svých strategií, ale musí najít způsob používání strategií v jednotlivých partiích. Smíšená strategie je charakterizována vektorem pravděpodobností, jeho každý prvek vyjadřuje pravděpodobnost použití příslušné čisté strategie hráče. Věta von Neumannova – každá maticová hra má řešení v oboru smíšených strategií. Maximinová i minimaxová strategie vede ke stejnému výsledku
Hry proti přírodě: - 16 -
www.cz-milka.net Hry proti přírodě = hry s neinteligentním hráčem – zvláštní případ maticových her. Funkci jednoho z hráčů přebírá příroda, tedy hráč, kterému je výsledek hry lhostejný. Strategii volí pouze inteligentní hráč. ü Rozhodnutí – strategie inteligentního hráče. ü Souhrn objektivně existujících okolností – strategie přírody. Řešení her za podmínek rizika – riziko je představováno pravděpodobnostním vektore, jehož jednotlivé složky jsou pravděpodobnostmi uplatnění jednotlivých strategií přírody. Kritéria pro výběr nejlepší strategie inteligentního hráče: ü Bayesův princip Řešení her za podmínek nejistoty – inteligentní hráč nemá žádné vodítko pro odhad chování přírody. Kritéria pro výběr nejlepší strategie inteligentního hráče: ü Waldovo kritérium – situace posuzována jako hra inteligentních hráčů, princip zaručené, byť minimální výhry, inteligentní hráč volí maximinovou strategii, pojišťuje se proti všem nejhorším situacím. ü Savageovo kritérium – hodnotí strategie inteligentního hráče z hlediska ztrát, ke kterým by došlo, jestliže by nebyla použita nejlepší strategie pro každou strategii přírody. ü Bernoulli-Laplaceovo kritérium – vychází při volbě strategie inteligentního hráče z toho, že příroda svoje strategie používá rovnoměrně, tedy že jejich pravděpodobnosti (četnosti) použití jsou stejné. ü Hurwitzovo kritérium – založeno na očekávání nejlepších a nejhorších výsledků každé strategie, nejprve potřeba stanovit takzvaný optimisto pesimistický index t.
- 17 -
www.cz-milka.net
9. Simulace Generátor náhodných čísel – výběr náhodných čísel z celku. Typy: ü Selekce ü Sekvence ü Iterace
- 18 -
