Lineární programování – jaro 2013 – 3. termín
1. (15 bodů) Formulujte Farkasovo lemma udávající nutnou a postačující podmínku
na reálná čísla a, b, c, d, e, g, h, k, ℓ, m, n, aby polyedr
P = { (x, y) ∈ R2
| ax + by ≤ c, dx + ey ≤ g }
obsahoval bod, který se na obou složkách dohromady neliší o více než o 2 od
nějakého bodu polyedru
Q = { (x, y) ∈ R2
| hx + ky ≤ 0, ℓx + my ≥ n }.
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 | x ≤ yT
≤ 0, cx ≤ yb, yA + d ≥ c },
kde x a y jsou vektory proměnných stejné dimenze, b, c, d jsou konstantní vektory
a A je matice. Formulujte větu o dualitě pro tuto dvojici úloh.
3. (25 bodů) Definujte stěny obecného 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, y) | xA ≤ y, x ∈ Rm
, y ∈ Rn
} a svoje
tvrzení zdůvodněte. Formulujte a dokažte charakterizaci minimálních stěn jistého
polyedru, na níž je založena primární 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 − 2y − z
při stejných omezeních x ≥ 0, y ≥ 0, z ≥ 0 a
4x − y − 2z ≥ −1,
x − 2y − z ≤ −2,
y − 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.