Lineární programování – jaro 2014 – 3. 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 má kapacitu ai 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 bij l/s a minimálním požadovaném průtoku cij 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á bij a cij nulová.)
2. (20 bodů) Určete funkci f vektoru proměnných z, matici F a vektor a takové,
že úloha lineárního programování
max { f | zF = a, z ≤ 1 }
je duální k úloze
min { cx | (y + 1)A = p, Bx ≥ q, yb ≤ dx }.
Formulujte větu o dualitě pro tuto dvojici úloh.
(x je sloupcový vektor proměnných; y je řádkový vektor proměnných; A a B jsou
matice; b, c, d, p a q jsou vektory; 1 značí vektor (1, . . . , 1))
3. (25 bodů) Definujte stěny polyedru. Charakterizujte polyedry, které nemají žádné
maximální stěny. Charakterizujte minimální stěny polyedrů pomocí systémů nerovnic
a tuto charakterizaci dokažte. Uveďte, jak lze z matice zadávající polyedr
určit dimenzi minimálních stěn, a svoje tvrzení dokažte. Dejte příklad polyedru
dimenze 3 takového, že průnikem libovolné dvojice jeho maximálních stěn je jeho
minimální stěna.
4. (30 bodů) Vytvořte simplexovou tabulku odpovídající bazické množině indexů
{3, 1, 2} (v tomto pořadí) pro úlohu lineárního programování maximalizovat
x1 − x2 − x3 − 2x4 + 2x5
při omezeních (x1, x2, x3, x4, x5) ≥ 0 a
2x1 + x2 + 3 = x3 + x4 + 2x5,
x1 + 2x4 + 5 = x3 + 2x5,
x2 + 2x3 + x4 = 13
a s touto počáteční tabulkou vyřešte úlohu primární simplexovou metodou. Po
jejím vyřešení přidejte další omezení
x4 + 1 ≥ x1 + 2x2 + 3x3
a úlohu dořešte duální simplexovou metodou.