Úloha lineárního programování Úvod do problematiky lineárního programování ilustrujme 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ů Ki, K2a K3v 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 x\ 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 = 20000*! + 14000x2 za podmínek 0,5x-\ + 0,25x2 < 40 0,5x! + 0,5x2 < 60 0,25x2 < 25 Xi, x2 > o Formulace úlohy optimalizace výrobního programu Označíme - li x\ 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 = 20000*! + 14000x2 za podmínek 0,5*1 + 0,25x2 <40 0,5*1 + 0,5x2 < 60 0,25x2 <25 *1, 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)T je vektor cenových koeficientů v účelové funkci, b = (40,60,25)T je vektor kapacitních Matematická formulace obecné úlohy lineárního programování (LP) Obecnou úlohu LP pro n proměnných a m omezení můžeme zapsat takto minimalizuj (maximalizuj) funkci * = E7=1 CjXj za podmínek YľM agy? bi, / = 1,...a77 Xj > 0, j = 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é Matematická formulace obecné úlohy lineárního programování (LP) Obecnou úlohu LP pro n proměnných a m omezení můžeme zapsat takto: minimalizuj (maximalizuj) funkci * = Ey=i CjXj za podmínek YľM agy? bi, / = 1,...a77 Xj > 0, j = 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, obvykle se uvádí v tzv. základním tvaru. Snadno lze převést úlohu minimalizační na úlohu maximalizace funkce -z = Y^=a (-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. 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ě. 0)5x1+0,25x2<40 Kvůli nezápornosti proměnných se omezíme pouze na první kvadrant. Znázorníme zde polorovinu tvořenou body splňujícími první omezující podmínku. 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ě. 0,5x1+0,5x2<60 Znázorníme také polorovinu tvořenou body splňujícími druhou omezující podmínku. 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ě. 0,25x2<25 Znázorníme ještě polorovinu tvořenou body splňujícími třetí omezující podmínku. 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ě. a1 Množina přípustných řešení M je tvořena body, které vyhovují všem omezením. 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ě. Izokvanta účelové funkce z = 20000^ + 14000x2 = 0 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 Izokvanta účelové funkce z = 20000xi + 14000x2 = 350000 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ě. Izokvanta účelové funkce z = 20000xi + 14000x2 = 700000 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ě. z= 1050000 Izokvanta účelové funkce z = 20000xi + 14000x2 = 1050000 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ě. z= 1920000 Izokvanta účelové funkce z = 20000xi + 14000x2 = 1920000 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ě. Nejvyšší izokvanta se dotýká množiny M v bodě x * 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ě. 40 80 Xl Bod x* = [40,80] je optimálním řešením. Simplexová metoda Postup hledání optima je založen na tom, že díky tvaru vrstevnic může ležet extrém pouze na kraji přípustné množiny. Přípustná množina je také díky linearitě omezení speciálního tvaru (jde o konvexní mnohostěn), čehož využívá speciální algoritmus řešení úloh LP Simplexová metoda je iterační postup k nalezení optimálního řešení úlohy LP Úvodním krokem je nalezení výchozího základního řešení. 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. Simplexová metoda Postup hledání optima je založen na tom, že díky tvaru vrstevnic může ležet extrém pouze na kraji přípustné množiny. Přípustná množina je také díky linearitě omezení speciálního tvaru (jde o konvexní mnohostěn), čehož využívá speciální algoritmus řešení úloh LP. Simplexová metoda je iterační postup k nalezení optimálního řešení úlohy LP. Úvodním krokem je nalezení výchozího základního řešení. 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. Množina přípustných řešení Simplexová metoda Postup hledání optima je založen na tom, že díky tvaru vrstevnic může ležet extrém pouze na kraji přípustné množiny. Přípustná množina je také díky linearitě omezení speciálního tvaru (jde o konvexní mnohostěn), čehož využívá speciální algoritmus řešení úloh LP. Simplexová metoda je iterační postup k nalezení optimálního řešení úlohy LP. Úvodním krokem je nalezení výchozího základního řešení. 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. výchozí bod Výchozí základní řešení Simplexová metoda Postup hledání optima je založen na tom, že díky tvaru vrstevnic může ležet extrém pouze na kraji přípustné množiny. Přípustná množina je také díky linearitě omezení speciálního tvaru (jde o konvexní mnohostěn), čehož využívá speciální algoritmus řešení úloh LP. Simplexová metoda je iterační postup k nalezení optimálního řešení úlohy LP. Úvodním krokem je nalezení výchozího základního řešení. 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. výchozí bod Přesuneme se do sousedního vrcholu s lepší hodnotou účelové funkce Simplexová metoda Postup hledání optima je založen na tom, že díky tvaru vrstevnic může ležet extrém pouze na kraji přípustné množiny. Přípustná množina je také díky linearitě omezení speciálního tvaru (jde o konvexní mnohostěn), čehož využívá speciální algoritmus řešení úloh LP. Simplexová metoda je iterační postup k nalezení optimálního řešení úlohy LP. Úvodním krokem je nalezení výchozího základního řešení. 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. výchozí bod Přesuneme se do sousedního vrcholu s ještě lepší hodnotou účelové funkce Simplexová metoda Postup hledání optima je založen na tom, že díky tvaru vrstevnic může ležet extrém pouze na kraji přípustné množiny. Přípustná množina je také díky linearitě omezení speciálního tvaru (jde o konvexní mnohostěn), čehož využívá speciální algoritmus řešení úloh LP. Simplexová metoda je iterační postup k nalezení optimálního řešení úlohy LP. Úvodním krokem je nalezení výchozího základního řešení. 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. výchozí bod Zase se přesuneme do sousedního vrcholu s lepší hodnotou účelové funkce Simplexová metoda Postup hledání optima je založen na tom, že díky tvaru vrstevnic může ležet extrém pouze na kraji přípustné množiny. Přípustná množina je také díky linearitě omezení speciálního tvaru (jde o konvexní mnohostěn), čehož využívá speciální algoritmus řešení úloh LP. Simplexová metoda je iterační postup k nalezení optimálního řešení úlohy LP. Úvodním krokem je nalezení výchozího základního řešení. 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 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 Wj (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? 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 Wj (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/Vi + 6O1/1/2 + 251/1/3 za omezení, že se nevyplatí vyrábět ani směs Mocca ani Standard, tedy, že platí nerovnosti 0,51/1/1 + 0,5w2 > 20, 0,5i/i/i +0,25w2 + 0,5w3 > 14. 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 Wj (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/Vi + 6O1/1/2 + 251/1/3 za omezení, že se nevyplatí vyrábět ani směs Mocca ani Standard, tedy, že platí nerovnosti 0,51/1/1 + 0,5w2 > 20, 0,51/1/1 + 0,251/1/2 + 0,51/1/3 > 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 gr(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 ^ primární duální ^ omezení typu < ^ omezení typu > ^ omezení typu rovnice nezáporná proměnná ^ nekladná proměnná ^ proměnná neomezená ^ Minimalizační úloha duální primární nezáporná proměnná nekladná proměnná proměnná neomezená omezení typu > omezení typu < omezení typu rovnice Poznámka : 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 Wj. 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 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í! 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. 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í. Ú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 Í7i (x) < (resp. =, resp. >)0 Sk (x) < (resp. =, resp. >)0 gm(x) < (resp. =, resp. >)0, kde alespoň jedna z funkcí ŕ, gy,..., gn je nelineárni, nazveme úlohou nelineárního programování (NLP). □ s Ú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 01 (x) < (resp. =, resp. >)0 92(x) < (resp. =, resp. >)0 ■ gm(x) < (resp. =, resp. >)0, kde alespoň jedna z funkcí f, ,..., 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 f limitován na nějakou podmnožinu X c Rn, hovoříme o vázaných extrémech. Ú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 01 (x) < (resp. =, resp. >)0 92(x) < (resp. =, resp. >)0 ■ gm(x) < (resp. =, resp. >)0, kde alespoň jedna z funkcí f, ,..., gn je nelineárni, 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 f 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! Připomenutí - Lagrangeovy multiplikátory 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í Vg, lineárně nezávislé vektory (tj. žádné omezení není nadbytečné), pak pro bod optima x* existují jednoznačné hodnoty X^1 ..., A™, takové, že: Vf(x*) + £,=i A/ • Vft-(x*) = 0. Čísla X^1 ..., A™ se nazývají Lagrangeovy multiplikátory a umožňují převedení optimalizační úlohy na řešení systému rovnic. Pripomenutí - Lagrangeovy multiplikátory 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í Vg, lineárně nezávislé vektory (tj. žádné omezení není nadbytečné), pak pro bod optima x* existují jednoznačné hodnoty X^1 ..., A™, takové, že: Vr(x*) + £,=i A/ • Vft-(x*) = 0. Čísla X^1 ..., A™ 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/ • 0(x) a sestaví se podmínky pro její stacionární body, tzv. podmínky 1. řádu: Vx/.(x,A) = 0, VA/-(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 f i M konvexní, pak je bod x* globálním minimem funkce f na množině M. 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 S a V 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 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 S a V 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) = ^ + !*p. Řešení: Zavedeme Lagrangeovu funkci L{S, V, A) = ^ + ^P- - A(f + f - 6). Podmínky prvního řádu jsou: LS(S, V,\) = £;-$ = 0 LV(S, V,X) = 2T7-! = o LX(S, V,X) = f + |-6 = 0 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 S a V 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) = ^ + !*p. Řešení: Zavedeme Lagrangeovu funkci L{S, V, A) = ^ + ^P- - A(f + f - 6). Podmínky prvního řádu jsou: LS(S, V,\) = £;-$ = 0 LV(S, V,X) = 2T7-! = o LX(S, V,X) = f + |-6 = 0 Z prvních dvou rovnic lze vyjádřit, že A = | = y, neboli S = 2V. Spolu s poslední podmínkou dostaneme řešení S* = 12, V* = 6 uncí, A* = g, což dává užitek 1/(12,6) = 2,14. Ekonomická interpretace Znázorněme si uvažovanou úlohu graficky, si 24 12 6 12 V Sklon rozpočtové linie je dán vztahem dán poměrem cen Ekonomická interpretace Znázorněme si uvažovanou úlohu graficky, si 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): = Ekonomická interpretace Znázorněme si uvažovanou úlohu graficky, st 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): = Spočteme mezní užitky US(S, V) = ^ UV(S, V) = ^7, jejich podíl je = | Protože v bodě optima (S*, \/*) je sklon rozpočtové linie a indiferenční křivky shodný, platí: -2 = neboli ^ = ^ (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 \. Získaný užitek bude 1/(14,7) = 2,29. Přírůstek užitku je tedy AU = (7(14,7) - (7(12,6) = 2,29 - 2,14 = 0,15 = (i) • 1. Zřejmě jeden dodatečný dolar vyvolal (^)-násobný přírůstek užitku, což je něco mezi 1 a 1. Můžeme říct, že optimální hodnota Lagrangeova multiplikátoru vyjadřuje mezní užitek peněz určených k útratě. 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 \. Získaný užitek bude 1/(14,7) = 2,29. Přírůstek užitku je tedy AU = (7(14,7) - (7(12,6) = 2,29 - 2,14 = 0,15 = (i) • 1. Zřejmě jeden dodatečný dolar vyvolal (^)-násobný přírůstek užitku, což je něco mezi 1 a 1. 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í 6: S* = 26, l/* = 6aA* = ^. Optimální užitek při rozpočtu 6 je po úpravě: f(B) = (7(26,6) = \ln{2) + ln(B). Derivováním podle 6 získáme jeho mezní užitek ť(B) = ^ což je rovno A*. 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 \. Získaný užitek bude 1/(14,7) = 2,29. Přírůstek užitku je tedy AU = (7(14,7) - (7(12,6) = 2,29 - 2,14 = 0,15 = (i) • 1. Zřejmě jeden dodatečný dolar vyvolal (^)-násobný přírůstek užitku, což je něco mezi 1 a 1. 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í 6: S* = 26, l/* = 6aA* = ^. Optimální užitek při rozpočtu 6 je po úpravě: f(B) = (7(26,6) = \ln{2) + ln(B). Derivováním podle 6 získáme jeho mezní užitek ť{B) = 1, 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 a b \ ( x Q(x, y) = (x, y) . Předpokládejme, že hledáme optimum b c i \ y této funkce na množině dané lineární rovnicí Ax + By = 0. 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 = - a dosadíme-li do Q, dostaneme = Q(x, = ax2 + 2bx(-*x) + c(-|x)2 = -^[2bAB - aB2 - cA2]. Výraz uvnitř hranaté závorky lze také zapsat jako determinant matice / 0 A B \ H = \ A a b \, což je vlastně Hessova matice Lagrangeovy funkce \ B b c J /.(A, x, y) = \(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 f(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(gr(x,y) - c) + f{x,y). Pak je-li ve stacionárním bodě determinant det(H(\,x,y)) • kladný, je stacionární bod bodem maxima • záporný, je stacionární bod bodem minima Lagrangeova funkce - postačující podmínky pro optimum Zobecníme-li odvození z předchozího slajdu pro funkci dvou proměnných f(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(gr(x,y) - c) + f{x,y). Pak je-li ve stacionárním bodě determinant cfer(/-/(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 /.(A, S, V) = ^ + ^ + A(f + | - 6) Hessovu matici /OJ \ \ H=\ \ ~2^2 0 . Její determinant je deř(H(A,S, \/)) = + což je kladné číslo pro jakékoliv S, V, 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 f(x\ ,...,xn) optimalizovanou na množině dané soustavou rovnic Označme H(\i,..., Xm, ,..., xn) Hessovu matici Lagrangeovy funkce L(\i,..., Am,xi,..., xn), pak pro její hodnotu v případném stacionárním bodě platí: O má - li determinant H(\i,..., Xm, x^,..., 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. O má - li všech n - m největších hlavních minorů včetně determinantu H(\i,..., Xm, x^,..., xn) znaménko (-1 )m, pak ve stacionárním bodě nastává minimum. O 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//7(S) + \ln(V) + \ln(J) a rozpočet zůstává $6. 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//7(S) + \ln(V) + \ln(J) a rozpočet zůstává $6. Lagrangeova funkce úlohy bude /_(A, S, V,J) = 1//7(S) + \ln{V) + 1/a?(J) + A(f + | + ^ - 6). Z podmínek prvního řádu pro proměnné odvodíme S = 21/, J = 6\/apo dosazení do rozpočtového omezení vyjde S* = 8, V* = 4 a J* = 24 uncí. 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//7(S) + \ln{V) + \ln{J) a rozpočet zůstává $6. Lagrangeova funkce úlohy bude L{\ S, V,J) = 1//7(S) + \ln{V) + 1/a?(J) + A(f + f + ^ - 6). Z podmínek prvního řádu pro proměnné odvodíme S = 21/, J = 6\/apo dosazení do rozpočtového omezení vyjde S* = 8, V* = 4 a J* = 24 uncí. Hessova matice Lagrangeovy funkce je: /-/(A, S, 1/, J) = 1 -3^ 0 0 1 n __í- o 2 u 3v2 u 1 n n 1 V 15 0 0 'ú ) Podmínka druhého řádu pro případ n = 3, m = 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) = -(i29ěW + 144J2V2 + 36§2j*)' 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 - 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, S, V, J) = l/n(S) + \ln( V) + J) + A(f +1 + ^ - 6) + + J- 24). Z podmínek prvního řádu pro proměnné odvodíme V = 3^S) a po dosazení do soustavy omezení vyjde S* = 8, 1/* = ^ a J* = 16 uncí. 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/n(S) + \ln{ V) + J) + A(f +1 + ^ - 6) + + J - 24). Z podmínek prvního řádu pro proměnné odvodíme V = 3^S) a po dosazení do soustavy omezení vyjde S* = 8, 1/* = ^ a J* = 16 uncí. Hessova matice / 0 0 1 1 — \ / w w 4 2 12 \ 0 0 1 0 1 Lagrangeovy funkce je: /-/(A, /i, S, 1/, J) = ^ 1 -^ 0 0 1 0 0 -gl* 0 V ^ i o o y Podmínka druhého řádu pro případ n = 3, m = 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) = -(+ ih* + irôb* )■ co^ Je sporné v každém bodě, takže ve stacionárním bodě nastává maximum. Optimalizační úloha s omezením ve formě nerovností -motivační příklad Uvažujme jednoduchou optimalizační úlohu f (x, y) = x2 - 2x + y2 - 2y + 3 min za podmínky x + y < 1. Můžeme problém převést na úlohu s omezením ve tvaru rovností? Optimalizační úloha s omezením ve formě nerovností -motivační příklad Uvažujme jednoduchou optimalizační úlohu f (x, y) = x2 - 2x + y2 - 2y + 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 pomocnou proměnnou: Optimalizační úloha s omezením ve formě nerovností -motivační příklad Uvažujme jednoduchou optimalizační úlohu f (x, y) = x2 - 2x + y2 - 2y + 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 pomocnou proměnnou: x + y + w2 = 1 a vytvoříme Lagrangeovu funkci L(x, y, iv, A) = x2 - 2x + y2 - 2y + 3 + A • (x + y + w2 - 1) Optimalizační úloha s omezením ve formě nerovností -motivační příklad Uvažujme jednoduchou optimalizační úlohu f (x, y) = x2 - 2x + y2 - 2y + 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 pomocnou proměnnou: x + y + w2 = 1 a vytvoříme Lagrangeovu funkci L(x, y, iv, A) = x2 - 2x + y2 - 2y + 3 + A • (x + y + w2 - 1)_ Kromě podmínek 2x-2 + A = 0, 2y-2 + A = 0ax + y+w2-1 = 0 dostaneme derivováním podle w ještě 2wA = 0. Optimalizační úloha s omezením ve formě nerovností -motivační příklad Uvažujme jednoduchou optimalizační úlohu f (x, y) = x2 - 2x + y2 - 2y + 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 pomocnou proměnnou: x + y + w2 = 1 a vytvoříme Lagrangeovu funkci L(x, y, w, A) = x2 - 2x + y2 - 2y + 3 + A • (x + y + w2 - 1)_ Kromě podmínek 2x 2 + A = 0. 2y-2 + A = 0ax + y+w2-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) = 1 ax = y = 1 - | = |. Optimalizační úloha s omezením ve formě nerovností -motivační příklad Uvažujme jednoduchou optimalizační úlohu f (x, y) = x2 - 2x + y2 - 2y + 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 pomocnou proměnnou: x + y + w2 = 1 a vytvoříme Lagrangeovu funkci L(x, y, w, A) = x2 - 2x + y2 - 2y + 3 + A • (x + y + w2 - 1)_ Kromě podmínek 2x 2 + A = 0. 2y-2 + A = 0ax + y+w2-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) = 1 ax = y = 1 - | = |- Podmínka komplementarity 2wA = 0 říká, že extrém leží buď na hranici (w = 0) nebo ve stacionárním bodě (A = 0). Pokud nás omezení nepustí do stac. bodu, musí být A nezáporná. Skutečně, i kdybychom zvětšili omezující konstantu o nějaké ô < 1, dostaneme x + y < 1 + ô. Je-li toto omezení aktivní, musí být A = 2-(1+5) = 1- r5a tedy zřejmě A > 0. Shrňme podmínky qk> obecnoiáo Optimalizační úloha s omezením ve formě nerovností Uvažujme úlohu na vázaný extrém f (x) min , na množině M vymezené soustavou m nerovnic g,(x) < c,, i = 1,... m. Formálni postup je obdobný případu s omezujícími rovnostmi: vytvoří se opět Lagrangeova funkce /.(x, A) = f(x) + YlT=\ ^/ ■ (flí/(x) - c/) a sestaví se podmínky 1. řádu: Optimalizační úloha s omezením ve formě nerovností Uvažujme úlohu na vázaný extrém f (x) min , na množině M vymezené soustavou m nerovnic g,(x) < c,, i = 1,... m. Formálni postup je obdobný případu s omezujícími rovnostmi: vytvoří se opět Lagrangeova funkce /.(x, A) = f(x) + YlT=\ ^/ ■ (ff/W _ ci) a sestaví se podmínky 1. řádu: Vx/_(x, A) = 0, (stacionarita) Optimalizační úloha s omezením ve formě nerovností Uvažujme úlohu na vázaný extrém f (x) min , na množině M vymezené soustavou m nerovnic g,(x) < c,, i = 1,... m. Formálni postup je obdobný případu s omezujícími rovnostmi: vytvoří se opět Lagrangeova funkce /.(x, A) = f(x) + YlT=\ A, • (gf/(x) - C/) a sestaví se podmínky 1. řádu: Vx/_(x, A) = 0, (stacionarita) gf/(x) < C/, / = 19... in (primární přípustnost) Optimalizační úloha s omezením ve formě nerovností Uvažujme úlohu na vázaný extrém f (x) min , na množině M vymezené soustavou m nerovnic g,(x) < c,, i = 1,... m. Formálni postup je obdobný případu s omezujícími rovnostmi: vytvoří se opět Lagrangeova funkce /.(x, A) = f(x) + YlT=\ ^/ ■ (flí/(x) - c/) a sestaví se podmínky 1. řádu: Vx/_(x, A) = 0, (stacionarita) gf/(x) < C/, / = 19... in (primární přípustnost) A, > 0, / = 1,... #77 (duální přípustnost) Optimalizační úloha s omezením ve formě nerovností Uvažujme úlohu na vázaný extrém f (x) min , na množině M vymezené soustavou m nerovnic g,(x) < c,, i = 1,... m. Formálni postup je obdobný případu s omezujícími rovnostmi: vytvoří se opět Lagrangeova funkce /.(x, A) = f(x) + YlT=\ ^/ ■ (flí/(x) - c/) a sestaví se podmínky 1. řádu: Vx/_(x, A) = 0, (stacionarita) gf/(x) < C/, / = 19... in (primární přípustnost) A, > 0, / = 1,... #77 (duální přípustnost) A, • (gf/(x) - Cj) = 0, / = 1,... #77 (komplementarita) Optimalizační úloha s omezením ve formě nerovností Uvažujme úlohu na vázaný extrém f (x) min , na množině M vymezené soustavou m nerovnic g,(x) < c,, i = 1,... m. Formálni postup je obdobný případu s omezujícími rovnostmi: vytvoří se opět Lagrangeova funkce /.(x, A) = f(x) + YlT=\ ^/ ■ (í7/(x) - c/) a sestaví se podmínky 1. řádu: Vx/-(x, A) = 0, (stacionarita) gf/(x) < C/, / = 19... in (primární přípustnost) A, > 0, / = 1,... #77 (duální přípustnost) A, • (gf/(x) - Cj) = 0, / = 1,... #77 (komplementarita) Tyto vztahy se nazývají Ku h n-Tu cke rovy 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-pod minky. 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. 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. 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í -příklad Najděte minimum funkce f(x,y) = x - \ + y2 na "pulelipse'Vymezené nerovnostmi \ +y2 < |, y > 0. Optimalizační úloha s omezením ve formě nerovností -příklad Najděte minimum funkce f(x,y) = x - \ + y2 na "půlelipse"vymezené nerovnostmi \ +y2 < |, y > 0. Řešení: druhé omezení přepíšeme do tvaru -y < 0 a vytvoříme Lagrangeovu funkci /_ = x- ^+y2 + A(^+y2-§) + /n(-y) Optimalizační úloha s omezením ve formě nerovností -příklad Najděte minimum funkce f(x,y) = x - ^ + y2 na "půlelipse"vymezené nerovnostmi \ + y2 < |, y > 0. Řešení: druhé omezení přepíšeme do tvaru -y < 0 a vytvoříme Lagrangeovu funkci /_ = x- ^+y2 + A(^+y2-§) + n(-y) Zapišme KKT podmínky pro minimum: Ux = 1 - x + Xx = 0, /.^ = 2y + 2Ay - (stacionarita) |-+y2<|, y>0 (primární přípustnost) A > 0, ii > 0 (duální přípustnost) A(^+y2-|) =03//y = 0 (komplementarita) Optimalizační úloha s omezením ve formě nerovností -příklad Najděte minimum funkce f(x,y) = x - ^ + y2 na "půlelipse"vymezené nerovnostmi \ + y2 < |, y > 0. Řešení: druhé omezení přepíšeme do tvaru -y < 0 a vytvoříme Lagrangeovu funkci /_ = x- ^+y2 + a(^+y2-§) + /i(-y) Zapišme KKT podmínky pro minimum: Ux = 1 - x + Xx = 0, /.^ = 2y + 2Ay - (stacionarita) |-+y2<|, y>0 (primární přípustnost) a > 0, ii > 0 (duální přípustnost) a (t + y2 ~ i) = 03 = 0 (komplementarita) Výpočet provedeme zvlášť pro všechny kombinace (ne)nulovosti multiplikátorů a a ii\ X = ii = 0, pak z podmínek stacionarity dostaneme x = 1, y = 0, účelová funkce zde má hodnotu f(1,0) = \. Optimalizační úloha s omezením ve formě nerovností -příklad Najděte minimum funkce f(x,y) = x - ^ + y2 na "půlelipse"vymezené nerovnostmi \ + y2 < |, y > 0. Řešení: druhé omezení přepíšeme do tvaru -y < 0 a vytvoříme Lagrangeovu funkci /_ = x- ^+y2 + A(^+y2-§)+ /i(-y) Zapišme KKT podmínky pro minimum: Ux = 1 - x + Xx = 0, Uy = 2y + 2Ay - n (stacionarita) |-+y2<|, y>0 (primární přípustnost) A > 0, ii > 0 (duální přípustnost) ^ (t + y2 ~ i) = 03 = 0 (komplementarita) Výpočet provedeme zvlášť pro všechny kombinace (ne)nulovosti multiplikátorů A a n\ A = 0, ii > 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]. Optimalizační úloha s omezením ve formě nerovností -příklad Najděte minimum funkce f(x,y) = x - ^ + y2 na "půlelipse"vymezené nerovnostmi \ + y2 < |, y > 0. Řešení: druhé omezení přepíšeme do tvaru -y < 0 a vytvoříme Lagrangeovu funkci /_ = x- ^+y2 + A(^+y2-§)+ /i(-y) Zapišme KKT podmínky pro minimum: Ux = 1 - x + Xx = 0, Uy = 2y + 2Ay - n (stacionarita) |-+y2<|, y>0 (primární přípustnost) A > 0, ii > 0 (duální přípustnost) ^ (t + y2 ~ §) = 03 = 0 (komplementarita) Výpočet provedeme zvlášť pro všechny kombinace (ne)nulovosti multiplikátorů A a ii\ A > 0, ii = 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 y + O2 = §, získáme tedy body [-§, 0], [§, 0], hodnoty A jsou §, resp. ^. Optimalizační úloha s omezením ve formě nerovností -příklad Najděte minimum funkce f(x,y) = x - ^ + y2 na "půlelipse"vymezené nerovnostmi \ + y2 < |, y > 0. Řešení: druhé omezení přepíšeme do tvaru -y < 0 a vytvoříme Lagrangeovu funkci /_ = x- ^+y2 + A(^+y2-§) + /i(-y) Zapišme KKT podmínky pro minimum: Ux = 1 - x + Xx = 0, /.^ = 2y + 2Ay - (stacionarita) |-+y2<|, y>0 (primární přípustnost) A > 0, ii > 0 (duální přípustnost) ^ (t + y2 ~ i) = 03 = 0 (komplementarita) Výpočet provedeme zvlášť pro všechny kombinace (ne)nulovosti multiplikátorů A a ii\ A > 0, ii > 0 nedává žádný nový bod, protože kvůli komplementaritě je y = 0 a současně + y2 = |, což se shoduje s předchozím případem. Optimalizační úloha s omezením ve formě nerovností -příklad Najděte minimum funkce f(x,y) = x - ^ + y2 na "půlelipse"vymezené nerovnostmi \ + y2 < |, y > 0. Řešení: druhé omezení přepíšeme do tvaru -y < 0 a vytvoříme Lagrangeovu funkci /_ = x- ^+y2 + a(^+y2-§)+ n(-y) Zapišme KKT podmínky pro minimum: Ux = 1 - x + Xx = 0, Uy = 2y + 2Ay - n (stacionarita) |-+y2<|, y>0 (primární přípustnost) a > 0, ii > 0 (duální přípustnost) ^ (t + y2 ~ §) = 03 = 0 (komplementarita) Výpočet provedeme zvlášť pro všechny kombinace (ne)nulovosti multiplikátorů a a n\ Porovnáním hodnot ve všech podezřelých bodech f(1,0) = \, /(-§, 0) = ^f1, 0) = | zjistíme, že minimum nastává v bodě Optimalizační úloha s omezením ve formě nerovností -příklad Znázorněme si vrstevnice funkce f(x,y) = x - ^- +y2 a přípustnou množinu vymezenou nerovnostmi ^- + y2 < |, y > 0, minimum nastává v bodě [-§,0], maximum v bodě [\, 1]. Konvexní programování Úlohu f (x) -> min na přípustné množině M vymezené soustavou m nerovnic gr,-(x) < C/, / = 1,... m nazveme úlohou konvexního programování, jestliže účelová funkce f (x) i levé strany omezení g,(x), / = 1,..., m jsou konvexní funkce. Konvexní programování Úlohu f(x) min na přípustné množině M vymezené soustavou m nerovnic gf/(x) < C/, / = 19... in nazveme úlohou konvexního programování, jestliže účelová funkce ř(x) i levé strany omezení g,(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. Konvexní programování Úlohu f (x) min na prípustné množině M vymezené soustavou m nerovnic gf/(x) < c,, / = 19... in nazveme úlohou konvexního programování, jestliže účelová funkce f (x) i levé strany omezení g,(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 f(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 f(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í: VxL(x*,A*) > 0 VxL(x*,A*).-x = = 0 VA/-(x*,A*) < 0 VA/-(x*,A*). ■ X-- = o, kde symbolem "."rozumíme násobení vektorů po složkách. 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 (Vx/_(x*, A*) = 0) pro případ s obligátními podmínkami x > 0. 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 (Vx/_(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/)/=i5...5 poslední dva vztahy vyjadřují tedy podmínky přípustnosti a komplementarity vzhledem k omezujícím podmínkám. 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 (Vx/_(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,...jm 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 /_(x, A) = f(x) - YllĹ\ \ ' (9i(x) - °i) a v podmínkách pro sedlový bod se uvažují opačné nerovnosti. Konvexní programování - prí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 Konvexní programování - prí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 + AT-A-x-AT-b = -AT • b. Konvexní programování - prí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+AAx-Ab= -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 f (x) = \xT C x + d x na množině M = {x e Rn, x > 0, A x < b} nazveme úlohou kvadratického programování. □ s Kvadratické programování Problém minimalizace funkce f (x) = |xT C x + d x na množině M = {xg1", x > 0, A x < b} nazveme úlohou kvadratického programování. Jedná o úlohu konvexního programování? Pří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. □ s Kvadratické programování Problém minimalizace funkce f (x) = |xT C x + d x na množině M = {xg1", x > 0, A x < b} nazveme úlohou kvadratického programování. Jedná o úlohu konvexního programování? Pří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: Vx/-(x*, A*) = Cx + d + ATA>0 Vx/-(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 Kvadratické programování Problém minimalizace funkce f (x) = \xT C x + d x na množině M = {xg1", x > 0, A x < b} nazveme úlohou kvadratického programování. Jedná o úlohu konvexního programování? Pří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: Vx/-(x*, A*) = Cx + d + ATA>0 Vx/-(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-iv = 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(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(XhXj). 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. 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(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(XhXj). 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 je náhodná veličina Y = Píxí- Očekávaný výnos bude roven E(Y) = Y!í=\ PíE(Xj). Variabilitu výnosu portfolia je možné vyjádřit pomocí jeho rozptylu, D( V) = (Pí,..., Pn) • V(X) • (pí,..., p„)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 ^"=1 p,■ = 1 . 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 ^"=1 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 Rmjn a minimalizace rizika mezi všemi portfolii s výnosem alespoň Ftmin. Dostaneme úlohu kvadratického programování /(Pí,... ,p„) = (p,... ,p„) ■ V(X) • (A ,...,pn)T -> m/n , za omezení A > 0, Hl A = 1, Eľ=1 PiE(Xi) > Ftmin. Pro nedegenerovaná portfolia je matice V(X) pozitivně definitní, takže problém je konvexní. 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 ^"=1 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 Rmjn a minimalizace rizika mezi všemi portfolii s výnosem alespoň Ftmin. Dostaneme úlohu kvadratického programování /(Pí,... ,p„) = (p,... ,p„) ■ V(X) • (A ,...,pn)T -> m/n , za omezení A > 0, Hl A = 1, Eľ=1 PiE(Xi) > Ftmin. 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ů , 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 £(X|) = 0,03, E(X2) = 0,05, rozptyly D(X|) = 3, D{X2) = 4 a kovarianci C(X15X2) = 2. Kvadratické programování, příklad: optimalizace portfolia Zapíšeme matematický model úlohy: r(Pi,A>) = (Pí,02) • ( 2 4 ) ' ( p2 ) ^ m//7 za P°dmí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!) Kvadratické programování, příklad: optimalizace portfolia Zapíšeme matematický model úlohy: r(Pi,A>) = (Pí,02) • ( 2 4 ) ' ( p2 ) ^ m//7 za P°dmí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 /.(Pí, p2, A, p) = 3pf + 4p!p2 + 4p| + A(pi + P2 - 1) + M-3pi - 5p2 + 4) Kvadratické programování, příklad: optimalizace portfolia Zapíšeme matematický model úlohy: f{fh,P2) = (Pi,P2) • ( 2 4 ) ' ( ^ ) ^ m,n za P°dmínky Pí, P2 > 0, 3p! + 5p> > 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 /.(P!,P2, A, n) = 3pf + 4p!P2 + 4pf + A(p! + P2 - 1) + M-3P1 - 5p2 + 4) Kuhn-Tuckerovy podmínky pro pí, P2, A, /i > 0 jsou: Ľpy = 6pi + 4p2 + A - 3/i > 0, (6p! + 4p2 + A - 3m)Pi = 0 l'p2 = 4Pi + 8p2 + A - 5/í > 0, (4pi + 8p2 + A - 5/i)p2 = 0 Í-'a = Pí +P2-1 <0, (pí +P2-1)A = 0 L' = -3p! - 5p2 + 4 < 0, (-3p! - 5p2 + 4)yu = 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 /i\ A > 0, ii > 0 : Komplementarita pro oba multiplikátory dává 3p^ + 5p2 = 4, Pí + P2 = 1, což nám dá řešení p^ = p2 = \, po dosazení do prvních dvou rovnic dostaneme 5 + A - 3/i = 0, 6 + A - 5/i = 0, tato soustava ale dává záporné A, takže nezískáme žádné řešení. 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 /i\ A > 0, ii > 0 : Komplementarita pro oba multiplikátory dává 3p^ + 5p2 = 4, Pí + P2 = 1, což nám dá řešení p^ = p2 = \, po dosazení do prvních dvou rovnic dostaneme 5 + A - 3/i = 0, 6 + A - 5/i = 0, tato soustava ale dává záporné A, takže nezískáme žádné řešení. A = 0, ii > 0 : Z komplementarity pro ii plyne 3p^ + 5p2 = 4. Zřejmě tedy p2 7^ 0 a druhou podmínku lze vydělit p2: 4^ + 8p2 - 5/i = 0, po vyloučení možnosti Pí = 0 (pokazila by se nezápornost U^) musí být 6pi + 4p2 + A - 3/i = 0, takže dostaneme lineární soustavu, jejímž řešením je Pí = 0,16, p2 = 0,7, ii = 1,25 a očekávaný výnos 4 při riziku 2,5. 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 /i\ A > 0, ii > 0 : Komplementarita pro oba multiplikátory dává 3p^ + 5p2 = 4, Pí + P2 = 1, což nám dá řešení p^ = p2 = \, po dosazení do prvních dvou rovnic dostaneme 5 + A - 3/i = 0, 6 + A - 5// = 0, tato soustava ale dává záporné A, takže nezískáme žádné řešení. A = 0, ii > 0 : Z komplementarity pro ii plyne 3pi + 5p2 = 4. Zřejmě tedy p2 0 a druhou podmínku lze vydělit p2: Ap\ + 8p2 - 5/i = 0, po vyloučení možnosti Pí = 0 (pokazila by se nezápornost U^) musí být 6pi + 4p2 + A - 3/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, ii = 0 : Z komplementarity pro A plyne Pí + p2 = 1. Pro extrémní případ Pí = 0, p2 = 1 nebo naopak se pokazí nezápornost derivace UpA nebo Up2. Tedy pí, p2 ^ 0 a první dvě podmínky lze vydělit pí a p2: 6pi + 4p2 + A = 0, Ap\ + 8p2 + A = 0 a dostaneme soustavu, pro niž však vyjde A < 0, takže nezískáme žádné řešení. Kvadratické programování, příklad: optimalizace portfolia A = fi = 0 : Z prvních dvou rovnic dostaneme (6pi + 4p2)pi = 0, (4pí + 8p2)p2 = 0, což má jediné nezáporné řešení Pí = p2 = 0, což však nevyhovuje podmínce 3pi + 5p2 > 4. 2=|- Kvadratické programování, příklad: optimalizace portfolia Úlohu bychom mohli řešit i pro jiné aspirační úrovně výnosu Rmjn, například Rmin e {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: o J ji 4 vi 2 - i v t : i L : riziko i 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í f{Y) = c • E (Y) - (1 - c) • D{Y) na množině všech portfolií, kde konstanta c probíhá interval (0,1).