Metoda de prezentare
Obiectivul principal al metodei funcție de penalizare este de a transforma problema de minimizare a funcției
cu restricțiile corespunzătoare introduse pe x, în sarcina de a găsi minim fără funcție de limitare
Funcția este o pedeapsă. Este esențial ca, în caz de încălcare a restricțiilor ea „amendat» funcția Z, adică, a crescut znachenie.V de acest caz, minimul Z va fi amplasat în zona de restricții. Funcția îndeplinește această condiție nu poate fi singurul. problema Minimalizarea poate fi formulată după cum urmează:
sub constrângeri 0, j = 1,2, \ dots, m "/> 0, j = 1,2, \ dots, m" />.
Funcția poate fi în mod convenabil în scris, după cum urmează:
în care r - valoare pozitivă.
Apoi, funcția ia forma
Dacă x este valoarea admisibilă, adică valoare, pentru care Z preia valorile care sunt valorile corespunzătoare (adevărat funcționale țintă a problemei), iar diferența poate fi redusă din cauza faptului că r poate fi foarte mică. Dar dacă x ia valori pe care, cu toate că acestea sunt acceptabile, dar aproape de limitele de frontieră și funcția de cel puțin unul este aproape de zero, atunci valorile funcției, și valorile astfel de Z vor deveni foarte mari. Astfel, funcția de efect este de a crea o „creasta cu margini abrupte“ de-a lungul fiecare limita de limitări. Prin urmare, în cazul în care căutarea va începe de la un punct fezabil și căutările pentru funcția minimă fără constrângeri, cel puțin, desigur, va fi realizat în zona permisă pentru obiective limitate. Presupunând o suficient de mică valoare a lui r, pentru a efectua a fost mică la punctul minim, putem face o funcție minimă punct, fără a se limita la care coincide cu punctul de problemă minim cu constrângeri.
Metoda funcție de penalizare algoritm
Să presupunem că avem următoarea problemă: Minimizarea sub constrângeri „/>.
Etapa inițială Selectați 0 "/> 0" /> ca o oprire constantă, inițial punct ∈ fezabil, pentru care 0 "/> 0" /> "/>, scalar și 0" /> - acest parametru, ale cărui valori scad cu fiecare iterație; - greutăți pozitive.
Exemple de funcții de penalizare sunt:
1) funcția inversă „/>
2) o funcție logaritmică
Pune „/> la soluția optimă a problemei de minimizare și du-te la al doilea pas.
Minimalizarea funcție de penalizare poate fi realizată prin orice optimizare neconstrâns metodă, de exemplu, un gradient.
În cazul în care, apoi se opri. Soluția este solicitată.
În caz contrar, pus = \ beta „/>. Schimbarea și du-te la primul pas (k + 1) iterație.
Metoda funcțiilor barieră
Metoda de prezentare
Funcția penalizare Metoda se referă la un grup de metode de punct interior, adică începe să lucreze cu un punct acceptabil și generează o secvență de puncte valide. Funcția de barieră Metoda, prin contrast, se referă la un grup de metode punct extern, ea începe să caute un punct inacceptabil, și generează o secvență de decizii incorecte, care se apropie soluția optimă în afara regiunii admisibile.
Să presupunem că avem o sarcină pentru a minimiza supuse constrângerilor
În special, pentru funcțiile dorite - limitele corespunzătoare pentru a utiliza funcția de barieră a forma:
^ R_1 (g_i (x)) + "/> -. Funcții continue care satisfac condițiile Dacă = 0"“.. /> Dacă dacă 0" /> = 0 "/> și 0"/> 0 /> 0 „/>. dacă.
Tipice sunt următoarele expresii pentru funcțiile:
) ^ P „/> ,, unde p - este un întreg pozitiv.
În continuare cu privire la sarcinile inițiale ale tranziției la optimizarea neconstrâns de funcții auxiliare: pentru a minimiza, în cazul în care 0 „/> 0“ /> - factor de penalizare.
Să funcție continuă α-. Notăm „/>.
Abordarea funcției de barieră este de a rezolva problemele de forma:
maximiza limitând în același timp
Algoritmul funcției de barieră
Să presupunem că avem următoarea problemă:
Minimizarea sub constrângeri, în cazul în care funcțiile.
Selectați etapa inițială 0 „/> 0“ /> Selectați punctul de pornire, parametrul de penalizare și numărul de 1 „/> 1„/>. Pune k = 1 și du-te la etapa principală.
Scena principală. k-lea iterație.
Primul pas. Atunci când parametrul penalizare punct de pornire și de a rezolva următoarea problemă:
Pune „/> egală cu soluția optimă a problemei și trece la al doilea pas.
cu următoarele restricții
0 "alt =" 8-x_1 ^ 2 - x_2 ^ 2 - x_3 ^ 2 - x_4 ^ 2 - x_1 + x_2 - x_3 + x_4> 0 "/> 0" alt = „10 -x_1 ^ 2-2x_2 ^ 2- x_3 ^ 2-2x_4 ^ 2 + x_1-x_4> 0 "/> 0" alt = "5 - 2x_1 ^ 2 - x_2 ^ 2 - x_3 ^ 2 - 2x_1 + x_2 + x_4> 0" />
Tabelul de mai jos prezintă rezultatele intermediare ale algoritmului.
Funcții de valoare miimiziruemoy
Coordonatele primului punct
Punctul optim vom ajunge la repetare 114y cu funcția de valoare optimă
Recomandarea programator
Cu ajutorul funcției de penalizare pentru rezolvarea problemelor asociate cu o anumită dificultate de calcul. În primul rând, căutarea poate începe cu un punct x fezabil, pentru care „/> .Pentru unele probleme în găsirea acestui punct este dificil. În plus, datorită utilizării de pași discreți algoritm de optimizare in apropiere de posibila etapa de frontieră, care merge dincolo de limitele zonei permise. El conduce la o scădere a valorilor, adică contrafaceri succes. Astfel, o necesitate clară Validating fiecare punct ulterior, care la fiecare iterație este necesară pentru a calcula valorile funcției.
Eficacitatea metodei funcției de barieră afectează substanțial alegerea valorilor inițiale și metoda de reducere a valorilor în procesul de minimizare, iar alegerea coeficienților de ponderare. În cazul în care valoarea funcției este selectată prea mică, atunci chiar și în faza inițială a procesului vine la o funcție minimă, care este puțin probabil să fie aproape de punctul real într-un minim noțională. Pe de altă parte, dacă valoarea selectată este prea mare, pe primele iterații ale procesului de calcul punctul curent va fi în mod inevitabil prea mult în afara zonei permise, și căutarea de necesitatea de a reveni la limitele regiunii fezabilă va fi foarte îndelungată.