Lineární programování – jaro 2013 – 2. termín
1. (15 bodů) Máme za úkol vytvořit volební program politické strany, který sestává
z n kapitol. Do každé kapitoly můžeme napsat reformní plány a populistická
hesla. Zbytek programu bude tvořen nicneříkajícími frázemi. Pokud i-tá kapitola
(pro i = 1, . . . , n) bude obsahovat x procent reformních plánů, ztratíme aix milionů
hlasů voličů, ale získáme bix milionů nových kmenových voličů. Bude-li i-tá
kapitola obsahovat x procent populistických hesel, získáme cix milionů hlasů, ale
ztratíme dix milionů kmenových voličů. Formulujte Farkasovo lemma udávající
nutnou a postačující podmínku na čísla ai, bi, ci, di, abychom mohli vytvořit program
splňující současně následující podmínky:
• Přibude nám alespoň milion hlasů.
• Nesníží se nám počet kmenových voličů.
• V jednotlivých kapitolách programu je v průměru nejvýše 50 procent nicneříkajících
frází.
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ů) Formulujte větu o rozkladu polyedrů a definujte v ní použité pojmy.
Dokažte libovolnou ze dvou implikací této věty. Předveďte rozklad uvedený v této
větě na polyedru
{ (x, y) ∈ R2
| x ≥ 0, y ≥ 0, x + y ≥ 1, x − y ≤ 2, y − x ≤ 2 }.
Přitom útvary, na které polyedr rozkládáte, zadejte v souladu s příslušnými defi-
nicemi.
4. (30 bodů) Vyřešte primární simplexovou metodou úlohu lineárního programování
minimalizovat 2x + y + z − 9t
při omezeních x ≥ 0, y ≥ 0, z ≥ 0, t ≥ 0 a
x − y − 2z ≤ −20,
2x − 2y − 4z − t ≥ −47,
x − 2t ≥ −6,
z + t ≤ 8.
Poté využijte závěrečnou simplexovou tabulku k vyřešení úlohy, která vznikne
z původní úlohy nahrazením čísla 8 na pravé straně poslední nerovnice číslem 5,
duální metodou.