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~~