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

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

$$z = x_1 + x_2 + 3 x_3 - x_4$$

$$x_1 + 2 x_3 \leq 740$$

$$2 x_2 - 7 x_4 \leq 0$$

$$x_2 - x_3 + 2 x_4 \geq \frac{1}{2}$$

$$x_1 + x_2 + x_3 + x_4 = 9$$

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

$$x_1 + 2 x_3 + y_1 = 740$$

$$2 x_2 - 7 x_4 + y_2 = 0$$

$$x_2 - x_3 + 2 x_4 - y_3 = \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$

$$z_3 = \frac{1}{2} - x_2 + x_3 - 2 x_4 + y_3 = 0$$

$$z_4 = 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

$$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$$

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

$$\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$$

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

$$x_1 = y_2 = y_3 = 0\ \ , \qquad x_2 = \frac{133}{40} \simeq 3.33 \ ,$$

$$x_3 = \frac{189}{40} \simeq 4.73\ \ , \qquad x_4 = \frac{209}{220} \simeq 0.95$$

$$= 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ů.