next up previous
Next: Převedení obecné formy na Up: Lineární programování (simplexová metoda) Previous: Lineární programování (simplexová metoda)

Řešení omezené normální formy - příklad

Hledáme maximum účinkové funkce $z$, úloha je zadána následovně

$\displaystyle z = 2 x_2 - 4 x_3$      
$\displaystyle x_1 \geq 0, \quad x_2 \geq 0, \quad x_3 \geq 0, \quad x_4 \geq 0$      
$\displaystyle x_1 = 2 - 6 x_2 + x_3$      
$\displaystyle x_4 = 8 + 3 x_2 - 4 x_3$      

Nyní sestavíme proměnné do tabulky, $x_1, x_4$ jsou levostranné proměnné a $x_2, x_3$ pravostranné.

$x_2$ $x_3$
$z$ 0 2 -4
$x_1$ 2 -6 1
$x_4$ 8 3 -4

Kdyby $z$ mělo všechny koeficienty u pravostranných proměnných menší nebo rovné nule, byla by úloha již vyřešená. Kladné koeficienty u pravostranných proměnných v $z$ je třeba odstranit. Vybereme tu pravostrannou proměnnou (sloupec), která má u z maximální kladný koeficient. Pro tuto proměnnou vybereme hlavní prvek - podmínku (řádek), která maximálně omezuje rozsah proměnné a z této podnínky proměnnou vyjádříme, zde

\begin{displaymath}
x_2 = \frac{1}{3} - \frac{x_1}{6} +\frac{x_3}{6} \ \ .
\end{displaymath}

Potom tedy máme tabulku:

$x_1$ $x_3$
$z$ $2/3$ $-1/3$ $-11/3$
$x_2$ $1/3$ $-1/6$ $1/6$
$x_4$ $9$ $-1/2$ $-7/2$

Maximum $z$ je tedy při $x_1 = x_3 = 0$, $z_m = 2/3$, $x_2 = 1/3$ a $x_4 = 9$.

Algoritmus řešení lze tedy shrnout

  1. Najdeme hlavní sloupec a hlavní element.
  2. Uschováme hlavní sloupec.
  3. U řádků mimo hlavního vytvoříme takovou kombinaci s hlavním řádkem, aby v hlavním sloupci vznikla nula.
  4. Dělíme hlavní řádek $(-1)*$ hlavní element.
  5. Zaměníme hlavní element za jeho převrácenou hodnotu.
  6. Zbytek členů hlavního sloupce vždy vydělíme hodnotou hlavního elementu.


next up previous
Next: Převedení obecné formy na Up: Lineární programování (simplexová metoda) Previous: Lineární programování (simplexová metoda)
Jiri Limpouch
2000-04-18