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