7

OPTIMIZARE MULTICRITERIAL 7.1 Introducere

n multe dintre situaiile practice, din industrie sau din atelierele de proiectare, cnd se dorete optimizarea unui produs sau proces, este necesar satisfacerea simultan a ct mai multe criterii. n aceste condiii, trebuie determinat soluia care prezint fiabilitate maxim, este cel mai uor de realizat din punct de vedere tehnologic, cu consum minim de material, dimensiuni reduse, pre de cost minim, beneficiu maxim etc. Se pot determina cazuri n care o aceeai soluie este optim din toate punctele de vedere considerate, dar aceasta se ntmpl foarte rar pentru anumite situaii teoretice i de regul nu au nici un corespondent n situaiile practice, reale.

De cele mai multe ori, ne confruntm cu necesitatea de a concilia caliti opuse din punctul de vedere al criteriilor de optimizare i de a ezita n gsirea celui mai bun, sau a celui mai puin ru dintre compromisurile posibile. Dac dorim ca alegerea s fie fcut de calculator, atunci este necesar ntocmirea unui algoritm care s conin reguli sigure de apreciere, ce s permit alegerea cu discernmnt a soluiei optime. 7.2 Problema multicriterial a lui Pareto

Exemplul clasic al unei probleme de optimizare multicriterial [Osyczka, 1992], [Stancu-Minasian,1980], este cel al optimizrii geometriei unui arbore tubular, supus la torsiune i care trebuie s satisfac urmtoarele trei criterii:

a) Mas minim; b) Diametru exterior minim; c) Deformaie la torsiune minim.

Prin intermediul acestui exemplu, cunoscut n literatura de specialitate sub numele de Problema lui Pareto, vom introduce cteva noiuni de baz, care s permit facilitarea alegerii celei mai bune soluii, ntr-o situaie dat. Figura 7.1 definete complet elementul de arbore tubular, din punct de vedere al restriciilor geometrice. n urma analizei acestui element de arbore tubular, n funcie de un anumit tip de material, vom ncerca s determinm soluia optim, din punctul de vedere al celor trei criterii de optimizare amintite mai sus. Considerm ca variabile de decizie diametrele interior d, respectiv exterior D. Pentru reprezentarea convenabil a

Optimizare numeric. Algoritmi i programe n C

126

(7.1) (7.2)

(7.3)

(7.4)

(7.5)

(7.6)

(7.7)

(7.8)

conceptelor, considerm c lungimea L a arborelui este o constant.

Vom formula problema de optimizare a lui Pareto dup cum urmeaz:

Minimizm [ ] ;)(),(),()( 321 TXFXFXFXF = Supuse la: gj(X) 0; j = 1, 2, 3.

;

=

Dd

X

n care:

( )

( )( )

][;)(][;)(

][;5.016)(

][;32)(

][;)(

][;4

)(

min3

max2

441

443

2

221

VIddXgVDDXg

IVRdDDMXg

IIIdDG

MXF

IIDXF

IdDLXF

eT

T

==

=

==

=

unde: F1(X) este criteriul masei arborelui; F2(X) criteriul gabaritului arborelui; F3(X) criteriul deformaiei la torsiune; X vectorul variabilelor de decizie;

MT

MT

Dm

ax

d min

d D

L

Fig.7.1 Arbore tubular supus la torsiune.

Optimizare multicriterial

127

- densitatea materialului; MT momentul de torsiune aplicat arborelui tubular; G modulul de rezisten la forfecare; Re limita de elasticitate a materialului; coeficient de siguran. n figura 7.2 domeniul admisibil al soluiilor problemei este delimitat de restriciile (7.6) (7.8) astfel: la stnga de dreapta vertical d = dmin (notat [VI]), n partea de sus de dreapta orizontal D = Dmax (notat [V]), iar n zona dreapta-jos de restricia neliniar (7.6) (notat [IV]). Criteriul (7.3) al masei este minim atunci cnd paranteza (D2-d2) este minim. Pentru aceasta trebuie ca graficul funciei obiectiv notat cu [I] s se deplaseze n sensul sgeii din figura 7.2, cnd D scade, iar d crete. Poziia limit la care graficul funciei obiectiv F1(d,D) nc este n contact cu domeniul admisibil este punctul notat cu 1, pe frontiera acestuia. Aadar punctul 1 de pe frontiera domeniului admisibil reprezint punctul de optim pentru cazul n care problema de optimizare ar avea un singur obiectiv i anume masa minim. Criteriul (7.4) al gabaritului minim este reprezentat de funcia obiectiv F2(d,D) notat cu [II] n figura 7.2. Valoarea minim a lui F2 corespunde valorii minime a lui d, la care dreapta orizontal, notat [II], mai este n contact cu domeniul admisibil al soluiilor. Aceast situaie are drept soluie optim punctul 2 de pe frontiera domeniului admisibil. n fine, pentru criteriul al treilea al rezistenei la torsiune, funcia F3(d,D) este minim atunci cnd paranteza (D4-d4) este maxim, ceea ce

1

2

3

O

D

d dmin

Dmax

[I]

[II]

[III]

[IV]

[V]

[VI]

Fig.6.2 Interpretarea grafic a problemei lui Pareto.

Optimizare numeric. Algoritmi i programe n C

128

(7.9)

(7.10) (7.11)

(7.12)

nseamn c graficul funciei notat [III], se va deplasa spre valori mari ale lui D i valori mici ale lui d. Soluia optim pentru criteriul rezistenei la torsiune corespunde punctului notat cu 3 n figura 7.2.

Analiznd cele trei puncte de optim corespunztoare celor trei criterii de optimizare luate individual, se observ o complet incompatibilitate ntre acestea. Astfel, dac vom considera drept punct de optim al problemei de optimizare multicriterial , punctul 1, atunci criteriul masei minime va fi ndeplinit n proporie de 100% n timp ce restul criteriilor vor fi foarte departe de valorile lor optime. Dac alegem punctul 2 drept punct de optim, vom ndeplini criteriul gabaritului, dar vom da peste cap criteriile masei, respectiv rezistenei la torsiune s.a.m.d.

Acum trebuie s precizm c soluia acestei probleme nu depinde de nici o metod matematic miraculoas, ea depinde doar de o alt exprimare, din punct de vedere matematic.

Problema de optimizare descris mai sus (vezi fig.7.1 i fig.7.2), vizavi de arborele tubular, este cunoscut n literatura de specialitate sub denumirea de problema lui Pareto. Concluzia acestei probleme este c plecnd de la un punct interior domeniului admisibil al soluiilor, nu putem s mbuntim valoarea unuia dintre criterii, fr s antrenm deteriorarea cel puin a altuia. 7.3 Bazele matematice ale optimizrii multicriteriale

S considerm funcia vector, notat F(X), de k componente, fiecare dintre componente fiind la rndul ei o funcie dependent de vecorul X al variabilelor de decizie:

[ ] ;)(...,),(),()( 21 Tk XfXfXfXF = De asemenea considerm un set de restricii de tip inegalitate, respectiv egalitate, astfel:

.,...,2,1;0)(

;,...,2,1;0)(

pmmmjXhmjXg

j

j

+++===

iar ;],...,,[ 21

TnxxxX =

este un vector din spaiul Rn, indicii m, n, p, k aparinnd mulimii N, a numerelor naturale.

Funciile gj(X) i hj(X) sunt definite pentru toate valorile finite ale variabilelor x1, x2, , xn. Ele delimiteaz spaiul Rn al soluiilor admisibile i fiecare punct X din domeniul admisibil, definete o soluie posibil. Vectorul F(X), notat (7.9), este relaia care asociaz vectorii din Rn fiecrui element X din domeniul admisibil. Cele k componente ale vectorului F(X) reprezint diferitele funcii matematice care

Optimizare multicriterial

129

(7.13)

modeleaz criteriile de optimizare.

Dar a optimiza, n acest caz nu nseamn simplu s spui c este vorba de gsirea unei soluii care minimizeaz (sau maximizeaz) funciile obiectiv, ca i n cazul unei probleme de optimizare monocriteriale. Aici este vorba de a determina cea mai bun soluie din punct de vedere al ansamblului criteriilor, iar pentru aceasta, cel mai important este definirea principiului de optimalitate. Pentru simplificarea expunerii, vom considera c toate funciile obiectiv trebuie minimizate. Nu se va pierde nimic din generalitatea informaiilor fcnd aceast ipotez, pentru c putem transforma foarte simplu orice problem de maximizare ntr-una de minimizare, prin relaia:

)};({min)}({max xfxf =

n general, nu putem obine soluia ideal Xideal, care minimizeaz simultan toate componentele vectorului funcie obiectiv. Trebuie s ne mulumim cu o soluie de compromis, situaie n care cercetarea se va efectua n dou etape.

Etapa I. Determinarea soluiilor nonsuperioare numit i mulimea Pareto optimal.

F(X)

F(Xp)

X

Xp

x1

x2

O O f1

f2

IXI

A

B

min1f

min2f

Fig.7.3 Corespondena ntre mulimea a punctelor X, din domeniul admisibil al soluiilor i respectiv mulimea , a imaginilor acestor puncte prin intermediul funciei vector F.

Optimizare numeric. Algoritmi i programe n C

130

Definiie: Mulimea Pareto-optimal este format din acele soluii fa de care nici o funcie obiectiv nu poate fi mbuntit fr a degrada simultan cel puin o alt funcie obiectiv. n figura 7.3 este reprezentat grafic o problem de optimizare cu dou funcii obiectiv f1(X) i f2(X), n care vectorul variabilelor de decizie depinde de dou variabile, adic X = X(x1,x2). Pentru orice punct X din domeniul admisibil al soluiilor , exist un singur punct f(X) aparinnd mulimii , de coordonate f1(X) i f2(X). Prin urmare, mulimea reprezint imaginea domeniului admisibil al soluiilor , al problemei de optimizare multicriterial, prin intermediul funciei obiectiv vector f(X). Frontiera AB a mulimii , reprezint mulimea Pareto-optimal. Punctele A i B de pe aceast frontier satisfac condiia Af =min1 , respectiv Bf =min2 . Punctul notat cu I din exteriorul domeniului corespunde punctului Xideal, ce optimizeaz simultan ambele componente f1 i f2, ale vectorului funcie obiectiv. Pentru toate valorile X din pentru care avem f2(X) = f2, vom avea f2(XP) = f2(X) i f1(XP) = f1(X), unde XP reprezint o valoare X din , ce are ca imagine un punct din mulimea soluiilor lui Pareto.

Etapa II. Determinarea, pornind de la mulimea soluiilor lui Pareto, a soluiei celei mai favorabile pentru situaia considerat, ceea ce necesit aplicarea unei reguli sigure i n acelai timp potrivite de determinare. 7.4 Metode de optimizare multicriterial

n cadrul metodelor de optimizare multicriterial vom folosi aceleai tehnici de determinare a extremelor unei funcii, tehnici nvate n cadrul capitolelor precedente. Soluionarea acestor tipuri de probleme, cu mai multe funcii obiectiv, dup cum am afirmat-o deja, nu depinde de o metod matematic miraculoas, ci de o alt modalitate de formulare matematic a problemei de optimizare. 7.4.1 Metoda criteriului global

S considerm o problem de optimizare multicriterial n care vectorul funcie obiectiv are k componente fi(X), (i = 1, 2, , k), iar condiiile suplimentare sunt date de m restricii de tip inegalitate gj(X) 0, (j = 1, 2, , m).

Prima etap n rezolvarea acestei probleme const n determinarea soluiei ideale, adic a vectorului fi(Xideal) ce satisface condiiile e minim pentru fiecare dintre funciile obiectiv, luate independent una de cealalt. Cu alte cuvinte,

Optimizare multicriterial

131

(7.14)

(7.15)

(7.16)

(7.17)

O f1

f2

I

A

B

min1f

min2f

E

D (p = 2)C (p = 1)

U(fI)

Fig.7.4 Interpretarea grafic a metodei criteriului global.

rezolvm problema de optimizare monocriterial, pentru fiecare dintre componentele vectorului funcie obiectiv n parte. n aceast situaie, criteriul global se exprim sub forma urmtoare:

( ) ( ) ;11

)(pk

i

pidealii

p XfXfF

= =

Deci, trebuie s determinm vectorul X a crui norm, definit de relaia (7.14) este minim i n acelai timp sunt respectate toate restriciile. Normele cel mai fecvent utilizate sunt:

( ) ( )( ) ( )

( ) ( ) ;,...,2,1

max

;2

;1

)(

21

2

1

)2(

1

)1(

idealii

k

i

idealii

k

i

idealii

XfXfki

Fp

XfXfFp

XfXfFp

=

==

==

==

=

=

n cazul n care vectorul funcie obiectiv are doar dou componente, conform figurii 7.4, utilizarea cazului p = 1 revine la a minimiza suma distanelor dintre valorile fi ale componentelor vectorului funcie obiectiv i valorile lor ideale. Grafic, soluia problemei este reprezentat de punctul C din figura 7.4, dat de dreapta paralel cu a doua bisectoare a axelor de coordonate, tangent la mulime Pareto-optimal.

Utilizarea lui p = 2 se reduce la determinarea celei mai mici distane ntre punctul ideal I i diferitele puncte ale domeniului . Soluia este reprezentat de punctul D din figura 7.4, n care cercul de raz minim, cu centrul n I, este tangent

Optimizare numeric. Algoritmi i programe n C

132

(7.18)

la mulimea Pareto-optimal. n fine, cazul p = se reduce la determinarea punctului din , situat la distana

maxim n raport cu punctul ideal I (punctul A n situaia descris de fig.7.4). Din cele expuse pn aici, putem trage concluzia c soluia optim va depinde n mare msur de alegerea exponentului p din relaia (7.14). Nu se poate da o reet referitoare la alegrea lui p, aceasta depinznd de fiecare caz particular studiat. innd cont c rareori, n practic, toate componentele vectorului funcie obiectiv sunt de aceeai natur dimensional, sau de acelai ordin de mrime, vom defini criteriul global sub forma:

( ) ( )( ) ;1

1

)(pk

i

p

ideali

idealiip

XfXfXfF

=

=

Structura programului de optimizare a unei probleme multicriteriale, exprimat n pseudo-cod este redat mai jos.

// Partea I. Determinarea valorilor ideale pentru fiecare component // a vectorului funcie obiectiv i = 0; while( i < k ) { i = i +1; y(i) = Fi(X); Minimizm Fi(X); ;)()( min* XFiy i= } // Partea II. Determinarea soluiei optime a problemei folosind // relaia (6.18) a metodei criteriului global iniializarea valorii lui p;

;)(

)()(1

1*

* ppk

i

i

iyiyxFy

=

=

Minimizm y;

Optimizare multicriterial

133

(7.19)

(7.20)

(7.21)

(7.22)

(7.23)

7.4.2 Metoda funciilor utilitate Problema multicriterial se poate reduce la o problem monocriterial, prin minimizarea unei funcii utilitate, definit cu ajutorul componentelor vectorului funcie obiectiv. n aceast situaie, problema de optimizare se definete n modul urmtor:

Minimizm: U(f1,f2,,fk); Supus la: gi(X) 0; i = 1, 2, , m.

La prima vedere, aceast metod pare a fi cea mai simpl de aplicat, dar n practic este mai puin pertinent. Aceasta deoarece, ntotdeauna este foarte dificil de definit o funcie utilitate U, care modeleze perfect, din punct de vedere matematic, problema de optimizare multicriterial. Din punct de vedere geometric, soluia problemei o reprezint punctul de contact E, dintre curba funciei utilitate U i mulimea soluiilor lui Pareto (vezi fig.7.4). ntr-un caz particular al acestei metode, numit i metoda parametric, dac gradul de importan al fiecrui criteriu este cunoscut, putem atribui fiecrei componente a vecorului funcie obiectiv o pondere, notat w, 0

Optimizare numeric. Algoritmi i programe n C

134

(7.24)

(7.18), pentru cazul p = 1. 7.4.3 Metoda ordonrii Principiul acestei metode este diferit de cel al metodelor de optimizare multicriterial prezentate pn acum i din acest punct de vedere nu poate fi aplicat dect n anumite situaii particulare. Aceste situaii particulare presupun ca funciile n baza crora este definit vectorul funcie obiectiv, s nu depind de acelai ansamblu de variabile de decizie. Metoda este relativ simpl i presupune n primul rnd ordonarea componentelor vectorului funcie obiectiv, n baza gradului de importan wi al fiecrei componente. Soluia problemei este aceea care minimizeaz componentele vectorului funcie obiectiv, ncepnd cu acea component al crei grad de importan este cel mai ridicat, continund apoi cu celelalte componente ale vectorului funcie obiectiv conform ierarhiei acestora. Dac indicii 1, 2, , k corespund gradelor de importan, conform ierarhiei stabilite, atunci putem ilustra modul de soluionare al problemei n urmtorul mod:

Determinm x1* , ce minimizeaz f1 i atunci f1* = f1(x*);

apoi determinm x1* , ce minimizeaz f2(X) i satisface la f1(X) = f1* pe f2* = f2(x2*)

i aa mai departe, pn la determinarea soluiei unice. Procedura se poate opri nainte de a lua n considerare componentele vectorului funcie obiectiv de rang inferior ca grad de importan. 7.4.4 Metoda nivelelor ideale n multitudinea de situaii practice, se poate ntlni i cazul n care este foarte greu de stabilit o ierarhie a importanei componentelor vectorului funcie obiectiv. Pentru nceput, determinm soluia optim a problemei de optimizare, lund n considerare fiecare component a vectorului funcie obiectiv n parte. Prin urmare vom avea de rezolvat k probleme de optimizare monocriteriale, care vor conduce la k soluii diferite, notate Xkoptim. Deoarece n cazurile reale este aproape imposibil ca toate componentele vectorului funcie obiectiv s-i ating valorile optime simultan n acelai punct, va exista ntotdeauna o diferen ntre acestea, diferen pe care o vom denumi ecart i o vom nota cu Z. Pentru fiecare component vom avea:

( ) ( ) ( ) .,...,2,1; kiXfXZXf optimii == Vor rezulta deci, k ecuaii n care figureaz noua variabil Z(X) numit variabil de ecart. Problema de optimizare se reduce, n acest caz, la minimizarea lui Z(X).

Optimizare multicriterial

135

(7.25)

Aadar, suntem din nou n situaia rezolvrii unei probleme de optimizare monocriteriale. Prin definirea vectorului grad de importan al variabilei de ecart:

( ) ;,...,, 21 Tk = putem enuna problema de optimizare sub forma general:

Determinm X* ce minimizeaz Z(X) unde Fi(X) i Z(X) = Fi(Xoptim); i = 1, 2, , k. supuse la: gj(X) 0; j = 1, 2, , m.

n figura 7.5 este ilustrat aceast metod, pentru cazul n care vectorul funcie obiectiv are dou componente. Vectorul definete direcia vectorului avnd originea n punctul ideal I, iar vrful n punctul M, aparinnd mulimii lui Pareto, reprezentat de arcul AB. Variind raportul 1/ 2, vom descrie ansamblul soluiilor lui Pareto. Pe de alt parte, dac domeniul nu este convex, am putea obine o soluie neconvenabil, care de fapt nu aparine mulimii lui Pareto. Aceast situaie este ilustrat n figura 7.6.

O f1

f2

I

A

B

min1f

min2f

02F

01F

2

1

Fig.7.5 Ilustrarea grafic a metodei nivelelor ideale.

Optimizare numeric. Algoritmi i programe n C

136

(7.26)

(7.27)

n figura 7.6, cazul (b), zona definit de arcul A1B1 nu aparine mulimii Pareto-optimal. 7.4.5 Metoda Mini-Max S considerm problema general de optimizare definit de ecuaiile (7.9) (7.12) i s considerm i = (1, 2, , k) drept mulimea indicilor corespunztori componentelor vectorului funcie obiectiv. Vom admite c pentru fiecare X i toi indicii i, fi(X) > 0 (sau fi(X) < 0). Aceasta nseamn c oricare dintre componentele vectorului funcie obiectiv nu-i schimb semnul sau se anuleaz, ceea ce corespunde situaiilor reale, ntlnite n practic. Considerm vectorul soluie: ( ) ;,...,, )()(2)(1)( Tioptimnioptimioptimioptim xxxX = cu Xoptim(i) , ce minimizeaz funcia obiectiv cu indicele I, adic fi(X) i s notm acest minim cu optimiF . Atunci, pentru orice X , putem exprima valoarea variabilei de ecart corespunztoare diferenei dintre funcia obiectiv cu indicele I i valoarea sa minim sub forma: ( ) ;0)(,)()( = XZcuFFXfXZ ioptimioptimiii

O O f1

f2

I

A

B

min1f

min2f

f2

f1

A

B I

min1f

min2f

a) b)

A1

B1

Fig.7.6 Diferite soluii de optim, relativ la mulimea Pareto optimal.

Optimizare multicriterial

137

(7.28)

(7.29)

(7.30)

(7.31)

(7.32)

(7.33)

Notm cu: ( ) ( ) ( ) ( )( ) ;...,,, 21 Tk XZXZXZXZ =

vectorul ale crui k componente reprezint valorile de ecart relative la X , corespunztoare diferenei dintre valorile celor k funcii obiectiv i valorile lor minime. Plecnd de la aceste considerente, putem exprima principial aceast metod sub urmtoarea form:

Considerm funcia obiectiv ( ) ( ){ };1

max XZki

XV i

=

Problema de optimizare const n determinarea lui Xoptim , ce minimizeaz funcia V(X), astfel nct:

( ) ( ){ } ;1

maxmin

= XZ

kiXXV i

optim

Putem atunci considera c Xoptim este cea mai bun soluie pentru problema de optimizare multicriterial, n situaia n care toate criteriile avute n vedere au acelai grad de importan. ntr-un caz mai general n care se poate atribui un grad de importan i fiecrei funcii Zi, vom avea:

( ) ( ){ };1

max XZki

XV ii

=

n aceast situaie, soluia Xoptim a problemei de optimizare va trebui sa verifice relaia:

( ) ( ){ } ;1

maxmin

= XZkiX

XV iioptim

Aceast metod de determinare a celei mai bune soluii este de fapt, un caz particular al metodei nivelelor ideale. Se poate arta c soluia aparine mulimii Pareto-optimal i atunci vom avea: ( ) ( ) ( );...21 optimkoptimoptim XZXZXZ === Dac avem n vedere o problem de optimizare n care vectorul funcie obiectiv are dou componente f1 i f2, conform figurii 6.7, mulimea soluiilor lui Pareto este

Optimizare numeric. Algoritmi i programe n C

138

( ) ( )( ) ;1111 optimoptim FFXfXZ =( ) ( )( ) ;2222 optimoptim FFXfXZ =

( )( ) ( )( ) ;22112211 optimoptimoptimoptim FFFXfFXf =

reprezentat de arcul AB. Vom avea:

i pentru Z1(X) = Z2(X) vom obine:

( ) ( ) ;2211 optimoptim FXfFXf = Soluia problemei este reprezentat n acest caz de ctre punctul P din figura 7.7. Dac inem cont i de gradul de importan 1 respectiv 2, ale funciilor obiectiv f1 i f2, atunci:

iar soluia este reprezentat de punctul Q din figura 7.7. Fcnd s varieze raportul 1/2, vom descrie mulimea soluiilor lui Pareto.

(7.34)

(7.35)

(7.36)

O f1

f2

I

A

B

min1f

min2f

*2F

*1F

*22

*11

FF

P

Q

Fig.7.7 Interpretarea grafic a metodei MINI-MAX.

(7.37)