Lineární programování – jaro 2012 – 1. termín
1. (15 bodů) Formulujte Farkasovo lemma udávající nutnou a postačující podmínku
k tomu, aby součet P + Q polyedrů
P = { x ∈ Rn
| Ax ≤ b } a { x ∈ Rn
| Bx = c, x ≥ 0 }
obsahoval nulový vektor.
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 | yA = p, Bx = 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ů) Definujte stěny polyedru P = { y | yA ≥ c }. Formulujte větu charakterizující
minimální stěny tohoto polyedru algebraicky pomocí systémů nerovnic.
Uveďte nutnou a postačující podmínku k tomu, aby byly minimálními stěnami
tohoto polyedru vrcholy. Formulujte a dokažte charakterizaci vrcholů polyedru P,
na níž je založena duální simplexová metoda. (K důkazu můžete použít dříve
formulovanou obecnou větu.) Vysvětlete, jak souvisí tato charakterizace s údaji
v simplexové tabulce.
4. (30 bodů) Vytvořte simplexovou tabulku odpovídající bazické množině indexů
{3, 1} (v tomto pořadí) pro úlohu lineárního programování minimalizovat
x2 + x3 + 2x4
při omezeních (x1, x2, x3, x4, x5) ≥ 0 a
x1 − x2 − x3 + 2x4 − 2x5 = −7,
2x1 + x2 − x3 − x4 − x5 = −2
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í
2x1 − 2x3 − x4 − x5 ≥ −1
a úlohu dořešte duální simplexovou metodou.