Dvě proměnné
Úloha číslo: 3256
Vyřešte úlohu LP \[\begin{eqnarray*} \max (x_1+2x_2) \\ x_1 - x_2 & \le & 2 \\ -x_1 + x_2 & \le & 1 \\ 2x_1 + x_2 & \le & 7 \\ x_1,x_2 & \ge & 0 \end{eqnarray*}\]
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čí.
