Lineární programování – jaro 2016 – 3. termín
1. (15 bodů) Ministr financí již přislíbil každému z n ministerstev ve státním rozpočtu
na příští rok jistou částku, a to konkrétně i-tému ministerstvu ai korun,
pro i = 1, . . . , n. Na zasedání vlády bylo následně rozhodnuto o zvýšení schodku
rozpočtu o α korun, přičemž i-té ministerstvo z této částky požaduje bi korun,
pro i = 1, . . . , n. Formulujte Farkasovo lemma udávající nutnou a postačující podmínku
na hodnoty ai, bi, α a β, aby bylo možno rozdělit celou částku mezi ministerstva
při splnění následujících podmínek:
(a) Každému ministerstvu bude přidána alespoň polovina částky, kterou poža-
duje.
(b) Žádnému ministerstvu se přislíbená částka nezvýší o více než o deset procent.
(c) Pro libovolná dvě ministerstva nepřekročí rozdíl mezi jim přidanými částkami
β korun.
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 | yA = 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ů) Formulujte větu o rozkladu polyedrů na polytopy a kužely a definujte
všechny ve větě použité pojmy. Dokažte, že každý polyedr jde opravdu takto rozložit.
Charakterizujte všechny polyedry, pro které je tento rozklad jednoznačný,
a tuto charakterizaci dokažte. Dejte příklad polyedru dimenze tři, který lze popsaným
způsobem jednoznačně rozložit na polytop dimenze jedna a kužel dimenze
dva.
4. (30 bodů) Vyřešte primární simplexovou metodou úlohu lineárního programování
minimalizovat 2x + y − 10z − t
při omezeních x ≥ 0, y ≥ 0, 8 ≥ z ≥ 0, t ≥ 0 a
x − y + 2z + 2t ≤ −4,
2x − 2y + 3z + 4t ≥ −15,
x − 2z − t ≥ −6.
Poté využijte závěrečnou simplexovou tabulku k vyřešení úlohy, která vznikne
z původní úlohy nahrazením podmínky 8 ≥ z podmínkou 2 ≥ z, duální metodou.