Lineární programování – jaro 2011 – 5. termín
1. (15 bodů) Formulujte variantu Farkasova lemmatu udávající nutnou a postačující
podmínku k tomu, aby afinní podprostor
{ (x1, . . . , xn) ∈ Rn
| A · (x1, . . . , xn)T
= b }
obsahoval bod (x1, . . . , xn) takový, že pro všechna i ∈ {1, . . . , n−1} se xi+1 liší od
xi nejvýše o danou hodnotu ai > 0.
2. (20 bodů) Určete funkci f vektoru proměnných y, matici G a vektor h takové,
že úloha lineárního programování
max { f | yG ≤ h, y ≤ 0 }
je duální k úloze
min { cXd | AX ≤ B, X ≥ 0 },
kde A je daná matice typu m×n a X je matice proměnných typu n×k. Formulujte
větu o dualitě pro tuto dvojici úloh.
3. (25 bodů) Definujte polyedr a jeho dimenzi. Definujte maximální stěny polyedru,
charakterizujte je algebraicky pomocí systémů nerovnic a tuto charakterizaci dokažte.
Určete, kolik maximálních stěn mají polyedry, jejichž všechny maximální
stěny mají dimenzi 0.
4. (30 bodů) Duální simplexovou metodou nalezněte nějakou přípustnou simplexovou
tabulku pro úlohu lineárního programování
maximalizovat 2x − y − 5z
při omezeních x ≥ 0, y ≥ 0, z ≥ 0 a
2x − y + 3z ≥ 2,
2x − 3y − 8z ≤ −9,
2x − 2y + 3z ≤ −2,
4x − 3y − z ≤ −1
a úlohu poté dořešte primární simplexovou metodou.