Lineární programování – jaro 2015 – 1. termín
1. (15 bodů) Nechť A a B jsou matice typu m × n nad R, a b, c ∈ Rm
a v1, . . . , vk ∈
Rn
jsou sloupcové vektory takové, že množiny P = { x ∈ Rn
| Ax ≤ b } a Q =
{ x ∈ Rn
| Bx ≤ c } jsou disjunktní. Formulujte Farkasovo lemma udávající nutnou
a postačující podmínku k tomu, aby existovaly body x ∈ P a y ∈ Q, které leží na
přímce kolmé ke všem vektorům v1, . . . , vk.
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 = 0, z ≤ 0 }
je duální k úloze
max { c · (xT
+ y) | x2
1 ≤ α ≤ by, By ≤ (xA)T
},
kde x = (x1, . . . , xn) a y = (y1, . . . , yn)T
jsou vektory proměnných, b a c jsou
konstantní vektory, A a B matice a α ≥ 0 číslo. Formulujte větu o dualitě pro tuto
dvojici úloh.
3. (25 bodů) Definujte stěny polyedru. Charakterizujte polyedry, které mají právě
jednu stěnu. 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ě
tři minimální stěny.
4. (30 bodů) Řešte primární simplexovou metodou úlohu minimalizovat
10x − y + 15z
při omezeních x ≥ 0, y ≥ 0, z ≥ 0 a
2x − y + 4z ≥ 6,
3x − 2y + z ≥ 7.
Po jejím vyřešení přidejte další dvě omezení
5x + 5y + 5z ≤ 13,
x − y + 7z ≤ 4
a úlohu dořešte duální simplexovou metodou.