7. cvičení z M3110 - lineární programování - simplexová metoda, podzim 2024 Příklad. 1. V IR3 najděte minimum funkce c(x) = —2xx + 3x2 — x3 za podmínky, že ^1,^2,^3 > 0. Řešení. Úlohu min{c(x), Ax < b, x > 0} převedeme na úlohu min{c(x), Ax + Es = b, x > 0 s > 0} s jednotkovou maticí E tvaru 3 x 3 a pomocnými neznámými s1; s2, s3 > 0. Simplexovou metodu začneme proto na vrcholu (xi, x2, x3, si, s2, s3) = (0, 0, 0,10, 3,10). □ Příklad. 2. Simplexovou metodou řešte nalezení minima funkce c(x) = 1x\ + Ax2 + 7x3 + 2x4 + 5rr5 za podmínek, že 'l 1 2 1 2\ /7\ 1 2 3 1 1 -a: = I 6 , x>0. i i i 2 i/ \4y Řešení. Abychom mohli najít vrchol, kde začneme simplexovou metodu, tak hledáme {min(ŕi + t2 + ŕ3); + Et = b, x > 0, t > 0}. □ Příklad. 3. Simplexovou metodou řešte nalezení minima funkce c{x) = 15x2 + 30x3 + 15a:5 za podmínek, že 1 1 0 0 0\ /120\ 10 2 1 0 U> 80 , x>0. 0 1 0 2 3/ \110/ Příklad. 4. Simplexovou metodou nalezněte minimum funkce c(x) = — x\ — x2 za podmínek, že x > 0. Příklad. 5. Firma Defekt vyrábějící jízdní kola chce naplánovat optimální měsíční výrobu. Produkuje tři typy kol: silniční, horská a zimní. Výroba je rozdělená na montáž a testování kvality, přičemž firma má k dispozici 520 hodin provozu montážní linky a 100 hodin testovací laboratoře zajeden měsíc. Pro výrobu silničního kola jsou potřeba 4 hodiny montáže, pro výrobu jednoho horského kola 5 hodin montáže a pro výrobu jednoho zimního kolka 6 hodin montáže. Pro každé kolo je potřeba 1 hodina testování. Firma chce, aby zimní kola tvořila maximálně polovinu měsíční produkce všech kol. Zisk z prodeje jednoho silničního kola je 4000 Kč, z prodeje jednoho horského kola 6000 Kč a z prodeje jednoho zimního kola 7000 Kč. Firma vždy prodá všechna vyrobená kola. i 2 Při jakém počtu vyrobených silničních, horských a zimních kol za jeden měsíc maximalizuje firma svůj zisk? A jaký tento zisk bude? Zformulujte problém jako úlohu lineární optimalizace a úlohu vyřešte. Řešení. Chceme maximalizovat funkci Axi + 6x2 + 7rc3 za podmínek tvaru Ax < b a x > 0. To je totéž jako za stejných podmínek minimalizovat funkci c(x) = —Axi — 6x2 — 7x%. Postupujeme jako v 1. úloze. 4 5 6 1 0 0 520 \ 1 1 1 0 1 0 100 -1 -1 1 0 0 1 0 v -4 -6 -7 0 0 0 0 / / - -1 0 1 1 -5 0 20 \ 1 1 1 0 1 0 100 0 0 2 0 1 1 100 l 2 0 -1 0 6 0 600 J První číslo v záhlaví je kladné, proto x\ = 0. tisíc Kč. / o 1 2 1 -4 0 120 \ 1 1 1 0 1 0 100 0 0 2 0 1 1 100 -2 -3 0 4 0 400 j / -1 0 1 1 -5 0 20 \ 2 1 0 -1 6 0 80 2 0 0 -2 11 1 60 l 1 0 0 1 1 0 620 j Dále odečteme x2 = 80, rc3 = 20. Zisk je 620 □ Příklad. 6. Květinářství odebírá každý týden květiny od dvou stálých dodavatelů Anny a Boba. Pro tento týden má smysl brát nejvýše jednu dodávku od Anny a jednu od Boba. Při jedné dodávce doveze Anna maximálně 50 svazků květin, přičemž nabízí dovoz růží a tulipánů. Také Bob doveze při jedné dodávce nejvýše 50 svazků květin a nabízí rovněž růže a tulipány. Květinářství může uskladnit maximálně 70 svazků růží a 60 svazků tulipánů, vedoucí ví, že prodá všechny dodané květiny. Zisk z jednoho svazku růží od Anny je 60 Kč, z jednoho svazku tulipánů od Anny 80 Kč, z jednoho svazku růží od Boba je 100 Kč a z jednoho svazku tulipánů od Boba 110 Kč. Kolik a jakých svazků má vedoucí pro tento týden objednat, aby maximalizoval svůj zisk? A jaký tento zisk bude? Zformulujte problém jako úlohu lineární optimalizace a pak úlohu vyřešte. Řešení. Maximální zisk je 9100 Kč pro xi = 0, x2 = 50, rc3 = 40 a x4 = 10.. □