Simplexový algoritmus

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Další významy jsou uvedeny v článku 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 je ve spojitostí s vlastnostmi polytopu v N dimenzionálním euklidovském prostoru. Řešená úloha je tak i graficky interpretovatelná - hledají se vlastně co nejvíce vzdálené vrcholy polytopu.

Popis řešených úloh zpracovávaných simplexovým algoritmem[editovat | editovat zdroj]

Ú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 = {c}^T * x
vůči omezením
\mathbf{A}\mathbf{x} \le \mathbf{b}, \, \mathbf{x} \ge 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[editovat | editovat zdroj]

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 | editovat zdroj]

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} \ge 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} \ge 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
cT je transponovaný vektor cenových koeficientů

2. Získání výchozího přípustného řešení[editovat | editovat zdroj]

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 | editovat zdroj]

Ř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é[editovat | editovat zdroj]

Vystupující proměnnou určíme z čísla ti 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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Maximalizujte funkci:

\mathbf{z} = \mathbf{x}_1 + \mathbf{x}_2

vůči omezením

-\mathbf{x}_1 + \mathbf{x}_2 < 1
\mathbf{x}_1 < 3
\mathbf{x}_2 < 2
\mathbf{x}_1, \mathbf{x}_2 \ge 0

Řešení[editovat | editovat zdroj]

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ř. 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ě:
\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 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:
\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 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).

Reference[editovat | editovat zdroj]

Literatura[editovat | editovat zdroj]

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