Lineární programování – jaro 2010 – 2. termín
1. (15 bodů) Formulujte Farkasovo lemma udávající nutnou a postačující podmínku
k tomu, aby soustava Ax = By v proměnných x = (x1, . . . , xn)T
a y =
(y1, . . . , ym)T
měla řešení splňující x1 ≥ 1, . . . , xn ≥ 1.
2. (20 bodů) Určete funkci f vektoru proměnných y, matici B a vektor d takové,
že úloha lineárního programování
min { f | yB = d, y ≥ 0 }
je duální k úloze
max { cx | Ax = b, x ≥ 0 }.
Formulujte větu o dualitě pro tuto dvojici úloh.
3. (25 bodů) Definujte polyedry a jejich stěny. Charakterizujte stěny polyedrů algebraicky
pomocí systémů nerovnic a tuto charakterizaci dokažte.
4. (30 bodů) Mějme dvě úlohy lineárního programování:
minimalizovat 8x1 − 3x2 + 2x3
maximalizovat −2x1 − x2 − 3x3
při stejných omezeních x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 a
x1 − 6x2 + 2x3 ≥ 5,
x1 − x2 + x3 ≥ 4,
x1 + 4x2 − x3 ≤ 1.
Vyřešte jednu z těchto úloh duální simplexovou metodou a poté využijte získanou
simplexovou tabulku k dořešení druhé úlohy primární simplexovou metodou.