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

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

$$z = 2 x_2 - 4 x_3$$

$$x_1 \geq 0, \quad x_2 \geq 0, \quad x_3 \geq 0, \quad x_4 \geq 0$$

$$x_1 = 2 - 6 x_2 + x_3$$

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

$$x_2 = \frac{1}{3} - \frac{x_1}{6} +\frac{x_3}{6} \ \ .$$

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.