Lineární programování – jaro 2017 – 4. termín
1. (15 bodů) Formulujte Farkasovo lemma udávající nutnou a postačující podmínku
na body a, b1
, . . . , bk
, c1
, . . . , c ∈ Rn
(kde k, ≥ 1), aby existovala afinní nadrovina
neobsahující bod a taková, že body a, b1
, . . . , bk
leží v jednom poloprostoru určeném
touto nadrovinou a body c1
, . . . , c ve druhém.
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, |x1| + |x2| ≤ 1 },
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ů) Definujte polyedry a jejich stěny. Zdůvodněte, že každá stěna polyedru
je průnikem jeho maximálních stěn. Formulujte věty, které jste při tomto
zdůvodnění použili, a jednu z nich dokažte. Dejte příklad polyedru obsahujícího
minimální stěnu, která jde jako průnik maximálních stěn vyjádřit jediným způsobem,
a současně stěnu, pro kterou takové vyjádření není jednoznačné.
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.