Lineární programování – jaro 2016 – 2. termín
1. (15 bodů) Formulujte Farkasovo lemma udávající nutnou a postačující podmínku
na řádkové vektory a1
, . . . , ak
, b1
, . . . , bℓ
∈ Rn
, aby polytop generovaný
body a1
, . . . , ak
měl neprázdný průnik s konvexním kuželem generovaným vektory
b1
, . . . , bℓ
.
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 polyedru a jejich dimenzi. Popište všechny polyedry,
jejichž minimálními stěnami jsou právě maximální stěny. 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 obecnou větu charakterizující minimální
stěny polyedrů. Dejte příklad úlohy lineárního programování ve tvaru, na který se
přímo aplikuje primární simplexová metoda, a nějakého jejího optimálního řešení,
které při použití této metody nikdy neobdržíme.
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.