Lineární programování – jaro 2016 – 4. termín
1. (15 bodů) Nechť A a B jsou matice typu m×n nad R a b, c ∈ Rm
jsou sloupcové
vektory takové, že množiny P = { x ∈ Rn
| Ax ≤ b } a Q = { x ∈ Rn
| Bx ≤ c }
jsou disjunktní. Nechť dále k ≥ 1 a v1, . . . , vk ∈ Rn
jsou nenulové sloupcové
vektory. Formulujte Farkasovo lemma udávající nutnou a postačující podmínku
k tomu, aby existovaly body y ∈ P a z ∈ Q takové, že přímka, která jimi prochází,
je rovnoběžná s lineárním podprostorem generovaným vektory v1, . . . , vk.
2. (20 bodů) Určete funkci f vektoru proměnných z, matici F a vektor h takové,
že úloha lineárního programování
max { f | zF ≥ h, z ≤ 0 }
je duální k úloze
min { cx | Ax = Bx, Cx ≤ b, |dx| ≤ 1 }.
Formulujte větu o dualitě pro tuto dvojici úloh.
(|dx| značí absolutní hodnotu dx.)
3. (25 bodů) Definujte stěny polyedru. Charakterizujte maximální stěny polyedrů
algebraicky pomocí systémů nerovnic a tuto charakterizaci dokažte. Dejte příklad
matice A a vektoru b takových, že žádné dva řádky A nejsou lineárně závislé
a systém Ax ≤ b obsahuje právě šest nerovnic, přičemž právě tři z nich jsou
implicitními rovnicemi a právě jedna je nadbytečná.
4. (30 bodů) Duální simplexovou metodou nalezněte nějakou přípustnou simplexovou
tabulku pro úlohu lineárního programování
minimalizovat 6x − 3y − 2z
při omezeních x ≥ 0, y ≥ 0, z ≥ 0 a
−x + y + 2z ≤ −1,
2x − y + 2z ≥ 8,
2x + y − 2z ≥ 6
a úlohu poté vyřešte primární simplexovou metodou.