Cape. 4.2: Simplexný algoritmus

Cape. 4.: Simplexný algoritmus profesor Dr. Petra Mutzel Predsedníčka pre algoritmické inžinierstvo, LS Fakulta informatiky, TU Dortmund Literatúra pre toto VO V. Chvatal: Lineárne programovanie D. ertsimas: Lineárne programovanie 4.-7. VO A&D WS 08/09 .- 6.008 Prehľad 3. Simplexný algoritmus 4. Simplexný algoritmus Zavedenie základného výmenného kurzu Tableauova metóda Štandardná simplexná Revidovaná simplexná metóda s faktorizáciou Pravidlá pre výber stĺpcov a riadkov Ukončenie Analýza doby behu V praxi sú lineárne programy riešené pomocou simplexného algoritmu [Dantzig 955]. Max 3x + x + x 3 Podlieha x + x 3 8 x + x 7 x + xx, x, x 3 0 3 4 Vizualizácia simplexného algoritmu Simplexný algoritmus Max z 3x + x + x 3 x 3 0,0, 8 0,6,8,5,6 z 8 0,6,0 z 0,5,0 7,0, z 3 Optimálne! x Zadané: LP s roztokom mnohosten Pest súhlasí s ľubovoľným rohom počiatočný roh v P. Ak nedôjde k zlepšeniu dopadu hrany na v stop: v je optimálne. 3 Poradie každej zlepšujúcej sa hrany e v. Ak e je neobmedzené, t. J. Nemá žiadny iný koncový bod zastavenia: LP je neobmedzené. 4 Nech u je druhý koncový bod e. Nastaviť vu. Prejdite na x 7,0,0 z

algoritmus

eweis: a b b A vyplýva z A nahradením r-tého stĺpca A qs. Máme AAF, kde F 0 0 s s. 0 0 r r, s r rs ā r +, s 0 0. ā ms 0 0 Pretože: Máme Ā s A, a preto je A qs s-tý stĺpec AF rovnaký A AA s AAA s A qs a všetky ostatné stĺpce zostávajú ako v A. Máme ā rs> 0, takže F je pravidelné a preto A je asis. 4 5 Ďalej, x A b F A b F x F b s 0 0 as. 0 0 ār, s F Takže pre i. m: r-tý stĺpec Ak ā je> 0: xb pi i āis br bi āis bi 0 āis najmä pre ir: xb pr r br 0 nová nezákladná premenná Ak ā je 0: xb pi i āis br bi 0 a x br 0 qs nová základná premenná So x je uskutočniteľné základné riešenie základne. ār +, s. āms 0 0. 0 0 b3 nedegenerovaný prípad: λ 0> 0: 6 7 Simplexný algoritmus Tableauova metóda Začnite s prípustným asis Iterované použitie vety: a STOP, optimálnosť b STOP, neobmedzená základná zmena: Pivot s otočným stĺpcom s a kontingenčná čiara r hodnoty objektívnej funkcie hodnoty základných premenných - c TA b A bc NT c TAANAAN t 00 t 0. t 0n znížené náklady Varianty: Tableau metóda Standard simplex Revidovaná metóda t 0 t. t n. t m0 t m. t mn Tablo je prípustné, ak t i0 0 pre všetky i. Tablo je optimálne, ak t 0j 0 pre všetky j. 3

Pravidlá výpočtu zo základného výpočtu výmenného kurzu Ā A A N: A A N A F A N F A A N A N sa líšia od A N iba v tom, že r-tý stĺpec patrí do premennej s indexom p r. Pravidlá výpočtu zo základného výmenného kurzu Ak chcete prepočítať Ā, Ā, musíte ho v podstate vynásobiť F; Výnimkou je piaty stĺpec a piaty riadok. To isté platí pre výpočet b a c. Element ā rs sa nazýva otočný prvok. Z toho vyplývajú nasledujúce pravidlá výpočtu: 0 ff fff Pozorovania simplexného algoritmu V každej iterácii je jedno základné riešenie nahradené iným. Iba veľmi malá časť tabuľky sa používa na výpočet nového základného riešenia x: potrebujete A -, bx a c, ako aj piaty stĺpec A. Myšlienka: Namiesto zakaždého, keď vypočítate celú maticu, vypočítajte iba časť, ktorá je skutočne potrebný a táto simplexná metóda 4 bola revidovaná priamo z pôvodných údajov

Revidovaná simplexná metóda 6 7 Rovnaké ako predtým pri 4, 5, N, 3, c 3, 5, 4, 0, 0, 0 x4 3 0 A, x 0, A x 5 5 4 0. Iterácia: y TA c T: y TF rx sú znížené náklady x nastáva cy T 0 0 0 0 y 0 0 c 5. Ocko Toto nám dáva nové základné a základné riešenie: x 3 x: x4 x 5, 5 N, 4, 3 3 x: Platí nasledujúce: AA staré F 3 3 5 0 0 0 0 0 t 3 a x4 von. 9. Iterácia Znížené náklady: y T 0 5 5, 0 y 0 x: 3 5, 0 0 x 4: 0 5, 0 5 0 0 x 3: 4 5, 0 3 4 x 3 v t 3 a x 5 v . A d a: x 3 3 x: 0 d d 4 3 x x 5 3 7 6 3 3 0, 3, N, 4, 5 7 6 x: 3 0 Platí nasledujúce: A Starý F 0 3 4 30 3 5

Porovnanie runtime tablo s revidovanou simplexnou metódou Runtime na iteráciu pre riedko osídlené matice: Odhad podľa Chvatal-uch: Predpoklad: stĺpce a riadky tabla obsahujú m/alebo n/nenulové prvky; Faktorizačné matice k: m nenulových prvkov; ETA stĺpce: cca 5% -50% hustý FTRAN: cca 0m, TRAN: cca 0m Výber vstupných premenných: Výpočet výstupných premenných: m Aktualizácia x a: m Celkový čas revidovaného simplexu: 3m + 0n Celkový čas Tableau method: mn/4 8