Lineární programování – jaro 2017 – 1. termín
1. (15 bodů) Nechť ϕ: Rm
→ Rn
je afinní zobrazení prostorů řádkových vektorů
definované předpisem ϕ(x) = xA + u. Nechť dále C je konvexní kužel generovaný
vektory v1, . . . , vk ∈ Rm
a nechť α je kladné reálné číslo. Formulujte Farkasovo
lemma udávající nutnou a postačující podmínku na matici A, vektory u, v1, . . . ,
vk a číslo α, aby existoval v kuželu C bod takový, že se každá složka jeho ϕ-obrazu
liší od 1 nejvýše o hodnotu α.
2. (20 bodů) Určete funkci f vektoru proměnných z, matici F a vektor a takové,
že úloha lineárního programování
max { f | zF = a, z ≤ 1 }
je duální k úloze
min { cx | (y + 1)A = p, Bx ≥ q, yb ≤ dx }.
Formulujte větu o dualitě pro tuto dvojici úloh.
(x je sloupcový vektor proměnných; y je řádkový vektor proměnných; A a B jsou
matice; b, c, d, p a q jsou vektory; 1 značí vektor (1, . . . , 1))
3. (25 bodů) Definujte dimenzi polyedru. Charakterizujte maximální stěny polyedrů
algebraicky pomocí systémů nerovnic a tuto charakterizaci dokažte. Uveďte, jak je
možné pomocí lineárního programování určit, zda je nerovnice v systému nadbytečná.
Dejte příklad systému nerovnic zadávajícího polyedr v prostoru dimenze 3,
který má jedinou maximální stěnu dimenze 1.
4. (30 bodů) Vytvořte simplexovou tabulku odpovídající bazické množině indexů
{3, 1, 2} (v tomto pořadí) pro úlohu lineárního programování maximalizovat
x1 − x2 − x3 − 2x4 + 2x5
při omezeních (x1, x2, x3, x4, x5) ≥ 0 a
2x1 + x2 + 3 = x3 + x4 + 2x5,
x1 + 2x4 + 5 = x3 + 2x5,
x2 + 2x3 + x4 = 13
a s touto počáteční tabulkou vyřešte úlohu primární simplexovou metodou. Po
jejím vyřešení přidejte další omezení
x4 + 1 ≥ x1 + 2x2 + 3x3
a úlohu dořešte duální simplexovou metodou.