Matfyz Wiki

Optimalizační metody 15.5.2019 2. záp. písemka

awk at 2019-05-16 09:05:02

  1. písemka z lineárního programování
    Písemku vypracovávejte samostatně. Nezapoměňte všude uvádět postupy, může vás to zachránit v případě numerické chyby. Všechna tvrzení je třeba řádně zdůvodnit, věty z přednášky či cvičení však dokazovat nemusíte, vždy pouze uveďte, co a kde používáte.
    Příklady mohou být rozdílně složité a proto doporučujeme nejdříve pročíst všechna zadání a začít od těch, které vám budou připadat jednodušší. Hodně štěstí!
    Jméno/Přezdívka:

Příklad první
Formulujte pomocnou úlohu simplexové metody a s její pomocí nalezněte přípustné bázické řešení lineárního programu, nebo ukažte, že je program nepřípustný:
max⁡ 2x1+x3+x48x1−3x3−x4+2x6=164x2−x3−x4=8−x2+x3+x5=2−2x3+x4+x6=4x1,…,x6≥0\begin{align*} \max \ 2x_1 + x_3 + x_4 & \\ 8x_1 - 3x_3 - x_4 + 2x_6 &= 16 \\ 4x_2-x_3-x_4 &=8 \\ -x_2+x_3+x_5&=2 \\ -2x_3+x_4+x_6&=4 \\ x_1,\ldots,x_6 &\ge 0 \end{align*}

Příklad druhý
Pomocí simplexové metody vyřešte následující úlohu lineárního programování:
max⁡ 3x1+4x2x3=10−x1+x2x4=40−2x1+x2x5=20+x1+x2x6=15+10x1−5x2x1,…,x6≥0\begin{align*} \max \ 3x_1&+4x_2 \\ x_3=10&-x_1+x_2 \\ x_4=40&-2x_1+x_2 \\ x_5=20&+x_1+x_2 \\ x_6=15&+10x_1-5x_2 \\ x_1,\ldots,&x_6 \ge 0 \end{align*}
Jako výchozí přípustné řešení užijte vektor $(0,0,10,40,20,15)$.

Příklad třetí
Problém Minimálního pokrytí grafu klikami je zadán následovně: Pro daný neorientovaný graf chceme nalézt co nejméně klik (uplných podgrafů) tak, že každý vrchol zadaného grafu bude patřit do nějaké kliky a zároveň každá taková klika používá pouze hrany z grafu.
Dualizujte následující relaxovaný celočíselný program pro tento problém (nn je počet vrcholů a [n][n] značí množinu {1,2,…,n}\{1,2,\ldots,n\}):
min⁡ ∑k∈[n]ykxu,k+xv,k≤1∀{u,v}∉E,∀k∈[n]∑k∈[n]xv,k≥1∀v∈Vyk≥1n∑v∈Vxv,k∀k∈[n]xv,k≥0∀v∈V,k∈[n]yk≥0∀k∈[n]\begin{align*} \min \ \sum_{k \in [n]} y_k & \\ x_{u,k} + x_{v,k} &\le 1 \quad &\forall{\{u,v\}} \notin E, \forall{k} \in [n] \\ \sum_{k \in [n]} x_{v,k} &\ge 1 \quad &\forall{v} \in V \\ y_k &\ge \frac{1}{n} \sum_{v\in V} x_{v,k} \quad &\forall{k} \in [n] \\ x_{v,k} &\ge 0 \quad &\forall{v} \in V, k \in [n] \\ y_k &\ge 0 \quad &\forall{k} \in [n] \end{align*}

Příklad čtvrtý
Pro zadaný lineární program nalezněte optimální řešení s využitím toho, že optimální řešení duálního programu je (2,1,0,0)(2,1,0,0):
min⁡ 4x1+3x2+7x3+12x4x1+x2+x3+2x4≥42x1+x2+x3+3x4≥53x1+2x2+2x3+x4≥2x1+3x2+7x3+2x4≥1x1,…,x4≥0\begin{align*} \min \ 4x_1+3x_2+7x_3&+12x_4 \\ x_1+x_2+x_3+2x_4 &\ge 4 \\ 2x_1+x_2+x_3+3x_4 &\ge 5 \\ 3x_1+2x_2+2x_3+x_4 &\ge 2 \\ x_1 + 3x_2 + 7x_3 + 2x_4 &\ge 1 \\ x_1,\ldots,x_4 &\ge 0 \end{align*}

Součástí zadání byly ještě nějaké užitečné věty a definice.