Optimizare
Optimizarea reprezintă activitatea de selectare, din mulțimea soluțiilor posibile unei probleme, a acelei soluții care este cea mai avantajoasă în raport cu un criteriu predefinit. Această definiție implică existența următoarelor componente:
- O problemă constând în găsirea unei soluții printr-un procedeu matematic;
- Existența mai multor soluții pentru aceeași problemă;
- Un criteriu de selectare a soluției optime.
Funcția obiectiv reprezintă expresia matematică a criteriului de optimizare. Aceasta trebuie să reflecte eficiența economică a procesului și în același timp să răspundă obiectivelor funcționării oricărui proces industrial: siguranța în exploatare și respectarea condițiilor de calitate.
Problema de optimizare reprezintă o aplicație matematică de selectare a unei soluții, dintr-o mulțime posibilă, pe baza evaluării funcției obiectiv. Foarte multe probleme din domeniile matematicii, statisticii, ingineriei, economiei și științelor aplicate se pot formula ca probleme de optimizare.
În matematică, termenul de optimizare se referă la studiul problemelor care sunt de forma
- Se dă: o funcție pentru o mulțime de numere reale
- Se cere: un element pentru care ("minimizare"), sau ("maximizare").
O asemenea formulare este câteodată numită program matematic (un termen care nu are legătură directă cu programarea calculatoarelor, dar încă se mai folosește în programarea liniară). Multe probleme din lumea reală cât și probleme teoretice, pot fi modele pentru această ramură a matematicii.
Tipic, este o submulțime a spațiului euclidian , des specificat ca un set de limitări de posibilități, egalități sau inegalități pe care membrii lui trebuie să le satisfacă. Elementele lui se numesc soluții admisibile. Funcția se numește funcție obiectiv, sau funcție cost. O soluție admisibilă care minimizează (sau maximizează, dacă acesta este scopul) funcția obiectiv se numește soluție optimă.
În general, există mai multe puncte de minim sau maxim local, unde minimul local este definit ca fiind un punct pentru care câțiva și toți x astfel încât
formula
se verifică; aceasta înseamnă că, în anumite bile ale lui toate valorile funcțiilor sunt mai mari sau egale decât valoarea în acel punct. Maximul local se definește similar. În general, minimul local este simplu de găsit — informații adiționale despre problemă (spre exemplu, funcția este convexă) sunt necesare pentru a fi siguri că soluția problemei este minimul global.
Notații
[modificare | modificare sursă]Problemele de optimizare sunt deseori exprimate prin notații speciale. Iată câteva exemple:
Această problemă cere minimul expresiei algebrice . În acest caz, valoarea minimului este 1, pentru .
Aici se cere maximul pentru . În acest caz nu există un maxim deoarece funcția este nemărginită, soluția problemei fiind "infinit" sau "nedefinită".
Aici se cere valoarea (sau valorile) lui pentru care se minimizează expresia . (Valoarea minimul nu contează.) În acest caz, soluția este .
Aici se cer perechile de forma care maximizează valoarea expresiei , cu condiția că . (Aici iarăși, valoarea maximă nu contează.) În acest caz soluțiile sunt perechi de forma și , unde .
Subcategorii majore
[modificare | modificare sursă]- Programarea liniară studiază cazurile în care funcția obiectiv f este liniară și mulțimea A este specificată folosind doar egalități sau inegalități liniare.
- Programarea quadrică permite funcției obiectiv să aibă termeni quadrici, iar mulțimea A trebuie să fie specificată doar prin egalități sau inegalități liniare.
- Programarea neliniară studiază cazurile când funcția obiectiv sau condițiile impuse de problemă sunt specificate prin egalități sau inegalități neliniare
- Teoria stocurilor studiază cazurile în care condițiile impuse de problemă depind de variabile aleatoare.
- Programarea dinamică studiază cazurile în care strategia de optimizare se bazează pe împărțirea problemei în probleme mai simple.
- Optimizarea combinatorică se ocupă cu problemele ale căror soluții admisibile sunt discrete sau pot fi reduse la soluții discrete.
- Optimizarea infinit-dimensională studiază cazurile în care o mulțime de soluții admisibile este o submulțime a unui spațiu infinit dimensional, precum un spațiu de funcții.
Tehnici
[modificare | modificare sursă]Pentru funcțiile dublu diferențiabile, problemele fără limitări de posibilități se pot rezolva găsind punctele în care panta funcției obiectiv este 0 (acestea sunt punctele staționare) și folosind matricea Hessiană pentru a clasifica tipul fiecărui punct. Dacă este pozitiv definită, punctul este un minim local, dacă este negativă, un maxim local, iar dacă este nedefinită, un punct de șa.
Se poate găsi acel punct staționar pornind de la o bănuială despre el, apoi ajungând la el printr-una din metodele:
- descreșterea pantei
- metoda lui Newton
- conjugatul pantei
- căutarea liniară
Dacă funcția este convexă în regiunea de interes, atunci orice minim local este și global. Există metode rapide pentru optmizarea funcțiilor dublu diferențiabile convexe.
Problemele cu limitări de situații pot fi transformate în probleme fără limitări cu ajutorul multiplicatorilor lui Lagrange.
Iată câteva metode populare:
- algoritmi genetici
- strategie de evoluție
- evoluție diferențială
Utilizări
[modificare | modificare sursă]Problemele de dinamică a corpurilor rigide (în particular cele articulate) necesită de multe ori tehnici matematice de programare, din moment ce un dinamica corpurile rigide poate fi văzută ca o rezolvare a unei ecuații diferențiale simple cu multiple limitări de situații; constrângerile sunt constrângeri geometrice neliniare precum "aceste două puncte trebuie să coincidă", "această suprafață nu trebuie să se interpenetreze cu alta", sau "acest punct trebuie să se plimbe pe o curbă". De asemenea, la calculul forțelor de contact se poate rezolva numai rezolvând o problemă de complementaritate liniară, care poate fi văzută ca o QP (problemă "quadratic programming").
Multe probleme de proiectare pot fi exprimate ca programe de optimizare. Aceste probleme se numesc probleme de optimizare a designului. O dezvoltare recentă a unei categorii a acesteia sunt problemele de optimizare a designului multidisciplinar, care, deși sunt folositoare în multe probleme simple, au fost aplicate și în problemele de inginerie aerospațială.
Altă categorie care folosește foarte mult optimizarea este reprezentată de cercetările operaționale.
Istoric
[modificare | modificare sursă]Istoric vorbind, primul termen introdus a fost programarea liniară, care a fost inventat de George Dantzig în anii 1940. În acest context, termenul de programare nu se referă la programarea calculatoarelor (deși astăzi calculatoarele sunt folosind în multe cazuri pentru a rezolva probleme matematice). Termenul vine de la folosirea cuvântului program de către armata S.U.A. pentru a face referire la orarul de pregătire și logistică, exact ceea ce Dantzig studia la acea vreme. Mai târziu, termenu de "programare" a devenit important, primind fonduri guvernamentale, fiind asociat cu ariile de înaltă tehnologie, care erau foarte importante.
Vezi și
[modificare | modificare sursă]- argmax
- teoria jocurilor
- cercetări operaționale
- logica fuzzy
- optimizare aleatoare
- inegalități variaționale
- algoritmul simplex
- metoda punctelor interioare
- problema comis-voiajorului
- publicații importante în optimizare
Referințe
[modificare | modificare sursă]- Stephen Boyd and Lieven Vandenberghe (2004). Convex Optimization, Cambridge University Press. ISBN 0-521-83378-7.
Legături externe
[modificare | modificare sursă]Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.