FORMULAREA MATEMATICĂ
A PROBLEMELOR DE OPTIMIZARE
1. Terminologie
1.1 Funcţii criteriu şi restricţii
Optimizarea include :
- alegerea unui criteriu de optimizare
- stabilirea restricţiilor de tip egalitate şi inegalitate
- determinarea valorilor optime ale variabilelor
(care intervin în expresia criteriului
şi în expresiile restricţiilor),
aceste valori asigurând un extrem
(maxim sau minim, după caz),
al criteriului de optimizare.
Notând variabilele care intervin
în expresiile criteriului şi restricţiilor prin
x1, x2, … , xn,
criteriul de optimizare poate fi notat prin funcţia
f = f(x1, x2, … , xn)
numită funcţie criteriu,
funcţie obiectiv,
indice de performanţă,
funcţie de cost,
funcţie de optimizare,
funcţie scop, etc
RESTRICŢIILE DE TIP EGALITATE
pot fi exprimate prin relaţii de forma
hi(x1, x2, … , xn)= 0 , cu i = 1, 2, … , m
(presupunând că sunt impuse mrestricţii de acest tip)
Mai sunt denumite şi restricţii active
RESTRICŢIILE DE TIP INEGALITATE
pot fi exprimate prin relaţii de forma generală
lj≤ gj(x1, x2, … , xn) ≤ Ljcu j = 1, 2, … , r,
(presupunând că intervin rrestricţii de acest tip),
unde ljşi Ljsunt limita inferioară admisă
şi limita superioară admisă
Mai sunt denumite şi restricţii inactive,
iar expresiile care le descriu sunt denumite ecuaţii limită
În unele cazuri, se impune o singură limită,
iar uneori aceasta poate fi nulă,
rezultând restricţii de forma
gi(x1, x2, … , xn)≥ 0
sau de forma
gi(x1, x2, … , xn)≤0
Numărul m al restricţiilor egalitate
trebuie să fie mai mic decât numărul n al variabilelor,
deci este necesară o relaţie de forma
m < n
În cazul restricţiilor de tip inegalitate
NU intervind condiţii de acest tip,
întrucât aceste restricţii delimitează şi
numărul lor poate fi mai mare decât numărul variabilelor
1.2 Mulţimi convexe şi neconvexe
O mulţime este convexă dacă unind printr-o dreaptă
oricare pereche de puncte ale mulţimii,
segmental de dreaptă aparţine în întregime mulţimii respective;
în caz contrar, mulţimea este neconvexă
Pentru x3oarecare de pe segmental respectiv
x1≤ x2≤ x3
x2= λx1+ (1-λ)x3
în care valorile scalarului λ satisfac condiţia
0 ≤ λ ≤ 1
Mulţimi neconvexe
intersecţia unui număr finit de mulţimi convexe este şi ea convexă
1.3 Funcţii convexe şi concave
Funcţia f(x) este convexă
pentru că satisface condiţia că segmentul de dreaptă
care uneşte punctele f(x1) şi f(x2)
se găseşte deasupra graficului funcţiei
Segmetul axei absciselor dintre x1 şi x2 satisface relaţia
x = λx1+ (1 – λ)x2cu 0 ≤ λ≤ 1
În consecinţă, porţiunea funcţiei f(x) dintre f(x1)şi f(x2)
este definită de relaţia
f(x) = f [λx1+ (1 – λ)x2]
Segmentul de dreaptă care uneşte punctele f(x1)şi f(x2)
este definit prin relaţia
λf(x1) + (1 – λ)f(x2)cu 0 ≤ λ≤ 1
Condiţia ca segmentul să nu se găsească sub graphic
se exprimă deci prin relaţia
f [λx1+ (1 – λ)x2] ≤ λf(x1) + (1 – λ)f(x2)
O funcţie este concavă dacă segmentul menţionat
nu se găseşte nicăieri deasupra graficului funcţiei
Condiţia de concavitate a unei funcţii se exprimă prin relaţia
f [λx1+ (1 – λ)x2] ≥ λf(x1) + (1 – λ)f(x2)
Unele funcţii nu sunt nici concave, nici convexe
2. Formularea optimizării prin intermediul spaţiilor vectoriale
Într-un spaţiu real cu ndmensiuni Rn,
fiecare punct este definit de ncoordonate,
respectiv de vectori n-dimensionali :
nn y
y
y
y
x
x
x
x
2
1
2
1
Un spaţiu vectorial S este linear dacă pentru
SySx ,
combinaţia lineară
Sbyax )(
aşi bfiind constante scalare
Un spaţiu este complet
dacă orice şir Cauchy format cu elemente ale spaţiului
are limita şirului în spaţiul respectiv
Un spaţiu are un produs scalar
dacă în spaţiul respectiv este definită o operaţie
care atribuie un număr real
fiecărei perechi de elemente ale spaţiului
1
2
1 2 1 1 2 2 1
n
Tn n n i i
i
n
y
y
x x x x y x y x y x y
y
xy
Produsul scalar a doi vectori,
denumit şi produs intern,
se notează prin
<x, y>
1 1 1 1 2 1
2 2 1 2 2 2
12
12
n
n
Tn
n n n n n
x x y x y x y
x x y x y x y
y y y
x x y x y x y
xy
Produsul
se numeşte produs extern (sau produs dyadic)
şi se notează prin
> x, y <
Un spaţiu Hilbert
este un spaţiu linear, complet şi având un produs scalar
Dacă variabilele x1, x2, … , xn
din funcţia criteriu sunt coordonatele unui vextor x în
n
optimizarea constă în agăsi acel vector x*pentru care funcţia are
un minim, deci pentru care rezultă
)()( *xx ff
pentru orice x din vecinătatea lui x*
Se construieşte o secvenţă (şir) de vectori x0, x1, x2, …
astfel încât să se obţină
)()( 1ii ff xx
i
i
ii pxx
1
αi–scalar - asigură pasul căutării
pi-vector din acelaşi spaţiu cu xi
determină direcţia căutării optimului
Avantajele utilizării spaţiilor Hilbert pentru optimizare :
1. spaţiul Hilbert fiind linear, xi+1 va fi un element al spaţiului,
deoarece reprezintă o combinaţie lineară a vectorilor xişi pi
2. spaţiul Hilbert fiind complet, limita şirului de vectori
construit se va găsi în spaţiul rspectiv
3. faptul că spaţiul Hilbert este definit ca un produs scalar
ajută la determinarea vectorului pi
care asigură direcţia căutării optimului.
Produsul scalar permite definirea conceptului de ortogonalitate
doi vectori sunt ortogonali, dacă produsul lor scalar este nul,
deci dacă este îndeplinită condiţia
< x, y> = 0
Produsul scalar permite şi definirea unei norme,
respectiv a unei măsuri a lungimii unui element al spaţiului,
introducând astfel o metrică a spaţiului
şi oţinându-se un spaţiu metric
, x x x
n
ii
x
1
2
x
AUTOMATIZARE ŞI OPTIMIZARE
1. OPTIMIZǍRI STAŢIONARE
Exemplu: o instalaţie tehnologicǎ din industria chimicǎ
-R –reactorul
-S -schimbǎtorul de cǎldurǎ
-D –decantorul
-C-coloană de distilare
-PA-paleta de amestecare
-Aşi B– reactanţii - cu debitele QAşi QB
-debitul - fracţiunea recirculatǎ prin reactor
din debitul total QPB de produs de bazǎ al coloanei
-debitul - restul produsului de bazǎ,
folosit în calitate de combustibil
1
PB
Q
2
PB
Q
Din reactorul R, în care temperatura are valoarea T,
se obţine debitul total QR,
care însumeazǎ debitele a 6 componente rezultate din reacţie :
-debitele QRA şi QRB
corespunzǎtoare cantitǎţilor din reactanţii Aşi B
care nu au participat la reacţie
-debitele QRE şi QRF ale produselor secundare Eşi F
obţinute din reacţie
-debitul QRG de produs secundar greu, uleios, G, obţinut din reacţie
- debitul QRP de produs principal
Debitul total QRde ieşire din reactor
intrǎ în schimbǎtorul de caldurǎ S
(în care are loc un proces de rǎcire
datoritǎ fluidului de rǎcire FR)
trecând apoi în decantorul D,
care separǎ produsul greu G,
la baza decantorului rezultând debitul QRG;
produsul greu Gnu poate fi utilizat
şi, în plus, necesitǎ o anumitǎ tratare,
deci implicǎ o anumitǎ cheltuialǎ,
înainte de a fi evacuate ca reziduu,
evitându-se astfel efectele de poluare
provocate de produsul respectiv
Produsele intermediare Eşi F
pot fi folosite numai în calitate de combustibili
şi au, deci, o valoare utilǎ corespunzǎtore;
folosirea debitului (o parte din debitul QPB
de produs de bazǎ al coloanei C)
în calitate de combustibil este posibilǎ
datoritǎ acestei proprietǎţi utile
a produselor intermediare Eşi F
1
PB
Q
Dupǎ separarea produsului greu G, în decantor,
restul componentelor debitului QRintrǎ în coloana C,
din care se obţine la vârf produsul principal P,
(cu debitul QP ),
iar la bazǎ rezultǎ debitul de produs de bazǎ PB,
(cu debitul QPB ),
împǎrţit în debitul de combustibil
şi debitul de recirculare în reactor
Funcţionarea instalaţiei tehnologice
este caracterizatǎ de 12 mǎrimi :
debitele QA, QB, QR, QRA, QRB, QRE, QRF,
QRG, QRP, QP , , şi temperatura Tdin reactor
mǎrimi ce intervin
atât în expresia criteriului de optimizare,
cât şi în expresiile restricţiilor
Optimizarea staţionarǎ are ca obiectiv
sǎ determine pentru instalaţia tehnologicǎ
acel regim de funcţionare de lungǎ duratǎ
(acele valori staţionare optime
ale mǎrimilor caracterizând funcţionarea instalaţiei)
care sǎ asigure maximizarea
ratei anuale de recuperare a investiţiilor
1
PB
Q
2
PB
Q
Expresia criteriului de optimizare
(a ratei anuale de recuperare a investiţiilor)
se obţine în funcţie de unele dintre aceste 12 mǎrimi
Prin intermediul diferitelor grupe de mǎrimi
se obţin expresiile restricţiilor de tip egalitate (9 restricţii)
şi ale restricţiilor de tip inegalitate (14 restricţii)
Restricţiile de tip egalitate
rezultǎ scriind ecuaţiile bilanţurilor de material pe ansamblu
şi pentru fiecare componentǎ
De exemplu, pentru ansambul instalaţiei tehnologice
rezultǎ relaţia de egalitate a debitelor de intrare şi de ieşire
1
PBPRGBA QQQQQ
Optimizarea staţionarǎ
îşi propune ca obiectiv
determinarea valorilor staţionare optime ale unor mǎrimi,
care vor fi menţinute timp îndelungat
pentru obţinerea unui maxim al criteriului,
reprezentat de rata anualǎ de recuperare a investiţiilor,
criteriul însuşi fiind formulat
prin intermediul unui interval mare de timp
Menţinerea anumitor mǎrimi la valorile optime stabilite
se va face prin intermediul unor bucle locale
de reglare automatǎ
în care vor interveni regimuri tranzitorii,
eventuala optimizare a acestor regimuri
formeazǎ obiectul unei alte clase de probleme :
problemele de optimizare dinamicǎ
2. OPTIMIZǍRI DINAMICE
Exemplu: cazul cel mai simplu,
al unui sistem de reglare automatǎ în funcţie de ieşire,
monovariabil (cu o singurǎ mǎrime de referinţǎ w
şi o singurǎ mǎrime reglatǎ), liniar şi continuu
-RA - este regulatorul automat
-EE – elementul de execuţie
-IT – instalaţia tehnologicǎ
-Tr –traductorul
-p1, p2, …, pk – perturbǎrile
care acţioneazǎ asupra instalaţiei tehnologice
Grupând elementele EE, IT şi Tr într-un singur bloc echivalent F,
rezultǎ pentru schema de elemente aspectul
-Feste blocul echivalent al pǎrţii fixate a sistemului
-ε–eroarea
-u– mǎrimea de comandǎ
-y– mǎrimea reglatǎ, respectiv mǎrimea de ieşire a sistemului
Regimul tranzitoriu al mǎrmii reglate y,
provocat de o variaţie treaptǎ unitarǎ a mǎrimii de referinţǎ w
În cazul rǎspunsului la variaţia treaptǎ unitarǎ pozitivǎ
a mǎrimii de referinţǎ w
0
I dt
2
1
0
J dt
0
2
2dtuJ
0
22
213 )( dtuJJJ
Polioptimizare
dtdtdtJ)( 2
2
2
1
0 0 0
2
2
2
14
u)f(x,x
.
x
u
Criteriile integrale pǎtratice
se formuleazǎ şi în limbajul intrare-stare-ieşire,
care descrie funcţionarea sistemului
prin intermediul ecuaţiilor de stare
vectorul stǎrilor
(de regulǎ) vectorul comenzilor,
dar se poate defini şi un set de parametri.
0
5)( dtJRuuQxxTT
0
6)( dtJeRuuyQy TT
x, u, y-vectrii stǎrilor, comenzilor şi mǎrimilor de ieşire (reglate)
Q, Qe, R–matrice de ponderare
FOLOSIREA METODELOR DE DESCOMPUNERE
(DECOMPOZIŢIE)
În ultima vreme a cǎpǎtat o extindere din ce în ce mai
largǎ otehnicǎ de optimizare bazatǎ pe descompunerea
unor probleme de optimizare pentru instalaţii sau sisteme
cu structuri mari şi de complexitate ridicatǎ în probleme de
optimizare ale unor subansambe (subsisteme) mai simple
ale instalaţiilor respective; aceastǎ tehnicǎ este numitǎ
“tehnicǎ de descompunere” sau “tehnicǎ de decompoziţie”
O asemenea descompunere poate prezenta avantaje
importante pentru obţinerea soluţiilor optimizǎrii, întrucât
problemele de optim ale subsistemelor se rezolvǎ mai uşor,
datoritǎ numǎrului redus de variabile care intervin în
fiecare subsistem; pentru obţinerea unui optim pe
ansamblu, pe lângǎ optimizarea funcţionǎrii fiecǎrui
subsistem este necesarǎ şi oacţiune de coordonare centralǎ,
pentru compensarea legǎturilor de interacţiune dintre
subsisteme
Se obţine astfel o structurǎ ierahizatǎ, cu douǎ sau mai
multe nivele; în cazul a douǎ nivele, menţionat anterior, la
nivelul inferior are loc optimizarea funcţionǎrii fiecǎrui
subsistem, iar la nivelul superior se efectueazǎ acţiunea de
coordonare pentru obţinerea optimului de ansamblu
Considerentele referitoare la ierahizarea pe douǎ nivele se
pot generaliza uşor pentru cazul mai multor nivele
Structura unui sistem multinivel cu douǎ nivele este
reprezentatǎ în figura de mai jos
La nivelul inferior se gǎsesc subsistemele 1, 2, 3,
care asigurǎ optime locale,
de exemplu prin maximizarea unor criterii I1, I2, I3,
iar nivelul superior este constituit de coordonatorul 4,
care asigurǎ un opitim global
(schimbând informaţii în ambele sensuri cu subsistemele 1, 2, 3,
informaţii reprezentate simbolic prin sǎgeţi)
de exemplu prin minimizarea unui criteriu I4
Exemplu
Cele douǎ subsisteme formate, subsistemul 1şi subsistemul 2,
sunt legate prin douǎ mǎrimi :
debitul de intrare în coloana C, notat cu
la ieşirea din subsistemul 1
la intrarea în subsistemul 2
fracţiunea recirculatǎ din produsul de bazǎ, notata cu
la ieşirea din subsistemul 2
la intrarea în subsistemul 1
C
Q
^
C
Q
2
PB
Q
2
^
PB
Q
La restricţiile anterioare de tip egalitate se adaugǎ alte restricţii.
Una dintre ele rezultǎ din ecuaţia bilanţului de material
pentru debitul care iese din subsistemul 1:
QC = QR –QRG
aceastǎ ecuaţie conducînd la restricţia
QR –QRG –QC = 0
Alte douǎ restricţii de tip egalitate
rezultǎ din necesitatea egalitǎţii debitelor
de ieşire din unul dintre subsisteme
şi de intrare în celǎlalt
C
CQQ
^
2
22
^
PB
PB QQ
0
^ C
CQQ
^0
22 PBPB QQ
21
^
PBPBP
CQQQQ
0
^
21 C
PBPBPQQQQ
Pentru subsistemul 2rezultǎ osingurǎ ecuaţie de bilanţ de material :
din aceasta obţinându-se restricţia
STRUCTURA MULTISTRAT
realizeazǎ, de asemenea, o ierarhizare,
şi anume pe “straturi”, sau “algoritmi”,
la diversele straturi intervenind algoritmi cu scopuri diferite
Stratul 1
conţine algoritmii de reglare automatǎ
şi acţioneazǎ în permanenţǎ pentru ca valorile mǎrimilor reglate,
constituind vectorul y,
sǎ urmǎreascǎ valorile prescrise prin mǎrimile de referinţǎ,
constituind vectorul w;
stratul 1transmite elementelor de execuţie din blocul F
vectorul mǎrimilor de comandǎ c
Asupra blocului Facţioneazǎ şi vectorul perturbǎrilor p
Stratul 2
include un algoritm de optimizare, care,
pe baza informaţiilor y şi x
(primite de la blocul F) şi a informaţiilor n
(primite de la mediul înconjurǎtor)
elaboreazǎ valorile optime prescise
pemtru mǎrimile reglate y,
transmiţând stratului 1aceste valori
sub forma vectorului mǎrimilor de referinţǎ w
valorile optime sunt calculate
de algoritmul de optimizare
în ipoteza cǎ parametrii instalaţiei tehologice
(factori de amplificare, constante de timp, timp mort,
constituind un vector α)
nu suferǎ variaţii în timp
stratul 3
realizeazǎ un algoritm de adaptare
Pe baza informaţiilor x, y şi z,
primite de la blocul F,
şi a informaţiilor q primite de la mediul înconjurǎtor,
algoritmul 3 determinǎ valorile parametrilor α
şi le transmite stratului 2,
pentru ca algoritmul de optimizare din acest strat
sǎ ia în considerare valorile respective,
uneori fiind modificatǎ în mod corespunzǎtor
structura acestui algoritm
Stratul 3asigurǎ astfel o actualizare
a valorilor parametrilor modelului matematic
al instalaţiei tehnologice
Pe lângǎ cele trei straturi menţionate, poate exista
şi un al patrulea strat, cu algoritm de auto-organizare,
care, în funcţie de anumiţi factori exteriori –de
exemplu factori economici –poate asigura eventuale
modificǎri ale structurii sistemului ierarhizat
În sistemele cu structurǎ multistrat, fiecare strat
intervine la intervale de timp diferite, intervalele fiind cu
atât mai mari cu cât stratul are o poziţie mai înaltǎ
De asemenea, fiecare strat foloseşte un grad de
simplificare diferit pentru modelul instalaţiei tehnologice,
modelul fiind cu atât mai simplificat şi mai abstractizat –
prin evitarea considerǎrii unor detalii –cu cât poziţia
stratului este mai înaltǎ
În unele cazuri, structura multistrat are un aspect
preponderent temporal
Astfel, de exemplu, în cazul optimizǎrii utilizǎrii resurselor
de apǎ, stratul superior determinǎ soluţia pe termen lung, de un
an, folosind un model simplificat, în care toate rezervoarele mai
puţin importante sunt înlocuite printr-un rezervor echivalent
Pe baza calculelor de optimizare din stratul superior, se
transmite stratului mijlociu o soluţie, care nu este însǎ detailatǎ,
întrucât rezervoarele de dimensiuni medii şi mici nu au fost
considerate la volumele lor reale
Stratul mijlociu calculeazǎ mai precis soluţia de
optimizare pe termen de olunǎ, considerând datele
exacte ale rezervoarelor medii şi înlocuind toate
rezervoarele mici printr-un rezervor echivalent,
rezultatul optimizǎrii pentru sfârşitul primei zi a lunii
fiind transmis stratului inferior
În cadrul stratului inferior se calculeazǎ soluţia
detailatǎ pe termen de ozi – ţinând seama de
dimensiunile reale ale rezervoarelor mici –şi se asigurǎ
realizarea acestei soluţii prin intermediul
echipamentelor de reglare automatǎ ale instalaţiilor de
distribuţie a apei.
Pe mǎsura realizǎrii soluţiilor calculate (deci dupǎ fiecare
zi, respectiv dupǎ fiecare lunǎ) se transmit semnale de reacţie
de la stratul inferior la cel mediu şi de la cel mediu la cel
superior, aceste informaţii fiind utilizate ca valori iniţiale – de
cǎtre straturile care le primesc –pentru recalcularea soluţiilor
optime pe intervalele aferente, de olunǎ şi respectiv un an
Descompuneri de tip temporal intervin şi în cadrul
metodelor de optimizare bazate pe principiul maximului
discret şi pe programarea dinamicǎ
