Tehnici de optimizare

S1. Problematica optimizării: definire, noţiuni fundamentale, etape ale optimizării.

Optimizarea se defineşte în multiple moduri [DEX]:

‐ un raționament sau calcul care permite găsirea valorilor unuia sau mai multor variabile corespunzând maximului sau minimului unei funcții;

‐ un ansamblu de lucrări de cercetare operațională care urmăreşte găsirea celei mai bune soluții pentru rezolvarea unei anumite probleme;

‐ alegerea şi aplicarea soluției (economice) optime (dintre mai multe posibile).

Optimizarea este clasificată ca o ramură:

matematicii aplicate (sau numerice)

cercetării operaționale

proiectării sistemelor asistate de computer în funcție orientarea accentului:

‐ pe aspectele teoretice (condițiile de existență a soluțiilor optime) sau

‐ pe aspectele practice (procedee de atingere a optimelor).

S2. Formularea unei probleme de optimizare (inclusiv explicarea noţiunilor implicate)

O problemă de optimizare se defineşte prin tripletul format din:

necunoscută numită variabilă (sau variabilă de decizie)

un obiectiv

mulțime de restricții.

Funcția obiectiv şi restricțiile sunt funcții de variabile.

Formularea matematică:

minimizează y = f(x) ,

respectând restricțiile:

Unde x∈X,y∈Y.

y se numeşte funcție obiectiv sau funcție cost.

Funcția obiectiv acționează ca un criteriu în raport cu care se face optimizarea.

x se numeşte spațiu de căutare sau spațiul deciziilor sau spațiul variabilelor sau spațiul necunoscutelor.

S3. Caracterizarea problemelor de optimizare - sinteza

Diversele proprietăți matematice specifice ale funcției obiectiv, ale variabilelor, ale restricțiilor şi/sau ale relațiilor funcției obiectiv cu variabilele permit caracterizarea unei probleme de optimizare din multiple perspective, caracterizare care indică de cele mai multe ori abordarea adecvată a problemei în cauză.

Principalele perspective (unghiuri de caracterizare) ale problemelor de optimizare împreună cu tipurile asociate de probleme sunt următoarele, cu precizarea că o problemă de optimizare poate fi (şi de regulă este) caracterizată simultan din mai multe unghiuri.

optimizare matematică / optimizare experimentală

optimizare statică / optimizare dinamică

optimizare parametrică / optimizare de funcționale

optimizare fără restricții / optimizare cu restricții

programare discretă / programare continuă

programare liniară / programare neliniară

programare în numere întregi, programare mixtă

programare convexă / programare neconvexă

programare deterministă / programare stochastică

optimizare uniobiectiv / optimizare multiobiectiv

S4. Optimizare statică / optimizare dinamică, programare deterministă / programare stochastică

Optimizarea este statică (predictivă) dacă optimul este invariant în timp sau staționar. Odată cunoscută poziția şi valoarea optimului, căutarea se opreşte. Dacă valorile variabilelor care influențează obiectivul se modifică în timp şi deplasează optimul, optimizarea este catalogată drept dinamică (reactivă). Scopul optimizării dinamice este menținerea unei condiții optime în ciuda condițiilor variabile ale mediului. Căutarea devine astfel un proces continuu.

Optimizarea dinamică are în vedere sistemele sau reprezentările lor matematice în care se operează pe faze sau secvențe. Se bazează pe teorema de optimalitate enunțată de Bellman. Dacă starea la un anumit pas depinde numai de decizia la acel pas şi de starea anterioară (deci nu

există feedback) se poate aplica programarea dinamică.

Programare deterministă /programare stochastică

Modelul de programare deterministă este specificat în întregime, adică toate datele necesare sunt cunoscute a priori.

Problemele din lumea reală sunt însă adesea afectate de incertitudine, din cauza:

‐ indisponibilității datelor (din cauza ex., a costului prea mare al obținerii datelor)

‐ erorilor de citire a datelor de intrare

‐ riscului prezent în dinamica fenomenelor

‐ erorilor de modelare a incertitudinii.

Programarea stocastică studiază cazurile în care parametrii (în totalitate sau parțial) sau restricțiile sau funcția obiectiv depind de variabile aleatoare (Faber, 1970). Scopul este de a găsi politici fezabile pentru (aproape) toate instanțele posibile de date şi care mimizează media unei funcții cu variabile de decizie şi variabile aleatoare.

S5. Optimizare cu restricţii / optimizare fără restricţii,programare discretă / programare continuă

Dacă nu se impun nici un fel de restricții asupra variabilelor, atunci optimizarea se numeşte fără restricții.

Optimizarea cu restricții. Restricțiile pot fi de tip egalitate sau de tip inegalitate, definite pe domeniu finit sau infinit.

Programare discretă / programare continuă

Programarea discretă tratează problemele pentru care spațiul de căutare este finit sau numărabil. Cu alte cuvinte, soluțiile admisibile sunt discrete sau pot fi reduse la soluții discrete. O variabilă este discretă atunci când este definită numai pentru anumite valori numerice, care nu sunt infinit vecine.

Dacă mulțimea variabilelor este nenumărabilă infinită, atunci optimizarea se numeşte programare continuă. În acest caz, optimizarea este de regulă mai facilă, deoarece putem folosi informații din valorile funcției obiectiv şi restricții