Lineární programování – jaro 2012 – 3. termín
1. (15 bodů) V našem dole se těží n různě kvalitních rud, které dodáváme zpracovateli.
Vytěžení jednotkového množství i-té rudy vyžaduje využití ai procent měsíční
výrobní kapacity dolu. Z jednotkového množství i-té rudy zpracovatel získá bi tun
kovu, přičemž zpracovatel nemá zájem za měsíc vyprodukovat více než b tun kovu.
Provoz dolu stojí měsíčně c korun, přičemž vytěžení jednotkového množství i-té
rudy nás navíc stojí ci korun. Zpracovatel nám za jednotkové množství i-té rudy
zaplatí di korun. Formulujte Farkasovo lemma udávající nutnou a postačující podmínku
na čísla ai, bi, b, c, ci a di (pro i ∈ {1, . . . , n}), abychom byli schopni v našem
dole provozovat neztrátovou těžbu.
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 ≤ 0 }
je duální k úloze
max { c · (x + y) | (x2
1, . . . , x2
n) ≤ b, by ≥ α, By ≤ Ax },
kde x = (x1, . . . , xn)T
a y jsou vektory proměnných stejné dimenze, b ≥ 0 a c jsou
konstantní vektory, A a B matice a α číslo. Formulujte větu o dualitě pro tuto
dvojici úloh.
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. Zadejte systémem nerovnic množinu
Q + C ⊆ R2
, kde
Q = { (x, y) | x + y ≤ 1, y − x ≤ 1, y ≥ 0 } a
C = { (x, y) | x + y = 0 }.
4. (30 bodů) (Zadání čtěte velmi pozorně!) Řešte primární simplexovou metodou
úlohu minimalizovat
3x + y + z
při omezeních y ≥ 0, z ≥ 0 a
2x − y + z ≤ 5,
x − 2y + z ≥ 2.
Po jejím vyřešení přidejte další omezení
x + y + 2z ≤ 4
a využijte závěrečnou simplexovou tabulku k dořešení úlohy primární simplexovou
metodou. Konečně, po jejím vyřešení přidejte další omezení
x − 2y + 2z ≤ 3
a úlohu dořešte duální simplexovou metodou.