Lineární programování – jaro 2012 – 4. termín
1. (15 bodů) Nechť ϕ, ψ: Rn
→ Rm
jsou lineární zobrazení definovaná předpisy
ϕ(x) = A · x a ψ(x) = B · x. Nechť dále P = { x ∈ Rn
| Cx ≤ d } je polyedr.
Formulujte Farkasovo lemma udávající nutnou a postačující podmínku k tomu,
aby existoval bod polyedru P, jehož obrazy v zobrazeních ϕ a ψ se na žádné
složce neliší o více než o 1.
2. (20 bodů) Určete funkci f vektoru proměnných z, matici C a vektor a takové,
že úloha lineárního programování
min { f | Cz = a, z ≤ 1 }
je duální k úloze
max { dx | |x1| ≤ |y1|, . . . , |xn| ≤ |yn|, cx = yb, y ≤ 0, Ax ≥ b, yB + d ≤ c }
kde x = (x1, . . . , xn)T
a y = (y1, . . . , yn) jsou vektory proměnných, b, c, d jsou
konstantní vektory a A, B jsou matice. Formulujte větu o dualitě pro tuto dvojici
úloh.
3. (25 bodů) Definujte stěny polyedru a jejich dimenzi. 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ů) Mějme dvě úlohy lineárního programování:
minimalizovat 3x − y + z
maximalizovat −2x − y − z
při stejných omezeních x ≥ 0, y ≥ 0, z ≥ 0 a
4x − y − 2z ≥ −5,
x − 2y − z ≤ −2,
x + 2y − 2z ≥ 3.
Vyřešte jednu z těchto úloh duální simplexovou metodou a poté využijte získanou
závěrečnou simplexovou tabulku k dořešení druhé úlohy primární simplexovou
metodou.