Pomocná úloha
Úloha číslo: 3259
Vyřešte následující úlohu LP simplexovou metodou. Pro nalezení přípustného bázického řešení použijte pomocnou úlohu LP.
\[\begin{eqnarray*} \max (4x_1-2x_2+7x_3) \\ 5 x_1 + x_2 - 2 x_3 & \le & 12 \\ - x_1 - x_2 + x_3 & \le & -1 \\ 2x_1 + x_2 & \le & 4 \\ x_1 + x_3 & \le & 4 \\ x_1,x_2,x_3 & \ge & 0 \end{eqnarray*}\]
Řešení
Nejprve sestavíme simplexovou tabulku.
Tato tabulka má ale nevýhodu, že příslušné bázické řešení není přípustné (\(x_5=-1 < 0 \)). Musíme řešit pomocnou úlohu s tabulkou:
\[ \begin{array}{r|rrrrrrr|r} 4 & 5 & 1 & 2 & 1 & 0 & 0 & 0 & 12 \\ 5 & -1 & -1 & 1 & 0 & 1 & 0 & 0 & -1 \\ 6 & 2 & 1 & 0 & 0 & 0 & 1 & 0 & 4 \\ 7 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 4 \\ \hline & 4 & -2 & 7 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \] \[ \begin{array}{r|rrrrrrrrrrr|r} 4 & -1 & 5 & 1 & 2 & 1 & 0 & 0 & 0 & 12 \\ 0 & -1 & -1 & -1 & 1 & 0 & 1 & 0 & 0 & -1 \\ 5 & -1 & 2 & 1 & 0 & 0 & 0 & 1 & 0 & 4 \\ 6 & -1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 4 \\ \hline & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \end{array} \]
Řádky upravíme vůči sloupci pro \(x_0\) tak, aby tabulka byla konzistentní neboli
\[ \begin{array}{r|rrrrrrrrrrr|r} 4 & 0 & 6 & 2 & 1 & 1 &-1 & 0 & 0 & 13 \\ 0^*& 1 & 1 & 1 &-1 & 0 &-1 & 0 & 0 & 1 \\ 5 & 0 & 3 & 2 &-1 & 0 &-1 & 1 & 0 & 5 \\ 6 & 0 & 2 & 1 & 0 & 0 &-1 & 0 & 1 & 5 \\ \hline & 0 & 1 & 1^*&-1 & 0 &-1 & 0 & 0 & 1 \\ \end{array} \] \[ \begin{array}{r|rrrrrrrrrrr|r} 4 &-2 & 4 & 0 & 3 & 1 & 1 & 0 & 0 & 11 \\ 2 & 1 & 1 & 1 &-1 & 0 &-1 & 0 & 0 & 1 \\ 6 &-2 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 3 \\ 7 &-1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 4 \\ \hline &-1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \end{array} \]
Dostali jsme optimum pomocné úlohy. Protože \(x_0=0\), toto řešení odpovídá přípustnému řešení původní úlohy \(\mathbf x=(0{,}1,0{,}11,0{,}3,4)^T\) a bazí indexů \(B=\{4{,}2,6{,}7\}\).
Pokračujeme původní úlohou, t.j. bez proměnné \(x_0\) a s původní účelovou funkcí. (tabulka vpravo má poslední řádek po úpravě)
\[ \begin{array}{r|rrrrrrr|r} 4 & 4 & 0 & 3 & 1 & 1 & 0 & 0 & 11 \\ 2 & 1 & 1 &-1 & 0 &-1 & 0 & 0 & 1 \\ 6 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 3 \\ 7 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 4 \\ \hline & 4 & -2 & 7 & 0 & 0 & 0 & 0 & 0\\ \end{array} \] \[ \begin{array}{r|rrrrrrr|r} 4 & 4 & 0 & 3 & 1 & 1 & 0 & 0 & 11 \\ 2^* & 1 & 1 &-1 & 0 &-1 & 0 & 0 & 1 \\ 6 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 3 \\ 7 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 4 \\ \hline & 6 & 0 & 5^*& 0 &-2 & 0 & 0 & 2\\ \end{array} \]
\[ \begin{array}{r|rrrrrrr|r} 4 & 5 & 0 & 0 & 1 & 2 & 1 & 0 & 14 \\ 2 & 2 & 1 & 0 & 0 & 0 & 1 & 0 & 4 \\ 3^* & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 3 \\ 7 & 0 & 0 & 0 & 0 &-1 &-1 & 1 & 1 \\ \hline & 1^*& 0 & 0 & 0 &-7 &-5 & 0 & -13\\ \end{array} \] \[ \begin{array}{r|rrrrrrr|r} 4 & 0 & -\frac52 & 0 & 1 & 2 & -\frac32 & 0 & 4 \\ 1 & 1 & \frac12 & 0 & 0 & 0 & \frac12 & 0 & 2 \\ 3 & 0 & -\frac12 & 1 & 0 & 1 & \frac12 & 0 & 1 \\ 7 & 0 & 0 & 0 & 0 &-1 & -1 & 1 & 1 \\ \hline & 0 & -\frac12 & 0 & 0 &-7 &-\frac{11}2 & 0 &-15\\ \end{array} \]
Výsledek
Optimum je \(\mathbf x=(2{,}0,1)^T\) a hodnota účelové funkce v optimu je 15.
