2. seminář:
Lineární a celočíselné programování, řešení pomocí MS Excel Solver, postoptimalizační analýza
Příklad 1: Řešení úloh z příkladu 1 minulého cvičení 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, které je možné pro další práci uložit na disk H. Po otevření souboru v Excelu spustíte Řešitel na roletce 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 2: Pomocí Řešitele nalezněte optimální řešení úlohy z minulého cvičení: z = 36xi + 12^2 + 60^3 —> max. za podmínek
2x\ + X2 + 3^3 < 9 x\ +  3x3 < 3
Xu x2, xs > 0 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í.
Příklad 3: 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 nej menší 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 4: Aplikujte ručně metodu větví a mezí na následující modifikaci úlohy o batohu (použijte bivalentní proměnné a relaxace dílčích podúloh řešte bez pomoci simplexové metody):
Máme k dispozici sklad o celkové skladovací ploše 8400m2. O pronájem skladu má zájem 5 zájemců s různými požadavky na skladovou plochu a různými nabídkami za pronájem této plochy. Požadavky musí být splněny buď v plné výši nebo vůbec. V tabulce jsou uvedeny požadavky na plochu Pí a ceny za pronájem uvedené plochy q od každého zájemce i = 1,..., 5.
i	1	2	3	4	5
Pl[m2}	5000	1600	2800	6200	2200
ct[Kč}	39000	9000	33000	63000	18000
Rozhodněte, kterým zájemcům poskytneme skladovací plochu, aby příjem z pronájmu byl co nejvyšší.