Declarația problemei de optimizare "Având în vedere o funcție f (x1, x2, ..., xn), care se numește de obicei țintă. Este necesar să se găsească fie o valoare maximă sau minimă a acestei funcții, sub rezerva anumitor restricții suplimentare. Problemele de căutare max și min sunt ușor de convertit între ele (prin înmulțirea funcției obiectiv cu -1). Restricțiile suplimentare sunt introduse în formă generală, deoarece anumite inegalități neliniare:
restricțiile pot fi reprezentate sub formă de inegalități și sub formă de egalități.
Problema generală de optimizare.
Prin forma funcției obiective și a limitărilor problemei de optimizare, este obișnuit să se împartă în următoarele tipuri.
Dacă funcția obiectivă este liniară și constrângerile sunt și ele liniare, atunci o astfel de problemă se numește o problemă de programare liniară. Problemele LP au fost studiate bine, deci există o metodă de linearizare - transformarea problemelor neliniare într-o formă liniară.
Dacă funcția obiectivă este reprezentată de o formă patratică, atunci problema este numită problema programării patrate. Problemele neliniare conduc adesea la o problemă patratică, deoarece rezolvarea unei probleme patrate este adesea mai ușoară decât o problemă generală.
Teoria programării cubice continuă să se dezvolte. Nu a fost încă dezvoltată pe deplin.
Dacă nu există restricții asupra funcției obiective sau au o formă simplă xia (restricții numai pe o variabilă), atunci o astfel de problemă este numită problema optimizării necondiționate.
Dacă funcția este neliniară și există constrângeri (complexe), atunci problema se referă la optimizarea neliniară.
Dacă există parametri dependenți de timp în problemă, în timp ce ei au un efect semnificativ asupra soluției, atunci la fiecare moment (timpul total este împărțit în mai multe etape), soluția optimă se dovedește a fi diferită, iar soluția optimă finală este suma deciziilor luate în fiecare etapă. Metodele de rezolvare a acestor probleme în mai multe etape se referă la metodele teoriei programării dinamice.
În problema programării liniare (nn), funcția obiectivă poate fi reprezentată ca sumă a produselor variabilelor în anumite constante:
Constrângerile problemei pot fi reprezentate sub formă de egalități și inegalități:
(restricții sub formă de egalități) (restricții sub formă de inegalități)
Setul de xi este numit vectorul necunoscut. Soluția problemei va fi apoi valoarea acestui vector de necunoscute, pentru care funcția f are un maxim sau un minim. Coeficienții ci formează și un vector, numit vectorul de resurse. Elementele lui bi formează un vector cu numele vectorului stocurilor. Pentru confortul soluției, este obișnuită reducerea problemei de la o declarație generală la o formă standard specială.
Cerințe pentru forma standard a problemei:
Parametrii xi trebuie să fie mai mari sau egali cu zero (xi 0). Dacă există o restricție care permite o valoare negativă a lui xi. apoi faceți o schimbare a variabilelor astfel încât noul xi să nu fie negativ.
Restricțiile sub formă de inegalități se transformă în constrângeri sub formă de egalități.
Elementele din dreapta trebuie să fie nonnegative în egalități, adică bi 0.
Articole similare
Trimiteți-le prietenilor: