Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooooc Matematika III - 4. přednáška Funkce více proměnných: Zobrazení mezi euklidovskými prostory, inverzní zobrazení a implicitně definované zobrazení Michal Bulant Masarykova univerzita Fakulta informatiky 13. 10. 2010 Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooooc Obsah přednášky Q Literatura Q Zobrazení mezi euklidovskými prostory • Zobrazení a transformace • " Chain Rule" • Věta o inverzním zobrazení • Implicitně zadaná zobrazení Q Tečny a normály k implicitně zadaným plochám • Gradient funkce • Tečné a normálové prostory Q Vázané extrémy • Metoda Lagrangeových multiplikátorů • Speciální optimalizační metody Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooooc Plán přednášky Q Literatura Q Zobrazení mezi euklidovskými prostory a Zobrazení a transformace a " Chain Rule" • Věta o inverzním zobrazení • Implicitně zadaná zobrazení Q Tečny a normály k implicitně zadaným plochám • Tečné a normálové prostory Q Vázané extrémy » Metoda Lagrangeových multiplikátorů • Speciální optimalizační metody Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooooc Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooooc 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 Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooooc 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 Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooooc 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). 9 Předmětové záložky v IS MU Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooooc Obsah první písemky • určování limit, resp. důkaz neexistence, spojitost Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooooc Obsah první písemky • určování limit, resp. důkaz neexistence, spojitost • výpočty parciálních a směrových derivací Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooooc Obsah první písemky • určování limit, resp. důkaz neexistence, spojitost • výpočty parciálních a směrových derivací • použití diferenciálu - aproximace, tečná nadrovina Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooooc Obsah první písemky • určování limit, resp. důkaz neexistence, spojitost • výpočty parciálních a směrových derivací • použití diferenciálu - aproximace, tečná nadrovina • využití Taylorovy věty a Hessiánu pro aproximaci Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooooc Plán přednášky Q Literatura Q Zobrazení mezi euklidovskými prostory • Zobrazení a transformace • " Chain Rule" • Věta o inverzním zobrazení • Implicitně zadaná zobrazení Q Tečny a normály k implicitně zadaným plochám • Tečné a normálové prostory Q Vázané extrémy » Metoda Lagrangeových multiplikátorů • Speciální optimalizační metody Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy •oooooooooooooooo ooooooo ooooooooooooc Zobrazení F : En —> Em je při zvolených kartézských souřadnicích na obou stranách obyčejná m-tice F(xi,... ,x„) = (fi(xi,... ,x„),..., fm(x1,... ,xn)) funkcí fj : En —>■ R. Řekneme, že F je diferencovatelné nebo spojitě diferencovatelné zobrazení, jestliže tuto vlastnost mají všechny funkce f\,..., fm. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy •oooooooooooooooo ooooooo ooooooooooooc Zobrazení F : En —> Em je při zvolených kartézských souřadnicích na obou stranách obyčejná m-tice F(xi,... ,x„) = (fi(xi,... ,x„),..., fm(x1,... ,xn)) funkcí fj : En —>■ R. Řekneme, že F je diferencovatelné nebo spojitě diferencovatelné zobrazení, jestliže tuto vlastnost mají všechny funkce f\,..., fm. Diferencovatelná zobrazení F : En —> En, která mají inverzní zobrazení G : En —> En definované na celém svém obrazu, se nazývají (diferencovatelné) transformace. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy •oooooooooooooooo ooooooo ooooooooooooc Zobrazení F : En —> Em je při zvolených kartézských souřadnicích na obou stranách obyčejná m-tice F(xi,... ,x„) = (fi(xi,... ,x„),..., fm(x1,... ,xn)) diferencovatelné zobrazení, jestliže tuto vlastnost mají všechny funkce f\,..., fm. Diferencovatelná zobrazení F : En —> En, která mají inverzní zobrazení G : En —> En definované na celém svém obrazu, se nazývají (diferencovatelné) transformace. Příkladem transformace v e2 je přechod mezi polárními a kartézkými souřadnicemi: Řekneme, že F je diferencovatelné nebo spojitě [r, 0] h> [r cos6>, r sin 0] s inverzi [x,y] 1 y [a/x2 + y2,arctg-], [0,y] ^ [y,-sgny]. Tečny a nor ooooooo ály k implicitně zadaným plochá Lineární zobrazení dfj(x) : E" —> R lineárně aproximují přírůstky f;. I í\ Definice df2(x) ĚÍL dxx df2 dxi ĚÍL dxo df2 8x2 % 8x„ w dfjr, dxi dfm 8x2 8fm , ■ dxj se nazývá Jacobiho matice zobrazení F v bodě x. Lineární zobrazení D1F(x) definované na přírůstcích v = (y\,..., vn) pomocí stejně značené Jacobiho matice nazýváme diferenciál zobrazení F v bodě x z definičního oboru, jestliže lim 1/-Í-0 -{F{x + v) - F(x) - D1F(x)(v)) = 0. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy oo«oooooooooooooo ooooooo ooooooooooooc Důsledek Věty o existenci diferenciálu pro funkce n proměnných je: Věta Necht F : En —> Em je zobrazení, jehož všechny souřadné funkce mají spojité parciální derivace v okolí bodu x e En. Pak existuje diferenciál D1F(x) zobrazení F zadaný Jacobiho maticí. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooo«ooooooooooooo ooooooo ooooooooooooc Diferenciál složeného zobrazení Věta ("Chain rule") Necht F : En —>• Em a G : Em —>• Er jsou dvě diferencovatelná zobrazení, přičemž definiční obor G obsahuje celý obor hodnot F. Pak také složené zobrazení G o F je diferencovatelné a jeho diferenciál je v každém bodě z definičního obodu F kompozicí diferenciálů D\G o F)(x) = D1G{F{x)) o D1F{x). Příslušná Jacobiho matice je dána součinem příslušných Jacobiho matic. Zobrazení mezi euklidovskými prostory oooo»oooooooooooo Tečny a nor ooooooo ály k implicitně zadaným plochá Polární souřadnice vzniknou z kartézských souřadnic transformací F : Ei —> Ei, kterou v souřadnicích [x,y] a [r, Ei, kterou v souřadnicích [x,y] a [r, R v polárních souřadnicích g(r, K: D1 (g o F)(x) = DV(F(x)) o D1 F {x) = (dr dr \ dx dy \ d

R inverzní funkce f_1 existuje (nezaměňujme značení s funkcí x i—> (f (x))_1), pak je dána jednoznačně kterýmkoliv ze vztahů f_1 o f = idR, f o f_1 = idR,. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy oooooo»oooooooooo ooooooo ooooooooooooc Věta o inverzní funkci jedné proměnné - připomenutí Pokud k dané funkci f : R —> R inverzní funkce f_1 existuje (nezaměňujme značení s funkcí x i—> (f (x))_1), pak je dána jednoznačně kterýmkoliv ze vztahů f_1 o f = idR, f o f_1 = idR,. Pokud bychom věděli, že pro diferencovatelnou funkci f je i f_1 diferencovatelná, vztah pro derivaci složené funkce nám (pro y = f{x)) dává i = (id)'(x) = (r1 o o'(x) = (f-1)'^)) • f(x) a tedy přímo víme formuli (zjevně f'(x) v takovém případě nemůže být nulové) (f-1)'^)) = jfa. Věta Je-li f diferencovatelná funkce na okolí bodu xo a f'(xo) ^ 0, pak existuje na nějakém okolí bodu yo = f(xo) funkce f_1 inverzní k f a platí vztah t 1 fM' Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám ooooooo«ooooooooo ooooooo Vázané extrémy ooooooooooooc Věta o inverzním zobrazení Věta Nechi F : En —>• En je spojitě diferencovatelné zobrazení na nějakém okolí bodu x* e En a nechi je Jacobiho matice D1F(x*) invertibilní. Pak na nějakém okolí bodu x* existuje inverzní zobrazení F-1 a jeho diferenciál v bodě F(x*) je inverzním zobrazením k D1F(x*), tzn. je zadán inverzní maticí k Jacobiho matici zobrazení F v bodě x*. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooo«ooooooooo ooooooo ooooooooooooc Věta o inverzním zobrazení Věta Nechi F : En —>• En je spojitě diferencovatelné zobrazení na nějakém okolí bodu x* e En a nechi je Jacobiho matice D1F(x*) invertibilní. Pak na nějakém okolí bodu x* existuje inverzní zobrazení F-1 a jeho diferenciál v bodě F(x*) je inverzním zobrazením k D1F(x*), tzn. je zadán inverzní maticí k Jacobiho matici zobrazení F v bodě x*. Princip důkazu: Z pravidla pro derivování složené funkce vyplývá, že pokud diferencovatelná inverze existuje, pak musí být její Jacobiho matice inverzí k původní Jacobiho matici (srovnejte s případem 1 proměnné). Důkaz poměrně komplikovaným způsobem vyvozuje, že díky invertovatelnosti Jacobiho matice existuje diferencovatelná inverze. Tečny a nor ooooooo ály k implicitně zadaným plochá Příklad Rozhodněte, zda zobrazení F = (f,g) : K' souřadnicích f (x, y) = xy, g(x, y) definované po x y je prosté v okolí bodu [2,1]. V kladném případě určete Jacobiho matici inverzního zobrazení v bodě F(2,1). Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooo«ooooooo ooooooo ooooooooooooc Věta o implicitní funkci - neformální připomenutí Pokud máme zadánu funkci f(x) vzorcem y = f{x), hovoříme o jejím explicitním zadání. Obecnějším zadáním funkce je rovnice F(x,y) = 0, kde závislá proměnná y představuje „neznámou" funkci. Pokud tuto rovnici nelze (nebo to nepotřebujeme) vyřešit vzhledem k y, pak hovoříme o funkci zadané implicitně. Avšak i v tomto obecnějším případě budeme schopni vypočítat y'(x) (aniž bychom znali explicitní vzorec pro y(x)), a to pomocí pravidla pro derivaci složené funkce. Příklad Rovnice y2 = x definuje dvě diferencovatelné funkce yi = y/x, y2 = -yfx Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooo«ooooooo ooooooo ooooooooooooc Věta o implicitní funkci - neformální připomenutí Pokud máme zadánu funkci f(x) vzorcem y = f{x), hovoříme o jejím explicitním zadání. Obecnějším zadáním funkce je rovnice F(x,y) = 0, kde závislá proměnná y představuje „neznámou" funkci. Pokud tuto rovnici nelze (nebo to nepotřebujeme) vyřešit vzhledem k y, pak hovoříme o funkci zadané implicitně. Avšak i v tomto obecnějším případě budeme schopni vypočítat y'(x) (aniž bychom znali explicitní vzorec pro y(x)), a to pomocí pravidla pro derivaci složené funkce. Příklad * Rovnice y2 = x definuje dvě diferencovatelné funkce yi = v*, Y2 = -V* Při derivování implicitně zadaných funkcí obsahuje výsledná derivace y' jak proměnnou x tak proměnnou y (na rozdíl od běžného derivování funkce, kdy je ve výsledku pouze proměnná x). Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy OOOOOOOOOO0OOOOOO ooooooo ooooooooooooc Věta o implicitní funkci ro jednoduchost vyložíme ideu v rovině E^'. Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy OOOOOOOOOO0OOOOOO ooooooo ooooooooooooc Věta o implicitní funkci Pro jednoduchost vyložíme ideu v rovině E^. Pro spojitě diferencovatelnou funkci f(x,y) : e2 —> R hledejme body [x,y], ve kterých platí f(x,y) = 0. Příkladem může být třeba obvyklá (implicitní) definice přímek a kružnic: f(x, y) = ax + by + c = 0 f(x,y) = (x - s)2 + (y - í)2 - r2 = 0, r > 0. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy OOOOOOOOOO0OOOOOO ooooooo ooooooooooooc Věta o implicitní funkci Pro jednoduchost vyložíme ideu v rovině E^. Pro spojitě diferencovatelnou funkci f(x,y) : E2 —> K hledejme body [x,y], ve kterých platí f(x,y) = 0. Příkladem může být třeba obvyklá (implicitní) definice přímek a kružnic: f(x, y) = ax + by + c = 0 f(x,y) = (x - s)2 + (y - í)2 - r2 = 0, r > 0. V prvním případě je (při b 7^ 0) předpisem zadaná funkce y = f (x) = - pro všechna x. Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy OOOOOOOOOO0OOOOOO ooooooo ooooooooooooc Věta o implicitní funkci Pro jednoduchost vyložíme ideu v rovině E^. Pro spojitě diferencovatelnou funkci f(x,y) : e2 —> R hledejme body [x,y], ve kterých platí f(x,y) = 0. Příkladem může být třeba obvyklá (implicitní) definice přímek a kružnic: f(x, y) = ax + by + c = 0 f(x,y) = (x - s)2 + (y - í)2 - r2 = 0, r > 0. V prvním případě je (při b 7^ 0) předpisem zadaná funkce y = f (x) = - pro všechna x. Ve druhém případě umíme pouze pro [a, b] splňující rovnici kružnice a b 7^ t najít okolí bodu a, na kterém nastane jedna z možností: y = f (x) = t + \J (x — s)2 — r, y = f (x) = ŕ - yJ{x-sY-r. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooo«ooooo ooooooo ooooooooooooc Body [s ± r, ř] také vyhovují rovnici kružnice, platí v nich ale Fy(s ± r, ř) = O, což znamená, že tečna ke kružnici v těchto bodech je rovnoběžná s osou y. V těchto bodech neumíme najít okolí, na němž by kružnice byla popsána jako funkce y = f {x). Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooo«ooooo ooooooo ooooooooooooc Body [s ± r, ř] také vyhovují rovnici kružnice, platí v nich ale Fy(s ± r, ř) = O, což znamená, že tečna ke kružnici v těchto bodech je rovnoběžná s osou y. V těchto bodech neumíme najít okolí, na němž by kružnice byla popsána jako funkce y = f {x). Navíc umíme spočítat i derivace: 'W 1 2(x - s) 2 V(* " s)2 " y-t x — s X y Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooo«ooooo ooooooo ooooooooooooc Body [s ± r, ř] také vyhovují rovnici kružnice, platí v nich ale Fy(s ± r, ř) = O, což znamená, že tečna ke kružnici v těchto bodech je rovnoběžná s osou y. V těchto bodech neumíme najít okolí, na němž by kružnice byla popsána jako funkce y = f {x). Navíc umíme spočítat i derivace: fl = 1 2(x-s) = x-s = _Fx 2 y/(x - s)2 - r2 y-t Fy Naopak, pokud budeme chtít najít závislost x = f(y) takovou, aby F{f(y), y) = O, pak v okolí bodů (s ± r, t) bez problémů uspějeme. Všimněme si, že v těchto bodech je parciální derivace Fx nenulová. Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy OOOOOOOOOOOO0OOOO ooooooo ooooooooooooc Shrňme pozorování (pro pouhé dva příklady): Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy OOOOOOOOOOOO0OOOO ooooooo ooooooooooooc Shrňme pozorování (pro pouhé dva příklady): Pro funkci F(x,y) a bod [a, b] G E2 takový, že F(a, b) = 0, umíme najít funkci y = f (x) splňující F(x, f (x)) = 0, pokud je Fy(a, b) 7^ 0. V takovém případě umíme i vypočíst f'{x) = —Fx/Fy. Z následující věty plyne, že takto to platí vždy, navíc rozšířené i na libovolné počty proměnných. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooo«ooo ooooooo ooooooooooooc Necht F : E„+i —> R je spojitě diferencovatelná funkce na otevřeném okolí bodu [x*,y*] G En x R, ve kterém je F(x*,y*) = 0 a §^(x*,y*) ^ 0. Potom existuje spojitá funkce f : En —> R definovaná na nějakém okolí U bodu x* e En taková, že F(x, f{x)) = 0 pro všechny x G U. Navíc má funkce f v okolí bodu x* parciální derivace splňující df_ dxj 8F_ dx; f(x)) dF_ dy Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooo«ooo ooooooo ooooooooooooc Necht F : E„+i —> R je spojitě diferencovatelná funkce na otevřeném okolí bodu [x*,y*] G En x R, ve kterém je F(**,y*) = 0 a §^(x*,y*) ^ 0. Potom existuje spojitá funkce f : En —> R definovaná na nějakém okolí U bodu x* e En taková, že F(x, f{x)) = 0 pro všechny x G U. Navíc má funkce f v okolí bodu x* parciální derivace splňující Poslední tvrzení o derivaci přitom je dobře zapamatovalné (i pochopitelné) z výrazu pro diferenciál: df_ dxj 8F_ dx; '(*)) 7(x, f(x)) dF_ dy 0 = dF Fx dx + Fy dy = (Fx + Fy f'(x)) dx. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy oooooooooooooo»oo ooooooo ooooooooooooc Příklad Určete lokální extrémy funkce z = f(x,y), která je určena implicitně rovnicí F(x, y, z) = x2 + y2 + z2 — xz — V2yz — 1 = 0. Řešení Derivováním rovnosti podle x a y dostáváme: 2x + 2z • zx — z — x • zx - V2yzx = 0 2y + 2z • zy — x ■ zy - - V2z — \flyzy - = o, odkud vyjádříme z-2x V2z- 2y 2z — x — \/2y' 2z — x — V2y □ s - ■ i Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooo«o ooooooo ooooooooooooc Řešení (pokr.) Stacionární body musí splňovat: zx = 0, zy = 0, tj. z = 2x = yf2y, a tedy y = V2x. Dosazením do původní rovnice dostáváme stacionární body [1, \/2, 2] a [—1, —y/2, —2]. V těchto bodech je Fz ^0 (je to zároveň jmenovatel všech zde vystupujících zlomků), proto je v jejich okolí implicitně určena jistá funkce z = f(x, y). Dalším derivováním implicitní rovnice vypočteme parciální derivace f 2. řádu: ___2___2 Zxx — ~ô ' Zxy ~ ' Zyy ~ ~~ň 7^~' 2z — x — v 2y 2z — x — v 2y □ s - ■ ■O O. o- Tečny a nor ooooooo ály k implicitně zadaným plochá Řešení (pokr.) Stacionární body musí splňovat: zx = 0, zy = 0, tj. z = 2x = \/2y, a tedy y = \/2x. Dosazením do původní rovnice dostáváme stacionární body [1, \/2, 2] a [—1, —\/2, —2]. V těchto bodech je Fz ^0 (je to zároveň jmenovatel všech zde vystupujících zlomků), proto je v jejich okolí implicitně určena jistá funkce z = f(x, y). Dalším derivováním implicitní rovnice vypočteme parciální derivace f 2. řádu: ___2___2 Zxx — ~ô ' Zxy ~ ' Zyy ~ ~~ň 7^~' Zz — x — v 2y Zz — x — \J zy Ve stacionárních bodech je Hf negativně, resp. pozitivně definitní, proto zde nastávají lokální maximum, resp. minimum funkce f. Zobrazení mezi euklidovskými prostory 0000000000000000« Tečny a nor ooooooo ály k implicitně Vázané extrémy ooooooooooooc Nejobecnější případ, kdy definujeme implicitně zadané zobrazení, popisuje následující věta (v případě n=l kopíruje větu o implicitní funkci). Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy 0OOOOOOOOOOOOOOO« ooooooo ooooooooooooc Nejobecnější případ, kdy definujeme implicitně zadané zobrazení, popisuje následující věta (v případě n=l kopíruje větu o implicitní funkci). Věta (O implicitním zobrazení) Nechi F : Em+n —>• En je spojitě diferencovatelné zobrazení na otevřeném okolí bodu [x*,y*] G Em x En = Em+n, v němž platí F(x*,y*) = O a det D*F ^ 0. Potom existuje spojitě diferencovatelné zobrazení G : Em —> En definované na nějakém okolí U bodu x* G Em s obrazem G{U), který obsahuje bod y*, a takové, že F(x, G(x)) = O pro všechny x G U. Navíc je Jacobiho matice D1G zobrazení G na okolí bodu x* zadána součinem matic D1G(x) = -{DlF)~\x, G(x)) ■ DlF{x, G(x)). Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooooc Plán přednášky Q Literatura Q Zobrazení mezi euklidovskými prostory a Zobrazení a transformace a " Chain Rule" • Věta o inverzním zobrazení • Implicitně zadaná zobrazení Q Tečny a normály k implicitně zadaným plochám • Gradient funkce • Tečné a normálové prostory Q Vázané extrémy » Metoda Lagrangeových multiplikátorů • Speciální optimalizační metody Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy OOOOOOOOOOOOOOOOO «000000 ooooooooooooc Gradient funkce Definice Pro spojitě diferencovatelnou funkci f(x\,... ,xn) : En —>• R se vektor df df dx\' ' dxn df nazývá gradient funkce f. V technické a fyzikální literatuře se často zapisuje také jako grad f. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo «000000 ooooooooooooc Gradient funkce Definice Pro spojitě diferencovatelnou funkci f(x\,... ,xn) : En vektor af se dx\' ' dxn / nazývá gradient funkce f. V technické a fyzikální literatuře se často zapisuje také jako grad f. Rovnost f(xi,... ,xn) = b s pevnou hodnotou b G R zadává podmnožinu M C En, která mívá vlastnosti (n — l)-rozměrné nad plochy. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy OOOOOOOOOOOOOOOOO «000000 ooooooooooooc Pro spojitě diferencovatelnou funkci f{x\,... ,xn) : En —> R se vektor V technické a fyzikální literatuře se často zapisuje také jako grad f. Rovnost f(xi,... ,xn) = b s pevnou hodnotou b G R zadává podmnožinu M C En, která mívá vlastnosti (n — l)-rozměrné nadplochy. Přesněji: pokud je vektor parciálních derivací nenulový, můžeme lokálně množinu M popsat jako graf spojitě diferencovatelné funkce v n — 1 proměnných. nazývá gradient funkce f. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo «000000 ooooooooooooc Pro spojitě diferencovatelnou funkci f{x\,... ,xn) : En —> R se vektor V technické a fyzikální literatuře se často zapisuje také jako grad f. Rovnost f(xi,... ,xn) = b s pevnou hodnotou b G R zadává podmnožinu M C En, která mívá vlastnosti (n — l)-rozměrné nadplochy. Přesněji: pokud je vektor parciálních derivací nenulový, můžeme lokálně množinu M popsat jako graf spojitě diferencovatelné funkce v n — 1 proměnných. Hovoříme v této souvislosti také o úrovňových množinách Mt, (analogie vrstevnic v př. n = 2). nazývá gradient funkce f. □ s - ■ Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy OOOOOOOOOOOOOOOOO O0OOOOO ooooooooooooc Na derivacích křivek ležících v úrovňové množině Mt, se bude diferenciál df vždy vyčíslovat nulově: f(c(ř)) = b pro všechna ř, proto ^-f(c(r)) = df(c'(r)) = 0. Zobrazení mezi euklidovskými prostory ooooooooooooooooo Tečny a nor O0OOOOO ály k implicitně zadaným plochá Na derivacích křivek ležících v úrovňové množině Mt, se bude diferenciál df vždy vyčíslovat nulově: f(c(ř)) = b pro všechna ř, proto d dt f(c(r)) = df(c'(r)) = 0. Pro obecný vektor v = (v\,..., vn) e En je velikost příslušné směrové derivace funkce f: \dvf\ df df (df, v)=cos En a n rovnic r}(xi,..., xm+n) = bi, i = 1,..., n. Dle věty o implicitní funkci je „většinou" množina všech řešení (xi,... ,xm+n) grafem zobrazení G : Em —>• En. Pro pevnou volbu b = {b\,..., bn) je samozřejmě množinou M všech řešení průnik nadploch M(b,, fj) příslušejících jednotlivým rovnicím f; = b\. Totéž platí pro tečné směry a normálové směry: Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo oooo«oo ooooooooooooc Obecné dimenze: funkce F = (r~i, ...,fn): Em+n —> En a n rovnic f/(xi,..., xm+n) = bi, i = 1,..., n. Dle věty o implicitní funkci je „většinou" množina všech řešení (xi,... ,xm+n) grafem zobrazení G : Em —>• En. Pro pevnou volbu b = {b\,..., bn) je samozřejmě množinou M všech řešení průnik nadploch M(b,, f,) příslušejících jednotlivým rovnicím f; = b\. Totéž platí pro tečné směry a normálové směry: Afinní podprostor v Em+n obsahující právě všechny tečny k M bodem P dán rovnicemi: 0 = 7^(p) • (*i - ai) + • • • + ^(P) • (xm+n - am+n) •n ai) + --- + dx, dfr n •n (P)■(*m+ n Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooo«o ooooooooooooc Tento pod prostor se nazývá tečný prostor k (implicitně zadané) ploše M v bodě P. Normálový prostor v bodě P je afinní podprostor generovaný bodem P a gradienty všech funkcí f\,..., fn v bodě P, tj. řádky Jacobiho matice D1F. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooo«o ooooooooooooc Tento pod prostor se nazývá tečný prostor k (implicitně zadané) ploše M v bodě P. Normálový prostor v bodě P je afinní podprostor generovaný bodem P a gradienty všech funkcí f\,..., fn v bodě P, tj. řádky Jacobiho matice D1F. Příklad Spočtěme tečnu a normálový prostor ke kuželosečce v E3. Uvažujme rovnici 0 = f (x, y, z) = z - xjx2 + y2 kuželu s vrcholem v počátku a rovinu zadanou Q = g(x,y,z)=z-2x + y + l. Bod P = (1,0,1) patří jak kuželu, tak rovině a průnik M těchto dvou ploch je křivka. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo 000000« ooooooooooooc Příklad (pokr.) Její tečnou v bodě P bude přímka zadaná rovnicemi □ s Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo 000000« ooooooooooooc Příklad (pokr.) Její tečnou v bodě P bude přímka zadaná rovnicemi 0 =--. 1 2x 2^x2 + y2 ■{x-l)--T±==2y *=i,y=o 2Vx2+y2 ■y x=l,y=0 + l-(z-l) = -x + z 0 = -2(x - 1) + y + (z - 1) = -2x + y + z + 1 □ s Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo 000000« ooooooooooooc Příklad (pokr.) Její tečnou v bodě P bude přímka zadaná rovnicemi O :2x (x-1) x=l,y=0 2V*2+y: :2y x=l,y=0 2Vx2 + y2 + l-(z-l) = -x + z O = -2(x - 1) + y + (z - 1) = -2x + y + z + 1 zatímco rovina kolmá k naší křivce bodem P bude parametricky dána výrazem (1,0,1)+t(-1,0,1) + <7(-2,1,1) s parametry r a a. ■y Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooooc Plán přednášky Q Literatura Q Zobrazení mezi euklidovskými prostory a Zobrazení a transformace a " Chain Rule" • Věta o inverzním zobrazení • Implicitně zadaná zobrazení Q Tečny a normály k implicitně zadaným plochám • Tečné a normálové prostory Q Vázané extrémy • Metoda Lagrangeových multiplikátorů • Speciální optimalizační metody Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooooc 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 Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooooc 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. Příklad Určete lokální extrémy funkce f(x,y) = x2y na množině M dané implicitně rovnicí 5x2 + 2y2 = 14. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo •oooooooooooc Metoda Lagrangeových multiplikátorů V předchozím příkladu jsme viděli, že normálový vektor (tj. gradient) funkce, 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 Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo •oooooooooooc Metoda Lagrangeových multiplikátorů V předchozím příkladu jsme viděli, že normálový vektor (tj. gradient) funkce, 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 Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo •oooooooooooc Metoda Lagrangeových multiplikátorů V předchozím příkladu jsme viděli, že normálový vektor (tj. gradient) funkce, 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 G 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) = d/7(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 Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo o»ooooooooooc 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 Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo o»ooooooooooc 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(xi,... ,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 = (ř"i,..., 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 D1F 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 Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo oo«oooooooooc 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 Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooo»ooooooooc Absolutní extrémy 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 Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooo»ooooooooc Absolutní extrémy 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 ŕ(x,y) = 2x + y za podmínky ^- +y2 < 1. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo oooo«oooooooc Ř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 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. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo oooo«oooooooc Ř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 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 Z_(x, y, A) = 2x + y - A(^- + y2 - 1). Pak dostáváme: 0 = Lx = 2- 0 = Ly = 1 - 2Ay 0 = X2 A + y2 - 1. O0.O- Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo oooo«oooooooc Ř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 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 Z_(x, y, A) = 2x + y - A(4- + y2 - 1). Pak dostáváme: 0 0 0 = 2 -= 1 - + y2 2Ay - 1. Odtud snadno x (resp. A = h y 2A' 17 17' a tedy A y = — pro minimum). y 17 Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy OOOOOOOOOOOOOOOOO OOOOOOO OOOOO0OOOOOOC 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 Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo oooooo«oooooc 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. Iterace: xn+i = xn + 7n grad r"(x„), pro dostatečně malé 7„, aby f(xn+i) > f(x„). Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo oooooo«oooooc 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. 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. Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy OOOOOOOOOOOOOOOOO OOOOOOO OOOOOOO0OOOOC 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 Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy OOOOOOOOOOOOOOOOO OOOOOOO OOOOOOO0OOOOC 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 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 Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo oooooooo«oooc 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 Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo oooooooo«oooc 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- (Wr"(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á a metoda sdružených gradientů pro řešení příslušné soustavy, • různých tzv. /cvaz/-newtonovských metod, využívajících pouze přibližného Hessiánu (např. BFGS). Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy OOOOOOOOOOOOOOOOO OOOOOOO OOOOOOOOO0OOC 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 Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy OOOOOOOOOOOOOOOOO OOOOOOO OOOOOOOOO0OOC 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-x < bk ak+i ■ x = bk+i at-x = bt Zobrazení mezi euklidovskými prostory ooooooooooooooooo Tečny a nor ooooooo Lineární programování Lze ukázat, že každou (rozumnou) úlohu lineárního programování lze převést na tzv. standardní úlohu tvaru za podmínek maximalizovat f (x) = c • x a\ ■ x < b\ ak-x< bk, kde xi > 0,... ,x„ > 0. Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooo»c Simplexová metoda Standardní úlohu řeší klasická Simplexová metoda (George Dantzig, 1947). Literatura Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooo»c 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 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 Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy ooooooooooooooooo ooooooo ooooooooooo»c 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 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 Zobrazení mezi euklidovskými prostory Tečny a normály k implicitně zadaným plochám Vázané extrémy OOOOOOOOOOOOOOOOO OOOOOOO OOOOOOOOOOOOÍ 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.