Lineární programování – jaro 2018 – 1. termín
1. (15 bodů) Formulujte Farkasovo lemma udávající nutnou a postačující podmínku
k tomu, aby bylo možno zajistit požadovanou cirkulaci vody v uzavřeném chladicím
systému, který sestává z n čerpadel, kde i-té čerpadlo je schopno čerpat
nejméně ai l/s a nejvýše bi l/s, pro i = 1, . . . , n, přičemž z i-tého do j-tého čerpadla
vede potrubí o maximálním možném průtoku cij l/s a minimálním požadovaném
průtoku dij l/s, pro všechna i, j = 1, . . . , n. (Všechna voda, která do některého
čerpadla vstupuje, musí být před opuštěním tohoto čerpadla vyčerpána vzhůru.)
(Praktická poznámka: pokud některé potrubí neexistuje, zvolili jsme příslušná cij
a dij nulová.)
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ů) Formulujte algebraickou charakterizaci stěn polyedru pomocí systémů
nerovnic. Charakterizujte minimální stěny polyedrů pomocí systémů nerovnic a
tuto charakterizaci dokažte. Definujte bodovaný polyedr. Charakterizujte bodované
polyedry, jejichž maximálními stěnami jsou právě minimální stěny. Dejte
příklad dvou bodovaných polyedrů takových, že jejich průnik má o tři vrcholy
více, než mají původní polyedry dohromady.
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.