În cazul general, metodele de gradient sunt înțelese ca metode în care direcția de mișcare până la punctul optim al funcției coincide cu direcția de gradient al acestei funcții. Metodele de gradient se referă la metodele aproximative pentru rezolvarea problemelor de programare neliniară. În general, ele oferă o soluție optimă printr-un proces infinit de aproximări succesive. Cu toate acestea, în unele cazuri, procesul se poate termina după un număr finit de iterații.
Metodele gradient pot fi aplicate la orice problemă de programare neliniară, conducând doar la un extremism local mai degrabă decât la cel global. Prin urmare, ele sunt mai eficiente în rezolvarea problemelor de programare convexă, unde orice extremum local este simultan global.
Formula generală a problemei corespunde cu (5.1) și (5.2). Cu toate acestea, fără pierderea generalității, ea poate fi transformată în formă
Strategia matematică a metodei gradientului este următoarea. Se selectează un punct acceptabil arbitrar. Pentru a trece prin iterații de la un punct la altul, determinați această direcție. astfel încât, dacă raza este suficient de mică, ea aparține regiunii admisibile. Adică, următorul punct al procesului iterativ este determinat de formula:
Diferența dintre metodele de gradient este modul de determinare a direcției și a parametrului.
1. Dacă este un punct interior al domeniului soluțiilor admisibile, atunci
există un gradient al funcției într-un punct. Strategia, exprimată prin relația (5.57), definește mișcarea cu pas variabil, deoarece valoarea pasului depinde de valoarea gradientului. Pe măsură ce valoarea gradientului scade în apropierea optimei, în unele zone pașii vor fi mici, ceea ce prelungește timpul de căutare. Acest defect poate fi eliminat prin utilizarea unei strategii de gradient cu un pas constant. În acest caz, vectorul de gradient este înlocuit cu vectorul direcției gradientului:
2. Nu aparține unui domeniu admisibil. Acest lucru poate fi cazul dacă punctul, care se deplasează în direcția celei mai mari creșteri a funcției, a încălcat constrângerea i (5.54). Ca pedeapsă pentru încălcarea restricției i, introducem factorul Ri și funcția obiectivului auxiliar.
Dacă funcția obiectivă este de a înțelege venitul întreprinderii, adică nimic mai puțin decât venitul întreprinderii după deducerea penalităților.
În cel mai simplu caz, Ri este ales după cum urmează:
Numărul R trebuie să fie suficient de mare pentru a determina punctul să se miște în interiorul regiunii admisibile. Direcția de mișcare a punctului în acest caz este dată de vector
Dezavantajul acestei strategii este că acuratețea calculului depinde de alegerea R. Dacă nu este alegerea numărului de proces iterativ R va fi caracterizat prin fluctuații ascuțite în punctul în apropierea graniței.
Acest defect poate fi evitat dacă acceptăm că pedeapsa ar trebui să fie mai mică decât încălcarea mai mică poate avea loc, adică este rezonabil să se presupună că
1) Numărul parametrilor este constant la toate iterațiile. Cu cât numărul este mai mic. cu cât calculul este mai precis. În consecință, timpul de căutare al optimului crește de asemenea;
2) Parametrul este selectat la fiecare pas din condiția min # 955; ', # 955; "> unde # 955; "- valoarea parametrului la care raza + # 955; (k) S (k) intersectează GDZ; # 955; - o astfel de valoare valabilă # 955; pentru care funcția f (+ # 955; (k) S (k)) atinge un maxim pe rază. Această strategie vă permite să stați la punctul LDU și să optimizați numărul de iterații. Totuși, cu constrângeri neliniare și cu o funcție obiectivă neliniară, calculul # 955; ' # 955; "poate fi destul de consumatoare de timp.
Pentru a ilustra metoda gradientului, alegem următoarea strategie: # 955; - numărul este constant; valoarea pedepsei este proporțională cu valoarea încălcării restricției; Direcția de mișcare a punctului coincide cu direcția gradientului. Aceasta este așa-numita metodă de gradient Arrow-Hurwitz. Dacă constrângerile semnului (5.55) sunt absente, atunci coordonatele noului punct pot fi calculate în conformitate cu (5.56), (5.60) conform formulei:
Luând în considerare condiția nonnegativity (5.55), expresia (5.62) va arata ca:
În expresiile (5.62) și (5.63), funcția de penalizare este calculată din formula (5.61).
Exemplul 5.3 Este necesară maximizarea funcției
lăsa # 955; = 0,1; R1 (0) = 2; x1 (0) = 3; x2 (0) = 1.5, adică am ales punctul de plecare, care cu siguranță nu aparține domeniului admisibil.
Ecuațiile (5.62) au următoarea formă:
Ecuațiile (5.61) au următoarea formă:
A doua iterație: punctul este deja în interiorul regiunii admisibile, cu toate acestea, multiplicatorul. deși mai puțin. dar, de asemenea, diferit de 0, iar limita continuă să „împinge“ un punct în mișcare în interiorul zonei admisibile (acest punct este încă pe „distanța periculoasă“ de la frontieră):
În mod similar, acest proces poate continua. Cu o creștere a numărului de iterații, punctul sub convexitatea funcției obiective tinde spre rezolvarea problemei.
Lista recomandărilor recomandate
1. A. V. Kuznetsov, I. I. Kholod. Programarea matematică. - Minsk: Școala superioară. 984. - 221 p.
4. Zaichenko Yu.P. Investigarea operațiunilor: Proc. manual pentru studenți. - ed. 2 Revizuit. și suplimentare. - Kiev: Școala Vishcha. Editura principală, 1979. 392 p.
5. IA Akulich. Programarea matematică în exemple și probleme. - M. "Școala superioară", 1986.- 319 p.
9. S. Gass. Programare liniară. - M. "Science", 1961.-303 p.
10. Sakovich V.A. Investigarea operațiunilor (metode și modele deterministe): o carte de referință. - Mn. Ta. săpt. 1984.-256s.
11. Taha H. Introducere în studiul operațiilor: în două cărți. Kn 1,2 Trans. cu engleza. - M. Mir, 1985.
Articole similare
Trimiteți-le prietenilor: