Optimalizace – obecny´ u´vod
Optimalizace – obecny´ u´vod • Motivace optimalizacˇnı´ch u´loh [procˇ optimalizovat?] • Formalizace proble´mu [jak obecneˇ popsat optimalizacˇnı´ u´lohu?] • Klasifikace optimalizacˇnı´ch proble´mu˚ [existujı´ podobne´ proble´my?] • Trˇ´ıdy optimalizacˇnı´ch algoritmu˚ [existujı´ algoritmy na rˇesˇenı´ me´ho proble´mu?] • Prˇ´ıklady
1
2
Optimalizace – obecny´ u´vod
Motivace optimalizacˇnı´ch u´loh Jak se nejlevneˇji najı´st? • Cı´l: Z dane´ho seznamu potravin sestavit nejlevneˇjsˇ´ı jı´dlo • Omezenı´: Vy´sledne´ jı´dlo musı´ mı´t dostatecˇnou nutricˇnı´ hodnotu • Poprve´ zkouma´no v 40. letech minule´ho stoletı´ pro arma´dnı´ u´cˇely Polozˇka
Cena
Nutricˇnı´ hodnota
[Kcˇ/1kg]
[Cal/100g]
Veprˇova´ pecˇeneˇ s kostı´
120,10
273
Kurˇe
51,49
331
Brambory rane´
8,39
93
Chle´b konzumnı´ kmı´novy´
15,56
260
...
3
Optimalizace – obecny´ u´vod
Motivace optimalizacˇnı´ch u´loh Jak nejbezpecˇneˇji ulozˇit penı´ze? • Cı´l: Ulozˇit penı´ze do vybrany´ch akciı´ s nejmensˇ´ım rizikem • Omezenı´: Dosa´hnout alesponˇ prˇedepsane´ho vy´nosu • Za´kladnı´ proble´m Managementu portfolia [3] Akcie Komercˇnı´ banka CˇEZ Unipetrol Philip Morris CˇR ...
Cena [Kcˇ] 2001
2002
2003
2004
2005
1000
2000
2250
3100
3450
850
990
140
330
700
45
40
60
80
225
8000
1100
15000
17500
19000
4
Optimalizace – obecny´ u´vod
Motivace optimalizacˇnı´ch u´loh Jak neju´sporneˇji cestovat? • Cı´l: Vykonat co nejkratsˇ´ı okruzˇnı´ jı´zdu po vybrany´ch meˇstech • Omezenı´: Kazˇde´ meˇsto navsˇtı´vit alesponˇ jednou ´ loha obchodnı´ho cestujı´cı´ho, poprve´ uvedena´ v roce 1930 • U • Aplikace v na´vrhu spoju˚, automaticke´ vy´robeˇ . . . Praha
Brno
Ostrava
Cheb
Praha
0 km
205
381
176
Brno
207
0 km
180
381
Ostrava
380
181
0 km
550
Cheb 176 384 556 0 km Vzda´lenosti mezi vybrany´mi meˇsty
5
Optimalizace – obecny´ u´vod
Motivace optimalizacˇnı´ch u´loh Jaky´ pocˇı´tacˇ si vybrat? • Cı´l: Nakoupit nejvhodneˇjsˇ´ı notebook • Krite´ria vy´beˇru: Cena, vy´kon, velikost pameˇti, disku, u´hloprˇ´ıcˇka . . . • Typicky´ prˇ´ıklad hleda´nı´ kompromisnı´ho rˇesˇenı´ [teorie rozhodova´nı´] Cena
´ hloprˇ´ıcˇka U
Disk
Va´ha
[Kcˇ]
[”]
[GB]
[kg]
AMILO Pro V2035
14 999
15,4
60
2,9
Aspire 9814WKMi
65 996
20
240
7,5
Qosmio G30-194
93 210
17
320
4,5
Lifebook Q2010 U1400 105 743 12 80 Vybrane´ parametry notebooku˚ (prosinec 2006)
0,9
Typ
6
Optimalizace – obecny´ u´vod
Formalizace optimalizacˇnı´ch u´loh • Obecna´ formulace: Najdi xopt ∈ O , ktere´ splnˇuje H
f (xopt ) f (x)
pro vsˇechna
x∈O
• „x“ – promeˇnne´ vystupujı´cı´ v [matematicke´] formulaci proble´mu • „O “ – mnozˇina prˇ´ıpustny´ch rˇesˇenı´ (odpovı´da´ omezenı´ ) • „ f “ – cı´lova´ funkce [ f : O → H] • „H“ – obor hodnot cı´love´ funkce H
• „“ – [cˇa´stecˇne´] usporˇa´da´nı´ oboru hodnot cı´love´ funkce – umozˇnˇuje urcˇit, ktere´ rˇesˇenı´ je „lepsˇ´ı“ • „xopt “ – optima´lnı´ rˇesˇenı´ u´lohy
7
Optimalizace – obecny´ u´vod
Formalizace optimalizacˇnı´ch u´loh Optima´lnı´ dieta • N ru˚zny´ch potravin • Nezna´me´ – hmotnost jednotlivy´ch potravin v kg: xi ∈ R, xi ≥ 0 • Cı´lova´ funkce f ( x ) = x1 c1 + x2 c2 + . . . x N c N , kde ci je cena za 1 kg i-te´ potraviny • Obor hodnot H =
R0+ ,
H
odpovı´da´ <
• Omezenı´ x1 k1 + x2 k2 + . . . x N k N ≥ K, kde k i je nutricˇnı´ obsah i-te´ potraviny a K pozˇadovany´ nutricˇnı´ obsah • O odpovı´da´ poloprostoru v R N
8
Optimalizace – obecny´ u´vod
Formalizace optimalizacˇnı´ch u´loh Na´kup pocˇı´tacˇe • Nezna´ma´ – porˇadove´ cˇ´ıslo notebooku x ∈ N • Cı´lova´ funkce: M ru˚zny´ch krite´riı´ f( x ) = [ f 1 ( x ), f 2 ( x ), . . . , f M ( x )],
H ∈ RM
• Porovna´nı´ dvou rˇesˇenı´
H
x1 x2
≡
f 1 ( x1 ) f (x ) 2 1 f 3 ( x1 ) f (x ) 4
• Optima´lnı´ portfolio → cvicˇenı´ • Obchodnı´ cestujı´cı´ → prˇedna´sˇka cˇ. 6
1
≤
f 1 ( x2 )
≥
f 2 ( x2 )
≥
f 3 ( x2 )
≤
f 4 ( x2 )
9
Optimalizace – obecny´ u´vod
Za´kladnı´ klasifikace optimalizacˇnı´ch u´loh • Dimenze proble´mu N – pocˇet [neza´visly´ch] slozˇek x • Jak roste pocˇet operacı´ potrˇebny´ch k zı´ska´nı´ xopt s dimenzı´? – ≈ CN k – Polynomia´lnı´ proble´m (P) [dieta, portfolio, volba notebooku] – ≈ 2 N – Exponencia´lnı´ proble´m (E) – Nedeterministicky´ Polynomia´lnı´ proble´m (NP) – proble´m rˇesˇitelny´ pomocı´ polynomia´lnı´ho pocˇtu kroku˚, ale jen pomocı´ stochasticke´ho pocˇ´ıtacˇe, ktery´ „umı´ uha´dnout spra´vnou variantu“ [2] [obchodnı´ cestujı´cı´] ?
P = NP ≺ E • „?“ ma´ cenu 1 mil USD
Optimalizace – obecny´ u´vod
Prakticˇteˇjsˇı´ klasifikace optimalizacˇnı´ch u´loh
Prˇ´ıklad „optimalizacˇnı´ho stromu“ http://www-fp.mcs.anl.gov/otc/Guide/OptWeb
10
11
Optimalizace – obecny´ u´vod
Jaka´ je souvislost mezi prˇedchozı´mi prˇı´stupy? • Konvexnı´ mnozˇina
• [Ostrˇe] konvexnı´ funkce
O konvexnı´ + f konvexnı´ = P • [Ostrˇe] konvexnı´ funkce na konvexnı´ mnozˇineˇ ma´ pra´veˇ jedno minimum • Efektivnı´ metody matematicke´ho programova´nı´ [1]
Optimalizace – obecny´ u´vod
Shrnutı´ • Optimalizacˇnı´ u´loha: – [Matematicky´] model proble´mu – Optimalizacˇnı´ promeˇnne´ x – Cı´lova´ funkce f – Definicˇnı´ obor O – Obor hodnot H + metodika porovna´va´nı´ • Metody rˇesˇenı´ – Konvexnı´ u´loha → P → matematicke´ programova´nı´ → prˇedna´sˇky 2–3 – Nekonvexnı´ u´loha → NP/E → heuristicke´ metody → prˇedna´sˇky 4+
12
13
REFERENCE
Reference [1] S. Boyd and L. Vandenberghe, Convex optimization, Cambridge University Press, Cambridge, United Kingdom, 2004, http://www.stanford. edu/~boyd/cvxbook. [2] K. Devlin, Proble´my pro trˇetı´ tisı´ciletı´: Sedm nejveˇtsˇ´ıch nevyrˇesˇeny´ch ota´zek matematiky, Edice Atelier, vol. 24, Nakladatelstvı´ Dokorˇa´n a Argo, Praha, 2005. [3] J. Vesela´, Analy´za trhu cenny´ch papı´ru˚. I. Dı´l, Vysoka´ sˇkola ekonomicka´ v Praze, Fakulta financı´ a u´cˇetnictvı´, 1999. 2 Prosba. V prˇ´ıpadeˇ, zˇe v textu objevı´te neˇjakou chybu nebo budete mı´t na´meˇt na jeho vylepsˇenı´, ozveˇte se prosı´m na
[email protected]. Verze −002
