Scurtă teorie

Metoda multiplicatorilor Lagrange este o metodă clasică de rezolvare a problemelor de programare matematică (în special, convexe). Din păcate, în aplicarea practică a metodei, pot apărea dificultăți de calcul semnificative, restrângând aria de utilizare a acesteia. Considerăm aici metoda Lagrange în principal pentru că este un aparat utilizat în mod activ pentru a justifica diverse metode numerice moderne care sunt utilizate pe scară largă în practică. În ceea ce privește funcția Lagrange și multiplicatorii Lagrange, acestea joacă un rol independent și extrem de important în teoria și aplicațiile nu numai ale programării matematice.

Luați în considerare o problemă clasică de optimizare:

Printre restricțiile acestei probleme nu există inegalități, nu există condiții pentru nenegativitatea variabilelor, discretitatea acestora și funcțiile și sunt continue și au derivate parțiale de cel puțin ordinul doi.

Abordarea clasică a rezolvării problemei oferă un sistem de ecuații (condiții necesare) care trebuie satisfăcut de punctul care asigură funcția cu un extremum local pe mulțimea de puncte care satisfac constrângerile (pentru o problemă de programare convexă, punctul găsit va fi în același timp punctul extremum global).

Să presupunem că funcția (1) are un extremum condiționat local în punctul și rangul matricei este egal cu . Atunci condițiile necesare pot fi scrise ca:

este funcția Lagrange; sunt multiplicatorii Lagrange.

Există și condiții suficiente în care soluția sistemului de ecuații (3) determină punctul extremum al funcției . Această întrebare este rezolvată pe baza studiului semnului celei de-a doua diferenţiale a funcţiei Lagrange. Cu toate acestea, condițiile suficiente sunt în principal de interes teoretic.

Puteți specifica următoarea procedură pentru rezolvarea problemei (1), (2) prin metoda multiplicatorului Lagrange:

1) alcătuiți funcția Lagrange (4);

2) găsiți derivatele parțiale ale funcției Lagrange în raport cu toate variabilele și echivalați-le

zero. Astfel, se va obtine un sistem (3) format din ecuatii Rezolvati sistemul rezultat (daca se dovedeste a fi posibil!) si gasiti astfel toate punctele stationare ale functiei Lagrange;

3) din punctele staționare luate fără coordonate, selectați puncte la care funcția are extreme locale condiționate în prezența restricțiilor (2). Această alegere se face, de exemplu, folosind condiții suficiente pentru un extremum local. Adesea, studiul este simplificat dacă sunt utilizate condiții specifice ale problemei.

Exemplu de rezolvare a problemei

Sarcina

Firma produce două tipuri de mărfuri în cantităţi şi . Funcția de cost util este definită de relația . Prețurile acestor bunuri pe piață sunt egale și respectiv.

Determinați la ce volume de producție se realizează profitul maxim și cu ce este egal dacă costurile totale nu depășesc

Aveți dificultăți în înțelegerea procesului de soluționare? Site-ul dispune de un serviciu Rezolvarea problemelor prin metode de solutii optime la comanda

Rezolvarea problemei

Modelul economic și matematic al problemei

Funcția de profit:

Limite de cost:

Obținem următorul model economic și matematic:

În plus, conform sensului sarcinii

Metoda multiplicatorului Lagrange

Să compunem funcția Lagrange:

Găsim derivate parțiale de ordinul I:

Compunem și rezolvăm sistemul de ecuații:

De atunci

Profit maxim:

Răspuns

Astfel, este necesar să se producă unități. bunuri de primul tip si unitati. bunuri de al 2-lea tip. În acest caz, profitul va fi maxim și va fi de 270.
Este dat un exemplu de rezolvare a problemei programării convexe pătratice printr-o metodă grafică.

Rezolvarea unei probleme liniare printr-o metodă grafică
Este luată în considerare o metodă grafică pentru rezolvarea unei probleme de programare liniară (LPP) cu două variabile. Pe exemplul problemei, se oferă o descriere detaliată a construcției unui desen și găsirea unei soluții.

Modelul de gestionare a stocurilor Wilson
Pe exemplul de rezolvare a problemei se ia în considerare modelul principal de management al stocurilor (modelul Wilson). Se calculează indicatori ai modelului precum dimensiunea optimă a lotului comenzii, costurile anuale de stocare, intervalul dintre livrări și punctul de plasare a comenzii.

Matricea raportului cost direct și matricea intrări-ieșiri
Pe exemplul rezolvării problemei, este luat în considerare modelul intersectorial Leontiev. Se prezintă calculul matricei coeficienților costurilor directe ale materialelor, matricei „input-output”, matricei coeficienților costurilor indirecte, vectorilor consumului final și producției brute.

Cu Esența metodei Lagrange este de a reduce problema extremului condiționat la soluția problemei extremului necondiționat. Luați în considerare un model de programare neliniară:

(5.2)

Unde
sunt funcții binecunoscute,

A
sunt dați coeficienți.

Rețineți că în această formulare a problemei, constrângerile sunt date de egalități și nu există nicio condiție ca variabilele să fie nenegative. În plus, presupunem că funcțiile
sunt continue cu primele lor derivate parțiale.

Să transformăm condițiile (5.2) în așa fel încât părțile din stânga sau din dreapta ale egalităților să conțină zero:

(5.3)

Să compunem funcția Lagrange. Include funcția obiectiv (5.1) și părțile din dreapta ale constrângerilor (5.3), luate respectiv cu coeficienții
. Vor fi atât de mulți coeficienți Lagrange câte constrângeri există în problemă.

Punctele extreme ale funcției (5.4) sunt punctele extreme ale problemei inițiale și invers: planul optim al problemei (5.1)-(5.2) este punctul extremum global al funcției Lagrange.

Într-adevăr, să se găsească soluția
problema (5.1)-(5.2), atunci condițiile (5.3) sunt îndeplinite. Să înlocuim planul
în funcția (5.4) și verificați validitatea egalității (5.5).

Astfel, pentru a găsi planul optim al problemei inițiale, este necesar să se investigheze funcția Lagrange pentru un extremum. Funcția are valori extreme în punctele în care derivatele sale parțiale sunt egale zero. Se numesc astfel de puncte staționar.

Definim derivatele parțiale ale funcției (5.4)

,

.

După egalizare zero derivate obținem sistemul m+n ecuatii cu m+n necunoscut

,(5.6)

În cazul general, sistemul (5.6)-(5.7) va avea mai multe soluții, care includ toate maximele și minimele funcției Lagrange. Pentru a evidenția maximul sau minimul global, valorile funcției obiectiv sunt calculate în toate punctele găsite. Cea mai mare dintre aceste valori va fi maximul global, iar cel mai mic va fi minimul global. În unele cazuri este posibil să se utilizeze condiţii suficiente pentru un extremum strict funcții continue (vezi problema 5.2 de mai jos):

lasa functia
este continuu si de doua ori diferentiabil intr-o vecinatate a punctului sau stationar (acestea.
)). Apoi:

A ) dacă
, (5.8)

apoi este punctul maxim strict al funcției
;

b) dacă
, (5.9)

apoi este punctul minim strict al funcției
;

G ) dacă
,

atunci chestiunea prezenței unui extremum rămâne deschisă.

Mai mult, unele soluții ale sistemului (5.6)-(5.7) pot fi negative. Ceea ce nu este în concordanță cu sensul economic al variabilelor. În acest caz, ar trebui analizată posibilitatea înlocuirii valorilor negative cu zero.

Sensul economic al multiplicatorilor Lagrange. Valoarea optimă a multiplicatorului
arată cât de mult se va schimba valoarea criteriului Z la creşterea sau scăderea resursei j pe unitate, deoarece

Metoda Lagrange poate fi aplicată și atunci când constrângerile sunt inegalități. Deci, găsirea extremului funcției
in conditii

,

realizat în mai multe etape:

1. Determinați punctele staționare ale funcției obiectiv, pentru care rezolvă sistemul de ecuații

.

2. Din punctele staţionare sunt selectate acelea ale căror coordonate îndeplinesc condiţiile

3. Metoda Lagrange este folosită pentru a rezolva problema cu constrângeri de egalitate (5.1)-(5.2).

4. Punctele găsite la a doua și a treia etapă sunt examinate pentru un maxim global: valorile funcției obiective în aceste puncte sunt comparate - cea mai mare valoare corespunde planului optim.

Sarcina 5.1 Să rezolvăm problema 1.3, considerată în prima secțiune, prin metoda Lagrange. Distribuția optimă a resurselor de apă este descrisă de un model matematic

.

Compuneți funcția Lagrange

Găsiți maximul necondiționat al acestei funcții. Pentru a face acest lucru, calculăm derivatele parțiale și le echivalăm cu zero

,

Astfel, am obținut un sistem de ecuații liniare de forma

Rezolvarea sistemului de ecuații este planul optim de repartizare a resurselor de apă pe suprafețele irigate

, .

Cantitati
măsurată în sute de mii de metri cubi.
- suma venitului net la o sută de mii de metri cubi de apă de irigare. Prin urmare, prețul marginal al 1 m 3 de apă de irigare este
den. unitati

Venitul net suplimentar maxim din irigare va fi

160 12,26 2 +7600 12,26-130 8,55 2 +5900 8,55-10 16,19 2 +4000 16,19=

172391.02 (unități den.)

Sarcina 5.2 Rezolvați o problemă de programare neliniară

Reprezentăm constrângerea ca:

.

Compuneți funcția Lagrange și determinați derivatele ei parțiale

.

Pentru a determina punctele staționare ale funcției Lagrange, ar trebui să echivaleze derivatele sale parțiale cu zero. Ca rezultat, obținem un sistem de ecuații

.

Din prima ecuație urmează

. (5.10)

Expresie înlocuiți în a doua ecuație

,

din care există două soluţii pt :

și
. (5.11)

Înlocuind aceste soluții în a treia ecuație, obținem

,
.

Valorile multiplicatorului Lagrange și ale necunoscutului calculați prin expresiile (5.10)-(5.11):

,
,
,
.

Astfel, avem două puncte extreme:

;
.

Pentru a afla dacă aceste puncte sunt puncte maxime sau minime, folosim condițiile suficiente pentru un extremum strict (5.8)-(5.9). Preexpresie pentru , obținut din restricția modelului matematic, substituim în funcția obiectiv

,

. (5.12)

Pentru a verifica condițiile pentru un extremum strict, ar trebui să determinăm semnul derivatei a doua a funcției (5.11) în punctele extreme pe care le-am găsit
și
.

,
;

.

Prin urmare, (·)
este punctul minim al problemei inițiale (
), A (·)
- punct maxim.

Planul optim:

,
,
,

.

Descrierea metodei

Unde .

Motivație

Următoarea justificare a metodei multiplicatorului Lagrange nu este dovada sa riguroasă. Conține raționament euristic care ajută la înțelegerea semnificației geometrice a metodei.

carcasă 2D

Linii de nivel și curbă.

Să fie necesar să se găsească extremul unei funcții a două variabile în condiția dată de ecuație . Vom presupune că toate funcțiile sunt diferențiabile continuu, iar această ecuație definește o curbă netedă S la suprafata. Atunci problema se reduce la găsirea extremului funcției f pe curbă S. Vom presupune și asta S nu trece prin punctele unde gradientul f se transformă în 0.

Desenați în plan liniile de nivel ale funcției f(adică curbe). Din considerente geometrice se poate observa că extremul funcției f pe curbă S pot exista doar puncte în care tangentele la S iar linia de nivel corespunzătoare sunt aceleași. Într-adevăr, dacă curba S traversează linia de nivel fîntr-un punct transversal (adică la un unghi diferit de zero), apoi deplasându-se de-a lungul curbei S din punct de vedere putem ajunge pe amândouă la liniile de nivel corespunzătoare valorii mai mari f, și mai mici. Prin urmare, un astfel de punct nu poate fi un punct extremum.

Astfel, condiția necesară pentru extremum în cazul nostru va fi coincidența tangentelor. Pentru a-l scrie în formă analitică, rețineți că este echivalent cu paralelismul gradienților funcțiilor fși ψ în acest punct, deoarece vectorul gradient este perpendicular pe tangenta la linia de nivel. Această condiție este exprimată în următoarea formă:

unde λ este un număr diferit de zero, care este multiplicatorul Lagrange.

Luați în considerare acum Funcția Lagrangeîn funcție de și λ :

O condiție necesară pentru extremul său este gradientul zero. În conformitate cu regulile de diferențiere, se scrie ca

Am obținut un sistem ale cărui prime două ecuații sunt echivalente cu condiția extremă locală necesară (1), iar cea de-a treia este echivalentă cu ecuația . Din el puteți găsi. În acest caz, deoarece în caz contrar gradientul funcției f dispare la un moment dat , ceea ce contrazice presupunerile noastre. Trebuie remarcat faptul că punctele găsite în acest fel pot să nu fie punctele extreme condiționale dorite - condiția considerată este necesară, dar nu suficientă. Găsirea unui extremum condiționat folosind o funcție auxiliară Lși formează baza metodei multiplicatorului Lagrange aplicată aici pentru cel mai simplu caz al două variabile. Rezultă că raționamentul de mai sus poate fi generalizat în cazul unui număr arbitrar de variabile și ecuații care specifică condițiile.

Pe baza metodei multiplicatorilor Lagrange, se pot demonstra și unele condiții suficiente pentru un extremum condiționat, care necesită o analiză a derivatelor secunde ale funcției Lagrange.

Aplicație

• Metoda multiplicatorului Lagrange este folosită pentru a rezolva probleme de programare neliniară care apar în multe domenii (de exemplu, în economie).
• Metoda principală pentru rezolvarea problemei de optimizare a calității codificării datelor audio și video pentru un anumit bitrate mediu (optimizarea distorsiunii - engleză. Optimizarea ratei-distorsiuni).

Vezi si

Legături

• Zorich V. A. Analiza matematică. Partea 1. - ed. a 2-a, rev. si suplimentare - M.: FAZIS, 1997.

Fundația Wikimedia. 2010 .

Vedeți ce sunt „multiplicatorii Lagrange” în alte dicționare:

Multiplicatori de Lagrange- factori suplimentari care transformă funcția obiectivă a problemei extreme a programării convexe (în special, programarea liniară) atunci când aceasta este rezolvată prin una dintre metodele clasice prin metoda rezolvării factorilor ... ... Dicţionar economic şi matematic

Multiplicatori de Lagrange- Factori suplimentari care transformă funcția obiectivă a problemei extreme a programării convexe (în special, programarea liniară) atunci când aceasta este rezolvată prin una dintre metodele clasice prin metoda rezolvării factorilor (metoda Lagrange). ... ... Manualul Traducătorului Tehnic

Mecanica. 1) Ecuații lagrangiene de primul fel, ecuații diferențiale ale mișcării unui mecanic. sisteme, care sunt date în proiecții pe axe de coordonate dreptunghiulare și conțin așa-numitele. Multiplicatori de Lagrange. Primit de J. Lagrange în 1788. Pentru un sistem holonomic, ...... Enciclopedia fizică

Mecanica ecuații diferențiale ordinare de ordinul 2, care descriu mișcarea unei mecanice. sisteme aflate sub influenţa forţelor aplicate acestora. L. la. stabilit de J. Gama Lag sub două forme: L. at. Primul fel, sau ecuații în coordonate carteziene cu ...... Enciclopedie matematică

1) în hidromecanică, ecuația pentru mișcarea unui lichid (gaz) în variabilele Lagrange, care sunt coordonatele mediului. Am primit franceza. savantul J. Lagrange (J. Lagrange; c. 1780). De la L. la. legea de mișcare a mediului h c este determinată sub formă de dependențe ... ... Enciclopedia fizică

Metoda multiplicatorului Lagrange, o metodă pentru găsirea extremului condiționat al funcției f(x), unde, în raport cu m constrângeri, i variază de la unu la m. Cuprins 1 Descrierea metodei ... Wikipedia

O funcție utilizată în rezolvarea problemelor pentru un extremum condiționat de funcții ale mai multor variabile și funcționale. Cu ajutorul lui L. f. condiţiile de optimitate necesare se notează în probleme pentru un extremum condiţionat. Nu este nevoie să exprimați doar variabile... Enciclopedie matematică

Metoda de rezolvare a problemelor pentru extremul Condițional; L. m. m. constă în reducerea acestor probleme la probleme pentru un extremum necondiţionat al unei funcţii auxiliare a aşa-numitei. Funcții Lagrange. Pentru problema extremului funcției f (x1, x2,..., xn) pentru ... ...

Variabile, cu ajutorul cărora se construiește funcția Lagrange în studiul problemelor pentru un extremum condiționat. Utilizarea lui L. m. și a funcției Lagrange face posibilă obținerea condițiilor de optimitate necesare într-un mod uniform în probleme pentru un extremum condiționat ... Enciclopedie matematică

1) în hidromecanică, ecuațiile de mișcare ale unui mediu lichid scrise în variabile Lagrange, care sunt coordonatele particulelor mediului. De la L. la. legea de mișcare a particulelor mediului este determinată sub formă de dependențe ale coordonatelor în timp și conform acestora ... ... Marea Enciclopedie Sovietică

METODA LAGRANGE

Metoda de reducere a unei forme pătratice la o sumă de pătrate, indicată în 1759 de J. Lagrange. Să fie dat

din variabile x 0 , X 1 ,..., x n. cu coeficienţi din teren k caracteristici Se cere aducerea acestei forme la canonice. minte

folosind o transformare liniară nedegenerată a variabilelor. L. m. se compune din următoarele. Putem presupune că nu toți coeficienții formei (1) sunt egali cu zero. Prin urmare, două cazuri sunt posibile.

1) Pentru unii g, diagonala Atunci

unde forma f 1 (x) nu conține o variabilă x g . 2) Dacă toate dar apoi

unde forma f 2 (x) nu conţine două variabile xgși x h . Formele de sub semnele pătrate din (4) sunt liniar independente. Prin aplicarea transformărilor formei (3) și (4), forma (1) după un număr finit de pași se reduce la suma pătratelor formelor liniare liniar independente. Folosind derivate parțiale, formulele (3) și (4) pot fi scrise ca

Lit.: G a n t m a h e r F. R., Teoria Matricilor, ed. a II-a, Moscova, 1966; K ur o sh A. G., Curs de algebră superioară, ed. a XI-a, M., 1975; Alexandrov P.S., Prelegeri de geometrie analitică..., M., 1968. I. V. Proskuryakov.

Enciclopedie matematică. - M.: Enciclopedia Sovietică. I. M. Vinogradov. 1977-1985.

Vedeți ce este „METODA LAGRANGE” în ​​alte dicționare:

Metoda Lagrange- Metoda Lagrange - o metodă de rezolvare a unui număr de clase de probleme de programare matematică prin găsirea unui punct de șa (x *, λ *) al funcției Lagrange, care se realizează prin egalarea la zero a derivatelor parțiale ale acestei funcții în raport cu . .. ... Dicţionar economic şi matematic

Metoda Lagrange- O metodă pentru rezolvarea unui număr de clase de probleme de programare matematică prin găsirea unui punct de șa (x*, ?*) al funcției Lagrange, care se realizează prin egalarea la zero a derivatelor parțiale ale acestei funcții în raport cu xi și ?i . Vezi Lagrangian. (X, y) = C și f 2 (x, y) = C 2 la suprafata XOY.

De aici urmează o metodă de găsire a rădăcinilor sistemului. ecuații neliniare:

Determinați (cel puțin aproximativ) intervalul de existență a unei soluții la sistemul de ecuații (10) sau ecuația (11). Aici este necesar să se țină cont de tipul de ecuații incluse în sistem, domeniul de definire al fiecăreia dintre ecuațiile lor etc. Uneori se folosește selecția aproximării inițiale a soluției;

Tabelați soluția ecuației (11) pentru variabilele x și y pe intervalul selectat sau construiți grafice ale funcțiilor f 1 (X, y) = C, și f 2 (x, y) = C 2 (sistem(10)).

Localizați rădăcinile estimate ale sistemului de ecuații - găsiți mai multe valori minime din tabelul de tabelare a rădăcinilor ecuației (11) sau determinați punctele de intersecție ale curbelor incluse în sistem (10).

4. Găsiți rădăcinile sistemului de ecuații (10) folosind suplimentul Căutați o soluție.