Lineární programování – jaro 2018 – 2. termín
1. (15 bodů) Formulujte Farkasovo lemma udávající nutnou a postačující podmínku
na řádkové vektory a1
, . . . , ak
∈ Rm
a matici A ∈ Rm×n
, aby polytop generovaný
body a1
, . . . , ak
měl neprázdný průnik s polyedrem { x ∈ Rm
| xA ≥ b }.
2. (20 bodů) Určete funkci f vektoru proměnných z, matici C a vektor a takové,
že úloha lineárního programování
min { f | Cz ≤ a, z ≤ 1 }
je duální k úloze
max { dx | x ≤ yT
≤ 0, cx ≤ yb, yA ≥ d },
kde x a y jsou vektory proměnných stejné dimenze, b, c, d jsou konstantní vektory
a A je matice. Formulujte větu o dualitě pro tuto dvojici úloh.
3. (25 bodů) Definujte stěny polyedru a jejich dimenzi. Popište všechny polyedry,
které mají právě dvě maximální stěny. Formulujte a dokažte charakterizaci minimálních
stěn jistého polyedru, na níž je založena primární simplexová metoda;
k důkazu můžete použít obecnou větu charakterizující minimální stěny polyedrů.
Dejte příklad polyedru P a lineárně nezávislých vektorů c a d takových, že množinou
všech optimálních řešení úlohy max{ cx | x ∈ P } a úlohy max{ dx | x ∈ P }
je tatáž maximální stěna polyedru P.
4. (30 bodů) Mějme dvě úlohy lineárního programování:
minimalizovat 3x − y + z
minimalizovat 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.