1.1 Formularea problemei de optimizare parametrica. Are întodeauna 3 elemente: a) functia criteriu sau functia obiectiv (care poate fi si o… [613317]

1 Sisteme Optimale

Capitolul 1
Optimizari parametrice
1.1 Formularea problemei de optimizare parametrica.
Are întodeauna 3 elemente:
a) functia criteriu sau functia obiectiv (care poate fi si o functionala) care trebuie mini mizata
sau maximizat
),,,( , :21 nnx xxf Df LRRRRRRRR→ ⊆

2

1.2 Aspecte matematice în determinarea extremelor n etede
Rolul central revine primei variatii a functiei obi ectiv Functia obiectiv: nR Xxxf ⊂ ∈ ), (
Se cauta un punct de extrem absolut pentru functia obiectiv f(x) pe X, Dx∈*, a.î
Dxxf xf x ∈∀ ≥ ), ( )(ea proprietat cu * *,
pentru un punct de maxim absolut pe X
Dxxf xf x ∈∀ ≤ ), ( )(ea proprietat cu * *,
pentru un punct de minim absolut pe X
x* este maxim local daca:
ε ε ≤∆ ∆+ =∀ ≤ >∃ ||cu , x ), ( )( a.i , 0* *x xx xf xf
x* este minim local daca:
ε ε ≤∆ ∆+ =∀ ≥ >∃ ||cu , x ), ( )( a.i , 0* *x xx xf xf

Formularea problemelor de optimizare parametrica po ate fi o:
problema de programare liniara daca f, h i, g j sunt liniare în raport cu variabilele x1, …, x n
problema de programare neliniara daca cel putin una din functiile f, h i, g j este neliniara în
raport cu variabilele x1, …, x n.

3 Conditii matematice pentru stabilirea punctelor de extrem
)( ) (* *xf x xff −∆+ =∆
Daca f admite derivate partiale de orice ordin în punctul x=x *, f∆poate fi dezvoltata în serie
Taylor, în jurul acestui punct
… 21*
22 *
+∆



∂∂∆+∆

∂∂=∆ x
xfx xxff
TT
T
primul termen: diferenta de ordinul I a variatiei f∆
xxff
T∆

∂∂=*
δ
al doilea termen: diferenta de ordinul II a variati ei f∆:
x
xfx f
TT∆



∂∂∆=*
22
2
21δ ,
unde
H
xf
xxfxxf
xf
xf
n nn
=




∂∂
∂∂∂∂∂∂
∂∂
=
∂∂
22
1212
2
12
22
KMK

H este o matrice patrata simetrica numita Hessianul functiei f.„
Conditii de extrem:
grad 0 )(*
1*
*=




∂∂∂∂
=

∂∂= ∇
nxfxf
xfxf M (ca vector)
Se rezolva ecuatia de mai sus pe X si se afla punctele x*.
2) Orice punct x* este un punct de extrem daca dife renta de ordinul 2, f2δ , este o forma
patratica definita în vecinatatea acestui punct. Se calculeaza H în x* si
– daca H este o matrice negativ definita atunci x* este un punct de maximum;
– daca H este o matrice pozitiv definita atunci x* este un punct de minimum;
3) Se examineaza care puncte de extrem sunt locale si care sunt globale.

4 Exemplul 1 : Fie ( A, b, cT) un sistem dinamic liniar cu


−−=2 112A ; 
=01b ;
Se cere sa se determine punctul optim de functionar e al procesului, stiind ca functia obiectiv
care evalueaza calitatea punctului de functionare e ste
; 1 2 )( + + = xb Ax x xfT T (1)
si ca f(x) trebuie sa fie maxim.
[ ] [ ] 1 0122 112 )(
21
21
21 +
+



−−=xx
xxxx xf ;
[ ] 1 2 2 2 )(1
21
2 1 2 1 + +
− + −= xxxx x xx xf ;
1 2 )2 ( ) 2()(1 2 2 1 12 1 + + − + + −= x xx x xxx xf ;
1 2 2 2 2 )(1 212
22
1 + + + − −= x xx x x xf ;
02 42 2 4
1 22 1
21=

+ −+ + −=




∂∂∂∂
=∂∂
x xx x
xfxf
xf

= + −=+ + −⇔
0 2 402 2 4
*
1*
2*
2*
1
x xx x




==
3132
*
2*
1
xx

Observatie: Se poate calcula gradientul direct din (1):
0 2 2 = + =∂∂b Ax xf; bA x1 * −−=⇒ ;




− −− −
=−
32
3131
32
1A
[ ]0 1
32
3131
32
*




− −− −
−=x =




3132
;
()()351 2 2 2 2 )(*
1*
2*
12*
22*
1*=+ + + − −= x xx x x xf

5 4) 2 2 4(
12 1
2
12
−=∂+ + −∂=
∂∂
xx x
xf
; 2) 2 2 4(
22 1
212
=∂+ + −∂=∂∂∂
xx x
xxf;
A
xf
xxfxxf
xf
H 24 224
2
22
212212
2
12
=

−−=




∂∂
∂∂∂∂∂∂
∂∂
=
[ ] [ ] ) ( 44 22 4
4 2242
2 212
1
2 12 1
2 1
21
2 1 x xx xx xx xxxxxxx Hx xT+ − −=

−+ −=



−−=

Deci 0 ≤Hx xT;2RRRR∈∀x (i.e. este o forma patratica negativ definita) ⇒*xeste un punct de
maxim

1.3 Aspecte matematice în determinarea extremelor n etede cu
restrictii de tip egalitate (legaturi)
Cu notatiile anterioare, avem o functie f pentru care cautam extremul pe un domeniu
nXRRRR⊆ , a.î. sa se verifice si egalitatile:
n m ,…,m i xhi < = = ; 1 , 0 )( (2)
Aceste egalitati se mai numesc si legaturi .
Exista doua metode de rezolvare a problemei determi narii extremelor.
Prima metoda
Se elimina m vaiabile din f(x) cu ajutorul legaturilor si se cauta extremul lui f în raport cu
celelalte n-m variabile.
A doua metoda
Se bazeaza pe regula multiplicatorilor Lagrange. Da ca f si hi admit derivate partiale continue
într-o vecinatate a punctului de extrem x* si grad f si grad hi sunt liniar independenti, atunci
exista multiplicatorii mλ λ ,,1L a.î. gradientul functiei
∑
=+ =m
iiixh xf xF
1)( )( )( λ
Sa fie nul în punctul x* :
0*
=

∂∂
xF (3)

6 Ecuatiile (2) si (3) formeaza un sistem de n+m ecuatii din care se pot determina coordonatele
punctului x* si multiplicatorii *λ

Exemplul 2 : Sa se determine volumul maxim al unui cilindru de raza x1 si înaltime x2, pentru o
arie totala A impusa.
Modelul problemei este
22
1 21),( xx xxf ⋅=π
0 2 2),( 212
1 21` =− + = A xx x xxh π π (5)
Functia sintetica este:
[ ]A xxx xx xxh xxf xxF − + + ⋅= ⋅+ = ) (2 ),( ),( ),( 2 11 22
1 21 21 21 πλ π λ
Anulam gradientul functiei F:

( ) 0 20) 2 (2 2
*
1*2*
1*
2*
2*
1* *
2*
1*
1
= ⋅+ ⋅=



∂∂= + ⋅+ ⋅ =



∂∂
x xxFx x xxxF
π λ ππ λ π
(6)
Daca rezolvam sistemul (6), considerand *λparametru, obtinem:
* *
2* *
1 4 ;2 λ λ −= −= x x ;
Introducem aceste valori în (5) si obtinem:
0 )(24 2*=−A λπ ;
πλ24 * A±=
Solutia pozitiva duce la incalcarea restrictiilor ( 4) si de aceea retinem solutia:
π6*
1Ax= ; *
1*
2 232xAx = =π; 2*
1 * x−=λ

Hessianul functiei ()*
2*
1,xxF este deci:

⋅ −=




−− −=




∂∂
∂∂∂∂∂∂
∂∂
=0113
612
0 22 6
*
1*
1*
1
2
22
212212
2
12
*A
xx x
xF
xxFxxF
xF
H π
ππ π
*Heste negativ definita si deci solutia x* este un maxim.

7 Daca dorim sa rezolvam aceasta problema cu toolboxu l de optimizari MATLAB, atunci va
trebui sa folosim functia fmincon ( vezi sectiunea 2.3 ).

1.4 Determinarea extremelor netede cu restrictii de tip inegalitate
Fie nX D⊂ domeniul determinat de restrictiile impuse variabil elor de stare. Chiar si în
conditii de regularitate ale functiilor f, h i, g j, în general, metoda multiplicatorilor Lagrange nu
poate fi aplicata si în acest caz. Doar cand puncte le de extrem se afla în interiorul domeniului
D.
În acest caz se folosesc metodele programarii matematice liniare si neliniare .
Exemplul 3: Sa se determine extremele functiei
2 1 21),( xx xxf +=
pe un domeniu D definit prin restrictiile:
; 0 , 02 1 ≥ ≥x x
0 2 4 :0 22 :
2 1 22 1 1
≥ −−≥ − −
x x gxx g
Din grafic, rezulta ca minimul functiei f este f=0, pt 02 1 = =x x , iar maximul este f=2 pt
2 ; 02 1 = =x x .
Daca mentinem domeniul D, dar luam functia obiectiv
2 1 21 2),( xx xxf + =
atunci aceasta admite o infinitate de maxime pe seg mentul desenat cu linie groasa.

x1 x2
h1 h2 0 f=0
f=2 1 2
4

8 1.5 Programare liniara
Se poate aplica atunci cand functiilor f, h i, g j sunt toate liniare în variabilele din x.

Exemplul 4
Un furnizor de placaj are 2 locatii într-un oras. F urnizorul primeste comenzi de la doi clienti
A si B, fiecare cerand foi de placaj de 3/4-inch. C lientul A cere 50 de foi si Clientul B cere 70
de foi.
Magazia din estul orasului are 80 de foi în stoc, i ar cea din partea de vest are 45 foi în stoc.
Costul livrarii per foaie este de:
– $0.50 de la magazia din est catre clientul A;
– $0.60 de la magazia din est catre clientul B;
– $0.40 de la magazia din vest catre clientul A;
– $0.55 de la magazia din vest catre clientul B;
Sa se afle cantitatile livrarilor de foi de placaj a.î costurile de livrare sa fie minimizate.
Care este acest cost?

1.5.1 Metodologia obtinerii modelului pt optimizare

1. Creati-va o idee generala despre problema.
2. Identificati obiectivul.(maximizare sau minimiza re)
3.Identificati variabilele.
4. Identificati restrictiile
5. Determinati vriabilele care pot fi controlate
6.Specificati cantitatile prin relatii matematice
7.Verificat modelul ca este complet si corect.

1. un graf cu magaziile si clientii
2. Sa se minimizeze costul livrarii
3. x1: magazie Est →client A
x 2: magazie Vest →client A
x 3: magazie Est →client B
x 4: magazie Vest →client B
4.Variabilele au doar limite inferioare
; 0 ; 0 ; 0 ; 0 4 3 2 1 x x x x ≤ ≤ ≤ ≤
Restrictii de tip inegalitate:

9 80 3 1 ≤ +xx
45 4 2 ≤ +x x
Restrictii de tip egalitate (legaturi):
50 2 1 = +xx
70 4 3 = +xx
Functia obiectiv:
4 3 2 1 4321 55 . 0 6 . 0 4 . 0 5 . 0 ),,,( x x x x xxxxf + + + =
Criteriul de optim: )( min xf
x cu




=
4321
xxxx
x

1.5.2 Utlizarea functiei linprog pentru rezolvarea unei probleme de
programare liniara
In contextul utilizarii functiei linprog, o problem a de programare liniara este definita prin:
Functia obiectiv este
xfT⋅
Iar criteriul de optim este
xfT
x⋅ min
Unde




=
nxxx
xM21
este vectorul cu variabilele ce fac obiectul optim izarii, iar fT este un vector
linie de aceeasi dimensiune n.
Restrictiile de tip inegalitate sunt exprimate prin
b Ax ≤,
unde A este o matrice m x n unde m este numarul de restrictii de tip inegalitate, iar b este un
vector de lungime m.
Restrictiile de tip egalitate sunt exprimate prin
eq eq bxA =⋅
Unde Aeq este o matrice r x n unde r este numarul de rsestrictii de tip egalitate, iar beq este un
vector de lungime r.

10 Exemplificam pe problema din exemplul 3.
Avem, în mod evident:
n=4;
[ ]55 . 0 6 . 0 4 . 0 5 . 0=Tf

Tlb 0] 0 0 [0 =
T ub ]inf inf inf inf [=


=
=45 80 ;10100101b A

=
=70 50 ;11000011
eq eq b A

Apelul functiei linprog se face ca mai jos

[x, fval]=linprog(f,A,b,Aeq,beq,lb,ub)

Daca vreun vector sau matrice lipseste, atunci argu mentul respectiv se completeaza cu [ ].