Lineární programování – jaro 2010 – 1. termín
1. (15 bodů) Formulujte Farkasovo lemma udávající nutnou a postačující podmínku
k tomu, aby soustava m nerovnic
A · (x1, . . . , xn)T
≤ b
měla řešení splňující x1 ≤ x2 ≤ · · · ≤ xn.
2. (20 bodů) Formulujte větu o dualitě pro úlohu lineárního programování
min { dx | Ax ≤ b, Bx = c }.
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ů) Řešte primární simplexovou metodou úlohu minimalizovat
9x1 − 7x2 − x3
při omezeních x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 a
2x1 + x2 ≤ 7,
2x1 − x2 − x3 ≥ 5,
x1 + 2x2 − 2x3 ≥ 4.
Po jejím vyřešení přidejte další omezení
2x1 − 2x2 ≥ 5
a úlohu dořešte duální simplexovou metodou.