Optimalizace

• Stránky předmětu: https://cw.felk.cvut.cz/doku.php/courses/a4b33opt/start
• Přednášející: Ing. Tomáš Werner, PhD, Prof. Ing. Jan Štecha, CSc.
• Cvičící: Ing. Vojtěch Franc, PhD, Ing. Saša Shekhovtsov, Ing. Jura Trefný, Ing. Karel Zimmermann, PhD

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

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

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

• Kdo po písemce překročí 49 bodů, může nebo nemusí jít k ústní části. Ta může výslednou známku zlepšit ale i zhoršit.
• NEW Přidány materiály s požadavky na zkoušku Požadavky ke zkoušce
• Stránka pro Požadavky ke zkoušce tady: Požadavky ke zkoušce

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.

ř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

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:

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

(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:
x_a = 0
1,5 < x_b < 2
-2 < x_c < -1,5
poslední 2 body symetrické stačí spočítat jeden
Newtonova metoda
začal jsem v x0 = 2
x_k+1 = x_k - f(x_k)/f ' (x_k)

x₁ = 2 - sin(2)-1/2*2/cos(2)-1/2
x₁ = 1,900995594
x₂ = x₁ - f(x₁)/f ' (x₁)
x₂ = 1,895511645
x₃ = 1,895494267
x₄ = 1,895494267
… už se to nemění, máme velmi přesný výsledek
Všechny body budou:
x_a = 0
x_b = 1,895494267
x_c = -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 c^Tx;suma x = k; k < = n; c∈Rⁿ; x>= 0
b)
max c^Tx; suma x = k; k < = n; c∈Rⁿ; 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 = x²
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(x₁, … ,x_n) vrací sumu dvou nejmenších prvků. Dokažte z definici, že funkce není konvexní.

a)
Najdi stacionární body funkce f(x,y)=x³ - 3xy + 3y²
b)
Urči zda jde extrémy.
c)
Udělej první krok Newtonova algoritmu, výchozí bod je x₀ = (1,1/2).

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

převeď funkci „Σ f(a_i^Tx_i - b_i)“ na LP, f byla definována obrázkem, který ukazoval funkci, která y=-x, pro x<0 a y = ½x pro x>=0

a)
a^Tx=1; ||a||₂=1; hledej x pro které platí a^Tx=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 cm². 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

Máme vektory a a b, které náleží Rⁿ, ||a||₂ = ||b||₂. Dokažte, že vektory a+b a a-b jsou navzájem kolmé.

Řešení

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í

Najděte potencionální lokální extrémy rovnice a^Tx + b^Ty. Za podmínek x^Ty = 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
a_1,1x + a_1,2y + a_1,3x*y = b₁
a_2,1x + a_2,2y + a_2,3x*y = b₂
a_3,1x + a_3,2y + a_3,3x*y = b₃
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).
a_1,1x + a_1,2y + a_1,3z = b₁
a_2,1x + a_2,2y + a_2,3z = b₂
a_3,1x + a_3,2y + a_3,3z = b₃
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.

minⁿ_i=1|x_i|; kde x náleží Rⁿ.
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 Σⁿ_i=1 c_ix_i; 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 (c₁,c₂,c₃)= (-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:
a_1,1x₁ + a_1,2x₂ + a_1,3x₃ < = b₁
a_2,1x₁ + a_2,2x₂ + a_2,3x₃ < = b₂
a_3,1x₁ + a_3,2x₂ + a_3,3x₃ = -b₃
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 {1x^T; ||Ax = b ||_∞) < = 1}
b)
min( max a_ix = b + ||x||_∞)

Prosím přidejte sem něco.

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.

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 za podminky pro zadane a hledane
   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
   1. najdete stacionarni body f(x,y) (odpoved: polozime jakobian == 0, po dopocteni vyjde stacionarni bod )
   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
   4. Newton-gradientni metoda - máme , určete pomocí Newtona,

Strany obdelnika oznacim a, b.


Lagarangeova fce:

Derivace lagarangeovy fce prolozime rovny nule:



Odtud:


A tedy:

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

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.

• Cvičení 2 - slovní úlohy na linprog
• Cvičení 3 - Lineární programování 2
• Cvičení 4 - Lineární programování 3
• Cvičení 5 - Lineární programování 4
• Cvičení 6 - Metoda nejmenších čtverců
• Cvičení 7 - Metoda nejmenších čtverců 2
• Cvičení 10 - Markowitzův model
• Cvičení 11 - Numerické metody řešení

• lineární programování 1

• Komentáře studentů k předmětu
• Reakci vyučujících na (páteční) diskusi najdete zde

Vypočítané příklady