Sbírka matematických úloh

Dvě proměnné

Úloha číslo: 3256

• 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čí.