Filtr seznamu úloh?
Škály
Štítky
«
«
Dvě proměnné
Úloha číslo: 3256
Vyřešte úlohu LP max
Varianta 1
nejprve grafickou metodou.
Řešení
Výsledek
Optimální řešení je \mathbf x^*=(2{,}3), s hodnotou účelové funkce z=5.
Varianta 2
simplexovou metodou v rovnicovém tvaru a sledujte, kde se v mnohostěnu vyskytují bázická přípustná řešení.
Nápověda
Výchozí tvar úlohy LP pro použití simplexové metody bude A\mathbf x\le \mathbf b.
Každé podmínce odpovídá nějaká proměnná, jejíž hodnota udává "vzdálenost" libovolného řešení od příslušné hraniční nadroviny – viz obrázek.
Během simplexové metody bude každé bázické řešení ležet v průsečíku dvou (= d = počtu původních proměnných) hraničních přímek (nadrovin), a to takových že jim odpovídající proměnné mají hodnotu 0. Takové nulové proměnné budou právě všechny nebázické proměnné, čili všechny proměnné na pravé straně tabulky.
Řešení
Pro každou podmínku zavedeme novou pomocnou proměnou a sestavu přepíšeme ve tvaru:
\begin{array}{rrrrrrrr} x_3 & = & - & x_1 & + & x_2 & + & 2 \\ x_4 & = & + & x_1 & - & x_2 & + & 1 \\ x_5 & = & - & 2 x_1 & - & x_2 & + & 7 \\ \hline z & = & & x_1 & + & 2 x_2 \\ \end{array}
kde všechny proměnné jsou nezáporné x_i\ge 0. Nalevo stojí tzv. bázické (v tuto chvíli jmenovitě všechny pomocné) proměnné, a pod čarou počítáme hodnotu z účelové funkce.
První bázické řešení tedy odpovídá hodnotám x_1,x_2=0, (x_1,…,x_5)=(0{,}0,2{,}1,7) a účelová funkce má hodnotu z=0.
Hodnotu účelové funkce lze zvýšit kupříkladu zvýšením x_1 (tzv. pivot). Hranice pro možné zvýšení stanovuje v našem případě nezápornost proměnných x_3 a x_5, a z těchto dvou je těsnější podmínka pro nezápornost x_3. Provedením substituce x_1=x_2-x_3+2 se z x_1 stane bázická proměnná, x_3 naopak bázi opustí. Dostaneme novou tabulku: \begin{array}{rrcrrrrrrr} x_1 & & & = & - & x_3 & + & x_2 & + & 2 \\ x_4 & = & (x_2-x_3+2)-x_2+1 & = & - & x_3 & & & + & 3 \\ x_5 & = & -2(x_2-x_3+2)-x_2+7 & = & & 2 x_3 & - & 3 x_2 & + & 3 \\ \hline z & = & (x_2-x_3+2)+x_2 & = & - & x_3 & + & 3 x_2 & + & 2 \\ \end{array} Nové bázické řešení je (x_1,…,x_5)=(2{,}0,0{,}3,3), na grafu jsme se posunuli z bodu (0{,}0) do bodu (2{,}0) po přímce x_2=0 (obecně by to byla přímka tvořící průnik d-1 nadrovin odpovídající nulovým t.j. nebázickým proměnným). Hodnota účelové funkce stoupla na z=2.
V dalším kroku zvolíme pivot x_2 (nemáme volbu), a bázi opustí x_5: \begin{array}{rrcrrrrrrrr} x_1 & = & -x_3+(2/3 x_3 -1/3 x_5+1)+2 & = & - & 1/3 x_3 & - & 1/3 x_5 & + & 3 \\ x_4 & & & = & - & x_3 & & & + & 3 \\ x_2 & & & = & & 2/3 x_3 & - & 1/3 x_5 & + & 1 \\ \hline z & = & -x_3+3(2/3 x_3 -1/3 x_5+1)+2 & = & & x_3 & - & x_5 & + & 5 \\ \end{array} Máme (x_1,…,x_5)=(3{,}1,0{,}3,0), z=5, posouvali jsme se po přímce x_3=0. Volíme pivot x_3, bázi opustí x_4 (je těsnější než x_1 protože 3< \frac{3}{1/3}) a máme: \begin{array}{rrcrrrrrrrr} x_1 & = & -1/3(-x_4+3)-1/3 x_5+3 & = & & 1/3 x_4 & - & 1/3 x_5 & + & 2 \\ x_3 & & & = & - & x_4 & & & + & 3 \\ x_2 & = & 2/3(-x_4+3)-1/3 x_5+1 & = & - & 2/3 x_4 & - & 1/3 x_5 & + & 3 \\ \hline z & = & (-x_4+3)-x_5+5 & = & - & x_4 & - & x_5 & + & 8 \\ \end{array} což odpovídá bázickému řešení (x_1,…,x_5)=(2{,}3,3{,}0,0), z=5. V tomto okamžiku simplexový algoritmus skončí, neboť libovolným zvýšením x_4 a x_5 by hodnota účelové funkce klesla. Každé jiné přípustné řešení musí mít nenulové alespoň jedno z x_4 nebo x_5 a tudíž má nižší hodnotu účelové funkce.
Varianta 3
Simplexovou metodou s použitím simplexové tabulky. (v prvním kroku vyberte za pivot x_1).
Nápověda
Výchozí tabulka má jeden sloupec pro každou proměnnou, v první sloupec obsahuje index bázické proměnné, jež je vyjádřena v daném řádku.
Bázické řešení má vlastnost, že jeho skalární součin s vektorem na posledním řádku zůstává 0 (protože leží v jednoznačném průniku d nadrovin). Za pivota vybíráme takový sloupec s, co má v posledním řádku kladnou hodnotu. Eliminací c_s na 0 se účelová funkce zvýší (t.j. -z se sníží), protože poslední sloupec je vždy nezáporný. V pravém dolním rohu zůstává (až na znaménko) hodnota účelové funkce. Změnu znaménka lze vysvětlit tím, že pokud bychom brali poslední řádek jako rovnici \mathbf c^T\mathbf x=z, je součin na levé straně vždy nulový, zatímco výraz na pravé staně bude ve tvaru z+t, kde t je skutečné číslo z rohu tabulky.
Dále tedy volíme s=1 a spočteme \min_{r\in I}\{\frac{b_r}{a_{r,s}}: a_{r,s}>0\} a vybereme takový bázickou proměnnou x_r, kde se minimum nabývá (čili r=3). Vzhledem k této proměnné eliminujeme elementárními úpravami všechny ostatní hodnoty v s-tém sloupci. (Elementárními úpravami se prostor řešení nemění.):
Řešení
\begin{array}{r|r|r} I & A & \mathbf b \\ \hline & \mathbf c^T & -z \\ \end{array} = \begin{array}{r|rrrrr|r} 3^* & 1 & -1 & 1 & 0 & 0 & 2\\ 4 & -1 & 1 & 0 & 1 & 0 & 1\\ 5 & 2 & 1 & 0 & 0 & 1 & 7\\ \hline & 1^* & 2 & 0 & 0 & 0 & 0\\ \end{array}
\begin{array}{r|rrrrr|r} 1 & 1 & -1 & 1 & 0 & 0 & 2\\ 4 & 0 & 0 & 1 & 1 & 0 & 3\\ 5^* & 0 & 3 & -2 & 0 & 1 & 3\\ \hline & 0 & 3^* & -1 & 0 & 0 & -2\\ \end{array} Pro s=2 dostaneme r=5 a posléze pro s=3 a r=4 \begin{array}{r|rrrrr|r} 1 & 1 & 0 & 1/3 & 0 & 1/3 & 3\\ 4^* & 0 & 0 & 1 & 1 & 0 & 3\\ 2 & 0 & 1 & -2/3 & 0 & 1/3 & 1\\ \hline & 0 & 0 & 1^* & 0 & -1 & -5\\ \end{array} \hspace{2cm} \begin{array}{r|rrrrr|r} 1 & 1 & 0 & 0 & -1/3 & 1/3 & 2\\ 3 & 0 & 0 & 1 & 1 & 0 & 3\\ 2 & 0 & 1 & 0 & 2/3 & 1/3 & 3\\ \hline & 0 & 0 & 0 & -1 & -1 & -8\\ \end{array} Tímto krokem simplexový algoritmus končí.