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

- vůči omezením

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 b má m 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ě:
- Kompaktně zapíšeme nově vzniklou úlohu následovně:
-
- Maximalizujte
vzhledem k omezením
a 
- Maximalizujte
- Kde:
-
- je jednotková matice (identity)
- 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:

vůči omezením
[editovat] Ř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č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:
- 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).























