Simplexová metoda

Simplexová metoda (Simplexový algoritmus) je iterativní způsob řešení problémů lineárního programování (lineární optimalizace) objevený americkým matematikem Georgem Dantzigem v roce 1947. Simplexová metoda postupuje od základního řešení, v každém svém kroku řešení pozmění takovým způsobem, aby hodnota účelové funkce byla vyšší než v kroku předchozím. Algoritmus terminuje, pokud řešení již nelze zlepšit (je optimální).

Základní postup

Základní postup řešení problémů maximalizace lineárního programování simplexovou metodou vyžaduje omezení ve tvaru nerovností a všechny proměnné musí být kladné.Pro řešení minimalizačních problémů je zapotřebí převést úlohu na maximalizační dle vzorce $\\min\\ f(x) = -\\max(-f(x))$ .

$\\max \\; \\{3x_{1} + 5x_{2}\\}$

Za podmínek:

$x_{1} \\leq 4$
$2x_{2} \\leq 12$
$3x_{1} + 2x_{2} \\leq 18$
$x_{i} \\geq 0$

Prvním krokem je odstranění nerovností z podmínek, čímž vzniknou v budoucí simplexové tabulce bázové proměnné.

$\\max \\; \\{3x_{1} + 5x_{2}\\}$

Za podmínek:

$x_{1} + x_{3} = 4$
$2x_{2} + x_{4} = 12$
$3x_{1} + 2x_{2} +x_{5} = 18$
$x_{i} \\geq 0$

Nyní přepíšeme problém do simplexové tabulky.

x₁	x₂	x₃	x₄	x₅	b
1	0	1	0	0	4
0	2	0	1	0	12
3	2	0	0	1	18
-3	-5	0	0	0	0

Sloupce odpovídají jednotlivým proměnným, řádky jednotlivým podmínkám. V posledním řádku je zapsáno kritérium ve tvaru $f(x) = 0 - (-3x_{1} - 5x_{2} - 0x_{3} - 0x_{4} - 0x_{5})$ . V posledním řádku sloupce b je hodnota kriteriální funkce za předpokladu, že jsou všechny nebázové proměnné nulové (ty jež nemají ve svých hodnotách jednotkovou matici).

$f(x) = 0x_{1} + 0x_{2} = 0$
$x_{3} = 4$
$x_{4} = 12$
$x_{5} = 18$

Nyní zvolíme klíčový sloupec. Klíčový sloupec je takový sloupec, na kterém hodnota kritéria závisí nejvíce. Z kriteriální funkce je to zřejmě $x_{2}$ , jelikož má tato proměnná nejvyšší multiplikativní koeficient (5). V simplexové tabulce je to sloupec, v jehož posledním řádku je nejnižší záporná hodnota (nejvyšší v absolutní hodnotě). Pokud jsou všechny hodnoty kladné, tak algorimus terminuje, řešení ve sloupci b je optimální.

Následuje volba klíčového prvku. V klíčovém sloupci hledáme takovou kladnou hodnotu, jejíž podíl s odpovídající hodnotou ve sloupci b je minimální ( $argmin \\{ {b_{i} \\over a_{ij}}, a_{ij} \\gt 0 \\}$ ). V tomto případě je to hodnota na druhém řádku. V případě rovnosti více minimálních hodnot vybereme libovolnou z nich. Tímto postupem vybíráme z omezení to, které je nejtvrdší (podle třetího omezení je x_2 maximálně 9, podle druhého maximálně 6).

Dalším krokem již je výpočet nové simplexové tabulky. Postupujeme tak, aby z báze vypadl sloupec obsahující jednotku na indexu klíčového prvku a nahradil jej v bázi klíčový sloupec, koeficienty v posledním řádku pod bází musí být nulové. Úpravy spočívají v přičítání (odečítání) násobků ostatních řádků, případně ve vynásobení řádku samotného.

x₁	x₂	x₃	x₄	x₅	b
1	0	1	0	0	4
0	1	0	1/2	0	6
3	0	0	-1	1	6
-3	0	0	5/2	0	30

V nové simplexové tabulce si povšimneme, že se hodnota kriteriální funkce zvýšila na 30, jejíž aktuální stav lze napsat takto:

$f(x) = 5 \\cdot 6 - (-3x_{1} + 2.5x_{4}) = 30 - (-3x_{1} + 2.5x_{4}) = 30$
$x_{1} = 0$
$x_{4} = 0$

Z uvedeného vyplývá, že řešení není stále optimální, protože zvýšení $x_{1}$ povede ke zvýšení hodnoty kritéria (v simplexové tabulce vidíme záporný koeficient v posledním řádku sloupce $x_{1}$ ). Proto provedeme další iteraci algoritmu.

x₁	x₂	x₃	x₄	x₅	b
0	0	1	1/3	-1/3	2
0	1	0	1/2	0	6
1	0	0	-1/3	1/3	2
0	0	0	3/2	1	36

V posledním řádku simplexové tabulky se již vyskytují pouze samé nezáporné hodnoty, řešení je proto optimální.

$f(x) = 3 \\cdot x_{1} + 5 \\cdot x_{2} = 3 \\cdot 2 + 5 \\cdot 6 = 36$

Speciální případy

Blandovo anticyklické pravidlo

Při řešení simplexové metody se můžeme dostat do cyklu - hodnota kriteriální funkce nestoupá a po několika iteracích se vrátíme k původnímu zadání. Tuto situaci řeší Blandovo anticyklické pravidlo, které upravuje volbu klíčového prvku takovým způsobem, aby k zacyklení nedošlo.

Jako klíčový sloupec bereme ten, který má v posledním řádku zápornou hodnotu a jeho index je nejnižší.
Pokud neexistuje jednoznačná volba, který sloupec opustí bázi, vybereme ten s nižším indexem.

Nekonečné množství řešení

Uvažujme příklad

$\\max \\; \\{2x_{1} + 4x_{2}\\}$

Za podmínek:

$x_{1} + x_{2} \\leq 4$
$x_{1} + 2x_{2} \\leq 6$
$x_{i} \\geq 0$

Převedeme na požadovaný tvar.

$\\max \\; \\{2x_{1} + 4x_{2}\\}$

Za podmínek:

$x_{1} + x_{2} + x_{3} = 4$
$x_{1} + 2x_{2} + x_{4} = 6$
$x_{i} \\geq 0$

Sestavíme simplexovou tabulku.

x₁	x₂	x₃	x₄	b
1	1	1	0	4
1	2	0	1	6
-2	-4	0	0	0

V posledním řádku jsou záporné koefienty, provedeme další iteraci.

x₁	x₂	x₃	x₄	b
1/2	0	1	-1/2	1
1/2	1	0	1/2	3
0	0	0	2	12

Dle dosud popsaných pravidel simplexová metoda končí. Ale povšimněme si, že v posledním řádku je nulový koeficient i u nebázové proměnné. To značí, že úloha má nekonečné množství řešení (řešením je celá stěna mnohostěnu). V tomto případě provedeme nad daným sloupcem (sloupci) další iteraci. Celkové řešení problému bude konvexním obalem jednotlivých řešení.

x₁	x₂	x₃	x₄	b
1	0	2	-1	2
0	1	-1	1	2
0	0	0	2	12

Celkové řešení úlohy je:

${\\mathbb{x^{*}}} = \\lambda \\cdot \\left[ \\begin{matrix}0 \\\\ 3 \\end{matrix} \\right] +(1 - \\lambda) \\cdot \\left[ \\begin{matrix} 2 \\\\ 2 \\end{matrix} \\right]$

Neomezené řešení

Další možností, na kterou lze v simplexové metodě narazit je neomezené řešení. To nastává tehdy, je-li mnohostěn řešení neomezený a vektor kriteriální může růst nadevšechny meze.

Mějme příklad

$\\max \\; \\{x_{1} + 3x_{2}\\}$

Za podmínek:

$-2x_{1} + x_{2} \\leq 1$
$x_{i} \\geq 0$

Převedeme na požadovaný tvar.

$\\max \\; \\{x_{1} + 3x_{2}\\}$

Za podmínek:

$-2x_{1} + x_{2} + x_{3} = 1$
$x_{i} \\geq 0$

Sestavíme simplexovou tabulku.

x₁	x₂	x₃	b
-2	1	1	1
-1	-3	0	0

Řešení není optimální, provedeme další iteraci.

x₁	x₂	x₃	b
-2	1	1	1
-7	0	3	12

V simplexové tabulce jsme se nyní dostali do situace, kdy by musela být hodnota klíčové prvku záporná, což není možné. Řešení je neomezené.

Jiná omezení a jejich převod na kanonický tvar

Za předpokladu, že jsou omezení zadána například pomocí rovnic (nikoliv pomocí nerovnic), nebyli bychom schopni problém řešit simplexovou metodou, protože by nám chybělo díky absenci báze základní řešení. V tomto případě se napřed musí vyřešit tzv. umělý problém.

$\\max \\{- \\sum \\; y_{i} : {\\mathbb{Ax}} + {\\mathbb{y}} = {\\mathbb{b}}; \\; {\\mathbb{x}} \\geq 0; \\; {\\mathbb{y}} \\geq 0 \\}$

Tato úloha má zřejmě totožné řešení jako úloha původní, a to pokud y = 0 . Pokud y nelze položit rovné nule, pak úloha nemá řešení.

Nejprve vyřešíme umělý problém tak, aby báze neobsahovala proměnné y. V momentě, kdy se nám to podaří, můžeme tyto proměnné z příkladu vyloučit - máme totiž simplexovou tabulku, která obsahuje základní bázi zadaného problému (nezávisí na proměnných y). Po případných úpravách nové tabulky (zajištění nulových koeficientů pod bází) již postupujeme standardním způsobem

Ukažme si uvedený postup na příkladu (zdroj: skripta profesora Štechy).

$\\max \\; \\{-3x_{1} + -2x_{2}\\}$

Za podmínek:

$x_{1} + x_{2} = 10$
$x_{1} \\geq 4$
$x_{i} \\geq 0$

Provedeme úpravu nerovnic.

$\\max \\; \\{-3x_{1} + -2x_{2}\\}$

Za podmínek:

$x_{1} + x_{2} = 10$
$x_{1} - x_{3} = 4$
$x_{i} \\geq 0$

Ze zadání nyní vidíme, že bychom klasickou simplexovou metodu nemohli nastartovat (chybí jednotková báze). Musíme proto provést dvoufázové řešení. V první fázi vyřešíme umělý problém dle vzorce uvedeného výše.

Nejprve sestavíme simplexovou tabulku.

x₁	x₂	x₃	y₁	y₂	b
1	1	0	1	0	10
1	0	-1	0	1	4
0	0	0	1	1	0

Tabulku upravíme tak, aby pod bází byly nulové koeficienty.

x₁	x₂	x₃	y₁	y₂	b
1	1	0	1	0	10
1	0	-1	0	1	4
-2	-1	1	0	0	-14

Provedeme první iteraci simplexové metody.

x₁	x₂	x₃	y₁	y₂	b
0	1	1	1	-1	6
1	0	-1	0	1	4
0	-1	-1	0	2	-6

Řešení není stále optimální (poslední řádek obsahuje záporné koeficienty), provedeme další iteraci.

x₁	x₂	x₃	y₁	y₂	b
0	1	1	1	-1	6
1	0	-1	0	1	4
0	0	0	1	1	0

Nyní jsme získali řešení umělého problému. Jak vidíme, tak toto řešení nezávisí na hodnotách proměnných y, a proto má původní problém řešení. Nyní můžeme sestavit simplexovou tabulku původního problému tak, že vypustíme sloupce proměnných y a do posledního řádku vepíšeme jeho kriteriální funkci. Tímto končí první fáze řešení, dále již postupujeme dle standardního postupu.

x₁	x₂	x₃	b
0	1	1	6
1	0	-1	4
3	2	0	0

Simplexovou tabulku upravíme tak, aby v posledním řádku pod bázovými proměnnými byly nulové koeficienty.

x₁	x₂	x₃	b
0	1	1	6
1	0	-1	4
0	0	1	-24

Z upravené tabulky vidíme, že jsme nalezli optimální řešení (pokud bychom toto štěstí neměli, tak bychom postupovali dle běžné simplexové metody).

$f(x) = -3 \\cdot x_{1} + -2 \\cdot x_{2} = -3 \\cdot 4 + -2 \\cdot 6 = -24$

Literatura

ŠTECHA, Jan. Optimální rozhodování a řízení : Přednášky. [s.l.] : Vydavatelství ČVUT, 2002. 241 s. ISBN 80-01-02083-5.