Problema optimizării în matematică este problema găsirii extremumului (minim sau maxim) al unei funcții reale într-un anumit domeniu. De regulă, considerăm domeniile care aparțin și sunt date de un set de egalități și inegalități.
Programarea matematică este o disciplină matematică care studiază teoria și metodele de rezolvare a problemelor în găsirea extremelor de funcții pe seturi de spațiu vectorial dimensional finit. definite de constrângeri lineare și neliniare (egalități și inegalități).
În procesul de proiectare, este de obicei sarcina de a determina cea mai bună, într-un anumit sens, structura sau valorile parametrilor obiectului. Această problemă se numește optimizare. Dacă optimizarea este asociată cu calculul valorilor optime ale parametrilor pentru o structură obiect dată, atunci se numește parametric. Sarcina de a alege structura optimă este optimizarea structurală.
Declarație de problemă de optimizare
Problema standard de optimizare matematică este formulată în acest fel. Printre elementele χ care formează seturile Χ, găsim un astfel de element χ *. care furnizează valoarea minimă a f (x *) a unei funcții date f (x). Pentru a seta corect problema optimizării, trebuie să specificați:
- Un set admisibil este un set;
- Funcția obiectiv este reprezentată de cartografiere;
- Criteriul de căutare (max sau min).
Rezolvarea problemei înseamnă:
- Arată asta.
- Arată că funcția obiectiv nu este limitată de dedesubt.
- Find.
- Dacă da, găsiți-o.
Dacă funcția minimizată nu este convexă. atunci adesea sunt limitate la găsirea minimelor și a maximelor locale: punctele x0 astfel încât oriunde în unele dintre cartierele lor să fie minim și maxim.
Dacă există un set admisibil. atunci o astfel de problemă se numește problema optimizării necondiționate. în caz contrar, este o problemă de optimizare condiționată.
Clasificarea metodelor de optimizare
Metodele de optimizare sunt clasificate în funcție de sarcinile de optimizare:
- Metode locale: converg la unele extremum local al funcției obiective. În cazul unei funcții obiective unimodale, acest extremum este unic și va fi maximul / minimul global.
- Metode globale: abordarea funcțiilor țintă multi-extrema. Cu o căutare globală, sarcina principală este de a identifica tendințele în comportamentul global al funcției obiective.
Metodele de căutare existente pot fi împărțite în trei grupe mari:
- determinist;
- aleatoare (stochastic);
- combinate.
Prin criteriul dimensiunii unui set admisibil, metodele de optimizare sunt împărțite în metode de optimizare unidimensională și metode de optimizare multidimensională.
Prin forma funcției obiective și setul admisibil, problemele de optimizare și metodele de rezolvare a acestora pot fi împărțite în următoarele clase:
- Problemele de optimizare în care funcția obiectivă și constrângerile sunt funcții liniare sunt rezolvate prin așa-numitele metode de programare liniară.
- În caz contrar, ele se ocupă de problema programării neliniare și aplică metodele adecvate. La rândul lor, se disting două sarcini separate de acestea:
- dacă u sunt funcții convexe, atunci o astfel de problemă este numită problema programării convexe;
- dacă, atunci se ocupă de problema programării întregi (discrete).
Conform cerințelor pentru netezime și prezența derivaților parțiali în funcția obiectivă, ele pot fi, de asemenea, împărțite în:
- Metode directe care necesită doar calcularea funcției obiective în punctele de aproximare;
- metode de primă comandă. necesită calcularea primelor derivate parțiale ale funcției;
- metode de ordinul doi: necesită calcularea al doilea derivat parțial, adică Hessian al funcției obiective.
În plus, metodele de optimizare sunt împărțite în următoarele grupuri:
În funcție de natura setului X, problemele de programare matematică sunt clasificate ca:
Metoda pentru găsirea extremului este complet determinată de clasa problemei. Dar, înainte de a obține un model matematic, trebuie să efectuați 4 etape de modelare:
- Determinarea limitelor sistemului de optimizare
- Respingem acele legături ale obiectului de optimizare cu lumea exterioară, care nu pot afecta foarte mult rezultatul optimizării, dar, mai precis, cele fără care soluția este simplificată
- Selectarea variabilelor gestionate
- "Înghețați" valorile unor variabile (variabile nesupravegheate). Altele ne lasă să luăm orice valoare din domeniul soluțiilor admise (variabile de control)
- Definirea constrângerilor asupra variabilelor gestionate
- ... (egalitate și / sau inegalitate)
- Alegerea unui criteriu numeric de optimizare
- Creați o funcție obiectivă