Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

## Simplexová metoda

Simplexová metoda je označení pro algoritmus řešící úlohu lineárního programování. Byla publikována v roce 1947 jedním ze zakladatelů lineárního programování američanem Georgem Dantzigem.

Idea

Omezující podmínku tedy změníme na . Toho docílíme přidáním jedné nezáporné proměnné pro každou podmínku ( je totiž ekvivalentní kde ). Tuto úpravu lze také zapsat jako . Dále předpokládáme, že matice má lineárně nezávislé řádky. Pro podmnožinu indexů označme matici , ze které ponecháme pouze sloupce, které jsou v . Analogicky pro libovolný vektor označme jako vektor, z něhož ponecháme jenom souřadnice z (má dimenzi ).

Poznamenejme jen, že bazické řešení ještě nemusí být přípustné. Je-li navíc i přípustné, říkáme mu přirozeně přípustné bazické řešení. Proměnným pro , kde je báze, říkáme bazické.

Věta

Nechť je přípustné řešení. Pak je bazické řešení, právě když sloupce matice odpovídající kladným proměnným jsou lineárně nezávislé.

Věta

Nechť je -prvková indexová množina a je regulární. Pak existuje nejvýše jedno přípustné bazické řešení ( ).

Mezi první tvrzeními jsme uvedli, že má-li daná úloha lineárního programování nějaké přípustné řešení a je-li zároveň účelová funkce na množině přípustných řešení omezená, pak existuje optimální řešení (tj. nabývá se maxima). Dá se ale dokázat dokonce následující.

Tato věta má obrovskou důležitost, neboť je jasné, že bazických řešení je jen konečně mnoho. Ukažme si fungování simplexové metody na konkrétním příkladu. Příklad

Maximalizujte funkci za omezujících podmínek ( ) a

Proof. [Řešení] Nejprve najdeme libovolné přípustné bazické řešení. Matice a vektor této úlohy jsou ze zadání

a . Vidíme tedy, že jedním z bazických řešení je . Odpovídající báze indexů je (matice je jednotková, a tedy regulární). Na základě tohoto vytvoříme tzv. simplexovou tabulku (počáteční přípustnou tabulku) tak, že vyjádříme bazické proměnné pomocí nebazických a přidáme jeden řádek s vyjádřenou účelovou funkcí pomocí nebazických proměnných.

V bodě je . Nyní budeme, jak bylo naznačeno, postupně zvyšovat hodnotu funkce , dokud nezjistíme, že jsme nalezli optimální řešení. Hodnotu funkce budeme zvětšovat zvětšením hodnoty některé nebazické (volné) proměnné.

Ponechejme a zvětšeme z 0 na (jednička je nejlepší možná, viz první rovnici a ). Pak pomocí tabulky dostaneme nové přípustné řešení, konkrétně . Z první rovnice teď vyjádříme :

a nahradíme touto rovnicí původní první rovnici . Toto řešení odpovídá bázi . Snadno zjistíme, že . Nyní se stalo, že proměnná nahradila proměnnou v bázi. Tomuto procesu říkáme, že proměnná vstoupila do báze, z ní vystoupila.

Dostáváme tak novou simplexovou tabulku

Nyní budeme zvyšovat . První rovnice neomezuje, druhá říká a třetí nyní říká (jelikož ). Položme tedy . Dostáváme nové řešení . Proměnná vstoupí do báze místo proměnná . Nová báze je .

Dostáváme další simplexovou tabulku

Zvětšíme z 0 na ( plyne ze třetí rovnice tabulky) a tím obdržíme další řešení , báze je , . Odpovídající nová simplexová tabulka je

Nyní je jasné, že libovolné zvýšení volné proměnné nebo sníží hodnotu účelové funkce. Z konstrukce simplexové metody plyne, že řešení je již optimální, neboť jsme prováděli pouze ekvivalentní rovnicové úpravy. Optimálním řešením dané úlohy je tedy bod .

Časová složitost simplexové metody je . Jeden z nejhorších případů můžeme vzít -dimenzionální krychli, která má přesně vrcholů. Na této krychli algoritmus může postupně navštívit všechny její vrcholy.

Simplexová metoda nachází uplatnění převážně při řešení optimalizačních úloh v inženýrství nebo ekonomii.