Nelineární optimalizace s omezeními - obecně Většinu spoj itých optimalizačních problémů lze vyjádřit následujícím způsobem: minimalizuj: f(x), x e Rn za předpokladu: Ci(x) = 0, i e E Ci(x) > 0, i e I Nelineární optimalizace s omezeními - obecně II Účelová funkce f, stejně jako funkce ci? určuj ící omezení, j sou zobrazení z Rn do R. E množina omezení ve formě rovnic I množina omezení ve formě nerovnic Dále budeme kvůli stručnosti označovat gradienty Vq jako a^ Nelineární optimalizace s omezeními - příklad Potravinářský velkoobchod má k dispozici sklad na 100 tun obilovin a jeho manažer se rozhoduje, jaké plodiny nakoupit: - hrách se prodává za 10 Kč/kg a jeho nákupní cena je 8 Kč/kg - mouka se prodává za 8Kč/kg, nákupní cena malého množství je 7Kč/kg, při každé odebrané tuně se cena snižuje o 0,02 Kč - čočka se prodává za 12 Kč/kg a její nákupní cena je 9 Kč/kg, speciálním potřebám pro skladování této plodiny však vyhovuje pouze jedna část skladu, která je schopná pojmout 50 t. Kolik nakoupit hrachu, kolik mouky a kolik čočky? Nelineární optimalizace s omezeními - příklad II Proměnné: x množství hrachu y množství mouky z množství čočky Omezení skladovací kapacity: x + y + z < 100 z<50 Nelineární optimalizace s omezeními - příklad III Zisk z jedné tuny: hrách 2000 Kč čočka 3000 Kč mouka (1000 + 20y)Kč Poznámka: Cena za kg: 7 - 0,02y => zisk z tuny tedy bude 1000.(8 - (7 - 0,02y)) = 1000 + 20y Účelová funkce má tedy tvar: 2000x + (1000 + 20y)y + 3000z = = 2000x + 1000y + 20y2 + 3000z Nelineární optimalizace s omezeními - definice Množina přípustných bodů: S = {x e Rn | Ci(x) = 0, i e E; c^x) > 0, i e 1} Přípustný bod x* e E, splňující omezující podmínky, nazveme omezeným lokálním minimem problému, pokud existuje okolí Q(x*) bodu x* tak, že pro všechna x e Q(x*), která splňují omezení, platí f(x*) < f(x). Nelineární optimalizace s omezeními - definice II Aktivní omezení v bodě x je indexová množina A, pro kterou platí: A(x)={i;Ci(x) = 0} Je-li tedy i e A(x), pak x je na hranici oblasti definované i-tým omezením. Velmi důležitá j e množina A* = A(x*), jestliže je tato množina známa, pak můžeme ostatní omezení ignorovat a řešit úlohu jako problém s omezeními ve formě rovnic E = A*. Nelineární optimalizace s omezeními - definice III Volné extrémy: Jsou to lokální extrémy účelové funkce, nezávisí na žádných dalších omezeních. Vázané extrémy Body účelové funkce, které jsou minimální (maximální) v oblasti, omezené jistými podmínkami. Omezení v podobě rovnic - obecně Minimalizuj: f(x), x e Rn za předpokladu: Cj(x) = 0, i e E Ci(x) > 0, i e I kde 1 = 0 Omezení v podobě rovnic - eliminace proměnných Jestliže j sou omezení tvořena pouze soustavou m rovnic, můžeme z nich vyjádřit m proměnných pomocí zbývaj ících n - m proměnných. Za těchto m proměnných pak můžeme dosadit v účelové funkci a řešit namísto původního problému o n proměnných s omezeními nepodmíněný minimalizační problém o n-m proměnných. Omezení v podobě rovnic - eliminace proměnných II Pokud řešení nepodmíněného problému splňuje omezení původní úlohy, dospěli jsme k řešení. Takto vytvořený nepodmíněný problém ale obecně nemusí být ekvivalentní původnímu problému, a proto je třeba při eliminaci proměnných zachovávat jistou opatrnost a konfrontovat nalezené řešení s původním zadáním. Omezení v podobě rovnic - eliminace proměnných III Příklad: Minimalizuj: f(x) = -xl - x2 Za předpokladu: xx2 + x22 = 1 Řešení: x2 = ±^l-xf x2 dosadíme do rovnice pro f(x), odderivujeme a řešíme f (x) = 0 globální minimum je řešením rovnice: min - Omezení v podobě rovnic - metoda Lagrangeových činitelů Cílem metody je najít vektory x* a X* splňující rovnice: g(x) = ^ai(x)Ai ieE Cj(x) = 0, ieE Kde: g(x) gradient f(x) a^x) Vcí(x) Omezení v podobě rovnic - metoda Lagrangeových činitelů II Pokud máme m omezení (|E| = m), pak dostáváme n+m rovnic o n+m neznámých. Nicméně jde o systém nelineárních rovnic, takže nalezení řešení obecně nemusí být jednoduché. Navíc řešením mohou být kromě lokálních minim také lokální maxima a sedlové body. Omezení v podobě rovnic - metoda Lagrangeových činitelů III Příklad: Minimalizuj xl + x2 Za předpokladu: Xj2 - x2 = 0 Sestavíme rovnice: ^^^^^^^^ í1! í2x0 A, g(x) — 1-iJ ieE o Ci(x) = 0, Í G E Odtud dostáváme: A,* = -l,x1* = -l/2ax2* = l/4 Omezení v podobě nerovnic - obecně Nyní opět rozšíříme své úvahy na obecnou nelineární optimalizační úlohu: Minimalizuj: f(x), x e Rn za předpokladu: Cj(x) = 0, i e E Ci(x) > 0, i e I Omezení v podobě nerovnic - obecně II Nechť opět x* je řešením úlohy. V okolí bodu x* jsou pak důležité jen ty nerovnice, které představují aktivní omezení v x*. Označíme je jako I*, kde I* = A* ni. Pokud x* j e lokálním minimem, pak musí splňovat následující podmínky: g(x*)= ^a^x*).^* ieA* a zároveň X{* > 0, i e I* Omezení v podobě nerovnic - příklad Ukázka použití podmínek z minulého slidu pro řešení příkladu: Minimalizuj: f(x) = - xí - x2 Za předpokladů: cx(x) = x2 - xí 2>0 c2(x) = 1 - xx2 - x22 > 0 Nemáme žádný obecný návod, jak zjistit, které z omezení je aktivní v x*. V tomto dvourozměrném případě lze nalézt aktivní omezení pomocí obrázku. Omezení v podobě nerovnic - příklad II Nalezení aktivního omezení pomocí obrázku: 1-x x =0 2 1 => Aktivní omezení je pouze omezení 2. Omezení v podobě nerovnic - příklad III Rovnice: g(x)=Xai(x*)Ji; kde: V ^ 0, i e I* Í€A* Tedy budou pro náš příklad vypadat následovně: -1 = -2X2xx -1 = -2X2x2 1 - Xl2 - x22 = 0 Uvedená soustava má dvě řešení, ale jen u jednoho z nich je X2 > 0: X2 = xx = x2 = j= Omezení v podobě nerovnic - příklad IV Při hledání aktivního omezení můžeme také postupovat tak, že systematicky otestujeme všechny kombinace daných omezení. V našem případě by to tedy byly tyto kombinace: a) A* = 0 Je zřejmé, že toto neplatí. b) A* = {1} Neexistuje řešení, pro které by bylo ?4 > 0. c) A* = {1,2} Neexistuje řešení, pro které by bylo zároveň ^>0a X2 > 0. d) A* = {2} Tady řešení existuje :-). Omezení v podobě nerovnic - podmínky pro vázané extrémy Na předchozích slidech j sme si ukázali, jakým způsobem lze odvodit nutné podmínky pro lokální minima problému. Dosažené výsledky nyní shrneme do jednoho tvrzení. Omezení v podobě nerovnic - podmínky pro vázané extrémy II Předtím zavedeme následující termíny: Podmínky regularity: - vektory a^jsou lineárně nezávislé, nebo - všechna omezení j sou lineární Lagrangeova funkci (lagrangeián): L(x, X) = f(x)-^Xi .ct (x) Omezení v podobě nerovnic - podmínky pro vázané extrémy III A nyní nutné podmínky pro lokální minimum problému (KuhnTuckerovy podmínky). Jeli x* lokálním minimem problému a pokud v x* platí podmínky regularity, pak existují Lagrangeovy činitele X* tak, že x* a X* splňují následující soustavu omezení: VxL(x,^) = 0 Ci(x) = 0, i g E Ci(x) > 0, i g I \ > 0, i g I \ Ci(x) = 0, Vi Omezení v podobě nerovnic - podmínky pro vázané extrémy IV Dále zavedeme dostatečné podmínky pro lokální minimum problému: Nechť pro x* existuje X* tak, že platí KuhnTuckerovy podmínky a platí: ST.Vx2L(x*,?i*).s > 0 pro všechna s ^ 0 taková, že s1^* = 0 pro i e E u I+* sT.ai* > 0 pro i e I0* kde I+* = {i; i e I*, V > 0} V = {í;ígI*, V = 0) Pak x* je ostré lokální minimum úlohy. Omezení v podobě nerovnic - řešení problému Využití klasických optimalizačních metod: Simplexová metoda Metody první derivace (spádové metody, konjugované gradienty) Metody druhé derivace (Newtonovské metody atd.) + respektování omezení při výpočtu kroku 8(k) + testování podmínek, uvedených na předchozích slidech Speciální případy NP - obecně Kvadratické programování: kvadratická účelová funkce, lineární omezení Konvexní programování: účelová funkce i omezení jsou konvexní funkce Separabilní programování: bez smíšených členů (2.xvx2) Lomené programování: účelová funkce a omezení jsou podíly lineárních funkcí Celočíselné programování: všechny nebo některé proměnné musí být celá čísla Kvadratické programování - obecně Přirozeným zobecněním lineárního programování je úloha kvdratického programování: Minimalizuj: q(x) = 1/2.xTGx + gTx Za předpokladů: a^x = bj, i e E a^x > b^ i e I Kvadratické programování - obecně II Tato úloha má význam nejen sama o sobě, ale také proto, že některé metody pro nelineární programování s omezeními převáděj í obecný problém na posloupnost kvadratických problémů. Pokud je Hessova matice G kladně semidefmitní, pak je funkce q konvexní a problém je speciálním případem úlohy konvexního programování a tedy má je jediné minimum. Kvadratické programování - obecně III Naopak úloha min {-xTx; -1 < x{ < 1, i = 1, n} má lokální minimum ve všech vrcholech intervalu [-1, l]n, tj. celkem 2n lokálních minim. Lze dokázat, že úloha kvadratického programování je NPtěžká (vzhledem k n). Kvadratické programování - metody řešení Omezení v podobě rovnic: • Přímá eliminace proměnných • Metoda nulového prostoru Omezení v podobě nerovnic (obecné): • Metoda aktivní množiny Celočíselné programování - obecně Reší úlohy typu: minimalizuj: f(x) za předpokladu: Cj(x) = 0, i e E Ci(x) > 0, i e I přičemž pro všechny složky vektoru řešení x platí: Xj e Z Celočíselné programování - příklad problému Problém batohu: Mějme n předmětů, pro něž jsou zadány veličiny: a= hmotno st j -tého předmětu C: cena j -tého předmětu Batoh je třeba naplnit tak, abychom maximalizovali celkovou cenu nákladu a nepřekročili přitom limit b jeho hmotnosti. Celočíselné programování - příklad problému II Zavedeme proměnné x: (j = 1, 2, ...,n): X: = 1 jestli naložíme j-tý předmět Xj = 0 jinak Matematická formulace úlohy: n max f (x) = y^CjXj j=i Za předpokladu: n 2>jXj q, tím vytvoříme úlohu 2b, a najdeme optimální řešení (nemusí být celočíselné). Celočíselné programování - metoda větví a mezí IV 3) Z optimálních řešení úloh 2a a 2b vybereme tu nadějnější větev (s vyšší hodnotou účelové funkce). V případě, že optimální řešení nadějnější větve ještě není celočíselné, pokračujeme stejně jako v bodě 2. Opakujeme body 2 a 3, dokud nedospějeme k celočíselnému optimálnímu řešení. Celočíselné programování - metoda větví a mezí - příklad Maximalizuj: f(x) = 2x1 + 3x2 Za předpokladu: 4x1 + 3x2 < 13 x1 + 2x2 < 6 xv x2 ^ 0 x-| 5 X2 ~ cgI© Celočíselné programování - metoda větví a mezí - příklad II 1) Nalezení optimálního řešení (x) v R2. Graficky, výsledek: x = (8/5, 11/5), f(x) = 49/5 Celočíselné programování - metoda větví a mezí - příklad III 2) Vybereme xx a interval p < xt < q, tedy je: 1 ^(x1 = 8/5)<2 s Úloha 2a - 1. větev: Přidáme k zadání podmínku: 2 < x Řešení: x' = (2,5/3), f(x> 9 s Úloha 2b - 2. větev: Přidáme k zadání podmínku: x1 < 1 Řešení: x' = (1,5/2), f(x> 19/2 Celočíselné programování - metoda větví a mezí - příklad IV 3) Nadějnější větev je větev 2 => x = (1,5/2) 2) Vybereme x2 a interval p ^ x2 < q, tedy je: 2 <(x2 = 5/2)<3 Úloha 2a - 1. větev: Přidáme k zadání podmínku: x2 < 2 Řešení: x' = (1,2), f(x> 8 STOP Úloha 2b - 2. větev: Přidáme k zadání podmínku: 3 <, x2 Řešení: x' = (0,3), f(x> 9 STOP => Celočíselným optimem je bod x = (0,3) Celočíselné programování - metoda větví a mezí - příklad V Znázornění výpočtu pomocí stromu: x = (8/5, 11/5), f(x) = 49/5 xl9 xx < 1 x = (1, 5/2), f(x) = 19/2 X2' x2 — ^ x = (1, 2), f(x) = 8 x2? X2 — ^ x = (0,3), f(x) = 9 Cvičení - metoda Lagrangeových činitelů Příklad: Minimalizuj _xi2 - 4x22 Za předpokladu: xl + 2x2 = 6 Sestavíme rovnice: ŕ-20 V 8x2 J v2y x1 + 2x2 = 6 Odtud dostáváme: X* = -6, x1* = 3ax2* = 3/2 Cvičení - celočíselné programování Maximalizuj: f(x) = 2x1 + x2 Za předpokladu: x1 + x2 < 5 -x1 + 2x2 < 0 6x1 + 2x2 < 21 x1, x2 > 0 x-| 5 X2 ~ cgI©