U příkladů dávám vždy FIXME **zkontrolovat** aby ho zkontroloval alespoň ještě jeden další člověk. Prosím prvního člověka, kterému příklad vyjde stejně aby toto SMAZAL ať je vždy kontrola! Dííkes ====== Ze script ====== Kdo co máte ze sript, zkuste se poďelit aspoň vám to ostatní opraví. ===== Kapitola 1 Úvod ===== ==== 1.4 Cviceni (str. 9)==== === 1.1 Najdete (uvahou) co nejjednoduzsi popis nasl. mnozin === == Zadani a) == \{ x^2 | x \in \mathbb{R} \} == Reseni == \langle 0, \infty ) == Zadani b) == \{ 1/x | x \ge 1 \} == Reseni == ( 0, 1 \rangle == Zadani c) == \{ e^{-x^2} | x \in \mathbb{R} \} == Reseni == ( 0, 1 \rangle == Zadani d) == \{ x + y | x^2 + y^2 < 1 \} == Reseni == ( - \sqrt{2}, \sqrt{2} ) == Zadani e) == \{ x + y | x^2 + y^2 = 1 \} == Reseni == \langle - \sqrt{2}, \sqrt{2} \rangle == Zadani f) == \{ |x| + |y| | x^2 + y^2 = 1 \} == Reseni == \langle 1, \sqrt{2}\rangle == Zadani g) == \{ x_1 + \dots + x_n | x \in \mathbb{R}^n, \|\mathbf{x}\| = 1 \} == Reseni == \langle - \sqrt{n}, \sqrt{n}\rangle == Zadani h) == \{ | x - y | \ | x \in \langle 0, 1 \rangle, y \in ( 1, 2 \rangle \} == Reseni == ( 0, 2 \rangle === 1.2 Mejme nozinu bodu v rovine === X = \langle -1, 1 \rangle \times \{ 0 \} = \{ ( x, 0 ) \ | \ -1 \leq x \leq 1 \} \subseteq \mathbb{R}^2 Nacrtnete nasledujici mnoziny == Zadani a) == \{ y \in \mathbb{R}^2 \ | \ min_{x \in X} \| x - y \| \leq 1 \} == Reseni == Je to usecka od (-1,0) do (1,0) == Zadani b) == \{ y \in \mathbb{R}^2 \ | \ max_{x \in X} \| x - y \| \leq 2 \} == Reseni == Tohle je utvar ze dvou usecek (-1,2) az (1,2) a (-1,-2) az (1,-2) a dvou polokruznic, ktere je spojuji. ===== Kapitola 2 Vektory a Matice ===== ===== Kapitola 3 Skalární součin a ortogonalita ===== ===== Kapitola 4 Metoda nejmenších čtverců ===== ===== Kapitola 5 Vlastní čísla a kvadratické formy ===== ===== Kapitola 6 Množiny a zobrazení v euklidovských prostorech ===== ===== Kapitola 7 Derivace ===== ===== Kapitola 8 Analytické podmínky na lokální extrémy ===== ===== Kapitola 9 Numerické algoritmy na hledání volných lokálních extrémů ===== ===== Kapitola 10 Konvexní množiny ===== ===== Kapitola 11 Lineární programování ===== ===== Kapitola 12 Simplexová metoda ===== ===== Kapitola 13 Dualita v lineárním programování ===== ====== Ze zkoušek ====== ===== Zkouška 23.1.2012 ===== Minimální bodová hranice na Ečko byla snížena z 25 na 20/50. Úlohu 5 nikdo nedal, tak se do hodnocení nepočítala. Histogram úspěšnosti: #A=2 #B=4 #C=11 #D=19 #E=32 #F=41 ==== 1) Řeka ==== === Zadání === Stojíte na břehu řeky široké 1km. Chcete se dostat ke stanu, který je na protějším břehu 1km po proudu. Chůzí po břehu se pohybujete 3km/h, plavete 2km/h. Proud řeky zanedbáme. Je to absolutní volej. Za jaký nejkratší čas se dostanete ke stanu? === Řešení === Po kraji řeky ujdeme nějakou vzdálenost, pak vlezeme do řeky a budeme plavat šikmo, přímo ke stanu. Úsek který jdeme pěšky podél řeky si označíme 1 - x zbytek vzdálenosti podél řeky bude tedy x. Podle pythagorovy věty budeme plavat vzdálenost \sqrt{x^2 + 1}. FIXME **Přidat obrázek** Sestavíme si rovnici pro čas: T = \frac{1-x}{3} + \frac{\sqrt{x^2 + 1}}{2} Hledáme minimum této funkce, proto jí zderivujeme a prfní derivaci položíme rovnou nule: T' = -\frac{1}{3} + \frac{2x}{4\sqrt{x^2 + 1}} -\frac{1}{3} + \frac{x}{2\sqrt{x^2 + 1}} = 0 \frac{x}{\sqrt{x^2 + 1}} = \frac{2}{3} 3x - 2\sqrt{x^2 + 1}} = 0 3x - 2(x^2 + 1)^\frac{1}{2} = 0 3x = 2(x^2 + 1)^\frac{1}{2} \log(3x) = \log(2) + \frac{1}{2}\log(x^2 + 1) 2\log(3x) = 2\log(2) + \log(x^2 + 1) \log(9x^2) = \log(4) + \log(x^2 + 1) Odlogaritmujeme: 9x^2 = 4(x^2 + 1) 9x^2 = 4x^2 + 4 x = \sqrt{\frac{4}{5}} T = \frac{\sqrt{\frac{4}{5}}-1}{3} + \frac{\sqrt{\frac{4}{5} + 1}}{2} Na kalkulačce: T = 0.6356295 ==== 2) Vážené nejmenší čtverce ==== === Zadání === Hldedejte minimum x metodou vážených nejmenších čtverců: f(x) = \sum_{i=1}^{m} w_i ( \sum_{j=1}^{n} a_{ij}x_j - b_i )^2 - Napište funkci v maticové formě f(x) = ??? - Najděte řešení v maticové podobě x = ??? === Řešení === Matice \mathbf{W} je ctvercova matice, ktera ma na diagonale prvky w_i, jinak vsude nuly. f(x) = (\mathbf{A} \mathbf{x} - \mathbf{b})^T \mathbf{W}^T (\mathbf{A} \mathbf{x} - \mathbf{b}) FIXME **zkontrolovat** Tady nevim. Ja to zderivoval, polozil rovno nule a vyjadril z toho vektor \mathbf{x}. **DERIVACE JE BUĎ** f'(x) = (\mathbf{A} \mathbf{x} - \mathbf{b})^T (\mathbf{W} + \mathbf{W}^T) FIXME **NEBO** zda se mi, ze derivujeme slozenou funkci, a ze tedy v predchozi verzi chybi "derivace vnitrni funkce" (Ax-b), coz by melo byt Acko) tedy derivace by mela vypadat takto: f'(x) = \mathbf{A}(\mathbf{A} \mathbf{x} - \mathbf{b})^T (\mathbf{W} + \mathbf{W}^T) Covynato? Dal pocitam s prvni variantou derivace. Matice \mathbf{W} je diagonalni, proto: f'(x) = (\mathbf{A} \mathbf{x} - \mathbf{b})^T 2 \mathbf{W} Roztransponujeme a roznasobime: f'(x) = \mathbf{x}^T \mathbf{A}^T 2 \mathbf{W} - \mathbf{b}^T 2 \mathbf{W} Polozime rovno nule: \mathbf{x}^T \mathbf{A}^T 2 \mathbf{W} - \mathbf{b}^T 2 \mathbf{W} = 0 2 \mathbf{x}^T \mathbf{A}^T \mathbf{W} = 2 \mathbf{b}^T \mathbf{W} \mathbf{x}^T = \mathbf{b}^T \mathbf{W} ( \mathbf{A}^T \mathbf{W} )^{-1} FIXME **zkontrolovat reseni** Řešil jsem to pro druhou a podle mě správnější variantu derivace f'(x) = (\mathbf{A} \mathbf{x} - \mathbf{b})^T (\mathbf{W} + \mathbf{W}^T)\mathbf{A} upravím protože \mathbf{W} = \mathbf{W}^T Položím derivaci rovno nule: (\mathbf{A} \mathbf{x} - \mathbf{b})^T 2\mathbf{W}\mathbf{A} = 0 (\mathbf{A} \mathbf{x})^T\mathbf{W}\mathbf{A} - \mathbf{b}^T\mathbf{W}\mathbf{A} = 0 \mathbf{x}^T\mathbf{A}^T\mathbf{W}\mathbf{A} = \mathbf{b}^T\mathbf{W}\mathbf{A} \mathbf{x}^T = \mathbf{b}^T\mathbf{W}\mathbf{A}(\mathbf{A}^T\mathbf{W}\mathbf{A})^{-1} \mathbf{x}^T = \mathbf{b}^T\mathbf{W}\mathbf{A}\mathbf{A}^{-1}\mathbf{W}^{-1}\mathbf{A}^{-T} \mathbf{x} = \mathbf{A}^{-1}\mathbf{b} což je stejné jako vyšlo v předchozím případě.. Souhlas s druhym resenim, vyjde to tak, i kdyz si f(x) nejdrive roznasobim a az pak derivuji {{:courses:a4b33opt:2_souhlas_roznasobeni_001.jpg?direct&100|}} ==== 3) Nejkratší spojnice mimoběžek ==== === Zadání === Máme dvě mimoběžky v prostoru, každá dána dvěma body p_i,q_i \in \mathbb{R}^n, i = \{1,2\}. Hledejte příčku, tj. nejkratší spojnici mezi mimoběžkami metodou nejmenších čtverců. min \| \mathbf{Ax-b} \|_2 === Řešení === Kdybych si to byl byval namaloval, mohl to byt celkem v pohode priklad =( Nasleduji myslenkove pochody a az nakonec vysledna forma. Abychom mohli "pochodovat" po prvni primce nadefinujeme si totok: (\mathbf{p}_1 - \mathbf{q}_1) a + \mathbf{q}_1 Kde \mathbf{p}_1 - \mathbf{q}_1 je smerovy vektor prvni primky a a je promenna, kterou tento vektor natahujeme. Analogicky pro druhou primku: (\mathbf{p}_2 - \mathbf{q}_2) b + \mathbf{q}_2 Tim jsme si nadefinovali po jednom bodu na kazde primce. Rozdil techto bodu je vektor, jehoz velikost chceme ze zadani minimalizovat. Body tedy od sebe odecteme: ( (\mathbf{p}_1 - \mathbf{q}_1) a + \mathbf{q}_1 ) - ((\mathbf{p}_2 - \mathbf{q}_2) b + \mathbf{q}_2 ) A zbavime se nehezkych minusu: (\mathbf{p}_1 - \mathbf{q}_1) a + (\mathbf{q}_2 - \mathbf{p}_2 ) b + \mathbf{q}_1 - \mathbf{q}_2 Nyni se to pokusime dostat do tvaru \mathbf{Ax-b} (\mathbf{p}_1 - \mathbf{q}_1) a + (\mathbf{q}_2 - \mathbf{p}_2 ) b - ( \mathbf{q}_2 - \mathbf{q}_1 ) Odtud uz by to melo byt videt. \mathbf{x} = \left( \begin{array}{c} a \\ b \end{array} \right), \mathbf{x} \in \mathbb{R}^2 \mathbf{A} = \left( \begin{array}{cc} (\mathbf{p}_1 - \mathbf{q}_1) & (\mathbf{q}_2 - \mathbf{p}_2 ) \end{array} \right), \mathbf{A} \in \mathbb{R}^{n\times2} \mathbf{B} = \left( \mathbf{q}_2 - \mathbf{q}_1 \right), \mathbf{b} \in \mathbb{R}^n Vypočítané koeficienty a a b se pak dosadí zpět do rovnic pro jednotlivé přímky (první dvě rovnice) abychom dostali body příčky, kterou hledáme. FIXME **zkontrolovat spravnost** ==== 4) GPS, nejmenší čtverce ==== === Zadání === Máme souřadnice m satelitů \mathbf{a}_1, \dots, \mathbf{a}_m \in \mathbb{R}^n. V reálném světě by n = 3, my počítáme obecné n \in \mathbb{R}. Naše souřadnice je \mathbf{x} \in \mathbb{R}. Známe vzdálenosti od jednotlivých satelitů y_i = \| \mathbf{a}_i - \mathbf{x} \|_2. Minimalizujeme: f(x) = \sum_{i=1}^{m} ( \| \mathbf{a}_i - \mathbf{x} \|_2 - y_i )^2 - Napište matlabskou funkci ''x = gps(A,y,x0)'' která řeší úlohu čistou Gauss-Newtonovou metodou, kde \mathbf{A} \in \mathbb{R}^{n\times m}, y \in \mathbb{R}^{m} a kde x0 je počáteční odhad. - Je funkce f konvexní? Napište důkaz z definice. - Kde není funkce f diferencovatelná? - Bude nediferencovatelnost dělat problém v reálu? === Řešení === Navrh alespon na prvni cast - kod v matlabu (mozna nejaka indexace nemusi sedet - snad jsem to ale nepopletl) {{:courses:a4b33opt:4_cast_v_matlabu_001.jpg?direct&100|}} ==== 5) Brambůrky, lupínky s pomocníkem ==== :!::!: Příklad nikdo nedal. nebyl započítán do bodování. :!::!: === Zadání === Děláme brambůrky a lupínky. Na kilo brambůrků spotřebujem 2kg brambor a 0.4 litry oleje. Na kilo lupínků spotřebujem 1.5kg brambor a 0.2 litrů oleje. Brambůrky prodáváme za 120,- za kilo, lupínky za 76,- za kilo. Máme pomocníka. Pomocník si nechá zaplatit 10,- za vyrobený kilogram zboží. Nad 30 kilogramů si ale nechává platit 20,- za kilogram. Nad 40 kilogramů čehokoli vyrobeného za den dáme pomocníkovi 40,- za kilo. (Funkce kolik peněz pomocník dostane, závislá na množství vyrobeného zboží je taková dvakrát nahoru zlomená čára. ) Předpokládáme, že na začátku dne máme nakoupeno 100kg brambor a 10litrů oleje. Co se nespotřebuje to se vyhodí. (Cenu surovin jsem si nezapisoval, páč je nám k ničemu). - vyrobte LP - simplex tabulka - jeden krok simplex metody === Řešení === Kdyby nebyla pomocníkova cena dvakrát zlomená, vypadala by LP snad takhle: max 120 l + 76 h - 10 (l+h) z.p. 2 l + 1.5 h <= 100 0.4 l + 0.2 h <= 10 FIXME **zkontrolovat** Myslim, ze se to da resit takto: (vcetne te "lomene" fce, kterou je trik radsi nelamat) {{:courses:a4b33opt:5_brambory_lp_001.jpg?direct&100|}} max 120 b + 76 b - 10 c1 - 20 c2 - 40 c3 a k tomu podminka c1 + c2 + c3 = b + l (a tez zbyvajici) ==== 6) Maxima, minima, nic-ima ==== === Zadání === Máme funkci f(x,y) = x^2y + y^2 + x na množině \{ (x,y) \in \mathbb{R}^2 | -1 \le x - y \le 1 \} . Určete lokální extrémy a zda jsou maxima, nebo mimnima. === Řešení === Parciální derivace položíme rovny nule: f_x(x,y) = 2xy + 1 = 0 f_y(x,y) = x^2 + 2y = 0 Z první rovnice: y = -\frac{1}{2x} Dosadíme do druhé: x^2 -\frac{1}{x} = 0 Odtud: x^3 - 1 = 0 A tedy: x = 1 y = -\frac{1}{2} Toto je sice stacionární bod zadané funkce, ale ani nemusíme řešit, jestli je to extrém. Ono totiž x - y = 1.5 a tím nám to vypadne z množiny, pro kterou máme příklad řešit. FIXME **zkontrolovat** FIXME **dodělat** Teď mi ale došlo, že musíme teda najít, kterým směrem ta fce soupá a padá a hranice toho "definičního oboru" označit za extrémy. **lagrange nerovnosti "hrubou silou"** zkusit to vyřešit pomocí Langrangeových multiplikátorů vyzkoušením všech možností (4) nějaké rozumné extrémy mi vyšly jen při aktivaci omezení x-y=1, při x-y=-1 vyjdou komplexní kořeny nerovnice a při aktivaci obou nemá soustava řešení mám tedy 2 řešení (x,y)=(\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}}-1),(x,y)=(-\frac{1}{\sqrt{3}},-\frac{1}{\sqrt{3}}-1) vypočítám si Hessian \begin{pmatrix}2y & 2x \\ 2x & 2\end{pmatrix} dosadím a pro první bod mi vyjde indefinitní a stejně tak pro druhou, oba tedy budou nejspíše sedla.. ==== 7) Linprog, duál, podm.kompl. ==== === Zadání === Máme zadaný vektor a číslo \mathbf{c} \in \mathbb{R}^n, k \in \mathbb{N}, k \le n, a řešíme max \ \mathbf{c}^T\mathbf{x}, z.p. \ \mathbf{1}^Tx \le k, \mathbf{0} \le \mathbf{x} \le \mathbf{1}, \mathbf{x} \in \mathbb{R}^n - řešte úvahou - napište duál - napište podmínky komplementarity === Řešení === Úvaha: Stačí si představit co dělají podmínky. Součet všech čísel v x je menší nebo rovno k, a my maximalizujeme, tedy bude rovno k. Navíc jednotlivá čísla v x jsou od nuly do jedné. Vezmeme tedy k jedniček a narveme je do x na stejné souřadnice, jako je ve vektoru c, k-největších čísel. \\edit Tady je podle mě zrada, je třeba vzít v úvahu, že c^T může být třeba celé záporné a tedy výsledek bude \max\lbrace 0, k-\text{největších čísel}\rbrace Doporučuju se podívat na str. 94 do skript. Rovnice úplně dole vyjadřují téměř přesně tuhle úlohu. \mathbf{A} = \left( \begin{matrix} 1 & 1 & \dots & 1 & 1 \\ 1 & 0 & \dots & 0 & 0 \\ 0 & 1 & \dots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & 0 \\ 0 & 0 & \dots & 0 & 1 \\ \end{matrix} \right), A \in \mathbb{R}^{(n+1) \times n}, \ \mathbf{b} = \left( \begin{matrix} k \\ 1 \\ \vdots \\ 1 \end{matrix} \right), \mathbf{b} \in \mathbb{R}^{(n+1)} Primár pak vypadá takto: max \ \mathbf{c}^T \mathbf{x} z.p. \ \mathbf{Ax} \le \mathbf{b}, \ \mathbf{x} \ge \mathbf{0} A od něj duál: min \ \mathbf{y}^T \mathbf{b} z.p. \ \mathbf{y} \ge \mathbf{0}, \ \mathbf{y}^T{A} \ge \mathbf{c}^T \\edit tohle je podle mě špatně a zneménka mají být opačně... z.p. \ \mathbf{y} \le \mathbf{0}, \ \mathbf{y}^T{A} \le \mathbf{c}^T Podmínky komplementarity pak stačí opsat ze skript z 13.2 ===== Zkouška 6.2.2012 ===== ==== 1) Středoškolská úloha - žebřík ==== === Zadání === Zeď od které se svažuje zem pod úhlem alfa (zadaným ve formě směrnice k = tg(alfa)). Kam máme postavit žebřík (vodorovná vzdálenost x) délky 1 (jedna) tak, aby dosáhl co nejvýš? | |\ / | \ / | \ / | \ / | \ / | \/ | / | / | / ) | / ) | / alfa) +----------- |--x--| === Řrešení === Rozdělíme si výšku do které dosáhne žebřík na dvě části tak, že vedeme rovnoběřku s osou x patou žebříku. Tím nám vzniknou dva trojúhelníky. Horní trojúhelník má šikmou stranu žebřík, spodní stranu o délce x a vlevo je svislá strana, tedy část maximalizované výšky. Z tohoto trojúhelníka vyjádříme výšku podle pythagorovy věty jako h_1 = \sqrt{1-x^2} Spodní trojúhelník má šikmou stěnu na "svahu" vodorovná je opět rovna x a svislá je druhá část výšky. druhou část dopočítáme podle tan(alfa) tan(\alpha) = k = \frac{h_2}{x}, tedy \ h_2 = kx h = \sqrt{1-x^2} + kx Toto se zderivuje polozi rovno nule a vyjadri se z toho x. ==== 2) Extremy ==== === Zadani === Najte extremy a reknete co to je f(x,y) = \frac{1}{2} x^2 + \frac{1}{3} y^3 - xy === Reseni === Parcialni derivace (jakobian) polozime rovno nule ... vyjdou body (0,0) a (1,1) Druha derivace (hessian) vyjde jako ( 1 -1 ; -1 2y ) a po dosazeni vyjde pro (0,0) indefinitni a (1,1) pozitivne definitni, tedy (1,1) je lok. minimum a (0,0) sedlo. ==== 3) Simplex ==== === Zadani === Na lisu na plasty vyrabime bud hadicky nebo trubicky. hadicky = 25 kc/kg trubicky = 30 kc/kg vyrobime 200 kg/h hadicek maximalne ale 6000kg vyrobime 140 kg/h trubicek maximalne ale 4000kg mame maximalne 40 hodin provozu lisu Vse ostatni taknejak ignorujem =)) === Reseni === Pomerne hezke reseni (diky Petru Nobstovi) bylo prevest si vsechno na hodiny a koruny. LPcko pak vypada takhle: max 5000*t1 + 4200*t2 z.p. t1 + u1 = 30 t2 + u2 = 28,57 <<<--- 4000 / 140 t1 + t2 + u3 = 40 Tak jak to je se to namlati do simplexove tabulky, (bacha je to maximum, tak nejlip prevest na minimum). Nakonec vyjde, ze vyrabime hadicek 30hod * 200kg/h = 6000 kg trubicek 10hod * 140kg/h = 1400 kg ==== 4) lagaranze ==== === Zadani === minimalizute a^Tx za podminky xTCx = 1 , C je symetricka pozitivne definitni matice. min \{ \mathbf{a}^T\mathbf{x} \ | \ \mathbf{x}^T\mathbf{C}\mathbf{x} = 1 \} b) jak se zmeni kdyz misto \mathbf{x}^T\mathbf{C}\mathbf{x} = 1 bude \mathbf{x}^T\mathbf{C}\mathbf{x} \leq 1 c) graficka reprezentace pro n = 2 ~~DISCUSSION~~