Lineární programování – jaro 2019 – 1. 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 existovaly body, které se od sebe
na žádné složce neliší o více než o 1, jeden z nich náleží do polytopu generovaného
body a1
, . . . , ak
a druhý náleží do konvexního kuželu generovaného vektory
b1
, . . . , b .
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ů) Definujte stěny polyedru a jejich dimenzi. Charakterizujte minimální
stěny polyedrů pomocí systémů nerovnic a tuto charakterizaci dokažte. Uveďte, jak
lze ze systému nerovnic zadávajícího polyedr určit dimenzi a zaměření minimálních
stěn. Dokažte, že n-rozměrný polyedr v prostoru Rn
, jehož minimální stěny mají
dimenzi n − 1, má nejvýše dvě vlastní stěny. Dejte příklad dvou polyedrů dimenze
tři, z nichž v jednom je počet minimálních stěn dvojnásobkem počtu stěn dimenze
o 1 větší a ve druhém je počet minimálních stěn polovinou počtu stěn dimenze o 1
větší.
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.