Lineární programování – jaro 2016 – 1. termín
1. (15 bodů) V továrně na výrobu známek jsou všechny stroje si, pro i = 1, . . . , n,
chlazeny vodou přitékající do továrny přes stroj s1 a odtékající z továrny přes
stroj sn, přičemž množství přitékající a odtékající vody není omezeno a ze stroje
si do stroje sj vede jednosměrné potrubí o maximálním možném průtoku bij l/s,
pro všechna i, j = 1, . . . , n. Formulujte Farkasovo lemma udávající nutnou a postačující
podmínku k tomu, aby bylo možno zajistit průtok vody továrnou takový,
že strojem si protéká alespoň ai l/s, pro i = 1, . . . , n. (Pokud některé potrubí
neexistuje, zvolili jsme příslušné bij rovné nule; například bii = 0 pro všechna i.)
2. (20 bodů) Určete funkci f vektoru proměnných z, matici F a vektor a takové,
že úloha lineárního programování
max { f | zF ≤ a, z ≤ 1 }
je duální k úloze
min { cx | (y + 1)A = p, xT
B ≥ q, yb ≤ dx }.
Formulujte větu o dualitě pro tuto dvojici úloh.
(x je sloupcový vektor proměnných; y je řádkový vektor proměnných; A a B jsou
matice; b, c, d, p a q jsou vektory; 1 značí vektor (1, . . . , 1))
3. (25 bodů) Formulujte větu o rozkladu polyedrů na polytopy a kužely a definujte
všechny ve větě použité pojmy. Dokažte, že pro každý polyedr je příslušný kužel
určen jednoznačně. Dejte příklad polyedru dimenze tři takového, že není sám kuželem
a že mezi polytopy, které lze použít k jeho rozkladu, neexistuje nejmenší
vzhledem k inkluzi.
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.