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

<{ForumPost(poster="awk", timestamp=2019-05-16 09:05:02)}>
 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.
<{/ForumPost}>