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

Uživatelský avatar
awk
Matfyz(ák|ačka) level II
Příspěvky: 56
Registrován: 21. 5. 2018 18:54
Typ studia: Informatika Bc.

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

Příspěvek od awk »

2. 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ý:
\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í:
\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 (n je počet vrcholů a \[n\] značí množinu \{1,2,\ldots,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):
\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.
Odpovědět

Zpět na „Ostatní“