Algoritmul metodei multiplicatorilor lui Lagrange

Acasă | Despre noi | feedback-ul

metoda multiplicatorului Lagrange.

metoda multiplicatorilor Lagrange este una dintre tehnicile care ne permit să rezolve problema de programare neliniară.

Programarea neliniara este o ramură a programării matematice, metode de rezolvare a problemelor de optimizare cu funcții obiectiv neliniare și regiunea fezabilă definită de constrângerile neliniare de învățare. În economie, acest lucru corespunde cu faptul că rezultatele (eficiența) majorarea sau reducerea o modificare disproporționată în scale de utilizare a resurselor (sau, echivalent, producția la scară) de tensiune. ca urmare a repartizării costurilor întreprinderilor de producție în care variabilele și condiționate constantă; datorită saturării cererii de bunuri, atunci când fiecare unitate de lângă vinde mai greu decât cele anterioare, și așa mai departe. d.

Problema este formulată ca o problemă de programare neliniară găsirii optime funcției țintă specific

atunci când condițiile

unde x este vectorul variabilelor necunoscute;

g (x) - limitarea funcției (continuu diferențiabilă);

b - vectorul constantelor limitări.

Soluția de rezolvare a problemei de programare neliniare (globală maximă sau minimă) poate aparține fie limita sau interiorul setului fezabil.

În contrast cu problema de programare liniară, în problema de programare neliniare optime nu se află neapărat pe limita zonei definită de restricțiile. Cu alte cuvinte, provocarea este de a alege astfel de variabile non-negativ supuse unor restricții sub forma unui sistem de inegalități, cu care maxim (sau minim) a funcției. În acest caz, forma nu specifică nicio funcție țintă sau inegalitate. Pot fi cazuri diferite: funcția obiectiv este constrângerile liniare și neliniare; funcția obiectiv este liniară și limitată (cel puțin una dintre ele) sunt liniare; și funcția obiectiv și constrângerile neliniare.

problemă de programare neliniara se găsește în științe naturale, inginerie, economie, matematică, în domeniul relațiilor de afaceri în știința guvernului.

programare neliniara, de exemplu, este asociat cu sarcina economică principală. Deci, problema alocării resurselor limitate sau de a maximiza eficiența, sau în cazul în care studiul de consum, consumul de prezența unor constrângeri, care exprimă condițiile lipsei de resurse. Într-o astfel de situație generală a formulării matematice a problemei nu poate fi posibil, dar în cererea specifică de vedere cantitativ a tuturor funcțiilor pot fi determinate în mod direct. De exemplu, o instalație de fabricare a produce produse din plastic. eficiența producției este profiturilor estimate și constrângerile de numerar sunt interpretate ca forță de muncă, facilități de producție, echipamente performante, etc.

Metoda de „cost - eficiență“, de asemenea, se încadrează în schema de programare neliniare. Această metodă a fost dezvoltată pentru a fi utilizat în procesul de luare a deciziilor în guvern. Funcția generală a eficienței este bogăția. Acest lucru ridică două probleme de programare neliniara: prima - pentru a maximiza efectul cu costuri limitate, al doilea - minimizarea costurilor, cu condiția ca efectul este peste un anumit nivel minim. De obicei, această sarcină este bine modelat prin programarea non-lineară.

Probleme Nonlinear sunt complexe, ele sunt adesea simplificate prin faptul că acestea conduc la liniar. În acest scop, presupus convențional că la o anumită porțiune țintă crește funcției sau descrește proporțional cu variabilele independente. Această abordare este numită de aproximări liniare pe porțiuni, se aplică, cu toate acestea, numai pentru anumite tipuri de probleme neliniare.

Probleme neliniara, în anumite condiții, sunt rezolvate prin funcția Lagrange: găsirea ei un punct de șa, și astfel să găsim soluția. Printre algoritmi de calcul N. n. Un loc mare este ocupat de metode de gradient. aceeași metodă universală pentru probleme neliniare acolo și, aparent, nu poate fi, deoarece acestea sunt extrem de variate. Mai ales dificil sunt rezolvate problemele multiextremal.

Una dintre metodele care vă permit să reducă problema programării neliniare pentru rezolvarea sistemului de ecuații este metoda multiplicatorilor lui Lagrange.

Cu ajutorul metodei multiplicatorului Lagrange, condițiile necesare sunt stabilite pe fond, care să permită identificarea punctului optim în probleme de optimizare cu constrângeri în formă ra-egalități. Astfel, problema cu constrângeri convertite la problema echivalentă valență de optimizare fără restricții, care a prezentat unele dintre parametrii necunoscuți, numit La multiplicatori Grange.

Lagrange Metoda multiplicatorilor constă în reducerea extremum condițional la probleme necondiționate extremum auxiliare funcției - t n .. funcția Lagrange.

multiplicatori # 955; 1. # 955; 2. # 955; m numit. multiplicatorilor lui Lagrange.

Dacă valoarea X1. x2. xn. # 955; 1. # 955; 2. # 955; m sunt soluții de ecuații care definesc punctul staționar al funcției Lagrange, și anume, pentru funcțiile derivabile sunt soluții ale sistemului de ecuații

atunci când suficiente ipoteze x1 generale. x2. xn oferi valoare extremă a f.

Luați în considerare problema minimizarea funcției de n variabile care fac obiectul restricțiilor sub formă de egalitate:

În conformitate cu metoda multiplicatorilor lui Lagrange, sarcina este transformată în următoarea problemă de optimizare fără restricții:

minimizând L (x, # 955;) = f (x) - # 955; * h (x) (3)

în cazul în care funcția L (x; # 955;) este numit Lagrangianului,

# 955; - constantă necunoscută, care se numește un multiplicator Lagrange. pe semnul # 955; nu există cerințe sunt impuse.

Să presupunem că, pentru o anumită valoare # 955 = # 955; 0 minimă absolută a funcției L (x, # 955;) în raport cu x este atins la x = x0 și x0 satisface h1 ecuația (x0) = 0. Apoi, așa cum este ușor de văzut, minimalizează x0 (1) cu (2), deoarece toate valorile lui x care satisface (2), h1 (x) = 0 și L (x, # 955;) = min f (x).

Desigur, trebuie să alegeți o valoare # 955 = # 955; 0, astfel încât punctul de minim absolut de coordonate x0 satisfac ecuația (2). Acest lucru se poate face prin luarea în considerare # 955; ca variabilă, găsi minimul absolut al funcției (3) în funcție de # 955;, apoi selectați # 955;, în care egalitatea (2). Ilustrăm acest lucru cu titlu de exemplu.

Minimizarea f (x) = x1 + x2 2 2 = 0

Corespondent de optimizare fără restricții este scris după cum urmează:

Decizie. Echivalând gradientul L două componente la zero, obținem

Pentru a verifica dacă punctul de staționare x ° corespunde la minim, se calculează elementele Hessian matrice ale funcției L (x; u), considerate ca funcție de x,

care se dovedește a fi pozitiv definită.

Acest lucru înseamnă că L (x, u) - funcția convexă x. În consecință, coordonatele x1 = 0 # 955;, x2 = 0 # 955; / 2 este determinat punctul minim global. Valoarea optimă # 955; Este găsit prin substituirea valorilor x1 și x2 0 0 uravnenie2x1 + x2 = 2, de la 2 # 955 + # 955; / 2 = 2, sau # 955; 0 = 4/5. Astfel, se realizează minimul relativ când x1 = 0 4/5 0 și x2 = 2/5 și egal min f (x) = 4/5.

În rezolvarea problemei exemplului am uitat la L (x; # 955;) ca o funcție de două variabile x1 și x2, și, în plus, se presupune că valoarea parametrului # 955; alese astfel încât să satisfacă restrictie-chenie. În cazul în care soluția sistemului

funcționează ca explicite # 955; nu pot fi obținute, atunci valorile lui x și # 955; Ele se găsesc prin rezolvarea următorului sistem format din n + 1 ecuații cu n + 1 necunoscute:

Pentru a găsi toate soluțiile posibile ale acestui sistem, puteți utiliza metode de căutare numerice (cum ar fi metoda lui Newton). Pentru fiecare dintre soluțiile () este necesară pentru calcularea elementelor Hessian funcțiilor matricei L, considerate ca funcție de x, și de a afla dacă aceasta este o matrice pozitiv definită (un minim local) sau negativ definit (maxim local).

Lagrange metoda multiplicatorilor poate fi extinsă la cazul în care sarcina are puține restricții în formă de ecuații. Luați în considerare o problemă generală, care necesită

sub constrângeri hk = 0, k = 1, 2 K.

Funcția Lagrange ia forma următoare:

aici # 955; 1. # 955; 2. # 955; k este un factor Lagrange, și anume parametrii necunoscuți ale căror valori trebuie determinate. Prin echivalarea derivatelor parțiale cu privire la x L la zero, obținem următorul sistem de n ecuații cu n necunoscute:

Dacă găsiți o soluție de cele de mai sus sub formă de funcții vectoriale # 955; este dificil, este posibil să se extindă sistemul prin includerea restricțiilor sub formă de egalități

Sistemul extins soluție constând din n + k ecuații cu K funcție necunoscută n + definește un punct fix procedură de verificare L. se realizează atunci minimul sau maximul, care se bazează pe calculul elementelor funcției Hessian L, considerată ca funcție de x, doar așa cum sa făcut în cazul unei probleme cu o singură restricție. Pentru unele probleme, a extins sistemul n + k ecuatii cu n + necunoscutele K nu pot avea soluții și metoda Lagrange de multiplicare este inaplicabilă. Trebuie remarcat, totuși, că astfel de probleme în practică sunt rare.

Considerăm cazul special al problemei generale de programare neliniare, presupunând că sistemul conține numai constrângeri ale ecuației, nu există condiții de non-negativitate și variabile, și - funcția este continuă, împreună cu derivații săi parțiale

Această problemă se numește problema unei extremum condiționată sau o problemă de optimizare clasică.

Pentru a găsi o soluție la această problemă, să introducă un set de variabile numite multiplicatorilor lui Lagrange. alcătuiesc Lagrangianului

sunt derivatele parțiale ale sistemului și considerând ecuațiile m n +

cu n + m necunoscutelor Fiecare soluție de ecuații (7) definește un punct care poate avea loc extremum funcției. rezolvarea în consecință un sistem de ecuații (7) pentru a obține toate punctele în care funcția (6) pot avea valori extreme.

Algoritmul metodei multiplicatorilor lui Lagrange

Funcția 1.Sostavlyaem Lagrange.

2.Nahodim derivate parțiale ale funcției Lagrangiene în ceea ce privește variabilele xj, # 955; i și egalează le la zero.

3.Reshaem sistem de ecuații (7), vom găsi punctul în care funcția țintă a problemei poate fi extreme.

4. Printre punctele care sunt suspecte extremum găsi cele în care este atins extremum și calcula valorile funcției (6), la aceste puncte.

Context: Conform planului companiei de producție are nevoie pentru a produce 180 de produse. Aceste produse pot fi făcute două moduri tehnologice. În metoda de producție costurile de fabricație 1 x1 sunt 4x1 + x1 2 RUB. și la fabricarea articolelor 2 x 2 mod care le fac 8x2 + x2 2 ruble. Determina cât de multe elemente ale fiecărei metode ar trebui să facă la costul de producție a fost minimă.

Funcția obiectiv pentru această problemă este dată de
®min în condiții x1 + x2 = 180, x2 ≥0.
1.Sostavlyaem Lagrangiene
.
2. Calculati derivatele parțiale în raport cu x1. x2, # 955; și le echivala cu zero:

3. Prin rezolvarea sistemului de ecuații rezultat, obținem x1 = 91, x2 = 89

4.Sdelav substituție în obiectivul funcției x2 = 180 x1. obține o funcție de o variabilă, și anume f1 = 4x1 + x1 2 + 8 (180 x1) + (180 x1) 2

Calculati sau 4x1 -364 = 0,

A: Numărul de produse fabricate de prima metodă este egală cu x1 = 91, x2 = a doua metodă 89, în care valoarea funcției obiectiv este egală cu 17278 freca.