Lineární programování – jaro 2015 – 2. termín
1. (15 bodů) V jedné demokratické zemi se blíží prezidentské volby a v současnosti
vládnoucí diktátor si potřebuje zajistit vítězství. Aby se mu podařilo volby věrohodně
zfalšovat, potřebuje získat alespoň 30% hlasů, přičemž v zemi je α voličů
a žádný volič si nedovolí nepřijít k volbám. Mezi voliči má diktátor aktuálně β
příznivců a γ odpůrců; každý ze zbývajících „standardních voličů jej bude volit
s pravděpodobností 50%. Současně se musí diktátor vyhnout nebezpečí revoluce,
která hrozí, pokud zastoupení odpůrců mezi voliči překročí 60%. Diktátor zná dvě
metody, jak zvýšit svoji popularitu: výboje a hledání vnitřního nepřítele; přitom
nejvyšší částka, kterou může za tímto účelem použít, je δ miliónů. Investováním
jednoho miliónu do výbojů dojde k přesunu ε standardních voličů mezi příznivce
a ζ standardních voličů mezi odpůrce, přičemž η standardních voličů zemře na
bojišti. Investováním jednoho miliónu do hledání vnitřního nepřítele dojde k popravě
ϑ příznivců, přičemž ι standardních voličů se stane diktátorovými příznivci
a κ příznivců se přesune mezi odpůrce. Formulujte Farkasovo lemma udávající
nutnou a postačující podmínku k tomu, aby se diktátor nemusel uchýlit k „použití
nedemokratických prostředků . (Jedná se o velkou zemi, takže lze všechny veličiny
považovat za spojité a počet voličů v žádné skupině se nikdy nepřiblíží k nule.)
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 | |x1| ≤ y1, . . . , |xn| ≤ yn, cx = yb, Ax ≥ b, yB ≤ c }
kde x = (x1, . . . , xn)T
a y = (y1, . . . , yn) jsou vektory proměnných, b, c, d jsou
konstantní vektory a A, B jsou matice. Formulujte větu o dualitě pro tuto dvojici
úloh.
3. (25 bodů) Definujte stěny polyedru. Charakterizujte maximální stěny polyedrů
algebraicky pomocí systémů nerovnic a tuto charakterizaci dokažte. Uveďte, jak
je možné pomocí lineárního programování určit, zda je nerovnice implicitní rovnicí.
Dejte příklad polyedru dimenze 3, jehož všechny vlastní stěny jsou současně
maximální i minimální.
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 ≤ −11,
2x − 2y + 3z + 4t ≥ −29,
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 1 ≥ z, duální metodou.