Lineární programování – jaro 2015 – 3. termín
1. (15 bodů) Nechť
P = { x ∈ Rn
| Ax ≤ a, x ≤ 0 } a Q = { x ∈ Rn
| Bx ≥ b, x ≥ 0 }
jsou dva polyedry. Formulujte Farkasovo lemma udávající nutnou a postačující
podmínku na matice A a B a vektory a a b, aby existovaly body y ∈ P a z ∈ Q,
jejichž manhattanská vzdálenost je 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 P, které lze zadat systémem nerovnic takovým,
že systém všech jeho implicitních rovnic zadává stěnu polyedru P; svoje tvrzení
zdůvodněte. Charakterizujte minimální stěny polyedrů pomocí systémů nerovnic
a tuto charakterizaci dokažte. Dejte příklad polyedru dimenze 3, který má právě
jednu omezenou maximální stěnu.
4. (30 bodů) Mějme dvě úlohy lineárního programování:
maximalizovat x + 2y + z
minimalizovat x + 2y + z
při stejných omezeních x ≥ 0, y ≥ 0, z ≥ 0, t ≥ 0 a
x − y + 2z − t ≤ −1,
3x + y − t ≤ 1,
2x − y + 3z − t ≥ 2,
2x + 2y − t ≥ 8.
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.