Nelineární optimalizace s omezeními - obecně •Většinu spojitých optimalizačních problémů lze vyjádřit následujícím způsobem: • minimalizuj: • f(x), x Î Rn • za předpokladu: • ci(x) = 0, i Î E • ci(x) ³ 0, i Î I Nelineární optimalizace s omezeními - obecně II •Účelová funkce f, stejně jako funkce ci, určující omezení, jsou 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 Ñci jako ai. 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 Î Rn | ci(x) = 0, i Î E; ci(x) ³ 0, i Î I} • •Přípustný bod x* Î E, splňující omezující podmínky, nazveme omezeným lokálním minimem problému, pokud existuje okolí W(x*) bodu x* tak, že pro všechna x Î W(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 Î A(x), pak x je na hranici oblasti definované i-tým omezením. •Velmi důležitá je 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 Î Rn •za předpokladu: • ci(x) = 0, i Î E • ci(x) ³ 0, i Î I •kde • I = Æ Omezení v podobě rovnic - eliminace proměnných •Jestliže jsou 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) = -x1 - x2 •Za předpokladu: x12 + x22 = 1 •Řešení: • • 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 l* splňující rovnice: • • • ci(x) = 0, i Î E • •Kde: g(x) gradient f(x) • ai(x) Ñci(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 x1 + x2 •Za předpokladu: x12 - x2 = 0 •Sestavíme rovnice: • • • x12 - x2 = 0 •Odtud dostáváme: • l* = -1, x1* = -1/2 a x2* = 1/4 Omezení v podobě nerovnic - obecně •Nyní opět rozšíříme své úvahy na obecnou nelineární optimalizační úlohu: •Minimalizuj: • f(x), x Î Rn •za předpokladu: • ci(x) = 0, i Î E • ci(x) ³ 0, i Î 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* Ç I. •Pokud x* je lokálním minimem, pak musí splňovat následující podmínky: • • • • a zároveň li* ³ 0, i Î 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) = - x1 - x2 •Za předpokladů: c1(x) = x2 - x12 ³ 0 • c2(x) = 1 - x12 - 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: • • • • •=> Aktivní omezení je pouze omezení 2. • Omezení v podobě nerovnic – příklad III •Rovnice: • kde: li* ³ 0, i Î I* • •Tedy budou pro náš příklad vypadat následovně: • -1 = -2l2x1 • -1 = -2l2x2 • 1 - x12 - x22 = 0 •Uvedená soustava má dvě řešení, ale jen u jednoho z nich je l2 ³ 0: l2 = x1 = x2 = 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* = Æ Je zřejmé, že toto neplatí. • b) A* = {1} Neexistuje řešení, pro které by • bylo l1 ³ 0. • c) A* = {1,2} Neexistuje řešení, pro které by bylo • zároveň l1 ³ 0 a l2 ³ 0. • d) A* = {2} Tady řešení existuje :-). Omezení v podobě nerovnic - podmínky pro vázané extrémy •Na předchozích slidech jsme 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 ai*jsou lineárně nezávislé, nebo –všechna omezení jsou lineární – •Lagrangeova funkci (lagrangeián): • • • 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 l* tak, že x* a l* splňují následující soustavu omezení: • ÑxL(x,l) = 0 • ci(x) = 0, i Î E • ci(x) ³ 0, i Î I • li ³ 0, i Î I • li ci(x) = 0, "i 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 l* tak, že platí KuhnTuckerovy podmínky a platí: • sT.Ñx2L(x*,l*).s > 0 • pro všechna s ¹ 0 taková, že • sT.ai* = 0 pro i Î E È I+* • sT.ai* ³ 0 pro i Î I0* •kde • I+* = {i; i Î I*, li* > 0} • I0* = {i; i Î I*, li* = 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 d(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.x1.x2) 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) = ½.xTGx + gTx • Za předpokladů: • aiTx = bi, i Î E • aiTx ³ bi, i Î 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ě semidefinitní, 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 £ xi £ 1, i = 1, …, n} •má lokální minimum ve všech vrcholech intervalu [-1, 1]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ě • Řeší úlohy typu: • minimalizuj: • f(x) • za předpokladu: • ci(x) = 0, i Î E • ci(x) ³ 0, i Î I –přičemž pro všechny složky vektoru řešení x platí: xi Î 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: •aj hmotnost j-tého předmětu •cj cena j-tého předmětu •Batoh je třeba naplnit tak, abychom maximalizovali celkovou cenu nákladu a nepřekročíli přitom limit b jeho hmotnosti. • Celočíselné programování - příklad problému II •Zavedeme proměnné xj (j = 1, 2, ...,n): •xj = 1 jestli naložíme j-tý předmět •xj = 0 jinak •Matematická formulace úlohy: • • •Za předpokladu: • xj Î{0, 1}; j = 1, 2, …, n • Celočíselné programování - metody řešení •Metody řezných (sečných) nadrovin •Gomoryho algoritmus •Metoda větví a mezí •Speciální metody (maďarská metoda atd.) • • Celočíselné programování - metoda větví a mezí •V současné době nejpoužívanější metoda celočíselného programování. •Metoda je dostatečně obecná, takže ji lze použít na mnoho úloh. •Využívá se pro řešení celočíselných úloh LP i v rámci profesionálních programových systémů. Celočíselné programování - metoda větví a mezí II •Předpokládejme, že jsme nalezli optimální řešení, jehož některé (nebo všechny) složky xi nesplňují podmínku celočíselnosti. Postupujeme následovně: •1)Vybereme takové xi z optimálního řešení, které není celočíselné. (Při více takových xi nezáleží na tom, které vybereme.) Zvolíme interval: p £ xi £ q, • kde p je nejbližší menší celé číslo a q nejbližší větší celé číslo vzhledem k xi. Vzhledem k tomu, že celočíselné řešení není uvnitř intervalu (p,q), hledáme ho vně. Celočíselné programování - metoda větví a mezí III •2) Přidáme k původní úloze podmínku ve tvaru xi £ p, tím vytvoříme úlohu 2a, a najdeme optimální řešení (nemusí být celočíselné). • • Poté přidáme k původní úloze (tzn. úloze bez xi £ p) podmínku ve tvaru xi ³ 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 • Minimalizuj: • f(x) = 2x1 + 3x2 • Za předpokladu: • 4x1 + 3x2 £ 13 • x1 + 2x2 £ 6 • x1, x2 ³ 0 • x1, x2 - celé • 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 x1 a interval p £ x1 £ q, • tedy je: 1 £ (x1 = 8/5) £ 2 • Úloha 2a – 1. větev: • Přidáme k zadání podmínku: 2 £ x1 • Řešení: x´ = (2, 5/3), f(x´)= 9 • Ú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 x1, x1 ³ 2 x = (2, 5/3), f(x) = 9 x1, x1 £ 1 x = (1, 5/2), f(x) = 19/2 x2, x2 £ 2 x = (1, 2), f(x) = 8 x2, x2 ³ 3 x = (0, 3), f(x) = 9 Cvičení - metoda Lagrangeových činitelů •Příklad: •Minimalizuj -x12 - 4x22 •Za předpokladu: x1 + 2x2 = 6 •Sestavíme rovnice: • • • x1 + 2x2 = 6 •Odtud dostáváme: • l* = -6, x1* = 3 a x2* = 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 • x1, x2 - celé