Lineární programování – jaro 2012 – 2. termín
1. (15 bodů) Nechť ϕ: Rn
→ Rm
je injektivní lineární zobrazení definované předpisem
ϕ(x) = A · x. Nechť dále v1, . . . , vk jsou vektory v Rm
. Formulujte Farkasovo
lemma udávající nutnou a postačující podmínku k tomu, aby existoval vektor
x ∈ Rn
takový, že x ≥ (1, . . . , 1)T
a vektor ϕ(x) svírá neostrý úhel se všemi
vektory konvexního kužele generovaného vektory v1, . . . , vk.
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ů) Definujte stěny polyedru. Charakterizujte polyedry, které nemají žádné
maximální stěny. Charakterizujte minimální stěny polyedrů pomocí systémů nerovnic
a tuto charakterizaci dokažte. Dejte příklad polyedru, jehož každá maximální
stěna obsahuje právě tři minimální stěny.
4. (30 bodů) Řešte primární simplexovou metodou úlohu minimalizovat
10x − y + 15z
při omezeních x ≥ 0, y ≥ 0, z ≥ 0 a
2x − y + 4z ≥ 6,
3x − 2y + z ≥ 7.
Po jejím vyřešení přidejte další dvě omezení
x + y + z ≤ 5,
x − y + 7z ≤ 4
a úlohu dořešte duální simplexovou metodou.