Nelineární programování - úvod
Brožová H.: Matematické programování I, Nelineární
optimalizační modely, skripta ČZU, 2004
Pánková V.:Nelineární optimalizace pro ekonomy, Professional
Publishing,2003
Klasifikace optimalizačních modelů
Podle počtu kritérií• jednokriteriální• VícekriteriálníPodle typu použitých
funkcí • lineární optimalizační
modely, • nelineární optimalizační
modely
Podle typu kritéria • minimalizační model• maximalizační model• cílovém modeluPodle charakteru množiny
přípustných řešení a účelové funkce
• konvexních optimalizačních modelech
• nekonvexních optimalizačních modelech.
Konvexní optimalizační model
Minimalizačním optimalizačním modelem nazveme úlohu nalezení minimální hodnoty účelové funkce za daných omezujících podmínek, tedy
min f(x) qi(x) 0 , i = 1, ..., m , x = (x1, x2, ..., xn)T Rn ,
kde f(x) a qi (x) jsou reálné funkce více proměnných a x je prvek vektorového prostoru Rn.
Konvexní optimalizační model s minimalizací účelové funkce obsahuje pouze konvexní funkce, resp. účelová funkce je konvexní funkce (musí existovat jediné minimum) a množina přípustných řešení je konvexní množina
Model lineárního programování
Funkce f je konvexní, jestliže pro každé dva rozdílné body X1,X2 a :platí ג
Konvexní množina přípustných řešení
X1=(0,3)
X2=(2,4)
1 2 1 21 1 ; 0,1f x x f x f x
Příklad 1
Firma chce zařadit do výrobního programu 2 typy výrobků. Průzkumem bylo zjištěno, že jednotkový zisk je v závislosti na prodaném množství (40-x1) resp. (60-2x2)na jeden prodaný kus. Na každý kus je potřeba 1 m2 plechu, kterého bylo nakoupeno 500 m2 ,a jedna hodina práce na první výrobek a dvě hodiny na druhý výrobek. K dispozici je 800 pracovních hodin.
Kolik kterých výrobků má být vyrobeno, aby zisk byl maximální?
Předpokládáme, že se všechny vyrobené výrobky prodají.
• Řešení: Graficky sestrojíme množinu přípustných řešení. První parciální derivace účelové funkce položíme rovny nule a zkoumáme, zda tento bod leží v množině přípustných řešení.
• Optimum je tedy: x1=20 a x2=15, maximální zisk 850.
1 1 2 2
2 21 1 2 2
1 2
1 2
1 2
40 60 2 max
40 60 2 max
500
2 800
0; 0
x x x x
x x x x
x x
x x
x x
1 2 3 4 5 6 7 8 9 10x1=20
-1000-800-600-400
-2000
200
400
600
800
1000
0
100
200
300
400
500
600
0 200 400 600x1
x2
Gradient funkce
• Vektor prvních parciálních derivací funkce f(x) se nazývá gradient a značí se
f x
1
2
n
f
x
f
xf x
f
x
Gradient funkce pro příklad 1
• Převedeme na formu v definici, tj. minimalizace:
2 21 1 2 240 60 2 minx x x x
1
2
40 2
60 4
xf x
x
Hessova matice
Hessova matice H je symetrická matice druhých parciálních derivací, kdy na místě ij je prvek:
Je-li příslušná Hessova matice pozitivně definitní, je funkce konvexní. Jestliže pro prvky některé hii platí:
pak matice H není pozitivně definitní.
2
; 1, 2,..., ; 1, 2,...,i j
f xi n j m
x x
0iih
Hessova matice pro příklad 1
Příslušná Hessova matice je pozitivně definitní (prvky na hlavní diagonále jsou kladné, funkce je konvexní.
1
2
40 2 2 0;
60 4 0 4
xf x
x
H
Příklad 2: Zjistěte, zda funkce je konvexní
2 21 2 1 2 1 2( ) 12 4 4 4f x x x x x x
1 2
1 2
8 4 8 4;
12 4 8 4 8
x xf x
x x
H
Lagrangeovy multiplikátoryÚloha na vázaný extrém:min f(x) qi(x) = 0 , i = 1, ..., m , x = (x1, x2, ..., xn)T Rn ,
• Hledání optima nelineární úlohy, jejíž množina přípustných řešení je omezena podmínkami typu qi(x) = 0, je možné převést na řešení soustavy rovnic.
• Pokud:• funkce f a q jsou spojitě diferencovatelné• gradienty funkcí q jsou lineárně nezávislé vektory• xopt bod lokálního minima funkce,• pak existují jednoznačné skaláry u1,u2,…,um takové, že platí:
1
0m
opt i j optj
f x u g x
Lagrangeova funkce
Má-li funkce f(x) lokální minimum, pak:
)()f()(qu)f(),L( Tm
iii xquxxxux
1
0
0
x opt
u opt
L x
L x
• Vytvoří se soustavy n+m rovnic o n+m neznámých.• Pokud je množina M konvexní a funkce f(x) také konvexní,je
nalezený extrém je jediným globálním minimem. Hessova matice příslušné Lagrangeovy funkce je pozitivně definitní.
Příklad 3:
Řešení soustavy rovnic: x1=20; x2=15; u1=0; u2=0
2 21 1 2 2
1 2
1 2
2 21 1 2 2 1 1 2 2 1 2
40 60 2 min
35 0
2 50 0
40 60 2 35 2 50
x x x x
x x
x x
L x x x x u x x u x x
1
2
1
2
1 1 2
2 1 2
1 2
1 2
40 2 0
60 4 2 0
35 0
2 50 0
x opt
x opt
u opt
u opt
L x x u u
L x x u u
L x x x
L x x x
B b2 0 1 1 400 4 1 2 601 1 0 0 351 2 0 0 50
inverze x0 0 2 -1 200 0 -1 1 152 -1 -12 8 0
-1 1 8 -6 0
-1x = B b
Příklad 4: Lineární model
1 2
1
1 2
1 2 1 1 2 1 2
60 70 min
10 0
40 0
60 70 10 40
x x
x
x x
L x x u x u x x
1
2
1
2
1 2
2
1
1 2
60 0
70 0
10 0
40 0
x opt
x opt
u opt
u opt
L x u u
L x u
L x x
L x x x
Řešení soustavy rovnic: x1=20; x2=30; u1=-10; u2=70
0 0 1 1 60 c10 0 0 1 70 c21 0 0 0 10 b11 1 0 0 40 b2
uf0 0 1 0 10 x1 27000 0 -1 1 30 x21 -1 0 0 -10 u10 1 0 0 70 u2
Příklad 5: Optimalizace portfolia
Hodláme investovat 1 jednotku do 4 aktiv, které mají náhodné výnosy c1,…,c4 . Z jedné investované jednotky chceme získat 1,2 jednotky.
Jsou známy očekávané výnosy (aritmetický průměr sloupce) a matice kovariance.
Čím jsou její prvky blíž k 1, tím se investice vzájemně ovlivňují ve stejném směru. Negativní kovariance značí pohyb v opačném směru.
c1 c2 c3 c4
0,5 1,1 1,5 1,7
0,2 1 1,2 1,5
0,7 0,9 1,6 0,8
0,6 0,8 1,7 0,6
0,6 0,9 1,2 1,2
0,8 1 1,4 1,9
0,7 1,1 1,2 1,8
0,5 0,9 1,4 1,6
0,6 1,3 1,3 1,7
0,7 1,1 1,4 0,4
Matice kovariance 1 2 3 4
1 0,0249 0,0011 0,0069 -0,0118
2 0,0011 0,0189 -0,0099 0,0288
3 0,0069 -0,0099 0,0269 -0,0428
4 -0,0118 0,0288 -0,0428 0,2616
1
i i j j
ijj
E c c c cq
1 2 3 4
1 2 3 4
min
1
0,59 1,01 1,39 1,32 1,2
Tx Qx
x x x x
x x x x
1
21 2 3 4
3
4
2 2 2 21 2 3 4
0,0249 0,0011 0,0069 0,0118
0,0011 0,0189 0,0099 0,0288
0,0069 0,0099 0,0269 0,0428
0,0118 0,0288 0,0428 0,2616
0,0211 0,0389 0,0189 0,2358 min
x
xx x x x
x
x
x x x x
2 2 2 21 2 3 4
1 1 2 3 4 2 1 2 3 4
0,0211 0,0389 0,0189 0,2358
( 1 0,59 1,01 1,39 1,32 1,2
L x x x x
u x x x x u x x x x
2 2 2 21 2 3 4
1 2 3 4
1 2 3 4
0,0211 0,0389 0,0189 0,2358 min
1 0
0,59 1,01 1,39 1,32 1,2 0
x x x x
x x x x
x x x x
1
2
3
4
1
2
1 1 2
2 1 2
3 1 2
4 1 2
1 2 3 4
1 2 3 4
0,0422 0,59 0
0,0778 1,01 0
0,0378 1,39 0
0,4716 1,32 0
1 0
0,59 1,01 1,39 1,32 1,2 0
x opt
x opt
x opt
x opt
u opt
u opt
L x x u u
L x x u u
L x x u u
L x x u u
L x x x x x
L x x x x x
Výsledky
• Vzhledem k tomu, že v tomto typu modelu nejsme schopní počítat s nerovnicemi, nelze vložit ani podmínky nezápornosti.
x1 0,041989
x2 0,157962
x3 -0,57686
x4 1,376908
u1 0,013003
u2 -0,02504
Kuhn-Tuckerova věta o sedlovém bodě
Konvexní optimalizační modelmin f(x) qi(x) 0 , i = 1, ..., m , x = (x1, x2, ..., xn)T Rn ,
Účelová funkce f(x) nabývá minima v bodě xopt modelu právě tehdy, když existuje vektor
uopt Rm a platí následující vztahy :
xopt 0 a uopt 0
L(xopt, u) L(xopt, uopt) L(x, uopt)
a existuje alespoň jeden vektor x Rn, že qi(x) < 0,i=1, ...m.
V bodě xopt, uopt má Lagrangeova funkce sedlový bod.Min vzhledem k x a max vzhledem k u.
Kuhn - Tuckerovy podmínky Konvexní optimalizační úloha má řešení xopt právě tehdy,
když existuje vektor uopt a platí :
opt opt
opt optopti
. 0 0
( , ). 0 1
( , ). . 0 1
. 0 1
. 0 1
opt opt
i
i
opt opt
j
opt optoptj
j
I x a u
LII , i ,...,m
u
LIII u , i ,...,m
u
L( , )IV , j ,...,n
x
L( , )V x . , j ,...,n
x
x u
x u
x u
x u
Kuhn - Tuckerovy podmínky Zápis pomocí gradientů:
opti
. 0 0
. 0 1
. . 0 1
. 0 1
. 0 1
i
i
j
j
opt opt
u
u
x
optj x
I x a u
II L , i ,...,m
III u L , i ,...,m
IV L , j ,...,n
V x . L , j ,...,n
Příklad 4: Lineární model
1 2
1
1 2
1 2 1 1 2 1 2
60 70 min
10
40
60 70 10 40
x x
x
x x
L x x u x u x x
1
1 2 1 2
1
, , ,u
L x x u uL
u
1
2
1
2
1 2
2
1 1 1 2
2 1 2
. 60 0
70 0
. 60 0
70 0
x
x
x
x
IV L u u
L u
V x L x u u
x L x u
1
2
1
2
1 2 1 2
1
1 2
1 1 1
2 2 1 2
. 0; 0; 0; 0
. 10 0
40 0
. 10 0
40 0
u
u
u
u
I x x u u
II L x
L x x
III u L u x
u L u x x