Lineární programování – jaro 2011 – 1. termín
1. (15 bodů) Formulujte Farkasovo lemma udávající nutnou a postačující podmínku
k tomu, aby soustava lineárních rovnic
A · (x1, . . . , xm)T
= B · (y1, . . . , yn)T
+ c
v proměnných x1, . . . , xm, y1, . . . , yn měla řešení splňující
yj ≥ 0, pro všechna j = 1, . . . , n,
a
|xi| ≤ y1 + · · · + yn, pro všechna i = 1, . . . , m.
(|xi| značí absolutní hodnotu xi.)
2. (20 bodů) Určete funkci f vektoru proměnných z, matici F a vektor d takové,
že úloha lineárního programování
max { f | zF = d, z ≥ 1 }
je duální k úloze
min { cx | Ax = Bx, Cx ≤ b, x ≤ 1 }.
Formulujte větu o dualitě pro tuto dvojici úloh.
(1 značí vektor (1, . . . , 1)T
)
3. (25 bodů) Definujte stěny polyedru. Formulujte větu charakterizující minimální
stěny algebraicky pomocí systémů nerovnic. Určete dimenzi minimálních stěn polyedru
P = { x | Ax = b, x ≥ 0 } a svoje tvrzení zdůvodněte. Formulujte a dokažte
charakterizaci minimálních stěn polyedru P, na níž je založena simplexová metoda.
(K důkazu můžete použít dříve formulovanou obecnou větu.)
4. (30 bodů) Vyřešte primární simplexovou metodou úlohu lineárního programování
minimalizovat x1−x2−9x3+x4
při omezeních x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 a
x1 − 2x2 ≥ −20,
2x1 + x3 ≤ 4,
2x3 − x4 ≤ 6,
x2 + x3 + 2x4 ≤ 9.
Poté využijte získanou simplexovou tabulku k vyřešení úlohy, která vznikne z původní
úlohy nahrazením čísla 9 na pravé straně poslední nerovnice číslem 6.