Známka u zkoušky:
body 100-90 89-80 79-70 69-60 59-50 49-0
známka A B C D E F
Písemka trvala 2 hodiny. Byla jen jedna skupina. Opisovat nešlo. Werner nabízel dokonce i půlhodinu navíc pokud by byla potřeba. Psalo se do 11 hodin, opraveno bylo před 15. hodinou. Příklady, které nikdo nedal, se prý nezapočítávaly. Minimální počet bodů byl 17, maximálně i něco přes 60.
1) Převody na LP, pokud to jde. Hodně absolutních hodnot. Některé převést nešly.
2) Simplexovka. Sestavit tabulku. Zda je bázové řešení přípustné a zdůvodnit. Pak udělat jeden krok simplexní metody.
3) min || Ax - b ||_1 …. udělat z toho LP, sestavit duální úlohu, napsat pravidlo komplementarity pro tento případ - nikdo prý nedal
4) Vypočítat vlastní čísla matice 2×2 a určit, co platí: kladně / záporně definitní, kladně / záporně semidef., indefinitní
5) Sestavit lagrange z x - 2y, za podmínky (2x)^2 + y^2 = 1. Určit kritické body. Řešení na wolfram-alpha
6) Poznat, zda jsou matice symetrické, antisymetrické, ortonormální nebo ortogonální (i více možností samozřejmě). 4 matice 2×2.
7) Zjistit kritické body funkce 3x^4 + … nějaké y na něco a další x atd. Pak zjistit, které z nich jsou lok. min, max. nebo sedlo.
8) Zadaná funkce f(x,y,z), x = u.cos v, y = u . sin v, z = v (nějak tak). Určit parciální derivaci funkce f podle u a podle v.
9) Sestavit hessián pro funkci: f(x,y) = ln(e^x + e^y) (hessián je matice druhých derivací).
10) Důkaz, že poloprostor je konvexní množina z definice. Popsat slovy postup důkazu.
11) Zadané nějaké funkce na množinách (většinou R^2). Napsat, jestli jsou konvexní, konkávní, obojí nebo nic.
12) První iterace newtonovy metody pro výpočet kořenů funkce: x^3……, x0 = 3.
Oproti minulemu kolu bylo mene prikladu, ale byly pry vice na zamysleni (dle slov Wernera).
1) Úlohu zformulujte jako LP nebo napište, že to není možné a zdůvoďněte: min Suma( f( aix - bi ) ) (suma přes i) kde a1,..,am je prvkem R^n, b1,..,bm je prvkem R a fce je dana obrazkem (jednoduchy obrazek kde to bylo max(-x,1/2*x))
2) Napište příklad simplexové tabulky LP (a zároveň udejte aktuální bázi) tak, že akt. bázové řešení je přípustné a degenerované.
3) Nechť A (z R^m*n), b (z R^m). Nechť m < n a nechť soustava rovnic Ax = b má nekonečně mnoho řešení. Hledáme vektor x* (z R^n) nejmenší délky splňující soustavu rovnic, tedy x* je řešením úlohy min { ||x||2 | x z R^n, Ax = b }
a) je kritérium konvexní funkce? b) je množina přípustných řešení konvexní množina? c) vyřešte metodou Lagrangeových multiplikátorů. Výsledkem bude explicitní vzorec pro x*. d) ve větě o Lag. multipl. vystupuje pojem regulárního bodu omezení. Co znamená tato podmínka v této úloze?
4) Čemu je rovno min(xT*A*x + bT * x) kde matice A (z R^n*n) je libovolná (tj. nemusí být symetrická)? Diskutujte řešení pro různé vlastnosti matice A a vektoru b.
5) Odpovězte a zdůvodněte, zda je -2 vl. číslem matice [ 1 0 3, 0 -1 -1, 3 -1 2 ]. Pokud ano, napište vlastní vektor.
6) Je nebo není množina { (x,y) z R^2 | x >= 0, y >= 0, y^2 >= 2*x } konvexní? Důkaz proveďte algebraicky na základě definice, nikoliv obrázkem.
7) Mějme úlohu LP: min dT*x za podmínek Ax + By = c, x>=0, y>=0 kde se minimalizuje přes x a y.
a) napište duální úlohu k této b) napište pro tuto dvojici úloh podmínku komplementarity
1) Určit bázové řešení, určit zda je přípustné, pokud lze, udělat 1 krok simplexové metody
2) Vypočítat simplexovou metodou
3) Určit hodnotu ||x||1,||x||2 a ||x||8 pro vektor (1,-2,-3)
4) napsat rovnici optimálního x pro min(||Ax-b||2)
5) {min sum(ai*xi); kde xi>0; sum(xi)=1}, určit optimální xi, napsat duální úlohu a podmínku komplementarity
6) min |xi| Dokázat, zda je nebo není funkce konvexní
7) Newtonova metoda, obecný výpočet Xk+1 z Xk a konkrétní příklad f(X)=ln(x+y)-(x^+y^2)/2 X=(1,1)
8) Příklad s kolem a závažími na provázku
1) A je antisymetrická, je AA symetrická/antisymetrická? (řešení: symetrická)
mozna hezci reseni: (AA)^T = A^T A^T = (-A)(-A) =(-1)^2 AA = AA a pokud AA=AA^T pak je symetricka
2)
3) Vyřešit sin x = 1/2x (řešení: Newtonova metoda na sin x - 1/2x = 0, nutnost počítat sin v radiánech, malý tip : mnohé kalkulačky umí pracovat s předchozí hodnotou (Ans), tedy stačí do nich napsat vzorec s (Ans) a dávat “=“ dokud se děje nějaká změna)
4) Je ((x, y) | y = x^2) konvexní množina? (řešení: Aby to byla konvexní množina, tak byste museli vzít dva body na parabole a body na spojnici by musely být vyjádřitelné jako v definici. Tedy není konvexní, stačí dosadit jakákoliv dvě čísla a zvolit alfu 1/2)
, nyní už jen ověříme
5)-x) můžou editovat další
(latex zda se nefunguje)
1) Dokazat ze matice je pos. def.:
x^T (A^T A + \alpha I)x = x^T(A^T A)x + (x^T \alpha I)x
x^T(A^TA)x=(Ax)^T Ax=||Ax||^2 >=0
(x^T \alpha I)x=\alpha x^T I x=\alpha ||x||^2 > 0
kdyz to sectu jsem > 0 a tudiz pos def.
2) zebrik: h(x)=kx + (1-x^2)^1/2
zderivuju, dam rovne nule a vyjde
x=(k^2/(1+k^2)^1/2
citelna verze:
a mene citelne avsak s opsanymi pocty bodu:
(pls add something)
sin x = 1/2*x
f = sin x - 1/2*x = 0
f' = cos x - 1/2
od ruky nakreslíme sin x a 1/2*x vidíme, že se protínají ve 3 bodech:
xa = 0
1,5 < xb < 2
-2 < xc < -1,5
poslední 2 body symetrické stačí spočítat jeden
Newtonova metoda
začal jsem v x0 = 2
xk+1 = xk - f(xk)/f ' (xk)
x1 = 2 - sin(2)-1/2*2/cos(2)-1/2
x1 = 1,900995594
x2 = x1 - f(x1)/f ' (x1)
x2 = 1,895511645
x3 = 1,895494267
x4 = 1,895494267
… už se to nemění, máme velmi přesný výsledek
Všechny body budou:
xa = 0
xb = 1,895494267
xc = -1,895494267
Někdo kdo s tímto řešením souhlasí, by to sem mohl napsat a smazat , případně napsat, že s tím nesouhlasí, a uvést opravu. (+2*Souhlas)
Pěstujeme melouny, dnes jich máme 200 kg a výkupní cena je 9 Kč/kg, každý den vypěstujeme 5 kg, ale výkupní cena klesne o 10 halířů. Kdy je máme prodat, abychom co nejvíce vydělali?
a)
max cTx;suma x = k; k < = n; c∈Rn; x>= 0
b)
max cTx; suma x = k; k < = n; c∈Rn; 0 < = x < = 1
U = span{(0,-1,1),(1,0,-1)}.
a)
ortogonální doplněk U
b)
ortogonální projekce
c)
Leží (1,1,0) na U.
y = x2
Kružnice se středem (3,0) a poloměrem 1
Spočítejte bod na parabole, který je nejblíže kružnici.
Řešení na wolfram alpha
Funkce f(x1, … ,xn) vrací sumu dvou nejmenších prvků. Dokažte z definici, že funkce není konvexní.
a)
Najdi stacionární body funkce f(x,y)=x3 - 3xy + 3y2
b)
Urči zda jde extrémy.
c)
Udělej první krok Newtonova algoritmu, výchozí bod je x0 = (1,1/2).
Dokaž, že ATA+α*I je pozitivně definitní; α>0
převeď funkci „Σ f(aiTxi - bi)“ na LP, f byla definována obrázkem, který ukazoval funkci, která y=-x, pro x<0 a y = ½x pro x>=0
a)
aTx=1; ||a||2=1; hledej x pro které platí aTx=1, že vzdálenost od bodu b je minimální.
b)
Nakresli pro dvojrozměrný prostor.
Týdně vytěžíme 10t červené rudy a 8 tun černé rudy. Z rud vyrábíme tři slitiny, měkkou, tvrdou a pevnou, na jednu tunu měkké slitiny spotřebujeme 3 t červené a 5 t černé rudy, na tvrdou slitinu spotřebujeme 5 t červené a 3 tuny černé rudy a na pevnou 5 t červené a 5 t černé. Měkkou slitinu prodáváme za 2,5, tvrdou za 3 a pevnou za 4 (v (asi) 100 tis Kč).
a)
Kolik které slitiny máme vyrobit, abychom vydělali, co nejvíce? Formulujte LP.
b)
Vyřešte simplexovým algoritmem.
c)
Formulujte duální úlohu k této úloze.
d)
Spočítejte dual co nejjednodušeji.
1)
[za 25]
10)
Matlabovské řešení - zdroják
Optimální hodnota: 7
Řešení primár: (0, 1, 1)
Řešení duál: (0.3, 0.5)
Prosím přidejte sem nějaké vyřešené příklady…
Psali jsme to jenom z paměti po zkoušce, takže to možná bylo zadané jinak, ale představu o zadaných příkladech by to mělo poskytnout.
Máme papír, který má celkovou plochu 600 cm2. Nahoře a dole je okraj 2 cm a na stranách 1 cm. Spočítejte rozměry papíru, aby plocha tisknutelné části byla co největší. Výsledek uveďte přesně, v nezaokrouhleném tvaru.
Máme vektory a a b, které náleží Rn, ||a||2 = ||b||2. Dokažte, že vektory a+b a a-b jsou navzájem kolmé.
Vyrábíme kravaty, vyrábíme dva modely luxusnější model A a model B. Model A prodáváme za 400 Kč a model B za 300 Kč. Výroba modelu A trvá dvojnásobnou dobu co výroba kravaty B. Stroje stihnou za den vyrobit 1000 kusů kravaty B. Obě kravaty jsou stejně náročné na látku. Denně dostaneme látku, ze které lze vyrobit 800 kravat typu B. Na kravatu A dáváme luxusní sponu, máme domluvenou dodávku až 300 těchto spon. Na kravatu B dáváme obyčejnou sponu a těch máme k dispozici 700 denně. Vypočtěte kolik kravat A a kolik B je nejlepší vyrobit pro maximální zisk.
Najděte potencionální lokální extrémy rovnice aTx + bTy. Za podmínek xTy = 1. Vektory x a y jsou neznámé proměnné a vektory a a b jsou dané.
Máme funkci f = 1/x + 1/y + xy.
a) Najděte stacionární body.
b) Určete, zda jsou to lokální extrémy.
c) Proveďte Taylorův polynom 1. řádu pro bod (2,2).
a)
Nějaká soustava která vypadala nějak takto
a1,1x + a1,2y + a1,3x*y = b1
a2,1x + a2,2y + a2,3x*y = b2
a3,1x + a3,2y + a3,3x*y = b3
ačka i b čka byla daná, jenom si je nepamatujeme, byla tam nápověda, která říkala, že jsme měli jsme nahradit x*y na z (z = x*y).
a1,1x + a1,2y + a1,3z = b1
a2,1x + a2,2y + a2,3z = b2
a3,1x + a3,2y + a3,3z = b3
tato soustava měla myslím 1 řešení.
Pak jsme se měli zamyslet, kolik to má jako celek řešení. x*y mi nedávalo z, takže bych řekl, že to asi nemělo řešení.
b)
Měli jsme udělat 1. krok Gauss-Newtonovy metody výše uvedené soustavy.
minni=1|xi|; kde x náleží Rn.
Myslím, že tam bylo výslovně napsáno dokaž z definice.
a)
Pro které n je funkce konvexní.
b)
Pro které n je funkce konkávní.
max Σni=1 cixi; vektor c je daný, vektor x je neznámá proměnná
a)
Napište vzorec pro maximální hodnotu funkce.
b)
Napište duál.
c)
Komplementarita.
d)
Máme daný vektor c, myslím, že to bylo nějak takto (c1,c2,c3)= (-2,3,4) nebo možná trochu jinak. Napište hodnotu x pro primární a hodnotu duální úlohy.
Byla zadaná soustava, ve tvaru:
a1,1x1 + a1,2x2 + a1,3x3 < = b1
a2,1x1 + a2,2x2 + a2,3x3 < = b2
a3,1x1 + a3,2x2 + a3,3x3 = -b3
ačka a bčka byla nějaká čísla ale ty si nikdo nepamatoval.
a)
Inicializujte simplexovu metodu. Nepoužívejte duální simplex.
b)
Proveďte jeden krok simplexova algoritmu.
c)
Napište aktuální bázi po jednoum kroku simplexovy metody a hodnotu kriteriální funkce.
Převeďte na LP nebo dokažte, že to nejde.
a)
min {1xT; ||Ax = b ||∞) < = 1}
b)
min( max aix = b + ||x||∞)
Prosím přidejte sem něco.
4. 11. 2011
Strany obdelnika oznacim a, b.
Lagarangeova fce:
Derivace lagarangeovy fce prolozime rovny nule:
Odtud:
A tedy:
Slajdy z optimalniho rozhodovani a rizeni
Fotky z přednášky o simplexové metodě (na uloz.to)
Článek o simplexové metodě na základě přednášek profesora Štechy
Simplexová metoda - studijní materiály technické univerzity v Liberci
Skvělý applet pro výpočet simplexové metody
Simplexová metoda z Jihočeské univerzity
Pěkné vysvětlení LP (slidy, opět JČU)
Dualita (stručně a jasně, opět JČU)
Výpočet vlastních čísel a vlastních vektorů na Algoritmy.net
Optimalizační úlohy z Masaryčky - mohlo by se hodit na zkoušku, konkrétně druhá část knihy.