Lineární programování – jaro 2010 – 3. termín
1. (15 bodů) Formulujte Farkasovo lemma udávající nutnou a postačující podmínku
k tomu, aby soustava Ax = b, Cy ≤ d v proměnných x = (x1, . . . , xn)T
a y =
(y1, . . . , yn)T
měla řešení splňující x ≥ y.
2. (20 bodů) Určete funkci f vektoru proměnných x, matici B a vektor d takové,
že úloha lineárního programování
max { f | Bx ≥ d }
je duální k úloze
min { yc | yA ≥ b, y ≤ 1 }.
Formulujte větu o dualitě pro tuto dvojici úloh.
3. (25 bodů) Definujte polyedry, jejich stěny a maximální stěny. Charakterizujte
maximální stěny polyedrů pomocí systémů nerovnic a tuto charakterizaci dokažte.
4. (30 bodů) Řešte primární simplexovou metodou úlohu minimalizovat
10x − y + 15z
při omezeních x ≥ 0, y ≥ 0, z ≥ 0 a
x − 3y + 7z ≤ 8,
2x − y + 4z ≥ 6,
3x − 2y + z ≥ 7.
Po jejím vyřešení přidejte další omezení
2x − y + 14z ≤ 1
a úlohu dořešte duální simplexovou metodou.