Lineární programování – jaro 2013 – 4. termín
1. (15 bodů) Nechť ϕ: Qm
→ Qk
a ψ: Qn
→ Qk
jsou lineární zobrazení definovaná
předpisy ϕ(x) = xA a ψ(x) = xB. Uvažme následující polyedry:
P = { x ∈ Qm
| xC = b, x ≤ 0 },
Q = { x ∈ Qn
| xD ≤ c },
R = { x ∈ Qk
| xF ≥ 0 }.
Formulujte Farkasovo lemma udávající nutnou a postačující podmínku na matice
A, B, C, D, F a vektory b, c, aby polyedry ϕ(P), ψ(Q) a R měly společný bod.
2. (20 bodů) Určete funkci f vektoru proměnných z, matici B a vektor a takové,
že úloha lineárního programování
min { f | Bz + a ≥ 0 }
je duální k úloze
max { x1 + · · · + xm | x1 ≥ y · d1, . . . , xm ≥ y · dm, Ax = b, y1 ≤ y2 ≤ · · · ≤ yn },
kde x = (x1, . . . , xm)T
a y = (y1, . . . , yn) jsou vektory proměnných, b, d1, . . . , dm
konstantní vektory a A matice. 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.
Předveďte rozklad uvedený v této větě na polyedru
P = { (x, y, z) ∈ R3
| 0 ≤ x ≤ 1 };
přitom útvary, na které polyedr rozkládáte, zadejte v souladu s příslušnými definicemi.
Dokažte implikaci uvedené věty, která tvrdí, že rozklad existuje.
4. (30 bodů) (Zadání čtěte velmi pozorně!) Řešte primární simplexovou metodou
úlohu minimalizovat
x + 3y + z
při omezeních x ≥ 0, z ≥ 0 a
x − 2y − z ≥ −7,
x − y − z ≤ −2.
Po jejím vyřešení přidejte další omezení
2x − 2y − 3z ≥ −7
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 − 3z ≥ −5
a úlohu dořešte duální simplexovou metodou.