Lineární programování – jaro 2011 – 3. termín
1. (15 bodů) Uvažujme n různých chemikálií, přičemž 1 kg i-té chemikálie má hodnotu
hi, zabere ve skladu pi metrů čtverečních a vyžaduje na chlazení výkon vi W,
pro i = 1, . . . , n. Máme k dispozici sklad o ploše p metrů čtverečních s chlazením
o výkonu v W. Formulujte variantu Farkasova lemmatu udávající nutnou a postačující
podmínku, kterou musejí splňovat čísla h, p, v, hi, pi, vi ∈ Q+
, abychom byli
schopni skladovat chemikálie v celkové hodnotě alespoň h. (Uvažujeme množství
skladovaných chemikálií vyjádřitelná racionálními čísly.)
2. (20 bodů) Určete funkci f vektoru proměnných z, matici F a vektor h takové,
že úloha lineárního programování
max { f | zF ≤ h, z ≥ 0 }
je duální k úloze
min { cx | Ax = By + d, x ≤ y ≤ 1 }.
Formulujte větu o dualitě pro tuto dvojici úloh.
(x a y jsou vektory proměnných stejné dimenze a 1 značí vektor (1, . . . , 1)T
.)
3. (25 bodů) Formulujte větu o rozkladu polyedrů a definujte v ní použité pojmy.
Dokažte tu implikaci této věty, která říká, že každý polyedr je možné rozložit.
Dejte příklad takového rozkladu polyedru
{ (x, y) ∈ R2
| x ≥ 0, y ≥ 0, x + y ≥ 1 }.
4. (30 bodů) Řešte primární simplexovou metodou úlohu maximalizovat
−8x − 10y + 11z
při omezeních x ≥ 0, y ≥ 0, z ≥ 0 a
2x + 3y − 3z ≥ 9,
3x + 4y − 5z ≥ 11.
Po jejím vyřešení přidejte další omezení
x + y − z ≤ 2
a úlohu dořešte duální simplexovou metodou.