Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Matematika III - 5. přednáška Globální (absolutní) extrémy, vázané extrémy, optimalizační metody, lineární programování Michal Bulant Masarykova univerzita Fakulta informatiky 20. 10. 2010 Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Obsah přednášky Q Literatura Q Absolutní (globální) extrémy • Absolutní extrémy • Vázané extrémy • Metoda Lagrangeových multiplikátorů Q Speciální optimalizační metody Q Lineární programování Q Integrální počet více proměnných • Integrály závislé na parametru 9 Integrace funkcí více proměnných • Násobné integrály Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Plán přednášky O Literatura Q Absolutní (globální) extrémy • Absolutní extrémy 9 Vázané extrémy » Metoda Lagrangeových multiplikátorů ©Speciální optimalizační metody Q Lineární programování © Integrální počet více proměnných • Integrály závislé na parametru • Integrace funkcí více proměnných • Násobné integrály Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Zuzana Došlá, Ondřej Došlý, Diferenciální počet funkcí více proměnných, MU Brno, 2006, 150 s. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Zuzana Došlá, Ondřej Došlý, Diferenciální počet funkcí více proměnných, MU Brno, 2006, 150 s. • Zuzana Došlá, Roman Plch, Petr Sojka, Diferenciální počet funkcí více proměnných s programem Maple, MU Brno, 1999, 273 s. (příp. http://www.math.muni.cz/~plch/mapm). Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Zuzana Došlá, Ondřej Došlý, Diferenciální počet funkcí více proměnných, MU Brno, 2006, 150 s. • Zuzana Došlá, Roman Plch, Petr Sojka, Diferenciální počet funkcí více proměnných s programem Maple, MU Brno, 1999, 273 s. (příp. http://www.math.muni.cz/~plch/mapm). • Ján Plesník, Jitka Dupačová, Milan Vlach, Lineárne programovanie, Alfa, 1990. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Zuzana Došlá, Ondřej Došlý, Diferenciální počet funkcí více proměnných, MU Brno, 2006, 150 s. • Zuzana Došlá, Roman Plch, Petr Sojka, Diferenciální počet funkcí více proměnných s programem Maple, MU Brno, 1999, 273 s. (příp. http://www.math.muni.cz/~plch/mapm). • Ján Plesník, Jitka Dupačová, Milan Vlach, Lineárne programovanie, Alfa, 1990. • Boris Pavlovic Děmidovič, Sbírka úloh a cvičení z matematické analýzy, Fragment, 2003. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Zuzana Došlá, Ondřej Došlý, Diferenciální počet funkcí více proměnných, MU Brno, 2006, 150 s. • Zuzana Došlá, Roman Plch, Petr Sojka, Diferenciální počet funkcí více proměnných s programem Maple, MU Brno, 1999, 273 s. (příp. http://www.math.muni.cz/~plch/mapm). • Ján Plesník, Jitka Dupačová, Milan Vlach, Lineárne programovanie, Alfa, 1990. • Boris Pavlovic Děmidovič, Sbírka úloh a cvičení z matematické analýzy, Fragment, 2003. • Předmětové záložky v IS MU Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Plán přednášky Q Literatura Q Absolutní (globální) extrémy • Absolutní extrémy • Vázané extrémy • Metoda Lagrangeových multiplikátorů 9 Speciální optimalizační metody Q Lineární programování ^ Integrální počet více proměnných • Integrály závislé na parametru • Integrace funkcí více proměnných • Násobné integrály Literatur Absolutní (globáln ') extrémy Speciální optimalizační metody Linea rní programov ání Integrální počet více proměnných •ooooooo oooooooooooooo Absolutní extrémy Definice Nechť f : En —> R a M je podmnožinou definičního oboru f. V bodě x* nabývá f absolutního (globálního) maxima (minima) na M, pokud je f(x*) > f(x) (f(x*) < f(x)) pro všechna x e M. Literatur Absolutní (globáln ') extrémy Speciální optimalizační metody Linea rní programov ání Integrální počet více proměnných •ooooooo oooooooooooooo Absolutní extrémy Definice Nechť f : En —> R a M je podmnožinou definičního oboru f. V bodě x* nabývá f absolutního (globálního) maxima (minima) na M, pokud je f(x*) > f (x) (f (x*) < f (x)) pro všechna x e M. Existence extrémů na kompaktní (uzavřené a ohraničené) množině vyplývá z Weierstrassovy věty. Věta Necht M C En je kompaktní množina, f : M —> R spojitá. Pak f nabývá svých absolutních extrémů buď v bodech lokálních extrémů uvnitř M nebo v některém hraničním bodě. Literatur Absolutní (globáln ') extrémy Speciální optimalizační metody Linea rní programov ání Integrální počet více proměnných •ooooooo oooooooooooooo Absolutní extrémy Definice Nechť f : En —> R a M je podmnožinou definičního oboru f. V bodě x* nabývá f absolutního (globálního) maxima (minima) na M, pokud je f(x*) > f (x) (f (x*) < f (x)) pro všechna x e M. Existence extrémů na kompaktní (uzavřené a ohraničené) množině vyplývá z Weierstrassovy věty. Věta Necht M C En je kompaktní množina, f : M —> R spojitá. Pak f nabývá svých absolutních extrémů buď v bodech lokálních extrémů uvnitř M nebo v některém hraničním bodě. Hledání absolutních extrémů funkce na množině tak máme převedeno na nalezení lokálních extrémů (což umíme - vyšetříme stacionární body a body v nichž funkce není diferencovatelná) a vyšetření hraničních bodů. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných o«oooooo oooooooooooooo Příklad Nalezněte extrémy funkce f (x, y) = xy — x2 — y2 + x + y na množině M, která je ohraničena trojúhelníkem, tvořeným souřadnými osami a přímkou x + y — 4 = 0. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných o«oooooo oooooooooooooo Příklad Nalezněte extrémy funkce f (x, y) = xy — x2 — y2 + x + y na množině M, která je ohraničena trojúhelníkem, tvořeným souřadnými osami a přímkou x + y — 4 = 0. Řešení Jediným stacionárním bodem je [1,1], kde nastává absolutní maximum f(l, 1) = 1. Absolutní minimum —12 nastává v hraničních bodech [4,0] a [0,4]. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oo«ooooo oooooooooooooo Vázané extrémy Již dříve jsme se zabývali úlohou nalézt absolutní extrém dané funkce na (uzavřené) množině, což vedlo na vyšetření lokálních extrémů funkce na hranici této množiny. Jinými slovy, na hledání extrémů funkce v bodech, které jsou vázány nějakou další podmínkou. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oo«ooooo oooooooooooooo Vázané extrémy Již dříve jsme se zabývali úlohou nalézt absolutní extrém dané funkce na (uzavřené) množině, což vedlo na vyšetření lokálních extrémů funkce na hranici této množiny. Jinými slovy, na hledání extrémů funkce v bodech, které jsou vázány nějakou další podmínkou. Ukážeme nejprve názorně graficky na případu funkcí dvou proměnných obecnou metodu. Určete lokální extrémy funkce f(x,y) = x2y na množině M dané implicitně rovnicí 5x2 + 2y2 = 14. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných ooo»oooo oooooooooooooo Metoda Lagrangeových multiplikátorů V předchozím příkladu jsme viděli, že normálový vektor (tj. gradient) funkce h, k níž hledáme extrém, musí být ve vyšetřovaném bodě prvkem normálového prostoru k ploše (v temže bodě). Toto samozřejmě platí i obecně. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných ooo»oooo oooooooooooooo Metoda Lagrangeových multiplikátorů V předchozím příkladu jsme viděli, že normálový vektor (tj. gradient) funkce h, k níž hledáme extrém, musí být ve vyšetřovaném bodě prvkem normálového prostoru k ploše (v temže bodě). Toto samozřejmě platí i obecně. Pokud je M ve všech svých bodech grafem hladkého zobrazení, musí být každý extrém P e M stacionárním bodem, tj. pro každou křivku c(ř) C M procházející přes P = c(0) musí být h(c(t)) extrémem pro tuto funkci jedné proměnné. Proto musí platit ^rh(c(t))lt=0 = dc,{0)h(P) = dh(P)(c'(Q)) = 0. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných ooo»oooo oooooooooooooo Metoda Lagrangeových multiplikátorů V předchozím příkladu jsme viděli, že normálový vektor (tj. gradient) funkce h, k níž hledáme extrém, musí být ve vyšetřovaném bodě prvkem normálového prostoru k ploše (v temže bodě). Toto samozřejmě platí i obecně. Pokud je M ve všech svých bodech grafem hladkého zobrazení, musí být každý extrém P e M stacionárním bodem, tj. pro každou křivku c(ř) C M procházející přes P = c(0) musí být h(c(t)) extrémem pro tuto funkci jedné proměnné. Proto musí platit jth(c(t))\t=0 = dc,(0)/7(P) = dft(P)(c'(0)) = 0. Tato vlastnost je ekvivalentní tvrzení, že gradient h leží v normálovém podprostoru (přesněji v jeho zaměření). Takové body P G M budeme nazývat stacionární body funkce h vzhledem k vazbám F. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooo«ooo oooooooooooooo V praxi mívají optimalizační úlohy často m + n parametrů, které jsou vázány n podmínkami. V našem jazyce diferenciálního počtu tedy hledáme extrémy spojitě diferencovatelné funkce h na množině bodů M zadaných implicitně rovnicí F(x\,... ,xm+n) = 0 (F : Em+n —> En\ Normálový prostor k naší množině M je generován řádky Jacobiho matice zobrazení F a stacionární body jsou proto ekvivalentně určeny následujícím tvrzením, kterému se říká metoda Lagrangeových multiplikátorů: Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooo«ooo oooooooooooooo V praxi mívají optimalizační úlohy často m + n parametrů, které jsou vázány n podmínkami. V našem jazyce diferenciálního počtu tedy hledáme extrémy spojitě diferencovatelné funkce h na množině bodů M zadaných implicitně rovnicí F(x\,... ,xm+n) = 0 (F : Em+n —> En\ Normálový prostor k naší množině M je generován řádky Jacobiho matice zobrazení F a stacionární body jsou proto ekvivalentně určeny následujícím tvrzením, kterému se říká metoda Lagrangeových multiplikátorů: Věta Necht F = (fi,..., fn) : Em+n —>• En je spojitě diferencovatelná v okolí bodu P, F{P) = 0 a M je zadána implicitně rovnicí F(xi,... ,xm+n) = 0, přičemž hodnost matice DXF v bodě P je n. Pak P je stacionárním bodem spojitě diferencovatelné funkce h : Em+n —)• R právě, když existují reálné parametry Ai,..., A„ takové, že grad h = Xi grad f\ H-----h A„ grad fn. 19 0,0- Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných ooooo»oo oooooooooooooo Všimněme si počtu neznámých a rovnic v tomto algoritmu: gradienty jsou vektory o m + n souřadnicích, tedy požadavek z věty dává m + n rovnic. Jako neznámé máme jednak souřadnice xi,... ,xm+n hledaných stacionárních bodů P, ale navíc také n parametrů A; v hledané lineární kombinaci. Zbývá však požadavek, že hledaný bod P patří implicitně zadané množině M, což představuje dalších n rovnic. Celkem tedy máme 2n + m rovnic pro 2n + m proměnných a proto lze očekávat, že řešením bude diskrétní množina bodů P (tj. každý z nich bude izolovaným bodem). Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooo«o oooooooooooooo Výklad o vázaných extrémech jsme začali tím, že pro nalezení absolutních extrémů funkce na kompaktní množině často potřebujeme vyšetření extrémů na množině bodů vázaných nějakou podmínkou. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooo«o oooooooooooooo Výklad o vázaných extrémech jsme začali tím, že pro nalezení absolutních extrémů funkce na kompaktní množině často potřebujeme vyšetření extrémů na množině bodů vázaných nějakou podmínkou. Ilustrujme si to na příkladu: Příklad Maximalizujte f(x,y) = 2x + y za podmínky \ + y2 <1. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných 0000000» oooooooooooooo Řešení Množina určená vazební podmínkou je uzavřená a ohraničená, proto zde nabývá jakákoliv spojitá funkce svých extrémů, a to buď ve stacionárních bodech (funkce je zřejmě diferencovatelné na celé vyšetřované množině) nebo na hranici. Snadno se ale přesvědčíme (df(x,y) = (2,1)), že uvnitř množiny extrémy nejsou. Proto maximalizujeme funkci f za podmínky ^- +y2 = 1. 90.0- Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných 0000000» oooooooooooooo Množina určená vazební podmínkou je uzavřená a ohraničená, proto zde nabývá jakákoliv spojitá funkce svých extrémů, a to buď ve stacionárních bodech (funkce je zřejmě diferencovatelné na celé vyšetřované množině) nebo na hranici. Snadno se ale přesvědčíme (df(x,y) = (2,1)), že uvnitř množiny extrémy nejsou. Proto maximalizujeme funkci f za podmínky ^- +y2 = 1. Sestrojíme Lagrangeovu funkci L(x, y, A) = 2x + y - A(^- + y2 - 1). Pak dostáváme: O O L L ■x ■y -2Xy X' .2 O po. O- Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných 0000000» oooooooooooooo Řešení Množina určená vazební podmínkou je uzavřená a ohraničená, proto zde nabývá jakákoliv spojitá funkce svých extrémů, a to buď ve stacionárních bodech (funkce je zřejmě diferencovatelné na celé vyšetřované množině) nebo na hranici. Snadno se ale přesvědčíme (df(x,y) = (2,1)), že uvnitř množiny extrémy nejsou. Proto maximalizujeme funkci f za podmínky ^- + y2 = 1. Sestrojíme Lagrangeovu funkci L(x, y, A) = 2x + y - A(^- + y2 - 1). Pak dostáváme: O O = 2 -= 1 - + y2 2Ay - 1. Odtud snadno x : (resp. A = — ^P, 2A' a tedy A x 2 '•' V17 h= pro minimum). y 17 Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Plán přednášky Q Literatura Q Absolutní (globální) extrémy • Absolutní extrémy 9 Vázané extrémy » Metoda Lagrangeových multiplikátorů Q Speciální optimalizační metody Q Lineární programování Q Integrální počet více proměnných • Integrály závislé na parametru • Integrace funkcí více proměnných • Násobné integrály Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Speciální optimalizační metody Zmiňme se jen ve stručnosti o speciálních optimalizačních technikách, které se v dnešní praxi používají. Zájemce o bližší seznámení s nimi můžeme odkázat na další předměty MU, např.: • Optimalizace - PřF: M0160 (jaro) • Optimalizace - PV027 (jaro) • Lineární programování - PřF: M4110 (jaro) • Matematické programování - PřF: M5170 (podzim) Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Metoda gradientu Již dříve jsme zmínili, že funkce nejrychleji roste ve směru gradientu (a nejrychleji klesá ve směru opačném) - proto je přirozené se při hledání maxima vydat z daného bodu ve směru gradientu (analogie chození do kopce nejprudším svahem). Otázka je, jak dlouho „jít" a jak často gradient počítat (podrobněji viz např. http://en.wikipedia.org/wiki/Gradient_descent). Iterace: xn+1 = xn + 7n grad f (x„), pro dostatečně malé 7„, aby f(xn+i) > f(x„). Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Metoda gradientu Již dříve jsme zmínili, že funkce nejrychleji roste ve směru gradientu (a nejrychleji klesá ve směru opačném) - proto je přirozené se při hledání maxima vydat z daného bodu ve směru gradientu (analogie chození do kopce nejprudším svahem). Otázka je, jak dlouho „jít" a jak často gradient počítat (podrobněji viz např. http://en.wikipedia.org/wiki/Gradient_descent). Iterace: xn+i = xn + 7„ grad f(xn), pro dostatečně malé 7„, aby f(xn+i) > f(x„). Problémy: • náročný opakovaný výpočet 7, • velký počet iterací v případě velmi různorodé křivosti v různých směrech; např Rosenbrockova banánová funkce f(x,y) = (l-x)2 + 100(y-x2)2. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Newtonova optimalizační metoda Newtonova metoda je dobře známý numerický postup pro nalezení kořenů dané reálné funkce f . Známe-li bod xo „rozumně" blízko kořene, zkonstruujeme v bodě [xo, f(xo)] tečnu ke grafu funkce f a za bod xi zvolíme průsečík tečny s osou x. Tento postup opakujeme. Snadno je vidět, že platí rekurentní vztah x"+1-x" f(xny Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Newtonova optimalizační metoda Newtonova metoda je dobře známý numerický postup pro nalezení kořenů dané reálné funkce f . Známe-li bod xo „rozumně" blízko kořene, zkonstruujeme v bodě [xo, f(xo)] tečnu ke grafu funkce f a za bod xi zvolíme průsečík tečny s osou x. Tento postup opakujeme. Snadno je vidět, že platí rekurentní vztah x"+1-x" f(xny Tento postup např. poskytuje efektivní postup pro výpočet \f2 (nebo obecněji y/ď) s libovolnou přesností; pokud bychom ale chtěli hledat řešení rovnice x1/3 = 0, tak snadno vidíme, že metoda diverguje, ať začneme jakkoli blízko 0. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Při hledání extrémů funkcí (i více proměnných) může být Newtona metoda využita pro nalezení stacionárních bodů - v nich musí být derivace nulová, proto jde vlastně o nalezení kořenů derivace iterativním postupem xn+1 =xn- (Wf(xn))_1 • grad f(xn). Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Při hledání extrémů funkcí (i více proměnných) může být Newtona metoda využita pro nalezení stacionárních bodů - v nich musí být derivace nulová, proto jde vlastně o nalezení kořenů derivace iterativním postupem xn+1 =xn- (Wf(xn))_1 • grad f(xn). Výpočet inverze Hessiánu je časově náročná operace, proto se často místo toho využívá » metoda sdružených gradientů pro řešení příslušné soustavy, • různých tzv. /cvazZ-newtonovských metod, využívajících pouze přibližného Hessiánu (např. BFGS) - viz např. http://demonstrations.wolfram.com/ MinimizingTheRosenbrockFunction/ Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Plán přednášky Q Literatura Q Absolutní (globální) extrémy • Absolutní extrémy 9 Vázané extrémy 9 Metoda Lagrangeových multiplikátorů ©Speciální optimalizační metody Q Lineární programování © Integrální počet více proměnných • Integrály závislé na parametru • Integrace funkcí více proměnných • Násobné integrály Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Lineární programování Úloha lineárního programování Pro daná ceM" řeší lineární programování úlohu optimalizovat (tj. maximalizovat nebo minimalizovat) lineární účelovou funkci f(x) = c ■ x = cixi H-----h cnxn Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Lineární programování Úloha lineárního programování Pro daná ceM" řeší lineární programování úlohu optimalizovat (tj. maximalizovat nebo minimalizovat) lineární účelovou funkci f(x) = c ■ x = cixi H-----h cnxn za daných (lineárních) omezení a\ ■ x < b\ ak+i ■ x = bk+i at-x = bt Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Lineární programování Lze ukázat, že každou (rozumnou) úlohu lineárního programování lze převést na tzv. kanonický tvar maximalizovat f (x) = c • x za podmínek a\ ■ x < b\ ak x < bk, kde x = (xi,..., x„), xi > 0,..., x„ > 0. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Lineární programování Lze ukázat, že každou (rozumnou) úlohu lineárního programování lze převést na tzv. kanonický tvar maximalizovat f (x) = c • x za podmínek a\ ■ x < b\ ak x < bk, kde x = (xi,..., x„), xi > 0,..., x„ > 0. Převody: • minimalizace c • x —> maximalizace (—c) • x • nerovnice o rovnice (doplnková proměnná, resp. nahrazení rovnice dvojicí nerovnic) • reálná proměnná x —> nezáporné proměnné (substituce x = x+ - x", x+ > 0, x" > 0). Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Grafické řešení úlohy lineárního programování Úloha lineárního programování má pro 2 proměnné graficky názorný způsob řešení, vycházející z obdobného přístupu jako v případě vázaných extrémů. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Grafické řešení úlohy lineárního programování Úloha lineárního programování má pro 2 proměnné graficky názorný způsob řešení, vycházející z obdobného přístupu jako v případě vázaných extrémů. V rovině si znázorníme množinu, vyhovující všem omezujícím podmínkám a pomocí vrstevnic účelové funkce najdeme bod(y) této množiny, kde nabývá účelová funkce extrémů. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Grafické řešení úlohy lineárního programování Úloha lineárního programování má pro 2 proměnné graficky názorný způsob řešení, vycházející z obdobného přístupu jako v případě vázaných extrémů. V rovině si znázorníme množinu, vyhovující všem omezujícím podmínkám a pomocí vrstevnic účelové funkce najdeme bod(y) této množiny, kde nabývá účelová funkce extrémů. Příklad Maximalizujte hodnotu x + y za podmínek 4x - y < 8 2x + y < 10 5x - 2y > -2 x,y > 0 Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Simplexová metoda Standardní úlohu řeší klasická Simplexová metoda (George Dantzig, 1947). Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Simplexová metoda Standardní úlohu řeší klasická Simplexová metoda (George Dantzig, 1947). Úvodní fáze spočívá v nalezení nějakého vrcholu na polytopu (zobecnění polyedru, tj. mnohostěnu, na více dimenzí), který je tvořen body vyhovujícími podmínkám. V dalších krocích postupuje po hranách do vrcholů s vyšší hodnotou účelové funkce. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Simplexová metoda Standardní úlohu řeší klasická Simplexová metoda (George Dantzig, 1947). Úvodní fáze spočívá v nalezení nějakého vrcholu na polytopu (zobecnění polyedru, tj. mnohostěnu, na více dimenzí), který je tvořen body vyhovujícími podmínkám. V dalších krocích postupuje po hranách do vrcholů s vyšší hodnotou účelové funkce. Sice je ukázán příklad podmínek, kdy simplexová metoda projde nešikovně všech 2" vrcholů (jde o příklad zborcené n-rozměrné krychle), a tedy metoda je v nejhorším případě exponenciální, ale v praxi je obvykle pozoruhodně úspěšná (kolem roku 2000 bylo dokázáno, že očekávaný čas běhu na náhodném vstupu je polynomiální). Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Příklad * Maximalizujte f = 2x — 3y + 4z za podmínek 4x - 3y + z < 3 x + y + z < 10 2x + y - z < 10 x > 0,y > 0,z > 0. Řešení Převedeme úlohu z kanonického do standardního tvaru - k tomu stačí zavést doplňkové proměnné u, v, w. Maximalizujeme 4x - 3y +Z+U = 3 x + y +z + v = 10 2x + y —z + w = 10 2x + 3y -4z +f = 0 90.0- Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Řešení (pokračování) Úlohu přepíšeme do tzv. simplexové tabulky. X y z u v w u 4 -3 1 1 0 0 3 v 1 1 1 0 1 0 10 w 2 1 -1 0 0 1 10 f -2 3 -4 0 0 0 0 V posledním řádku odpovídajícím účelové funkci najdeme některou zápornou hodnotu {heuristika: největší v abs. hodnotě), což odpovídá tomu, že se snažíme postupovat po hraně ve směru proměnné odpovídající příslušnému sloupci. Krajní vrchol této hrany najdeme tak, že najdeme minimum z podílů 3/1,10/1 absolutních členů a kladných koeficientů u proměnné, v jejímž směru se snažíme postupovat. Zde půjde o sloupec proměnné z a eliminovat budeme pomocí 1. řádku ("pivot"je 1) - řádek označíme stejně jako dotyčný sloupec (proměnná přejde do báze). Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Řešení (pokračování) X y z u v w z 4 -3 1 1 0 0 3 v -3 4 0 -1 1 0 7 w 6 -2 0 1 0 1 13 f 14 -9 0 4 0 0 12 Nyní máme jediný záporný prvek v posledním řádku (sloupec y) a v něm jediný kladný prvek, proto pivotujeme podle 4 ve 2. řádku. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Řešení (dokončení) X y Z u 1/ M/ z 7 4 0 1 i 4 3 4 0 33 4 y 3 4 1 0 1 4 1 4 0 7 4 w 9 2 0 0 1 2 1 2 1 33 2 f 29 4 0 0 / 4 9 4 1 111 4 Nyní již máme všechny prvky v posledním řádku kladné, dosáhli jsme tedy maxima pro z = j, y = ^ a w = 4p. Původní proměnná x je nyní nebazická (x není uvedeno jako označení žádného řádku nebo ekvivalentně: sloupec x není eliminovaný), což odpovídá x = 0. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooooooooo Plán přednášky © Literatura Q Absolutní (globální) extrémy • Absolutní extrémy 9 Vázané extrémy 9 Metoda Lagrangeových multiplikátorů ©Speciální optimalizační metody © Lineární programování Q Integrální počet více proměnných • Integrály závislé na parametru 9 Integrace funkcí více proměnných • Násobné integrály Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných OOOOOOOO «0000000000000 Připomenutí: Riemannův integrál Motivace: výpočet plochy mezi grafem funkce f(x) a osou x na uzavřeném intervalu. Funkce f : R —> R jedné proměnné ohraničená na uzavřeném intervalu [a, b]). •A.iA Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných OOOOOOOO 0*000000000000 Zvolíme dělení D = {xi = a,... ,x„ = b} intervalu [a, b] a hledaný integrál (tj. plochu pod grafem) aproximujeme součtem /%(x)dx^f(6)(x,+1-x,), Ja ;=i kde G [x/,xf+1] je libovolný. (Součet ploch obdélníků pod křivkou). Zvolíme dělení D = {xi = a,... ,x„ = b} intervalu [a, b] a hledaný integrál (tj. plochu pod grafem) aproximujeme součtem kde G [x/,xf+1] je libovolný. (Součet ploch obdélníků pod křivkou). Je-li norma dělení (tj. maximum z délek intervalů [x,-, xf+1]) malá, pak výše uvedená suma je velmi blízko zmíněné ploše (přesněji pomocí nulové posloupnosti delenia limit). b n-l Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oo«ooooooooooo Připomenutí: Riemannův integrál Vlastnosti: Množina Riemannovsky měřitelných funkcí na intervalu [a, b] tvoří vektorový prostor a integrál je na něm lineární formou. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oo«ooooooooooo Připomenutí: Riemannův integrál Vlastnosti: Množina Riemannovsky měřitelných funkcí na intervalu [a, b] tvoří vektorový prostor a integrál je na něm lineární formou. Aplikace: • plocha ohraničená grafy 2 funkcí j^[f(x) — g(x)]dx, Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oo«ooooooooooo Připomenutí: Riemannův integrál Vlastnosti: Množina Riemannovsky měřitelných funkcí na intervalu [a, b] tvoří vektorový prostor a integrál je na něm lineární formou. Aplikace: • plocha ohraničená grafy 2 funkcí j^[f(x) — g(x)]dx, • délka křivky zadané parametricky f£ ^íp'(t)2 + tp'(t)2dt, Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oo«ooooooooooo Připomenutí: Riemannův integrál Vlastnosti: Množina Riemannovsky měřitelných funkcí na intervalu [a, b] tvoří vektorový prostor a integrál je na něm lineární formou. Aplikace: • plocha ohraničená grafy 2 funkcí j^[f(x) — g(x)]dx, • délka křivky zadané parametricky f£ ^íp'(t)2 + tp'(t)2dt, • objem rotačního tělesa ir f2(x)dx, Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oo«ooooooooooo Připomenutí: Riemannův integrál Vlastnosti: Množina Riemannovsky měřitelných funkcí na intervalu [a, b] tvoří vektorový prostor a integrál je na něm lineární formou. Aplikace: • plocha ohraničená grafy 2 funkcí j^[f(x) — g(x)]dx, • délka křivky zadané parametricky f£ ^íp'(t)2 + tp'(t)2dt, • objem rotačního tělesa ir f2(x)dx, 9 povrch pláště rotačního tělesa 2ir f(x)^/l + [f'(x)]2dx. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo ooo«oooooooooo Integrály závislé na parametru Jestliže integrujeme podle jedné proměnné x funkci n + 1 proměnných f(x,y\,... ,yn), potom výsledek bude funkcí F(yi,... ,yn) ve zbývajících n proměnných. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo ooo«oooooooooo Integrály závislé na parametru Jestliže integrujeme podle jedné proměnné x funkci n + 1 proměnných f(x,y\,... ,yn), potom výsledek bude funkcí F(yi,... ,yn) ve zbývajících n proměnných. Věta (O záměně derivace a integrálu) Pro spojitě diferencovatelnou funkci f(x,yi,... ,yn) definovanou pro x z konečného intervalu [a,fi\ a na nějakém okolí bodu a = [a\,..., an] G En uvažujme integrál ŕ F{yi, ■ ■ ■ ,yn) = j f{x,yi,...,yn)dx. Potom platí pro všechny indexy j = 1,..., n OF ŕ df dyj J a dyj Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooo»ooooooooo Integrace funkcí více proměnných Obdobně jako v případě jedné proměnné můžeme potřebu zavedení integrálu více proměnných motivovat výpočtem objemu trojrozměrného prostoru pod grafem funkce z = f(x,y) dvou proměnných. M isto výběru malých intervalů [x/,x,-+i] dělících celý interval, přes který integrujeme, a přiblížením příslušné části objemu ploškou obdélníku s výškou danou hodnotou funkce f v reprezentantu tohoto intervalu tj. výrazem f(6)(*/+i - */) budeme pracovat s děleními v obou proměnných a hodnotami reprezentujícími výšku grafu nad tímto obdélníčkem v rovině. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooo»ooooooooo Integrace funkcí více proměnných Obdobně jako v případě jedné proměnné můžeme potřebu zavedení integrálu více proměnných motivovat výpočtem objemu trojrozměrného prostoru pod grafem funkce z = f(x,y) dvou proměnných. M isto výběru malých intervalů [x/,x,-+i] dělících celý interval, přes který integrujeme, a přiblížením příslušné části objemu ploškou obdélníku s výškou danou hodnotou funkce f v reprezentantu tohoto intervalu tj. výrazem f(6)(*/+i - */) budeme pracovat s děleními v obou proměnných a hodnotami reprezentujícími výšku grafu nad tímto obdélníčkem v rovině. Co jsou obory integrace? Nejjednodušším přístupem je uvažovat pouze obory integrace S, které jsou dány jako součiny intervalů, tj. jsou zadány rozsahem x G [a, b] a y e [c, d]. Hovoříme v této souvislosti o vícerozměrnémninte»valu-. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo ooooo«oooooooo Pokud je S jiná ohraničená množina v R2, pracujeme místo ní s dostatečně velikou oblastí [a, b] x [c, d], ale upravíme naši funkci tak, že f(x,y) = 0 pro všechny body mimo S. Definice Riemannova integrálu věrně sleduje náš postup pro jednu proměnnou. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo ooooo«oooooooo Pokud je S jiná ohraničená množina v R2, pracujeme místo ní s dostatečně velikou oblastí [a, b] x [c, d], ale upravíme naši funkci tak, že f(x,y) = 0 pro všechny body mimo S. Definice Riemannova integrálu věrně sleduje náš postup pro jednu proměnnou. Integrál existuje, jestliže pro každou volbu posloupnosti dělení E (nyní ve všech proměnných zároveň) a reprezentantů jednotlivých krychliček j e [xí,xí+1] x ... x [zj,zJ+1] c R", s maximální velikostí mezi všemi použitými intervaly jdoucí k nule, budou integrální součty Se,S = f(6v..j)(*/+i - */) • • • (zj+i ~ zj). konvergovat k jedné hodnotě, kterou zapisujeme f(x,...,z)dx.. .dz Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooo»ooooooo Pro všechny spojité funkce f lze opět dokázat existenci Riemannova integrálu a tento výsledek lze snadno rozšířit pro „dostatečně spojité" funkce na „dostatečně rozumných" oborech integrace. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooo»ooooooo Pro všechny spojité funkce f lze opět dokázat existenci Riemannova integrálu a tento výsledek lze snadno rozšířit pro „dostatečně spojité" funkce na „dostatečně rozumných" oborech integrace. Definice Omezenou množinu ScE„ označujeme za Riemannovsky měřitelnou, jestliže je její charakteristická funkce, definovaná X(x) = 1 pro x G S a %(x) = 0 jinak, Riemannovsky integrovatelná. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo ooooooo«oooooo Definice Riemannova integrálu sice nedává rozumný návod, jak hodnoty integrálů skutečně vypočíst (kromě využití výpočetní techniky, kdy je přímé použití definice na místě), okamžitě ale vede k základním vlastnostem Riemannova integrálu (srovnejte s vlastnostmi integrálu v jedné proměnné): Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo ooooooo«oooooo Definice Riemannova integrálu sice nedává rozumný návod, jak hodnoty integrálů skutečně vypočíst (kromě využití výpočetní techniky, kdy je přímé použití definice na místě), okamžitě ale vede k základním vlastnostem Riemannova integrálu (srovnejte s vlastnostmi integrálu v jedné proměnné): Množina Riemannovsky integrovatelných funkcí na vícerozměrném intervalu ScE„ je vektorovým prostorem a Riemannův integrál je na něm lineární formou. Pokud je obor integrace S zadán jako disjunktní sjednocení konečně mnoha Riemannovsky měřitelných oborů Sj, je integrál funkce f přes S dán součtem integrálů přes obory Sj. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooo»ooooo ' Příklad * Vypočtěte dvojný integrál / xy dxdy i[0,l]x[0,l] jako limitu integrálního součtu. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo oooooooo»ooooo Příklad Vypočtěte dvojný integrál / xy dxdy i[0,l]x[0,l] jako limitu integrálního součtu. Řešení Za nulovou posloupnost dělení uvážíme posloupnost (Dn)^L1, kde n-té dělení dostaneme pomocí přímek x = i/n, y = j/n pro i, j = 1, 2,..., n — 1, přičemž hodnoty £;j budeme vybírat z pravých horních rohů dělících čtverečků. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných oooooooo ooooooooo«oooo Řešení (dokončení) Pak [0,11x10,1i ™0 • • • > xn) dxi) dxn Jai \Ja2 \-Jan / / nezávislý na pořadí, ve kterém postupně integraci provádíme. Literatura Absolutní (globální) extrémy Speciální optin oooooooo Příklad (nezávislé meze integrace) Vypočtěte dvojný integrál 1=1 3(x - l)2 + (y - 2)2 + 2 dxdy. J [0,1] X [0,3] Literatur Absolutní (globáln ') extrémy Speciální optimalizač ní metody Linea rní programov ání Integrální počet více proměnných oooooooo OOOOOOOOOOOO0O Příklad (nezávislé meze integrace) Vypočtěte dvojný integrál 1=1 3(x - l)2 + (y - 2)2 + 2 dxdy. J [0,1] X [0,3] Řešení S využitím předchozí věty dostáváme / = £ (jí1 3(x - l)2 + (y - 2)2 + 2dx^j dy = = f [{x-lf+x{y-2f + 2x]1x=Qdy Jo = J (y-2)2 + 3dy = [^y-2)3 + 3y]3Q = 12 Stejný výsledek dostaneme i při integraci v opačném pořadí. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných OOOOOOOO OOOOOOOOOOOOO* Příklad (závislé meze integrace) Vypočtěte integrál xy dxdy, kde S je plocha v 1. kvadrantu E2 ohraničená grafy funkcí y = x a 2 y = x . Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných OOOOOOOO OOOOOOOOOOOOO* Příklad (závislé meze integrace) Vypočtěte integrál / = J xy2 dxdy, kde S je plocha v 1. kvadrantu E2 ohraničená grafy funkcí y = x a 2 y = x . Řešení Snadno je vidět, že grafy se protínají v bodech [0,0] a [1,1], přičemž pro x e [0,1] je x2 < x. Literatura Absolutní (globální) extrémy Speciální optimalizační metody Lineární programování Integrální počet více proměnných OOOOOOOO OOOOOOOOOOOOO* Příklad (závislé meze integrace) Vypočtěte integrál / = J xy2 dxdy, kde S je plocha v 1. kvadrantu E2 ohraničená grafy funkcí y = x a 2 y = x . Řešení Snadno je vidět, že grafy se protínají v bodech [0,0] a [1,1], přičemž pro x e [0,1] je x2 < x. Proto je y=xz dx