Lineární programování – jaro 2018 – 3. termín
1. (15 bodů) Z n látek, které se na sebe vzájemně samovolně přeměňují, potřebujeme
vytvořit směs, která bude mít stále stejné složení. Cena jednoho gramu i-té látky je
ci Kč, přičemž jí můžeme zakoupit nejvýše ai gramů, pro i = 1, . . . , n. Jeden gram
i-té látky se během jedné sekundy přemění na směs obsahující právě bi,j g j-té
látky, pro j = 1, . . . , n. Formulujte Farkasovo lemma udávající nutnou a postačující
podmínku na čísla ai, bi,j, ci a γ, aby bylo možné nakoupit 1 kg stabilní směsi za
cenu nejvýše γ Kč.
2. (20 bodů) Určete funkci f vektoru proměnných z, matici B a vektor a takové,
že úloha lineárního programování
min { f | Bz + a ≥ 0 }
je duální k úloze
max { x1 + · · · + xm | x1 ≥ y · d1, . . . , xm ≥ y · dm, Ax = b, y1 ≤ y2 ≤ · · · ≤ yn },
kde x = (x1, . . . , xm)T
a y = (y1, . . . , yn) jsou vektory proměnných, b, d1, . . . , dm
konstantní vektory a A matice. Formulujte větu o dualitě pro tuto dvojici úloh.
3. (25 bodů) Formulujte větu o rozkladu polyedrů a definujte v ní použité pojmy.
V souladu s touto větou rozložte polyedr
P = { (x, y, z) ∈ R3
| 0 ≤ x ≤ 1 },
a to tak, aby všechny útvary použité v rozkladu měly stejnou dimenzi; přitom tyto
útvary zadejte v souladu s příslušnými definicemi. Dokažte, že pro každý polyedr
rozklad uvedený ve větě existuje.
4. (30 bodů) Vytvořte simplexovou tabulku odpovídající bazické množině indexů
{3, 1, 2} (v tomto pořadí) pro úlohu lineárního programování maximalizovat
x1 − x2 − x3 − 2x4 + 2x5
při omezeních (x1, x2, x3, x4, x5) ≥ 0 a
2x1 + x2 + 3 = x3 + x4 + 2x5,
x1 + 2x4 + 5 = x3 + 2x5,
x2 + 2x3 + x4 = 13
a s touto počáteční tabulkou vyřešte úlohu primární simplexovou metodou. Po
jejím vyřešení přidejte další omezení
x4 + 1 ≥ x1 + 2x2 + 3x3
a úlohu dořešte duální simplexovou metodou.