Wikipedie

Simplexový algoritmus

algoritmus pro řešení úlohy lineárního programování
Další významy jsou uvedeny na stránce Simplexový algoritmus (rozcestník).

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 editovat

Ú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 editovat

 
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 editovat

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í editovat

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é editovat

Ř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é editovat

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 editovat

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 editovat

Maximalizujte funkci:

 

vůči omezením

 
 
 
 

Řešení editovat

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 editovat

  • 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 editovat

Citováno z „https://cs.wikipedia.org/w/index.php?title=Simplexový_algoritmus&oldid=23155838“