EMM 6 Ekonomicko-matematické metody 6 Prof. RNDr. Jaroslav Ramík, CSc. přednáší doc. RNDr. David Bartl, Ph.D. MME6 2 Úloha lineárního programování Základní tvar n c1x1+ c2x2+ ... + cnxn ® MAX; (1) účelová funkce n (MIN) nza podmínek n n a11x1+ a12x2+ ... + a1nxn ≤ b1 n a21x1+ a22x2+ ... + a2nxn ≤ b2 n ....................... (2) omezující podmínky n am1x1+ am2x2+ ... + amnxn ≤ bm ve tvaru nerovností n n x1 ³ 0 , x2 ³ 0 , ... , xn ³ 0 (3) podmínky nezápornosti MME6 3 Příklad 1: Optimální výrobní plán – úloha LP n n z = 2000x1 + 3000x2 ® MAX; npři omezeních n 0,9x1 + 0,3x2 ≤ 270 n 0,5x2 ≤ 100 n 0,1x1 + 0,2x2 ≤ 60 n xi ³ 0 n EMM 6 Dualita jako vztah mezi dvěma úlohami lineárního programování •Dualitou v úlohách LP rozumíme vzájemný, přesně definovaný vztah mezi dvojicí úloh LP - primární a duální úlohou vycházejících ze stejných vstupních dat. •Dualita je vzájemně symetrickým vztahem obou úloh - úloha primární není nadřazena úloze duální ani naopak! •Duální úloha k duální úloze je úloha primární. •Formální formulace tvaru primární a duální úlohy – souměrná a nesouměrná dualita. EMM 6 Souměrná dualita – zápis pomocí sumací primární úloha (P) duální úloha (D) maximalizovat minimalizovat EMM 6 Souměrná dualita – maticový zápis Primární úloha (P) Duální úloha (D) maximalizovat z = cTx minimalizovat f = bTy Ax ≤ b ATy ≥ c x ≥ 0 y ≥ 0 EMM 6 Souměrná dualita - postup konstrukce duální úlohy k úloze primární •maximalizace účelové funkce se mění na minimalizaci, popř. naopak •ke každému vlastnímu omezení (P) se přiřadí jedna duální proměnná yi, i = 1,2,…,m a dále podmínka : yi ³ 0 •ke každé proměnné xj, j = 1,2,…,n, (P) se přiřadí vlastní omezení duální úlohy •matice strukturních koeficientů (D) se mění na transponovanou matici strukturních koeficientů (P) •koeficienty pravé strany (D) se mění na koeficienty účelové funkce (P) a naopak •smysl nerovností vlastních omezení se v (D) mění na opačný! EMM 6 Souměrná dualita Příklad 1: „Krmné směsi“ (P) (D) maximalizovat z = 2000x1 + 3000x2 minimalizovat f = 270y1 + 100y2 + 60y3 0,9x1 + 0,3x2 ≤ 270 0,5x2 ≤ 100 0,1x1 + 0,2x2 ≤ 60 0,9y1 + 0,1y3 ≥ 2000 0,3y1 + 0,5y2 + 0,2y3 ≥ 3000 x1 ≥ 0 x2 ≥ 0 y1 ≥ 0 y2 ≥ 0 y3 ≥ 0 EMM 6 Nesouměrná dualita •U souměrné duality byla v úloze s maximalizací účelové funkce všechna vlastní omezení ve tvaru nerovnic se smyslem nerovnosti „≤“ •Pro všechny proměnné platily podmínky nezápornosti •V reálných úlohách LP se tato situace často nevyskytuje EMM 6 (P) maximalizovat z = 2000x1 + 3000x2 za podmínek 0,9x1 + 0,3x2 ≤ 270 0,5x2 ≥ 100 0,1x1 + 0,2x2 ≤ 60 x1 ≥ 0 x2 ≥ 0 Podmínku ≥ vynásobíme -1, a tím změníme znak nerovnosti na ≤ , pak je úloha ve tvaru pro souměrnou dualitu Nesouměrná dualita Příklad 2: „Krmné směsi“ EMM 6 •(P) •maximalizovat • z = 2000x1 + 3000x2 •za podmínek • 0,9x1 + 0,3x2 ≤ 270 • 0,5x2 ≤ 100 • 0,1x1 + 0,2x2 = 60 • x1 ≥ 0 • x2 ≥ 0 • Nesouměrná dualita Příklad 3: „Krmné směsi“ EMM 6 •Rozložíme 3. podmínku = ve tvaru rovnosti na dvě nerovnice: • 0,1x1 + 0,2x2 ≥ 60 • 0,1x1 + 0,2x2 ≤ 60 •1. nerovnici ≥ vynásobíme -1 • -0,1x1 - 0,2x2 ≤ -60 •Pak je úloha ve tvaru pro souměrnou dualitu • Nesouměrná dualita Příklad 3: „Krmné směsi“ – řešení 1 EMM 6 •Primární úloha má nyní tvar: •maximalizovat • z = 2000x1 + 3000x2 •za podmínek • 0,9x1 + 0,3x2 ≤ 270 • 0,5x2 ≤ 100 • 0,1x1 + 0,2x2 ≤ 60 • -0,1x1 - 0,2x2 ≤ -60 • x1 ≥ 0 • x2 ≥ 0 •4 podmínky ≤ Þ 4 duální proměnné y1, y2, y3´, y3´´!!! • Nesouměrná dualita Příklad 3: „Krmné směsi“ – řešení 2 EMM 6 •Duální úloha je tedy následující: • minimalizovat – f = 270y1 + 100y2 + 60(y3´- y3´´) • za podmínek • 0,9y1 + 0,1(y3´- y3´´) ≥ 2000 • 0,3y1 + 0,5y2 + 0,2(y3´- y3´´) ≥ 3000 • y1 ≥ 0 • y2 ≥ 0 • y3´ ≥ 0 • y3´´ ≥ 0 Nesouměrná dualita Příklad 3: „Krmné směsi“ – řešení 3 y3 y3 y3 EMM 6 •Označíme y3 = y3´- y3´´ , lze (D) zjednodušit •Pozor! rozdíl dvou nezáporných čísel není vždy nezáporný • (P) (D) maximalizovat z = 2000x1 + 3000x2 minimalizovat f = 270y1 + 100y2 + 60y3 0,9x1 + 0,3x2 ≤ 270 0,5x2 ≤ 100 0,1x1 + 0,2x2 = 60 0,9y1 + 0,1y3 ≥ 2000 0,3y1 + 0,5y2 + 0,2y3 ≥ 3000 x1 ≥ 0 x2 ≥ 0 y1 ≥ 0 y2 ≥ 0 y3 libovolné Nesouměrná dualita Příklad 3: „Krmné směsi“ – řešení 4 EMM 6 Nesouměrná dualita úlohy LP s rovnicemi ve vlastních omezeních – standardní tvar (maticový zápis) (P) (D) maximalizovat z = cTx minimalizovat f = bTy Ax = b ATy ≥ c x ≥ 0 y – libovolné (tj. omezení nezápornosti chybí) EMM 6 Vztahy mezi (P) a (D) úlohou LP Věty 1 až 5: 1.Duální úloha k duální úloze LP je úloha primární 2.Mají-li obě úlohy (P) a (D) přípustné řešení, pak mají obě také řešení optimální 3.Je-li x libovolné přípustné řešení úlohy (P), y libovolné přípustné řešení úlohy (D), pak cTx ≤ bTy 4.Platí-li cTx = bTy, pak x je optimální řešení úlohy (P) a y je optimální řešení úlohy (D) 5.Má-li jedna z úloh (P) a (D) přípustné řešení, ale nemá řešení optimální, pak druhá úloha nemá žádné přípustné řešení EMM 6 Věta 6: Hlavní věta o dualitě • Má-li jedna z úloh (P) nebo (D) optimální řešení (x nebo y), má jej také druhá úloha, přičemž platí, že hodnoty účelových funkcí jsou stejné, tj. cTx = bTy EMM 6 Příklad 4: Primární a duální úloha … • (D) • 6 y1 + 10 y2 ® MIN; • při omezeních • 2 y1 + 4 y2 ³ 3 • 3 y1 ³ 2 • 6 y1 + 2 y2 ³ 1 • yj ³ 0 • Přípustná řešení (např.): • xT = (x1; x2 ; x3 ) = (1 , 0 , 0) , yT = (y1 ;, y2 ) = (1 , 1) • Optimální řešení: • x*T = (2,5 ; 0,33 ; 0) , y*T = (0,67 ; 0,42), cTx* = bTy* = 8,17 • (P) 3 x1 + 2 x2 + x3 ® MAX; při omezeních 2 x1 +3 x2 + 6 x3 £ 6 4 x1 + 2 x3 £ 10 xi ³ 0 EMM 6 Příklad 1: „Krmné směsi“ (P) (D) maximalizovat z = 2000x1 + 3000x2 minimalizovat f = 270y1 + 100y2 + 60y3 0,9x1 + 0,3x2 ≤ 270 0,5x2 ≤ 100 0,1x1 + 0,2x2 ≤ 60 0,9y1 + 0,1y3 ≥ 2000 0,3y1 + 0,5y2 + 0,2y3 ≥ 3000 x1 ≥ 0 x2 ≥ 0 y1 ≥ 0 y2 ≥ 0 y3 ≥ 0 EMM 6 Ekonomická interpretace duality 1 •Prvky primárního modelu (P): •x1 množství výrobku1 (vyrobené směsi I ) •x2 množství výrobku2 (vyrobené směsi II) •z celkový zisk, z* = 1 020 000,- Kč •b1 disponibilní kapacita zdroje1 (rýže), b1 = 270 •b2 disponibilní kapacita zdroje2 (pšenice), b2= 100 •b3 disponibilní kapacita zdroje3 (vloček), b3 = 60 •x* optimální výrobní program x* = (240 ; 180) •Označme y* optimální řešení duální úlohy y* = (666,67 ; 0 ; 14000) EMM 6 Ekonomická interpretace duality 2 •Podle hlavní věty o dualitě platí: • z* = cTx* = bTy* • z* = 270·666,67 + 100·0 + 60·14000 = 1020000 •Hodnoty duální proměnné interpretujeme jako ocenění 1 jednotky příslušného zdroje •Jde tu o marginální ocenění zdrojů, tzn. nejvyšší cenu jednotky užitého zdroje, za kterou se ještě „vyplatí“ nakoupit tento zdroj, tzv. stínová cena („shadow price“) •Je-li skutečná cena jednotky zdroje menší než stínová cena, vyplatí se rozšířit výrobu nákupem tohoto zdroje •Stínová cena představuje náklady obětované příležitosti: nevyčerpaný zdroj má nulovou hodnotu duální proměnné, tj. nulovou stínovou cenu. Jeho zvýšení o jednotku proto nezpůsobí zvýšení zisku! Rýže Pšenice Vločky EMM 6 Ekonomická interpretace duality 3 •Konkrétně: •jednotka 1. zdroje (rýže) se podílí na dalším zisku hodnotou y1 = 666,67 Kč •y2 = 0 znamená, že se 2. zdroj (pšenice) na dalším ev. zisku přímo nepodílí. Tento zdroj není plně využit Þ jeho zvýšení o jednotku nezpůsobí zvýšení hodnoty účelové funkce (tj. zvýšení zisku) •jednotka 3. zdroje (vločky) se podílí na dalším zisku hodnotou y3 = 14 000 Kč (stínová cena) EMM 6 Ekonomická interpretace duality 4 •Otázka: Jak se změní hodnota účelové funkce (zisk), jestliže se kapacita rýže zvýší o jednotku? •Odpověď: Vzroste o hodnotu příslušné duální proměnné y1 = 2000/3 (ověřte v Excelu – Řešiteli!) •y2 = 0 Þ změna kapacit u 2. zdroje nemá na výsledný zisk žádný vliv. SKUTEČNĚ???!!! •Kdyby kapacita pšenice (2. zdroj) výrazně poklesla (o kolik?), stala by se pak nedostatkovou a to by jistě celkový zisk ovlivnilo Þ hodnoty duálních proměnných je nutné uvažovat jen v rámci intervalů stability jednotlivých zdrojů! EMM 6 Dopravní problém LP obr6_1 Dodavatelé Odběratelé Doprava zboží – dopravní cesty EMM 6 Ekonomický a matematický model dopravního problému (DP) •Prvky DP: •m dodavatelů (výrobců, zdrojů ): D1, D2, …, Dm •n odběratelů (spotřebitelů, skladů): O1, O2, …, On •kapacity jednotlivých dodavatelů: a1, a2, …, am •požadavky odběratelů: b1, b2, …, bn •náklady na přepravu jedné jednotky zboží z místa zdroje Di do odběratelského místa Oj: cij •Cíl řešení DP: •Naplánovat objemy přepravy xij mezi Di a Oj tak, aby byly uspokojeny požadavky všech dodavatelů i odběratelů a celkové přepravní náklady byly minimální! Matematický model DP 1 Dodavatelé Odběratelé Kapacity dodavatelů O1 O2 … On D1 c11 c12 … c1n a1 x11 x12 … x1n D2 c21 c22 c2n a2 x21 x22 x2n … … … … … … Dm cm1 cm2 … cmn am xm1 xm2 … xmn Požadavky odběratelů b1 b2 … bn EMM 6 Matematický model DP 2 •Rozlišujeme: •Vyrovnaný dopravní problém • •Nevyrovnaný dopravní problém Každý nevyrovnaný DP lze převést na vyrovnaný! Převod nevyrovnaného DP na vyrovnaný DP •… při převisu nabídky: •přidáme do modelu fiktivního odběratele Of, jehož požadavek bf se bude rovnat danému přebytku, tj. • •… při převisu poptávky: •doplníme model o fiktivního dodavatele Df, jehož kapacita af se bude rovnat chybějícímu množství, tj. • •Dopravní náklady od fiktivního dodavatele a k fiktivnímu odběrateli jsou nulové ! Převod nevyrovnaného DP na vyrovnaný DP: Příklad Dodavatelé Odběratelé Kapacity dodavatelů O1 O2 O3 D1 10 13 6 100 D2 15 18 10 150 D3 8 12 11 300 Požadavky odběratelů 130 210 160 550 500 EMM 6 Převod nevyrovnaného DP na vyrovnaný DP: Příklad - řešení EMM 6 Matematický model (vyrovnaného) DP •Minimalizovat • • •za podmínek • EMM 6 Matematický model (nevyrovnaného) DP: •Minimalizovat • • •za podmínek • EMM 6 Řešení vyrovnaného DP Nalezení počátečního přípustného řešení Test optimality: Je nalezené řešení optimální? Výpočet nového přípustného řešení (spec. Simplex. metoda) Konec ANO NE DP má vždy optimální řešení! EMM 6 Nalezení počátečního řešení: Metoda severozápadního rohu - SZR Nalezení optimálního řešení: speciální Simplexová metoda (Excel-Řešitel) Pokud ai a bj jsou celá čísla, je i optimální řešení celočíselné, tj. xij jsou celá čísla EMM 6 DP Příklad: Optimální řešení Excel - Řešitel EMM 6 Přiřazovací problém - speciální DP •Přiřadit n objektů na n aktivit tak, aby se maximalizoval celkový užitek: •Maximalizovat • • •za podmínek • •cij – dílčí užitek z přiřazení objektu i na aktivitu j •xij = 1 pokud objekt i se přiřadí na aktivitu j, •xij = 0 jinak EMM 6 Přiřazovací problém: Příklad 4 cij – užitek (body) z přiřazení i na j Objekty cij xij Aktivity Přiřazené objekty A1 A2 A3 O1 10 13 6 1 0 1 0 O2 15 18 10 1 1 0 0 O3 8 12 11 1 0 0 1 Přiřazené aktivity 1 1 1 3 3 EMM 6 Přiřazovací problém: Příklad 4 Řešení Excel - Řešitel DP_PP.xls