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
- vůči omezením
- 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.
- je transponovaný vektor cenových koeficientů
Průběh algoritmu klasické simplexové metody
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Simplex_algorithm_diagram.jpg/220px-Simplex_algorithm_diagram.jpg)
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:
Úlohu přepíšeme na tzv. ekvivalentní soustavu rovnic ve tvaru:
- Maximalizujte vzhledem k omezením:
kde:
- – je jednotková matice (identity)
Při výpočtu je vhodné používat zápis v tzv. simplexové tabulce, která má následující výchozí tvar:
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
- cT 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 určíme následujícím způsobem:
- v maximalizační úloze k je index řádku, kde
- v minimalizační úloze k je index řádku, kde
4. Výběr vystupující proměnné
Vystupující proměnnou určíme z čísla ti přiřazenému každému omezení s , kde k je index klíčového sloupce. Vybíráme
index i je index klíčového řádku, který označíme q. Potom je klíčový prvek.
5. Transformace tabulky
Tabulku upravíme pomocí Gaussovy eliminační metody, kdy pro klíčový řádek platí:
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:
kde
- je inverzní matice báze
- je transponovaný vektor cen bazických proměnných
Demonstrační úloha
Maximalizujte funkci:
vůči omezením
Řešení
1. Zavedeme nové proměnné a zapíšeme do tabulky:
- Po úpravě:
2. Hledáme kandidáty do báze:
- 1. Vezměme si např. x1 – mohli bychom i x2 (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 x1 omezení je druhá rovnice. Podle ní je x1 maximálně 3. (Kdybychom zvolili x2, nejpřísnější omezení by plynulo z první rovnice: x2 je max. 1)
- 3. vyjádříme x1 z druhé rovnice, dosadíme x1 do zbývajících rovnic a do účelové funkce. Dopracujeme se k následující soustavě:
- 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 x2
- 5. Postupujme obdobně jako před chvílí. Nejpřísnější omezení klade poslední rovnice – x2 je podle ní max. dva. Vyjádřeme tedy x2 z poslední rovnice a dosaďme do účelové funkce a ostatních rovnic:
- 6. Další analogická úprava není možná – účelová funkce nemůže být dále maximalizována. Víme (předpoklady úlohy), že x4 ani x5 není menší, než nula. Maximální hodnota účelové funkce z’ je menší, nejvýše rovna 5 pro vektor (x1,…,x5) = (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