Lineární programování – jaro 2011 – 2. termín
1. (15 bodů) Formulujte variantu Farkasova lemmatu udávající nutnou a postačující
podmínku k tomu, aby soustava lineárních rovnic
A · (x1, . . . , xn)T
+ B · (y1, . . . , yn)T
= C · (x1, . . . , xn)T
+ d
v proměnných x1, . . . , xn, y1, . . . , yn měla řešení splňující buď
∀ i = 1, . . . , n: xi ≤ yi
nebo
∀ i = 1, . . . , n: yi ≤ xi.
2. (20 bodů) Určete funkci f vektoru proměnných z, matici F a vektor h takové,
že úloha lineárního programování
max { f | zF ≥ h, z ≤ 0 }
je duální k úloze
min { cx | Ax = Bx, Cx ≤ b, |dx| ≤ 1 }.
Formulujte větu o dualitě pro tuto dvojici úloh.
(|dx| značí absolutní hodnotu dx.)
3. (25 bodů) Definujte stěny polyedru. Charakterizujte maximální stěny polyedrů
algebraicky pomocí systémů nerovnic a tuto charakterizaci dokažte. Dejte příklad
polyedru dimenze 2, jehož maximálními stěnami jsou právě jeho minimální stěny.
4. (30 bodů) Duální simplexovou metodou nalezněte nějakou přípustnou simplexovou
tabulku pro úlohu lineárního programování
minimalizovat 6x − 3y − 2z
při omezeních x ≥ 0, y ≥ 0, z ≥ 0 a
−x + y + 2z ≤ −1,
2x − y + 2z ≥ 8,
2x + y − 2z ≥ 6
a úlohu poté vyřešte primární simplexovou metodou.