Lineární programování – jaro 2011 – 4. termín
1. (15 bodů) Uvažujme lineární izomorfismus ϕ: Rn
→ Rn
definovaný předpisem
ϕ(x) = A · x, kde A je matice typu n × n nad R. Nechť P = { x ∈ Rn
| Bx ≤ c }
je polyedr. Formulujte variantu Farkasova lemmatu udávající nutnou a postačující
podmínku pro to, aby izomorfismus ϕ zobrazil některý bod polyedru P do
polyedru P.
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 ≤ 1 }
je duální k úloze
min { cx | Ax ≤ b, xT
B ≥ d }.
Formulujte větu o dualitě pro tuto dvojici úloh.
(1 značí vektor (1, . . . , 1)T
.)
3. (25 bodů) Definujte polyedry a jejich stěny. Charakterizujte stěny polyedrů algebraicky
pomocí systémů nerovnic a tuto charakterizaci dokažte. Vypište všechny
stěny polyedru
{ (x, y) ∈ R2
| x ≥ 0, y ≥ 0, x + y ≥ 1 }.
4. (30 bodů) Mějme dvě úlohy lineárního programování:
minimalizovat 3x + 2y + z
maximalizovat −x + 2y − 2z
při stejných omezeních x ≥ 0, y ≥ 0, z ≥ 0 a
2x − z ≥ −2,
x − y + z ≥ 3,
x − 2y + z ≤ 0.
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.