CURSUL NR. 1.

INTRODUCERE ÎN PROBLEMATICA OPTIMIZĂRII. CLASIFICAREA PROBLEMELOR DE OPTIMIZARE. FORMA STANDARD A UNEI PROBLEME DE OPTIMIZARE.

1. INTRODUCERE

1.1. ASPECTE GENERALE PRIVIND PROBLEMELE DE OPTIMIZARE

În cadrul etapelor de proiectare (design), optimizarea a devenit o componentă necesară, obligatorie, atunci când

se impun cerinţe de performanţă a produsului realizat. Zona problematică nu se reduce doar la inginerie, fiind

cunoscute o serie de aplicaţii economice, de la evaluarea şi optimizarea performanţelor unei investiţii la aplicaţii

bancare ori din sfera asigurărilor. În anii din urmă, când optimizarea profitului a devenit un termen al limbajului

comun, aplicaţiile de optimizare, explicite ori implicite (de exemplu, programele care comanda maşinile

automate de croire/tăiere în industria lemnului ori industria confecţiilor) sunt tot mai prezente. De asemenea,

instrumentele soft-ware de tip MAT-LAB au cunoscut în ultimele versiuni îmbogăţirea semnificativă a

aplicaţiilor utilizabile pentru rezolvarea problemelor de optimizare.

Optimizarea reprezintă în cazul general acţiunea de obţinere a celui mai bun rezultat în anumite

condiţii impuse.

Conform definiţiei, procedeul poate fi aplicat unei extrem de largi varietăţi de probleme. Din domeniul

ingineriei, cele mai importante direcţii care au determinat în timp evoluţia tehnicilor de optimizare, sunt :

- proiectarea aerospaţială (probleme de masa minimă)

- inginerie civilă (dimensionarea structurilor de rezistenţă, dimensionarea grinzilor în structurile metalice,

dimensionarea spaţiilor utile din construcţii)

- proiectarea pieselor mecanice

- proiectarea dispoziţivelor electrotehnice (dimensionarea miezului magnetic, al înfăşurărilor, al

elementelor de răcire, controlul nivelului de vibraţii ori al armonicilor)

- proiectarea echipamentelor energetice şi a reţelelor energetice

- proiectarea unităţilor ori a liniilor de producţie

Din punct de vedere istoric, bazele clasice ale tehnicilor de optimizare, bazate pe operatori derivativi, au

fost puse prin lucrările lui Newton, Filipacci, Euler, dar mai ales prin cercetările lui Cauchy şi Lagrange.

Aceştia din urma au reuşit în sec. 19 să acopere teoretic domeniul clasic al problemelor de optimizare, pentru

funcţii liniare şi neliniare dar şi pentru cazurile aplicaţiilor care suferă restricţii.

Pînă la mijlocul sec.20 progresele în domeniul teoretic şi practice al tehnicilor de optimizare au fost

neînsemnate. Apariţia calculatorului numeric a schimbat fundamental direcţiile cercetării matematice şi a grăbit

în anii ’50 şi ’60 cercetările şcolii engleze de matematică care s-au orientat asupra domeniului algoritmilor

numerici. Al doilea impuls a venit din direcţia care se poate încadra sub numele generic de “inteligenţă

artificială”.

1

Elementele generale ale formulării unei probleme de optimizare presupun cunoaşterea prealabilă a

regulilor de proiectare dintr-un domeniu specific apoi abilitatea de a descrie proiectarea în termeni matematici.

Aceasta presupune:

- designul variabilelor

- designul parametrilor

- designul funcţiilor obiectiv

În cele ce urmează, prin termenul “design” vom desemna operaţiile de proiectare, alegere. Cum

termenul ales are o sferă mai largă în raport cu fiecare operaţie amintită, este potrivit în descrierea etapelor

algoritmilor, tehnicilor de optimizare.

1.2. CLASIFICAREA PROBLEMELOR DE OPTIMIZARE.

Problemele de optimizare pot fi descrise, clasificate în mai multe feluri, în funcţie de diverse moduri de

abordare:

A) pe baza existenţei constrîngerilor: optimizări cu ori făra constrîngeri

-problemele fără constrîngeri prezintă funcţtie obiectiv dar lipsesc constrîngerile aplicate variabilelor.

Ajustarea datelor masurate ori calculate, data fitting, este un domeniu tipic al acestui gen de optimizare.

Funcţia obiectiv trebuie sa fie obligatoriu una neliniară, deoarece minimum unei funcţii liniare fara

constrîngeri este -∞.

B) pe baza naturii variabilelor de design (variabile de proiectare) se definesc

două tipuri importante:

-optimizarea parametrilor (optimizare statică): problema este aflarea valorilor pentru setul de parametrii

de proiectare care formează un set de funcţii prescrise, supuse unor constrîngeri

-optimizarea traiectoriei (optimizare dinamică) : problema este aflarea setului de parametrii de

proiectare, care sunt funcţii continue de alţi parametrii, care minimizează functia obiectiv supusă unui set de

restricţii

C) pe baza structurii fizice a problemei se definesc două grupe:

-control optimal: sunt probleme de programare matematică ce presupune mai multe etape, unde fiecare

etapă este determinată de cea precedentă într-un mod prescriptibil. Sunt descrise de două tipuri de variabile:

cele de stare şi cele de control. Variabilele de control (variabilele de design) trebuiesc determinate aşa încît

să minimizeze toate funcţiile obiectiv (indicele de performanţă) supuse la setul de restrcţii, la nivelul tuturor

etapelor care definesc procesul.

-controlul suboptimal: nu minimizează îtregul set de variabile pe la nivelul tuturor etapelor din proces. De

multe ori ţn problemele practice de inginerie, adoptarea tehnicilor suboptimale poate simplifica remarcabil

soluţia problemei, pătrînd un nivel de performanţă impus iniţial

D) pe baza naturii ecuaţiilor modelului matematic: expresiile matematice ale funcţei obiectiv ori ale

constrîngerilor au permis dezvoltarea mai multor metode de rezolvare specifice claselor de probleme

2

următoare: liniare, neliniare, geometrice ori pătratice (quadratic). Vom reveni în detaliu asupra

specificului fiecărui tip de problemă enunţată în capitolele următoare.

-optimizarea liniară (programarea liniară): cînd funţia obiectiv şi toate constrîngerile sunt de tip liniar.

- optimizarea pătratică (programare pătratică): dacă funţia obiectiv este de tip pătratic iar toate

constrîngerile sunt de tip liniar. Metodele de rezolvare permit extinderea celor elaborate pentru optimizarea

liniară.

- optimizarea neliniară (programarea neliniară): unde una sau mai multe restricţii, constrîngeri sunt de

tip neliniar

E) pe baza valorilor permise variabilelor de design: probleme se împart în doua categorii:

-cu variabile întregi

-cu variabile reale

F) pe baza naturii de tip deterministic a variabilelor:

-deterministe

-stohastice

G) pe baza separabilităţii funcţiilor:

-probleme separabile dacă funcţiile ce descriu problema sunt separabile, adică pot fi descrise ca sumă

de n funcţii de unică variabilă

-probleme inseparabile daca funcţiile modelului matematic nu sunt separabile

H) pe baza numarului funcţiilor obiectiv:

-probleme cu unică funcţie obiectiv

-probleme multiobiectiv

Clasificarea propusă pînă acum este una derivată din aspectele matematice ori fizice ale modelelor pe baza

cărora se obţin soluţiile optimale. Este utilă de amintit şi clasificarea propusă în cadrul toolbox-ului de

optimizare MATLAB, respectiv algoritmi standard de optimizare şi algoritmi de optimizare de dimensiune

mare (large scale).

De asemenea metodele clasice de optimizare pot fi grupate în două categorii principale:

- metode neiterative (într-un singur pas) – utilizează operatori derivative şi folosesc proprietăţile de

derivabilitate, convexitate ale funcţiei obiectiv

- metode iterative – utilizează algoritmi numerici iterativi de aflare a optimului.

Startul metodei îl reprezintă o valoare iniţială aleasă arbitrar din spaţiul de căutare iar ulterior se calculează la

fiecare iteraţie o noua soluţie a problemei. Metodele iterative se împart la rîndul lor în două categorii:

- metode de căutare directă

- metode de gradient (de coborâre) - care reprezintă în prezent cele mai cunoscute şi utilizate metode de

optimizare

3

1.3. FORMA STANDARD A PROBLEMEI DE OPTIMIMIZARE

Exprimarea matematică generală a de optimizare se face astfel:

să se minimizeze: f(X1,X2,…,Xn) (1)

în prezenţa restricţiilor: h1(X1,X2,…,Xn)=0

h2(X1,X2,…,Xn)=0

hl(X1,X2,…,Xn)=0

g1(X1,X2,…,Xn)≤ 0

g2(X1,X2,…,Xn)≤ 0

gm(X1,X2,…,Xn)≤ 0

în condiţiile: xi,min≤ xi≤ xi,max

unde:

f(X1,X2,…,Xn) = funcţia obiectiv (cost) dată că funcţie de n parametrii

xi,min = valoarea minimă admisă pentru parametrul xi

xi,max = valoarea maximă admisă pentru parametrul xi

În cazul problemelor clasice de optimizare, funcţia obiectiv este unică. Se optimizează astfel un singur

aspect, considerat esenţial, al problemei (de exemplu, în cazul proiectării maşinilor electrice se alege drept

funcţie obiectiv doar randamentul). Practica impune însă unui produs ori unei acţiuni umane îndeplinirea

simultană a mai multor indici de calitate, funcţii obiectiv. În exemplul proiectării maşinii electrice, se poate

adaugă şi elementul cost că şi direcţie semnificativă al designului optimal global. Acest tip de proiectare, de

design, se numeşte design multiobiectiv (design multidisciplinar). În mod evident funcţiile obiectiv alese sunt

impuse de cerinţele temei de proiectare şi putem regăsi alături de randament ori preţ şi masă, temperatura

maximă, nivelul de vibraţii, conţinutul de armonici, viteze maxime ş.a.m.d. Conform percepţiei generale, ne

aşteptăm că aceste funcţii obiectiv să fie concurente, contradictorii. Exista totuşi şi situaţii în care ele sunt

obiective cooperante. Din punct de vedere al interesului actual, problemele de optimizare multiobiectiv sunt

cele mai importante, interesul pentru tehnicile şi algoritmii multiobiectiv fiind pe primul loc. În cazul

problemelor multiobiectiv, funcţia f va deveni vectorul f.

Din punct de vedere al formalismului matematic, minimizarea funcţiei obiectiv (a funcţiei cost)

este preferabilă şi are că semnificaţie practică tocmai reducerea efortului, resurselor necesare atingerii unui

anumit obiectiv, scop. În cazul în care funcţia obiectiv impune determinarea maximului (în cazul optimizării

randamentului unui echipament, instalaţii, proces) atunci se poate foarte simplu afla minimul funcţiei obiectiv

negate:

Min f(x)=Max [- f(x)] (2)

4