Kvantitativní metody v rozhodování Každý manažer je ve své denodenní praxi vystaven řadě rozhodovacích situací a problémů, které může analyzovat ze dvou hledisek: ► buď na základě znalostí a zkušeností (kvalitativní analýza) ► nebo pomocí údajů v numerické podobě a jejich exaktního matematického zpracování (kvantitativní analýza), viz schéma. KVALITATIVNÍ ANALÝZA založená na úsudku a zkušenostech manažera KVANTITATIVNÍ ANALÝZA založená na matematických technikách Souhrn a vyhodnocení Rozhodnutí Kvantitativní metody v rozhodování Ve specifických situacích je samozřejmě možné provádět jen jednu ze zmíněných analýz. Spolehneme-li se však pouze na kvalitativní analýzu bez číselných propočtů, závisí výsledek do značné míry na dobrém úsudku manažera. Naopak přílišná důvěra v numerické výsledky může být zavádějící: každé číselné řešení je přesné jen do té míry, jak přesně byl zkonstruován model. Navíc kvantitativní analýza problému může být zdlouhavá a neefektivní v situaci, kdy je třeba přijmout rozhodnutí rychle. Kdy by tedy měl manažer přizvat na pomoc kvantitativní metody? Zejména, je-li problém: ► složitý, kdy specialisté mohou manažerovi pomoci prostřednictvím simulace reality vhodným modelem ► velmi důležitý, například jde-li o velké peníze a manažer chce mít pro rozhodování solidní podklady ► nový, chybí zkušenosti s řešením obdobných problémů ► opakovaný, takže použití ověřených kvantitativních procedur šetří čas i prostředky Ekonomicko - matematický model Modelem rozumíme určité zobrazení reálného systému. Nikdy nejde o dokonalý obraz skutečnosti, to ani není žádoucí! Správně zkonstruovaný model musí vystihovat pouze ty vlastnosti, které jsou z hlediska řešení problému důležité. Zahrneme-li do modelu všechny detaily, bude složitý, špatně řešitelný a nepřehledný. Na druhou stranu při přílišné snaze o zjednodušení můžou být opomenuty některé významné skutečnosti a vazby. Při modelování je klíčové právě dobré nastavení vztahu mezi reálným světem a modelem. Manažer by měl umět problém dobře ► formulovat tak, aby bylo možné k jeho řešení využít kvantitativních metod, a následně výsledky ► interpretovat a implementovat do praxe. S vlastním řešením matematického modelu mohou pomoci experti či specializovaný software. I při možnosti využití výpočetní techniky je však dobré mít přehled o dostupných metodách, abychom v konkrétní situaci uměli vybrat vhodný algoritmus a nastavit jeho parametry. Co to je "optimalizace"? Při optimalizaci řešíme problém výběru "nejlepšího řešení" mezi všemi "možnými řešeními". V každé konkrétní úloze je třeba pojmy uvedené v uvozovkách specifikovat. Všechna možná řešení budeme dále popisovat pomocí množiny M , kterou nazveme množina přípustných řešení, a míru kvality řešení budeme vyjadřovat prostřednictvím funkce / :M->1, která se označuje jako cílová nebo kriteriální nebo též účelová funkce. Zadání optimalizační úlohy pak zní: Najděte prvek x* e M takový, že platí: f(x*) > /(x), Vx e M, Pozn.: Maximalizační úlohu "/ —>• max"\ze snadno převést na minimalizační úlohu "-/ —>• min". Příklady optimalizačních úloh v ekonomii: ► Optimalizace výrobního programu ► Optimalizace portfolia ► Optimální rozdělení práce a řazení pracovních operací ► Minimalizace distribučních nákladů, plánování rozvozních tras a umístění distribučních center ► Minimalizace doby realizace při řízení projektů ► Optimální řízení zásob Co je to "optimalizace"? Z hlediska přípustné množiny rozlišujeme dva typy optimalizačních úloh: ► Je-li přípustným řešením každý bod x n-rozměrného Euklidova prostoru Rn, tj. M = Rn, hovoříme o nepodmíněné optimalizaci, resp. o volných extrémech. Postup analytického řešení takových úloh je znám ze základního kurzu matematiky ► V opačném případě, tedy je-li M cRn hovoříme o vázaných extrémech. Jejich existenci pro spojitou funkce na omezené uzavřené množině zaručuje Weierstrassova věta. Možnosti analytického řešení složitějších úloh (např. když je v úloze mnoho proměnných, komplikovaná hranice přípustné množiny nebo dostaneme nelineární rovnice pro určení stacionárního bodu) jsou však omezené. Proto byly vyvinuty speciální metody pro řešení určitých typů optimalizačních úloh. Matematické programování Pojem matematické programování označuje souhrn metod sloužících k optimalizaci předem definovaného kritéria vyjádřeného jako funkce n proměnných při současném splnění omezujících podmínek zadaných zpravidla ve formě rovností a nerovností. Úlohy matematického programování můžeme rozdělit na úlohy ► lineárního programování (dále jen LP), kdy účelová funkce i omezující podmínky jsou lineárními funkcemi proměnných ► nelineárního programování (NLP), když výše uvedená podmínka není splněna. Speciálním případem NLP je kvadratické programování, kdy účelová funkce je polynom druhého stupně, ale omezující podmínky jsou lineární. Dále se zaměříme hlavně na modely LP, ty jsou jednoznačně nejrozšířenější. Proč? Hodně reálných problémů lze dobře formulovat jako úlohu LP, pro jejich rychlé řešení jsou dostupné programové prostředky, atp. V praxi se sice běžně vyskytují nelineární vztahy (např. neproporcionalita: když cena není konstantní, tak příjem není přímo úměrný prodanému množství, neaditivita: objem roztoku není roven součtu objemů výchozích látek, apod.), avšak kvůli nepoměrně větší složitosti postupů NLP bývá často výhodnější použít aproximaci lineárním modelem. ineární programování Při formulaci úlohy matematického programování je třeba vycházet z dobře popsaného ekonomického modelu. Je tedy třeba znát: ► cíl, jehož chceme dosáhnout (tedy zvolit kritérium: zisk nebo náklady nebo objem výroby, atd. a určit, zda se jej budeme snažit minimalizovat nebo maximalizovat) ► řiditelné vstupy, tj. jaké proměnné můžeme ovlivňovat za účelem dosažení cíle (počet vyrobených kusů různých typů produktu, velikost převáženého nákladu, atd.) ► neřiditelné vstupy neboli omezení, která nás limitují (ceny nakupovaných surovin, dispoziční množství zdrojů, kapacita zařízení, atd.) Neřiditelné vstupy (externí limity) Řiditelné vstupy (rozhodovací proměnné) Řešení (hodnoty proměnných) Úloha LP - Optimalizace výrobního programu Veškerý další výklad problematiky lineárního programování bude ilustrován na následující optimalizační úloze převzaté z knihy Josefa Jablonského "Operační výzkum, Kvantitativní modely pro ekonomické rozhodování": Balírny a pražírny kávy DE, a.s. plánují výrobu dvou směsí Mocca a Standard. Od dodavatelů mají k dispozici tři druhy kávových bobů Kí, K2 a K3 v kapacitě 40, 60 a 25 tun. Technologický postup určující skladbu směsí shrňme v tabulce. Komponenta Mocca Standard Kapacita [t] Ki 0,5 0,25 40 K2 0,5 0,5 60 K3 0,25 25 Vzhledem k výrobním nákladům a prodejní ceně směsí byl vykalkulován zisk, který činí 20000 Kč resp. 14000 Kč na jednu tunu směsi Mocca resp. Standard. Management firmy chce naplánovat produkci tak, aby její zisk byl maximální. Formulace úlohy optimalizace výrobního programu Označíme - li xi množství tun směsi Mocca a x2 množství tun směsi Standard, můžeme problém formulovat matematicky jako úlohu maximalizovat účelovou funkci: z = 20000xi + 14000x2 za podmínek 0,5xi + 0,25x2 <40 0,5xi + 0,5x2 < 60 0,25x2 <25 Xi, x2 > 0 Je možný též maticový zápis úlohy: z = cT x —^ max za podmínek A x < b, x > 0, kde x = (xi, x2)T je vektor strukturních proměnných, c = (20, 14) je vektor cenových koeficientů v účelové funkci, b = (40,60,25)T je vektor kapacitních Matematická formulace obecné úlohy LP Obecnou úlohu LP pro n proměnných a m omezení můžeme zapsat takto: minimalizuj (maximalizuj) funkci ^ = EýLi cjxj za podmínek aijXj ? bh i = 1,... m Xj > 0, y = 1,... n, kde na místě symbolů ? můžou být libovolná relační znaménka <,=,>. Omezení se uvádějí v takové podobě, aby pravé strany b\ byly nezáporné. Je dobré si uvědomit, že jednu úlohu lze formulovat různými způsoby. Snadno lze převést úlohu minimalizační na úlohu maximalizace funkce -z = Y^\=\ (-cj)xj- Omezení ve formě rovnosti lze přepsat jako dvě nerovnice typu < a > s týmiž koeficienty i pravou stranou jako původní rovnice. Převod omezení ve formě nerovnosti na rovnici se zase řešení zavedením dodatečných proměnných, jak si dále ukážeme. Grafické řešení úlohy LP Úlohy obsahující pouze dvě proměnné lze řešit graficky. Ukažme si postup pro naši úlohu o kávě. A Nejvyšší izokvanta se dotýká množiny M v bodě x Základní věta lineárního programování Přípustná množina M je vymezena obligátními podmínkami (nezápornost) a omezujícími podmínkami A • x < b. Ty lze vyjádřit pomocí rovností: 0,5xi + 0,25x2 + x3 =40 0,5xi + 0,5x2 + x4 =60 0,25x2 + x5 =25 Proměnné x3, x4, x5 označujeme jako přídatné a lze je ekonomicky interpretovat jako nevyužitou kapacitu jednotlivých surovin. Soustava obsahuje m rovnic pro m + n proměnných, může mít obecně nekonečně mnoho řešení. Takové řešení soustavy, pro které je n proměnných rovno nule, nazýváme základní (Ve 2D odpovídají základní řešení průsečíkům hraničních přímek jednotlivých nerovností.) Nenulové proměnné pak označujeme jako základní, nulové jako nezákladní. Pozor! Ne každé základní řešení je přípustné. Přípustná základní řešení odpovídají krajním bodům M. V našm příkladě je m = 3, n = 2; celkem dostaneme ? základních řešení, z toho ? přípustných. Hlavní věta lineárního programování: Jestliže má úloha optimální řešení, pak má také optimální základní řešení. mplexová tabulka Uvedenou soustavu rovnic můžeme zapsat maticově jako (A, I) • (x^, x2, x3, x4, x5)T = b, kde I je jednotková matice řádu m = 3. Každou takovou soustavu m rovnic pro m + n neznámých, kde matice levé strany obsahuje všechny sloupce jednotkové matice řádu m, nazveme soustavou v kanonickém tvaru. Snadno vidíme jedno z řešení takové soustavy: x^ = 0. x2 = 0, x3 = £>i = 40, x4 = b2 = 60, x5 = b3 = 25, jde dokonce o řešení základní. Znázorněme vše do přehledné tabulky: zákl. prom. Xi x2 x3 x4 x5 bi x3 xa x5 1 1 2 4 1 1 2 2 o l 1 0 0 0 1 0 0 0 1 40 60 25 zj -20 -14 0 0 0 0 Poslední řádek odpovídá účelové funkci v tzv. anulovaném tvaru, původní vyjádření z = 20xi + 14x2 [v tis. Kč] jsme převedli na tvar z - 20^ - 14x2 - 0x3 - Oxa - 0x5, pro výchozí základní řešení dostaneme hodnotu účelové funkce z = 0, viz pravý dolní roh tabulky. Uvedené schéma nazveme výchozí simplexovou tabulkou úlohy. mplexová metoda Simplexová metoda je iterační postup k nalezení optimálního řešení úlohy LR Úvodním krokem je nalezení výchozího základního řešení. U úloh obsahujících pouze nerovnice typu "<"je tento krok díky přídatným proměnným jednoduchý, u jiných typů úloh jej získáme řešením počáteční úlohy minimalizace pomocných proměnných vyjadřujících porušení omezujících podmínek, hovoříme pak o dvoufázové simplexové metodě. Dále metoda v jednotlivých krocích vypočte nové základní řešení s lepší hodnotou účelové funkce. Po konečném počtu kroků se nalezne řešení s nejlepší hodnotou účelové funkce (podle základní věty LP jde pak o optimální řešení celé úlohy) nebo se zjistí, že takové řešení neexistuje. Na obrázku ukažme schematické znázornění postupu ve 3D. optimum výchozí bod Nelze se přesunout do žádného lepšího bodu, byl nalezen bod optima Iterační krok simplexové metody Čísla zy v spodním řádku simplexové tabulky nazýváme redukované ceny. Ukazují, jak se změní účelová funkce při přechodu k novému základnímu řešení. Stane-li se nezákladní proměnná xk proměnnou základní, tj. změní-li hodnotu z 0 na t > 0, bude přírůstek účelové funkce Az = -t • zk. Při maximalizaci chceme, aby toto Az bylo kladné, tj. aby zk < 0. Pokud jsou všechny redukované ceny nezáporné , již nejde zvýšit hodnotu účelové funkce, řešení je optimální. Jinak vybereme xk, pro které je zk nejmenší (říkáme mu vstupující proměnná), a nahradíme s ním některou základní (vystupující) proměnnou. Tedy pro naši simplexovou tabulku zákl. prom. X1 x2 x3 x4 x5 Pí x4 x5 1 1 2 4 1 1 2 2 o l 1 0 0 0 1 0 0 0 1 40 60 25 zj -20 -14 0 0 0 0 bude vstupující proměnnou xi, protože -20 je nejmenší hodnota na posledním řádku. Iterační krok simplexové metody Volba vystupující proměnné vychází z nutnosti zachovat přípustnost řešení, tedy nezápornost všech základních proměnných. Zapišme tuto podmínku pro nové hodnoty původních základních proměnných x3, x4, X5, jestliže nově = t.Z platnosti rovnic: x3 =40- \t> 0 x4 = 60 - \\> 0 x5 = 25 - 0 > 0 Zřejmě největší možné takové t je t = 80, pro ně dostaneme x3 = 0. To se nyní stane vystupující proměnnou. Tabulku přepočteme elementárními úpravami tak, abychom vlevo nahoře dostali jedničku a pod ní samé nuly. zákl. prom. x^ x2 x3 Xa x5 Pí x^ 1 1 2 2 0 0 80 xA 0 1 4 -1 1 0 20 x5 0 1 4 0 0 1 25 zj 0 -4 40 0 0 1600 Dostali jsme novou tabulku. Další iterační krok Redukovaná cena z2 = -4 naznačuje, že lze ještě zvýšit účelovou funkci, jestliže zvolíme x2 jako vstupující. zákl. prom. x^ X2 X3 Xa x5 ßi x^ 1 1 2 2 0 0 80 Xa 0 1 4 -1 1 0 20 X5 0 1 4 0 0 1 25 ZJ 0 -4 40 0 0 1600 Nejvyšší hodnotou t, pro kterou můžeme položit x2 = ř, je /77//7{2.80, 4.20, 4.25} = 80. Vyjdou nám pak nové hodnoty základních proměnných x^ = 80 - \\ = 40, x4 = 20 - \t = 0, x5 = 25 - \t = 5. Tedy x4 se stane nezákladní, Dostali jsme novou tabu e vystupující proměnnou. zákl. prom. x^ x2 X3 Xa x5 ßi x^ 1 0 4 0 0 40 x2 0 1 -4 4 0 80 x5 0 0 1 -1 1 5 ZJ 0 0 24 16 0 1920 ku. Ukončení výpočtu Ve výsledné tabulce jsou již všechny redukované ceny nezáporné: zákl. prom. x^ x2 x3 Xa x5 Pí x^ 1 0 4 0 0 40 x2 0 1 -4 4 0 80 x5 0 0 1 -1 1 5 zj 0 0 24 16 0 1920 Nelze tedy již zvýšit hodnotu účelové funkce, maximální zisk je 1920 tisíc. Nezákladní proměnné jsou x3, x4, ty budou tedy nulové. Hodnoty základních proměnných vyčteme z tabulky: Xi = 40, x2 = 80, x5 = 5. To nám říká, že optimálně máme vyrobit 40 tun směsi Mocca a 80 tun směsi Standard, přičemž zcela spotřebujeme první dvě suroviny a zbyde nám pět tun třetí suroviny. Pozn.: Pokud by dole zbyla nezáporná redukovaná cena, ale ve sloupci nad ní by už žádné číslo nebylo > 0, tak je úloha neomezená. Pro minimalizační úlohu by se obrátila role znamének v dolním řádku - vybírali bychom vstupující proměnnou podle nejvyšší redukované ceny a výpočet bychom ukončili až by všechny redukované ceny byly < 0. Dvoufázová simplexová metoda Vyskytují-li se v úloze i jiná omezení než nerovnosti typu "<", je nutné nejprve najít výchozí přípustné základní řešení. K tomu slouží první fáze simplexové metody. Ukažme si ji na ilustračním příkladě. z = xi - x2 —>> min za podmínek x^ > 2 x2 > 2 5xi + 10x2 < 50 Omezující podmínky lze opět zavedením nezáporných přídatných proměnných převést na rovnosti: x^ -x3 = 2 x2 -x4 = 2 5xi + 10x2 +x5 = 50 Bohužel nejde o soustavu v kanonickém tvaru, protože koeficienty u x3 a x4 nejsou = 1. Proto přičteme k levým stranám příslušných omezení ještě nezáporné pomocné proměnné yi, y2 a tyto proměnné již budou spolu s x5 základními. Pro výchozí bod platí yi = y2 = 2, x5 = 50, což však není přípustné pro původní úlohu. Dvoufázová simplexová metoda K získání přípustného řešení původní úlohy je třeba zajistit, aby yi = y2 = 0. To lze pomocí minimalizace pomocné účelové funkce z' = yi + y2. (jestliže má tato funkce minimum >0, pak výchozí úloha nemá žádné přípustné řešení). Vyjádřeme z' pomocí nezákladních proměnných a výsledné redukované ceny zapišme do simplexové tabulky: z' = (2 - + x3) + (2 - x2 + x4) = 4 - - x2 + x3 + x4 zákl. prom. x2 X3 Xa x5 /2 Pi /i 1 0 -1 0 0 1 0 2 Y2 0 1 0 -1 0 0 1 2 X5 5 10 0 0 1 0 0 50 1 1 -1 -1 0 0 0 4 Jako vstupující proměnnou můžeme zvolit xi nebo x2, zvolme nejprve tu druhou. zákl. prom. x^ x2 X3 Xa x5 /2 Pi x^ 1 0 -1 0 0 1 0 2 x2 0 1 0 -1 0 0 1 2 x5 0 0 5 10 1 -5 -10 20 0 0 0 0 0 -1 -1 0 Nalezli jsme minimum pomocné fce z' = 0, můžeme tedy zahájit 2. fázi: vynecháme yi, y2 a z bodu [2,2,0,0,20] minimalizujeme funkci z = x\ - x2 = (2 - x3) - (2 - xa) = -x3 + x4, jejíž redukované ceny přidáme Dvoufázová simplexová metoda Druhou fázi již dořešíme běžným způsobem: zákl. prom. x^ x2 X3 Xa x5 Pi x^ 1 0 -1 0 0 2 0 1 1 2 0 1 10 4 Xa 0 0 1 2 1 1 10 2 zi 0 0 3 2 0 1 " 10 -2 Dostali jsme optimální tabulku, je tedy xi = 2, x2 = 4, zopŕ = -2. Dvoufázová simplexová metoda Celý postup v grafickém znázornění: 1 -.-1-.-1-1-■-1-■-1-.-1-^4 1 \2 3 4 5 6 7 8 Po jednom kroku dosáhneme optima v bodě [xi, x2] = [2,4]. Dualita úloh LP Na původní úlohu lze nahlížet i jiným způsobem. Předpokládejme, že bychom suroviny nezpracovávali, ale rovnou prodali. Otázka zní, kdy se nám tento přímý prodej zdrojů vyplatí. To bude samozřejmě záviset na zisku z prodeje jednotlivých zdrojů - vyjádříme jej pomocí tzv. duálních proměnných, které označíme w-, (v naší úloze máme tři druhy kávových bobů, tedy / = 1,2,3). Můžeme pak formulovat tzv. duální úlohu k výchozímu problému: Jaký je minimální zisk z prodeje zdrojů, při kterém se nám nevyplatí vyrábět ani jeden výrobek? Tedy minimalizujeme zisk z prodeje zdrojů gf(w) = 40i/i/i + 6O1/1/2 + 25w3 za omezení, že se nevyplatí vyrábět ani směs Mocca ani Standard, tedy, že platí nerovnosti 0,5i/i/i + 0,5w2 > 20, 0,5i/i/i + 0,25w2 + 0,5w3 > 14. Při použití označení zavedeného výše, kde c = (20, 14) je vektor zisků z prodeje směsí, b = (40,60,25)T je vektor kapacit surovin a A strukturní matice, můžeme porovnat maticový zápis původní, tzv. primární úlohy a úlohy duální: primární úloha duální úloha maximalizovat z = cT x minimalizovat g(w) = bT w za podm. A x < b, x > 0, za podm. AT • w > c, w > 0 Dualita úloh LP Obecně lze pro formulaci duální úlohy k úloze LP použít následující pravidla: Maximalizační úloha Minimalizační úloha primární duální duální primární omezení typu < nezáporná proměnná omezení typu > nekladná proměnná omezení typu rovnice proměnná neomezená nezáporná proměnná omezení typu < nekladná proměnná omezení typu > proměnná neomezená omezení typu rovnice Dualita úloh LP Vztah mezi vzájemně duálními úlohami lze vyjádřit větou o dualitě: Existuje-li optimální řešení jedné z duálně sdružených úloh, potom existuje i optimální řešení druhé úlohy a navíc optimální hodnoty účelových funkcí se sobě rovnají! Z této věty logicky plyne, že pokud jedna ze sdružených úloh optimální řešení nemá, tak jej nemůže mít ani úloha druhá, lze ukázat, že pokud jedna úloha nemá žádné přípustné řešení, tak druhá úloha je neomezená a naopak. Dalším důsledkem je tzv. slabá věta o dualitě: Hodnota účelové funkce maximalizační úlohy je vždy menší nebo rovna hodnotě účelové funkce minimalizační úlohy. Dále platí tzv. věta o rovnováze: Je-li /c-tá proměnná v řešení primární úlohy nenulová (tedy kladná), pak je /c-tá podmínka v řešení duální úlohy splněna jako rovnost. Říkáme, že je /c-tá podmínka aktivní. Postoptimalizační analýza Analýza citlivosti primární úlohy zkoumá, do jaké míry ovlivní případné změny vstupních údajů původní optimální řešení. Zejména nás zajímají efekt při změně zisku z jednotlivého výrobku, případně při změně v jednotlivém kapacitním omezení. To lze zjistit bez nutnosti přepočítávat celou úlohu znovu. Určujeme tzv. intervaly stability, a to pro: ► koeficienty účelové funkce Ck, kdy zjišťujeme, v jakém rozmezí hodnot můžeme měnit jednotlivé Cr (při zachování hodnot ostatních koeficientů) tak, aby nedošlo ke změně optimálního řešení, ► kapacitní omezení £>,, kdy zjišťujeme v jakém rozmezí se může jednotlivé b\ pohybovat, aby nedošlo ke změně množiny základních proměnných, tedy byla zachována množina aktivních omezení. Pro manažerské rozhodování je důležité zjistit, jaký je vliv změny kapacitního omezení na hodnotu účelové funkce. To nám prozradí optimální hodnoty duálních proměnných w-,. Tyto hodnoty se nazývají stínové ceny a vyjadřují hodnotu, o kterou se změní hodnota účelové funkce, jestliže zvýšíme kapacitu / - tého zdroje b\ o jednotku (za předpokladu že se touto změnou nedostaneme mimo interval stability). Postoptimalizační analýza - intervaly stability pro ceny Vlastní určení intervalů stability není složité a bývá nedílnou součástí softwarových výstupů. Dále si ukážeme grafickou interpretaci a odvození intervalů stability pro koeficienty účelové funkce v našem jednoduchém příkladě optimalizace výroby kávy. Na obrázku je vidět, jak lze optimální izokvantu účelové funkce naklánět, aby stále bylo optimálním řešením x*. A 100 80 20 40 80 Postoptimalizační analýza - intervaly stability pro ceny Mezní hodnoty naklonění určíme tak, že přímka bude procházet body x* = [40,80],4= [20,100] resp. x* = [40,80], B= [80,0]. Pro její směrnici q tedy musí platit nerovnosti Směrnici původní izokvanty z = C1X1 + c2x2 vyjádříme jako q = přičemž původní hodnoty koeficientů jsou Ci = 20, c2 = 14. Interval stability pro Ci tedy zjistíme po dosazení q = do nerovností: -2 < < -1, tj. Ci g (14,28). Analogicky pro c2 získáme interval stability dosazením q = ^ do nerovností: -2 < ^ < -1 a dostaneme c2 g (10,20). 2 80-0 40-80 80-100 40-20 Postoptimalizační analýza - intervaly stability pro kapacity Ještě si ukažme ve stejné úloze grafické odvození intervalů stability pro pravé strany omezení. Na obrázku je vidět, jak můžeme posunout hranici prvního omezení, aby stále optimální řešení leželo v průsečíku hraničních přímek prvního a druhého omezení. \ x2 x \\ \ \ \ \ \\ \ 120N 100 \\ * \ \ x \\\ x M \ \ \ V \ \c 20 80\ 120\ \ \ Postoptimalizační analýza - intervaly stability pro kapacity Původní rovnice hraniční přímky prvního omezení byla 0,5xi + 0,25x2 = 40. Její pravou stranu £>i můžeme změnit maximálně tak, že by přímka procházela bodem A, resp. bodem C. Dosazením souřadnic bodu A = [20,100] do levé strany omezení dostaneme 0,5 • 20 + 0,25 • 100 = 35, což je dolní hranice pro £>i. Dosazením souřadnic bodu C = [120,0] do levé strany omezení dostaneme 0,5 • 120 + 0,25 • 0 = 60, což je horní hranice pro ůi. Dostáváme tedy interval stability £>i: e (35,60). Podobně obdržíme intervaly stability pro ostatní omezení. Tyto intervaly jsou důležité při rozhodování o nákupu dalších zdrojů: pokud je stínová cena daného omezení větší než nákupní cena příslušné suroviny, vyplatí se v rozmezí intervalu stability navyšovat kapacitu. A jak určíme stínovou cenu pro £>i ? Změnou na £>i + A dostaneme nový bod optima jako průsečík přímek o rovnicích 0,5xi + 0,25x2 = 40 + A, 0,5x^ + 0,5x2 = 60, tedy bod o souřadnicích [40 + 4A, 80 - 4A]. V tomto bodě je pak hodnota účelové funkce z = 20(40 + 4A) + 14(80 - 4A) = 1920 + 24A. Stínová cena je 1/1/1 = 24. Stínové ceny najdeme v optimální tabulce pod sloupci přídatných proměnných! Speciální úlohy lineárního programování Mezi typickými úlohami LP lze najít úlohy s nějakými speciálními vlastnostmi. Tyto vlastnosti se mohou týkat struktury modelu, zejména strukturní matice, typu proměnných, dále způsobů řešení, apod. Významnou skupinu takových speciálních úloh tvoří distribuční úlohy. Z těchto úloh představíme dopravní problém, přiřazovací problém a okružní dopravní problém. Další problémy (kontejnerový či vícestupňový dopravní problém, úloha o pokrytí, stanovení řezných plánů apod.) viz literatura. Úlohy, ve kterých některé proměnné mohou nabývat pouze hodnot z množiny celých čísel souhrne nazýváme úlohami celočíselného programování. Proměnné v těchto úlohách zpravidla vyjadřují počty nedělitelných kusů, případně nabývají pouze hodnot 0 a 1, kterými se kóduje absence či přítomnost určitého spojení mezi zadanými objekty. Specifikům celočíselných úloh a základním přístupům k jejich řešení se budeme později také věnovat. V neposlední řadě stručně zmíníme alternativní přístup k řešení úloh LP, kdy je možné současně optimalizovat více kritérií, a to cílové programování. Dopravní problém - formulace V dopravní úloze se typicky řeší rozvržení rozvozu z dodavatelských míst k odběratelům tak, aby byly minimalizovány náklady související s rozvozem. Je definováno m dodavatelských míst - zdrojů Vu V2l ..., Vms omezenými kapacitami a\,a2, ..., am a dále máme n cílových míst - odběratelů Si, S2, ..., Sn se stanovenými požadavky £>i, b2, ..., bn. Každá dvojice zdroj-cíl je nějak ohodnocena, typicky například náklady na přepravu jednotky zboží. Tyto náklady označíme c,y, / = 1,..., m, j = 1,..., n. Cílem je naplánovat objemy přepravy mezi jednotlivými zdroji a cíli ( označíme je X/y, / = 1,..., /77, j = 1,..., a?) tak, aby byly uspokojeny požadavky odběratelů a nebyly překročeny kapacity zdrojů.Úloha tedy obsahuje m • n proměnných x#, pro něž minimalizujeme účelovou funkci z = 5Xi Eyti QjXij za podmínek Y!j=i Xij 0, / = 1, . . . , A77, j = 1,..., n Účelová funkce i omezení jsou lineární, jde tedy o úlohu LP. Dopravní problém - metody řešení I když jde o úlohu LP, kterou lze řešit simplexovou metodou, vzhledem k velkému počtu proměnných a speciální struktuře matice omezení jsou většinou praktičtější jiné metody (jde o tzv. řídkou matici - obsahuje hodně nul, navíc zbylé jedničky mají blokovou strukturu). Příklad: Pro reálnou úlohu s 20 zdroji a 300 zákazníky máme ? proměnných a ? omezení, to znamená 1920000 polí v simplexové tabulce, což zabere cca II MB operační paměti Ze simplexové metody vychází modifikovaná distribuční metoda (MODI), nebudeme se jí však podrobně zabývat. Pro rychlé získání přibližného řešení bez záruky optimality lze využít heuristické metody, z nichž si ukážeme tři: metodu severozápadního rohu, metodu maticového minima (zvanou též indexní) a Vogelovu aproximační metodu (VAM). Dopravní problém - vyrovnání úlohy Zřejmě není možné uspokojit všechny spotřebitele, jestliže celková poptávka X^=i ty převyšuje celkovou kapacitu a/> úloha pak nemá přípustné řešení. Úlohu, ve které platí rovnost ty = Z)/Li Bi označujeme jako vyrovnaný dopravní problém. Problém pak má přípustné řešení i pokud u omezení pro kapacity zdrojů nahradíme nerovnosti rovnostmi, spotřebují se tedy všechny jednotky. Nadále budeme pracovat jen s takovými vyrovnanými úlohami. Nevyrovnaná úloha s převisem poptávky se převede na vyrovnanou pomocí zavedení fiktivního zdroje s kapacitou X^y=i ty - XXi a,-. V případě převisu nabídky se naopak zavede fiktivní zákazník s požadavkem a'< ~ ty- Pozor! Přepravní náklady do fiktivních míst jsou vždy nulové. Dopravní problém - metoda SZ rohu Metoda severozápadního rohu je zrejme nejjednodušší metodou získání prípustného řešení dopravní úlohy, začíná se v levém horním rohu tabulky a požadavky zákazníků se uspokojují zleva doprava. Pokud je již zdroj vyčerpán, přejde se na další zdroj, tj. o řádek níž. Končí se v pravém dolním rohu. Metoda nebere v úvahu přepravní náklady. Ukažme si metodu pro úlohu z "M. Plevný, M. Žižka: Modelování a optimalizace v manažerském rozhodování": Najděte přípustné řešení DÚ s požadavky odběratelů Si, S2, S3 a S4 postupně 3, 6, 4 a 5 jednotek zboží a zdroji Vu V2 a V3 s kapacitou po řadě 5, 6 a 7 jednotek. požadavky 0 0 0 0 0 3 2 ^>> _Q 0 4 3 N 0 1 5 Dostali jsme přípustné řešení. Dopravní problém - indexová metoda Indexová metoda dává většinou řešení s nižšími přepravními náklady než předchozí metoda. Jde o tzv. hladový algoritmus, vybíráme postupně vždy trasy s nejnižším cenovým ohodnocením, (vynecháme případné fiktivní trasy) Ukažme si postup metody pro již dříve řešený dopravní problém, přidáme tabulku s přepravními náklady c,y, / = 1,... 3, j = 1,... 4. přepravní náklady požadavky 0 0 0 0 0 5 ^>> _Q 0 1 1 5 N 0 2 4 Si s2 s3 s4 Ví 2 1 3 4 v2 6 2 6 1 v3 7 3 3 3 Výsledné přepravní náklady jsou X^2'C^2+X2^'C2^+X22'C22+X24'C24+X3^'C3^+X33'C33 = 5+6+2+5+14+12 Pro předchozí metodu bychom dostali náklady ve výši 6 + 2 + 6 + 2 + 5 +14+12 = 47. = 44. Dopravní problém - VAM Vogelova aproximační metoda je třetí heuristickou metodou a její výhoda oproti metodě indexační spočívá v tom, že bere v každém kroku v úvahu "alternativní náklady"při volbě nejlevnější trasy. Pracuje s diferencemi, tedy rozdíly druhé nejlepší oproti nejlepší variantě v každém řádku a sloupci. Volí se pak vždy nejlevnější jízda v řádku či sloupci s největší diferencí. Použijme metodu pro náš známý příklad. K matici nákladů doplníme řádkové a sloupcové diference c/,., / = 1,... 3 a c/y, y = 1,... 4. požadavky 0 0 0 0 0 3 2 ^>> _Q 0 2 5 N 0 2 4 Si s2 s3 s4 Ví 2 1 3 4 1 v2 6 2 6 1 1 v3 7 3 3 3 0 dj 4 1 0 2 Výsledné přepravní náklady jsou Xn • Cn + XA2 ' C12 + ^22 • c22 + x24 • c24 + x32 • c32 + x33 • c33 = 35, což je výrazně méně než u předchozích metod. Dopravní problém - použití Příklady možných aplikací dopravního problému ilustruje následující přehled. druh činnosti zdroje cílová místa rozvoz pohonných hmot rafinérie, sklady čerpací stanice svoz poštovních zásilek přepravní uzly třídící centra sběr fotozakázek fotosběrny spádová centra distribuce léčiv sklady distribučních firem lékárny, nemocnice zpracování cukrové řepy produkční střediska cukrovary Výjimečně se u dopravních úloh setkáme i s maximalizací účelové funkce. Kdy? Přiřazovací problém Přiřazovací úlohu můžeme charakterizovat jako problém vytvoření párů z objektů ze dvou různých skupin, tak aby toto spárování přineslo co největší efekt. Typicky jde o přidělení jednotlivých projektů pracovníkům či pracovních činností strojům tak abychom minimalizovali náklady nebo maximalizovali zisk. Jde o úlohu příbuznou s dopravním problémem. Ukažme příklad takové úlohy z knihy "M. Kavan: Výrobní a provozní management": Optimalizujte přidělení prací 1, 2, 3 strojům A, B, C, D, přičemž výrobní náklady jsou dány tabulkou: stroje dj A B C D ráce 1 15 19 17 12 2 12 10 15 9 Q_ 3 18 14 11 14 Musíme tedy vybrat jedno číslo v každém řádku, tak aby jejich součet byl minimální a přitom žádná dvě čísla neležela ve stejném sloupci. Přiřazovací problém - matematická formulace Přidělení Mého úkolu y-tému pracovnímu místu můžeme reprezentovat zápisem x-n< = 1, ostatním proměnným přiřadíme hodnotu 0. Pokud by bylo úkolů více než pracovních míst (m > n), je úloha neřešitelná. V případě opačné nerovnosti dorovnáme úlohu zavedením fiktivních prací s nulovými náklady, tak aby m = n. Nadále předpokládejme, že je úloha vyrovnaná. Matematický model přiřazovacího problému zahrnuje podmínky, že řádkové a sloupcové součty v tabulce jsou rovny jedné, s tím že proměnné nabývají pouze hodnot 0 nebo 1. Úlohu můžeme zapsat tatkto: Minimalizujme účelovou funkci Z = S/=1 Sy=1 CÍJXÍJ za podmínek y^j—i xu= i •> / — i j • • • j X]/=1 Xjj = 1 , j = 1 , . . . , A7, Xij e {0, 1}, / = 1, j = 1,...,a? Přiřazovací problém - řešení Přiřazovací problém je možné řešit tzv. maďarskou metodou. Jejím principem je převedení původní úlohy na úlohu redukovanou tak, aby v každé řadě (řadou označujeme souhrne řádky a sloupce) byla aspoň jedna nula a přitom ostatní sazby zůstaly kladné. Optimální tabulka je taková, která obsahuje n "nezávislých nul"(nezávislé jsou tehdy, když žádné dvě neleží ve stejné řadě -jako v sudoku). To poznáme podle toho, že nelze "přeškrtnouťVšechny nuly pomocí méně než n vodorovných a svislých čar. Metodu ukážeme na řešení úvodní úlohy. Původní zadání je třeba vyrovnat, protože počet strojů je větší než počet prací. stroje dj A B C D ráce 1 15 19 17 12 2 12 10 15 9 Q_ 3 18 14 11 14 Optimální řešení znovu vyznačme v původní tabulce. Celkové náklady jsou 12 + 10 + 11 =33. Úloha nemusí mít jediné řešení - pokud je možné volit čáry pokrytí či vybírat nezávislé nuly více způsoby, všechna výsledná řešení budou mít stejnou hodnotu účelové funkce. Okružní dopravní problém Problém se často též nazývá jako Úloha obchodního cestujícího a připomíná přiřazovací úlohu. Cílem je vyjít z nějakého výchozího stanoviště (označme jej A), navštívit postupně každé jednou místa A, • • •, A? a nakonec se vrátit zpět tak, aby délka trasy byla co nejmenší. Úloha má velké množství reálných aplikací - pravidelný rozvoz či svoz různých produktů (pekárny, mlékárny, popeláři, atd.). V matematickém modelu se také zavádějí bivalentní proměnné x,y nabývající hodnoty 1 nebo 0 podle toho, zda cesta A, A bude na okružní trase zařazena či ne. Protože se každé místo projede právě jednou, tj. právě jednou bude koncovým a právě jednou výchozím bodem, máme stejně jako u přiřazovacího problému omezení ve formě jednotkových řádkových i sloupcových součtů. Okružní úloha je však o mnoho složitější, protože navíc obsahuje další omezení, které má zabránit tomu, aby se řešení rozpadlo do více samostatných cyklů (příklad viz tabulky). Okružní dopravní problém - přípustnost řešení Ilustrujme si rozdíl mezi přiřazovací a okružní úlohou na následujícím príklade. Cílem je najít nějakou okružní trasu (pro jednoduchost neuvádíme tabulku nákladů a tedy nepožadujeme optimalitu) mezi městy ,..., A5, může se nám tedy zdát, že je to stejné jako výběr dvojic měst, mezi kterými povede trasa. Znázorněme nějaký takový výběr v tabulce: Ai A2 A3 A4 A5 ^1 0 1 0 0 0 A2 0 0 1 0 0 A3 1 0 0 0 0 A4 0 0 0 0 1 A5 0 0 0 1 0 Jedná se o nepřípustné řešení okružní úlohy, reprezentuje dva samostatné cykly Ai - A2 - A3 - A^ a A4 - A5 - A4. Úloha celočíselného programování Mezi speciální úlohy lineárního programování patří i úlohy celočíselného programování (integer programming, IP). Jedná se o štandartní úlohy LP doplněné o podmínky celočíselnosti u některých ( smíšené úlohy IP ), případně všech proměnných ( ryze celočíselné úlohy ). Tyto podmínky zpravidla plynou přímo z ekonomického modelu, kdy proměnné vyjadřují počty kusů nedělitelných produktů, počty opakování nějaké aktivity, apod. U řady úloh se pracuje dokonce jen s proměnnými, které vyjadřují určité rozhodnutí nebo alternativu, nabývají hodnot {0, 1} a pak hovoříme o bivalentních úlohách . Typickými představiteli takových úloh jsou například přiřazovací či okružní dopravní problém nebo též tzv. "úloha o batohu": Máme n různě cenných věcí s různou hmotností a batoh o omezené kapacitě. Úkolem je vybrat věci, které vložíme do batohu tak, aby nebyl přetížen a cena jeho obsahu byla co nejvyšší. (Řešení úlohy bez podmínky celočíselnosti by bylo triviální: Seřadili bychom věci dle klesajícího poměru cena/hmotnost a plnili batoh v tomto pořadí. U první věci, která by se nevešla celá, bychom vzali jen její poměrnou část do výše kapacity batohu.) Celočíselné programování- příklad Příklad: Oděvní firma Styl, s.r.o. se zabývá se výrobou pánské módy. Za týden pracovnice ušijí xi modelů "Marceľa x2 modelů "Filip", Přitom na výrobu jednoho modelu "Marceľje potřeba 10 hodin a náklady na materiál jsou 400 Kč. Pro model "Filip"je to 20 hodin, materiál 300 Kč. Firma dostala nabídku na účast na zahraničním prodejním veletrhu, který se koná za týden. Očekávaný zisk z prodeje je 20 Euro, resp. 30 Euro pro jednotlivé modely. Navrhněte optimální plán výroby, jestliže firma má k dispozici jednu pracovnici na plný a jednu na poloviční úvazek (celkem 60 h) a zásobu materiálu za 1300Kč. Matematický zápis úlohy z uvedeného příkladu je následující: Maximalizovat účelovou funkci z = 20xi + 30x2 za podmínek 400xi + 300x2 < 1300 10* + 20x2 < 60 Xi, x2e {0,1,2,3,...} Celočíselné programování- grafické znázornění Úloha obsahuje pouze dvě proměnné, je tedy možné ji řešit graficky. Zaokrouhlením xceí = [1,6; 2,2] dostaneme bod [2,2], který není přípustný. Při zakrouhlení dolů na [1,2] dostaneme neoptimální řešení, dává pouze 20 + 2 • 30 = 80 Euro oproti 90 Euro v bodě x*. Celočíselné programování- metody V předchozím příkladě jsme viděli, že intuitivní přístup k řešení celočíselné úlohy zanedbat podmínky celočíselnosti, vyřešit získanou úlohu LP, tzv. zrelaxovanou úlohu a výsledné řešení zaokrouhlit, není vždy vhodný. Proto se používají jiné postupy vyvinuté speciálně pro celočíselné úlohy. Bývají však výpočetně náročnější, na běžných počítačích může výpočet zkolabovat i při počtu proměnných a omezení v řádu desítek. Metody řezných nadrovin (např. Gomoryho algoritmus) spočívají v hledání optima zrelaxované úlohy a následném přidání dalšího omezení, které toto optimum "odřízne", ale přitom mu budou vyhovovat všechna přípustná řešení původní úlohy. Tyto metody jsou starší a méně používané. Kombinatorické metody jsou založeny na efektivním prohledávání přípustné množiny, která pro ryze celočíselnou úlohu obsahuje konečně, avšak zpravidla velmi mnoho prvků. V programových systémech se nejčastěji využívá metody větví a mezí (též Branch and Bound, tj. B & B), kterou si blíže popíšeme. Speciální metody se používají pro úlohy se speciální strukturou, jde např. o různé heuristiky pro okružní dopravní problém nebo Maďarskou metodu. Celočíselné programování- metoda B & B Množina přípustných řešení se postupně dělí na menší části (branching), kde sledujeme horní, (při minimalizaci dolní) hranici hodnot účelové funkce (bounding). To nám umožní vytipovat podmnožinu, kde nejpravděpodobněji nastane optimum a také podmnožiny, kde optimum určitě nebude. Větvení je možné provést pomocí řešení klasické úlohy LP získané relaxací celočíselné úlohy - přípustnou množinu označme M0. Je-li její bod optima x° celočíselný, našli jsme již optimální řešení původní úlohy. Jinak vybereme nějaké /, pro něž je Má složka řešení xf necelá, a přidáme dodatečné omezení x, < a, resp. x, > b, kde a, b jsou celá čísla obklopující x,. Tím rozdělíme množinu M0 na podmnožiny Mi a M2. Na každé z nich zase najdeme optimum účelové funkce x1ax2a určíme jejich hodnoty účelové funkce z1 a z2. Celé části těchto hodnot nám dávají horní mez pro účelovou funkci na množinách Mi a M2. Celý proces pokračuje tak dlouho, dokud se všechny větve neuzavřou tak, že: ► Ve větvi je nalezeno celočíselné řešení nebo ► ve větvi neexistuje přípustné řešení nebo ► ve větvi je nalezeno necelé řešení, jehož hodnota je menší než hodnota celočíselného řešení z jiné větve Celočíselné programování- použití metody B & B Ukažme metodu B & B pro úlohu rozvržení výroby textilu M x°=(8/5,11/5) z° = 98 x'=(2,5/3) z1 = 90 xz=( 1,5/2) z2 = 95 x3=(1,2) z3 = 80 Postup řešení můžeme znázornit schematicky. Cílové programování Představuje jiný přístup k řešení úlohy LP Místo stanovení omezujících podmínek a kritéria optimality se zde stanoví pevné a volné cíle s přiřazenými cílovými hodnotami. U pevných cílů musí být tato hodnota splněna (analogie omezujících podmínek). U volných cílů můžeme dosáhnout vyšší i nižší hodnoty než je cíl (avšak ne moc odlišné). Protože cílových hodnot bývá několik a zpravidla není možné dosažení všech, volí se obvykle jeden ze dvou přístupů: ► pomocí preferencí - nejprve je optimalizován cíl s nejvyšší preferencí, atd. nebo ► pomocí vah - koeficientů vyjadřujících důležitost daného cíle, optimalizuje se pak vážený součet odchylek od všech cílů Modely cílového programování jsou obecnější než standardní modely LP, protože v praxi zpravidla nemáme jediné kritérium optimality, ale sledujeme více hodnot. Cílové programování - příklad Příklad z J. Jablonský, Operační výzkum: Vedení penzijního fondu se rozhoduje o nákupu dvou druhů cenných papírů (akcie a obligace). Má k dispozici prostředky, které není nutné úplně vyčerpat, nelze je však překročit. Do akcií lze investovat maximálně 50 % celkového objemu prostředků a do obligací maximálně 75 % prostředků. Očekávaný výnos z akcií je 15 % a z obligací 10 % p.a., míra rizika investice je ohodnocena koeficientem 5 u akcií a 2 u obligací. Navrhněte takovou skladbu portfolia [xi, x2], aby se dosáhlo průměrného výnosu 12 % p.a. a aby byla vážená míra rizika rovna 3 . Při standardním přístupu LP bychom museli zvolit jako účelovou funkci jen jedno z nich, např. výnos a k omezujícím podmínkám pro objem investic přidat další omezení, totiž že míra rizika nesmí překročit hodnotu 3. Lze spočítat, že optimálního řešení při tomto přístupu dosáhneme, dáme-li ^ prostředků do akcií a § do obligací. Při průměrném riziku 3 tak získáme 11,67 % p.a. Nebo naopak budeme minimalizovat účelovou funkci vyjádřenou váženým rizikem a jako dodatečnou podmínku stanovíme omezení, aby průměrný výnos byl nejméně 12 % p.a. Pak je optimální investovat 40 % prostředků do akcií a 60 % do obligací. Při výsledném výnosu 12 % p.a. pak bude míra rizika 3,2. Cílové programování - formulace modelu U volných cílů se používají odchylkové proměnné pro vyjádření kladných a záporných odchylek (značíme je df, resp. dj~) od cílových hodnot. Je-li cíle splněn, platí = dj~ = 0, dojde-li k přesáhnutí cíle, pak je df > 0, dj~ = 0 a není-li cíl dosažen, je gí+ = 0, dj~ > 0. Pevné cíle musí být respektovány, žádné odchylky se nepřipouští. V modelu cílového programování je vždy účelová funkce vyjádřena jako minimalizace odchylkových proměnných, přičemž do ní lze zahrnout buď pouze kladné, pouze záporné nebo oba typy odchylek ( pak se cílovým hodnotám blížíme shora, zdola nebo "oboustranně"). Zápis úlohy o optimalizaci portfolia by tedy byl: d£, d^ ->> min, za podmínek: + x2 < 1 x^ < 0,5; x2 < 0,75 15xi +10x2 + djf-t/1- = 12 5xi + 2x2 + c/2+ - d~ = 3 Xi,x2,c/1+,c/1",c/2+,c/2" > 0 Cílové programování - odlišení cílů vahami Při současné minimalizaci více odchylek můžeme odlišit jejich důležitost vahami. Abychom se vyhnuli problémům s různými jednotkami, je lepší pracovat s relativními odchylkami kde g-, značí /- tou cílovou hodnotu. Pokud je pro nás výnos pětkrát důležitější než riziko, stanovíme váhy 5 a 1 a účelová funkce bude mít podobu z = 5^- + \. Dále lze úlohu řešit běžnou simplexovou metodou. Řešením je dát \ prostředků do akcií a § do obligací, přitom je zcela splněna cílová hodnota rizika a výnos je 11,67%. Cílové programování - odlišení cílů preferencemi Při odlišení cílů preferencemi minimalizujeme nejprve odchylku od důležitějšího cíle a pokud má množina optimálních řešení více prvků, minimalizujeme na této množině druhou nejzávažnější odchylku, atd. Má-li v naší úloze vyšší prioritu výnos, minimalizujeme nejprve . Znázorněme situaci graficky v rovině xi, x2. Protože se přímky protínají mimo přípustnou množinu, nelze dosáhnout rovnosti = 0. Musíme riziko zvýšit, tj. posunout modrou přímku tak, aby se dotkla optimální úsečky proc/^. Našli jsme bod optima x* = [0,4; 0,6]. Optimalizace v grafech - základní pojmy Řadu reálných systémů (např. distibuční síť) lze modelovat rovinnými grafy. Graf je tvořen uzly, které budeme značit ui,...,íina hranami, přičemž hranu mezi uzly u, a U\ označíme h,j. V rovině můžeme znázornit graf pomocí bodů (koleček) a spojnic mezi nimi. Hrany, které umožňují pohyb v obou směrech nazýváme neorientované. Je-li povolen pouze jeden směr pohybu, znázorníme to na grafu šipkou a takové "jednosměrné"hrany nazýváme orientované. Neorientovaným grafem nazveme graf obsahující pouze neorientované hrany, jinak jej nazveme orientovaným. Na obrázku je znázorněn neorientovaný a orientovaný graf. Optimalizace v grafech - základní pojmy Cestou z uzlu Uj do uzlu Uj nazveme posloupnost na sebe navazujících hran, z nichž první začíná v u-, a poslední končí v Uj. Pokud cesta respektuje orientaci hran, nazývá se orientovaná (v opačném případě neorientovaná). Na obrázku je znázorněna jedna z orientovaných cest z uzlu 1 do uzlu 6. Naopak z uzlu 6 do uzlu 1 vedou pouze neorientované cesty. Cestu, pro kterou u-, = Uj, nazveme cyklus. Zobrazený graf obsahuje například neorientovaný cyklus 1 - 3 - 4 - 1. Graf, ve kterém mezi libovolnými dvěma uzly existuje aspoň jedna neorientovaná cesta, se nazývá souvislý. Každý souvislý neorientovaný graf, který neobsahuje cyklus, se nazývá strom. Optimalizace v grafech - základní pojmy Při řešení optimalizačních úloh zpravidla pracujeme s hranově ohodnocenými grafy. Hranám jsou přiřazeny hodnoty y-,j podle ekonomického významu (např. vzdálenosti mezi distribučními centry či náklady na přepravu mezi centry, apod.) Souvislý orientovaný a nezáporně ohodnocený graf se dvěma speciálními uzly (vstupem a výstupem) nazveme síť. Přidáme-li ohodnocení hran do našeho grafu, získáme síť se vstupním uzlem 1 a výstupním uzlem 6. Délkou cesty nazveme součet ohodnocení jejích hran. Například mezi délka orientované cesty 1 -2-5-6 je 3+7+6=16. Pozor! Graf je definován pomocí množiny uzlů a množiny hran, nikoliv zakreslením. Délky spojnic nemusí a často ani nemohou odpovídat ohodnocení hran. Optimalizace v grafech - úlohy Na grafech se řeší řada úloh: ► Štandartní optimalizační úlohou je hledání nejkratší cesty mezi dvěma uzly. Úloha se řeší v orientovaných i neorientovaných grafech, existuje více algoritmů, některé k určení celé matice vzdáleností. Jeden z nejznámějších algoritmů je Dijkstrův algoritmus. ► Hledání minimální kostry grafu - úkolem je vybrat takovou podmnožinu hran, aby mezi každými dvěma uzly existovala cesta a aby celkové ohodnocení bylo minimální. ► Určení maximálního toku v síti (propustnosti sítě): Představuje - li ohodnocení v síti přepravní kapacitu hran, pak úkolem je určení maximálního počtu jednotek, které je možné přepravit ze vstupního do výstupního uzlu. ► Další úlohy, jako problém barvení grafu, problém čínského pošťáka, problém obchodního cestujícího, atd. Řízení projektů Řízení projektů je jednou z typických aplikací teorie grafů. Projekt můžeme obecně chápat jako soubor činností. Tyto činnosti lze charakterizovat předpokládanou dobou trvání, náklady na realizaci, požaddavky na zajištění, výčtem činností, které realizaci musí předcházet, atd. Nejčastěji hledáme odpověď na tyto otázky: ► Jaká je nejkratší možná doba realizace projektu? ► Které činnosti jsou z hlediska dodržení termínu klíčové, tzv. kritické činnosti? ► Jaké jsou rezervy u nekritických činností ► Jaký je časový rozvrh pro realizaci jednotlivých činností? Kromě časové analýzy projektů nás zajímají též náklady na projekt v závislosti na čase, hovoříme pak o nákladové analýze. Dále můžeme sledovat úroveň a rozložení zdrojů potřebných pro jednotlivé činnosti, tedy provádět zdrojovou analýzu projektu. Řízení projektů - konstrukce síťového grafu Projekt znázorňujeme pomocí ohodnoceného síťového grafu, kde hrany reprezentují činnosti, ohodnocení většinou dobu jejich trvání a uzly představují momenty zahájení či ukončení jednotlivých činností. Při analýze nejprve musíme vymezit jednotlivé činnosti, odhadnout délky jejich realizace a definovat návaznosti pomocí výčtu bezprostředně předcházejících činností. Ukažme si síťový graf pro projekt vytvoření nového obchodního střediska firmy Q-mark, a.s. (J.Jablonský: Operační výzkum). Před vlastním sestavením grafu definujeme elementární činnosti a jejich vlastnosti, viz. tabulka: činnost popis činnosti trvání [týdny] předchází A výběr a nákup projektu 6 - B zpracování projektu 4 A C obsazení pozice manažera 3 A D výběr personálu 3 B,C E rekonstrukce a vybavení objektu 8 B F školení personálu 2 D G výběr sortimentu zboží 2 B,C H uzavření smluv s dodavateli 5 G 1 nákup zboží 3 E,F,H J reklama 2 H Řízení projektů - konstrukce síťového grafu Při sestavování grafu můžeme narazit na problém u definice uzlů. Například činnosti D musí předcházet B,C, ale činnosti E předchází pouze B. Jak tedy správně znázornit návaznost? Příklady nesprávného znázornění, viz obr.: (!>^)Ó©< C D Podobný problém je u činností l,J, které mají společného předchůdce H, ale činnosti I navíc předchází i E,F. Řízení projektů - konstrukce síťového grafu Problém s návazností lze řešit zavedením fiktivních činností, jimž odpovídající fiktivní hrany doplní chybějící spoje. Znázorňují se přerušovanou čarou. Doba fiktivních činností je vždy nulová. Do našeho příkladu tedy doplníme dvě fiktivní činnosti: X zprostředkující návaznost mezi B a D a činnost Y pro návaznost mezi Hal. Jedno z možných znázornění sítě projektu je na obrázku: Při sestavování grafu je dobré držet se pravidla, aby index počátečního uzlu každé hrany byl nižší než index jejího koncového uzlu. Potom graf nebude obsahovat žádné orientované cykly. Critical Path Method (CPM) Metoda se používá od 50. let minulého století. Jejím principem je určit pro každou činnost tyto 4 charakteristiky: ► Nejdříve možný začátek provádění činnosti začínající v uzlu u,, značíme jej: ťf ► Nejdříve možný konec provádění činnosti reprezentované hranou h,j získáme přičtením doby trvání činnosti: tf + y-,j ► Nejpozději přípustný konec provádění činnosti končící v uzlu uj, značíme jej: X] ► Nejpozději přípustný začátek provádění činnosti reprezentované hranou hjj získáme odečtením doby trvání činnosti: X] - y,j V síťovém grafu vyznačíme do jednotlivých uzlů i nejdříve možné začátky a nejpozději přípustné konce činností, které v něm začínají, resp. končí: Critical Path Method (CPM) Vlastní algoritmus metody probíhá ve čtyřech fázích: 1. Výpočet nejprve možných začátků: Pro činnosti začínající v uzlu Uj se spočte jako maximum nejdříve možných konců činností, které do něj vstupují, tf = maxi(tf + yij) Pro výstupní uzel tak dostaneme nejkratší možnou dobu realizace projektu. 2. Výpočet nejpozději přípustných konců: Pro činnosti končící v uzlu u-, se spočte jako minimum z nejpozději přípustných začátků činností z uzlu vystupujících, t} = mirij(tj - yjj) 3. Výpočet celkových časových rezerv: Činnost reprezentovaná hranou h,j má stanoveno, kdy může nejdříve začít (tf) a kdy musí nejpozději skončit (řy1). Doba, během které se musí realizovat, je tedy t] - tf a protože její realizace trvá y#, dostaneme její pro časovou rezervu vztah: Rij = tJ-$-yij 4. Sestavení harmonogramu činností Critical Path Method (CPM) - 1. fáze V první fázi metody CPM postupně zleva doprava počítáme nejdříve možné začátky činností. Nejdříve možná doba ukončení projektu je v čase ř9° = max{\8 + 3,17 + 2) = 21 týdnů. Critical Path Method (CPM) - 2. fáze Ve druhé fázi postupujeme zprava doleva a doplňujeme nejpozději přípustné konce. Předpokládejme, že chceme stihnout projekt v nejkratším možném čase. Nejpozději přípustný konec činnosti A je \\ = min(10 - 4,11 - 3) = 6. Protože jsme vycházeli z nejrychlejší možné realizace projektu, samozřejmě vyšlo =6-6 = 0. Critical Path Method (CPM) - 3. fáze Dopočítáme rezervy jednotlivých činností podle vztahu R,j = t] - tf - y#. Například činnost J musí proběhnout mezi 17. a 21. týdnem a trvá 2 týdny, její rezerva je tedy R79 = 21 -17-2 = 2 týdny, apod. Rezervy jednotlivých činností jsou uvedeny v závorkách. Červeně je znázorněna kritická cesta sestávající z činností A,B,E,I, které nemají žádnou časovou rezervu. Critical Path Method (CPM) - 4. fáze Poslední, ale velmi důležitou fází je rozvržení realizace činností v čase. Je nutné určit, které činnosti mohou probíhat paralelně a které na sebe musí navazovat. To nám umožní dále rozvrhovat zdroje potřebné pro jednotlivé činnosti. Ukažme si rozvrh činností v diagramu, kde rámečky tvoří nejdříve možný začátek a nejpozději přípustný konec činností, stínování naznačuje dobu jejich trvání. V horní části tabulky jsou kritické činnosti s nulovými rezervami - tyto musí na sebe bezprostředně navazovat, aby nedošlo ke zpoždění projektu. Činnost Cas 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 A B E I C D F G H J Metoda PERT Metoda PERT (Program Evaluation and Review Technique) je pravděpodobnostním rozšířením metody CPM. V praxi často není reálné stanovit realizační doby činností, proto jsou hodnoty y-,j nahrazeny náhodnými veličinami, které se realizují na nějakém intervalu (a,y, bij). Kromě tohoto mezního optimistického, resp. pesimistického odhadu se pracuje s nepravděpodobnější dobou trvání činnosti rriij, ta se označuje jako modálni odhad. Skutečné rozložení pravděpodobnosti náhodné veličiny není obecně známo, ale často se aproximuje ^-rozdělením. Lze ukázat, že pro její střední hodnotu a rozptyl platí: _ ajj+Amjj+bjj N — 6 Vlastní výpočet metodou PERT se neliší od metody CPM, jen se místo hodnot y,j pracuje se středními hodnotami /x,y. Za určitých předpokladů se dá dle centrální limitní věty aproximovat rozložení celkové délky projektu normální náhodnou veličinou a získat tak odpověď na otázky : Jaká je pravděpodobnost, že projekt bude ukončen v čase T, resp. v jakém čase bude projekt ukončen se stanovenou pravděpodobností p, apod. Vícekriteriální rozhodování V reálných rozhodovacích situacích je často důležité vzít do úvahy více optimalizačních kritérií. Tato však zřídka bývají ve vzájemném souladu, takže není možné najít řešení, které bude nejlepší podle všech kritérií. Úlohy vícekriteriálního rozhodování se dělí podle způsobu stanovení rozhodovacích variant. ► Jsou-li stanoveny výčtem, mluvíme o vícekriteriálním hodnocení variant (VHV). ► Jiný přístup je vymezení variant soustavou omezujících podmínek, mluvíme pak o úlohách vícekriteriálního programování. Vícekriteriální hodnocení variant V úlohách VHV je dána množina variant X = {Xí,..., Xn}, které jsou hodnoceny podle kritérií Y^,..., Yk. Každá varianta je pak popsána vektorem kriteriálních hodnot, tyto lze pak jako řádky pro jednotlivé varianty shrnout do kriteriální matice. Y2 Yk /n /12 /21 Y2k Xn /m Yn2 Ynk Součástí modelu úlohy musí být u kvantitativních kritérií i určení jejich typu (maximalizační či minimalizační). Protože některé metody vyžadují, aby všechna kritéria byla stejného typu, někdy je nutné provést transformaci (např. u hodnocení hospodářské vyspělosti je HDP na hlavu kritériem maximalizačním a míra nezaměstnanosti minmalizačním). Další oblasti aplikace VHV jsou velmi široké: různá výběrová řízení, hodnocení podniků, výrobků či služeb, výběr lokality pro investiční akci, atd. Vícekriteriální hodnocení variant - příklad Dále uvedené postupy budeme ilustrovat na příkladu výběru tabletu (z knihy Tomáš Šubrt a kol.: Ekonomicko - matematické metody): Uživatel definoval pět relevantních hledisek, podle kterých bude jednotlivé nabídky hodnotit: cena [Kč], velikost operační paměti RAM [MB], výdrž baterie [hod.], hmotnost [g] a souhrnně kombinace OS, procesoru a velikosti displeje. V úvahu připadá pět konkrétních tabletu T1 - T5, uveďme přehled jejich charakteristik: cena RAM výdrž baterie hmotnost OS, procesor, display T1 12000 1000 9,5 680 Android 3.0,Tegra 1 GHz, 10,1" T2 12000 1000 10 600 Apple 1054,1 GHz Dual, 9,7" T3 5000 512 7 380 Android 2.2, 1 GHz, 7" T4 20000 4000 3 1160 Windows 7,iCore5 1 GHz, 12,1" T5 5000 256 4 400 Android 2.1, 800 MHz, 7" První čtyři kritéria jsou kvantitativní (cena a hmotnost minimalizační, ostatní maximalizační), u pátého kritéria máme alespoň ordinální informaci v podobě pořadí tabletu dle odborníka: 1,3,4,2,5. Vícekriteriální hodnocení variant Mezi základní cíle při analýze VHV patří: ► výběr jedné, tzv. kompromisní varianty (např. při výběrovém řízení) ► uspořádání variant (např. spotřebitelské žebříčky) ► klasifikace variant (např. při přijímačkách: přijatí/nepřijatí nebo hodnocení bonity klientů bankou, atd.) Vzájemný vztah mezi variantami může při VHV být následující: ► Varianta X, dominuje variantu Xj, jestliže (y,i,..., y,k) > (yyi,..., yy/c), ale vektory se nerovnají. ► Varianta Xj dominuje variantu Xj ► Varianty X,, Xj jsou vzájemně nedominované. Řekneme, že varianta X, je nedominovaná, jestliže neexistuje žádná jiná varianta, která ji dominuje. Zřejmě kompromisní varianta musí být vždy nedominovaná. Dále definujeme pojmy bazálni a ideální varianta, což je označení pro zpravidla reálně neexistující variantu nabývající nejhorších (resp. nejlepších) hodnot podle všech kritérií. VHV - vztahy mezi variantami, příklad V úloze o výběru tabletu stanovte nedominované varianty a vyberte bazálni a ideální varinatu. cena RAM výdrž baterie hmotnost OS, procesor, display Tablet 1 12000 1000 9,5 680 1 Tablet 2 12000 1000 10 600 3 Tablet 3 5000 512 7 380 4 Tablet 4 20000 4000 3 1160 2 Tablet 5 5000 256 4 400 5 V tabulce jsou vyznačeny nejlepší hodnoty dosažené u jednotlivých kritérií. Ideální varianta by tedy hypoteticky byla (5000 Kč, 4000 MB, 10 hod., 380g a 1. pořadí dle experta). Obdobně bazálni varianta (20000 Kč, 256 MB, 3 hod., 1160g a 5. pořadí dle experta). Nedominované jsou téměř všechny varianty, dominovaný je pouze Tablet 5 (ve všem horší než Tablet 3) VHV - vyjádření preference kritérií U většiny metod VHV je nutné, aby rozhodovatel vyjádřil své preference ve vztahu k jednotlivým kritériím. Tyto preference mohou být stanoveny pomocí ► aspiračních úrovní kritérií, tedy stanovením minimálních hodnot, kterých má být dosaženo u jednotlivých maximalizačních kritérií (resp. maximálních hodnot pro minimalizační kritéria). Preference kritérií je tak vyjádřena nepřímo, důležitějším kritériím nastavíme přísnější limity. ► pořadí kritérií (ordinální informace o kritériích) ► vah kritérií: v = (1/1,..., vk), v,■■ = 1, v, > 0, / = 1,..., k. (kardinální informace o kritériích) ► míry substituce mezi kriteriálními hodnotami, na níž jsou založeny kompenzační metody VHV VHV - metody odhadu vah kritérií Získání vah od rozhodovatele přímo v numerické podobě bývá problematické, proto je vhodné usnadnit mu situaci pomocí nějakého jednoduchého nástroje. ► Metoda pořadí vyžaduje pouze seřazení kritérií od nejméně důležitého po nejdůležitější. Přiřazené pořadí p, tedy bude nabývat hodnot 1,..., k a odhad vah lze získat jejich normalizací: v-, = =^—. 2^=1 P i ► Bodovací metoda spočívá v tom, že rozhodovatel přiřadí každému kritériu body p, z nějaké předem zvolené škály. Přepočet bodů na váhy je stejný jako výše. ► Fullerův trojúhelník je založen na párovém porovnávání kritérií. Jednotlivým kritériím se přiřadí tolik bodů p/, kolikrát je zvolen jako důležitější nebo stejně důležitý mezi všemi dvojicemi různých kritérií, (takových dvojic je k(k - 1 )/2 a lze je uspořádat do trojúhelníkového schématu, odtud název metody) ► Poněkud propracovanější přístup představuje Saatyho metoda, při níž se projdou všechny dvojice kritérií a každé se přiřadí číslo s,y « ^, které odhaduje poměr mezi důležitostí jednotlivých kritérií. Matice S = (s,y)/}y=i}...}fr se nazývá Saatyho matice. VHV - Saatyho metoda odhadu vah kritérií Saatyho metoda umožňuje formulovat preference verbálně a pak vyjádřit numericky pomocí stupnice: ► kritéria Y, a Vy jsou stejně důležitá, pak s,y = sy/ = 1, ► kritérium Y, je slabě důležitější než Vy, pak s,y = 3, sy/ = 1 /3, ► kritérium Y, je silně důležitější než Vy, pak s,y = 5, Sy, = 1 /5, ► kritérium V/ je velmi silně důležitější než Vy, pak s,y = 7, sy/ = 1 /7, ► kritérium Y, je absolutně důležitější než Vy, pak s/y = 9, sy/ = 1 /9. Jestliže uvedená stupnice nepostačuje, lze použít i mezistupně 2,4,6,8. Pokud je Saatyho matice tzv. konzistentní, stačí váhy spočítat jako řešení soustavy rovnic ^ = s,y, /,/ = 1,..., /c, ^ i/, = 1. Pro nekonzistentní matici soustava nemá řešení a váhy se pak odhadují například normalizací geometrických průměrů řádků matice S: p, = y ľlyLi su- VHV - metody odhadu vah kritérií, příklad Pro úlohu o tabletu ukažme různé způsoby stanovení vah kritérií. Nejjednodušší metodou pořadí by uživatel při preferenci J.cena, 2.RAM, 3.názor experta, 4.výdrž baterie, 5.hmotnost" dospěl k váhám v V 15 ? 155 155 155 15;- Jiným způsobem je označení preference kritéria z daného řádku oproti kritériím v jednotlivých sloupcích vyznačením hodnoty 1 ve Fullerově trojúhelníku: cena RAM baterie hmotnost expert skóre váhy cena 1 1 1 1 4 0,4 RAM 0 1 1 1 3 0,3 baterie 0 0 1 0 1 0,1 hmotnost 0 0 0 0 0 0 expert 0 0 1 1 2 0,2 Bohužel váha nejméně důležitého kritéria vyjde při konzistenci v preferencích nulová. Postup je možné modifikovat přidáním jedniček na diagonále (jako by každé kritérium bylo ve srovnání se sebou samým důležitější). VHV - metody odhadu vah kritérií, příklad Ukažme ještě pro stejné zadání jedno z možných uživatelova vyplnění Saatyho matice. cena RAM baterie hmotnost expert bi V; cena 1 4 2 9 2 2,7 0,41 RAM 1/4 1 1/2 3 1/2 0,72 0,11 baterie 1/2 2 1 7 1 1,48 0,22 hmotnost 1/9 1/3 1/7 1 1/7 0,24 0,04 expert 1/2 2 1 7 1 1,48 0,22 U Saatyho metody vycházejí váhy většinou více diferencované než u ostatních metod. VHV - klasifikace metod Existuje celá řada přístupů k řešení úloh VHV, my zmíníme pouze ty jednodušší z nich. Metody lze klasifikovat podle typu informace o preferencích mezi jednotlivými kritérii a variantami, viz následující stručný přehled. Informace o preferencích mezi variantami aspirační úrovně ordinální informace kardinální informace funkce užitku vzdálenost variant od bazálni resp. ideální preferenční relace mezní míra substituce Metody PRIAM Lexikografická ORESTE Permutační WSA TOPSIS PROMÉTHEE ELECTRE AHP Kompezační VHV - metody nevyžadující váhy kritérií Pokud nejsou známy preference mezi kritérii nebo jsou kritéria rovnocenně důležitá, můžeme pro výběr kompromisní varianty použít pouhá pořadí hodnot u jednotlivých kritérií (v případě shodných hodnot se přiřadí průměrné pořadí). Vybere se ta varianta, která bude mít nejnižší součet poředí přes všechna kritéria. V příkladu s tablety pracujeme s pořadími rovnou v posledním sloupci (expertní názor). V ostatních sloupcích nahradíme jednotlivé hodnoty pořadím v rámci sloupce a doplníme jejich řádkové součty: cena RAM výdrž baterie hmotnost OS, procesor display součet Tablet 1 3 2,5 2 4 1 12,5 Tablet 2 3 2,5 1 3 3 12,5 Tablet 3 1 4 3 1 4 13 Tablet 4 5 1 5 5 2 18 Tablet 5 1 5 4 2 5 17 Podle uvedeného postupu by se jako nejvýhodnější jevily tablety 1 a 2. VHV - metody nevyžadující váhy kritérií Další metodou nevyžadující apriori váhy kritérií je metoda PRIAM , která pracuje s aspiračními úrovněmi kritérií. Varianty jsou pro konkrétní nastavení aspiračních úrovní rozděleny na akceptovatelné a neakceptovatelné. Může nastat situace, kdy nevyhovuje žádná varianta, pak je nutné úrovně některých kritérií uvolnit. Naopak, vyhovuje-li mnoho variant, je možné jejich počet zredukovat zpřísněním některých úrovní. Metoda PRIAM je interaktivním přístupem postupného přizpůsobování aspiračních mezí k dosažení určitého počtu akceptovatelných variant (v krajním případě jediné varianty, kterou pak zvolíme jako kompromisní). cena RAM výdrž baterie hmotnost OS, procesor, display vyhovuje Tablet 1 12000 1000 9,5 680 1 NE Tablet 2 12000 1000 10 600 3 ANO Tablet 3 5000 512 7 380 4 NE Tablet 4 20000 4000 3 1160 2 NE Tablet 5 5000 256 4 400 5 NE Budeme-li požadovat ještě nižší hmotnost, z3 = (12000,256,7,600,3), zůstane přijatelný pouze tablet 2. VHV - metody vyžadující pořadí kritérií Nejpoužívanější a současně zřejmě nejjednodušší metodou z třídy postupů vyžadujících pouze ordinální informaci o kritériích je metoda lexikografická . Řídíme se dle nejdůležitějšího kritéria a je-li nejlépe hodnocená varianta dle tohoto kritéria jediná, je zvolena jako kompromisní. V případě, že by nejlepší hodnoty dosáhlo více variant, vybere se ta z nich, která má lepší hodnocení dle druhého nejdůležitějšího kritéria, atd. Použitím lexikografické metody na výběr tabletu, je-li prioritním kritériem cena a druhým kritériem výdrž baterie, se rozhodneme pro tablet 3, protože je spolu s tabletem 5 nejlevnější a jeho baterie vydží 7 hodin oproti 4 hodinám tabletu 5: cena RAM výdrž baterie hmotnost OS, procesor, display vyhovuje Tablet 1 12000 1000 9,5 680 1 NE Tablet 2 12000 1000 10 600 3 NE Tablet 3 5000 512 7 380 4 ANO Tablet 4 20000 4000 3 1160 2 NE Tablet 5 5000 256 4 400 5 NE VHV - metody vyžadující kardinální informaci o kritériích Existují tři základní kategorie přístupů k hodnocení variant využívající vah kritérií, a to: ► maximalizace užitku ► minimalizace vzdálenosti od ideální varianty ► preferenční relace Z každé skupiny metod uvedeme jednoho zástupce. První z možností je vyčíslení užitku jednotlivých variant na škále od 0 do 1. Pro vyjádření celkového užitku varianty je třeba nejprve vyjádřit dílčí funkce užitku Uj dle jednotlivých kritérií j = 1,..., n. Kardinální hodnoty y-,j jsou tedy nahrazeny pomocí hodnot u-,j = Uj(y-,j), j = 1,..., n. Dílčí funkce užitku jsou nastaveny tak, aby ideální varianta měla dílčí užitek dle všech kritérií roven 1 a bazální varianta nulový. Rozlišujeme tři typy funkcí užitku: 1. lineární (růst užitku je proporcionální růstu hodnot kritéria) 2. progresivní (tempo růstu užitku se při zlepšování hodnot zvyšuje) 3. degresivní (tempo růstu užitku se při zlepšování hodnot snižuje) VHV - metody založené na funkci užitku Metoda váženého součtu (WSA) je založena na konstrukci lineární funkce užitku se stupnicí od 0 do 1. Jestliže pro Vy označíme Dy nejnižší a Hy nejvyšší kriteriální hodnotu, pak lze při maximalizaci nahradit prvky y,j standardizovanými hodnotami y n — Hj-Dj ■ Potom bude mít tedy nejhorší varianta Dy užitek 0 a nejlepší Hy užitek 1. Pro minimalizační kritéria použijeme vztah / _ Hj-yjj šij ~ Hj-Dj • Tentokrát bude nejhorší varianta Hy a nejlepší Dy a bude jim opět odpovídat užitek 0, resp. 1. Celkový užitek varianty X, pak spočteme jako vážený součet dílčích užitků u(Xj) = Y^í=a vjyíj a varianty pak seřadíme podle klesajících hodnot užitku. VHV - metoda WSA, příklad Použijme metodu WSA na problém výběru tabletu, přičemž převezmeme váhy stanovené dle Saatyho metody: cena RAM výdrž baterie hmotnost OS, procesor, display užitek Tablet 1 0,53 0,2 0,93 0,62 1 0,69 Tablet 2 0,53 0,2 1 0,72 0,5 0,59 Tablet 3 1 0,07 0,57 1 0,25 0,63 Tablet 4 0 1 0 0 0,75 0,29 Tablet 5 1 0 0,14 0,97 0 0,47 váhy 0,41 0,12 0,22 0,03 0,22 Dj 5000 256 3 380 1 Hj 20000 4000 10 1160 5 typ min max max min min Největší užitek nám přinese tablet 1 (v závěsu s tabletem 3). VHV - metody založené na optimalizaci vzdálenosti od bazálni a ideální varianty Metoda TOPSIS spočívá ve výběru varianty, která je co nejblíže tzv. ideální variantě a současně je co nejdál od tzv. bazálni varianty. Popišme její postup pro případ, kdy že jsou všechna kritéria maximalizační. Postupuje se v následujících krocích: 1. Normalizace: hodnoty y# se transformují na r,j podle vztahu 2. Vypočte se vážená kriteriální matice W = (wy) jako w-,j = v^j. 3. Z prvků W se vybere ideální varianta H = (Hi,..., Hk) a bazálni varianta D = (D^,..., Dk), kde Hy = maxj(Wij), Dj = mirii(Wij). (Pozor! Hodnoty Hj a Dy se neshodují s těmi dříve zavedenými - jsou spočteny po normalizaci a zvážení sloupců!) 4. Vypočtou se vzdálenosti variant od ideální a bazálni varianty dt = yEyti(^-Hy)2, dr = ^U^-Dif 5. Nakonec se vypočte relativní vzdálenost od bazálni varianty c, = d+'+d-a varianty se podle ní sestupně uspořádají. VHV - metoda TOPSIS, příklad Použijme metodu TOPSIS pro výběr tabletu, jako váhy opět vezmeme Saatyho odhady. cena RAM výdrž baterie hmotnost expert dt dr Ci T1 0,181 0,028 0,129 0,013 0,03 0,135 0,192 0,587 T2 0,181 0,028 0,135 0,011 0,089 0,148 0,166 0,53 T3 0,075 0,014 0,095 0,007 0,119 0,138 0,235 0,63 T4 0,302 0,112 0,041 0,022 0,059 0,248 0,138 0,357 T5 0,075 0,007 0,054 0,008 0,148 0,178 0,227 0,56 vi 0,41 0,12 0,22 0,03 0,22 typ min max max min min Dj 0,302 0,007 0,041 0,022 0,148 Hj 0,075 0,112 0,135 0,007 0,030 Vypočteme vzdálenosti od ideální a bazálni varianty c/+ a ól a relativní index vzdálenosti od bazálni varianty c,. Nejlépe se jeví tablet 3. VHV - metody Metoda AHP (Analytic Hierarchy Process) modeluje rozhodovací problém pomocí hierarchické struktury, která má pro nejjednodušší úlohy tři úrovně (viz obr.) Cíl hodnocení 100% Kritérium Yi Kritérium Y Varianta Xi Wu, j=1,..,k Varianta Xz W2J, j=1,..,k Kritérium Yi Varianta Xn Wnj, j=1,..,k VHV - metody Intenzitu vztahu mezi jednotlivými prvky hierarchie můžeme vyjádřit pomocí dělení počáteční jednotky (100 %) podle preferencí rozhodovatele na další úrovně. Nejprve jsou na druhé úrovni přiřazeny kritériím váhy i/y, j = 1,..., k. Tyto váhy se dále rozdělují jednotlivým variantám podle toho, jak dobře či špatně jsou tyto varianty dle daného kritéria ohodnoceny, čímž pro dané kritérium dostaneme preferenční indexy w-,j, / = 1,...,/?. Z konstrukce modelu vyplývá, že platí vztahy i/y = 1, XXi wv = vh J' = 1 > • • •k Celkový užitek, podle nějž lze varianty uspořádat, se vypočte jako u(Xi) = Eyti wij. Vlastní numerická realizace je založena na párovém porovnávání prvků podobně jako u Saatyho metody: Pro nejvyšší uzel se sestaví porovnávací matice (k x k) a z ní se odvodí váhy kritérií. Následně se pro každé kritérium určí preference variant párovým porovnáváním v matici (n x n). Nevýhodou metody je tedy očividně velký objem porovnávání, což je na druhou stranu vyváženo její univerzální použitelností a možností použití verbální stupnice pro vyjádření preferencí. Vícekriteriální programování Ve vícekriteriálním programování jde o optimalizaci více účelových funkcí na přípustné množině definované sadou omezení. Narozdíl od úloh VHV je množina variant v úlohách nekonečná a kritéria jsou definována v podobě funkcí. Jsou-li všechny účelové funkce i omezující podmínky lineární, mluvíme o vícekriteriálním lineárním programování (VLP). Problém VLP tedy můžeme formulovat jako úlohu "optimalizovat" Z\ = C1 X, Z2 = C2 • X, . . . Z/c = ck • X, za podmínek x g X = {x g rn|Ax < b, x > 0}, kde c1 je cenový vektor /-té účelové funkce. Pomocí ekvivalence minimalizační úlohy pro z-, s maximalizační úlohou pro -z-, můžeme převést úlohu do takové podoby, aby všechna kritéria měla maximalizační charakter. Úlohu je pak možné zapsat pomocí maticového zápisu, označíme-li z = (z\, z2,..., zk) vektor účelových funkcí a C matici vytvořenou z cenových vektorů c1, c2,... ck: z = C x MAX, x g X. Model VLP - základní pojmy Podobně jako u VHV je typicky cílem nalézt v množině všech přípustných řešení pomocí vhodného postupu nějaké prakticky přijatelné, tzv. kompromisní řešení. Je dobré si uvědomit, že při hledání kompromisního řešení se opět stačí omezit na nedominovaná řešení. Řešení x g X je nedominované, pokud neexistuje žádné přípustné řešení, jehož vektor kriteriálních hodnot by byl ve všech složkách větší nebo roven vektoru C • x (s vyloučením případu rovnosti vektorů). Většina principů pro hledání kompromisního řešení je založena na řešení dílčích úloh lineárního programování z, = c1 x —^ max, x g X standardní simplexovou metodou. Vektor xH, ve kterém všechny účelové funkce nabývají svých optimálních hodnot nazýváme ideální řešení. Analogicky bychom mohli zavést bazálni řešení xD. Optimální a bazálni řešení zpravidla neleží v přípustné množině. Model VLP - grafické znázornění Vícekriteriální lineární model je možné zobrazovat v rozhodovacím nebo kriteriálním prostoru. Nejprve schematicky znázorněme úlohu se dvěma proměnnými v rozhodovacím prostoru, kde souřadné osy budou reprezentovat hodnoty proměnných. Na hranici množiny přípustných řešení vymezené kriteriálním kuželem leží všechna nedominovaná řešení. Model VLP - grafické znázornění Při zobrazování v kriteriálním prostoru vynášíme na jednotlivé osy přímo hodnoty účelových funkcí. a Z1 2 2 C X 2 1 C X Modře jsou vyznačeny nedominované hodnoty Vícekriteriální programování - klasifikace metod Při řešení úloh VLP můžeme požadovat výsledky v podobě úplného popisu množiny nedominovaných řešení nebo nalezení nějaké její reprezentativní podmnožiny nebo výběru několika kompromisních variant. Chce-li uživatel vybrat jedinou kompromisní variantu, bude jeho rozhodnutí značně záviset na preferencích jednotlivých kritérií. Ty mohou být zadávány v různých fázích výpočtu: ► před započetím výpočtu, ► interaktivně v průběhu výpočtu, ► po skončení výpočtu, a to opět prostřednictvím aspiračních úrovní kritérií, pořadím kritérií, váhami kritérií nebo mírou kompenzace kriteriálních hodnot. Podle toho, kdy je informace o kritériích do modelu zapracována, dělíme výpočetní metody na: ► metody s preferenční informací a priori ► metody s preferenční informací a posteriori ► metody s postupným zpřesňováním preferenční informace ► metody kombinované Vícekriteriální programování - klasifikace metod Metody s informací apriori dělíme do několika skupin: ► metoda lexikografická ► metoda minimální komponenty ► řešení jednokriteriální úlohy s agregovanými kritérii ► záměna kritérií za omezení ► "minimalizace odchylek"od ideálních hodnot (při vhodně zvolené metrice) Metody s informací aposteriori spočívají v popisu množiny nedominovaných řešení, ve které následně uživatel vybírá kompromisní řešení. Patří sem: ► metoda parametrická (agregujeme kritéria s parametricky zadaným vektorem vah) ► metoda omezení (hledá nedominovaná řešení, kde hodnoty kritérií dosahují parametricky zadaných cílových hodnot) ► vícekriteriální simplexový algoritmus (postupně určuje nedominovaná bazická řešení) Metody interaktivní probíhají iterativně a jsou založeny na komunikaci mezi uživatelem a rozhodovatelem. Vícekriteriální programování - příklad Příklad z knihy Tomáš Šubrt, Ekonomicko-matematické metody: Vedení půjčovny lyžařského a snowboardového vybavení zvažuje optimalizaci sortimentu zboží. Do kalkulací zahrnuje obvyklou cenu za půjčení vybavení i riziko, že utrpí ztrátu, protože vybavení nebude půjčeno. Denní zisk [v Kč] při půjčení jednotlivých kompletů i riziko ztráty při nepůjčení [v bodech] jsou uvedeny v tabulce. lyžařský lyžařský lyžařský snowboardový komplet komplet komplet komplet sjezdový sjezdový běžecký dospělý dětský zisk 300 200 170 250 riziko 10 15 25 5 Společnost chce investovat nejvýše 1 mil. Kč do nákupu kompletů, přičemž snowboardové komplety chce nakoupit alespoň za 200 tis. Kč. Pořizovací cena každého z kompletů je 10 tis. Kč. Navrhněte, jak má společnost investovat, aby maximalizovala zisk a minimalizovala ztrátu. VLP - příklad, matematický model Označme xi,..., x4 proměnné vyjadřující počty nakoupených kompletů. Kriteriální funkce tedy jsou Zi = 300xi + 200x2 + 170x3 + 250x4 -> max Z2 = 1 0Xi + 1 5X2 + 25x3 + 5x4 /T7//7 Při pořizovací ceně kompletů 10 000 Kč budou mít omezení následující podobu: celkem lze koupit maximálně 100 ks kompletů, z toho nejméně 20 ks musí být snowboardové komplety: Xi +x2 + x3 + x4 < 100 x4 > 20 Dále musíme přidat obligátní podmínky : xi,x2,x3,x4 > 0 Správně bychom měli přidat ještě podmínky celočíselnosti, ale nebudeme pro zjednodušení zatím uvažovat. Řešením zjednodušených úloh modelu, kdy uvažujeme vždy pouze jednu kriteriální funkci dostaneme dílčí optimální řešení. VLP - dílčí optimální řešení, příklad Snadno lze zjistit, že minimálního rizika půjčovna dosáhne, jestliže nakoupí pouze požadované snowboardové komplety, tj. 20 ks po 10 000 Kč a ostatní komplety nebude kupovat vůbec. Podobně maximálního zisku půjčovna dosáhne, jestliže po zakoupení požadovaného množství snowboardových kompletů (tj. 20 ks) utratí všechny zbývající peníze za nejziskovější sjezdové komplety pro dospělé. Prostředky postačí pro zakoupení 80 ks těchto kompletů. Dílčí optimální řešení můžeme znázornit v kriteriální tabulce: Kriteriál výnos ní funkce riziko 80 dospělých sjezdových + 20 snowboardových 29000 880 20 snowboardových 5000 100 Z hlavní diagonály tabulky vidíme, že ideální řešení je ohodnoceno kriteriálními hodnotami zisku a rizika 29000 a 100, ale reálně neexistuje. VLP - lexikografická metoda Popišme si některé z metod s apriorní preferenční informací. Při použití lexikografické metody rozhodovatel určí pořadí významnosti kriteriálních funkcí (předpokládejme, že již jsou funkce označeny tak, že zi je nejvýznamnější a zk nejméně významné, jejich optimální hodnoty označme z°pt,..., z°kpt). Hledání kompromisního řešení spočívá v postupném řešení sekvence optimalizačních úloh max. zi = c1 x, x e X. Pokud má úloha více optimálních řešení, řešíme další úlohu: max. z2 = c2 • x, x g X, c1 x > z°pt. Opět je-li řešení více, postupujeme dále, až nalezneme kompromisní řešení jako bod optima úlohy max. zk = ck x, x e X, c1x > zop\ ..., ck"1x > z°k% Zmírnit předpoklad, že jednotlivé úlohy mají více než jedno řešení, je možné připuštěním odchylky 5-,, o kterou se můžou v jednotlivých krocích lišit hodnoty preferovaných účelových funkcí od svých optim. Například v druhém kroku bychom řešili úlohu max. z2 = c2 • x, x g X, c1x > zopt - £1, atd. Popsaná metoda v podstatě kopíruje reálné uvažování manažerů. VLP - lexikografická metoda, příklad Již víme, že při preferenci rizika je nejvýhodnější nakoupit pouze 20 snowboardových kompletů a při preferenci zisku 20 snowboardových a 80 dospělých sjezdových kompletů. Jaké by měla úloha řešení, jestliže budeme preferovat riziko, ale připustíme jeho odchylku z ideální hodnoty 100 na 120? Maximalizujeme tedy zisk zi = 300xi + 200x2 + 170x3 + 250x4 za omezení z2 = 10xi + 15x2 + 25x3 + 5x4 < 120 , (tj. že riziko nepřesáhne hodnotu 120) a dalších omezení modelu ^1 + ^2 + ^3 + ^4 < 100 x4 > 20 , Xi ,..., x4 > 0. Snadno vypočteme optimální řešení x<\ = 2, x2 = 0, x3 = 0, x4 = 20, tedy k požadovaným dvaceti snowboardovým přikoupíme ještě 2 dospělé sjezdové komplety. Zíkáme tak 5600 Kč a riziko bude rovno limitním 120 bodům. VLP - metoda minimální komponenty Jiným přístupem je stanovení kompromisního řešení podle minimální komponenty, kdy maximalizujeme nejmenší, tedy nejhorší komponentu vektoru hodnot účelových funkcí. Dostaneme tedy úlohu LP maximalizovat z = ô za podmínek c1 • x > ô, c2 • x > ô,... ck • x > ô, x e X . Pokud mají kritéria rozdílnou povahu, je třeba je nejprve převést všechna na maximalizační a upravit na bezrozměrné, aby byla zajištěna jejich srovnatelnost. VLP - metoda agregace kriteriálních funkcí Pomocí vhodně zvoleného operátoru je možné sloučit všechny kriteriální funkce do jediné. Obecně se při agregaci používají různé operátory, zde se jeví nejvhodnější lineární kombinace jednotlivých funkcí za použití normovaného vektoru vah v = (ví,..., vk). Místo původní optimalizační úlohy z = C x —>• MAX, x g X. řešíme jednorozměrnou úlohu zv = v C x max, x g X. Pozor! Při nastavení vektoru vah je třeba vzít v úvahu, že hodnoty funkcí se pohybují na různých škálách. Vyznačme agregované kritérium graficky (zelená přímka). Nemá praktickou interpretaci, je pouze kritériem pomocným. VLP - metoda agragace, příklad Při agregaci funkce zisku zi a funkce rizika z2 je třeba vzít v úvahu odlišnou povahu kritérií, například můžeme vynásobit z2 koeficientem (-1). Jestliže nastavíme vektor vah I00' 100 pak agregovaná účelová funkce bude mít tvar zv = 5,5xi - 4,25x2 - 15,25x3 + 7, 75x4. Snadno nahlédneme, že optimální řešení tedy bude X! = 0, x2 = 0, x3 = 0, x4 = 100, všechny peníze utratíme za snowboardové komplety. Optimální hodnota účelové funkce zv = 775, což nemá žádnou vypovídací schopnost, ale můžeme pro nalezené řešení dopočítat hodnotu zisku 25000 Kč a hodnotu rizika 500 bodů. VLP - převod kriteriálních funkcí na omezení Při postupném převodu kritérií na omezení postupujeme podobně jako u lexikografické metody. Předpokládáme opět, že jsou funkce označeny od nejvýznamnějšího po nejméně významné). Hledání kompromisního řešení spočívá v postupném řešení sekvence optimalizačních úloh max. zi = c1 x, x g X. Optimální hodnotu označíme z* a řešíme další úlohu, kde připustíme určitou odchylku od z\\ max. z2 = c2 • x, x g X, c1 x > z* - £1. Opět zjistíme z| a postupujeme dále, až nalezneme kompromisní řešení jako bod optima úlohy max. z/c = ck • x, x g X, c1x > z* - ô^,..., ck_1x > z£_i - ôk. Kritéria lze také převést na omezení najednou tak, že maximalizujeme pouze nejdůležitější kritérium z\ a přidáme do modelu současně všechna omezení z, > auh i = 2,... k ( aspirační úrovně všech kritérií auh i = 2,... k nastavíme někam mezi bazálni a ideálni hodnotu pro dané kritérium {z™in,z™ax).) Nevýhodou tohoto přístupu je, že může být obtížné nastavení aspiračních úrovní, aby nebyla přípustná množina prázdná nebo aby nebyl vliv kritérií eliminován úplně. Úvod Modely datových obalů (DEA) slouží k hodnocení technické efektivity produkčních jednotek na základě velikosti vstupů a výstupů (bez nutnosti cenového vyjádření). Historie: 1957: Farrell: model měření efektivity jednotek s jedním vstupem a výstupem 1978: Charnes, Cooper, Rhodes: CCR model: vícenásobné vstupy a výstupy, konstantní výnosy z rozsahu 1984: Banker, Charnes, Cooper: BCC model: proměnný výnos z rozsahu Uvažujme homogenní produkční jednotky, spotřebovávající stejný typ zdrojů (materiál, podlahová plocha, pracovníci, atd.), budeme je označovat vstupy, k produkci ekvivalentních efektů (tržby, zisk, počet obsloužených klientů, atp.), dále jen výstupy. Pokud v činnosti jednotek dominuje pouze jeden vstup a jeden výstup, lze snadno vyjádřit efektivitu pomocí poměrového ukazatele efektivita = výstup/vstup Pro vícenásobné vstupy a výstupy je možné jejich agregováním ukazatel modifikovat: efektivita = vážené výstupy/vážené vstupy Model s jedním vstupem a výstupem Uvažujme 8 poboček obchodní firmy, které charakterizujeme jedním vstupem (počet zaměstnanců) a jedním výstupem (počet uzavřených smluv s klienty). Efektivitu lze vyjádřit pomocí ukazatele "počet smluv na zaměstnance", údaje jsou zaznamenány v tabulce: Pobočka A B C D E F G H zaměstnanců 2 3 3 4 5 5 6 8 smluv 1 3 2 3 4 2 3 5 efektivita 0,5 1 0,667 0,75 0,8 0,4 0,5 0,625 Model s jedním vstupem a výstupem Data reprezentujeme graficky, viz: Ukazatel efektivity dané pobočky udává sklon přímky spojující příslušný bod s počátkem, pro pobočku B nabývá nejvyšší hodnoty - tuto přímku budeme dále nazývat efektivní hranicí. Nejlepší pobočkou je tedy pobočka B, efektivitu ostatních můžeme pak vyjádřit také v relativní míře. Například efektivita A / efektivita B =0,5 což znamená, že A dosahuje pouze 50% efektivity B. Tato relativní míra nabývá i pro ostatní pobočky hodnot z intervalu [0,1] a je nezávislá na jednotkách, ve kterých jsme vstup, resp. výstup měřili. Model s jedním vstupem a výstupem Jakým způsobem může jednotka A dosáhnout stoprocentní hodnoty, tj. efektivní hranice? Může snížit vstupy při zachování výstupů (model orientovaný na vstupy, v grafickém znázornění reprezentuje bod A^) nebo zvýšit výstup při zachování vstupů (model orientovaný na výstupy, v grafickém znázornění reprezentuje bod A2) nebo změnit obojí. Jednotky A^, A2 nazýváme virtuální, neodpovídají žádné reálné pobočce. Úsečka A\A2 reprezentuje všechny dostupné body na efektivní hranici, pro jejichž dosažení A nemusí zvyšovat počet zaměstnanců nebo snižovat počet uzavřených smluv. počet smluv / o H 5 počet zaměstnanců Model s jedním vstupem a výstupem Označíme-li souřadnice bodů >4[x,y], [xi,yi], A2[x2ly2], vzhledem k tomu, že >Ai, A2 leží na efektivní hranici, lze ve vyjádření relativní efektivity A použít ve jmenovateli místo jednotky B libovolnou z těchto virtuálních jednotek. Dostaneme pak -yly, neboť y = yi nebo -y/f2 =Y2/y neboť x = x2. V modelu orientovaném na výstupy můžeme relativní efektivitu interpretovat jako potřebné navýšení výstupu, ^ = f = 2, tedy efektivní hranice by A dosáhla zdvojnásobením počtu uzavřených smluv. Pro model orientovaný na vstupy převrácená hodnota relativní efektivity reprezentuje potřebnou redukci vstupů, ^ = \ = 0,5, tedy efektivní hranice by A dosáhla s polovinou zaměstnanců. Model s jedním vstupem a výstupem V předchozích úvahách jsme pracovali s předpokladem konstantních výnosů z rozsahu, kdy efektivní hranice byla tvořena polopřímkou, tj. pro každou pobočku s kombinací vstupu a výstupu [x,y] se předpokládá za dosažitelnou i kombinace [ax, ay] pro lib. a > 0. Ukazatel relativní efektivity pak vychází shodně, ať použijeme model orientovaný na vstupy či na výstupy. Za předpokladu variabilních výnosů z rozsahu je třeba efektivní hranici modifikovat. počet smluv Nyní tvoří hranice obal dat, tak že efektivní se jeví též jednotky E a H. Model s jedním vstupem a výstupem Ukazatel relativní efektivity se může měnit podle použitého modelu. Například pro jednotku F při orientaci na vstupy dostaneme hodnotu efektivita F^ I efektivita F = 215 = 0,4, kdežto při orientaci na výstupy hodnotu efektivita F/efektivita E = 1/2= 0,5 . počet smluv Dva vstupy a jeden výstup Uvažujme příklad 9 supermarketů , kde jako vstupy bereme počet zaměstnanců (v desítkách) a podlahovou plochu (v 1000 m2), výstupem rozumíme roční tržby. Za předpokladu konstantních výnosů z rozsahu můžeme dále pracovat s hodnotami vstupů přepočtenými na jednotku výstupu. Normované hodnoty jsou uvedeny v tabulce. Obchod ABCDEFGH I zaměstnanců plocha 4784256 5,5 6 3 3 1 2 4 2 4 2,5 2,5 tržby 11111111 1 Dva vstupy a jeden výstup V grafickém znázornění se efektivnější jeví ty obchody, které se nalézají blíž k počátku, efektivní hranice obaluje data následujícím způsobem: plocha/t žby 5 zaměstnanců/tib? Obchod A je neefektivní, míru jeho efektivity můžeme měřit radiálně jako |^[ = 0,8571 . Protože virtuální jednotka P je kombinací jednotek D,E, nazýváme je referenčními jednotkami pro A. Efektivní hranice lze dosáhnout též jinak než proporčním snížením obou vstupů o 15%, snížení pouze jednoho vstupu při zachování úrovně druhého demonstrují body , D. Jeden vstup a dva výstupy Nyní naopak uvažujme případ, kdy u 7 obchodních kanceláří sledujeme 1 vstup (počet obchodníků) a dva výstupy (počet obsloužených zákazníků a tržby. Hodnoty výstupů u jednotlivých poboček přepočtené na 1 obchodníka jsou uvedeny v tabulce. Kancelář A B C D E F G obchodníků 1111111 zákazníků tržby 1 2 3 4 4 5 6 5 7 4 3 6 5 2 Jeden vstup a dva výstupy Můžeme znázornit jednotkové výstupy jednotlivých kanceláří, efektivní hranice bude obalovat data z opačné strany, protože body ležící blíž k počátku reprezentují méně efektivní jednotky, (jde o jednotky A,C,D) klientů na obchodníka í QBV /A V / o \> / C r/\ G 1 1 1 1 1 0 5 tržby na obchodníka Míru neefektivity lze opět měřit radiálně, například pro jednotku D jako 1^1 = o, 75 . Pro bod A by analogická míra vyjadřovala pouze tzv. technickou neefektivitu, z bodu Q lze ještě zvýšit tržby bez ztráty klientů až na úroveň bodu B. CCR model Pro n jednotek Uu---,Unu nichž sledujeme m vstupů a r výstupů zavedeme označení xiq pro /-tý vstup q-\é jednotky a yiq pro y-tý vstup q-\é jednotky. Pro Uq značíme xq = (x1q, ..., xmq)', yq = (ylQ,..., yrqy. Hodnoty lze uspořádat do matic Pomocí vektorů nezáporných vah v = (1/1,..., i/m), u = U\,..., ur můžeme pro libovolnou jednotku Uq definovat virtuální vstup = 1/1X1Q + ... + vmxmq = vxq a virtuální výstup = 1/1/19 + ... + — uYq- Míru efektivnosti dané jednotky pak vyjádříme jako podíl jejího virtuálního výstupu a vstupu. CCR model optimalizuje váhy vstupů a výstupů tak, aby míra efektivnosti dané jednotky Uq, z = ?ľq*'''*"rírq = byla maximální za podmínky, že J J ^ • ■~rvmxmq vxq J 1 J efektivnosti ostatních jednotek jsou nejvýše jednotkové. Existuje-li kladné řešení s optimální hodnotou účelové funkce z* = 1, pak se jednotka Uq označuje jako CCR efektivní. CCR model orientovaný na vstupy Celý model pro jednotku Uq lze formulovat jako úlohu lineárního lomeného programování za omezeni uiyik+...+uryrk < 1 , k = 1 , . . . A7, v^x^k+...+vmxmk Uí > 0, Vj > 0, / = 1,... /77, y = 1,... r. Úlohu lze snadno linearizovat pomocí Charnes-Cooperovy transformace: Z = UAyAq + • • • + UrYrq -> maXu,v za omezení V^X^q + . . . + VmXmq = 1 U\Y\k + • • • + UrYrk < l/iXi/c + . . . + VmXmk, k = 1 , . . . A7, Ui >0, Vj > 0, / = 1,... /77, y = 1,... r. Tento model nazýváme CCR modelem orientovaným na vstupy. Množina takových indexů ke {1,... a?} efektivních jednotek, pro které jsou omezující podmínky v úloze pro Uq aktivní, definuje tzv. referenční množinu pro Uq. CCR model - príklad Uvažujme úlohu s dvěma vstupy a jedním výstupem, hodnoty pro 6 jednotek jsou uvedeny v tabulce: Jednotka A B C D E F x^ x2 4 7 8 4 2 10 3 3 1 2 4 1 y 11111 1 Linearizovaná úloha pro jednotku A bude mít podobu: z = u —>• max za omezení 4l/i +31/2 = 1, U, V\ , 1/2 > 0 u < 4i/i + 3v2 (A) u <7vi + 3v2 (B) u <8vi + v2 (C) u < AvA + 2i/2 (D) u < 2i/i +4i/2 (E) u < IO1/1 + v2 (F) Úlohu lze vyřešit standartními postupy lineárního programování, pro A dostaneme řešení z* = u* = 6/7, i/j" = i/2* = 1 /7 . Jednotka A není efektivní, protože z* = 6/7 < 1, omezující nerovnice pro jednotky D, E jsou aktivní, tedy D,E jsou kandidáty na referenční jednotky pro A. CCR model - príklad Úlohy pro ostatní jednotky budou podobné, lišit se budou pouze v omezující rovnosti, pro jednotku B to bude podmínka 7^ + 3v2 = 1, atd. V tabulce jsou shrnuty výsledky úloh pro všechny jednotky: jednotka x2 y i/* v2 z* = ď referenční množina A 4 3 1 1/7 Ml 6/7 D, E B 7 3 1 1/19 4/19 12/19 C,D C 8 1 1 1/12 1/3 1 C D 4 2 1 1/6 1/6 1 D E 2 4 1 3/14 1/7 1 E F 10 1 1 0 1 1 C Vidíme, že jednotky C,D,E jsou efektivní. Optimální hodnota účelové funkce pro F je sice také rovna 1, ale referenční jednotkou pro F je C, protože má při stejném vstupu v2 nižší vstup 1/1. V definici CCR efektivity je tedy třeba zdůraznit: jednotka je CCR efektivní, je-li její z* = 1 a existuje aspoň jedno řešení, pro něž ď > 0, v* > 0. Požadavek existence kladných vah lze zapracovat přímo do modelu, kdy v podmínkách nezápornosti proměnných změníme pravou stranu na nějaké e > 0. CCR model - duální úloha Zapišme CCR model pro jednotku Uq maticově: z = uyq -> maxu.v za omezení vxq = 1 uY < vX, u, v > 0. K úloze formulujme její duální problém, duální proměnné označíme 0 a A = (Ai,... Aa?) : z = 6 -r mirio.x za omezení (9xq > XA, YA > yq, A > 0 Použití duálního modelu je výhodné z výpočetního i interpretačního hlediska. Duální CCR model - interpretace Model vlastně hledá virtuální jednotku se vstupy a výstupy XA, YA, která je lepší nebo alespoň srovnatelná s radiální projekcí hodnocené jednotky Uq na efektivní hranici: <9xq > XA, YA > yq Hodnocená jednotka Uq leží přímo na efektivní hranici, je-li totožná s nalezenou virtuální jednotkou. Nutně tedy musí být optimální hodnota účelové funkce modelu 0* (tzv. Farellova efektivita) vyjadřující potřebnou radiální redukci vstupů k dosažení efektivní hranice jednotková, #* = 1. Při splnění této podmínky je jednotka Uq též nazvána technicky efektivní. K dosažení CCR-efektivity však současně musí být nulové všechny přídavné proměnné převádějící omezující nerovnosti na rovnosti: s = <9xq - XA = 0, s+ = YA - yq = 0 . Při splnění všech těchto podmínek vyhovuje hodnocená jednotka tzv. Pareto-Koopmansově definici efektivity, tj. není možné zlepšit žádný z jejích vstupů a výstupů, aniž by současně nedošlo ke zhoršení jiného. Duální CCR model - alternativní formulace Uvažujme primární CCR model s požadavkem nenulovosti vah u, v > e > 0 a označme e = (1,..., 1 )T. Duální úlohu lze též formulovat ve tvaru z = 0 - e • (e • s+ + e • s") -> mineXs+^ s_ za omezení s = 6>xq - XA, s+ = YA-yq, A, s+, s" > 0 Optimální hodnoty modelu dávají jednotce Uq návod pro zlepšení vstupů a výstupů na xq, yq pomocí tzv. CCR - projekce: Xq = 0*Xq - S~*, Yq' = yq + S+*, nebo též xq = XA*,yq/ = YA*. Přitom ty indexy j e {1,..., a?}, pro něž jsou hodnoty A* kladné, určují referenční jednotky pro Uq. CCR model orientovaný na výstupy Pro jednotku Uq můžeme také formulovat CCR model orientovaný na výstupy, zapišme jej rovnou v upravené duální podobě: z = 9 + e • (e • s+ + e • s") minQXs+^ s_ za omezení S = Xq - XA, s+ = YA-9yq, A, s+, s" > 0 Pokud je 9* > 1, jednotka Uq není efektivní a hodnota 9* vyjadřuje potřebnou míru proporcionálního navýšení vstupů. Opět lze analogicky definovat CCR projekci na efektivní hranici jako = XA*, yq' = YA*. V CCR modelech platí, že míry efektivnosti jednotky Uq při orientaci na vstupy či výstupy (tj. optimální hodnoty účelových funkcí modelů) jsou vzájemně převrácenými hodnotami 0* • 9* = 1 BCC model orientovaný na vstupy Jako modifikaci modelu CCR, který předpokládá konstantní výnosy z rozsahu a definuje tak kónický obal dat, navrhli Banker, Charnes a Cooper model využívající variabilní výnosy z rozsahu, tzv. BCC model. Při tomto přístupu jsou data obalována konvexním obalem, jako virtuální jednotky se neuvažují libovolné nezáporné kombinace XA, YA, ale pouze kombinace splňující podmínku eA = 1 . Díky této dodatečné podmínce vychází zpravidla jako efektivní větší počet hodnocených jednotek. Uveďme formulaci duálního BCC modelu orientovaného na vstupy: z = 0 - e • (e • s+ + e • s") -> minexs+^ s_ za omezení S" = 6>xq - XA, s=YA-yq, eA = 1 A, s+, s" > 0 Jako BCC efektivní jsou identifikovány ty jednotky, pro něž je 0* = 1,s+* =0,s * =0. Další DEA modely Kromě základních DEA modelů byla navržena řada jejich modifikací, mimo jiné: ► aditivní, též SBM (Slack-Based Measure) model: nenutí uživatele rozlišovat mezi orientací na vstupy nebo výstupy, měří efektivnost přímo pomocí přídavných proměnných s~, s+ ► DEA modely s nekontrolovatelnými výstupy a vstupy ► DEA modely s nežádoucími výstupy a vstupy ► Modely superefektivnosti ► diskrétní modely, např. FDH (Free Disposable Hull) model ► pro hodnocení změn efektivnosti v čase navržený Malmquistův index Metody jsou podrobněji popsány v použité literatuře: ► J. Jablonský, M. Dlouhý: Modely hodnocení produkčních jednotek, Professional Publishing, Praha 2004 ► W. W. Cooper, L. M. Seiford, K. Tone: Data Envelopement Analysis, Springer, New York 2007 Použití DEA k hodnocení efektivnosti dopravních podniků Údaje z výroční zprávy Sdružení dopravních podniků za rok 2012 (http://www.sdp-cr.cz/o-nas/vyrocni-zpravy/) byly použity k hodnocení efektivnosti podniků z 19 měst. V první tabulce jsou uvedeny údaje v následujícím pořadí: ► počet přepravených osob (tis. osob) ► tržby (tis. Kč) ► vozové kilometry (tis.) ► počet zaměstnanců ► z toho řidičů Druhá tabulka popisuje vozový park. město přeprav. tržby vozokm zamést. ridicu 1. Brno 352 052 994 040 38 118 2 727 1 375 2. České Budějovice 38 091 129 059 5 673 384 187 3. Děčín 8 938 42 731 3 678 207 132 4. Hradec Králové 35 162 120 854 6 242 401 226 5. Chomutov-Jirkov 5 223 50 367 1 838 253 163 6. Jihlava 13 530 50 232 2 821 170 94 7. Karlovy Vary 13 436 65 174 2 624 260 148 8. Liberec 32 656 192 236 8 648 377 169 9. Mariánské Lázně 3 844 11 439 495 30 19 10. Most-Litvínov 27 418 110 059 4 908 471 216 11. Olomouc 52 737 143 318 5 902 432 255 12. Opava 10 750 50 476 3 046 180 115 13. Ostrava 96 389 519 873 33 773 2 008 1 026 14. Pardubice 27 178 119 280 5 721 406 189 15. Plzeň 99 154 300 097 15 102 1 030 570 16. Praha 1 383 124 4 508 422 167 760 10 595 4 207 17. Teplice 15 039 94 159 5 726 265 176 18. Ustí nad Labem 47 091 203 278 7 347 501 253 19. Zlín-Otrokovice 32 335 119 506 4812 340 184 město autobusy tramvaje trolejbusy metro celkem 1. Brno 298 309 151 0 758 2. České Budějovice 83 0 58 0 141 3. Děčín 55 0 0 0 55 4. Hradec Králové 95 0 36 0 131 5. Chomutov-Jirkov 29 0 19 0 48 6. Jihlava 32 0 32 0 64 7. Karlovy Vary 67 0 0 0 67 8. Liberec 139 68 0 0 207 9. Mariánské Lázně 4 0 9 0 30 10. Most-Litvínov 80 57 0 0 137 11. Olomouc 77 60 0 0 137 12. Opava 34 0 34 0 68 13. Ostrava 297 273 62 0 632 14. Pardubice 73 0 55 0 128 15. Plzeň 113 122 88 0 323 16. Praha 1214 920 0 738 2872 17. Teplice 65 0 38 0 103 18. Ustí n. Labem 73 0 68 0 141 19. Zlín-Otrokovice 37 0 57 0 94 Použití DEA k hodnocení efektivnosti dopravních podniků Jako vstupy pro analýzu byly použity celkové počty zaměstnanců a celkový vozový park, jako výstupy počty přepravených osob, tržby a ujeté vozové kilometry. Byl zvolen model CCR orientovaný na vstupy, výpočty byly realizovány prostřednictvím doplňku Solver pro MS Excel a aplikace pro DEA (http://nb.vse.cz/ jabloň/) Výsledky jsou uvedeny v následující tabulce, červeně jsou vyznačeny podniky, které vyšly jako efektivní. město efektivita čísla refer. jednot. 1. Brno 0,9889 16 2. České Budějovice 0,833 8 9 16 3. Děčín 1 3 4. Hradec Králové 0,8546 8 16 17 5. Chomutov-Jirkov 0,6684 16 6. Jihlava 0,8493 8 16 17 7. Karlovy Vary 0,6592 3 16 8. Liberec 1 8 9. Mariánské Lázně 1 9 10. Most-Litvínov 0,6092 3 16 17 11. Olomouc 0,9351 16 12. Opava 0,8209 8 16 17 13. Ostrava 0,8838 3 16 17 14. Pardubice 0,7743 3 16 17 15. Plzeň 0,8426 8 16 17 16. Praha 1 16 17. Teplice 1 17 18. Ustí n. Labem 0,9465 8 16 19. Zlín-Otrokovice 0,8695 3 16 17 Matematická analýza funkcí více proměnných Předpokládejme dále, že funkce f je spojitě diferencovatelná až do řádu 2. Gradient funkce Buď X c Rn, f : X ->> r funkce a? proměnných. Gradientem funkce / v bodě t = ,..., tn) e X nazývame vektor V/(t) = (/í1(t),...,4(t))T. Hessova matice Hessovou maticí funkce / v bodě t = (ři,..., tn) e X nazývame symetrickou matici řádu n\ w(t) = (Cy(t))"/=i Příklad : Určete gradient a Hessovu matici funkce /(x, y) = x ■ y2 v bodě (5,3). Řešení: Parciální derivace prvního řádu jsou: fx(x,y) = y2, /y(x,y) = 2x y, tedy V/(5,3) = (9,30)T. Parciální derivace druhého řádu jsou: = 0, C(x,y) = 2y, /^(x,y) = 2x, tedy H(5,3) = Směrové derivace Uvažujme X c Rn, funkci / : X r, bod t g X a jednotkový vektor s e Rn. Vytvoříme funkci jedné proměnné v?(x) = /(t + x.s). Hodnotu nazveme derivací / ve směru s a značíme 4'(t). (pozn.: obdobně definujeme /^(t) jako <£"(0).) Dá se ukázat, že platí 4'(t) = s • V/(t), 4//(t) = s.H(t).sT. Příklad : Určete první a druhou derivaci funkce /(x, y) = x • y2 ve směru Řešení: Víme, že V/(x,y) = (y2, 2xy)T, tedy /s'(x,y) = ^±§^. Hessova matice je: H(x,y) = ^ ^ 2x )'tec^ 4"(*,y) = | • (0 + 2y + 2y + 2x) = 2y + x. Grafické znázornění funkce dvou proměnných V třírozměrném prostoru si můžeme graf funkce dvou proměnných představit jako zemský povrch. Pro znázornění povrchu ve 2D se používají většinou vrstevnice funkce. Grafické znázornění funkce dvou proměnných X Podobným způsobem si můžeme znázornit třeba funkci /(x,y) = x2 2 -2 -2 -1.5 -1 0.5 1 Vrstevnicí funkce /(x,y) "o nadmořské výšce c"rozumíme množinu všech bodů (x,y) g m2 takových, že platí /(x,y) = c. Například pro výše uvedenou funkci f(x, y) určíme nultou vrstevnici jako množinu všech řešení rovnice o dvou neznámých J+y2 = 0. Zřejmě musí být x = 0, ale y je libovolné, tedy dostaneme množinu {(0,y), y e R}. Grafické znázornění gradientů funkce dvou proměnných Gradient V/(x,y) většinou znázorňujeme jako vektor vycházející z bodu (x, y) do bodu (x + ťx(x, y), y + fý(x1 y)). Na obrázku vidíme gradienty funkce /(x,y) = 2X 2 v bodech pravidelné sítě. ľ 1 - i • 1 [ 1 - é. t. * *. *. * "S i •/ r £ i -~ -» ^ i. i J V ¥ * — $ t r í* - m w ^ i 4 ^ ^ % *s t J* * - * . V i i # * ► * 1 m- m- * «. 1 ř -» ■h 1 ď 0-' * * I_ *- - . ^ p >} B w- *-— *—- _ ^ W * - » ■ —» ->->"->—* +- m- - - « ú-- ■í i* * ——^ • * » ^ r •i i. P :í •x * * ' * f Si * * *- * t — t v *- i «f ^ Ť ■T % * ._, .» --* í* r t * *, * * * , - • j, -j t ť 4 i v 4 * ,f r r t * * ^ * * <■ j 1 i' i - 1 - 1 ľ 1 i -2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 Gradienty a vrstevnice Znázorníme-li gradienty funkce do stejného obrázku s vrstevnicemi, můžeme si všimnout, že se jeví jako normálové vektory vrstevnic. Dá se ukázat, že libovolná funkce / v zadaném bodě x nejprudčeji roste ve směru gradientu V/(x) a nejstrměji klesá ve směru - V/(x). Konvexní množina Množinu M cRn nazveme konvexní, jestliže pro každé dva její body A, B jsou všechny body úsečky AB také prvky množiny M. Tuto vlastnost můžeme analyticky vyjádřit symbolickým zápisem: A,Be M^WXe (0,1) : A/A + (1 - X)B e M Na obrázku je znázorněn příklad konvexní a nekonvexní množiny. Poznámka: Průnik dvou konvexních množin je opět konvexní množinou (toto tvrzení lze tedy zřejmě rozšířit pro průnik více konvexních množin). Konvexní funkce Funkci / definovanou na konvexní množině Meť nazveme konvexní na M, jestliže pro každé dva body A, B e M platí: VA G (0,1) : f{\A + (1 - \)B) < Xf(A) + (1 - A)/(B). Pokud je pro všechna A / B a A e (0,1) tato nerovnost ostrá, je funkce / na množině M ostře konvexní. Geometrický význam: "Spojnice každých dvou bodů grafu leží nad grafem."Na obrázku je znázorněn příklad funkce /(x, y) = x2 + y2, která je konvexní v r2. Konvexní funkce Příklady konvexních funkcí v Rn: ► Pro libovolný vektor c e Rn je lineární funkce /(x) = cT • x konvexní na Rn (není ale ostře konvexní). Pro konvexní funkce platí řada tvrzení: ► Jsou-li /(x) a flf(x) konvexní funkce, pak jejich součet /(x) + g(x) je též konvexní (totéž platí i pro součin /(x) • g(x) v případě nezápornosti funkcí). ► Pro konvexní funkci /(x) na Rn a libovolnou konstantu c platí: Množina X = {x eRn : /(x) < c} je konvexní. ► Protože průnik konvexních množin je konvexní množinou, zřejmě je i přípustná množina lineárních úloh X = {x e Rn : A • x < b} pro libovolnou matici A a vektor pravých stran b konvexní množinou. ► Euklidovská metrika llx Říkáme, že X je konvexní polyedr. Hessova matice konvexní funkce Funkci / nazveme konvexní v bodě t, jestliže existuje okolí tohoto bodu, na kterém je konvexní. U funkce jedné proměnné lze konvexitu rozpoznat podle znaménka druhé derivace. Zobecněním této úvahy pro funkci více proměnných dostaneme tvrzení: Dvakrát diferencovatelná funkce / je konvexní v bodě t právě když pro každý směr s platí: 4"(t) > 0 (při platnosti ostré nerovnosti dostaneme ostrou konvexitu). Tedy Hessova matice H(t) má následující vlastnost: VSGť: /s"(t) = S • H(t) • ST > 0 V lineární algebře se takové matice nazývají pozitivně semidefinitní (pokud je nerovnost pro každé nenulové s ostrá, pak je matice pozitivně definitní). Příklad : Je funkce /(x,y, z) = x2 + z • y2 konvexní v bodě [1,1,1]? / 2 0 0 \ Řešení: Spočítáme Hessovu matici: H(1,1,1)= 0 2 2 , například V 0 2 0 / pro vektor s = (-1, -1,2) platí s • H(1,1,1) • sT = -4 < 0. Funkce není v bodě [1,1,1] konvexní. Lokální extrémy Řekneme, že funkce / :ť-^Mmáv bodě a e Df : 1. lokální maximum, když existuje jeho č-okolí Us(a) c Df takové, že Vx e Uô(a) platí f (x) < f (a) 2. lokální minimum, když existuje jeho č-okolí Us{d) c Df takové, že Vx g O; (a) platí f(x) > f (a) Poznámka: jsou-li nerovnosti splněny na ryzím okolí Us(á) \ {a} ostře, pak extrémy nazýváme ostré. Poznámka: Funkce / může mít lokální extrémy pouze ve stacionárních bodech (tedy bodech s nulovým gradientem), nebo v bodech, v nichž neexistuje aspoň jedna parciální derivace prvního řádu. Příklad: Funkce f{x,y) = x2 - y2 má stacionární bod [0,0], kde není extrém, jedná se o sedlový bod. Lokální extrémy Při rozhodování o tom, zda ve stacionárním bodě nastává lokální extrém, se řídíme pomocí Hessovy matice. Zřejmě je-li ve svém stacionárním bodě funkce / ostře konvexní, tj. má-li zde pozitivně definitní Hessovu matici, pak zde nabývá svého lokálního minima. Pozitivně definitní matici lze rozpoznat podle toho, že má všechny hlavní minory, tj. determinanty vycházející z levého horního rohu, kladné. Podmínky pro existenci extrému shrnuje Sylvestrovo kritérium Buď / :ť^RaaeD/ její stacionární bod. Označme Dk(a), k = 1,..., n determinant submatice vytvořené z prvních k řádků a sloupců Hessovy matice H(a). Pak 1. Jestliže (a) > 0, D2(a) > 0,..., Dn(a) > 0, má / v a lok. minimum. 2. Jestliže Di (a) < 0, D2(a) > 0,..., (-1 )A?DA?(a) > 0, má / v a lok. maximum. 3. Jestliže jsou všechny minory Dk(a), k = 1,..., n nenulové a přitom neplatí žádná z předchozích možností, pak v bodě a není extrém. Příklad: Hessova matice funkce /(x, y) = x2 - y2 ve stacionárním bodě [0,0] je: H(0,0) = ^ ^ ^ ^, její hlavní minory jsou (0,0) = 2, D2(0,0) = -4, tedy je indefinitní a v bodě [0,0] není extrém. Lokální extrémy - příklad Analytické řešení úlohy hledání volných extrémů funkce / vť tedy spočívá v nalezení stacionárních bodů (resp. bodů, kde neexistuje gradient) a vyšetření definitnosti Hessovy matice v těchto bodech. Při hledání stacionárních bodů řešíme soustavu n rovnic o n neznámých. Příklad : Nalezněte extrémy funkce /(x, y) = x2y + y2x - xy. Řešení: První derivace jsou fý = 2xy + y2 - yjý = x2 + 2xy - x. Položíme-li obě parciální derivace současně nule, má soustava následující řešení: x = y = 0; x = 0, y = 1; x = 1, y = 0; x = 1 /3, y = 1 /3, což dává čtyři stacionární body dané funkce. Hodnoty Hessovy matice ve stacionárních bodech jsou postupně H(0,0) = ^ ^ 0 )' 1 ^ = H(1,0) = ( ° J ),H(1/3,1/3)=^g 2/3 ) ■ Pouze P°slední matice je pozitivně definitní, funkce má jen jedno lokální minimum, a to v bodě [1/3,1/3]. Globální extrémy Řekneme, že funkce / dosahuje na množině X v bodě a e X svého 1. globálního maxima jestliže Vx e X platí /(x) < /(a) 2. globálního minima jestliže Vx e X platí /(x) > /(a) Poznámka: Místo pojmu globální též používáme pojem absolutní. Opět definujeme ostré extrémy, jestliže nerovnosti jsou ostré pro Vx / a. Weierstrassova věta: Je-li X c Rn ohraničená, uzavřená množina a / : Rn —>• R spojitá funkce na X, pak má / na X globální extrémy, a to buď v bodech lokálních extrémů nebo na hranici množiny X. Poznámka: Není-li množina X uzavřená nebo ohraničená, pak globální extrémy nemusí existovat. Pokud extrémy existují, jsou jejich hodnoty určeny jednoznačně. Funkce však může nabývat těchto hodnot obecně ve více bodech. Hranici množiny lze většinou popsat pomocí rovnic. Vyšetřování hranice je úlohou s omezením. Globální extrémy - příklad Určete globální extrémy funkce f(xy) = (x - 1 )2 + (y - \)2 na obdélníku, který je určen body ,4= [0; 0]; B = [2; 0]; C = [2; 1]; D = [0; 1]. Řešení: Nalezneme lokální extrémy funkce /. Spočteme parciální derivace ťx = 2x - 2 a fy = 2y - 1 a nalezneme stacionární bod s = [1, \\. Matice kladné a proto v bodě s nastává lokální minimum funkce /. Hranice zadané množiny je tvořena čtyřmi úsečkami AB, BC, CD a DA. Je tedy třeba řešit čtyři optimalizační úlohy s funkcí / a postupně s podmínkami \/i : y = 0, V2 : x = 2, V3 : y = 1 a V4 : x = 0. Pozor! Při této formulaci je zapotřebí zvlášť vyšetřit body >A, B, C, D, protože nehledáme extrémy na celých hraničních přímkách, ale pouze na příslušných úsečkách. Globální extrémy - příklad Úlohy optimalizace f za podmínky VH kde / = 1,2,3,4 převedeme na ekvivalentní úlohy nalezení lokálních extrémů funkcí F,, kde Fi(x) = /(x,0) = (x-1)2 + l, F2(y) = /(2,y) = (y-l)2 + 1, F3(x) = /(x,1) = (x-1)2 + l, F4(y) = /(0,y) = (y-l)2 + 1. Snadno se zjistí, že jednotlivé úlohy mají minimum v bodech postupně: a = [1,0], b = [2, |], c = [1,1] a d = [0, \\. Hodnoty funkce / ve všech podezřelých bodech shrneme v tabulce: X s A B C D a b c d f(x) 0 5 4 5 4 5 4 5 4 i 4 1 i 4 1 Je zřejmé, že nejmenší hodnoty dosahuje funkce v bodě s = [1, \] a největší v bodech A, B, C, D. Úloha nelineárního programování (NLP) Úlohu hledání extrémů funkce n proměnných f(x) na množině M vymezené podmínkami gA (x) < (resp. =, resp. >)0 flk(x) < (resp. =, resp. >)0 flfm(x) < (resp. =, resp. >)0, kde alespoň jedna z funkcí /, gi,..., gn je nelineární, nazveme úlohou nelineárního programování (NLP). Je-li m = 0, tj. nejsou přítomna žádná omezení, hledáme tedy extrémy funkce f na celém Rn a hovoříme o volných extrémech. V případě, kdy jsou na proměnné uvalena omezení, tj. m > 0 nebo když je definiční obor funkce / limitován na nějakou podmnožinu X c Rn, hovoříme o vázaných extrémech. Poznámka: U úloh NLP nemusí existovat žádné řešení nebo naopak může existovat více extrémů, z nichž některé jsou pouze lokální. Optimum nemusí ležet pouze na hranici přípustné množiny! Úloha nelineárního programování (NLP) - příklad Uvažujme úlohu optimalizace funkce f(x, y) = x3 - 3x + y3 - 3y na množině M vymezené nerovnostmi x > 0, y > 0,2x + 2y < 5. Problém si můžeme znázornit graficky. Modře je vyznačena přípustná množina, vrstevnice jsou odstupňovány od nejnižší červené po nejvyšší žlutou. Zřejmě má funkce / na množině M minimum v bodě [1,1 ] a maximum v bodech [0;2,5] a [2,5;0]. Optimalizační úloha s omezením ve formě rovností Uvažujme úlohu na vázaný extrém f (x) —>• min , na množině M vymezené soustavou m rovnic g,(x) = 0, / = 1,... m. Jsou - li funkce f\gh i = 1,..., m spojitě diferencované a jsou - li gradienty omezení V g, lineárně nezávislé vektory (tj. žádné omezení není nadbytečné), pak pro bod optima x* existují jednoznačné hodnoty Ai, ..., Am, takové, že: V/(x*) + E£i A/. Vff/(x*) = 0. Čísla Ai, ..., Am se nazývají Lagrangeovy multiplikátory a umožňují převedení optimalizační úlohy na řešení systému rovnic. Jaký je formální postup? Vytvoří se tzv. Lagrangeova funkce L(x, A) = /(x) + E" i A/ • ff/(x) a sestaví se podmínky pro její stacionární body, tzv. podmínky 1. řádu: VxZ.(x,A) = 0, VAZ-(x,A) = 0 Jde o systém n + m rovnic pro n + m neznámých (posledních m rovnic vyjadřuje vlastně vazební podmínky). Jestliže má tento systém řešení (x*, A*) a jsou-li / i M konvexní, pak je bod x* globálním minimem funkce / na množině M. Optimalizační úloha s omezením ve formě rovností Ukažme si metodu Lagrangeových multiplikátorů na následující úloze: Najděte patu kolmice spuštěné z bodu [5,1,2] na rovinu 2x + 3y + z = 6. Řešení: Hledáme tedy bod [x, y, z] ležící v zadané rovině, pro nějž je vzdálenost od bodu [5,1,2] minimální. Místo minimalizace funkce /(x, y, z) = y/(x - 5)2 + (y - 1 )2 + (z - 2)2 můžeme pro zjednodušení výpočtu minimalizovat její druhou mocninu. Abychom mohli použít Lagrangeův multiplikátor, je třeba rovnici omezení anulovat: 2x + 3y + z - 6 = 0. Sestavme Lagrangeovu funkci úlohy: Z_(x, y, z, A) = (x - 5)2 + (y - 1 )2 + (z - 2)2 + A(2x + 3y + z - 6) a určeme její parciální derivace: /_*(x,y,z,A) = 2(x-5) + 2A, /_y(x,y,z, A) = 2(y-1) + 3A, /_z(x,y,z,A) = 2(z-2) + A, /_A(x, y, z, A) = 2x + 3y + z - 6. Položíme parciální rovnice rovny nule a dostaneme lineární systém, jehož vyřešením získáme bod optima [ff, ]f ]. Protože minimalizovaná funkce i přípustná množina jsou konvexní, nalezli jsme bod minima. Ekonomická interpretace Příklad z M. W. Klein: Mathematical Methods for Economics: Uvažujme úlohu hledání optima spotřebitele, který má 6 dolarů, které chce utratit za oběd v samoobslužné restauraci, kde se polévka i hlavní chod platí na váhu, přičemž cena za 1 unci polévky je $0,25 a za 1 unci hlavního chodu je $0,5. Označíme-li Sal/ zakoupené množství obou chodů (v uncích), pak rozpočtové omezení můžeme zapsat jako 6 = f + |. Hledáme takovou kombinaci jídel splňující tuto podmínku, která maximalizuje užitkovou funkci U{S, v) = !*& + mm. Řešení: Zavedeme Lagrangeovu funkci Z_(S, V, A) = ^ + ^P- - A(f + | - 6). Podmínky prvního řádu jsou: LS{S, V1\) = ±-±=0 Lv(S, V,\) = ±-±=0 LX(S, V,X) = f + |-6 = 0 Z prvních dvou rovnic lze vyjádřit, že A = | = ^, neboli S = 2V. Spolu s poslední podmínkou dostaneme řešení S* = 12, V* = 6 uncí, A* = ^, což dává užitek 17(12,6) = 2,14. Ekonomická interpretace Znázorněme si uvažovanou úlohu graficky. sÝ 24 12 6 12 V Sklon rozpočtové linie je dán vztahem dán poměrem cen: ^ = -2. Sklon indiferenční křivky je dán poměrem mezních užitků (mezní míra substituce): $ = -j%. Spočteme mezní užitky £/s(S, V) = ^, IV(S, V) = jejich podíl je yy. = 1. Protože v bodě optima (S*, V*) je sklon rozpočtové linie a S indiferenční křivky shodný, platí: -2 = - neboli ^1 — (rovnováha spotřebitele). Ekonomická interpretace Získáme-li dodatečný dolar, budeme-li tedy chtít utratit $7, u nového optimálního řešení bude zachován poměr spotřebovaných jídel: S* = 14, V* = 7 a hodnota Lagrangeova multiplikátoru poklesne na j. Získaný užitek bude (7(14,7) = 2,29. Přírůstek užitku je tedy AU= 17(14,7) - 17(12,6) = 2,29-2,14 = 0,15 = (^) • 1. Zřejmě jeden dodatečný dolar vyvolal (^)-násobný přírůstek užitku, což je něco mezi \ a \. Můžeme říct, že optimální hodnota Lagrangeova multiplikátoru vyjadřuje mezní užitek peněz určených k útratě. Tento vztah lze ukázat, vyjádříme-li si optimální množství jídel při rozpočtovém omezení B\ S* = 2B, V* = B a A* = ^. Optimální užitek při rozpočtu B je po úpravě: f(B) = U(2B, B) = ^/a?(2) + ln(B). Derivováním podle B získáme jeho mezní užitek ť{B) = ^, což je rovno A*. Podobně v úlohách optimalizace výrobního programu, budou Lagrangeovy multiplikátory u omezení pro jednotlivé vstupy vyjadřovat mezní užitek při zvýšení jejich kapacity. Tedy jsou rovny ceně, kterou je výrobce ochoten za dodatečnou jednotku vstupu zaplatit, proto se pro ně používá název stínové ceny. Lagrangeova funkce - postačující podmínky pro optimum Pro odvození podmínek 2. řádu uvažujme kvadratickou funkci Q(x, y) = ax2 + 2bxy + cy2, kterou lze též zapsat maticově jako Q(x,y) = (x,y) • ^ ^ c ) ( y )' přeclPok|ádejme, ^e hledáme optimum této funkce na množině dané lineární rovnicí Ax + By = 0. Vyjádříme-li y = - |x a dosadíme-li do Q, dostaneme /(x) = Q(x, -|x) = ax2 + 2bx(-|x) + c(-|x)2 = -^[2MB - a£2 - cA2]. Výraz uvnitř hranaté závorky lze také zapsat jako determinant matice / 0 A B \ H = i A a b \, což je vlastně Hessova matice Lagrangeovy funkce V B b c J /.(A, x, y) = X(Ax + By) + Q(x, y). Pokud je det(H) záporný, je funkce f (x) konvexní, což je postačující podmínka pro existenci minima ve stacionárním bodě (a je-li kladný, je f{x) konkávni - podmínka pro maximum). Lagrangeova funkce - postačující podmínky pro optimum Zobecníme-li odvození z předchozího slajdu pro funkci dvou proměnných /(x, y) optimalizovanou na množině dané rovnicí g(x, y) = c , dostaneme podmínky 2. řádu: Označme H(A, x, y) Hessovu matici Lagrangeovy funkce /.(A, x, y) = A(g(x, y) - c) + /(x, y). Pak je-li ve stacionárním bodě determinant c/eř(H(A,x,y)) ► kladný, je stacionární bod bodem maxima ► záporný, je stacionární bod bodem minima Příklad: Pro úlohu zákazníka restaurace má Lagrangeova funkce L{\, S, V) = ^p- + ^ + A(f + | - 6) Hessovu matici /Ol 1 \ H=\ l ~2^2 0 . Její determinant je W o ) det(H(\ S, \/)) = ^2 + ^2, což je kladné číslo pro jakékoliv S, \/, takže ve stacionárním bodě nastává maximum. Lagrangeova funkce - postačující podmínky pro optimum Zobecněme podmínky 2. řádu dále pro funkci n proměnných /(xi,..., xn) optimalizovanou na množině dané soustavou rovnic flf/(xi,. ..,xn) = Ci, i = 1,..., m : Označme H(Ai,..., Am, x^,..., xn) Hessovu matici Lagrangeovy funkce Z-(Ai,..., Am, xi,..., xn), pak pro její hodnotu v případném stacionárním bodě platí: 1. má - li determinant H(Ai,..., Am, Xi,..., xn) znaménko (-1 )n a všech n - m jejích největších hlavních minorů střídá znaménka, pak ve stacionárním bodě nastává maximum. 2. má - li všech n - m největších hlavních minorů včetně determinantu H(Ai,..., Am, xi,..., xn) znaménko (-1 )m, pak ve stacionárním bodě nastává minimum. 3. Je-li n - m největších hlavních minorů nenulových a přitom neplatí ani jedna z výše uvedených podmínek, pak ve stacionárním bodě není extrém. Lagrangeova funkce - postačující podmínky pro optimum, příklad Uvažujme modifikaci úlohy zákazníka restaurace, kdy je možné konzumovat ještě džus v ceně 1 dolar za 12 uncí, přitom novou funkci užitku vyjádříme jako U{S, V, J) = i/n(S) + \in{V) + \ln(J) a rozpočet zůstává $6. Lagrangeova funkce úlohy bude L{\, S, V, J) = l/n(S) + \in{V) + \ln(J) + A(f + f + ^ - 6). Z podmínek prvního řádu pro proměnné odvodíme S = 2V, J = 6V a po dosazení do rozpočtového omezení vyjde S* = 8, V* = 4 a J* = 24 uncí. Hessova matice /O 1 1 — \ / u 4 2 12 \ Lagrangeovy funkce je: H(A, S, \/, J) = i i 4 3S* 0 0 1 n __L_ n 2 u 3l/2 u V h o o -i / 12 w 3J2 Podmínka druhého řádu pro případ n = 3, /77 = 1 nabývá podoby: "je-li znaménko det(H) rovno (-1)3 a znaménko druhého hlavního minoru -(-1 )3, pak ve stacionárním bodě nastává maximum" Pro naši funkci je det(H) = -( 12961s2|/2 + z^j^ + 36^/2 )> což Je záporné v každém bodě a přitom determinant 2.hlavního minoru je + > což je kladné v každém bodě, takže ve stacionárním bodě nastává maximum. Lagrangeova funkce - postačující podmínky pro optimum, příklad Uvažujme další modifikaci, kdy kromě rozpočtového omezení uvažujeme ještě podmínku na celkový objem tekutin S + J = 24. Lagrangeova funkce úlohy bude /_(A,M, S, V,J) = l/A?(S) + l/A?(\/) + l/A?(J) + A(f + f+ ^-6)+/i(S+J-24). Z podmínek prvního řádu pro proměnné odvodíme V = 3(tf^s) a po dosazení do soustavy omezení vyjde S" Lagrangeovy funkce je: / 0 8, V" f a J* 16 uncí. Hessova matice H(A,M, S, V,J) 0 1 4 2 o 0 1 0 1 i 4 1 1 3S2 0 1 2 0 o \ 12 1 1 o 31/2 0 o o Podmínka druhého 3J2 7 řádu pro případ n = 3, /77 = 2 nabývá podoby: "je-li znaménko det(H) rovno (-1 )3 , pak ve stacionárním bodě nastává maximum a je-li jeho znaménko rovno (-1 )2, pak se jedná o minimum."Lze vypočítat, že pro naši funkci je det{H) = stacionárním bodě nastává maximum. (12W + i£j2 + 10^72)' c°ž Je záporné v každém bodě, takže ve Optimalizační úloha s omezením ve formě nerovností - motivační příklad Uvažujme jednoduchou optimalizační úlohu /(x, y) = x2 - 2x + 2y2 - y + 3 —>• min za podmínky x + y < 1. Můžeme problém převést na úlohu s omezením ve tvaru rovností? Přidáme na levou stranu omezující podmínky doplňkovou proměnnou: x + y + w2 = 1 a vytvoříme Lagrangeovu funkci Z_(x, y, m/, A) = x2 - 2x + y2 - 2y + 3 + A • (x + y + w2 - 1) Kromě podmínek 2x - 2 + A = 0, 2y-2 + A = 0ax + y+i/i/2-1 = 0 dostaneme derivováním podle w ještě 2wA = 0. Je zřejmé, že možnost A = 0 nedává žádné řešení, protože z prvních dvou rovnic dostaneme x = 1, y = 1 a pak třetí podmínka nemá řešení pro w. Musí tedy být w = 0, tedy x + y = 1, pak sečtením prvních dvou rovnic 2(x + y) - 4 + 2A = 0, takže A = 2-(x + y) = 1ax = y=1-| = f Rovnice 2w\ = 0 říká, že extrém leží buď na hranici (w = 0) nebo ve stacionárním bodě (A = 0). Kdybychom zvětšili omezující konstantu o ô, dostaneme x + y < 1 + ô. Je-li omezení aktivní (tj. w = 0), musí být ô < 1 a tedy zřejmě A = 2-(x + y) = 1 — ô >0. Shrňme podmínky pro obecnou úlohu. Optimalizační úloha s omezením ve formě nerovností Uvažujme úlohu na vázaný extrém /(x) —>• min , na množině M vymezené soustavou m nerovnic g,(x) < c,, / = 1,... m. Formálni postup je obdobný prípadu s omezujícími rovnostmi: vytvorí se opět Lagrangeova funkce Z_(x, A) = /(x) + Ylľ=i ^/ * (ff/OO _ c>) a sestaví se podmínky 1. řádu: V*/-(x, A) = 0, (stacionarita) flf/(x) < c,-, / = 1,... m (primární přípustnost) A/ > 0, / = 1,... m (duální přípustnost) A/ • (#/(x) - d) = 0, / = 1,... m (komplementarita) Tyto vztahy se nazývají Kuhn-Tuckerovy podmínky úlohy. Za určitých předpokladů regularity (nezávislost gradientů omezení) se jedná o nutné podmínky pro to, aby v bodě x* měla úloha lokální minimum. V tomto kontextu se též používá označení Karush-Kuhn-Tuckerovy podmínky, zkráceně KKT-podmínky. Optimalizační úloha s omezením ve formě nerovností Interpretace KKT podmínek vychází z ekonomického významu Lagrangeových multiplikátorů. ► Stacionarita a primární přípustnost jsou přirozené požadavky na optimalitu řešení úlohy s omezením. ► Z čeho plyne požadavek duální přípustnosti? Jestliže Lagrangeův multiplikátor A,- reprezentuje mezní užitek při uvolnění / - tého omezení, pak nerovnost A/ > 0 znamená, že optimální hodnota účelové funkce se nemůže uvolněním tohoto omezení zhoršit. ► Poslední požadavek komplementarity lze rozepsat jako: A/ = 0 nebo g,(x) = c, (případně mohou platit obě rovnosti) To znamená, že je-li příslušné omezení v bodě optima neaktivní (tj. není splněné jako rovnost), pak jeho multiplikátor musí být nulový, jinak by šla hodnota účelové funkce zlepšit uvolněním omezení. U aktivních omezení může být obecně i kladná hodnota multiplikátoru. Optimalizační úloha s omezením ve formě nerovností - príklad Najděte minimum funkce f (x, y) = x - \ + y2 na "pulelipse'Vymezené nerovnostmi ^- +y2 < f, y > 0. Výpočet provedeme zvlášť pro všechny kombinace (ne)nulovosti multiplikátorů A a /í: A = /í = 0, pak z podmínek stacionarity dostaneme x = 1, y = 0, účelová funkce zde má hodnotu /(1,0) = \. A = 0, /i > 0, pak opět stacionarita dává x = 1 a z podmínek komplementarity musí být y = 0. Dostali jsme opět bod [1,0]. A > 0, /i = 0, pak z podmínek stacionarity dostaneme 2y(1 + A) = 0, tedy buď y = 0 nebo A = -1, což nelze. Druhé souřadnice dopočítáme ze vztahu ?L- + 02 = |, získáme tedy body [-§,0], [|,0], hodnoty A jsou §, resp. \. Porovnáním hodnot ve všech podezřelých bodech /(150) = 1 /(-|,0) = ^f1, /(|,0) = | zjistíme, že minimum nastává v Optimalizační úloha s omezením ve formě nerovností - príklad Znázorněme si vrstevnice funkce f (x, y) = x - \ + y2 a prípustnou množinu vymezenou nerovnostmi |- + y2 < |, y > 0, minimum nastává v bodě [-|,0], maximum v bodě [|, 1]. Konvexní programování Úlohu /(x) —>• min na přípustné množině M vymezené soustavou m nerovnic Qi(x) < c/, / = 1,... m nazveme úlohou konvexního programování, jestliže účelová funkce /(x) i levé strany omezení c//(x), / = 1,..., m jsou konvexní funkce. Věta: Pro úlohu konvexního programování za předpokladu regularity platí: Vyhovuje-li bod x* KKT podmínkám, pak je bodem minima funkce /(x) na M. V případě konvexního programování je tedy splnění KKT vztahů postačující podmínkou pro existenci minima. Poznámka: Uvažujeme-li v dané úloze konvexního programování při vymezení přípustné množiny M také obligátní podmínky nezápornosti x > 0, pak lze KKT podmínky přeformulovat následovně: Funkce /(x) nabývá svého minima na M v bodě x* > 0 právě tehdy když existuje vektor A* > 0, takový že: Z_(x, A*) > Z_(x*, A*) > Z_(x*, A) pro všechny nezáporné vektory x, A. Toto tvrzení se nazývá Kuhn-Tuckerova věta o sedlovém bodě. Konvexní programování Poznámka: Vlastnosti sedlového bodu: Je-li (x*, A*) > 0 sedlovým bodem Lagrangeovy funkce na M, pak pro její gradienty zde platí: Vx/.(x*: ,A*) > 0 Vx/.(x*: ,A*).-x = 0 VA/-(x* ,A*) < 0 VA/-(x*,A*). A = 0, kde symbolem "."rozumíme násobení vektorů po složkách. Funkce Z_(x, A) nabývá na M v bodě (x*, A*) svého minima vzhledem k x a maxima vzhledem k A. První dvě podmínky jsou zřejmě zobecněním požadavku stacionarity (V*Z-(x*, A*) = 0) pro případ s obligátními podmínkami x > 0. Povšimněme si ještě, že VA/-(x*, A*) = (flf/(x) - C/)/=i,...,m, poslední dva vztahy vyjadřují tedy podmínky přípustnosti a komplementarity vzhledem k omezujícím podmínkám. Poznámka: Pro maximalizační úlohy se sestaví Lagrangeova funkce ve tvaru Z_(x, A) = /(x) - XX1 ' (9i(x) - °i) a v podmínkách pro sedlový bod se uvažují opačné nerovnosti. Konvexní programování - příklad Poznámka: Lineární problém cT x —>• max, A x < b, x > 0 je vlastně speciálním případem konvexního programování. Přepíšeme-li si účelovou funkci jako -cT • x min, budou podmínky pro sedlový bod (x, A) > 0 Lagrangeovy funkce následující: -cT + AT A > 0 (—cT + AT • A). • x = 0 A x - b < 0 (A-x-b).-A = 0 S těmito tvrzeními jsme se již setkali dříve, vyjadřují dualitu v úlohách LP. Optimální A je řešením tzv. duální úlohy bT • A min, AT A < c, A > 0, protože dosazením vztahu (-cT + AT • A) • x = 0 do Lagrangeovy funkce dostaneme tvar Z_(x, A) = -cT x + ATAx-ATb = -AT • b. Řešení primární i duální úlohy jsou totožná. Při velkém počtu omezení (m » rí) může být duální úloha mnohem jednodušší, proto se v praxi často při řešení primární úlohy používá tzv. duální algoritmus. Kvadratické programování Problém minimalizace funkce /(x) = |xT C x + d x na množině M={xGť, x > 0, A x < b} nazveme úlohou kvadratického programování. Jedná o úlohu konvexního programování? Prípustná množina M je jistě konvexní, stačí ověřit konvexitu účelové funkce. Hessova matice účelové funkce je H(x) = C, je-li tedy tato matice pozitivně definitní, jedná se o konvexní problém. Zapišme podmínky pro sedlový bod Lagrangeovy funkce: V*/-(x*, A*) = Cx + d + ATA>0 V*Z_(x*, A*), x = (C x + d + AT A), x = 0 VA/-(x*,A*) = A x-b<0 VA/-(x*, A*). • A = (A • x - b). • A = 0 Tato soustava se zpravidla upraví pomocí zavedení doplňkových proměnných w, kterými se první nerovnost převede na rovnici Cx + d + ATA-w = 0. Dále se úloha řeší jako lineární pomocí upravené simplexové metody, přičemž dodržení podmínky w. x = 0 se zajistí tak, že hlídáme, aby se do báze nedostaly proměnné x, a w-, nikdy současně (/ = 1,... a?). Na této myšlence je založena tzv. Wolfeho metoda řešení úloh kvadratického programování. Kvadratické programování, příklad: optimalizace portfolia Předpokládejme, že chceme sestavit portfolio z cenných papírů, jejichž výnosy jsou náhodné veličiny, které označíme X^,...,Xn. Tyto náhodné veličiny můžeme charakterizovat očekávaným výnosem E(Xí),..., E(Xn) a také variabilitou vyjádřenou rozptyly D(X^),..., D(Xn). Navíc mezi jednotlivými dvojicemi cenných papírů může existovat nějaký vztah, kdy se jejich ceny mohou vyvíjet souhlasně či naopak protichůdně - tyto závislosti jsou vyjádřeny pomocí kovariancí C(Xh Xj). Kovariance a rozptyly lze zapsat souhrnně pomocí variační matice V(X). Přístupem, založeným na těchto charakteristikách, se zabývá Markowitzův model portfolia. Výnos portfolia, ve kterém jsou jednotlivé cenné papíry zastoupeny v podílech p<\,...,pn\e náhodná veličina Y = XX1 PiX- Očekávaný výnos bude roven E(Y) = p,E(Xj). Variabilitu výnosu portfolia je možné vyjádřit pomocí jeho rozptylu, D(Y) = (p1?... ,pn) • V(X) • (pí,... ,Pn)T. Kvadratické programování, příklad: optimalizace portfolia Investor zpravidla požaduje co největší očekávaný výnos E(Y) za co nejmenšího rizika (riziko, tedy nejistotu můžeme vyjádřit právě rozptylem D{Y)) Jde o úlohu vícekriteriálního programování E(Y) ->> max, D(Y) ->> min za omezující podmínky P/ = 1 ■ Jeden z možných přístupů k řešení této vícekriteriální úlohy je stanovení minimálního požadovaného výnosu Rm-,n a minimalizace rizika mezi všemi portfolii s výnosem alespoň Rmin. Dostaneme úlohu kvadratického programování /(pípn) = (#,..., pn) • V(X) • (pí,..., pn)T min , za omezení p, > 0, XXi A = 1> XXi A^(^) > ^/n- Pro nedegenerovaná portfolia je matice V(X) pozitivně definitní, takže problém je konvexní. Příklad: Navrhněte strukturu portfolia z dvou cenných papírů Pí, P2, tak aby jeho očekávaný výnos byl alespoň 0,04 a riziko minimální. Sledováním časových řad cenového vývoje cenných papírů jsme odhadli očekávané výnosy E(X|) = 0,03, E{X2) = 0,05, rozptyly D(X,) = 3, D{X2) = 4 a kovarianci C(X^, X2) = 2. Kvadratické programování, příklad: optimalizace portfolia Zapíšeme matematický model úlohy: r(Pi,p2) = (Pi,A>) • ( g 4 ) ' ( p2 ) ^ ™n Za podmínky Pí, p2 > 0, 3pi + 5p2 > 4, pí + p2 < 1 . Poznámka: Očekávané výnosy jsme pro snadnější výpočty vynásobili 100 a poslední podmínku jsme zapsali jako nerovnici (připouštíme tedy i možnost nevyčerpání celé částky na investici!) Lagrangeova funkce úlohy má tvar /_(pi, p2, A, fi) = 3p2 + 4p!p2 + 4p| + A(pi + p2 - 1) + M-3pi - 5p2 + 4) Kuhn-Tuckerovy podmínky pro pí, p2, A, /i > 0 jsou: Lp, = 6pi + 4p2 + A - 3/i > 0, (6pi + 4p2 + A - 3/i)pi = 0 ^-p2 = 4pi + 8p2 + A - 5/i > 0, (4p! + 8p2 + A - 5/i)p2 = 0 /_'A=Pi+p2-1 <0, (pi+p2-1)A = 0 L' = -3pi - 5p2 + 4 < 0, (-3pi - 5p2 + 4)M = 0 Kvadratické programování, příklad: optimalizace portfolia Při hledání bodu vyhovujícího KT podmínkám uvažujme opět všechny možnosti (ne)nulovosti multiplikátorů A a /x: A = n = 0 : Z prvních dvou rovnic dostaneme (6pi + 4p2)pi = 0, (4p<\ + 8p2)p2 = 0, což má jediné nezáporné řešení pA = p2 = o, což však nevyhovuje podmínce 3pi + 5p2 > 4. A = 0, /i > 0 : Z komplementarity pro /i plyne 3pi + 5p2 = 4 (zřejmě tedy p1, p2 / 0) tedy, první dvě podmínky lze vydělit pí a p2: 6pi + 4p2 - 3/x = 0, 4^ + 8p2 - 5/i = 0, takže dostaneme lineární soustavu, jejímž řešením je Pí = 0,16, p2 = 0,7, /i = 1,25 a očekávaný výnos 4 při riziku 2,5. A > 0, /i = 0 : Z komplementarity pro A plyne pí + p2 = 1 (zřejmě tedy pu p2 / 0), první dvě podmínky lze vydělit pí a p2: 6pi + 4p2 + A = 0, 4p! + 8p2 + A = 0 a dostaneme soustavu, pro niž však vyjde A < 0, takže nezískáme žádné řešení. A > 0, /i > 0 : Komplementarita pro oba multiplikátory dává 3pi + 5p2 = 4, Pí + p2 = 1, což nám dá řešení = p2 = \, po dosazení do prvních dvou rovnic dostaneme 5 + A - 3/x = 0, 6 + A - 5/x = 0, tato soustava ale dává záporné A, takže nezískáme žádné řešení. Kvadratické programování, příklad: optimalizace portfolia Minimum pro naši úlohu nastalo v bodě pí = 0,16, p2 = 0,7, očekávaný výnos roven 4 a účelová funkce rizika nabývá v bodě optima hodnoty 2,5: Kvadratické programování, příklad: optimalizace portfolia Úlohu bychom mohli řešit i pro jiné aspirační úrovně výnosu Rm-,ni například Rmin £ {1; 1,5; 2; 2,5; 3; 3,5; 4; 5}. Vynesme si tyto hodnoty spolu s optimálními hodnotami účelové funkce (tj. minimálními riziky při daném výnosu) graficky v tzv. kriteriálním prostoru: rr 4 m i , f 3 >> i. ■i i í\ u c i : l : riziko i ' 4- Spojnice mezi body je odhadem tzv. efektivní hranice, tvořené portfolii, jejichž výnos lze zlepšit jen za cenu zhoršení rizika a naopak. Efektivní hranici také najít pomocí optimalizace funkcí /(/) = c • E (Y) - (1 - c) • D( V) na množině všech portfolií, kde konstanta c probíhá interval (0,1). Lineární lomené programování Dalším typem úloh, které lze převést na lineární problém, jsou úlohy lineárního lomeného programování optimalizovat funkci /(x) = d^'x^Qř° za C -X-|-Cq omezení x > 0, A x < b. Tyto úlohy sice nespadají do kategorie konvexních úloh, avšak umožňují pro cT • x + c0 > 0 zavedení substituce r = T "* . C -X-|-Cq Dostaneme účelovou funkci ve tvaru / = dT x r + dor, kterou můžeme vyjádřit jako funkci nových proměnných r, y, = x, • r, / = 1,..., n\ /(r, y\,... yn) = dT • y + d0r , podobně vyjádříme i omezení ^>0,y>0, A • y < b • r . Je však třeba přidat i další omezující podmínku 1 = r(cT • x + c0), tedy 1 = cT • y + c0r . Dostali jsme obyčejnou úlohu LP, kterou můžeme dále řešit například simplexovou metodou. Lineární lomené programování - příklad V ekonomii se setkáme s řadou ukazatelů poměrového typu. Jsou-li výrazy v čitateli a jmenovateli ukazatele lineárními funkcemi proměnných, podle kterých se snažíme ukazatel optimalizovat, jedná se o problém lineárního lomeného programování, viz úloha z knihy I. Gros: "Kvantitativní metody v manažerském rozhodování": Příklad: Uvažujme firmu, která má ve výrobním programu tři výrobky A, B, C s následujícími charakteristikami: Výrobek Variabilní náklady [Kč/t] Cena [Kč/t] A 11 000 12 000 B 15 000 18 000 C 14 000 16 000 fixní náklady 150 000 Kč Označíme-li si xi, x2, x3 množství prodaných výrobků, můžeme definovat například následující poměrové ukazatele: náklaHnvnQt tr7Ph v - 11 000*i +15QQQ^+14QQQ*3+150QQQ naKiaaovost irzeo z - —12000^+18000*2+16000*3—» rpntahilitu trřph 7 - A000x1 +3QQQ*2+2000*3-1 soooo reniaDiiuu irzeD z - ^000^+18000^+16000x3 ■ Lineární lomené programování - příklad Příklad: Minimalizujte nákladovost tržeb z uvedeného příkladu za podmínky, že celkové náklady nepřesáhnou 200 000 Kč. Matematický zápis úlohy: minimalizujte z = u^l7^ll7^l5° za podmínek 1 + 15x2 + 14x3 + 150 < 200, xi, x2, x3 > 0. Úlohu linearizujeme zavedením substituce r = 12xi+i8x2+i6x3» dostaneme tak problém minimalizovat funkci f(yuY2,y3,r) = 11/1 + 15y2 + 14y3 + 150r za omezení 11 y1 + 15y2 + 14y3 - 50r < 0, yi, y2, y3, r > 0 a doplňující podmínky 12y! + 18y2 + 16y3 = 1 Numerická optimalizace Řadu problémů není možné řešit analyticky (neznalost analytického vyjádření, mnoho proměnných, složité funkce - nelineární rovnice při určování stacionárních bodů) nebo by bylo analytické řešení příliš výpočetně náročné a tudíž neefektivní. Často nám stačí nalézt pouze přibližné řešení (v reálném světě stejně zaokrouhlujeme). Proto se v praxi používají metody iterační. Jejich charakteristikou je konstrukce posloupnosti bodů definičního oboru x°, x1, x2,..., které se blíží k optimálnímu řešení x*. Nasazení těchto metod pro vyhledání extrému je velice výhodné v kombinaci s výpočetní technikou. Existuje řada metod, a to jak pro funkce jedné proměnné, tak pro více proměnných. Zřejmě nejznámější jsou pro funkce jedné proměnné: ► metoda bisekce intervalu metoda zlatého řezu ► metoda kvadratické interpolace ► Newtonova metoda ► metoda Regula falši Jednorozměrná optimalizace - komparativní metody Nejprve se zaměřme na metody jednorozměrné numerické optimalizace , ty jsou totiž součástí některých vícerozměrných metod. Metody nevyžadující výpočet derivace funkce / nazýváme komparativní. Uvedeme tři z nich, a to trisekci, metodu zlatého řezu a metodu kvadratické interpolace. Většinou je třeba předem přibližně určit polohu bodu optima a stanovit počáteční interval / = (a, b) tak, aby na změněném intervalu účelová funkce / měla jen jedno minimum, tj. byla unimodální. V jednotlivých iteracích nahrazujeme krajní body intervalu obsahujícího minimum novými body, tak abychom jej postupně zužovali. Jako odhad bodu optima se vezme střed posledního intervalu ln = (an, bn) . U všech iteračních metod musíme předem nastavit nějaké pravidlo ukončení výpočtu. Metody většinou vyžadují splnění jistých podmínek, za kterých platí, že čím více iteračních kroků provedeme, tím přesnější odhad hledaného extrému získáme. Možné přístupy, kdy výpočet ukončit jsou například: ► po provedení zadaného počtu kroků ► dosažením stanovené přesnosti e (tedy když šířka intervalu ln splňuje: lib" - an\ < 2e) Jednorozměrná optimalizace - metoda trisekce Jako úvodní motivaci ukážeme intervalovou trisekci . fm I \ / = 1 = = y^> ; a = a" u v = b" b Minimum jistě leží vlevo od v, takže b nahradíme pomocí £>1 = v, levá hranice zůstává a1 = a. Tím se délka intervalu (obsahujícího minimum) zkrátí na dvě třetiny své původní délky. Dále pokračujeme s intervalem ŕ = (a1, Ď1), atd. Bod u však už nelze v následujícím kroku využít. Funkci musíme vyhodnotit v každém kroku dvakrát, což je neefektivní. Jednorozměrná optimalizace - metoda zlatého řezu Metoda zlatého řezu je založena na šikovnějším výběru dělicích bodů u a v. Označme p číslo o něco větší než 1 /3, jehož přesnou hodnotu teprve určíme. Označme body u = a + pd a v = b - pd. Předpokládejme opět, že f(u) < f(v), minimum je tedy mezi a a v. Nahradíme b pomocí v a proces opakujeme. Zvolíme-li správnou hodnotu p, bod u bude v pozici použitelné i v příštím kroku. Po prvním kroku se tak funkce / bude vyhodnocovat pokaždé už jen jednou. Jak tedy zvolit p? Tak, aby bod u hrál v redukovaném intervalu (a, v) stejnou roli jako bod v v původním intervalu, tj. aby poměr délky intervalu (a, u) k délce intervalu (a, v) byl stejný jako poměr délky intervalu (a, v) k délce intervalu (a, b), tj. p : (1 - p) = (1 - p) : 1. Po úpravě tohoto vztahu obdržíme kvadratickou rovnici p2 - 3p + 1 =0, jejímž řešením je p = 3-=^> ~ 0,382 , kde číslo 1 - p « 0,618 je tzv. poměr zlatého řezu. a u v pd (1-p)d d b Jednorozměrná optimalizace - metoda zlatého řezu, příklad Lze ukázat, že požadujeme-li při metodě zlatého řezu ukončení při dosažení stanovené přesnosti e, stačí provést N iterací, kde A/> **<^> Výsledný odhad bodu optima zapíšeme ve tvaru x* = bN+aN ± e Příklad: Nalezněte minimum funkce f(x) = x + ^ s přesností e = 0,05, víte-li, že se nalézá v intervalu (0,5; 3). Spočteme nejprve, kolik bude třeba provést iterací: n > ^gg, = ^Sk «6> 69>stačí tedy7 iterací- Jednorozměrná optimalizace - metoda zlatého řezu, příklad 7. krok: u= 1.819660, v= 1.852549, f (u) = 2.725686, f (v) = 2.726691. Nový interval je ľ = (1.766445,1.852549). Šířka intervalu je menší než 0,1, tedy odhadneme bod optima jeho středem: x* = 1,81 ± 0,05 Jednorozměrná optimalizace - metoda kvadratické interpolace Předpokládejme, že minimum leží v intervalu (a, b), a že je znám nějaký jeho vnitřní bod c, ve kterém hodnota funkce / nepřesáhne hodnoty /(a), f{b). \ ím / V^/f(c) 1 1 \ f(x)/ 1 J 1 1 1 1 1 a x c b Dá se ukázat, že x = ^ ^K£,-^žglgíÍ5%-^^> ■ Další P°stuP se volí podle hodnoty f{x). Jednorozměrná optimalizace - metoda kvadratické interpolace Víme, že x e (a, b), vyšlo nám x < c. Je-li f (x) < f (c), do další iterace použijeme vypočtené x místo bodu c, který se stane novým krajním bodem (pokud x < c, tak jím nahradíme horní hranici b, viz obr., v opačném prípade dolní hranici a). Je-li naopak f (x) > f (c), pak c ponecháme a novým krajovým bodem se stane x. Případ x -- -- c znamená, že buď jsme se strefili do optima nebo je nutná jiná volba c. Tento a další nedostatky překonává kombinovaný přístup, tzv. Brentova metoda. t f(b) r. f(x) f(c) H-h H-h a=a' x = c" c=b" b Výpočet se zastaví, až rozdíl dvou po sobě jdoucích odhadů \xn - xn 1 klesne pod hodnotu e. Jednorozměrná optimalizace - metoda kvadratické interpolace, příklad Příklad: Minimalizujte funkci f{x) = x + ^ na intervalu (0,5; 3) s přesností e = 0,05, jako první aproximaci volte x° = 1,5. První interpolaci provedeme pro body a = 0,5, c = 1,5 a b = 3. Znázorněme červeně graf /(x) na (a, £>) a modře parabolu, protínající jej v bodech a, £>, c: 1. krok: f (a) = 12.500000, f(c) = 2.833333, f(b) = 3.333333 x = 2.208333, f{x) = 2.823499 Nově: a = 1.500000, c = 2.208333, b = 3.000000, chyba |x1 - x°| = 0.708333. Jednorozměrná optimalizace - metody využívající derivace Kromě standartního předpokladu unimodálnosti funkce / na intervalu (a, b) předpokládejme dále, že / je zde diferencovatelná. Nejjednodušší iterační optimalizační metodou využívající derivaci funkce / je metoda bisekce, čili půlení intervalů. Jestliže označíme bod, v němž funkce / nabývá svého minima na intervalu (a, b) jako p, pak je / klesající na (a,p) (tudíž zde platí ť(x) < 0) a rostoucí na intervalu (p, b) (tudíž zde platí f (x) > 0). Vezmeme-li jako odhad bodu minima střed intervalu s = ^ , pak pro /'(s) < 0 leží minimum vpravo, klademe tedy a1 = s a pro /'(s) > 0 leží minimum vlevo a klademe £>1 = s, druhý krajní bod zůstává (pokud f(s) = 0, našli jsme přímo bod optima x*). Výpočet se zastaví po stanoveném počtu kroků nebo klesne-li šířka intervalu pod 2e, kde e je požadovaná přesnost. Lze ukázat, že pak stačí provést N > '^S1 iterací. Jednorozměrná optimalizace - metoda bisekce, příklad Ukažme si metodu opět pro minimalizaci funkce f(x) = x+ \ na počátečním intervalu (0,5; 3) s přesností e = 0,05. Funkce má derivaci ť(x) = 1-4. 2 ■ 0.5 1 1.5 2 2.5 3 5. krok: s = 1.828125, f'(s) = 0.017950 nový interval bude: /1 = (1.750000,1.828125). protože šířka intervalu < e, výpočet končí: x* ^ 1.789063 ±0,05 Jednorozměrná optimalizace - metody využívající derivace Další metoda hledá minimum jako kořen derivace. Nazývá se Newtonova metoda (též metoda tečen). Metoda využívá navíc i druhé derivace, předpokládejme tedy její existenci v každém bodě zadaného intervalu. Jak název napovídá, vedeme v bodě x0 tečnu ke grafu funkce ť(x) a jako následující odhad vezmeme průsečík této tečny s osou x. Rovnici tečny lze zapsat jako: y = f'(x0) + f"(x0) • (x - x0) . Položíme-li pravou stranu rovnu nule, spočteme odtud x = x0 - Tuto hodnotu označíme x^ a pokračujeme ve výpočtu až dokud není splněno | < e. Předností metody je její rychlost, značnou nevýhodou je ale fakt, že nekonverguje vždy. Ke konvergenci postačuje, aby na výchozím intervalu (a, b) neměnila f"{x) ani ť"(x) znaménko a aby platilo ť(á) • ť(b) < 0. Důležité je též dobrá volba bodu x0, doporučuje se volit tak, aby f'(x0) • f'"(x0) > 0 , jinak by xi neležel v intervalu (a, b). Jednorozměrná optimalizace - Newtonova metoda Geometrická interpretace je naznačena na obrázku, kde vidíme funkci ť{x) a počáteční iteraci x0, poté jsou provedeny tři další iterace. Jednorozměrná optimalizace, Newtonova metoda, příklad Příklad: Nalezněte minimum funkce f(x) = x + \ s přesností e = 0,05, víte-li, že se nalézá v intervalu (0,5; 3). Řešení: /'(*) = 1 /"(x) = lf. Zvolme x0 = 1.750000 (1. aproximace z metody bisekce) 1 .krok: x0 = 1,750000, /' (x0) = -0,119534, /"(x0) = -1,919200 Xi= 1,812283, |xi - x0| = 0,062283 2.krok: Xi = 1,812283, ť(xi) = -0,008029, /"(x1) = 1,668662 x2 = 1,817095, |x2-xi| = 0,004812, výpočet končí: x* « 1,817095±0,05 Jednorozměrná optimalizace - metody využívající derivace V předchozí metodě potřebujeme v každém kroku spočítat jak první, tak druhou derivaci funkce v daném bodě. Jelikož výpočet derivace funkce nemusí být vždy snadný, nahrazuje se tzv. poměrnou diferencí: ť{Xk) Ä !^m=ú My tuto aproximaci provedeme pro druhou derivaci: n*)«ľ(V^ŕ Nahradíme-li v iteračním vzorci Newtonovy metody druhou derivaci uvedenou aproximací, dostávame: xk^ = xk + f>(xl)-Xf>[xk_,)f'(xk) Právě uvedený vzorec reprezentuje tzv. metodu sečen. K výpočtu jsou třeba dva počáteční body x0lx<[. Tato metoda také není vždy konvergentní, lze ji však modifikovat tak, že do vzorce použijeme místo dvou po sobě jdoucích iterací body xm, xk s co největšími indexy, tak, aby platilo ť(xm) • ť{xk) < 0. Tuto modifikaci nazýváme metoda regula falši. Jednorozměrná optimalizace - metoda regula falši Zázorněme si metodu graficky, bod optima je x* a počáteční iterace jsou x0, xí, provedeme ještě další tři: Jednorozměrná optimalizace - metoda regula falši, příklad Příklad: Nalezněte minimum funkce f(x) = x + \ s přesností e = 0,05, víte-li, že se nalézá v intervalu (0,5; 3). Řešení: Pro nalezení prvních dvou iterací můžeme použít např. metodu bisekce. Tedy: x0 = 1,750000, x^ = 2,375000. Ověříme, že /'(xo)/'(xi) = -0,119534 • 0,552121 < 0. 1. krok:x2 = * + ľ^yrw/i^) = 1,861230, |x2 =0,062283 Protože //(x2) = 0,069426 > 0, použijeme dále x0 a x2. 2. krok: x3 = x2 + //(x*p°(XQ/(x2) = 1,820363, |x3 - x2| = 0,040867, výpočet končí: x* « 1,820363 ± 0,05. Vícerozměrná numerická optimalizace -přehled Numerické metody bez omezení ► Komparativní metody ► Gradientní metody ► Newtonova metoda a její modifikace ► Gaussova-Newtonova metoda ► Metody konjugovaných směrů ► Metoda konjugovaných gradientů ► Kvazi-newtonovské metody ► Simulované žíhání, genetické algoritmy, tabu search, atd. Numerické metody s omezením ► Metody přípustných směrů ► Metody aktivních množin ► Metoda projekce gradientu ► Metoda redukovaného gradientu ► Metody pokutových a bariérových funkcí ► Metody vnitřního bodu ► Sekvenční kvadratické programování Vícerozměrná optimalizace - Komparativní metody Metoda cyklické záměny proměnných převádí vícerozměrnou optimalizaci na posloupnost jednorozměrných optimalizačních úloh ve směru jednotlivých souřadnic: z výchozího bodu provádíme minimalizaci ve směru první souřadnice. Po nalezení lokálního extrému funkce /(x) ve směru s, = (1,0,..., 0) , pokračujeme ve směru druhé souřadnice s2 = (0,1,..., 0) atd., až dostaneme první iteraci. Nevýhodou metody je pomalý výpočet, navíc není ani zaručena konvergence metody. -1 -0.5 0 0.5 1 1.5 2 Metoda cyklické záměny proměnných - příklad Řešme následující úlohu z knihy V. Pánková, Nelineární optimalizace pro ekonomy: Hledejte minimum funkce /(xi,x2) = -12x2 + 4x2 + 4x2 + 4xix2 pomocí metody cyklické záměny proměnných. Proveďte první dvě iterace z bodu x° = (1,1 )T . Řešení: Při postupu ve směru první proměnné optimalizujeme funkci /(xí , 1) = -12 + 4x2 + 4 + Ax\, dostaneme x\ = - \. Následně ve směru druhé proměnné minimalizujeme /(-|,x2) = -12x2 + 1 +4x| - 2x2, dostaneme x2 = |. Dále postupujeme z bodu x1 = (-1, \)T ve směru první proměnné: minimalizujeme /(xl5 \) = -21 + 4x2 + ^ + 7x1? dostaneme x^ = - |. Poté ve směru druhé proměnné: funkce /(-|,x2) = -12x2 + ^ + 4x| - |x2 nabývá minima pro x2 = f^. Dostali jsme odhad x2 = (-|, jl)T , skutečné minimum nastává v bodě x* = (-1,2)T. Vícerozměrná optimalizace - Komparativní metody Metoda pravidelného a flexibilního simplexu: Startuje vytvořením výchozího simplexu v zadaném prostoru (Simplexem v n - rozměrném prostoru rozumíme konvexní obal n + 1 vrcholů v obecné poloze, tj. v rovině je to trojúhelník, v třírozměrném prostoru je to čtyřstěn atd.). Z vrcholů nahradíme ten s nejhorší hodnotou účelové funkce pomocí reflexe vzhledem k těžišti ostatních vrcholů novým vrcholem, čímž vznikne nový simplex, tj. další iterace. Metoda je heuristická, ale názorná a snadno implementovatelná. Rychlost a přesnost nalezení optimálního bodu záleží na velikosti simplexu. Čím větší je simplex, tím se rychleji blížíme k optimu. Přesnost výpočtu naopak vyžaduje malou velikost simplexu. Proto je při výpočtu třeba měnit délku hrany simplexu. V Nelder-Meadově metodě se toto zajistí pomocí operací expanze, kontrakce a redukce základního simplexu. Vícerozměrná optimalizace - metoda pravidelného simplexu Pro volbu pevné velikosti simplexu dosáhneme pouze omezené přesnosti. Vícerozměrná optimalizace - gradientní metody K nejstarším a zároveň nejpoužívanějším přístupům vícerozměrné numerické optimalizace patří gradientově metody. Ukažme si obecný princip gradientově metody pro minimalizaci diferencovatelné funkce /(x) pro xeť1: 1. urči výchozí bod x° 2. urči gradient funkce / v tomto bodě: V/(x°) 3. přejdi z bodu x° do bodu x1 ve směru "antigradientu" -V/(x°) tak, aby /(x°) > /(x1). 4. celý postup opakuj z bodu x1, atd. dokud není splněno pravidlo ukončení výpočtu Výpočet je možné ukončit: ► po provedení předem stanoveného počtu iterací ► pokud hodnota účelové funkce klesne o méně než předem stanovené e, tedy /(x'')-/(x/+1) (a) = /(x1 - a • Vf(x1)) = /(-6a; 1,5) = -9 - 36a + 144a2, minimum opět nastává pro a = 0,125. Tedy x2 = x1 - 0,125 • V/(x1) = (-0,75; 1,5)T . Dále bychom minimalizovali funkci g3(a) = /(x2 - a • V/(x2)) = /(-0,75; 1,5 + 0,375a), atd. Vícerozměrná optimalizace - newtonovské metody Podobně jako v jednorozměrném případě v newtonovských metodách funkci /(x) aproximujeme při přechodu z bodu xk kvadratickou funkcí, tedy Taylorovým polynomem T2(x) = /(xk) + V/(xk)T . (x - xk) + l(x - xk)T • H(xk) • (x - xk) a zapíšeme podmínku pro stacionární bod VT2(x) = 0, neboli V/(xk)T + H(xk) • (x - xk) = 0. Další iteraci xk+i dostaneme jako řešení této soustavy. xk+i = xk - H(xk)"1 • V/(xk) Pokud startujeme daleko od minima, je kvadratická aproximace nepřesná a Hessova matice může být singulární nebo negativně definitní. Newtonova metoda pak nefunguje nebo vede k maximu. Proto se používají modifikace Newtonovy metody, například Levenberg - Marquardtova metoda nebo trust region algoritmus. Newtonovské metody - příklad Hledejte minimum funkce /(xi,x2) =-12x2+ 4xf+ 4x2+ 4xix2 pomocí Newtonovy metody . Proveďte první iteraci z bodu x° = (0,0)T . Řešení: Již známe gradient V/(xi,x2) = (8x1 +4x^-12 + 4^ + 8x2)T. Spočteme Hessovu matici: H = ^ ^ ^ ^, její inverze je 2 -1 H-i — 12 12 — -1 2 12 12 Tedy můžeme spočítat první iteraci x1 = x° - H-1 • W(x°) = ( °n)-( % ° )=(-1,2)T 0 / \ =± fž I \ -12 Nalezli jsme přesně bod optima. Vícerozměrná optimalizace - kvazi-newtonovské metody a Gauss-Newtonova metoda Kvazi-newtonovské metody jsou gradientní metody, které leží někde mezi metodou nejrychlejšího spádu a Newtonovou metodou a snaží se využít předností obou metod. Gradientní metody mají zaručenou konvergenci a Newtonova metoda v okolí optima konverguje rychle. Newtonova metoda ale vyžaduje výpočet Hessovy matice, respektive její inverze. Aproximujeme-li tyto matice na základě dat z jednotlivých kroků iteračního algoritmu, dostaneme metodu Broydena, Fletchera, Goldfarba a Shannoa (BFGS) nebo metodu Davidona, Fletchera a Powella (DFP). Gaussova-Newtonova metoda řeší problém minimalizace kritéria ve tvaru nejmenších čtverců nelineární funkce. Na závěr ještě podotkněme, že metody obecně nejsou globálně konvergentní, doporučuje se tedy optimalizaci spustit vícekrát z různých počátečních bodů. Stále jsou vyvíjeny nové algoritmy, z modernějších metod můžeme zmínit simulované žíhání, genetické algoritmy, tabu search, atd. Vícerozměrná optimalizace - metoda sdružených směrů Metody sdružených (konjugovaných) směrů byly vyvinuty proto, aby urychlily konvergenci gradientních metod a vyhnuly se potížím spojeným s modifikací Newtonovy metody. Nejprve uveďme definici: Definice: Vektory Si,..., sp jsou konjugované vzhledem k symetrické matici Q tehdy, když platí • Q • sy= 0, V1 < i J < p, / / j Pokud funkci /(x) optimalizujeme postupně ve směrech Si,..., sp konjugovaných vzhledem k Hessově matici H, pro kvadratické funkce máme zajištěnu konvergenci pro p = n . Pro nekvadratické funkce je nutné metodu nejpozději po a?+ 1 krocích nastartovat znovu. Metoda bohužel není konstruktivní, neříká, jak sdružené směry určit. V případě, že se směry generují z gradientů a dosavadního směru pohybu, dostaneme modifikaci známou jako metoda sdružených gradientů. Další modifikací je metoda paralelních tečen, PARTAN. Metoda sdružených směrů - příklad Hledejte minimum funkce /(xi,x2) =-12x2+ 4x2+ 4x2+ 4xix2 pomocí metody konjugovaných směrů. Proveďte první dvě iterace z bodu x° = (1,1 )T a jako výchozí směr vezměte si = (1,0). ( 8 4 \ -r Řešení: Hessova matice je H = í 4 J . Směr s2 = (a, b) je sdružený s Si vzhledem k matici H pokud Si • H • s2 = 8a + 4b = 0. To je splněno například pro a = 1, b = -2. Začneme minimalizaci z x° ve směru Si: Q\ (a) = /(1 + a, 1) = 12a + 4a2, což je minimální pro a = -§, takže x1 = (-|, 1)T. Pokračujeme minimalizací z x1 ve směru S2: g2(a) = /(-| + a, 1 - 2a) = 9 + 12a + 12a2, což je minimální pro a = — \, takže x2 = (-1,2)T . Nalezli jsme přesně optimum funkce. Základní pojmy teorie her Teorie her se zabývá řešením matematických modelů konfliktních situací. Používá se názvosloví, jehož přehled je uveden v následující tabulce, (viz skripta Jan Štecha: Optimální rozhodování a řízení): Reálná rozhodovací Matematický model Teorie optimálního situace této situace - hra řízení rozhodovací situace hra v normálním tvaru optimalizační problém účastník hráč řídící veličina (proměnná) rozhodnutí strategie hodnoty řídících veličin množina rozhodnutí prostor strategií množina přípustných hodnot důsledky rozhodnutí výplatní funkce kritérium jakosti (účelová fce) důsledek výhra hodnota kritéria Hra v normálním tvaru je definována množinou {Q,X|,...,Xn, Ji(xi,...,xn),..., Jn(xi,...,xn)} kde Q = {1,2,..., a?} jsou hráči, množiny X\ až Xn jsou množiny strategií hráčů 1 až a? a J,(xi,..., xn) je výplatní funkce hráče /. Pokud jsou prostory strategií konečné množiny, řekneme, že je hra konečná. Typy rozhodování za nejistoty ► Racionální (inteligentní) rozhodovatel: jeho rozhodování je uvědomělé , využívající všech objektivně dostupných informací ► Neracionální (neinteligentní, indiferentní) rozhodovatel: lhostejný k důsledkům rozhodování; např. působení prostředí (svět, příroda); Inteligentní hráč může volit následující přístupy: ► Laplaceův princip navrhuje zvolit takovou strategii, která by byla optimální v případe, že by pravděpodobnosti, s nimiž nastanou různé stavy světa, byly shodné ► Maximinní (pesimistické ) kritérium - navrhuje pro jednotlivé strategie stanovit nejnižší hodnoty užitku a zvolit takovou strategii, pro kterou je toto minimum maximální. ► Maximaxní (optimistické ) kritérium - navrhuje pro jednotlivé možné strategie stanovit nejvyšší hodnoty užitku a zvolit takovou strategii, pro kterou je toto maximum maximální. Určtete majitelovy strategie při různých typech rozhodování. ► Hurwitzovo kritérium je konvexní kombinací optimistického a pesimistického kritéria. Vhodnou volbou parametru (tzv. ukazatale optimismu) lze nastavit vhodný kompromis mezi oběma krajnostmi Antagonistický konflikt Hru nazveme hrou s konstantním součtem jestliže při jakékoliv strategií hráčů je součet výher roven nějaké konstantě K. Platí tedy Y;UM*u...,xn) = K,VxieXi Pro K = 0 mluvíme o hře s nulovým součtem. Budeme se dále zabývat antagonistickým konfliktem dvou účastníků. Matematickým modelem tohoto antagonistického konfliktu bude hra dvou hráčů v normálním tvaru s konstantním součtem Q = {{1,2}; U, V; (u, v), J2(u, v)}, strategii prvního hráče místo x^ budeme dále značit u a strategii druhého hráče místo x2 písmenem v. Také stačí uvádět pouze jednu výplatní funkci J(u, v) = (u, v), protože pro druhou výplatní funkci platí J2(u, v) = K - (u, v), pro nulový součet přímo J2(u, v) = - Ji (u, v). Tedy J(u, v) vyjadřuje výhru prvního a zároveň ztrátu druhého hráče. První hráč se tedy bude snažit tuto funkci maximalizovat (je-li inteligentní) a druhý minimalizovat. Rovnovážné strategie (ď, v*) jednotlivých hráčů pak definujeme jako strategie vyhovující nerovnostem J(u, i/*) < J{ď, v*) < J{ď, v),Mu e U, v e V, tedy bod (a*, v*) je sedlový bod výplatní funkce. Maticové hry Konečný antagonistický konflikt dvou hráčů popisujeme maticovou hrou. V ní je počet strategií obou hráčů konečný, píšeme U = {1,..., m}, V = {1,..., a?}. Hodnoty výplatní funkce můžeme zapsat jako matici hry A = První hráč vybírá řádek / v matici hry a druhý hráč vybírá sloupec y v matici hry. První hráč chce maximalizovat (je-li inteligentní) a druhý hráč minimalizovat prvek a,y v matici hry. V teorii her veličinu c = max, min^a,;) nazveme dolní cena hry. Je to zaručená výhra prvního hráče. Naopak veličina c = miny max/(a,y) , tzv. horní cena hry vyjadřuje zaručenou výhru druhého hráče. Označení horní a dolní cena plyne z toho, že obecně platí c < č . Pokud je nerovnost splněna jako rovnost, nazýváme příslušnou hodnotu c = c = č cenou hry. Zřejmě, existuje-li rovnovážný bod (/*,y*), pak c = a-,*j* Maticové hry - příklad Příklad: Uvažujme maticovou hru s nulovým součtem a výherní matici / 2 3 4 \ A = 3 4 4 . Určete strategie prvního hráče podle různých principů. V 2 1 6 / Určete cenu horní a dolní cenu hry a rozhodněte, zda existuje rovnovážný bod. Řešení: Podle Laplaceova principu volíme řádek s největším průměrem (resp. součtem) prvků, tedy druhý řádek. Podle principu Maximaxu volíme třetí řádek, kde se nalézá největší prvek matice. Podle principu Minimaxu volíme druhý řádek, kde je největší řádkové minimum. Toto kritérium použijeme, je-li protihráč inteligentní. Dolní cena hry je c = max, miny(a,y) = max(2,3,1) = 3, horní cena hry je c = miny max/(a,y) = min(3,4,6) = 3. Cena hry je tedy c = 3 . Obou optim bylo dosaženo pro /* = 2, y* = 1 , rovnovážný bod je tedy (2,1). Maticové hry - příklad Příklad: Pro hru s výherní maticí A = ^ y ^ ^ určete cenu horní a dolní cenu hry a rozhodněte, zda existuje rovnovážný bod. Řešení: V této hře dolní cena hry c = max, miny(a,y) = 7 není rovna horní ceně hry c = miny max/(a,y) = 9, hra nemá sedlový bod a tedy nemá řešení na množině pevných strategií (nazývaných též ryzí strategie). Hráči nyní mají důvod svá rozhodnutí tajit, neboť dozví-li se hráč o rozhodnutí protivníka, může z této informace získat pro sebe výhodu. Protože ryzí rovnovážný bod neexistuje, zavádí se pojem smíšené strategie. Maticové hry - smíšené strategie Smíšenou strategií rozumíme náhodný výběr strategie hráče, přičemž je dáno rozdělení pravděpodobnosti na prostoru ryzích strategií: hodnoty pravděpodobnostní funkce pro prvního hráče označíme P = (Pi,P2,... ,pm) , pro druhého hráče q = (qt, q2l..., qn) .(Složky těchto vektorů jsou nezáporná čísla, jejichž součet je roven jedné.) Výplata hráčů je tedy náhodná veličina a pokud volí hráči strategie nezávisle na sobě, pro její střední hodnotu platí: E(p, q) = XX1 au • A • Q/ = p • A • qT. Poznámka: Ryzí strategie je vlastně zvláštním případem smíšené strategie, kdy první hráč vybírá konkrétní řádek s pravděpodobností 1. O smíšeném rozšíření maticových her platí základní věta teorie maticových her, Nashova věta: Každá maticová hra má řešení ve smíšených strategiích. Maticové hry - smíšené strategie, příklad Příklad: Pro hru s výherní maticí A = ^ y ^ ^ najděte řešení ve smíšených strategiích. Řešení: Zapišme si očekávanou výhru prvního hráče (současně se jedná o ztrátu druhého): V = E(p,q) = 1 ij^qn + 5pig2 + 7p2g1 + 9p2g2. Určíme podmínky pro stacionární (sedlový) bod Lagrangeovy funkce, přidáme- li k funkci V omezující podmínky pí + p2 - 1 =0, + q2 - 1 =0 vynásobené multiplikátory A,/x: 4i = 11 ch + 5q2 - A = 0 = 7qi + 9g2 - - A = 0 4, = 11pi +7p2 - /i = 0 = 5pi + 9p2 - - /i = 0 = Q1 + q2 - 1 = 0 L'x = Pí + P2 - 1 = 0 Tato soustava má řešení p! = 0,25, p2 = 0,75 a gi = 0,5, g2 = 0,5. (všechny hodnoty vyšly nezáporné, i když jsme podmínky nezápornosti do úlohy nezahrnuli). Hodnota výhry je pak V = 8. Maticové hry - smíšené strategie, príklad Úlohu lze řešit také graficky. Z pohledu prvního hráče můžeme jeho výhru při různých strategiích (pí, 1 - pí) znázornit dvěma lineárními funkcemi , V*2 (pro různé volby druhého hráče). První hráč si může zajistit výhru V<\ = n]\n(v^, V*2) Tato hodnota bude největší pro pí = 0,25, tedy v bodě průsečíku obou funkcí, pro něj je Ví = 8. p^O.25 1 Z pohledu druhého hráče můžeme jeho ztrátu při různých strategiích (<7i, 1 - <7i) znázornit dvěma lineárními funkcemi Vu, V2* (pro různé volby Maticové hry - řešení pomocí lineárního programování Bez újmy na obecnosti dále předpokládejme, že všechny prvky matice A jsou kladné (to lze zajistit přičtením vhodné konstanty ke všem prvkům) Jak určíme cenu hry c pro hru s maticí A? První hráč si chce pro jakoukoliv volbu druhého hráče zajistit výhru alespoň c: p • A > (c, c..., c). Tyto nerovnice můžeme vydělit c (dle předpokladů je větší než nula) a přepsat po substituci ti■■ = ^, / = 1,..., m jako: t • A > (1,1,. ..,1). První hráč se snaží tuto svoji minimální výhru maximalizovat: c —>• max, což můžeme přepsat jako XX1 ť m,n > neboť z podmínky JXi A = 1 dostáváme po vydělené c podmínku XX1 í; = l- Dostali jsme tedy úlohu lineárního programování pro proměnné U,...,tm, cenu hry získáme jako převrácenou hodnotu optima účelové funkce. Maticové hry - řešení pomocí lineárního programování Podobně druhý hráč chce zajistit, aby jeho ztráta nepřesáhla c při žádné volbě prvního hráče. Tedy požaduje: A • qT < (c, c..., c). Po vydělení hodnotou c a zavedení substituce Sj■ = ^, j = 1,..., n opět dostaneme úlohu LP v proměnných Si,.. .sn'. X]y=i sj max za omezení A • sT < (1,1,..., 1). neboť druhý hráč se snaží c minimalizovat, tedy \ maximalizovat. Obě úlohy jsou vzájemně duální. Literatura ► Fletcher, Roger: Practical methods of optimization, 1st ed., Chichester: John Wiley and Sons, 1987. ► Šubrt, Tomáš a kol.: Ekonomicko-matematické metody, Plzeň : Vydavatelství a nakladatelství Aleš Čeněk, 2011 ► Pánková, Václava: Nelineární optimalizace pro ekonomy,1. vyd., Praha : Professional Publishing, 2003 ► Intriligator, Michael D.: Mathematical optimization and economic theory,Philadelphia : Siam, 2002 ► Jablonský, Josef, Petr Fiala, Miroslav Maňas: Vícekriteriální rozhodování,1. vyd.,Praha : Vysoká škola ekonomická v Praze, 1994. ► Klapka, Jindřich, Jiří Dvořák, Pavel Popela Metody operačního výzkumu, Vyd. 2., Brno : VUTIUM, 2001 ► Klein, Michael W.: Mathematical methods for economics, 2nd ed., Boston : Addison-Wesley, c2002 ► JABLONSKÝ, Josef: Operační výzkum kvantitativní modely pro ekonomické rozhodování, 1. vyd. Praha: Professional Publishing, 2002 ► PLEVNÝ, Miroslav a Miroslav ŽIŽKA: Modelování a optimalizace v manažerském rozhodování, Vyd. 2. Plzeň: Západočeská univerzita, 2010 ► GROS, Ivan: Kvantitativní metody v manažerském rozhodování, 1. vyd. Praha: Grada, 2003 ► Jana Friebelová - Jana Klicnarová: Rozhodovací modely pro ekonomy, 1. vyd. České Budějovice: Jihočeská univerzita v Českých Budějovicích, 9nn7