Optimalizace

  • Předmět je pro silnější povahy. I když se získané znalosti budou hodit, práce v semestru je příliš mnoho a 6 kreditů se zdá být málo. Pokud předmět nemáte povině, dobře si jeho zápis rozmyslete.

Cvičení

  • Docházka na cvičení je povinná. Absence je povolena pouze v dobře zdůvodněných případech.
  • Odevzdání úloh ze všech cvičení. Ulohy se odevzdávají již na cvičení, na kterém jsou zadány. V případě pozdního odevzdání je nutné vypracovat zadání bonusových úloh, jenž jsou při odevzdávání v řádném termínu nepovinné.
  • ZS2011/12: Ulohy se odevzdavaji pres upload system do nasledujiciho cvika. Pri pozdnim odevzdani se postupne strhava maximalni pocet bodu za vypracovani.

Zkouška

Známka u zkoušky:

  • Za testy na přednáškách získáte 0-30 bodů (budou 3 hodnocené testy, každý po max 10 bodech).
    • 1. Test 16.10.
    • 2. Test 24.11.
    • 3. Test 15.12.
  • Lze získat až 10 bonusových bodů za zformulování optimalizační úlohy ze svého života jako lineární nebo (konvexní) kvadratické programování
  • Za písemnou část zkoušky získáte 0-70 bodů. Známka se poté určí takto:

body 100-90 89-80 79-70 69-60 59-50 49-0

známka A B C D E F

11.1.2010

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.

18.1.2010

řešená písemka

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

26.1.2010

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

12.1.2011

1) A je antisymetrická, je AA symetrická/antisymetrická? (řešení: symetrická)

GraphGraph

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)

Graph, nyní už jen ověříme Graph

5)-x) můžou editovat další

7.1.2013

(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

23.1.2014

Zadání

citelna verze:

a mene citelne avsak s opsanymi pocty bodu:

opt_zk_23.1.2014a.jpg opt_zk_23.1.2014b.jpg

Řešení

(pls add something)

7)

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 FIXME, případně napsat, že s tím nesouhlasí, a uvést opravu. (+2*Souhlas)

3.2.2014

Zadání

1)

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?

2)

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

3)

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.

4)

y = x2
Kružnice se středem (3,0) a poloměrem 1
Spočítejte bod na parabole, který je nejblíže kružnici.
fbz4cs1.jpg
Řešení na wolfram alpha

5)

Funkce f(x1, … ,xn) vrací sumu dvou nejmenších prvků. Dokažte z definici, že funkce není konvexní.

6)

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).

7)

Dokaž, že ATA+α*I je pozitivně definitní; α>0

8)

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

9)

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.

10)

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.

Řešení

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… FIXME

10.2.2014

Zadání

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.

1)

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.

Řešení na WolframAlpha

2)

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é.

Řešení

3)

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.

Řešení

4)

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é.

5)

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).

6)

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.

7)

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í.

8)

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.

9)

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.

10)

Převeďte na LP nebo dokažte, že to nejde.
a)
min {1xT; ||Ax = b ||) < = 1}
b)
min( max aix = b + ||x||)

Řešení

Prosím přidejte sem něco. FIXME

27.1.2016

Zadání

4.2.2016

Zadání

11.2.2016

Zadání

1.2.2017

Zadání

Písemky

1. test

4. 11. 2011

  1. Vypočítat rovnici pro vlastní čísla matice 3×3
  2. Dokázat, že součin ortogonálních matic je matice ortogonální
  3. Kvadratická forma matice 2×2, zjistit, jestli je výsledech pro všechna x vždy nezáporné. (Háček byl v tom, že matice nebyla symetrická)
  4. Nepamatuji se přesně
  5. Definovat úlohu najití bodu, který má od zadaných přímek minimální součet kvadrátů vzdáleností.
  6. Napsat 5 jako MatLabovskou fci.

2. test

Zadani 25. 11. 2011:

  1. slovni uloha: Mame k dispozici 100m plotu, chceme postavit obdelnikovou ohradu o co nejvetsi plose. Jedna strana ohrady bude stat u reky, oplotit musime tedy jen tri strany. Reste pomoci Lagarangeovych multiplikatoru. Řešení na WolframAlpha
  2. Minimalizujeme Graph za podminky Graph pro zadane Graph a hledane Graph
    1. hledejme to minimum.. (dela se pres Lagarangeovy m.)
    2. jaka je graficka reprezentace? (odpoved: na nadrovine hledame nejblizsi bod k pocatku. )
  3. Mejme fci Graph
    1. najdete stacionarni body f(x,y) (odpoved: polozime jakobian == 0, po dopocteni vyjde stacionarni bod Graph)
    2. je tento bod extrem? jaky? (odpoved: ja si udelal druhe derivace.. ty jsou tam vsechny kladne, (1,1) je tedy minimum)
    3. napiste tailorak druheho radu v bode Graph
    4. Newton-gradientni metoda - máme Graph, určete Graph pomocí Newtona,
Reseni 1:

Strany obdelnika oznacim a, b.
Graph
Graph
Lagarangeova fce:
Graph
Derivace lagarangeovy fce prolozime rovny nule:
Graph
Graph
Graph
Odtud:
Graph
Graph
A tedy:
Graph
Graph
Graph
Graph

3. test

  1. Napsat Simplexovu tabulku pro daný problém - nutno převádět nerovnosti na rovnosti, řádky se zápornými b vynásobit -1, VYNULOVAT čísla v nultém řádku nad bázovými vektory
  2. Udělat jeden krok simplexu a napsat hodnotu kritéria po kroku
  3. Napsat, jestli hodnota kritéria už byla globální minimum
  4. Slovní úloha na kravaty, napsat jako LP
  5. Přepsat minimalizační úlohu jako LP (byla tam maxima)
  6. Napsat k předchozímu duální úlohu
  7. A doplnit o podmínky komplementarity.
  8. Tři minimalizační úlohy - napsat řešení úvahou, nebo zapsat jako LP, nebo napsat, že to nejde na LP a proč (konvexita kritéria/přípustných řešení)

Materiály

Úkoly na cvičení

2011

Diskuse k předmětu

Vypočítané příklady

courses/a4b33opt.txt · Poslední úprava: 2019/01/10 18:36 (upraveno mimo DokuWiki)
Nahoru
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0