Simplexový algoritmus

Simplexový algoritmus nebo také simplexová metoda je algoritmus pro řešení úlohy lineárního programování, který byl poprvé popsán George Dantzigem. Algoritmus efektivně prohledává tzv. základní řešení úloh lineárního programování, kterých je konečný počet a hledá mezi nimi řešení optimální. Optimální řešení je takové základní řešení, které poskytuje nejlepší hodnotu účelové funkce. Metoda souvisí s vlastnostmi polytopu v N dimenzionálním euklidovském prostoru. Řešená úloha je tak i graficky interpretovatelná – hledají se vlastně co nejvzdálenější vrcholy polytopu.

Popis řešených úloh zpracovávaných simplexovým algoritmem

Úloha lineárního programování je taková úloha, která hledá extrém zadané kriteriální neboli účelové funkce při zadaných omezujících podmínkách. V ekonomických úlohách jsou přidány podmínky nezápornosti proměnných modelů z důvodu interpretace proměnných.

Mějme úlohu lineárního programování ve standardním tvaru:

Maximalizujte účelovou funkci z$\mathbf {z} =\mathbf {c} ^{T}\mathbf {x}$

vůči omezením $\mathbf {A} \mathbf {x} \leq \mathbf {b} ,\,\mathbf {x} \geq 0$

• A je matice strukturních koeficientů o velikosti m řádků x n sloupců (jinými slovy máme m omezení, každé max. n proměnných),
• vektor x je vektor proměnných modelu s n složkami,
• vektor b je vektor omezení nebo také vektor pravých stran a má m složek.
• ${c}^{T}$ je transponovaný vektor cenových koeficientů

Průběh algoritmu klasické simplexové metody

Algoritmus simplexové metody

Následující popis simplexového algoritmu neřeší speciální případy. Těmi jsou zejména:

• Neomezenost úlohy
• Degenerovanost úlohy
• Perturbace úlohy
• Nepřípustnost úlohy

1. Start – přepíšeme na ekvivalentní pomocnou úlohu

Zavedeme nové proměnné, tzv. přídatné proměnné, které vyrovnají omezující podmínky z nerovnic na rovnice. Přídatné proměnné definujeme následujícím způsobem:

$\mathbf {x} _{n i}=\mathbf {b} _{i}-\sum _{j=1}^{n}\mathbf {a} _{ij}\mathbf {x} _{j}$

$\mathbf {x} _{n i}\geq 0,i=1...m$

Úlohu přepíšeme na tzv. ekvivalentní soustavu rovnic ve tvaru:

Maximalizujte $\mathbf {d} ^{T}x$ vzhledem k omezením:

$\mathbf {Bx=b}$

$\mathbf {x} \geq 0$

kde:

$\mathbf {B} =(\mathbf {A} |\mathbf {I} ),\mathbf {I}$ – je jednotková matice (identity)

$\mathbf {d} =(\mathbf {c} |\mathbf {0} )$

$\mathbf {x} =(\mathbf {x_{1}x_{2}...x_{n}|x_{n 1}...x_{n m}} )$

Při výpočtu je vhodné používat zápis v tzv. simplexové tabulce, která má následující výchozí tvar:

$A\,\!$	$I\,\!$	$b\,\!$
$-c^{T}\,\!$	$0\,\!$	$0\,\!$

kde:

A je matice strukturních koeficientů velikosti m x n

I je jednotková matice řádu m x m

b je vektor pravých stran o velikosti m x 1

c^T je transponovaný vektor cenových koeficientů

2. Získání výchozího přípustného řešení

Pokud položíme všechny přídatné proměnné v jednotlivých omezeních pravým stranám těchto omezení a všechny ostatní proměnné se budou rovnat nule, získáme výchozí přípustné řešení.

Nenulové proměnné nazveme tzv. bazickými proměnnými, nulové proměnné jsou tzv. nebazické. Dá se používat i termínů základní a nezákladní proměnné.

3. Test optima a výběr vstupující proměnné

Řešení je optimální právě tehdy, pokud v maximalizační úloze platí, že všechny redukované a stínové ceny jsou větší rovno nule nebo v minimalizační úloze platí, že všechny redukované a stínové ceny jsou menší rovno nule. Pokud je daná podmínka splněna, řešení je optimální a hodnota účelové funkce je nejvyšší možná.

Pokud je uvedená podmínka v daném typu úlohy porušena, řešení není optimální, tedy hodnotu účelové funkce lze zlepšit. Vybereme proměnnou, která nejvíce porušuje kritérium optimality, odstraníme ji z báze a nahradíme výhodnější proměnnou.

Nová vstupující proměnná se nachází v tzv. klíčovém řádku k, kde $x_{k}$ určíme následujícím způsobem:

v maximalizační úloze k je index řádku, kde $x_{k}=\min z_{j},j=1..n\,\!$

v minimalizační úloze k je index řádku, kde $x_{k}=\max z_{j},j=1..n\,\!$

4. Výběr vystupující proměnné

Vystupující proměnnou určíme z čísla t_i přiřazenému každému omezení s $a_{ik}>0$, kde k je index klíčového sloupce. Vybíráme

$\min t_{i}={\frac {b_{i}}{a_{ik}}}$

index i je index klíčového řádku, který označíme q. Potom $a_{qk}$ je klíčový prvek.

5. Transformace tabulky

Tabulku upravíme pomocí Gaussovy eliminační metody, kdy pro klíčový řádek platí:

• $a_{qk}^{new}=1$
• $a_{qj}^{new}={\frac {a_{qj}}{a_{qk}}}$
• $b_{i}^{new}={\frac {b_{i}}{a_{qk}}}$

a ostatní řádky upravíme tak, aby v klíčovém řádku vznikl jednotkový vektor s jedničkou v klíčovém řádku. Gaussova eliminace se týká i vektoru pravé strany a řádku účelové funkce v simplexové tabulce.

Po transformaci pokračujeme na test optima.

Tabulka se po transformaci mění výpočtem na následující tvar:

$B_{s}^{-1}A\,\!$	$B_{s}^{-1}\,\!$	$B_{s}^{-1}b\,\!$
$c_{B}^{T}B_{s}^{-1}A-c^{T}\,\!$	$c_{B}^{T}B_{s}^{-1}\,\!$	$c_{B}^{T}B_{s}^{-1}b\,\!$

kde

$B_{s}^{-1}\,\!$ je inverzní matice báze

$c_{B}^{T}\,\!$ je transponovaný vektor cen bazických proměnných

Demonstrační úloha

Maximalizujte funkci:

$\mathbf {z} =\mathbf {x} _{1} \mathbf {x} _{2}$

vůči omezením

$-\mathbf {x} _{1} \mathbf {x} _{2}\leq 1$

$\mathbf {x} _{1}\leq 3$

$\mathbf {x} _{2}\leq 2$

$\mathbf {x} _{1},\mathbf {x} _{2}\geq 0$

Řešení

1. Zavedeme nové proměnné a zapíšeme do tabulky:

$\mathbf {x} _{3}=1-(-1\mathbf {x} _{1} 1\mathbf {x} _{2})$

$\mathbf {x} _{4}=3-(1\mathbf {x} _{1} 0\mathbf {x} _{2})$

$\mathbf {x} _{5}=2-(0\mathbf {x} _{1} 1\mathbf {x} _{2})$

$z'=\mathbf {x} _{1} \mathbf {x} _{2}$

Po úpravě:

$\mathbf {x} _{3}=1 1\mathbf {x} _{1}-1\mathbf {x} _{2}$

$\mathbf {x} _{4}=3-1\mathbf {x} _{1}$

$\mathbf {x} _{5}=2-1\mathbf {x} _{2}$

$z'=\mathbf {x} _{1} \mathbf {x} _{2}$

2. Hledáme kandidáty do báze:

1. Vezměme si např. x₁ – mohli bychom i x₂ (obě proměnné mají v účelové funkci kladné a v tabulce záporné znaménko), ale je to pomalejší.

2. Jediná rovnice, která nám klade na x₁ omezení je druhá rovnice. Podle ní je x₁ maximálně 3. (Kdybychom zvolili x₂, nejpřísnější omezení by plynulo z první rovnice: x₂ je max. 1)

3. vyjádříme x₁ z druhé rovnice, dosadíme x₁ do zbývajících rovnic a do účelové funkce. Dopracujeme se k následující soustavě:

$\mathbf {x} _{1}=3-\mathbf {x} _{4}$

$\mathbf {x} _{3}=4-\mathbf {x} _{4}-\mathbf {x} _{2}$

$\mathbf {x} _{5}=2-\mathbf {x} _{2}$

$z'=3-\mathbf {x} _{4} \mathbf {x} _{2}$

4. Nyní nám již zbývá jediná proměnná s kladným znaménkem v účelové funkci a současně se záporným znaménkem v rovnicích z tabulky – je to x₂

5. Postupujme obdobně jako před chvílí. Nejpřísnější omezení klade poslední rovnice – x₂ je podle ní max. dva. Vyjádřeme tedy x₂ z poslední rovnice a dosaďme do účelové funkce a ostatních rovnic:

$\mathbf {x} _{2}=2-\mathbf {x} _{5}$

$\mathbf {x} _{3}=2-\mathbf {x} _{4} \mathbf {x} _{5}$

$\mathbf {x} _{1}=3-\mathbf {x} _{4}$

$z'=5-\mathbf {x} _{4}-\mathbf {x} _{5}$

6. Další analogická úprava není možná – účelová funkce nemůže být dále maximalizována. Víme (předpoklady úlohy), že x₄ ani x₅ není menší, než nula. Maximální hodnota účelové funkce z’ je menší, nejvýše rovna 5 pro vektor (x₁,…,x₅) = (3,2,2,0,0).

Literatura

• Lagová M., Jablonský J., Lineární modely, Praha, 2004, nakladatelství Oeconomica, ISBN 80-245-0816-8
• Jablonský J., Programy pro matematické modelování, Praha, 2007, nakladatelství Oeconomica, ISBN 978-80-245-1178-8
• Jablonský J., Operační výzkum – kvantitativní metody pro ekonomické rozhodování, Praha, 2002, Professional Publishing, ISBN 80-86419-42-8

Externí odkazy

• Obrázky, zvuky či videa k tématu simplexový algoritmus na Wikimedia Commons
• Aplet využívající simplexového algoritmu

Autoritní data	PSH: 11411 GND: 4181488-5 LCCN: sh85122745 NLI: 987007546249105171