LINEÁRNÍ PROGRAMOVÁNÍ Lineární programování je druh matematického programování. Matematický model se skládá z: 1. účelové funkce 2. omezujících podmínek (vlastní omezení a podmínky nezápornosti) Účelová funkce i omezující podmínky jsou vyjádřeny lineárními vztahy s konstantními koeficienty u jednotlivých proměnných i s konstantními pravými stranami soustavy omezení. Základní pojmy Vektor řešení x = ( x1 , x 2 ,...x n ) označuje řešení optimalizačního problému. Při určování optimální výrobní struktury podniku složky vektoru řešení představují např. množství jednotlivých druhů výrobků. Optimální je taková struktura výroby, při které rozhodující veličina (např.zisk, náklady…) nabývá extrémní hodnoty (maximální nebo minimální). Tuto rozhodující veličinu vyjadřujeme pomocí účelové funkce. Účelová funkce z = f (x ) je funkce vektoru řešení. Při hledání optimální výrobní struktury představuje účelová funkce např. závislost zisku na množství jednotlivých výrobků, přičemž hledáme taková množství výrobků, která zaručují maximální zisk. Maximum nebo minimum – extrém – účelové funkce hledáme za určitých omezujících podmínek, které ovlivňují velikost složek vektoru řešení. Jednou z omezujících podmínek při hledání optimální struktury je vztah mezi disponibilními zdroji nutných k výrobě a spotřebou na jednotlivé výrobky. Tyto omezující podmínky nazýváme omezující podmínky vlastní a obecně je lze zapsat jako g i (x ) ≤ bi , g i (x ) ≥ bi nebo g i (x ) = bi , kde g i (x ) je daná funkce vyjadřující např. závislost spotřeby jednotlivého zdroje na vyrobeném množství výrobků, a bi jsou dané konstanty představující např. disponibilní množství surovin. Další omezující podmínky jsou podmínky nezápornosti a platí pro všechny složky vektoru řešení. Matematická formulace obecné úlohy lineárního programování (LP) Na množině nezáporných řešení soustavy lineárních rovnic a11 x1 + a12 x 2 + ... + a1n x n = b1 a 21 x1 + a 22 x 2 + ... + a 2 n x n = b2 M
M
M M a m1 x1 + a m 2 x 2 + ... + a mn x n = bm najděte extrém lineární funkce z = c1 x1 + c 2 x 2 + ... + c n x n , kde
a ij (i = 1,2,..., m; j = 1,2,..., n ) jsou strukturní koeficienty
bi (i = 1,2,..., m ) jsou požadavková čísla c j ( j = 1,2,..., n ) jsou ceny
Zjednodušený zápis matematického modelu úlohy LP Ax = b, x ≥ o, z = c T x → extrém 1
© Jana Friebelová
A … matice typu (m × n ) , jejíž prvky tvoří koeficienty a ij (i = 1,2,..., m; j = 1,2,..., n ) b c x o
… m-členný vektor požadavků … n-členný vektor cen … n-členný vektor neznámých (proměnných) … n-členný nulový vektor
Postup při sestavování modelu 1. určit, co je výsledkem výpočtu (co představují složky vektoru x a v jakých měrných jednotkách jsou uváděny) 2. rozhodnout, z jakého hlediska řešení dané úlohy optimalizovat, tzn. zformulovat účelovou funkci 3. věcně a matematicky formulovat vlastní omezující podmínky Příklad 1 Výrobce čajů má k dispozici 3 kg sušené máty a 1,5 kg sušené třezalky. Má možnost vyrábět dva druhy bylinných čajů, a to čistý mátový čaj nebo směs máty a třezalky v poměru 3:2. Byliny jsou plněny do nálevových sáčků po 10 g . Při výrobě je nutné počítat s odpadem u máty 5% a u třezalky 8%. Čistého mátového čaje prodá maximálně 100 sáčků. Zisk z jednoho sáčku čisté máty je 2 Kč a z jednoho sáčku směsi 3 Kč. Kolik sáčků každého druhu má výrobce vyrobit, aby zisk byl maximální.
x1 … počet sáčků čisté máty (ks) x 2 … počet sáčků směsi (ks) Disponibilní množství čistých bylin je: máta … 3000 g − 150 g = 2850 g třezalka … 1500 g − 120 g = 1380 g Vlastní omezující podmínky: 10 x1 + 6 x 2 ≤ 2850 4 x 2 ≤ 1380 x1 ≤ 100 Podmínky nezápornosti: x1 ≥ 0 x2 ≥ 0 Účelová funkce: z = 2 x1 + 3x2 → max Modely LP s binárními proměnnými Binární proměnné nabývají pouze hodnot 0 nebo 1. Vyjadřují skutečnost, že nějaký jev nastal či nikoliv; umožňují matematicky vyjádřit některé logické vztahy v modelovaném systému. Příklad 2 Stavební podnik si může vybrat z 5 staveb nejvýše 3 tak, aby měsíční náklady na tyto stavby nepřekročily 200 mil. Kč. Předpokládané měsíční náklady na tyto stavby a roční výnosy z nich jsou uvedeny v tab. 1 (v mil. Kč). 2
© Jana Friebelová
Tab. 1 Stavba S1 Náklady 28 Výnosy 56
S2 42 82
S3 66 104
S4 33 63
S5 78 120
Pro které stavby se má podnik rozhodnout, aby předpokládané celkové roční výnosy ze staveb byly co největší, jestliže nemůže současně vybrat stavby S2 a S4, ale má zájem alespoň na jedné stavbě ze staveb S1, S3, S4. x1 , x 2 , x3 , x 4 , x5 …proměnné, které indikují výběr staveb S1, S2, S3, S4 a S5 . Jsou to binární proměnné, které nabývají hodnoty 1, pokud stavba bude realizována a hodnoty 0 pokud nebude realizována x j = {0,1} pro j = 1,2,3,4,5
Vlastní omezující podmínky x1 + x 2 + x3 + x 4 + x5 ≤ 3 28 x1 + 42 x 2 + 66 x3 + 33 x 4 + 78 x5 ≤ 200 x2 + x4 ≤ 1 x1 + x3 + x 4 ≥ 1 Podmínky nezápornosti nejsou uvedeny, neboť binární proměnná nabývá hodnoty 0 a 1. Účelová funkce z = 56 x1 + 82 x 2 + 104 x3 + 63x 4 + 120 x5 → max . Obecné vlastnosti řešení úloh LP Úloha LP je tvořena omezujícími podmínkami vlastními, podmínkami nezápornosti a účelovou funkcí. Při řešení úlohy LP je soustava omezujících podmínek
převedena na
soustavu m rovnic o n neznámých (n>m). Aby byla soustava m rovnic řešitelná, je nutno n-m neznámých zvolit. Tyto volené neznámé jsou nezákladní a neznámé, podle kterých je soustava řešena, jsou základní (bázické) neznámé. Pokud za n-m volíme 0, dostaneme základní (bázické) řešení, které obsahuje nejvýše m nenulových položek. Nedegenerované řešení – počet nenulových složek základního řešení se rovná počtu nezávislých rovnic. Pokud je počet nenulových položek menší než než počet nezávislých rovnic, jedná se o degenerované řešení. V úlohách LP přichází v úvahu pouze nezáporné řešení soustavy – přípustné řešení. Množina přípustných řešení úloh LP je množina konvexní, tedy konvexní kombinace přípustných řešení je zase přípustné řešení. Základní přípustné řešení – obsahuje nejvýše m kladných složek a vektory koeficientů těchto neznámých musí být lineárně nezávislé.
Počet základních přípustných řešení se rovná nejvýše
3
© Jana Friebelová
⎛n⎞ n! ⎜⎜ ⎟⎟ = - tolika způsoby lze zvolit n-m nulových složek, aby vznikla soustava ⎝ m ⎠ (n − m )!m! m rovnic. Optimální řešení úlohy – přípustné řešení, které maximalizuje nebo minimalizuje účelovou funkci. Základní věta lineárního programování: Má-li úloha LP optimální řešení, má nutně též základní optimální řešení. Pokud má úloha LP více základních optimálních řešení, pak každá jejich konvexní kombinace představuje též optimální řešení, úloha má nekonečně mnoho rovnocenných optimálních řešení. Příklad 3: x1 + 2 x 2 + 3 x3 = 12 2 x1 + 8 x 2 + 6 x3 = 36 zvolíme x3 = 0 ⇒ x1 = 6, x 2 = 3 zvolíme x1 = 0 ⇒ x 2 = 3, x3 = 2 zvolíme x 2 = 0 ⇒ nemá řešení V prvních dvou případech jsou submatice koeficientů základních neznámých regulární a řešení jsou základní, přípustná a nedegenerovaná. Ve třetím případě je matice singulární, úloha nemá řešení. Příklad 4: x1 + 2 x 2 + 3 x3 = 6 2 x1 + 8 x 2 + 6 x3 = 36 x3 = 0 ⇒ x1 = −6, x 2 = 6
tato řešení jsou základní, nepřípustná, nedegenerovaná
x1 = 0 ⇒ x 2 = 6, x3 = −2 Příklad 5: x1 + 2 x 2 + 3 x3 = 6 2 x1 + 8 x 2 +6 x3 = 12 x3 = 0 ⇒ x1 = 6, x 2 = 0
tato řešení jsou základní, přípustná, degenerovaná
x1 = 0 ⇒ x 2 = 0, x3 = 2 Vektorová interpretace řešení soustavy m rovnic o n neznámých
4
© Jana Friebelová
Vektory koeficientů základních neznámých tvoří bázi m-rozměrného vektorového prostoru. Pokud základními neznámými je prvních m neznámých, vektory koeficientů těchto neznámých značíme a 1 , a 2 ,..., a m a vektor pravých stran symbolem b, pak určení základního řešení je hledání koeficientů lineární kombinace x1a1 + x 2 a 2 + ... + x m a m = b , neboli hledání souřadnic vektoru b v bázi (a1,a2,…,am). Různému výběru základních řešení odpovídají různé báze. Hledání souřadnic vektoru b v libovolné bázi se provádí buď pomocí vektorové rovnice nebo podle vzorce x B = B −1b.
Grafické řešení úloh LP se dvěma neznámými Model úlohy lineárního programování, který obsahuje pouze dvě neznámé, lze řešit graficky v rovině pravoúhlých souřadných os. V této rovině se nejprve zobrazí všechny omezující podmínky (nerovnice a rovnice), potom se najde jejich průnik v I. kvadrantu. Průnik představuje množinu všech přípustných řešení, na které se vyhledá extrém účelové funkce. Postup ilustrujeme na úloze s čaji (viz příklad 1). Matematický model úlohy:
x1 … počet sáčků čisté máty (ks) x 2 … počet sáčků směsi (ks) Vlastní omezující podmínky: a) 10 x1 + 6 x 2 ≤ 2850 b) c) x1
4 x 2 ≤ 1380 ≤ 100
Podmínky nezápornosti: x1 ≥ 0 x2 ≥ 0 Účelová funkce:
z = 2 x1 + 3x2 → max Grafické řešení úlohy
5
© Jana Friebelová
Každá nerovnice se dvěma proměnnými je geometricky zobrazena polorovinou. Hraniční přímka této poloroviny je určena rovnicí získanou z příslušné nerovnice použitím znaménka rovnosti. Která z opačných polorovin vyťatých hraniční přímkou vyhovuje dané nerovnici zjistíme tak, že dosadíme do nerovnice souřadnice libovolného bodu. Pokud nerovnice platí, pak je to polorovina, ve které tento bod leží. Pokud neplatí, je to polorovina opačná. Nejprve znázorníme všechny omezující podmínky v rovině souřadných pravoúhlých os.
6
© Jana Friebelová
Společnému řešení všech nerovnic tvořících soustavu omezujících podmínek odpovídá průnik příslušných polorovin a I. kvadrantu. Podmínky jsou v našem příkladu označeny písmenky a, b, c. Pokud by byl tento průnik prázdný, úloha nemá přípustné řešení. Neprázdný průnik všech polorovin a přímek, které jsou konvexní útvary, je opět konvexní útvar, který má konečný počet krajních bodů (vrcholů) a který je buď omezený nebo neomezený. Tento průnik označujeme jako množinu κ. Souřadnice jakéhokoliv bodu z množiny κ představují přípustné řešení úlohy. Krajní body množiny κ (v našem příkladu jsou tyto vrcholy označeny písmeny A, B, C, D, E) představují základní přípustná řešení. Pokud má úloha optimální řešení, je to jeden z vrcholů představujících základní přípustná řešení.
Pro nalezení extrému účelové funkce na množině přípustných řešení sestrojíme graf této funkce pro její dvě libovolně zvolené hodnoty. V našem příkladu jsme zvolili nejprve hodnotu 7
© Jana Friebelová
600 a potom hodnotu 1200. Tím získáme dvě rovnoběžné přímky. Ze vzájemné polohy těchto dvou přímek můžeme určit směr, který odpovídá růstu, popř. poklesu hodnoty účelové funkce. Přímka znázorňující účelovou funkci pak posouváme rovnoběžně příslušným směrem až do posledního bodu, který je společný s množinou κ. Pokud je množina κ neomezená, účelová funkce nabývá neomezeně velkých nebo neomezeně malých hodnot.
Grafickým řešení úlohy jsme zjistili, že optimální řešení se nachází v bodě B. Toto lze prověřit postupným dosazením souřadnic všech krajních bodů do účelové funkce. Bod A má souřadnice [0; 345] a po dosazení do účelové funkce získáme hodnotu 1035. Bod B má souřadnice [78; 345] a po dosazení do účelové funkce získáme hodnotu 1191. Bod C má souřadnice [100; 308,33] a po dosazení do účelové funkce získáme hodnotu 315. Bod D má souřadnice [100; 0] a po dosazení do účelové funkce získáme hodnotu 200. Bod E má obě souřadnice nulové, tedy i hodnota účelové funkce je nulová. V bodě B je hodnota účelové funkce největší. Znamená to, že nejvyšší zisk (1191 Kč) dosáhneme při výrobě 78 sáčků čisté máty a 345 sáčků směsi.
Zvláštní případy řešení úloh LP a) podmínky si odporují – úloha nemá přípustné řešení b) úloha má nekonečně mnoho rovnocenných optimálních řešení – graf účelové funkce je rovnoběžný s některou z přímek, které omezují množinu κ c) množina přípustných řešení je neomezená – hodnota z neomezeně roste či klesá 8
© Jana Friebelová
d) hledání celočíselného řešení – na množině přípustných řešení nás zajímají jen řešení ležící na průsečících svislých a vodorovných přímek, mezi nimiž je jednotková vzdálenost SIMPLEXOVÁ METODA Je to univerzální, iterační metoda, k optimálnímu řešení se dostaneme v krocích. Přecházíme podle určitých pravidel od výchozího základního přípustného řešení dané úlohy k jiným základním přípustným řešením, která dávají lepší hodnotu účelové funkce, až do dosažení optima. Algoritmus simplexové metody: 1. získání výchozího základního přípustného řešení 2. provedení testu optima; jestliže řešení není optimální, následuje další krok 3. přechod k novému základnímu přípustnému řešení s lepší hodnotou účelové funkce 4. opakování 2. a 3.kroku až do nalezení optima, popř. až do zjištění, že hodnota účelové funkce je neomezená Stanovení výchozího přípustného řešení úloh LP Proměnné, které jsou obsaženy v původních omezujících podmínkách, se nazývají strukturní proměnné. Omezující podmínky ve tvaru nerovnic je nutné nejprve převést na rovnice pomocí doplňkových proměnných. Matice soustavy musí obsahovat jednotkovou submatici, kterou tvoří koeficienty základních proměnných (kanonický tvar) 1. Nerovnice typu ≤ - přičítáme doplňkové proměnné d, které představují nevyužití horní hranice příslušného omezení, v účelové funkci mají tyto doplňkové proměnné nulové koeficienty 2. Nerovnice typu ≥ - odečítáme doplňkové proměnné d, které představují překročení dolní hranice příslušného omezení; v účelové funkci mají opět nulové koeficienty a zároveň přičítáme k levým stranám ještě tzv. umělé proměnné u 3. Pokud je omezení ve tvaru rovnice, též přičítáme umělé proměnné Zavedením umělých proměnných získáme rozšířenou úlohu k dané úloze, která je s původní ekvivalentní, pokud se umělé proměnné rovnají nule. Pokud neexistuje přípustné řešení
9
© Jana Friebelová
rozšířené úlohy s nulovými hodnotami umělých proměnných, nemá původní úloha řešení. Umělé proměnné se snažíme ze základního řešení vyloučit, a to následujícími způsoby: 1.Umělým proměnným přiřazujeme prohibitivní cenu (u maximalizačních úloh nízké záporné číslo –M a u minimalizačních úloh vysoké kladné číslo +M) 2. Minimalizujeme součet umělých proměnných, který je vždy nezáporný (pokud součet = 0, existuje přípustné řešení úlohy a pak řešíme dále běžným způsobem; pokud součet > 0, původní úloha nemá přípustné řešení) Příklad:
1,2 x1 + 1,5 x 2 ≤ 12 x1 + x 2 ≤ 9 3x1 + 7 x 2 ≥ 15 4 x1 + 3x 2 = 20 z = 5 x1 + 8 x 2 → max x 1, 2 ≥ 0 Nerovnice převedeme na rovnice pomocí doplňkových proměnných: 1,2 x1 + 1,5 x 2 + d1 = 12 .
x1 + x 2 + d 2 = 9 3x1 + 7 x 2 − d 3 = 15 4 x1 + 3x 2 = 20
Pro získání rovnic v kanonickém tvaru musíme přičíst ještě umělé proměnné: 1,2 x1 + 1,5 x 2 + d1 = 12 x1 + x 2 + d 2 = 9 3x1 + 7 x 2 − d 3 + u1 = 15 4 x1 + 3x 2 + u 2 = 20 z = 5 x1 + 8 x 2 + 0d1 + 0d 2 + 0d 3 − Mu1 − Mu 2 → max Pokud u1 = u 2 = 0 , obě soustavy jsou ekvivalentní. SIMPLEXOVÁ TABULKA Maximalizační úlohy Příklad 6 Podnik vyrábí výrobky V1 a V2, přičemž má k dispozici omezené množství suroviny S1 = 12 t
a S2 = 9 t. Cena výrobku V1 je 5 tis.Kč a cena výrobku V2 je 8 tis.Kč. Kolik kterých výrobků
10
© Jana Friebelová
má podnik vyrábět, aby měl maximální tržby? Spotřeba obou surovin na výrobky V1 a V2 jsou uvedeny v následující tabulce. V2 1,5 1
V1 1,2 1
S1 S2
Matematický model úlohy: x1…počet výrobků V1 (ks) x2…počet výrobků V2 (ks) 1,2 x1 + 1,5 x 2 ≤ 12
1,2 x1 + 1,5 x 2 + d1 = 12
x1 + x 2 ≤ 9
x1 + x 2 + d 2 = 9
z = 5 x1 + 8 x 2 → max
z − 5 x1 − 8 x 2 = 0
x1, 2 ≥ 0
Koeficienty strukturních a doplňkových proměnných zapíšeme do následující tabulky. První sloupec tabulky obsahuje proměnné, které jsou v bázi (struktura báze). V bázi jsou proměnné, jejichž vektory tvoří jednotkovou matici. Další sloupce jsou nadepsány symboly všech proměnných, které se v úloze vyskytují. Hodnoty bázických proměnných zjistíme v posledním sloupci tabulky (b - vektor pravých stran). Poslední řádek tabulky (indexní řádek – označený písmenkem z ) obsahuje anulovanou rovnici účelové funkce. Hodnotu účelové funkce v jednotlivých krocích zjistíme na průsečíku sloupce b a indexního řádku z. báze
x1
x2
d1
d2
b
d1
1,2
1,5
1
0
12
d2
1
1
0
1
9
z
-5
-8
0
0
0
Uvedené řešení je optimální, pokud neexistuje jiné základní přípustné řešení, které by dávalo vyšší hodnotu účelové funkce (u maximalizačních úloh se v indexním řádku už nevyskytuje záporné číslo). V našem případě jsou u výchozího řešení základní neznámé (obsažené ve sloupci báze) d1 a d2 (d1 = 12 a d2 = 9). Nezákladní proměnné jsou zde x1 a x2 (x1= 0 a x2 = 0). 11
© Jana Friebelová
Účelová funkce z = 5*0 + 8*0 + 0*12 + 0*9 =0. Protože se v indexním řádku vyskytují záporná čísla, lze řešení zlepšit. Postup při řešení simplexovou metodou:
V indexním řádku najdeme nejnižší číslo – tento sloupeček označíme jako klíčový. Proměnná, která je nadepsaná v záhlaví klíčového sloupce se stane v dalším kroku základní, tedy vstoupí do báze. Pak dělíme postupně pravou stranu kladným číslem v klíčovém sloupci pro všechny základní neznámé (pokud v klíčovém sloupci není kladné číslo, z je neomezená). Tam, kde vyjde podíl nejnižší, to pole označíme jako klíčové (v naší tabulce označené žlutě). Proměnná v řádku, ke kterému přísluší nejnižší podíl z báze vystoupí. Úpravami musíme dostat do klíčového pole 1 a nad a pod něj 0, pomocí Gauss-Jordanovy eliminační metody. Novou základní proměnnou zapíšeme do sloupce báze namísto vyloučené proměnné báze
x1
x2
d1
d2
b
d1
1,2
1,5
1
0
12
d2
1
1
0
1
9
z
-5
-8
0
0
0
x2
4/5
1
2/3
0
8
d2
1/5
0
-2/3
1
1
z
7/5
0
16/3
0
64
Základní neznámé jsou nyní x2 a d2 (x2 = 8 a d2 = 1) Nezákladní neznámé jsou x1 a d1 (x1 = 0 a d1 = 0) Účelová funkce z = 5*0 + 8*8 + 0*0 + 0*1 = 64. V indexním řádku se již nevyskytuje záporné číslo, řešení je optimální. Minimalizační úlohy
Do řešení vstupuje neznámá, která má v indexním řádku nejvyšší kladné číslo, vylučovanou proměnnou určujeme stejným způsobem jako u maximalizačních úloh. Optima je dosaženo tehdy, pokud jsou v indexním řádku pouze nekladná čísla. INTERPRETACE VÝSLEDNÉ SIMPLEXOVÉ TABULKY
Zadání viz příklad 6. Matematický model úlohy: x1…počet výrobků V1 (ks) x2…počet výrobků V2 (ks)
12
© Jana Friebelová
1,2 x1 + 1,5 x 2 ≤ 12 x1 + x 2 ≤ 9 z = 5 x1 + 8 x 2 → max x 1, 2 ≥ 0 báze d1 d2 z x2 d2 z
x1 1,2 1 -5 4/5 1/5 7/5
x2 1,5 1 -8 1 0 0
d1 1 0 0 2/3 -2/3 16/3
d2 0 1 0 0 1 0
b 12 9 0 8 1 64
V úloze jsou dvě strukturní proměnné (x1, x2) a dvě doplňkové proměnné (d1, d2). Ve výsledné tabulce, ke které jsme došli hned po prvním kroku simplexového algoritmu, jsou v bázi proměnné x2 a d2 (struktura báze se zjišťuje v prvním sloupečku tabulky a postupně se mění). Hodnoty těchto proměnných se zjišťují v příslušném řádku vždy v posledním sloupci (x2 = 8 a d2 = 1). Hodnota účelové funkce se zjistí v pravém dolním rohu výsledné tabulky (z = 64). Ostatní proměnné (x1 a d1) se v bázi nevyskytují a mají tedy nulovou hodnotu. V indexním řádku v konečné tabulce jsou pod bázickými proměnnými nuly a pod nebázickými proměnnými 7/5 a 16/3. V našem příkladu to znamená, že maximální možný zisk 64 tis.Kč nám zajistí výroba 8 ks výrobku V2 (výrobky V1 se nebudou vyrábět vůbec). Surovinu S1 spotřebujeme beze zbytku a suroviny S2 nám zůstane 1 t. (druhá omezující podmínka není splněna jako rovnice, neboť d2 = 1, proto zbytek S2 je 1 t. Číslo 7/5 pod strukturní nebázickou proměnnou x1 nám ukazuje, o kolik by se zhoršila hodnota účelové funkce při zařazení jedné jednotky proměnné x1 do báze. V našem případě to znamená, že pokud bychom do výrobního programu zařadili výrobek V1 (vyrobili bychom 1 ks tohoto výrobku za původních podmínek), klesly by tržby na 62,6 tis.Kč (64–7/5). Zároveň by klesl počet vyrobených výrobků V2 na 7,2 ks (8 – 4/5) a zbylo by i méně suroviny S2 (1 – 1/5), tedy 0,8 t. Číslo 16/3 pod doplňkovou nebázickou proměnnou d1 se vztahuje k první omezující podmínce. Pokud bychom první omezující podmínku zmírnili (namísto 12 t suroviny 1 bychom měli k dispozici 13 t této suroviny), hodnota účelové funkce by se zvýšila na 69,33 tis.Kč (64 + 16/3). Počet vyrobených výrobků V2 by se zvýšil na 8,66 ks (8 + 2/3) a zbytek suroviny 1 by se snížil na 0,33 t (1 – 2/3). Při zpřísnění první omezující podmínky by se hodnota účelové funkce naopak snížila, počet vyrobených výrobků V2 rovněž a naopak zbytek suroviny S2 by se zvýšil. MATICOVÝ ZÁPIS SIMPLEXOVÉ TABULKY Ax ≤ b, x ≥ o, z = cT x → extrém A … matice typu (m × n ) , jejíž prvky tvoří koeficienty aij (i = 1,2,..., m; j = 1,2,..., n ) b … m-členný vektor požadavků
c … n-členný vektor cen
13
© Jana Friebelová
x … n-členný vektor neznámých (proměnných) o … n-členný nulový vektor
Kanonický tvar A -cT
E oT
b 0
E … jednotková matice m-tého řádu oT… m-členný řádkový nulový vektor
V každém kroku simplexové tabulky se původní soustava transformuje do jiného kanonického tvaru s jednotkovou maticí na jiném místě, tomu odpovídá změna báze. báze d1 d2 z
x1 1,2 1 -5
x2 1,5 1 -8
d1 1 0 0
d2 0 1 0
b 12 9 0
d1 1 0 0 2/3 -2/3 16/3
d2 0 1 0 0 1 0
b 12 9 0 8 1 64
d1 d 2 ⎛1,2 1,5 ⎞ ⎛12 ⎞ T ⎟⎟ , b = ⎜⎜ ⎟⎟ , c = (5,8) , B 0 = ⎛ 1 0 ⎞ A = ⎜⎜ ⎟⎟ ⎜⎜ 1 1 ⎝ ⎝9⎠ ⎠ ⎝0 1⎠
báze d1 d2 z x2 d2 z
x1 1,2 1 -5 4/5 1/5 7/5
x2 1,5 1 -8 1 0 0
x2 d 2 ⎛ 2 / 3 0⎞ ⎟ B 1 = ⎛1,5 0 ⎞ , B 1−1 = ⎜⎜ ⎟⎟ ⎜⎜ − 2 / 3 1 ⎟⎠ ⎝ ⎝ 1 1⎠
⎛ 2 / 3 0 ⎞⎛12 ⎞ ⎡8⎤ ⎟⎟⎜⎜ ⎟⎟ = ⎢ ⎥ x = B1−1b = ⎜⎜ ⎝ − 2 / 3 1 ⎠⎝ 9 ⎠ ⎣1⎦ Struktura matice báze B se určuje v jednotlivých krocích ve sloupečku báze (v našem případě je struktura matice báze po prvním kroku - proto B1 - x2 a d2). Hodnoty v matici se vezmou vždy z výchozí simplexové tabulky ve sloupečku proměnné, která je zařazena v příslušném kroku do báze (v našem příkladu ve výchozí tabulce ve sloupečku pod x2 a d2). Inverzní matice báze po prvním kroku se značí B 1−1 . V tabulce jsou obě matice označeny barevně. B
B 1−1 A = vektory koeficientů u strukturních proměnných ve výsledné simplexové tabulce
14
© Jana Friebelová
⎛ 2 / 3 0 ⎞⎛1,2 1,5 ⎞ ⎛ 4 / 5 1 ⎞ ⎜⎜ ⎟⎟⎜⎜ ⎟⎟ = ⎜⎜ ⎟⎟ ⎝ − 2 / 3 1 ⎠⎝ 1 1 ⎠ ⎝ 1 / 5 0 ⎠ Hodnoty základních proměnných ve výsledné tabulce se spočítají takto: ⎛ 2 / 3 0 ⎞⎛12 ⎞ ⎛ 8 ⎞ ⎟⎟⎜⎜ ⎟⎟ = ⎜⎜ ⎟⎟ x = B 1−1b = ⎜⎜ ⎝ − 2 / 3 1 ⎠⎝ 9 ⎠ ⎝ 1 ⎠ Struktura báze výsledné simplexové tabulky je x2 a d2. Ve výchozí tabulce v indexním řádku najdeme jejich ceny. T c B1 = (8;0) Jednotlivé části indexního řádku lze určit takto: (c B1 )T B1−1A − cT = (8;0)⎛⎜⎜ 14//55 10 ⎞⎟⎟ − (5;8) = (7 / 5;0) ⎝ ⎠
( )
⎛ 2 / 3 0⎞ ⎟⎟ = (16 / 3;0 ) = (8;0 )⎜⎜ ⎝ − 2 / 3 1⎠ ⎛8⎞ T B1−1b = (8;0 )⎜⎜ ⎟⎟ = 64 ⎝1⎠
(c ) B T
B1
−1 1
(c ) B1
ANALÝZA CITLIVOSTI
Rozbor citlivosti optimálního řešení na změny (stabilita optimálního řešení). Změny se mohou týkat vstupních dat (vektor požadavků, vektor cen a matice strukturních koeficientů), dále počtu proměnných a počtu omezujících podmínek. Změní se buď údaje ve výsledné simplexové tabulce při zachování optimální báze, nebo se změní i struktura optimální báze. Změna vektoru požadavků Jakákoliv změna ve vektoru požadavků se projeví v hodnotách základních proměnných a v hodnotě účelové funkce B −1 (b + Δb ) = B −1 b + B −1 Δb ≥ o
⎛ 8 ⎞ ⎛ 2 / 3 0 ⎞⎛ Δb 1 ⎞ ⎛ 0 ⎞ ⎟⎟ ≥ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟⎜⎜ ⎝ 1 ⎠ ⎝ − 2 / 3 1 ⎠⎝ Δb 2 ⎠ ⎝ 0 ⎠ Změna v 1. omezující podmínce: Δb 1 Δb 2 = 0 ⎛ 8 ⎞ ⎛ 2 / 3 0 ⎞⎛ Δb 1 ⎞ ⎛ 0 ⎞ ⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟⎜⎜ ⎟⎟ ≥ ⎜⎜ ⎟⎟ ⎝ 1 ⎠ ⎝ − 2 / 3 1 ⎠⎝ 0 ⎠ ⎝ 0 ⎠
8 + 2 / 3Δb 1 ≥ 0 ⇒ Δb 1 ≥ −12 1 − 2 / 3Δb 1 ≥ 0 ⇒ Δb 1 ≤ 3 / 2 Δb 1 ∈ − 12, 3 / 2
15
© Jana Friebelová
Pokud pravá strana omezující podmínky bude v intervalu 0; 13,5 , nezmění se struktura báze. Pokud bude pravá strana menší než 0, úloha nemá přípustné řešení; pokud je větší než 13,5, změní se struktura báze. Změna v 2. omezující podmínce: Δb 1 = 0 Δb 2
⎛ 8 ⎞ ⎛ 2 / 3 0 ⎞⎛ 0 ⎞ ⎛ 0 ⎞ ⎟⎟ ≥ ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟⎜⎜ ⎝ 1 ⎠ ⎝ − 2 / 3 1 ⎠⎝ Δb 2 ⎠ ⎝ 0 ⎠ 8 + 0Δb 2 ≥ 0 ⇒ Δb 2 může být libovolné 1 + Δb 2 ≥ 0 ⇒ Δb 2 ≥ −1 Δb 2 ∈ − 1,+∞ Pokud pravá strana 2. omezující podmínky bude v intervalu 8,+∞ , struktura báze se nezmění. Změna ve vektoru cen
Při změně vektoru cen se změní údaje pouze v indexním řádku: a) změna cen nezákladních proměnných se neprojeví v hodnotě účelové funkce, zjišťujeme, jak velká změna ceny zvolené nezákladní proměnné musí být, aby se stala základní proměnnou b) změna cen základních proměnných ovlivní hodnotu účelové funkce; změna cen musí být v určitém intervalu, aby nenastala změna báze; pokud se cena základní proměnné rovná jedné z mezí tohoto intervalu, budou existovat rovnocenná optimální řešení Dualita v úlohách LP
Ke každé úloze LP můžeme formulovat úlohu duálně sdruženou, která je k původní (tzv.primární) úloze v jednoznačném vztahu. Obecné vztahy mezi duálně sdruženými symetrickými úlohami primár duál
Počet proměnných
n
m
Počet vlastních omezení
m
n
Matice strukturních koeficientů
A
AT
Vektor požadavků
b
c
Vektor cen
c
b
Typ omezení
≤
≥
ano
ano
Nezápornost proměnných Typ extrému účelové funkce
Max. Min.
16
© Jana Friebelová
Pokud jsou některá vlastní omezení primární maximalizační úlohy typu ≥, musíme je převést na omezení typu ≤ vynásobením (-1). Podobně pokud jsou v primární minimalizační úloze omezení typu ≤, musíme je převést na omezení typu ≥ vynásobením (-1). Příklad 7:
1,2 x1 + 1,5 x 2 ≤ 12 PRIMÁR
x1 + x 2 ≤ 9 z = 5 x1 + 8 x 2 → max .
1,2 y1 + y 2 ≥ 5 DUÁL
x1, 2 ≥ 0
1,5 y1 + y 2 ≥ 8 f = 12 y1 + 9 y 2 → min . y1, 2 ≥ 0
Příklad 8: 10 x1 + 6 x 2 ≤ 2850
10 y1 + y 3 ≥ 2
4 x 2 ≤ 1380
PRIMÁR x1
≤ 100
DUÁL
z = 2 x1 + 3 x 2 → max .
6 y1 + 4 y 2 ≥ 3 f = 2850 y1 + 1380 y 2 + 100 y 3 → min . y1, 2,3 ≥ 0
x1, 2 ≥ 0
Nesymetrické duální úlohy
Pokud soustava omezujících podmínek obsahuje omezení ve tvaru rovnic, u duálních proměnných není požadovaná nezápornost. Příklad 9: 2 x1 + 3 x 2 ≤ 15
2 y1 − y 2 + 3 y 3 ≥ 4
x1 + 2 x 2 ≥ 5
PRIMÁR 3 x1 + 5 x 2 = 20 z = 4 x1 + 3 x 2 → max . x1, 2 ≥ 0
DUÁL
3 y1 − 2 y 2 + 5 y 3 ≥ 3 f = 15 y1 − 5 y 2 + 20 y 3 → min . y1, 2 ≥ 0, y 3 nemusí být nezáporné
Vztahy mezi řešením duálně sdružených úloh
1. Pokud má primár konečné optimální řešení, pak i duál má konečné optimální řešení – optimální hodnoty se sobě rovnají zmax =fmin
17
© Jana Friebelová
2. Pokud v primáru je hodnota účelové funkce neomezená, pak v duálu neexistuje přípustné řešení 3. Pokud v primáru neexistuje přípustné řešení, v duálu účelová funkce neomezeně roste nebo klesá nebo neexistuje přípustné řešení Řešením jedné ze sdružených úloh získáme i řešení druhé úlohy a naopak. Řešení najdeme ve výsledné simplexové tabulce, a to v indexním řádku. Optimální hodnoty duálních strukturních proměnných najdeme v indexním řádku výsledné simplexové tabulky, a to pod přičítanými primárními doplňkovými proměnnými a naopak. Ve sloupečku pod strukturními proměnnými v indexním řádku konečné simplex. tabulky primární úlohy najdeme hodnoty doplňkových proměnných duálu. Příklad 10:
PRIMÁR
DUÁL
1,2 x1 + 1,5 x 2 ≤ 12
1,2 y1 + y 2 ≥ 5
x1 + x 2 ≤ 9
1,5 y1 + y 2 ≥ 8
z = 5 x1 + 8 x 2 → max
f = 12 y1 + 9 y 2 → min .
x 1, 2 ≥ 0
y1, 2 ≥ 0
1,2 x1 + 1,5 x 2 + d 1 = 12
1,2 y1 + y 2 − g 1 = 5
x1 + x 2 + d 2 = 9
1,5 y1 + y 2 − g 2 = 8 báze
x1
x2
d1
d2
b
d1
1,2
1,5
1
0
12
d2
1
1
0
1
9
z
-5
-8
0
0
0
x2
4/5
1
2/3
0
8
d2
1/5
0
-2/3
1
1
z
7/5
0
16/3
0
64
g
y1 = 16/3
x1 = 0
y2 = 0
x2 = 8
g1 = 7/5
d1 = 0
y
18
© Jana Friebelová
g2 = 0
d2 =1
fmin = 64
zmax = 64
( )
z max = (c B ) x B = f min = y (0 ) b T
(c B )T x B = (y (0 ) )T b,
T
x B = B −1b ⇒ ( y (0 ) ) = (c B ) B −1 T
T
Pokud jedna z úloh má nekonečně mnoho rovnocenných optimálních řešení, pak druhá úloha má degenerované řešení. Pokud je primární úloha minimalizační, indexní řádek ve výsledné simplexové tabulce obsahuje pouze nekladná čísla. Optimální hodnoty duálních proměnných se rovnají absolutním hodnotám příslušných indexních čísel. Podle stejných pravidel určíme optimální řešení primární úlohy, pokud známe výslednou tabulku příslušné duální úlohy. Můžeme se rozhodnout, kterou úlohu budeme řešit, která je pro nás z výpočetního hlediska výhodnější. Věta o komplementárnosti doplňkových proměnných
Pokud některé omezení v optimálním řešení jednoho ze sdružených problémů je splněno jako ostrá nerovnost, odpovídající duální proměnná se rovná nule. ⎛ n ⎞ y i = 0 ⇔ d i > 0 ⎜⎜ ∑ a ij x j < bi ⎟⎟ ⎝ j =1 ⎠ ⎛ n ⎞ y i > 0 ⇔ d i = 0 ⎜⎜ ∑ a ij x j = bi ⎟⎟ ⎝ j =1 ⎠ ⎛ m ⎞ x j = 0 ⇔ g j > 0 ⎜ ∑ a ij y i > c j ⎟ ⎝ i =1 ⎠ ⎛ m ⎞ x j > 0 ⇔ g j = 0 ⎜ ∑ a ij y i = c j ⎟ ⎝ i =1 ⎠
Ekonomická interpretace duality
Duální proměnné představují ocenění jednotkového rozsahu daných výrobních zdrojů z = b1 y1(0 ) + b2 y 2(0 ) + ... + bm y m(0 ) .
Nyní předpokládejme změnu požadavkového čísla bk o hodnotu Δbk, kde 1 ≤ k ≤ m . Pak y k(0 ) =
z + Δz = b1 y1(0 ) + b2 y 2(0 ) + ... + (bk + Δbk ) y k(0 ) + ... + bm y m(0 ) ⇒ Δz = Δbk y k(0 ) ,
neboli
Δz . Δb k
19
© Jana Friebelová
Optimální hodnota duální proměnné udává změnu optimální hodnoty účelové funkce připadající na jednotkovou změnu pravé strany příslušného omezení v primáru. Duálně simplexová metoda
Optimální báze úlohy LP musí splňovat dva požadavky: 1. hodnota základních proměnných musí být nezáporná 2. indexní řádek musí splňovat test optima Je-li splněn pouze 1. bod, báze je primárně přípustná, při splnění pouze bodu 2 je duálně přípustná. Algoritmus simplex. metody spočívá ve stanovení výchozí primárně přípustné báze a v postupné transformaci této báze v bázi, která je přípustná i duálně – primárně simplexový algoritmus. V některých případech je nutné přejít od báze duálně přípustné, ale primárně nepřípustné, k bázi přípustné i primárně. Tento algoritmus se nazývá duálně simplexová metoda. Při ní určujeme nejprve vyloučenou základní proměnnou a potom teprve proměnnou zařazenou do řešení. Z řešení vystoupí proměnná s nejnižším záporným číslem ve sloupci b a zařazená proměnná se určí tak, že indexní čísla nezákladních proměnných dělíme absolutními hodnotami odpovídajících záporných koeficientů v klíčovém řádku ( u minimalizačních úloh bereme tato čísla v absolutní hodnotě).
20
© Jana Friebelová
