Lineární programování – jaro 2013 – 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 Q = { x ∈ Rn
| Bx = c, x ≥ 0 }
měl neprázdný průnik s P.
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. Charakterizujte polyedry, které nemají žádné
maximální stěny. Charakterizujte minimální stěny polyedrů pomocí systémů nerovnic
a tuto charakterizaci dokažte. Dejte příklad polyedru, který má právě tři
maximální stěny a jehož každá maximální stěna obsahuje právě jednu minimální
stěnu.
4. (30 bodů) Vytvořte simplexovou tabulku odpovídající bazické množině indexů
{4, 1} (v tomto pořadí) pro úlohu lineárního programování minimalizovat
2x1 + 2x4 + x5
při omezeních (x1, x2, x3, x4, x5) ≥ 0 a
x1 + 2x2 − x3 − x4 − x5 = −2,
x1 − x2 + 2x3 − 2x4 + x5 = 5
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í
x1 + x2 + x3 − x4 + x5 ≤ 2
a úlohu dořešte duální simplexovou metodou.