Lineární programování – jaro 2014 – 1. termín
1. (15 bodů) Nechť ϕ: Rm
→ Rn
je lineární zobrazení prostorů řádkových vektorů
definované předpisem ϕ(x) = xA. Nechť dále P = { x ∈ Rm
| xB ≤ a } je polyedr a
nechť α je reálné číslo. Formulujte Farkasovo lemma udávající nutnou a postačující
podmínku na matice A a B, vektor a a číslo α, aby existoval v polyedru P bod
takový, že všechny složky jeho ϕ-obrazu se liší od α nejvýše o hodnotu 1.
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, z ≤ 0 }
je duální k úloze
max { x1 + · · · + xm | x ≥ y1 · d, Ax = b, yC ≤ c, y1 ≥ y2 ≥ · · · ≥ yn },
kde x = (x1, . . . , xm)T
a y = (y1, . . . , yn) jsou vektory proměnných, b, c, d konstantní
vektory a A, C matice. Formulujte větu o dualitě pro tuto dvojici úloh.
3. (25 bodů) Formulujte algebraickou charakterizaci stěn polyedru pomocí systémů
nerovnic. Charakterizujte polyedry, které nemají žádné maximální stěny. Charakterizujte
minimální stěny polyedrů pomocí systémů nerovnic a tuto charakterizaci
dokažte. Definujte bodovaný polyedr. Dokažte, že průnik bodovaného polyedru
s libovolným polyedrem, je-li neprázdný, je bodovaný polyedr. Dejte příklad dvou
bodovaných polyedrů takových, že jejich průnik má o dva vrcholy více, než mají
původní polyedry dohromady.
4. (30 bodů) Mějme dvě úlohy lineárního programování:
minimalizovat 3x − y + z
maximalizovat − 2y − z
při stejných omezeních x ≥ 0, y ≥ 0, z ≥ 0 a
4x − y − 2z ≥ −1,
x − 2y − z ≤ −2,
y − 2z ≥ 3.
Vyřešte jednu z těchto úloh duální simplexovou metodou a poté využijte získanou
závěrečnou simplexovou tabulku k dořešení druhé úlohy primární simplexovou
metodou.