next up previous
Next: About this document ... Up: Lineární programování (simplexová metoda) Previous: Řešení omezené normální formy

Převedení obecné formy na omezenou normální

Převedení ukážeme na příkladu

$\displaystyle z$ $\textstyle =$ $\displaystyle x_1 + x_2 + 3 x_3 - x_4$  
$\displaystyle x_1 + 2 x_3$ $\textstyle \leq$ $\displaystyle 740$  
$\displaystyle 2 x_2 - 7 x_4$ $\textstyle \leq$ $\displaystyle 0$  
$\displaystyle x_2 - x_3 + 2 x_4$ $\textstyle \geq$ $\displaystyle \frac{1}{2}$  
$\displaystyle x_1 + x_2 + x_3 + x_4$ $\textstyle =$ $\displaystyle 9$  

Zavedeme pomocné proměnné $y_1$, $y_2$, $y_3$ a tak podmínky s nerovnostmi převedeme na rovnost

$\displaystyle x_1 + 2 x_3 + y_1$ $\textstyle =$ $\displaystyle 740$  
$\displaystyle 2 x_2 - 7 x_4 + y_2$ $\textstyle =$ $\displaystyle 0$  
$\displaystyle x_2 - x_3 + 2 x_4 - y_3$ $\textstyle =$ $\displaystyle \frac{1}{2}$  

První a druhá rovnice jsou v omezené normální formě, pro třetí a čtvrtou zavedeme pomocné proměnné $z_3$, $z_4$
$\displaystyle z_3$ $\textstyle =$ $\displaystyle \frac{1}{2} - x_2 + x_3 - 2 x_4 + y_3 = 0$  
$\displaystyle z_4$ $\textstyle =$ $\displaystyle 9 - x_1 - x_2 - x_3 - x_4 = 0$  

Protože $z_3$, $z_4$ jsou nulové, zavedeme dodatečnou účinkovou funkci
$z' = -z_3 - z_4$, která má maximum pro $z_3 = z_4 = 0$.

Sestavíme tabulku pro omezenou normální formu

$x_1$ $x_2$ $x_3$ $x_4$ $y_3$
$z$ 0 1 1 3 $-1/2$ 0
$y_1$ 740 -1 0 -2 0 0
$y_2$ 0 0 -2 0 7 0
$z_3$ $1/2$ 0 -1 1 -2 1
$z_4$ 9 -1 -1 -1 -1 0
$z'$ $-19/2$ 1 2 0 3 -1

Vybereme hlavní element na příklad ze sloupce $x_2$, na třetím řádku je $x_{2m} = 1/2$, na čtvrtém $x_{2m} = 9$, ale na druhém $x_{2m} = 0$. Z druhého řádku máme $x_2 = - 1/2\, y_2 + 7/2\, x_4$. Kdybychom vzali hlavní prvek ze 3. řádku, bylo by po úpravě na 2. řádku $y_2 = -1 - 2 z_3 + 11 x_4 - 2 y_3$. To je ovšem chybně, konstanta nesmí být záporná ($-1$). Po úpravě má tabulka tvar

$x_1$ $y_2$ $x_3$ $x_4$ $y_3$
$z$ 0 1 $-1/2$ 3 3 0
$y_1$ 740 -1 0 -2 0 0
$x_2$ 0 0 $-1/2$ 0 $7/2$ 0
$z_3$ $1/2$ 0 $1/2$ 1 $-11/2$ 1
$z_4$ 9 -1 $1/2$ -1 $-9/2$ 0
$z'$ $-19/2$ 1 -1 0 10 -1

Hlavní sloupec je pod $x_4$, hlavní element ($-11/2$) je v řádku u $z_3$, odtud vyjádříme

\begin{displaymath}
x_4 = \frac{1}{11} + \frac{1}{11}\, y_2 + \frac{2}{11}\, x_3 -
\frac{2}{11}\, z_3 + \frac{2}{11}\, y_3
\end{displaymath}

a dostaneme tabulku

$x_1$ $y_2$ $x_3$ $z_3$ $y_3$
$z$ $9/11$ 1 $-5/22$ $39/11$ $-6/11$ $6/11$
$y_1$ 740 -1 0 -2 0 0
$x_2$ $1/11$ 0 $1/11$ $2/11$ $-2/11$ $2/11$
$x_4$ $1/11$ 0 $1/11$ $2/11$ $-2/11$ $2/11$
$z_4$ $189/22$ -1 $1/11$ $-20/11$ $9/11$ $-9/11$
$z'$ $-189/22$ 1 $-1/11$ $20/11$ $-20/11$ $9/11$

Nyní z řádku u $z_4$ dostaneme

\begin{displaymath}
\frac{20}{11} x_3 = 8 \frac{13}{22} - x_1 + \frac{1}{11}\, y_2 -
z_4 + \frac{9}{11}\, z_3 - \frac{9}{11}\, y_3
\end{displaymath}

a nová tabulka má tvar

$x_1$ $y_2$ $z_4$ $z_3$ $y_3$
$z$ $681/40$ $-19/20$ $-1/20$ $-39/20$ $21/20$ $-21/20$
$y_1$ $730 + 11/20$ $1/10$ $-1/10$ $11/10$ $-9/10$ $9/10$
$x_2$ $133/40$ $-7/20$ $-3/20$ $-7/20$ $-7/20$ $7/20$
$x_4$ $209/220$ $-1/10$ $1/10$ $-1/10$ $-1/10$ $1/10$
$x_3$ $189/40$ $-11/20$ $1/20$ $-11/20$ $9/20$ $-9/20$
$z'$ 0 0 0 -1 -1 0

Jakmile dostaneme všechna $z_i$ na pravou stranu, můžeme je vynechat, pomocná účinková funkce $z'$ je minimalizována a vynecháme ji. Úloha je převedena na omezenou normální formu.

V našem případě jsou už u $\forall$ skutečných pravostranných proměnných ($x_1$, $y_2$, $y_3$) koeficienty u účinkové funkce $z$ záporné a úloha je tedy vyřešena

$\displaystyle x_1 = y_2 = y_3 = 0\ \ , \qquad x_2$ $\textstyle =$ $\displaystyle \frac{133}{40} \simeq 3.33 \ ,$  
$\displaystyle x_3 = \frac{189}{40} \simeq 4.73\ \ , \qquad x_4$ $\textstyle =$ $\displaystyle \frac{209}{220} \simeq 0.95$  
$\displaystyle z_{max} = \frac{681}{40} = 17.025\ \ , \qquad$ y_1 $\textstyle =$ $\displaystyle 730\frac{11}{20} \ .$  

Degenerovaný možný vektor - stejně velké omezení ve více řádcích $\rightarrow$ více možných hlavních prvků. Potom se rozhodujeme při výběru rozhodujeme podle dalších sloupců.


next up previous
Next: About this document ... Up: Lineární programování (simplexová metoda) Previous: Řešení omezené normální formy
Jiri Limpouch
2000-04-18