Lineární programování – jaro 2014 – 2. termín
1. (15 bodů) Formulujte Farkasovo lemma udávající nutnou a postačující podmínku
na matici A, vektory a a b a číslo α, aby existoval v polyedru
{ x ∈ Rm
| xA ≤ a, α · x ≥ b }
bod, jehož žádné dvě složky se od sebe neliší o více než o 1.
2. (20 bodů) Určete funkci f vektoru proměnných z, matici F a vektor a takové,
že úloha lineárního programování
max { f | zF = a, z ≥ 1 }
je duální k úloze
min { cx | yA = p, Bx ≥ q, |yb| ≤ dx }.
Formulujte větu o dualitě pro tuto dvojici úloh.
(x je sloupcový vektor proměnných; y je řádkový vektor proměnných; A a B jsou
matice; b, c, d, p a q jsou vektory; 1 značí vektor (1, . . . , 1))
3. (25 bodů) Definujte polyedry, polytopy a konečně generované konvexní kužely.
Popište konstrukci, která z polytopů a konečně generovaných konvexních kuželů
vytvoří právě všechny polyedry. Dokažte, že každý polyedr je opravdu možné
touto konstrukcí získat. Uveďte charakterizaci těch polyedrů, které lze touto konstrukcí
získat jediným způsobem. Popište polyedr vytvořený z polytopu generovaného
množinou {(−1, 0), (1, 0)} a konvexního kužele generovaného množinou
{(−1, −1), (1, 1)} v souladu s definicí polyedru.
4. (30 bodů) Vyřešte primární simplexovou metodou úlohu lineárního programování
minimalizovat 2x + y − 10z − t
při omezeních x ≥ 0, y ≥ 0, 8 ≥ z ≥ 0, t ≥ 0 a
x − y + 2z + 2t ≤ −4,
2x − 2y + 3z + 4t ≥ −15,
x − 2z − t ≥ −6.
Poté využijte závěrečnou simplexovou tabulku k vyřešení úlohy, která vznikne
z původní úlohy nahrazením podmínky 8 ≥ z podmínkou 2 ≥ z, duální metodou.