od awk » 16. 5. 2019 09:05
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ý:
Příklad druhý
Pomocí simplexové metody vyřešte následující úlohu lineárního programování:
Jako výchozí přípustné řešení užijte vektor
.
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 (
je počet vrcholů a
značí množinu
):
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
:
Součástí zadání byly ještě nějaké užitečné věty a definice.
[size=200] 2. písemka z lineárního programování [/size]
Písemku vypracovávejte samostatně. Nezapoměňte všude [b]uvádět postupy[/b], může vás to zachránit v případě numerické chyby. Všechna tvrzení je třeba [b]řádně zdůvodnit[/b], 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šší. [i]Hodně štěstí![/i]
Jméno/Přezdívka:
[line][/line]
[size=150]Příklad první[/size]
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ý:
[latex]\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*}[/latex]
[size=150]Příklad druhý[/size]
Pomocí simplexové metody vyřešte následující úlohu lineárního programování:
[latex]\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*}[/latex]
Jako výchozí přípustné řešení užijte vektor [latex](0,0,10,40,20,15)[/latex].
[size=150]Příklad třetí[/size]
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 ([latex]n[/latex] je počet vrcholů a [latex]\[n\][/latex] značí množinu [latex]\{1,2,\ldots,n\}[/latex]):
[latex]\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*}[/latex]
[size=150]Příklad čtvrtý[/size]
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 [latex](2,1,0,0)[/latex]:
[latex]\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*}[/latex]
[line][/line]
Součástí zadání byly ještě nějaké užitečné věty a definice.