MKM.OMVE: úlohy k řešení Lineární programování, formulace optimalizační úlohy Příklad 1: Sestavte matematický model úlohy: a) Úloha rozvrhování reklamy Jde o rozdělení prostředků na reklamní kampaň pro penzijní připojištění do jednotlivých médií (televize, rozhlas, noviny, časopisy, poutače), tak aby byl maximalizován celkový účinek reklamy vyjádřený počtem osob "oslovených reklamou,, Reklama je prioritně zaměřena na určité kategorie osob dle věku, vzdělání a příjmové skupiny. Požadavky zadavatele jsou následující: • do televize a rozhlasu půjde maximálně 50 % prostředků • do každého z médií lze umístit aspoň 10% ale ne víc než 30 % celkového rozpočtu • je třeba oslovit aspoň 2,5 mil. osob ve věku 30-50 let, aspoň 0,8 mil. osob v příjmové skupině nad 20000,- Kč měsíčně a aspoň 1,5 mil. osob s minimálně středoškolským vzděláním. Celkový objem prostředků uvolněných na kampaň je 10 mil. Kč. Na základě pravidelných průzkumů prováděných reklamní agenturou bylo odhadnuto, že při vynaložení 1000 Kč bude prostřednictvím jednotlivých médií zasaženy následující počty osob z uvedených kategorií: druh média televize rozhlas časopis noviny poutače celkem 750 420 300 360 180 věk 30 - 50 320 280 140 240 120 příjem > 20 000 Kč 120 90 60 60 50 SS vzdělání 350 200 120 140 60 Navrhněte takovou strukturu reklamní kampaně, aby byl počet oslovených maximální a přitom byly splněny požadavky zadavatele i rozpočtové omezení. b) Úloha diverzifikace portfolia Investiční společnost plánuje investovat 50 mil. Kč do cenných papírů. Pro tuto investici vybírá z pěti variant: akcie tří společností A\,Ai, A% a dva druhy obli- gací 0\, 02- Každá z těchto pěti variant je charakterizovaná očekávanou mírou výnosu v procentech za rok a bezrozměrným koeficientem vyjadřujícím míru rizika investice, viz tabulka: Ai A2 A3 Oi o2 výnos [%] 25 18 20 14 12 míra rizika 9 5 7 3 1 Investiční strategie společnosti předpokládá, že: • do obligací půjde minimálně 50 % celkově investované částky • celková míra rizika (tj. vážený průměr rizik jednotlivých variant) nepřesáhne hodnotu 5 • žádná z variant nebude nakoupena v menším objemu než 5 mil. Kč Cílem modelu je navrhnout takovou strukturu portfolia, která bude maximalizovat celkový očekávaný výnos a přitom bude respektovat uvedenou investiční strategii. c) Finanční analýza projektů Investor, který má na začátku období volně k dispozici 1,5 mil. Kč se rozhoduje o účasti na třech investičních projektech A, B, C. Všechny porjekty jsou plánovány na dva roky, přičemž náklady a výnosy jsou definovány v půlročních intervalech, viz údaje v tabulce [mil. Kč] (kladné hodnoty představují výnosy a záporné náklady): období 1/2013 7/2013 1/2014 7/2014 12/2014 projekt A -0,5 -0,3 0,3 0,6 1,0 projekt B -1,0 -0,4 -0,2 0,7 2,3 projekt C -0,8 0,2 0,4 0,4 0,4 Protože investor nemá dostatečné prostředky aby pokryl všechny náklady v jednotlivých obdobích, musí volit pouze částečnou participaci na některých projektech (potom jsou náklady i výnosy kráceny na poměrnou část). Pokud investorovi v kterémkoliv období zbydou nějaké volné prostředky, může je uložit jako termínovaný vklad na 6 měsíců, čímž za toto období získá 5 % uložené částky. Úkolem je navrhnout investiční strategii tak, aby byl maximalizován objem prostředků na konci dvouletého období. Příklad 2: Pomocí grafické metody vyřešte úlohu LP: z = 2x\ — X2 —> min. za podmínek X\ — X2 > —2 X\ + X2 < 6 X\ — X2 < 0 Xi>l X2>0 Doplňující otázky: • Jak by se změnilo řešení, kdyby nerovnosti v omezeních byly ostré? • Jak se změní řešení, jestliže obrátíme u druhého omezení znaménko nerovnosti na x\ + X2 > 6? • Jak se změní řešení, jestliže kromě otočení druhé nerovnosti na x\ + X2 > 6 budeme účelovou funkci maximalizovat místo minimalizace? Lineární programování, simplexová metoda, řešení pomocí MS Excel Solver, postoptimalizační analýza Příklad 3: Řešení úloh z prvního příkladu minulé kapitoly pomocí počítače: Spusťte MS Excel a zapněte si doplněk Solver (Řešitel). Odkaz na návod, jak postupovat, je v učebních materiálech. Tamtéž se nalézají soubory finanalyza.xls, reklama.xls a portfolio.xls. Po otevření souboru v Excelu spustíte Řešitel na ro-letce Nástroje, dále je třeba nastavit cílovou buňku, měněné buňky a postupně přidat omezující podmínky. V Možnostech lze zakliknout tlačítko „Nezáporná čísla". Pokud jste postupovali správně, po uložení Možností stiskem „OK" a následným stiskem tlačítka „Řešit" se objeví hláška, že bylo nalezeno vyhovující řešení. Následným stiskem „OK" potvrdíme, že chceme uchovat řešení a můžeme si prohlédnout výsledky. Příklad 4: Simplexovou metodou řešte následující úlohy: a) z = 36xi + 12^2 + 6OX3 —> max. za podmínek 2x\ + X2 + 3^3 < 9 xi + 3^3 < 3 Xi, X2, ^3 > 0 b) z = xi + 2^2 ->■ m-ax. za podmínek #1 — ^2 < 12 -2xi + x2 < 8 xi, x2, > 0 c) z = 3xi — X2 —> max. za podmínek 3xi + X2 < 3 3xi - 4x2 > 12 —2xi + X2 > 6 xi, x2, > 0 Příklad 5: Pomocí Řešitele nalezněte optimální řešení úlohy z části a) předchozího příkladu. Doplňující otázky: • Na základě citlivostní zprávy z Řešitele určete intervaly stability pro cenové koeficienty i pro omezení. • Interpretujte zadání úlohy jako úlohu optimalizace výrobního programu s m surovinami a n výrobky a formulujte duální úlohu k původní úloze. • Kde ve výsledcích z Řešitele nalezneme optimální hodnoty duálních proměnných? • Kde v simplexové tabulce nalezneme řešení duální úlohy? • Zkontrolujte, zda se hodnoty účelových funkcí primární a duální úlohy shodují. Distribuční úlohy (metoda SZ rohu, indexová, VAM a MODI), přiřazovací úlohy (maďarská metoda) Příklad 6: Finanční úřad vypsal konkurz na místa vedoucích tří oddělení, vyžadující odlišné schopnosti a vědomosti. Do konkurzu se přihlásilo pět uchazečů, u kterých byly pomocí testů s maximálním počtem bodů 30 zjišťovány předpoklady pro výkon jednotlivých funkcí. Výsledky testu jsou uvedeny v tabulce. uchazeč oddělení A B C D E Oi 25 27 24 27 28 02 28 23 25 24 27 03 22 21 23 20 24 Přiřaďte pomocí maďarské metody 3 z uchazečů na příslušná vedoucí místa tak, aby jejich předpoklady pro práci na jednotlivých odděleních byly co nejvyšší. Příklad 7: Firma Glass bottle, a.s. vyrábí 4 typy pivních lahví (S10°, G12°, P12° 1/21 a P12° 1/31) na třech výrobních linkách A,B,C. Vzhledem k jejich rozdílnému výkonu jsou jednotkové náklady rozdílné, viz tabulka: S10° G12° P12° 1/21 P12° 1/31 kapacita linka A 2,20 2,50 2,50 1,80 100 linka B 2,00 2,30 2,40 1,70 150 linka C 1,95 2,20 2,30 1,70 130 požadavek 200 50 80 30 Měsíční výrobní kapacita linek A, B, C je po řadě 100, 150 a 130 tisíc ks. Na základě smluv je třeba dodat 200, 50, 80 a 30 tisíc ks lahví S10°, G12°, P12° 1/21 a P12° 1/31. Cílem je rozvrhnout produkci na jednotlivých linkách tak, aby byly minimalizovány výrobní náklady. Vaším úkolem je: • rozhodnout, o jaký typ úlohy se jedná • najít přípustné řešení metodou SZ rohu, indexovou metodou a VAM • získaná řešení porovnat s optimálním řešením získaným pomocí Řešitele _ / _ -s _ Příklad 8: Úloha z knihy T. Subrt a kol., Ekonomicko-matematické metody: Svoz brambor Ze tří honů (Hl, H2, H3) se svážejí brambory do čtyř skladů (SI, S2, S3, S4). Vzdálenosti honů a skladů jsou zadány v kilometrech, produkce honů a kapacity skladů v tunách. Máme stanovit takový přepravní plán, při kterém ujedou vozidla minimální počet tunokilometrů. Výchozí údaje o jednotlivých vzdálenostech a kapacitách jsou v tabulce Hon SI S2 S3 S4 produkce honu Hl 11 11 7 12 50 H2 6 9 6 10 200 H3 5 8 11 10 150 kapacita skladu 120 90 70 120 Zkontrolujte vyrovnanost úlohy, najděte výchozí přípustné řešení a postupujte dál metodou MODI až k nalezení optimálního řešení. Úlohy celočíselného programování, heuristiky pro okružní dopravní problém Příklad 9: Sestavte matematický model úlohy celočíselného programování a pomocí Řešitele nalezněte optimální řešení (nezapomeňte v Omezujících podmínkách přidat podmínky celočíselnosti): a) Úloha o bramborách Potravinářská firma se zabývá zpracováním brambor. Jejími produkty jsou bramborové lupínky, které prodává po 120 Kč/kg, a hranolky po 76 Kč/kg. Na výrobu 1 kg lupínků se spotřebuje 2 kg brambor a 0,4 1 oleje a na výrobu 1 kg hranolků 1,5 kg brambor a 0,2 1 oleje. Navrhněte výrobní program tak, aby byl při nákupních cenách surovin 12 Kč/kg brambor a 40 Kč/l oleje maximální ZISK (zanedbáme náklady na práci, energii, apod.) a přitom nebyla překročena kapacita dodavatele (100 kg brambor a 16 1 oleje). Jak se změní optimální řešení, je-li odběratel ochoten odebírat zboží pouze v baleních (lupínky á 3kg a hranolky á 15kg)? b) Úloha o řezném plánu 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í? c) Úloha o dopravě Dopravní společnost v městě S zásobuje paletovaným zbožím 4 stejně vzdálená sousední města A, B, C a D. Dnes má rozvézt 110 palet do města A, 70 do B, 58 do C a 62 do D. Má dva typy nákladních aut s fixními cenami jízdy: 6 malých aut s kapacitou 33 palet a cenou jízdy 120 Kč a 4 velká auta s kapacitou 60 palet a cenou jízdy 190 Kč. Každé auto stihne za den jen jednu cestu. Která auta mají kam jet, aby cena dopravy byla minimální? d) Úloha o pracovním rozvrhu služeb 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 ČT 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. e) Úloha o zakázkách Podnik může převzít 6 různých zakázek, které se liší spotřebou času výrobního zařízení. Je znám zisk z jednotlivých zakázek a materiálová spotřeba. Zásoba materiálu a času je omezená. Parametry zakázek jsou shrnuty v tabulce: č. zakázky 1 2 3 4 5 6 disponibilní kapacita zisk 11 63 9 5 4 8 —> max. spotřeba času směny] 1 7 1 1 1 5 15 směn spotřeba materiálu [kg] 15 70 10 5 3 2 lOOkg Navrhněte, které zakázky má podnik realizovat, aby byl jeho zisk maximální. Příklad 10: Dealer, sídlící ve městě A, má za úkol během dne nabízet zboží ve městech B, C, D, E, jejichž vzájemné vzdálenosti jsou uvedeny v tabulce. A B C D E A X 50 70 40 60 B 50 X 40 30 80 C 70 40 X 40 60 D 40 30 40 X 50 E 60 80 60 50 X V jakém pořadí má tato města navštívit, aby ujel co nejméně kilometrů? Navrhněte trasu metodou nej bližšího souseda (začátek volte postupně ve všech městech). Porovnejte nalezené řešení s řešením získaným metodou výhodnostních čísel. Optimalitu řešení ověřte maďarskou metodou, při které kontrolujte, zda se optimální řešení nerozpadá na dva samostatné okruhy, (nutnou podmínkou je nevybírat nezávislé nuly na pozicích symetrických dle hlavní diagonály a dalších pozicích uzavírajících okruh z již vybraných nul). Řízení projektů Příklad 11: Sestrojte síťový diagram znázorňující přípravu vědecké konference, která si vyžádá tyto hlavní činnosti: a) vypracování programu konference (2dny) b) zajištění termínu a místa konání konference (3dny) c) dojednání účasti přednášejících (7dní) d) vypracování a zaslání tezí od přednášejících (14dní) e) rozeslání pozvánek na konferenci (4 dny) f) příjem a zpracování přihlášek od zájemců o účast (20dní) g) zorganizování pořadatelské služby (2dny) h) tisk a rozmnožení tezí přednášek (3 dny) i) předání tezí a seznamu účastníků pořadatelské službě, rozpis ubytování a stravování (2dny) Příklad 12: Je dán projekt skládající se ze 7 elementárních činností, jejichž návaznosti a doba trvání je uvedena v následující tabulce: činnost trvání bezprostředně předcházející činnost A 5 - B 9 - C 11 A, B D 6 B E 7 A F 5 C,D G 9 C, E a) sestavte síťový graf projektu b) pomocí metody CPM určete minimální dobu projektu a vyznačte kritickou cestu c) sestavte časový diagram realizace činností projektu Příklad 13: Je dán projekt skládající se z 8 elementárních činností, jejichž návaznosti a doba trvání je uvedena v následující tabulce: činnost trvání bezprostředně předcházející činnost A 4 - B 1 - C 3 B D 3 A, B E 1 B F 5 B G 4 C, D H 4 C, D, F a) sestavte síťový graf projektu b) pomocí metody CPM určete minimální dobu projektu a vyznačte kritickou cestu c) sestavte časový diagram realizace činností projektu Příklad 14: Stáhněte si z adresy http://www.vertex42.com/ExcelTemplates/critical-path-method.html šablonu pro metodu CPM v Excelu a vložte údaje o projektech z předchozích úloh. Znázorněte Ganttovy diagramy řešených projektů. Metody vícekriteriálního rozhodování Příklad 15: Při hodnocení indexu kvality života podle OECD (www.oecd.org/) byly zjišťovány mimo jiné následující údaje: a) příjem domácností [USD] b) výdaje na bydlení [%] c) zaměstnanost [%] d) očekávaná délka života [roky] e) počet vražd na 100 000 obyvatel Jednotlivými variantami byly zvoleny země sousedící s CR: CR, Německo, Rakousko, Polsko, Slovensko. Hodnoty kritérií pro jednotlivé země jsou uvedeny v tabulce. kritérium varianty příj. dom. výd. na bydl. zaměstn. oč. dél. živ. vraž. CR 16614 26 65 77,7 0,9 Rakousko 27541 22 72 80,7 0,5 Německo 27692 22 71 80,5 0,8 Polsko 14508 26 59 75,2 1,6 Slovensko 15840 24 59 76,3 1,3 • Určete typy jednotlivých kritérií a vyberte nedominované varianty. • Stanovte kolektivně váhy jednotlivých kritérií pomocí Fullerova trojúhelníku. Preference kritérií stanovte hlasováním. • Stanovte váhy kritérií individuálně pomocí Saatyho metody. Výsledky porovnejte. • Pro kolektivně stanovené váhy seřaďte alternativy metodami WSA a TOP-SIS (výpočty můžete provádět v MS Excel, data naleznete v souboru oecd.xlsx) Příklad 16: Stáhněte si aplikaci SANNA a podle návodu k použití aktivujte v MS Excel. Proveďte znovu úkony z předchozího příkladu s využitím SANNY. Příklad 17: Uvažujte vícekriteriální lineární model z\ = 8x1 + 6x2 + 2x3 —> max Z2 = Sx\ + 4^2 + 5^3 —> min za omezení 4xi + 2x2 + X3 < 36 xi + 2x2 - 2x3 < 12 xu x2, xs>0 • Nalezněte simplexovou metodou dílčí optimální řešení • Nalezněte simplexovou metodou kompromisní řešení při agregaci kritérií s váhami v\ = 0, 5 a ví = 0, 5. • Nalezněte simplexovou metodou optimální hodnotu prvního kritéria, na-stavíme-li aspirační úroveň pro z^ na hodnotu 10. Příklad 18: Uvažujme nutriční problém sestavení denního jídelníčku pro 100 osob, přičemž k dispozici máme 9 druhů základních potravin. Složení potravin z hlediska důležitých výživových komponent a jejich ceny (vše přepočteno na lOOg potraviny), viz tabulka: energ. bflk. Fe vit. A vit. C chol cena [kJ] [g] [mg] [jed] [mg] [mg] [Kč] maso vepř. 1200 18,4 3,1 20 0 83 12 máslo 3000 0,6 0,2 2500 0 120 11,2 chleba 1160 7,2 0,8 0 0 1 1,5 brambory 300 1,6 0,6 40 10 0 1,2 jablka 240 0 0,5 60 2 0 1,5 eidam 1260 31,2 0,6 1100 0 71 10,6 kuře 650 20,2 1,5 0 0 57 6 jogurt 450 7 0,2 260 0 11 4,5 jahody 150 0 0,8 60 60 0 12 Nutriční odborníci stanovili, že denní dávka výživy pro dospělého by měla obsahovat minimálně 80 g bílkovin, 15mg železa, 6000 jednotek vitamínu A a 200 mg vitamínu C. Pro zajištění celodenního stravování pro 100 osob máme sestavit optimální skladbu jídelníčku při respektování doporučení nutričních expertů a současně s co nej vyšší energetickou hodnotou, co nej menším obsahem cholesterolu a za co nejméně peněz, přitom máme k dispozici maximálně 40 kg každé potraviny. Vyzkoušejte různé přístupy vícekriteriálního programování. Lineární lomené programování, Analýza datových obalů Příklad 19: Uvažujme úlohu lineárního lomeného programování minimalizovat funkci za podmínek x\ — %2 + ^3 < 5 X2 > 3 xi,xs>0 a) Linearizujte úlohu pomocí vhodné substituce b) Vyřešte linearizovanou úlohu c) Zkontrolujte řešení pomocí Řešitele Příklad 20: Uvažujte DEA model pro 8 nemocničních oddělení, jejichž výkon je charakterizován následujícími hodnotami: Jednotka Ol 02 03 04 05 06 07 08 personál 7 6 6 8 10 5 4 5 pacientů ambulantně 21 24 42 16 50 45 40 60 hospitalizovaných pacientů 63 36 48 40 40 15 24 10 a) Znázorněte graficky. Uvažujte konstantní výnosy z rozsahu a najděte efektivní hranici. b) Pro 5. oddělení určete graficky míru efektivity a nalezněte jeho referenční jednotky při orientaci na výstupy. c) Sestavte vstupově orientovaný CCR model pro 5. oddělení a vyřešte pomocí řešitele (nutno zvolit metodu GRG nonlinear) d) Linearizujte vstupově orientovaný CCR model pro 5. oddělení a vyřešte pomocí řešitele ( metodou Simplex LP) Příklad 21: (BCC model, zpracováno dle J. a M. Zouharových z VŠE) Následující tabulka zachycuje počet lektorů (v desítkách) a počet úspěšných absolventů (ve stovkách) za poslední rok pro jisté vysoké školy A až D. škola A B C D lektorů [10] 1 3 7 5 absolventů [100] 3 5 7 4 • V grafu s osami vstup a výstup zachyťte efektivní hranici při variabilních výnosech z rozsahu. Porovnejte počet efektivních jednotek při předpokladu VRS s případem CRS. • Najděte vstup, výstup a referenční jednotky pro virtuální jednotku D\ ve vstupově orientovaném modelu (input-oriented), spočtěte efektivnost D podle tohoto modelu. • Najděte vstup, výstup a referenční jednotky pro virtuální jednotku Di ve výstupově orientovaném modelu (output-oriented), spočtěte efektivnost D podle tohoto modelu. Příklad 22: (Úloha Mgr. Jany Kalčevové, PhD z VŠE) Uvažujte model DEA s 2 vstupy, 3 výstupy a 10 hodnocenými jednotkami: X (vstu] 3y) 3 2,5 4 2,3 4 7 3 5 5 2 5 4,5 6 3,5 6,5 10 5 7 7 4 Y (výstupy) 40 45 55 28 48 80 45 70 45 45 55 50 45 50 20 65 64 65 65 40 30 40 30 25 65 57 42 48 40 44 Najděte všechny efektivní jednotky, uvažujete - li a) CCR model orientovaný na vstupy b) CCR model orientovaný na výstupy c) BCC model orientovaný na vstupy d) BCC model orientovaný na výstupy Najděte pro 3. jednotku referenční efektivní jednotky, uvažujete-li a) CCR model orientovaný na vstupy b) BCC model orientovaný na výstupy K výpočtům použijte aplikaci DEA.