6. seminář: Optimalizace s omezením ve tvaru nerovností, lineární programování
Příklad 1: Dokončení úloh z minulého cvičení
Příklad 2: Použitím grafické metody řešte problém lineárního programování:
a) max 3x± + 4x2 s podmínkami       |       ^ ^2   ~   ^ x\ > 0, X2 > 0
b) min IOmi + 27w2 s podmínkami       < "   ^        u\ > 0, uo > 0
Příklad 3: Použitím grafické metody řešte problém lineárního programování:
-2xi + 3x2   < 6
a) max 1x\ + 5x2 s podmínkami       ^     7rri — 2x2   <   14        rci > 0, x2 > 0
X! +   x2   < 5
rri + 2rr2   < 8
b) max 8xi + 9x2 s podmínkami       ^  2rri + 3x2   <   13        x\ > 0, x2 > 0
rci +   :r2   < 6
c) max   — 2xi + x2 s podmínkami      0 < rci — 3x2 < 3, rri > 2, rri > 0, rc2 > 0
Příklad 4: Uvažujme množinu A všech [xi,x2] splňujících
-2:ci + ^2 < 2,       rri + 2x2 < 8,       xx > 0,    x2 > 0
Řešte následující problémy s přípustnou množinou A:
a)   max x2 b)   max rri c)   max 3x± + 2x2
d)   max x\ — 2x2 e)   max 2x\ + 4x2 f)   max — 3x\ — 2x2
Příklad 5: Existuje řešení následujícího problému?
max X\ + x2 s podmínkami       |        + ^2   _     1 ^i > 0, x2 > 0
?
Existuje řešení pro účelovou funkci z = —x\ — x2?
Příklad 6: Řešte následující problém graficky
i   ' i     •        i 4x + 5y   < 20 max 2x + 7y s podmínkami       ' 3x + 7y   <   21 X ^
a) Zapište duální problém a vyřešte ho graficky.
b) Jsou si hodnoty účelových funkcí rovny?
Příklad 7: Firma vyrábí malé a střední televizní sady. Zisk z malé sady je 400 a zisk ze střední sady je 500. Každý televizor při výrobě projde třemi divizemi. Každý malý televizor je při výrobě 2 hodiny v první oddělení, 1 hodinu v druhém oddělení a 1 hodinu ve třetím oddělení. Pro střední televizní sadu jsou tyto časy 1, 4 a 2, při zachovaném pořadí oddělení. Předpokládejme, že první dvě oddělení mají kapacitu nejvýše 16 hodin denně a třetí oddělení jen 11 hodin denně. Označme X\ malé televizní sady a x2 střední televizní sady, které jsou produkovány za den.
a) Ukažte, že pro maximální zisk musí firma řešit následující problém:
( 2xl +  x2   < 16
max 400:r1+500:r2 s podmínkami       <    x\ + Ax2   <   16 X\ > 0, x2 > 0
{    x1 + 2x2   < 11
b) Řešte problém graficky.
c) V případě, že by firma mohla zvýšit svoji kapacitu o jednu hodinu denně v jednom ze tří oddělení, ve kterém by to mělo být?
Příklad 8: Firma vyrábí dva výrobky A a B. firma vydělává 300 za jednu jednotku výrobku A a 200 za jednu jednotku výrobku B. Existují tři fáze výrobního procesu. Výrobek A prochází 6 hodin procesem přípravy, 4 hodiny výrobním procesem a 5 hodin balícím procesem. Výrobek B prochází 3 hodin procesem přípravy, 6 hodiny výrobním procesem a 5 hodin balícím procesem. Firma má na výrobu k dispozici celkem 54 hodin v první fázi, 48 ve druhé a 50 ve třetí fázi.
a) Formulujte a řešte problém lineárního programování pro maximalizaci zisku, který je omezen danými limity.
b) Zapište duální problém.
Příklad 9: Řešte problém lineárního programování:
x + y < 4
max x + 2y s podmínkami       <{  — x + y < 1 x > 0, y > 0.
2x-y < 3
Zapište také duální problém.