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ý:
{: alt="\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*}" type="image/"}
Příklad druhý
Pomocí simplexové metody vyřešte následující úlohu lineárního programování:
{: alt="\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*}" type="image/"}
Jako výchozí přípustné řešení užijte vektor {: alt="(0,0,10,40,20,15)" type="image/"}.
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 ({: alt="n" type="image/"} je počet vrcholů a {: alt="[n]" type="image/"} značí množinu {: alt="{1,2,\ldots,n}" type="image/"}):
{: alt="\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*}" type="image/"}
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 {: alt="(2,1,0,0)" type="image/"}:
{: alt="\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*}" type="image/"}
Součástí zadání byly ještě nějaké užitečné věty a definice.