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í. 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. Lineární programování Při formulaci úlohy matematického programování je třeba vycházet z dobře popsaného ekonomického modelu. Lineá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 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 □ s 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. Řešení úlohy LP v Excelu Je třeba aktivovat doplněk Řešitel (Solver) na liště Soubory - vybrat Možnosti, pak Doplňky, zvolit dole "spravovat doplňky Excel". V dialogovém okně odškrtnout položku Řešitel a potvrdit OK. Nabídka pro použití řešitele se pak objeví na záložce Data. Před použitím řešitele je třeba připravit si sešit se zadáním optimalizačního problému: A B c D E F 1 2 Rozhodovací proměnné množství produkce Mocca Standard 4 xl x2 5 6 7 účelová funce zisk z tuny (v 1000 Kč) celkový zisk 8 20 14 =BS*$B$5+CS*$C$5 3 10 koeficienty spotřebované množství kapacita 11 omezení 0,5 0,25 =B11*$B$5+C11*$C$5 =B12*$B$5+C12*$C$5 =B13*$B$5+C13*$C$5 <= 40 12 0,5 0,5 <= 60 13 0 0,25 <= 25 14 Řešení úlohy LP v Excelu V nastavení řešitele je třeba zvolit buňky s klíčovými komponentami optimalizačního problému účelovou funkcí a směrem optimalizace, proměnnými a omezeními : Parametry Řešitele SDSS Nastavit dl: Na; ®Max O Min O Hodnota: Na základě mněny proměnných buněk: ses5:SCs5 Onnezyjía podmínky: SDSll <= SFSll SD512 <= SFSlZ 5D513 <= 5FS13 0 Nastavit proměnné bez orneiujídch podmínek jako nezáporné Vyberte metodu řešení: Simplex LP Přidat Změnit Odstranit Vynulovat vše Načíst nebo uložit Možnosti Metoda řešení Modul GRG Nonlinear vyberte pro hladké nelineární problémy Řešitele. Modul LP Simplex zvolte pro lineární problémy Řešitele a modul Evolutionary pro nehladké problémy Řešitele, Náp_ověda Řešit Zavřít Řešení úlohy LP v Excelu Po zmáčknutí tlačítka „Řešit" ponechte volbu „Uchovat řešení Řešitele" a potvrďte. Optimální hodnoty proměnných a zisku se objeví v příslušných polích sešitu: A B c D E F 1 2 Rozhodovací proměnné 4 5 6 množství proč Mo cca Standard xl x2 7 účelová funce zisk z tu (v 1000 Kč) celkový zisk 3 20 14 1920 9 10 koeficienty spotřebované množství kapacita 11 omezení 0,5 0,25 60 <= 40 12 0,5 0,5 <= 60 13 14 0 0,25 <= 25 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 Příklad k samostatnému řešení Pan XY má rád steak s vařenými bramborami, proto se rozhodl, že založí svůj jídelníček výhradně na tomto jídle (plus nějaké tekutiny a vitamínové doplňky). Zároveň chce mít jistotu, že budou splněny nutriční požadavky na denní dávky uhlohydrátů a bílkovin a že nebude překročen limit pro obsah tuku. Nutriční hodnoty a ceny za porci jsou uvedeny v tabulce. Ingredience Gramů v porci Denní požadavek Steak Brambory (gramů) Uhlohydráty 5 15 > 40 Bílkoviny 20 5 > 50 Tuk 15 2 < 60 Cena porce 40 Kč 20 Kč Navrhněte panu XY, jaké množství porcí steaků a brambor má denně sníst, tak aby byly při minimální celkové ceně splněny všechny dietní požadavky. Formulujte jako problém lineárního programování a vyřešte grafickou metodou i pomocí Excelu. Dualita úloh LP Na úlohu o kávě 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 úlohu o kávě 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,25w^ + 0,5w2 + 0,25w3 > 14. Dualita úloh LP Na úlohu o kávě 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,25ivi + 0,51/1/2 + 0,251/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í. 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é Ck (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é bj 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 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 (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*. t*2 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],^ = [20,100] resp. x* = [40,80], B = [80,0]. Pro její směrnici q tedy musí platit nerovnosti Směrnici původní izokvanty z = c^x^ + 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 e (14,28). Analogicky pro c2 získáme interval stability dosazením q = =^ do nerovností: -2 < ^ < -1 a dostaneme c2 e (10,20). 2 80-0 40-80 < q < 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í. 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. Postoptimalizační analýza - intervaly stability pro kapacity Původní rovnice hraniční přímky prvního omezení byla 0,5^ + 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 b\: 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,5^ + 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 = 24. Stínové ceny najdeme v optimální tabulce pod sloupci přídatných proměnných! Postoptimalizační analýza v Excelu Postoptimalizační analýza je standardní součástí výstupu Řešitele, v dialogovém okně „Výsledky řešitele" je v nabídce sestav možnost zvolit Citlivostní zprávu, která se po potvrzení objeví na samostatném listu: IVťcrosoft Excel 14.0 Citlivostní sestava —■ List: [Sešiti]Listí Sestava vytvořena: 15.10. 201S 12:41:46 Proměnné buňky Konečná Snížené Cenový Povolený Povolený Buňka Název Hodnota náklady koeficient nárůst pokles $E$5 xl 40 0 2C 8 6 $C$5 x2 SO 0 14 6 4 Omezující podmínky Konečná Stínová Pravá strana Povolený Povolený Buňka Název Hodnota cena omezující podmínky nárůst pokles $D$11 omezení spotřebované množství 40 24 40 2C 5 $D$12 spotřebované množství 60 16 60 5 2C $D$13 spotřebované množství 2C 0 25 1E+30 5 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 a přiřazovací problém. Další problémy (kontejnerový či vícestupňový dopravní problém, úloha o pokrytí, okružní dopravní problém apod.) jsou popsány v literatuře. Úlohy, ve kterých některé proměnné mohou nabývat pouze hodnot z množiny celých čísel souhrnně 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. Tento typ úloh reprezentují například rozvrhování nebo stanovení řezných plánů. Celočíselný problém - rozvrhování Příklad : Správa sbírkového fondu a provozní potřeba galerie vyžadují, aby v jednotlivých dnech byly v galerii ve službě tyto počty osob: PO UT ST v- CT PA SO NE 22 17 13 14 15 18 24 Pracující nastupují do zaměstnání tak, že odpracují vždy 5 po sobě jdoucích dní, po kterých následují dva dny volna. Nástupy se mohou uskutečnit kterýkoliv den v týdnu. Úkolem je stanovit co nejmenší počet zaměstnanců a rozvrhnout jejich nástupy do 5-denních pracovních cyklů tak, aby byly každý den v týdnu pokryty provozní potřeby. Sestavte model a vyřešte v Řešiteli. Celočíselný problém - řezný plán Příklad : Firma vyrábějící kovové součástky nakupuje v libovolném množství trubky o délce 65 cm. K výrobě součástek potřebuje alespoň 1200 ks trubek o délce 20 cm a alespoň 900 ks trubek o délce 15 cm. Jakým způsobem má firma rozřezat nakoupené trubky tak, aby spotřeba nakoupeného materiálu byla minimální? Sestavte model a vyřešte v Řešiteli. Celočíselný problém - řezný plán Příklad : Firma vyrábějící kovové součástky nakupuje v libovolném množství trubky o délce 65 cm. K výrobě součástek potřebuje alespoň 1200 ks trubek o délce 20 cm a alespoň 900 ks trubek o délce 15 cm. Jakým způsobem má firma rozřezat nakoupené trubky tak, aby spotřeba nakoupeného materiálu byla minimální? Sestavte model a vyřešte v Řešiteli. 15 15 15 15 15 15 15 20 15 20 20 20 20 20 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 V2, ..., Vm s omezenými kapacitami a\, a2, ...,ama dále máme n cílových míst - odběratelů S^, S2, ..., Sn se stanovenými požadavky b\, £>2, ..., 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 Qy, / = 1,..., m, j = 1,..., n. Cílem je naplánovat objemy přepravy mezi jednotlivými zdroji a cíli ( označíme je Xjj, i = 1,..., /t?, j = 1,..., a?) tak, aby byly uspokojeny požadavky odběratelů a nebyly překročeny kapacity zdrojů. 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 V2, ..., Vm s omezenými kapacitami a\, a2, ...,ama dále máme n cílových míst - odběratelů S^, S2, ..., Sn se stanovenými požadavky b\, 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 Xjj, i = 1,..., /t?, 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 Xjj, pro něž minimalizujeme účelovou funkci Z — S/=1 Sy=1 Cijxij za podmínek Sy=1 Xij — / = ^ 5 . . . , a77, £^ = 7 = 1, . . . , a7, Xjj > 0, / = 1,..., m, ,7 = 1, . . . , a? Účelová funkce i omezení jsou lineární, jde tedy o úlohu lineárního programování. <=2, , Dopravní problém - vyrovnání úlohy Zřejmě není možné uspokojit všechny spotřebitele, jestliže celková poptávka Ylj=\ ty převyšuje celkovou kapacitu a/> úloha pak nemá přípustné řešení. Úlohu, ve které platí rovnost Yfj=\ ty = Z)/Li a\ 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. Dopravní problém - vyrovnání úlohy Zřejmě není možné uspokojit všechny spotřebitele, jestliže celková poptávka Ylj=\ ty převyšuje celkovou kapacitu a/> úloha pak nemá přípustné řešení. Úlohu, ve které platí rovnost Yfj=\ ty = Z)/Li a\ 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 ty - a/- v případě převisu nabídky se naopak zavede fiktivní zákazník s požadavkem a\ - Z)yLi ty-Pozor! Přepravní náklady do fiktivních míst jsou vždy nulové. Dopravní problém - príklad Příklad : Ukažme si řešení úlohy z "M. Plevný, M. Žižka: Modelování a optimalizace v manažerském rozhodování": Najděte optimální řešení dopravní úlohy s požadavky odběratelů S^, S2, S3 a S4 postupně 3, 6, 4 a 5 jednotek zboží a zdroji , V2 a V3 s kapacitou po řadě 5, 7 a 6 jednotek, kde náklady jsou dané tabulkou: Jednotkové náklady Cij Si s2 s3 s4 Ví 2 1 3 4 v2 6 2 6 1 7 3 3 3 Dopravní problém v Řešiteli Připravíme si tabulku nákladů a prázdné buňky, kde budeme ukládat přepravené množství. Pro výpočet celkových nákladů můžeme použít funkci skalární součin. A B c F H 1 2 3 j4_ 5 přepravené množství 6_ S1 S2 S3 S4 celkem kapacita 7_ V1 =SUMA(C7:F7) 5 8 V2 =SUMA(CS:F8) 9 V3 =SUMA(C9:F9) 6 10_ celkem =SUMA(C7:C9) =SUMA(D7:D9) =SUMA(E7:E9) =SUMA(F7:F9) 11 požadavek 3 6 4 5 12 13 14 náklady 15 S1 S2 S3 S4 15 V1 2 1 3 4 17 V2 6 2 6 1 18 V3 7 3 3 3 19 20 _ 21 celkové náklady 22 =SOUČIN.SKALÁRNÍ(C7:F9;C 1 Q:F18) Dopravní problém v Řešiteli Minimalizujeme celkové náklady za omezení, že jsou splněny požadavky a nejsou překročeny kapacity. Parametry Řešitele Nastavit dl: Na; O Max Miř O Hodnota: Na základě mněny proměnných buněk: SC57:SFS9 Omezující podmínky: SC510:SF510 = SCSll:SFSll SGS7:SG59 <= SHS7:SH59 @ Nastavit proměnné bez omezujících podmínek jako nezáporné Vyberte metodu řešení: Simplex LP Přidat Změnit Odstranit Vynulovat vše Načíst nebo uložit Možnosti Metoda řešení Modul GRG Nonlinear vyberte pro hladké nelineární problémy Řešitele. Modul LP Simplex zvolte pro lineární problémy Řešitele a modul Evolutionary pro nehladké problémy Řešitele. Nápověda Řešit Zavřít 7946 Dopravní problém v Řešiteli Vidíme nelezené optimální řešení s celkovými přepravními náklady ve výši 35 jednotek. B E F G H i 1 2 3 4_ S 6_ přepravené množství S1 S2 S3 S4 celkem kapacita 7_ V2 V3 celkem požadavek 3 2 0 0 5 5 8_ 0 2 0 5 7 7 9 0 2 4 0 e e 10 3 6 4 5 11 12 3 e 4 5 13 14 15 náklady S1 S2 S3 S4 16 17_ 18 19 Í0 V2 V3 2 1 3 4 6 7 2 6 1 3 3 3 ?1 12 celkové náklady 35 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. 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. Příklad : 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ž žádný stroj nemůže vykonávat dvě práce. Výrobní náklady jsou dány tabulkou: stroje Cij 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 celkový 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 xi}■ = 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 = Z)/=1 Z)y=1 CÍjXíj za podmínek y^j—i = i j /=i,..., a?, Xije{0, 1}, / = 1, j = 1,...,a? □ 3 ► < ► < -ě: -š -O Q, O Přiřazovací problém v Řešiteli Připravíme si tabulku nákladů a prázdné buňky, kde budeme ukládat hodnoty 1/0 podle toho zda se daná práce přiřadí konkrétnímu zdroji. Uvažujeme i čtvrtou fiktivní práci, abychom úlohu vyrovnali. Náklady na vykonání fiktivní práce jsou nulové. Pro výpočet celkových nákladů můžeme použít funkci skalární součin. A B C D E F G 1 NÁKLADY stroje 2 práce A B C D 1 15 19 17 12 4 2 12 10 15 9 5 3 18 14 11 14 6 fiktivní 4 0 0 0 0 7 S přiřadil? (l=ANO, 0=NE) stroje 9 práce A B C D suma 10 1 =SUMA(C10:F10) 11 2 =SUMA(C11:F11) 12 3 =SUMA(C12:F12) 13 fiktivní 4 =SUMA(C13:F13) 14 suma =SUMA(C10:C13) =SUMA(D10:D13) =SUMA(E10:E13) =SUMA(F10:F13) 15 Celkové náklady 16 =SOUČIN.SKALÁRNÍ(C3:F6;C10:F13] 17 Přiřazovací problém v Řešiteli Kromě podmínek, aby každá práce byla provedena právě jednou (řádkové součty = 1) a aby každý stroj vykonával právě jednu ze čtyř „prací" (sloupcové součty = 1) zahrneme podmínku, že všechny proměnné jsou binární. Parametry Řešitele Nastavit dl: Na O Max ® Min Na základě změny proměnných buněk: O Hodnota: 5C510:5F513 Ornezyjíd podmínky: SC510:5F513 = binární_číslo 5C514:5F514= 1 5G5lO:5G5l3 = 1 1^1 Nastavit proměnné bez omezirjídch podmínek jako nezáporné Vyberte metodu řešení: Simplex LP Přidat Změnit Odstranit Vynulovat vše Načíst nebo uložit Možnosti Metoda řešení Modul GRG Nonlinear vyberte pro hladké nelineární problémy Řešitele. Modul LP Simplex zvolte pro lineární problémy Řešitele a modul Evolutionary pro nehladké problémy Řešitele. Nápověda Řešit Zavřít Přiřazovací problém v Řešiteli Nalezené optimální řešení přiřadí práci 1 na stroj D, práci 2 na stroj B a práci 3 na stroj C. Stroj A nebude pracovat. Celkové náklady budou 12 + 10 + 11 =33. Úloha nemusí mít jediné řešení. A B C D E F G H 1 NÁKLADY stroje 2 práce 1 2 3 fiktivní 4 A B C D 15 19 17 12 4 12 10 15 9 5 18 14 11 14 6 0 0 0 0 7 S přiřadit? (l=ANO, 0=NE) stroje 9 práce A B C D suma 10 1 2 3 fiktivní 4 suma 0 0 0 1 1 11 0 1 0 0 1 12 0 0 1 0 1 13 1 0 0 0 1 14 1 1 1 1 15 Celkové náklady 33 16 17 Další tipy OpenSolver: rozšiřující doplněk pro Excel nebo Google Sheets, zvládne větší v počet proměnných a omezení než Řešitel https: //opensolver. org/ min i J til Model Show/Hide Model ^—^+ Quick Solve Solve OpenSolver T OpenSolver Literatura: 9 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 o GROS, Ivan: Kvantitativní metody v manažerském rozhodování, 1. vyd. Praha: Grada, 2003 Doplňující předměty: https://is.muni.cz/auth/predmet/econ/podzim2018/MPM_OMVE https://is.muni.cz/auth/predmet/econ/jaro2018/BPM_AOME