Simplexový algoritmus

Z Wikipedie, otevřené encyklopedie

Simplexový algoritmus (duální simplex. algoritmus) od George Dantziga je algoritmus pro řešení úlohy lineárního programování. 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.


Obsah

[editovat] Popis řešené úlohy

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


Maximalizujte účelovou funkci
\mathbf{c}^T \mathbf{x}
vůči omezením
\mathbf{A}\mathbf{x} \le \mathbf{b}, \, \mathbf{x} \ge 0


Domluvme se pro začátek, že A je matice mxn, tedy má právě m řádků a n sloupců (jinými slovy máme m omezení, každé max. n proměnných), vektor x má pak nutně (elementární algebra, násobení matic) n složek, vektor bm složek.

[editovat] Průběh algoritmu

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

  • Neomezenost úlohy l.p.
  • Degenerovanost úlohy l.p.
  • Perturbace úlohy l.p.
  • Nepřípustnost úlohy l.p.


[editovat] 1. Přepíšeme na pomocnou úlohu

  • zavedeme nové proměnné definované následovně:
\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


Kompaktně zapíšeme nově vzniklou úlohu následovně:
  • Maximalizujte \mathbf{d}^T x vzhledem k omezením \mathbf{Bx = b} a \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}})


Pozn.: Vyjádření proměnných spolu s účelovou funkcí zachovává informace o původní úloze.


[editovat] 2. Informace o nově vzniklých vektorech zapíšeme do tabulky

Jedna rovnice nové proměnné na řádek, původní proměnné píšeme nad sebe tak aby si v jednotlivých sloupcích odpovídaly. Tedy, abychom to shrnuli: máme teď každou nově zavedenou proměnnou vyjádřenou pomocí proměnných původních, přehledně zapsané do tabulky. Dosadíme-li za původní proměnné nuly, a dostaneme-li přípustné řešení, můžeme pokračovat, jinak (a toto je výše zmíněný případ nepřípustnosti úlohy l.p.) zavedeme další pomocnou proměnnou a upravíme podmínky.
Úmluva: Proměnné na levé straně jednotlivých rovnic v soustavách budeme nazývat bázovými, proměnné na pravé straně budeme nazývat nebázovými.


[editovat] 3. Tabulku nyní budeme upravovat podle účelové funkce

Budeme postupovat tak, abychom dostali řešení s vyšší hodnotou nebo dokázali, že už takové neexistuje.
Krok 1: Budeme postupně procházet jednotlivé rovnice v tabulce a vezmeme první proměnnou, která má v účelové funkci před sebou kladné znaménko a v některé z rovnic v tabulce záporné znaménko.
pozn.: Je dobré si uvědomit, že tento krok je v podstatě nedeterministický, tím myslím prakticky to, že můžeme vzít libovolnou proměnnou splňující naše požadavky a tedy postup řešení sám o sobě není jednoznačný.
Krok 2: Našli jsme tedy první proměnnou, řekněme, že si ji označíme xn, se záporným znaménkem (jestli ne, jsme hotovi, nelze maximalizovat). Podíváme se, jaká rovnice v tabulce na tuto proměnnou klade nejpřísnější omezení tak, aby řešení odpovídalo podmínkám úlohy.
Krok 3: Z této (nejpřísnější) rovnice vyjádříme xn a dosadíme do zbývajících rovnic a také do účelové funkce.
Uvědomme si, co jsme udělali: proměnnou která byla původně bázová jsme přesunuli mimo bázi, nebazovou xn jsme naopak přesunuli do báze.
Pozn.: Při určování „přísnosti“ rovnic v tabulce si uvědomme, že xi je větší nebo rovno nule pro všechny indexy.
Krok 4: Dokud můžeme přesouvat proměnnou do báze (dokud v tabulce existuje proměnná se záporným koeficientem, mající v účelové funkci kladný koeficient…) opakujeme postup od prvního kroku.
Závěr: Určíme hodnotu účelové funkce a ověříme přípustnost řešení.


[editovat] Zdroje


[editovat] Demonstrační úloha

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

[editovat] Ř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ř. 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časne 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).