Lineární programování – jaro 2017 – 3. termín
1. (15 bodů) Formulujte Farkasovo lemma udávající nutnou a postačující podmínku
na řádkové vektory a1
, . . . , ak
, b1
, . . . , b ∈ Rn
, aby polytop generovaný body
a1
, . . . , ak
obsahoval bod u, konvexní kužel generovaný vektory b1
, . . . , b obsahoval
bod v a přitom tyto body splňovaly podmínku, že každá složka v je alespoň o 1
větší než největší složka u.
2. (20 bodů) Určete funkci f vektoru proměnných z, matici B a vektor a takové,
že úloha lineárního programování
min { f | Bz + a = 0, z ≤ 0 }
je duální k úloze
max { x1 + · · · + xm | x ≤ y1 · d, Ax = b, yC ≥ c, |x1| + |x2| ≤ 1 },
kde x = (x1, . . . , xm)T
a y = (y1, . . . , yn) jsou vektory proměnných, b, c, d konstantní
vektory a A, C matice. Formulujte větu o dualitě pro tuto dvojici úloh.
3. (25 bodů) Definujte polyedry a polytopy a uveďte, jaký je mezi těmito pojmy
vztah. Zdůvodněte, že každý neprázdný polytop je bodovaný. Popište konstrukci,
která z polytopů a polyedrálních kuželů vytvoří právě všechny polyedry. Dokažte,
že každý polyedr je opravdu možné touto konstrukcí získat. V souladu s definicí
polyedru dejte příklad nebodovaného polyedru takového, že nejmenší počet vrcholů
příslušného polytopu je 3. Dokažte, že každý polyedrální kužel má nejmenší stěnu.
4. (30 bodů) Mějme dvě úlohy lineárního programování:
minimalizovat 3x − y + z
maximalizovat − 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.