7 Výpočet simplexové metody V této přednášce si ukážeme krok za krokem základní způsob implementace simplexové metody pomocí "pivotování" simplexové tabulky (Oddíl 6.4). To znamená, že od teorie přejdeme úplně k praktickým dovednostem a zkušenostem s řešením úloh LP. Některé pokročilejší úkony, jako přidávání umělých proměnných pro získání výchozího řešení, nebo použití lexikografického pravidla pro prevenci možného zacyklení, budou doplněny a probrány hlouběji v příští lekci. Stručný přehled lekce ˇ Ilustrační výpočet simplexové metody. ˇ Sloupcové a řádkové pravidlo, pivotování. ˇ Formální popis implementace simplexové metody. ˇ Příklady různých výpočtů. Petr Hliněný, FI MU 1 IA102 "OU": Výpočet simplexové metody 7.1 Ilustrační výpočet Vraťme se k základnímu Příkladu 3.1 s bramborovými lupínky a hranolky. Po vynáso- bení 10 (jen pro zbavení se necelých čísel) zadání zní: max 80x1 + 50x2 20x1 + 15x2 1000 4x1 + 2x2 160 x1, x2 0 Tuto snadnu úlohu si nyní vyřešíme v podrobných komentovaných krocích. ˇ Převedeme úlohu na kanonický tvar max 80x1 + 50x2 20x1 + 15x2 +x3 = 1000 4x1 + 2x2 +x4 = 160 x1, x2, x3, x4 0 Petr Hliněný, FI MU 2 IA102 "OU": Výpočet simplexové metody ˇ Chceme maximalizovat funkci 80x1 + 50x2, neboli min x0 , kde x0 + 80x1 + 50x2 = 0 . Máme (s implicitní nezáporností proměnných) tedy soustavu rovnic x0 + 80x1 + 50x2 = 0 20x1 + 15x2 +x3 = 1000 4x1 + 2x2 +x4 = 160 , zapsáno maticově 1 80 50 0 0 0 20 15 1 0 0 4 2 0 1 x0 x = 0 1000 160 . ˇ V simplexové tabulce (účelový řádek proměnné x0 nahoře) a s vyznačenou jed- notkovou bází vypadá naše úloha takto: 1 80 50 0 0 0 0 20 15 1 0 1000 0 4 2 0 1 160 Tato tabulka ukazuje výchozí bázické řešení x3 = 1000, x4 = 160, x1, x2 = 0 (x0 = 0), které je (naštěstí) přípustné. Pro jednoduchost už dále nebudeme účelový (nultý) řádek do tabulky zapisovat. Petr Hliněný, FI MU 3 IA102 "OU": Výpočet simplexové metody ˇ Přejdeme k sousední bázi, čili vyměníme jeden sloupec ve vyznačené bázi. Přesněji nejprve vybereme nový sloupec do báze pomocí sloupcového pravidla a pak vybereme stávající sloupec báze k odebrání pomocí řádkového pravidla. Nakonec pou- žijeme běžné maticové operace k tomu, abychom novou bázi ukázali jako jednotkovou. ­ Sloupcové pravidlo: Vybereme sloupec s, který má v nultém řádku největší z kladných redukovaných cen. Zde s = 1. ­ Řádkové pravidlo: Vybereme řádek i > 0, který splňuje ais > 0 a zároveň dosahuje nejmenší z podílů bi/ais. (Uvědomme si, že vždy bi 0.) Zde i = 2. ­ Provedeme pivot na prvku ai,s matice: Řádkovými úpravami matice (jako v Gaussově eliminaci) sloupec s upravíme tak, aby obsahoval samé nuly (včetně nultého řádku) mimo ai,s = 1. 80 50 0 0 0 20 15 1 0 1000 4 2 0 1 160 - 0 10 0 -20 -3200 0 5 1 -5 200 1 0.5 0 0.25 40 Co nám nová tabulka ukazuje o současném bázickém řešení x? x0 = -3200 c x = 3200, x1 = 40, x3 = 200, x2 = x4 = 0 (protože nejsou v bázi). Petr Hliněný, FI MU 4 IA102 "OU": Výpočet simplexové metody ˇ Opět vybereme podle téhož sloupcového pravidla sloupec s = 2 a podle řádko- vého pravidla řádek i = 1. Novým pivotem získáme: 0 10 0 -20 -3200 0 5 1 -5 200 1 0.5 0 0.25 40 - 0 0 -2 -30 -3600 0 1 0.2 -1 40 1 0 -0.1 0.75 20 Nyní již sloupcové pravidlo nelze použít, neboť redukované ceny v nultém řádku jsou všechny nekladné. To znamená, že jsme našli optimální řešení xo úlohy x0 = -3600 c xo = 3600, xo 1 = 40, xo 2 = 20, xo 3 = xo 4 = 0 (protože nejsou v bázi). 2 Poznámka k řádkovému pravidlu: Co by se stalo kdybychom vybrali jiný řádek než s nejmenším podílem bi/ais? Zkusme si to v předchozí úloze: 0 10 0 -20 -3200 0 5 1 -5 200 1 0.5 0 0.25 40 - -20 0 0 -25 -4000 -10 0 1 -7.5 -200 2 1 0 0.5 80 Jak vidíme, nové bázické řešení obsahuje x3 = -200 < 0, takže není přípustné. Výběr řádku i je volen dle uvedeného řádkového pravidla právě proto, abychom dostali ve všech složkách pravé strany b nezáporné, tj. přípustné hodnoty. Petr Hliněný, FI MU 5 IA102 "OU": Výpočet simplexové metody 7.2 Popis implementace Tvrzení 7.1. Mějme pro danou úlohu LP zápis simplexovou tabulkou v přípustném jed- notkovém tvaru. Pokud přejdeme k nové bázi tabulky získané ze stávající báze záměnou některého bázického sloupce sloupcem s kladnou redukovanou cenou, tak získáme buď stejné degenerované bázické řešení nebo řešení se striktně lepší účelovou hodnotou. Algoritmus 7.2. Implemenace Algoritmu 6.4 simplexové metody Následuje jednofázová metoda bez prevence zacyklení v degenerovaných řešeních. 0. Úlohu převedeme do základního a pak do kanonického tvaru max c x pro A x = b, x 0 přidáním doplňkových proměnných ke každé nerovnici (Lemma 6.1). Dále přidáme pro redukovaný zápis novou účelovou proměnnou x0 vztahem min x0 pro x0 + c x = 0 . 1. Zapíšeme maticově předchozí vztahy a odpovídající simplexovou tabulkou 1 c 0 A x0 x = 0 b - 1 c | 0 0 A | b . Horní (nultý) řádek tabulky nazýváme účelovým řádkem, jeho prvky jsou redu- kované ceny proměnných, sloupec b nazýváme pravou stranou a zbytek tabulky nazýváme levou stranou. V dalším textu již budeme tabulku zapisovat bez nultého účelového sloupce. Petr Hliněný, FI MU 6 IA102 "OU": Výpočet simplexové metody Dále získáme výchozí přípustné bázické řešení. K tomu potřebujeme tabulku v přípustném jednotkovém tvaru. Často tabulka již v takovém tvaru je (doplňkové proměnné nám přidají jednotkovou podmatici a pravé strany obvykle bývají kladné), ale jinak uplatníme následující postup: a) Všechny rovnice se zápornou pravou stranou vynásobíme -1. (Aby bylo vý- chozí bázické řešení přípustné.) b) Pro každý chybějící jednotkový vektor ei v tabulce na levé straně přidáme umělou proměnnou ui 0 s cenou -, kde je velmi velká konstanta, formálně = . Zapíšeme vzniklou výchozí ("umělou") tabulku v jednotkovém tvaru c . . . 0 - 0 A I Au b , která vyjadřuje vztahy: x0 + c x - u = 0 Au (x, u) T = b x, u 0 Petr Hliněný, FI MU 7 IA102 "OU": Výpočet simplexové metody c) Upravíme tabulku tak, aby i nultý účelový řádek obsahoval redukované ceny 0 ve sloupcích jednotkové podmatice I: Přičteme násobky řádků příslušných k jednotlivým jednotkovým vektorům I k účelovému řádku. 2. Jsou-li všechna čísla v účelovém řádku tabulky nekladná, máme optimální řešení, viz Tvrzení 6.8. Pokud však je v bázi stále ještě zůstává některá umělá proměnná, původní úloha nemá žádné přípustné řešení. 3. Je-li v tabulce sloupec s takový, že cs = a0s > 0 a ais 0 pro všechna i > 0, úloha nemá optimální řešení z důvodu neomezenosti. 4. Přejdeme k sousední bázi: a) Sloupcové pravidlo vybere sloupce s s nejvyšší kladnou hodnotou redukované ceny v účelovém řádku, tj. ve směru nejvyššího přírustku účelové funkce. b) Řádkové pravidlo vybere řádek i > 0 s nejmenší hodnotou podílu bi/ais pro ais > 0, což je nutné pro zachování nezápornosti pravé strany. c) Přejdeme k sousední bázi aplikací tzv. pivotu na prvku ais: ˇ Pro každé j = i, od j-tého řádku odečteme ajs/ais-násobek i-tého, ˇ i-tý řádek vydělíme číslem ais. (V nové bázi sloupec s nahradí sloupec původního jednotkového vektoru ei .) 5. Vrátíme se v cyklu do bodu 2. Petr Hliněný, FI MU 8 IA102 "OU": Výpočet simplexové metody 7.3 Různé příklady výpočtů Příklad 7.3. Dokončení výpočtu Příkladu 6.10. max 387x1 + 524x2 + 667x3 15x1 + 20x2 + 20x3 1000 63x1 + 126x2 + 133x3 5000 x1, x2, x3 0 Zmíněný příklad vedl na následující výchozí simplexovou tabulku, která je v přípustném jednotkovém tvaru. 387 524 667 0 0 0 15 20 20 1 0 1000 63 126 133 0 1 5000 Jsme v Algoritmu 7.2 v bodě 4. Užitím sloupcového pravidla vybereme třetí sloupec pro vstup do báze a pak řádkovým pravidlem druhý řádek pro opuštění báze. Výsledkem je: 71.05 -107.9 0 0 -5.015 -25075 5.526 1.053 0 1 -0.15 248.1 0.4737 0.9474 1 0 0.00752 37.6 Petr Hliněný, FI MU 9 IA102 "OU": Výpočet simplexové metody V další iteraci vybereme první sloupec a první řádek a výsledkem je tabulka: 0 -120.9 0 -12.84 -3.08 -28265 1 0.19 0 0.18 -0.027 44.88 0 0.8571 1 -0.0857 -0.02 16.33 Z poslední tabulky vidíme (viz Algoritmus 7.2 v bodě 2), že optimálním řešením je výroba (zhruba) 448.8 kg hranolků, 0 kg slaných lupínků a 163.3 kg paprikových lupínků se ziskem 28265 Kč. 2 Příklad 7.4. Ukázka výpočtu neomezené úlohy LP: max x1 + x2 + x3 -x1 - x2 + 2x3 2 -x1 + 2x2 - x3 4 2x1 - x2 - x3 6 x1, x2, x3 0 Petr Hliněný, FI MU 10 IA102 "OU": Výpočet simplexové metody Již dobře známým postupem přes kanonický tvar úlohy zapíšeme výchozí simplexovou tabulku v jednotkovém přípustném tvaru 1 1 1 0 0 0 0 -1 -1 2 1 0 0 2 -1 2 -1 0 1 0 4 2 -1 -1 0 0 1 6 . Dále postupujeme v intencích Algoritmu 7.2 následovně: 0 1.5 1.5 0 0 -0.5 -3 0 -1.5 1.5 1 0 0.5 5 0 1.5 -1.5 0 1 0.5 7 1 -0.5 -0.5 0 0 0.5 3 0 0 3 0 -1 -1 -10 0 0 0 1 1 1 12 0 1 -1 0 0.66 0.33 4.66 1 0 -1 0 0.33 0.66 5.33 Dobře si nyní všimněme poslední tabulky. V ní se stále ještě neuplatní bod 2 Algo- ritmu 7.2, stále nemáme optimální řešení díky kladné redukované ceně ve třetím sloupci. Poprvé mezi našimi příklady však vidíme uplatnění bodu 3 algoritmu ­ ve třetím sloupci jsou všechny další koeficienty nekladné, takže optimální řešení naší úlohy neexistuje z důvodu neomezenosti. 2 Petr Hliněný, FI MU 11 IA102 "OU": Výpočet simplexové metody Příklad 7.5. Vyřešme náš starý známý Příklad 3.1 o lupíncích a hranolcích s dodateč- ným požadavkem na výrobu alespoň 30 kg lupínků. Podmínky jsou zapsány max 80x1 + 50x2 20x1 + 15x2 1000 4x1 + 2x2 160 x1 30 . V kanonickém tvaru pak ú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. Jsme Algoritmu 7.2 v bodě 1 (a,b). Budeme proto muset přidat jednu umělou proměnnou u = x6 následovně: Petr Hliněný, FI MU 12 IA102 "OU": Výpočet simplexové metody max 80x1 + 50x2 - x6 20x1 + 15x2 +x3 = 1000 4x1 + 2x2 +x4 = 160 x1 -x5 + x6 = 30 x1, x2, x3, x4, x5, x6 0 , Zavedení umělé proměnné x6 pochopitelně mění­rozšiřuje množinu přípustných řešení úlohy, takže v konečném důsledku musíme vliv x6 z úlohy vyloučit. Toho dosáhneme určením "ob- rovské" záporné ceny - - pro x6. Nyní již můžeme sestavit výchozí tabulku v přípustném jednotkovém tvaru. Nezapo- meňme však podle Algoritmu 7.2 v bodě 1 (c) nejprve upravit nenulovou hodnotu redukované ceny x6 přičtením vhodného násobku posledního řádku. 80 50 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 80 + 50 0 0 - 0 30 20 15 1 0 0 0 1000 4 2 0 1 0 0 160 1 0 0 0 -1 1 30 Petr Hliněný, FI MU 13 IA102 "OU": Výpočet simplexové metody Dále již postupujeme běžným způsobem simplexové metody. 80 + 50 0 0 - 0 30 20 15 1 0 0 0 1000 4 2 0 1 0 0 160 1 0 0 0 -1 1 30 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 0 0 0 -25 -20 100 - -3400 0 0 1 -7.5 -10 10 100 0 1 0 0.5 2 -2 20 1 0 0 0 -1 1 30 Z poslední tabulky vidíme optimální řešení ­ vyrobit x1 = 30 kg lupínků a x2 = 20 kg hranolků. Hodnota x3 > 0 nám říká, že v první nerovnosti úlohy ještě zbývá do rovnosti rezerva x3, neboli v konkrétní formulaci nám zbývá 10 kg brambor. 2 Petr Hliněný, FI MU 14 IA102 "OU": Výpočet simplexové metody