Lagrange multiplikator metode

Lagrange multiplikatormetoden , der bruges til at løse problemer med matematisk programmering (især lineær programmering ) er en metode til at finde det betingede ekstremum af funktionen , hvor , i forhold til begrænsningerne , hvor varierer fra en til . $f(x)$ $x\in \mathbb{R} ^{n}$ $m$ $\varphi _{i}(x)=0$ $jeg$ $m$

Beskrivelse af metoden

Vi sammensætter Lagrange-funktionen som en lineær kombination af funktionen og funktionerne taget med koefficienter, kaldet Lagrange-multiplikatorer - : $f$ $\varphi _{i}$ $\lambda _{i}$

L(x,\;\lambda )=f(x)+\sum _{{i=1}}^{m}\lambda _{i}\varphi _{i}(x),

hvor .

\lambda =(\lambda _{1},\;\ldots ,\;\lambda _{m})

Lad os sammensætte et ligningssystem ved at nulstille de partielle afledte af Lagrange-funktionen med hensyn til og . $n+m$ $L(x,\;\lambda)$ $x_{j}$ $\lambda _{i}$
Hvis det resulterende system har en løsning med hensyn til parametrene og , så kan punktet være et betinget ekstremum, det vil sige en løsning på det oprindelige problem. Bemærk, at denne betingelse er nødvendig, men ikke tilstrækkelig. $x'_{j}$ $\lambda '_{i}$ $x'$

Begrundelse

Den følgende begrundelse for Lagrange-multiplikatormetoden er ikke dens strenge bevis. Den indeholder heuristisk ræsonnement, der hjælper med at forstå den geometriske betydning af metoden.

Todimensional kasus

Lad det være nødvendigt at finde yderpunktet af funktionen under betingelsen givet af ligningen . $f(x,\;y)$ $\psi(x,\;y)=0$

Det vil vi antage

1) funktionen er kontinuerligt differentierbar,

f

2) funktionen er kontinuerligt differentierbar, med partielle afledte, der ikke er lig med nul på samme tid, det vil sige, at ligningen definerer en glat kurve fra almindelige punkter på planet .

\psi

\psi(x,\;y)=0

S

(x,\;y)

3) kurven går ikke gennem punkter, hvor gradienten bliver .

S

f

0

Lad os på planet tegne funktionens niveaulinjer ( det vil sige kurverne ). Af geometriske betragtninger følger det, at punktet (eventuelt punkter) af funktionens betingede ekstremum kun kan være kurvens berøringspunkt og en eller anden niveaulinje, det vil sige det punkt, hvor tangenten til og tangenten til denne. niveaulinjen falder sammen. Faktisk, hvis kurven på et tidspunkt skærer niveaulinjen på tværs (det vil sige i en vinkel, der ikke er nul), så kan du, når du bevæger dig langs kurven fra punktet , komme begge til niveaulinjerne svarende til en værdi større end , og til niveaulinjerne svarende til en værdi mindre end . Derfor kan et sådant punkt ikke være et ekstremum punkt. $(x,\;y)$ $f$ $f(x,\;y)={\mathrm {konst}}$ $f$ $S$ $S$ $(x_{0},\;y_{0})$ $S$ $f(x_0,\;y_0)=C_0$ $S$ $(x_{0},\;y_{0})$ $C_{0}$ $C_{0}$

Den nødvendige betingelse for et ekstremum i den pågældende sag er således sammenfaldet af tangenterne. For at skrive det i analytisk form skal du bemærke, at det svarer til paralleliteten af funktionernes gradienter og ved et givet punkt, da gradientvektoren er vinkelret på tangenten til niveaulinjen. Denne betingelse er udtrykt i følgende form: $f$ $\psi$

\nabla f\Big|_{(x_0,\;y_0)}=\lambda \cdot \nabla\psi\Big|_{(x_0,\;y_0)},\qquad\qquad(1)

hvor er et eller andet ikke-nul tal, som er Lagrange-multiplikatoren. $\lambda$

Overvej nu Lagrange-funktionen afhængigt af og : $x,\;y$ $\lambda$

L(x,\;y,\;\lambda)=f(x,\;y)-\lambda \cdot \psi(x,\;y).

En nødvendig betingelse for dets ekstremum er nulgradienten . I overensstemmelse med reglerne om differentiering skrives det som $\nabla L(x_{0},\;y_{0},\;\lambda _{0})=0$

\left\{\begin{array}{llcc} \dfrac{\partial f}{\partial x}\Big|_{(x_0,\;y_0)} & -\lambda_0 \cdot \dfrac{\partial\psi }{\partial x}\Big|_{(x_0,\;y_0)} & = & 0,\\ \dfrac{\partial f}{\partial y}\Big|_{(x_0,\;y_0) } & -\lambda_0 \cdot \dfrac{\partial\psi}{\partial y}\Big|_{(x_0,\;y_0)} & = & 0,\\ & -\psi(x_0,\;y_0 ) & = & 0. \end{array}\right.

I det resulterende system er de to første ligninger ækvivalente med den nødvendige betingelse for det lokale ekstremum (1), og den tredje er ækvivalent med ligningen . Fra den kan du finde . Desuden , da ellers gradienten af funktionen forsvinder ved punktet , hvilket modsiger antagelserne. $\psi(x,\;y)=0$ $(x_{0},\;y_{0},\;\lambda _{0})$ $\lambda _{0}\neq 0$ $f$ $(x_{0},\;y_{0})\i S$

Bemærkning . De punkter, der findes på denne måde , er muligvis ikke betingede ekstremumpunkter - den skriftlige differentialbetingelse er nødvendig , men ikke tilstrækkelig . $(x_{0},\;y_{0})$ $f$

Ovenstående argumenter om at finde et betinget ekstremum ved hjælp af en hjælpefunktion danner grundlaget for Lagrange-multiplikatormetoden og er generaliseret til tilfældet med et vilkårligt antal variabler og ligninger, der specificerer betingelserne. $L$

Baseret på metoden med Lagrange-multiplikatorer kan man opnå tilstrækkelige betingelser for et betinget ekstremum, der kræver analyse (i det simpleste tilfælde) af de anden afledede af Lagrange-funktionen . $L$

Ansøgning

Lagrange-multiplikatormetoden bruges til at løse ikke-lineære programmeringsproblemer , der opstår på mange områder (for eksempel inden for økonomi ).
Den vigtigste metode til at løse problemet med at optimere kvaliteten af kodning af lyd- og videoinformation for en given gennemsnitlig bithastighed (se Forvrængningsoptimering).

Se også

Litteratur

Akulich I.L. Kapitel 3. Problemer med ikke-lineær programmering // Matematisk programmering i eksempler og opgaver. - M . : Højere skole , 1986. - 319 s. — ISBN 5-06-002663-9 . .
Zorich V. A. Matematisk analyse. Del 1. - udg. 2. rev. og yderligere - M. : FAZIS, 1997.
Protasov V. Yu Maxima og minima i geometri . — M. : MTsNMO. — 56 s. - (Bibliotek "Matematisk uddannelse", hæfte 31).