Lineární programování – jaro 2017 – 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 konstruktivní návrhy a strašení
hrozbami. Zbytek programu bude tvořen nicneříkajícími frázemi. Potenciální voliči
strany jsou v současnosti rozloženi následovně: α z nich by volilo naši stranu, β
jinou stranu a γ se nehodlá voleb zúčastnit. Pokud i-tá kapitola programu (pro
i = 1, . . . , n) bude obsahovat x procent konstruktivních návrhů, aix voličů, kteří
by nešli k volbám, bude volit naši stranu, ale bix voličů, kteří by hlasovali pro
naši stranu, bude volit stranu jinou. Bude-li i-tá kapitola z x procent složena ze
strašení, bude naši stranu volit cix voličů, kteří by volili stranu jinou, ale dix voličů,
kteří plánovali hlasovat pro naši stranu, k volbám nepřijde. 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:
• Mezi našimi potenciálními voliči, kteří přijdou k volbám, získáme alespoň 70
procent hlasů.
• V každé kapitole programu je nejvýše 50 procent nicneříkajících frází.
• V jednotlivých kapitolách programu zabírá strašení v průměru nejvýše 10
procent.
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 | x ≤ yT
≤ 0, cx ≤ yb, yA = yB },
kde x a y jsou vektory proměnných stejné dimenze, b, c, d jsou konstantní vektory
a A a B jsou matice. Formulujte větu o dualitě pro tuto dvojici úloh.
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 a že každý jeho vrchol musí být současně i vrcholem příslušného
polytopu. Popište příslušný polytop a kužel pro polyedr { (x, y, z) ∈ R3
|
0 ≤ x − y ≤ 1 }.
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.