8 Podrobnosti a variace metody Dostáváme se k poslední lekci našeho textu týkající se lineárního programování, která pojed- nává o třech doposud opomíjených (a problematických) detailech simplexové metody: ˇ Jak efektivně získat výchozí přípustné bázické řešení úlohy (pomocí umělých proměn- ných). ˇ Jak účinně zamezit zacyklení simplexové metody v degenerovaných bázických řešeních (lexikografické pravidlo). ˇ Jak odhadnout celkový počet iterací simplexové metody. Zatímco pro první dva body si ukážeme dostačující řešení, ten třetí je už po dlouhá léta těžkým teoretickým problémem v optimalizaci a uspokojující odpověď na něj není známa. Stručný přehled lekce ˇ Dvoufázová simplexová metoda pro zbavení se umělých proměnných. ˇ Ukázkový výpočet dvou fází. ˇ Lexikografická varianta simplexové metody pro zabránění zacyklení. ˇ Další poznámky k variantám a složitosti metody. Petr Hliněný, FI MU 1 IA102 "OU": Podrobnosti a variace metody 8.1 Umělé proměnné; dvě fáze Jak bylo popsáno v Algoritmu 7.2, umělé proměnné přidáváme do výchozí tabulky, abychom snadno získali výchozí přípustné bázické řešení. Pochopitelně však požadu- jeme, aby ve výsledném řešení měly tyto umělé proměnné nulovou hodnotu. K odstranění umělých proměnných se přirozeně nabízejí dva postupy: ˇ "Nekonečná" cena: Umělým proměnným u přiřadíme cenu -, kde je velmi velké číslo (nepřesně bychom mohli zapsat, že = ). Pokud některá umělá proměnná vyjde ve výsledném řešení větší než nula, pak původní úloha nemá přípustné řešení. Pozor, nezapomeňme, že ceny - v nultém řádku se musíme zbavit už ve výchozí tabulce, a to přičtením -násobku i-tého řádku k nultému řádku. ˇ Dvoufázová simplexová metoda: Ve dvoufázové metodě všem umělým proměnným u nejprve přiřadíme cenu -1 a původním proměnným cenu 0. (Součet všech umělých proměnných tak mi- nimalizujeme.) Jestliže optimum této první fáze vyjde nenulové, původní úloha nemá přípustné řešení. Naopak pro nulové optimum umělé proměnné následně vypustíme a pokračujeme druhou fází v řešení původní úlohy. Petr Hliněný, FI MU 2 IA102 "OU": Podrobnosti a variace metody Dvoufázová metoda Algoritmus 8.1. Implementace dvoufázové simplexové metody Dvoufázová simplexová metoda (zapsaná simplexovou tabulkou) je založena na postupu Algoritmu 6.4 jednofázové metody s následujícími vylepšeními. 0. Vyjdeme z (už známého) kanonického tvaru úlohy v redukovaném zápise: min x0 x0 + c x = 0 A x = b x 0 1. Jako v Algoritmu 7.2, bod 1, po případném přidání umělých proměnných zapíšeme výchozí simplexovou tabulku v jednotkovém tvaru c 0 . . . 0 0 A I Au b , která vyjadřuje vztahy x0 + c x = 0 Au (x, u) T = b x, u 0 . Petr Hliněný, FI MU 3 IA102 "OU": Podrobnosti a variace metody Nyní však pro první fázi k ocenění umělých proměnných zavedeme novou účelovou funkci a pro cu = (1, c, 0) novou úlohu zapíšeme jako max - u1 - . . . - uk cu (x0, x, u) T = 0 Au (x, u) T = b x, u 0 . 0 . . . 0 - 1 . . . - 1 0 c 0 . . . 0 0 Au b . (1) Nakonec ještě musíme tabulku upravit tak, aby účelový řádek obsahoval 0 ve sloupcích umělých proměnných. 2.­5. Postupujeme v těchto bodech podle Algoritmu 6.4, ale máme na paměti, že i původní účelový řádek je vyloučen z působnosti řádkového pravidla, třebaže jinak je pokládán za běžný řádek tabulky. 6. Pokud optimální řešení první fáze má kladnou hodnotu (tedy u = 0), pak původní úloha nemá žádné přípustné řešení. 7. Jinak z výsledné tabulky první fáze vypustíme umělý účelový řádek i všechny sloupce umělých proměnných. Pokračujeme ve výpočtu druhé fáze metody už známým zůsobem od bodu 2 Algoritmu 7.2. Petr Hliněný, FI MU 4 IA102 "OU": Podrobnosti a variace metody Věta 8.2. Pokud první fáze Algoritmu 8.1 skončí s optimálním řešením s hodnotou 0, pak po vypuštění umělých proměnných v bodě 7 získáme správnou výchozí simlexovou tabulku v jednotkovém tvaru pro původní úlohu LP. Pokud naopak první fáze skončí s řešením s kladnou hodnotou, pak původní úloha LP nemá žádné přípustné řešení. Důkaz: ...... 2 Důsledek 8.3. Algoritmus 8.1 správně řeší úlohy LP. Petr Hliněný, FI MU 5 IA102 "OU": Podrobnosti a variace metody 8.2 Ukázkový výpočet Pro lepší pochopení dvoufázové simplexové metody je nejlepší se podívat na malý názorný příklad jejího použití. Příklad 8.4. Vyřešme Příklad 7.5 za pomocí dvoufázové simplexové metody. Připomeneme, že v kanonickém tvaru úloha zní max 80x1 + 50x2 20x1 + 15x2 +x3 = 1000 4x1 + 2x2 +x4 = 160 x1 -x5 = 30 x1, x2, x3, x4, x5 0 , což bohužel nedává tabulku v jednotkovém tvaru. Opět tak budeme muset nejprve zavést umělou proměnnou do poslední rovnice. Petr Hliněný, FI MU 6 IA102 "OU": Podrobnosti a variace metody Podstatou dvoufázové simplexové metody je, že optimalizace probíhá ve dvou stupních, nejprve vyloučením umělých proměnných a pak teprve původní účelovou funkcí. Proto nejprve musíme původní účelovou funkci převést na rovnost s x0 v redukovaném tvaru. -x0 + 80x1 + 50x2 = 0 20x1 + 15x2 +x3 = 1000 4x1 + 2x2 +x4 = 160 x1 -x5 = 30 x1, x2, x3, x4, x5 0 , Nyní je čas zavést umělou proměnnou x6, jejíž hodnotu budeme v první fázi minimali- zovat. max -x6 -x0 + 80x1 + 50x2 = 0 20x1 + 15x2 +x3 = 1000 4x1 + 2x2 +x4 = 160 x1 -x5 + x6 = 30 x1, x2, x3, x4, x5, x6 0 , Z poslední formulace teď sestavíme výchozí simplexovou tabulku, která již po úpravě nultého řádku bude v jednotkovém přípustném tvaru. Petr Hliněný, FI MU 7 IA102 "OU": Podrobnosti a variace metody 0 0 0 0 0 -1 0 80 50 0 0 0 0 0 20 15 1 0 0 0 1000 4 2 0 1 0 0 160 1 0 0 0 -1 1 30 - 1 0 0 0 -1 0 30 80 50 0 0 0 0 0 20 15 1 0 0 0 1000 4 2 0 1 0 0 160 1 0 0 0 -1 1 30 Všimněme si dobře, že naše tabulka obsahuje dva účelové řádky. To je přirozené, neboť si potřebujeme pamatovat původní účelovou funkci, tj. vztah proměnné x0, i novou účelovou funkci max -x6. Dále budeme postupovat pivotováním obdobně jako v Algoritmu 7.2. 1 0 0 0 -1 0 30 80 50 0 0 0 0 0 20 15 1 0 0 0 1000 4 2 0 1 0 0 160 1 0 0 0 -1 1 30 0 0 0 0 0 -1 0 0 50 0 0 80 -80 -2400 0 15 1 0 20 -20 400 0 2 0 1 4 -4 40 1 0 0 0 -1 1 30 Jak vidíme z poslední tabulky, dosáhli jsme optimálního řešení v první fázi metody, tj. máme minimální přípustnou hodnotu 0 umělé proměnné x6. Petr Hliněný, FI MU 8 IA102 "OU": Podrobnosti a variace metody Nyní vymazáním nultého řádku a sloupce umělé proměnné x6 z poslední tabulky zís- káme správnou výchozí tabulku původní úlohy v přípustném jednotkovém tvaru. 0 50 0 0 80 -2400 0 15 1 0 20 400 0 2 0 1 4 40 1 0 0 0 -1 30 0 10 0 -20 0 -3200 0 5 1 -5 0 200 0 0.5 0 0.25 1 10 1 0.5 0 0.25 0 40 0 0 0 -25 -20 -3400 0 0 1 -7.5 -10 100 0 1 0 0.5 2 20 1 0 0 0 -1 30 Výsledek výpočtu je x1 = 30, x2 = 20, x3 = 100, x4 = x5 = 0. Účelová funkce má hodnotu 3400. Porovnejte si tento výsledek s výsledkem v Příkladu 7.5. 2 Petr Hliněný, FI MU 9 IA102 "OU": Podrobnosti a variace metody 8.3 Degenerace a prevence zacyklení Jak plyne z definice, degenerovaná řešení se v průběhu simplexové metody objevují, pokud pravá strana tabulky obsahuje 0. Pak nová báze získaná iterací simplexové me- tody může odpovídat totožnému řešení (vrcholu). Jak pak ale u degenerovaných řešení zabránit zacyklení bází ve stejném vrcholu? Příklad 8.5. Ukázka zacyklení Algoritmu 7.2 simplexové metody na úloze LP. Použijme k řešení následující úlohy LP Algoritmus 7.2 s tím, že při nejednoznačné volbě sloupcového a řádkového pravidla vybereme podle nejnižšího indexu. max -20x1 + 53x2 + 41x3 - 204x4 2x1 - 11x2 - 5x3 + 18x4 +x5 = 0 -x1 + 4x2 + 2x3 - 8x4 +x6 = 0 -2x1 + 11x2 + 5x3 - 18x4 +x7 = 1 x1, x2, x3, x4 x5, x6, x7 0 Čtenář nechť si sám zkusí spočítat několik iterací simplexové metody podle popsané implementace. (Po šesté iteraci uvidí, že získal zpět jednu z předchozích tabulek.) 2 Petr Hliněný, FI MU 10 IA102 "OU": Podrobnosti a variace metody Definice 8.6. Lexikografické porovnání vektorů ("zprava"): Vektor x je lexikograficky menší než y, píšeme x y, pokud i : xi < yi j > i : xj = yj . Vektor x je lexikograficky kladný, pokud x 0. Lexikografické porovnávání již asi čtenář zná jako způsob řazení slov ve slovníku (lexikon) ­ jednotlivá písmena slov odpovídají složkám vektorů. Je třeba si však uvědomit, že naše definice porovnává zprava, tedy od konců vektorů. Význam lexikografického porovnání vektorů pro vylepšení Algoritmu 7.2 simplexové metody tkví v následujících poznatcích. Tvrzení 8.7. Mějme simplexovou tabulku, jejíž každý řádek mimo účelového je lexi- kograficky kladný. Zvolme její libovolný sloupec s s kladnou redukovanou cenou. a) Je-li v tabulce ai,s > 0, pak aplikace pivotu na ai,s lexikograficky zmenší vektor účelového řádku. b) Je-li i > 0 index řádku tabulky s lexikograficky nejmenším vektorem 1 ai,s (ai, bi), pak po aplikaci pivotu na ai,s zůstane každý řádek mimo účelového lexikograficky kladný. Důkaz: Oba závěry přímočaře plynou z definice lexikografického uspořádání a z vý- znamu pivotu. Detaily ponecháme čtenáři. 2 Petr Hliněný, FI MU 11 IA102 "OU": Podrobnosti a variace metody Algoritmus 8.8. Lexikografické simplexové metody Algoritmus 7.2 simplexové metody zpřesníme v následujících dvou bodech. ˇ V kroku 1 u výchozí tabulky přesuneme sloupce vybrané jednotkové podmatice na konec. (Tím zajistíme lexikografickou kladnost výchozí tabulky.) ˇ V kroku 4.b řádkového pravidla vybíráme řádek i > 0 tabulky s lexikograficky nejmenším vektorem 1 ai,s (ai, bi). Věta 8.9. Algoritmus 8.8 lexikografické simplexové metody vždy skončí se správným výsledkem. Důkaz: Jelikož podle Tvrzení 8.7 se každou iterací Algoritmu 8.8 lexikograficky zmenší účelový řádek tabulky, nikdy se v průběhu algoritmu stejná tabulka nezopakuje. Jak víme (Oddíl 6.4), přípustná bázická řešení jednoznačně odpovídají přípustným zápisům tabulky úlohy v jednotkovém tvaru. Proto se nezopakuje v průběhu algoritmu ani stejné bázické řešení úlohy. Takže algoritmus musí skončit v konečném čase. Správnost výsledného řešení úlohy pak plyne z Lematu 6.5. 2 Petr Hliněný, FI MU 12 IA102 "OU": Podrobnosti a variace metody 8.4 Poznámky k simplexové metodě Z předchozích Vět 8.2,8.9 plyne hlavní závěr našeho výkladu: Důsledek 8.10. Dvoufázová lexikografická simplexová metoda vždy skončí a správně nalezne optimální řešení úlohy, nebo případně potvrdí jeho neexistenci. Jak jsme již uvedli, exponenciální horní odhad počtu kroků simplexové metody prostou enumerací všech možných bázických řešení zatím neumíme nijak podstatně vylepšit. Co se týče složitosti nejhoršího případu výpočtu, je známo následující: Fakt: Pro každá běžná pravidla výběru pivota v simplexové metodě jsou známy proti- příklady vyžadující exponenciální počet kroků výpočtu. Ukázka [H.J. Greenberg, http://carbon.cudenver.edu/ hgreenbe/glossary/notes/Klee-Minty.pdf]. Pro řešení úloh LP jsou známy algoritmy s nejhorší polynomální časovou složitostí (viz Khachiyan, Karmarkar), avšak pro svou jednoduchost a rychlost v běžných praktických výpočtech se stejně nejčastěji používá simplexová metoda. Petr Hliněný, FI MU 13 IA102 "OU": Podrobnosti a variace metody Na závěr si uděláme malý přehled (nástin) některých dalších užitečných variant imple- mentace simplexové metody. Pro jejich podrobné nastudování čtenáře odkazujeme na doplňkovou literaturu. ˇ Redukovaná simplexová metoda Jedná se o paměťově úspornější variantu simplexové metody, ve které samotná jednotková podmatice I v matici A není uložena v tabulce a místo toho bázické proměnné přiřazujeme řádkům. ˇ Revidovaná simplexová metoda Její použití je výhodné, když má úloha mnohem více proměnných než nerovností. Pak vůbec nemodifikujeme výchozí tabulku ­ matici A, ale místo toho řádkové úpravy (pivoty) provádíme na (n + 1) × (n + 1) matici D, která zleva násobí A. Tabulka simplexové metody je tedy v každém kroku dána maticí D A. Výhodou je, že upravujeme pouze "malou" matici D a celá tabulka se ani nemusí držet v pracovní paměti. ˇ Duální simplexová metoda Tato metoda zjednodušeně řečeno prochází přípustná řešení duální úlohy, až najde přípustné primární řešení. Petr Hliněný, FI MU 14 IA102 "OU": Podrobnosti a variace metody