Lineární programování – jaro 2010 – 4. termín
1. (15 bodů) Formulujte Farkasovo lemma udávající nutnou a postačující podmínku
k tomu, aby polyedry { x ∈ Rn
| Ax ≥ b } a { x ∈ Rn
| Bx = c, x ≤ 0 } měly
neprázdný průnik.
2. (20 bodů) Určete funkci f vektoru proměnných z, matici D a vektor k takové,
že úloha lineárního programování
max { f | zD = k, z ≥ 0 }
je duální k úloze
min { hx | A(x + y) = b, Cx ≥ d, Fy ≤ g }
s vektory proměnných x a y stejné dimenze. Formulujte větu o dualitě pro tuto
dvojici úloh.
3. (25 bodů) Formulujte větu o rozkladu polyedrů a definujte v ní použité pojmy.
Dokažte libovolnou ze dvou implikací této věty.
4. (30 bodů) Mějme dvě úlohy lineárního programování:
maximalizovat x − 3y + 2z
minimalizovat 5x + y + z
při stejných omezeních x ≥ 0, y ≥ 0, z ≥ 0 a
2x − y + 2z ≤ 9,
2x − 2y + z ≥ 2,
x + y − z ≥ 3.
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.