Metode for Lagrange-multiplikatorer eksempler. Lagrange multiplikatormetode
Løsning. Finn ytterpunktet til funksjonen F(X) = 9 x 1 +x 1 2 +6 x 2 +x 2 2 ved å bruke Lagrange-funksjonen:
hvor
er den objektive funksjonen til vektoren.
- implisitte begrensninger (i=1..n)
Som objektiv funksjon, med forbehold om optimalisering, fungerer funksjonen i dette problemet:
F(X) = 9 x 1 + x 1 2 +6 x 2 + x 2 2
La oss omskrive begrensningen av problemet i en implisitt form:
Vi komponerer den ekstra Lagrange-funksjonen:
= 9 x 1 +x 1 2 +6 x 2 +x 2 2 + λ(x 1 +x 2 -150)
En nødvendig betingelse for ekstremumet til Lagrange-funksjonen er lik null av dens partielle deriverte med hensyn til variablene x i og en ubestemt multiplikator λ.
La oss lage et system:
∂L/∂x 1 = 2 x 1 +λ+9 = 0
∂L/∂x 2 = λ+2 x 2 +6 = 0
∂F/∂λ = x 1 + x 2 -150= 0
Vi løser systemet ved hjelp av Gauss-metoden eller ved hjelp av Cramers formler.
Vi skriver systemet på skjemaet: 
For enkelhets skyld bytter vi linjene: 
La oss legge til den andre linjen til den første:
Multipliser den andre raden med (2). Multipliser den tredje raden med (-1). La oss legge til den tredje linjen til den andre: 
Multipliser den andre raden med (-1). La oss legge til den andre linjen til den første: 
Fra 1. linje uttrykker vi x 3
Fra 2. linje uttrykker vi x 2
Fra den tredje linjen uttrykker vi x 1
Således, for at de totale produksjonskostnadene skal være minimale, er det nødvendig å produsere x 1 = 74,25; x2 = 75,75.
Trening. I henhold til produksjonsplanen må bedriften produsere 50 produkter. Disse produktene kan produseres på 2 teknologiske måter. Ved produksjon av x 1 - produkter i den første metoden er kostnadene 3x 1 + x 1 2 (tonn rubler), og ved produksjon av x 2 - produkter på den andre måten vil de være 5x 2 + x 2 2 (tonn rubler). Bestem hvor mange produkter hver av metodene må produseres slik at den totale produksjonskostnaden er minimal.
Løsning: komponer den objektive funksjonen og begrensningene:
F(X) = 3x 1 +x 1 2 + 5x 2 +x 2 2 → min
x 1 + x 2 = 50
an(t)z(n)(t) + an − 1(t)z(n − 1)(t) + ... + a1(t)z"(t) + a0(t)z(t) = f(t)
består i å erstatte vilkårlige konstanter ck i den generelle løsningen
z(t) = c1z1(t) + c2z2(t) + ...
Cnzn(t)
relevant homogen ligning
an(t)z(n)(t) + an − 1(t)z(n − 1)(t) + ... + a1(t)z"(t) + a0(t)z(t) = 0
til hjelpefunksjoner ck(t) hvis deriverte tilfredsstiller det lineære algebraiske systemet
Determinanten for system (1) er Wronskian av funksjonene z1,z2,...,zn, som sikrer dens unike løsebarhet med hensyn til .
Hvis er antiderivater for tatt ved faste verdier av integrasjonskonstantene, så er funksjonen
er en løsning på den opprinnelige lineære inhomogene differensialligningen. Integrering inhomogen ligning i nærvær av en generell løsning av den tilsvarende homogene ligningen, reduseres dermed til kvadraturer.
Lagrange-metoden (metode for variasjon av vilkårlige konstanter)
En metode for å oppnå en generell løsning til en inhomogen ligning, kjenne til den generelle løsningen av en homogen ligning uten å finne en spesiell løsning.
For en lineær homogen differensialligning av n-te orden
y(n) + a1(x) y(n-1) + ... + an-1 (x) y" + an(x) y = 0,
hvor y = y(x) er en ukjent funksjon, a1(x), a2(x), ..., an-1(x), an(x) er kjent, kontinuerlig, sann: 1) det er n lineært uavhengige løsninger ligninger y1(x), y2(x), ..., yn(x); 2) for alle verdier av konstantene c1, c2, ..., cn, er funksjonen y(x)= c1 y1(x) + c2 y2(x) + ... + cn yn(x) en løsning på ligningen; 3) for enhver startverdier x0, y0, y0,1, ..., y0,n-1 det er verdier c*1, c*n, ..., c*n slik at løsningen y*(x)=c*1 y1(x) + c*2 y2(x) + ... + c*n yn (x) tilfredsstiller for x = x0 Innledende forhold y*(x0)=y0, (y*)"(x0)=y0,1, ...,(y*)(n-1)(x0)=y0,n-1.
Uttrykket y(x)= c1 y1(x) + c2 y2(x) + ... + cn yn(x) kalles felles løsning lineær homogen differensialligning av n-te orden.
Settet med n lineært uavhengige løsninger av en lineær homogen differensialligning av n-te orden y1(x), y2(x), ..., yn(x) kalles det grunnleggende løsningssystemet til ligningen.
For en lineær homogen differensialligning med konstante koeffisienter det er en enkel algoritme for å konstruere et grunnleggende system av løsninger. Vi vil se etter en løsning på ligningen på formen y(x) = exp(lx): exp(lx)(n) + a1exp(lx)(n-1) + ... + an-1exp(lx) " + anexp(lx) = = (ln + a1ln-1 + ... + an-1l + an)exp(lx) = 0, dvs. tallet l er roten karakteristisk ligning ln + a1ln-1 + ... + an-1l + an = 0. Venstre side av den karakteristiske ligningen kalles det karakteristiske polynomet til en lineær differensialligning: P(l) = ln + a1ln-1 + ... + an-1l + an. Dermed er problemet med å løse en lineær homogen ligning av n-te orden med konstante koeffisienter redusert til å løse en algebraisk ligning.
Hvis den karakteristiske ligningen har n forskjellige reelle røtter l1№ l2 № ... № ln, så består det grunnleggende løsningssystemet av funksjonene y1(x) = exp(l1x), y2(x) = exp(l2x), . .., yn (x) = exp(lnx), og den generelle løsningen av den homogene ligningen er: y(x)= c1 exp(l1x) + c2 exp(l2x) + ... + cn exp(lnx).
et grunnleggende system av løsninger og en generell løsning for tilfellet med enkle reelle røtter.
Hvis noen av de reelle røttene til den karakteristiske ligningen gjentas r ganger (en r-fold rot), så tilsvarer r funksjoner det i det grunnleggende løsningssystemet; hvis lk=lk+1 = ... = lk+r-1, så inn grunnleggende system løsninger til ligningen, er det r funksjoner: yk(x) = exp(lkx), yk+1(x) = xexp(lkx), yk+2(x) = x2exp(lkx), ..., yk+ r-1(x)=xr-1exp(lnx).
EKSEMPEL 2. Grunnleggende system av løsninger og generell løsning for tilfellet med flere reelle røtter.
Hvis den karakteristiske ligningen har komplekse røtter, tilsvarer hvert par av enkle (av multiplisitet 1) komplekse røtter lk,k+1=ak ± ibk i det fundamentale løsningssystemet et funksjonspar yk(x) = exp(akx) cos(bkx), yk+ 1(x) = exp(akx)sin(bkx).
EKSEMPEL 4. Grunnleggende system av løsninger og generell løsning for tilfellet med enkle komplekse røtter. imaginære røtter.
Hvis et komplekst røtterpar har multiplisitet r, så tilsvarer et slikt par lk=lk+1 = ... = l2k+2r-1=ak ± ibk, i det fundamentale løsningssystemet funksjonene exp(akx)cos( bkx), exp(akx )sin(bkx), xexp(akx)cos(bkx), xexp(akx)sin(bkx), x2exp(akx)cos(bkx), x2exp(akx)sin(bkx), .. ...... ........ xr-1exp(akx)cos(bkx), xr-1exp(akx)sin(bkx).
EKSEMPEL 5. Grunnleggende system av løsninger og generell løsning for tilfellet med flere komplekse røtter.
For å finne en generell løsning på en lineær homogen differensialligning med konstante koeffisienter bør man altså: skrive ned den karakteristiske ligningen; finn alle røttene til den karakteristiske ligningen l1, l2, ... , ln; skriv ned det grunnleggende løsningssystemet y1(x), y2(x), ..., yn(x); skriv et uttrykk for den generelle løsningen y(x)= c1 y1(x) + c2 y2(x) + ... + cn yn(x). For å løse Cauchy-problemet, må vi erstatte uttrykket for den generelle løsningen i startbetingelsene og bestemme verdiene til konstantene c1,..., cn, som er løsninger av systemet med lineært algebraiske ligninger c1 y1(x0) + c2 y2(x0) + ... + cn yn(x0) = y0, c1 y"1(x0) + c2 y"2(x0) + ... + cn y"n(x0) ) =y0,1, ........... , c1 y1(n-1)(x0) + c2 y2(n-1)(x0) + ... + cn yn(n-1)( x0) = y0,n-1
For en lineær inhomogen differensialligning av n-te orden
y(n) + a1(x) y(n-1) + ... + an-1 (x) y" + an(x) y = f(x),
hvor y = y(x) er en ukjent funksjon, a1(x), a2(x), ..., an-1(x), an(x), f(x) er kjente, kontinuerlige, gyldige: 1 ) hvis y1(x) og y2(x) er to løsninger av en inhomogen ligning, så er funksjonen y(x) = y1(x) - y2(x) en løsning til den tilsvarende homogene ligningen; 2) hvis y1(x) er en løsning på en inhomogen ligning, og y2(x) er en løsning på den tilsvarende homogene ligningen, så er funksjonen y(x) = y1(x) + y2(x) en løsning på en inhomogen ligning; 3) hvis y1(x), y2(x), ..., yn(x) er n lineært uavhengige løsninger av den homogene ligningen, og ych(x) - vilkårlig avgjørelse ikke-homogen ligning, så for alle startverdier x0, y0, y0,1, ..., y0,n-1 er det verdier c*1, c*n, ..., c*n slik at løsning y*(x )=c*1 y1(x) + c*2 y2(x) + ... + c*n yn (x) + ych(x) tilfredsstiller for x = x0 startbetingelsene y*( x0)=y0, (y*)"(x0)=y0,1, ...,(y*)(n-1)(x0)=y0,n-1.
Uttrykket y(x)= c1 y1(x) + c2 y2(x) + ... + cn yn(x) + ych(x) kalles den generelle løsningen av en lineær inhomogen differensialligning av n-te orden.
For å finne spesielle løsninger av inhomogene differensiallikninger med konstante koeffisienter med høyre side av formen: Pk(x)exp(ax)cos(bx) + Qm(x)exp(ax)sin(bx), der Pk(x), Qm(x) er polynomer av grad k og m tilsvarende, er det en enkel algoritme for å konstruere en bestemt løsning, kalt seleksjonsmetoden.
Seleksjonsmetoden, eller metoden for usikre koeffisienter, er som følger. Den ønskede løsningen av ligningen skrives som: (Pr(x)exp(ax)cos(bx) + Qr(x)exp(ax)sin(bx))xs, hvor Pr(x), Qr(x) er polynomer av grad r = max(k, m) med ukjente koeffisienter pr , pr-1, ..., p1, p0, qr, qr-1, ..., q1, q0. Faktoren xs kalles resonansfaktoren. Resonans finner sted i tilfeller der det blant røttene til den karakteristiske ligningen er en rot l = a ± ib av multiplisitet s. De. hvis det blant røttene til den karakteristiske ligningen til den tilsvarende homogene ligningen er slik at dens reelle del faller sammen med koeffisienten i eksponenten, og den imaginære delen sammenfaller med koeffisienten i argumentet trigonometrisk funksjon på høyre side av ligningen, og multiplisiteten til denne roten er s, så er det i den ønskede spesielle løsningen en resonansfaktor xs. Hvis det ikke er en slik tilfeldighet (s=0), så er det ingen resonansfaktor.
Ved å erstatte uttrykket for den bestemte løsningen på venstre side av ligningen, får vi et generalisert polynom av samme form som polynomet på høyre side av ligningen, hvis koeffisienter er ukjente.
To generaliserte polynomer er like hvis og bare hvis koeffisientene til faktorer av formen xtexp(ax)sin(bx), xtexp(ax)cos(bx) med samme potenser av t er like. Ved å likestille koeffisientene til slike faktorer får vi et system med 2(r+1) lineære algebraiske ligninger i 2(r+1) ukjente. Det kan vises at et slikt system er konsistent og har en unik løsning.
|
Lagrange-metoden er en metode for å løse et problem betinget optimalisering, der begrensningene skrevet som implisitte funksjoner, kombineres med objektivfunksjonen i form av en ny ligning kalt Lagrangian.
Ta i betraktning spesielt tilfelle felles oppgave ikke lineær programmering:
Gitt system ikke-lineære ligninger (1):
(1) gi(x1,x2,…,xn)=bi (i=1..m),
Finn den minste (eller største) verdien av funksjonen (2)
(2) f (х1,х2,...,хn),
hvis det ikke er betingelser for ikke-negativitet til variablene og f(x1,x2,...,xn) og gi(x1,x2,...,xn) er funksjoner som er kontinuerlige sammen med deres partielle deriverte.
For å finne en løsning på dette problemet kan du søke følgende metode: 1. Et sett med variabler λ1, λ2,..., λm, kalt Lagrange-multiplikatorer, introduseres, og utgjør Lagrange-funksjonen (3)
(3) F(х1,х2,…,хn, λ1,λ2,...,λm) = f(х1,х2,...,хn)+ λi .
2. Finn de partielle deriverte av Lagrange-funksjonen med hensyn til variablene xi og λi og lig dem med null.
3. Løs ligningssystemet, finn punktene der den objektive funksjonen til problemet kan ha et ekstremum.
4. Blant punktene som er mistenkelige for ikke et ekstremum, finner de de der ekstremumet nås, og beregner funksjonens verdier ved disse punktene .
4. Sammenlign de oppnådde verdiene for funksjonen f og velg den beste.
I henhold til produksjonsplanen må bedriften produsere 180 produkter. Disse produktene kan produseres på to teknologiske måter. Ved produksjon av x1 produkter etter metode I er kostnadene 4 * x1 + x1 ^ 2 rubler, og ved produksjon av x2 produkter etter metode II er de 8 * x2 + x2 ^ 2 rubler. Bestem hvor mange produkter hver av måtene skal lages, slik at den totale produksjonskostnaden er minimal.
Løsning: Den matematiske formuleringen av problemet består i å bestemme den minste verdien av en funksjon av to variabler:
f = 4*x1+x1^2 +8*x2 +x2^2, gitt x1 +x2 = 180.
La oss komponere Lagrange-funksjonen:
F(x1,x2,λ) = 4*x1+x1^2+8*x2+x2^2+λ*(180-x1-x2).
Vi beregner partielle deriverte med hensyn til x1, x2, λ og likestiller dem til 0:
Vi overfører de to første likningene λ til høyresidene og setter likhetstegn mellom venstresidene deres, vi får 4 + 2*x1 = 8 + 2*x2, eller x1 − x2 = 2.
Løser vi den siste likningen sammen med likningen x1 + x2 = 180, finner vi x1 = 91, x2 = 89, det vil si at vi har en løsning som tilfredsstiller betingelsene:
La oss finne verdien av objektivfunksjonen f for disse verdiene av variabler:
F(x1, x2) = 17278
Dette punktet er mistenkelig for et ekstremum. Ved å bruke de andre partielle deriverte kan vi vise at ved punktet (91.89) har funksjonen f et minimum.
La oss først vurdere tilfellet med en funksjon av to variabler. Det betingede ekstremumet til funksjonen $z=f(x,y)$ ved punktet $M_0(x_0;y_0)$ er ekstremumet til denne funksjonen, nådd under forutsetning av at variablene $x$ og $y$ i nærhet til dette punktet tilfredsstiller begrensningsligningen $\ varphi(x,y)=0$.
Navnet "betinget" ekstremum skyldes det faktum at tilleggsbetingelsen $\varphi(x,y)=0$ er pålagt variablene. Hvis det er mulig å uttrykke en variabel i form av en annen fra forbindelsesligningen, reduseres problemet med å bestemme det betingede ekstremumet til problemet med det vanlige ekstremumet til en funksjon av en variabel. For eksempel, hvis $y=\psi(x)$ følger av begrensningsligningen, og deretter erstatte $y=\psi(x)$ med $z=f(x,y)$, får vi en funksjon av én variabel $ z=f\venstre (x,\psi(x)\høyre)$. PÅ generell sak, men denne metoden er til liten nytte, så en ny algoritme er nødvendig.
Metode for Lagrange-multiplikatorer for funksjoner av to variabler.
Metoden for Lagrange-multiplikatorer er at for å finne det betingede ekstremumet, er Lagrange-funksjonen sammensatt: $F(x,y)=f(x,y)+\lambda\varphi(x,y)$ (parameteren $\lambda $ kalles Lagrange-multiplikatoren ). De nødvendige ekstremumforholdene er gitt av et ligningssystem som de stasjonære punktene bestemmes fra:
$$ \venstre \( \begin(justert) & \frac(\delvis F)(\delvis x)=0;\\ & \frac(\delvis F)(\delvis y)=0;\\ & \varphi (x,y)=0.\end(justert)\høyre.$$
Tegnet $d^2 F=F_(xx)^("")dx^2+2F_(xy)^("")dxdy+F_(yy)^("")dy^2$. Hvis ved et stasjonært punkt $d^2F > 0$, så har funksjonen $z=f(x,y)$ et betinget minimum på dette punktet, men hvis $d^2F< 0$, то условный максимум.
Det er en annen måte å bestemme ekstremumets natur. Fra begrensningsligningen får vi: $\varphi_(x)^(")dx+\varphi_(y)^(")dy=0$, $dy=-\frac(\varphi_(x)^("))( \varphi_ (y)^("))dx$, så på et hvilket som helst stasjonært punkt har vi:
$$d^2 F=F_(xx)^("")dx^2+2F_(xy)^("")dxdy+F_(yy)^("")dy^2=F_(xx)^( "")dx^2+2F_(xy)^("")dx\left(-\frac(\varphi_(x)^("))(\varphi_(y)^("))dx\right)+ F_(åå)^("")\venstre(-\frac(\varphi_(x)^("))(\varphi_(y)^("))dx\høyre)^2=\\ =-\frac (dx^2)(\left(\varphi_(y)^(") \right)^2)\cdot\left(-(\varphi_(y)^("))^2 F_(xx)^(" ")+2\varphi_(x)^(")\varphi_(y)^(")F_(xy)^("")-(\varphi_(x)^("))^2 F_(yy)^ ("")\right)$$
Den andre faktoren (plassert i parentes) kan representeres i denne formen:
Elementer av $\left| \begin(array) (cc) F_(xx)^("") & F_(xy)^("") \\ F_(xy)^("") & F_(yy)^("") \end (array) \right|$ som er hessian av Lagrange-funksjonen. Hvis $H > 0$ så $d^2F< 0$, что указывает на условный максимум. Аналогично, при $H < 0$ имеем $d^2F >$0, dvs. vi har et betinget minimum av funksjonen $z=f(x,y)$.
Legg merke til formen til $H$-determinanten. Vis skjul
$$ H=-\left|\begin(array) (ccc) 0 & \varphi_(x)^(") & \varphi_(y)^(")\\ \varphi_(x)^(") & F_ (xx)^("") & F_(xy)^("") \\ \varphi_(y)^(") & F_(xy)^("") & F_(yy)^("") \ end(array) \right| $$
I denne situasjonen endres regelen formulert ovenfor som følger: hvis $H > 0$, så har funksjonen et betinget minimum, og for $H< 0$ получим условный максимум функции $z=f(x,y)$. При решении задач следует учитывать такие нюансы.
Algoritme for å studere en funksjon av to variabler for et betinget ekstremum
- Komponer Lagrange-funksjonen $F(x,y)=f(x,y)+\lambda\varphi(x,y)$
- Løs system $ \left \( \begin(aligned) & \frac(\partial F)(\partial x)=0;\\ & \frac(\partial F)(\partial y)=0;\\ & \ varphi(x,y)=0.\end(justert)\right.$
- Bestem arten av ekstremumet i hver av de som er funnet i forrige avsnitt stasjonære punkter. For å gjøre dette, bruk en av følgende metoder:
- Komponer determinanten $H$ og finn ut tegnet
- Regn ut tegnet på $d^2F$ ved å ta hensyn til begrensningsligningen
Lagrange multiplikatormetode for funksjoner av n variabler
Anta at vi har en funksjon av $n$ variablene $z=f(x_1,x_2,\ldots,x_n)$ og $m$ begrensningslikninger ($n > m$):
$$\varphi_1(x_1,x_2,\ldots,x_n)=0; \; \varphi_2(x_1,x_2,\ldots,x_n)=0,\ldots,\varphi_m(x_1,x_2,\ldots,x_n)=0.$$
Ved å angi Lagrange-multiplikatorene som $\lambda_1,\lambda_2,\ldots,\lambda_m$, komponerer vi Lagrange-funksjonen:
$$F(x_1,x_2,\ldots,x_n,\lambda_1,\lambda_2,\ldots,\lambda_m)=f+\lambda_1\varphi_1+\lambda_2\varphi_2+\ldots+\lambda_m\varphi_m$$
De nødvendige betingelsene for tilstedeværelsen av et betinget ekstremum er gitt av et system av ligninger hvorfra koordinatene til stasjonære punkter og verdiene til Lagrange-multiplikatorene er funnet:
$$\left\(\begin(aligned) & \frac(\partial F)(\partial x_i)=0; (i=\overline(1,n))\\ & \varphi_j=0; (j=\ overline(1,m)) \end(justert) \right.$$
Det er mulig å finne ut om en funksjon har et betinget minimum eller et betinget maksimum på det funnet punktet, som før, ved å bruke tegnet $d^2F$. Hvis ved det funnet punktet $d^2F > 0$, har funksjonen et betinget minimum, men hvis $d^2F< 0$, - то условный максимум. Можно пойти иным путем, рассмотрев следующую матрицу:
Matrisedeterminant $\venstre| \begin(array) (ccccc) \frac(\partial^2F)(\partial x_(1)^(2)) & \frac(\partial^2F)(\partial x_(1)\partial x_(2) ) & \frac(\partial^2F)(\partial x_(1)\partial x_(3)) &\ldots & \frac(\partial^2F)(\partial x_(1)\partial x_(n)) \\ \frac(\partial^2F)(\partial x_(2)\partial x_1) & \frac(\partial^2F)(\partial x_(2)^(2)) & \frac(\partial^2F )(\partial x_(2)\partial x_(3)) &\ldots & \frac(\partial^2F)(\partial x_(2)\partial x_(n))\\ \frac(\partial^2F) )(\partial x_(3) \partial x_(1)) & \frac(\partial^2F)(\partial x_(3)\partial x_(2)) & \frac(\partial^2F)(\partial x_(3)^(2)) &\ldots & \frac(\partial^2F)(\partial x_(3)\partial x_(n))\\ \ldots & \ldots & \ldots &\ldots & \ ldots\\ \frac(\partial^2F)(\partial x_(n)\partial x_(1)) & \frac(\partial^2F)(\partial x_(n)\partial x_(2)) & \ frac(\partial^2F)(\partial x_(n)\partial x_(3)) &\ldots & \frac(\partial^2F)(\partial x_(n)^(2))\\ \end( array) \right|$ uthevet i rødt i $L$-matrisen er Hessian av Lagrange-funksjonen. Vi bruker følgende regel:
- Hvis tegnene til de mindre hjørnene er $H_(2m+1),\; H_(2m+2),\ldots,H_(m+n)$ matriser $L$ sammenfaller med tegnet $(-1)^m$, da er det stasjonære punktet som studeres det betingede minimumspunktet for funksjonen $z =f(x_1,x_2,x_3,\ldots,x_n)$.
- Hvis tegnene til de mindre hjørnene er $H_(2m+1),\; H_(2m+2),\ldots,H_(m+n)$ veksler, og tegnet til moll $H_(2m+1)$ sammenfaller med tegnet til tallet $(-1)^(m+1 )$, så er det studerte stasjonære punktet det betingede maksimumspunktet for funksjonen $z=f(x_1,x_2,x_3,\ldots,x_n)$.
Eksempel #1
Finn det betingede ekstremumet til funksjonen $z(x,y)=x+3y$ under betingelsen $x^2+y^2=10$.
Den geometriske tolkningen av dette problemet er som følger: det kreves for å finne den største og minste verdi applikater av planet $z=x+3y$ for punktene i dets skjæringspunkt med sylinderen $x^2+y^2=10$.
Det er litt vanskelig å uttrykke en variabel i form av en annen fra begrensningsligningen og erstatte den med funksjonen $z(x,y)=x+3y$, så vi bruker Lagrange-metoden.
Ved å angi $\varphi(x,y)=x^2+y^2-10$, komponerer vi Lagrange-funksjonen:
$$ F(x,y)=z(x,y)+\lambda \varphi(x,y)=x+3y+\lambda(x^2+y^2-10);\\ \frac(\partial F)(\delvis x)=1+2\lambda x; \frac(\partial F)(\partial y)=3+2\lambda y. $$
La oss skrive ned likningssystemet for å bestemme de stasjonære punktene til Lagrange-funksjonen:
$$ \venstre \( \begin(justert) & 1+2\lambda x=0;\\ & 3+2\lambda y=0;\\ & x^2+y^2-10=0. \end (justert)\høyre.$$
Hvis vi antar $\lambda=0$, blir den første ligningen: $1=0$. Den resulterende motsetningen sier at $\lambda\neq 0$. Under betingelsen $\lambda\neq 0$, fra den første og andre ligningen har vi: $x=-\frac(1)(2\lambda)$, $y=-\frac(3)(2\lambda) $. Ved å erstatte de oppnådde verdiene i den tredje ligningen, får vi:
$$ \left(-\frac(1)(2\lambda) \right)^2+\left(-\frac(3)(2\lambda) \right)^2-10=0;\\ \frac (1)(4\lambda^2)+\frac(9)(4\lambda^2)=10; \lambda^2=\frac(1)(4); \venstre[ \begin(justert) & \lambda_1=-\frac(1)(2);\\ & \lambda_2=\frac(1)(2). \end(justert) \right.\\ \begin(aligned) & \lambda_1=-\frac(1)(2); \; x_1=-\frac(1)(2\lambda_1)=1; \; y_1=-\frac(3)(2\lambda_1)=3;\\ & \lambda_2=\frac(1)(2); \; x_2=-\frac(1)(2\lambda_2)=-1; \; y_2=-\frac(3)(2\lambda_2)=-3.\end(justert) $$
Så systemet har to løsninger: $x_1=1;\; y_1=3;\; \lambda_1=-\frac(1)(2)$ og $x_2=-1;\; y_2=-3;\; \lambda_2=\frac(1)(2)$. La oss finne ut naturen til ekstremumet ved hvert stasjonært punkt: $M_1(1;3)$ og $M_2(-1;-3)$. For å gjøre dette, beregner vi determinanten $H$ ved hvert av punktene.
$$ \varphi_(x)^(")=2x;\; \varphi_(y)^(")=2y;\; F_(xx)^("")=2\lambda;\; F_(xy)^("")=0;\; F_(åå)^("")=2\lambda.\\ H=\venstre| \begin(array) (ccc) 0 & \varphi_(x)^(") & \varphi_(y)^(")\\ \varphi_(x)^(") & F_(xx)^("") & F_(xy)^("") \\ \varphi_(y)^(") & F_(xy)^("") & F_(yy)^("") \end(array) \right|= \venstre| \begin(array) (ccc) 0 & 2x & 2y\\ 2x & 2\lambda & 0 \\ 2y & 0 & 2\lambda \end(array) \right|= 8\cdot\left| \begin(array) (ccc) 0 & x & y\\ x & \lambda & 0 \\ y & 0 & \lambda \end(array) \right| $$
Ved punktet $M_1(1;3)$ får vi: $H=8\cdot\left| \begin(array) (ccc) 0 & x & y\\ x & \lambda & 0 \\ y & 0 & \lambda \end(array) \right|= 8\cdot\left| \begin(array) (ccc) 0 & 1 & 3\\ 1 & -1/2 & 0 \\ 3 & 0 & -1/2 \end(array) \right|=40 > 0$, så ved punktet $M_1(1;3)$ funksjonen $z(x,y)=x+3y$ har et betinget maksimum, $z_(\max)=z(1;3)=10$.
På samme måte finner vi i punktet $M_2(-1;-3)$: $H=8\cdot\left| \begin(array) (ccc) 0 & x & y\\ x & \lambda & 0 \\ y & 0 & \lambda \end(array) \right|= 8\cdot\left| \begin(array) (ccc) 0 & -1 & -3\\ -1 & 1/2 & 0 \\ -3 & 0 & 1/2 \end(array) \right|=-40$. Siden $H< 0$, то в точке $M_2(-1;-3)$ имеем условный минимум функции $z(x,y)=x+3y$, а именно: $z_{\min}=z(-1;-3)=-10$.
Jeg legger merke til at i stedet for å beregne verdien av determinanten $H$ ved hvert punkt, er det mye mer praktisk å utvide den i generelt syn. For ikke å rote opp teksten med detaljer, vil jeg skjule denne metoden under et notat.
Determinant $H$ notasjon i generell form. Vis skjul
$$ H=8\cdot\left|\begin(array)(ccc)0&x&y\\x&\lambda&0\\y&0&\lambda\end(array)\right| =8\cdot\venstre(-\lambda(y^2)-\lambda(x^2)\høyre) =-8\lambda\cdot\venstre(y^2+x^2\høyre). $$
I prinsippet er det allerede åpenbart hvilket tegn $H$ har. Siden ingen av punktene $M_1$ eller $M_2$ sammenfaller med opprinnelsen, er $y^2+x^2>0$. Derfor er tegnet til $H$ motsatt av tegnet til $\lambda$. Du kan også fullføre beregningene:
$$ \begin(aligned) &H(M_1)=-8\cdot\left(-\frac(1)(2)\right)\cdot\left(3^2+1^2\right)=40;\ \ &H(M_2)=-8\cdot\frac(1)(2)\cdot\venstre((-3)^2+(-1)^2\høyre)=-40. \end(justert) $$
Spørsmålet om ekstremumets natur ved de stasjonære punktene $M_1(1;3)$ og $M_2(-1;-3)$ kan løses uten å bruke determinanten $H$. Finn tegnet på $d^2F$ ved hvert stasjonært punkt:
$$ d^2 F=F_(xx)^("")dx^2+2F_(xy)^("")dxdy+F_(yy)^("")dy^2=2\lambda \left( dx^2+dy^2\høyre) $$
Jeg legger merke til at notasjonen $dx^2$ betyr nøyaktig $dx$ hevet til andre potens, dvs. $\left(dx\right)^2$. Derfor har vi: $dx^2+dy^2>0$, så for $\lambda_1=-\frac(1)(2)$ får vi $d^2F< 0$. Следовательно, функция имеет в точке $M_1(1;3)$ условный максимум. Аналогично, в точке $M_2(-1;-3)$ получим условный минимум функции $z(x,y)=x+3y$. Отметим, что для определения знака $d^2F$ не пришлось учитывать связь между $dx$ и $dy$, ибо знак $d^2F$ очевиден без дополнительных преобразований. В следующем примере для определения знака $d^2F$ уже будет необходимо учесть связь между $dx$ и $dy$.
Svar: ved punktet $(-1;-3)$ har funksjonen et betinget minimum, $z_(\min)=-10$. Ved punktet $(1;3)$ har funksjonen et betinget maksimum, $z_(\max)=10$
Eksempel #2
Finn det betingede ekstremumet til funksjonen $z(x,y)=3y^3+4x^2-xy$ under betingelsen $x+y=0$.
Den første måten (metoden til Lagrange-multiplikatorer)
Ved å betegne $\varphi(x,y)=x+y$ komponerer vi Lagrange-funksjonen: $F(x,y)=z(x,y)+\lambda \varphi(x,y)=3y^3+4x ^2 -xy+\lambda(x+y)$.
$$ \frac(\delvis F)(\delvis x)=8x-y+\lambda; \; \frac(\delvis F)(\delvis y)=9y^2-x+\lambda.\\ \venstre \( \begin(justert) & 8x-y+\lambda=0;\\ & 9y^2-x+\ lambda=0;\\&x+y=0.\end(justert)\right.$$
Når vi løser systemet, får vi: $x_1=0$, $y_1=0$, $\lambda_1=0$ og $x_2=\frac(10)(9)$, $y_2=-\frac(10)(9) )$ , $\lambda_2=-10$. Vi har to stasjonære punkter: $M_1(0;0)$ og $M_2 \left(\frac(10)(9);-\frac(10)(9) \right)$. La oss finne ut naturen til ekstremumet ved hvert stasjonært punkt ved å bruke determinanten $H$.
$$ H=\venstre| \begin(array) (ccc) 0 & \varphi_(x)^(") & \varphi_(y)^(")\\ \varphi_(x)^(") & F_(xx)^("") & F_(xy)^("") \\ \varphi_(y)^(") & F_(xy)^("") & F_(yy)^("") \end(array) \right|= \venstre| \begin(array) (ccc) 0 & 1 & 1\\ 1 & 8 & -1 \\ 1 & -1 & 18y \end(array) \right|=-10-18y $$
Ved punkt $M_1(0;0)$ $H=-10-18\cdot 0=-10< 0$, поэтому $M_1(0;0)$ есть точка условного минимума функции $z(x,y)=3y^3+4x^2-xy$, $z_{\min}=0$. В точке $M_2\left(\frac{10}{9};-\frac{10}{9}\right)$ $H=10 >0$, så på dette tidspunktet har funksjonen et betinget maksimum, $z_(\max)=\frac(500)(243)$.
Vi undersøker naturen til ekstremumet ved hvert av punktene med en annen metode, basert på tegnet $d^2F$:
$$ d^2 F=F_(xx)^("")dx^2+2F_(xy)^("")dxdy+F_(yy)^("")dy^2=8dx^2-2dxdy+ 18ydy ^2 $$
Fra begrensningsligningen $x+y=0$ har vi: $d(x+y)=0$, $dx+dy=0$, $dy=-dx$.
$$ d^2 F=8dx^2-2dxdy+18ydy^2=8dx^2-2dx(-dx)+18y(-dx)^2=(10+18y)dx^2 $$
Siden $ d^2F \Bigr|_(M_1)=10 dx^2 > 0$, så er $M_1(0;0)$ det betingede minimumspunktet for funksjonen $z(x,y)=3y^3+ 4x^ 2-xy$. På samme måte, $d^2F \Bigr|_(M_2)=-10 dx^2< 0$, т.е. $M_2\left(\frac{10}{9}; -\frac{10}{9} \right)$ - точка условного максимума.
Andre vei
Fra begrensningsligningen $x+y=0$ får vi: $y=-x$. Ved å erstatte $y=-x$ i funksjonen $z(x,y)=3y^3+4x^2-xy$, får vi en funksjon av variabelen $x$. La oss betegne denne funksjonen som $u(x)$:
$$ u(x)=z(x,-x)=3\cdot(-x)^3+4x^2-x\cdot(-x)=-3x^3+5x^2. $$
Dermed reduserte vi problemet med å finne det betingede ekstremumet til en funksjon av to variabler til problemet med å bestemme ekstremumet til en funksjon av en variabel.
$$ u_(x)^(")=-9x^2+10x;\\ -9x^2+10x=0; \; x\cdot(-9x+10)=0;\\ x_1=0; \ ;y_1=-x_1=0;\\ x_2=\frac(10)(9);\;y_2=-x_2=-\frac(10)(9).$$
Fikk poeng $M_1(0;0)$ og $M_2\left(\frac(10)(9); -\frac(10)(9)\right)$. Videre forskning kjent fra kurset differensialregning funksjoner til én variabel. Ved å undersøke tegnet til $u_(xx)^("")$ ved hvert stasjonært punkt eller sjekke fortegnsendringen til $u_(x)^(")$ ved de funnet punktene, får vi de samme konklusjonene som i den første løsningen . Kontroller for eksempel tegnet $u_(xx)^("")$:
$$u_(xx)^("")=-18x+10;\\ u_(xx)^("")(M_1)=10;\;u_(xx)^("")(M_2)=- 10,$$
Siden $u_(xx)^("")(M_1)>0$, så er $M_1$ minimumspunktet for funksjonen $u(x)$, mens $u_(\min)=u(0)=0 $ . Siden $u_(xx)^("")(M_2)<0$, то $M_2$ - точка максимума функции $u(x)$, причём $u_{\max}=u\left(\frac{10}{9}\right)=\frac{500}{243}$.
Verdiene til funksjonen $u(x)$ under den gitte tilkoblingsbetingelsen faller sammen med verdiene til funksjonen $z(x,y)$, dvs. de funnet ytterpunktene til funksjonen $u(x)$ er de ønskede betingede ekstrema av funksjonen $z(x,y)$.
Svar: ved punktet $(0;0)$ har funksjonen et betinget minimum, $z_(\min)=0$. Ved punktet $\left(\frac(10)(9); -\frac(10)(9) \right)$ har funksjonen et betinget maksimum, $z_(\max)=\frac(500)(243) )$.
La oss se på et eksempel til, der vi finner ut hva ekstremumet er ved å bestemme tegnet $d^2F$.
Eksempel #3
Finn maksimums- og minimumsverdiene for funksjonen $z=5xy-4$ hvis variablene $x$ og $y$ er positive og tilfredsstiller begrensningsligningen $\frac(x^2)(8)+\frac( y^2)(2) -1=0$.
Komponer Lagrange-funksjonen: $F=5xy-4+\lambda \left(\frac(x^2)(8)+\frac(y^2)(2)-1 \right)$. Finn de stasjonære punktene til Lagrange-funksjonen:
$$ F_(x)^(")=5y+\frac(\lambda x)(4); \; F_(y)^(")=5x+\lambda y.\\ \venstre \( \begin(justert) & 5y+\frac(\lambda x)(4)=0;\\ & 5x+\lambda y=0;\\ & \frac(x^2)(8)+\frac(y^2)(2)- 1=0;\\ & x > 0; \; y > 0. \end(justert) \right.$$
Alle videre transformasjoner utføres under hensyntagen til $x > 0; \; y > 0$ (dette er fastsatt i tilstanden til problemet). Fra den andre ligningen uttrykker vi $\lambda=-\frac(5x)(y)$ og erstatter den funnet verdien i den første ligningen: $5y-\frac(5x)(y)\cdot \frac(x)( 4)=0$ , $4y^2-x^2=0$, $x=2y$. Ved å erstatte $x=2y$ i den tredje ligningen, får vi: $\frac(4y^2)(8)+\frac(y^2)(2)-1=0$, $y^2=1$, $y =1$.
Siden $y=1$, deretter $x=2$, $\lambda=-10$. Naturen til ekstremumet ved punktet $(2;1)$ bestemmes fra tegnet $d^2F$.
$$ F_(xx)^("")=\frac(\lambda)(4); \; F_(xy)^("")=5; \; F_(åå)^("")=\lambda. $$
Siden $\frac(x^2)(8)+\frac(y^2)(2)-1=0$, så:
$$ d\left(\frac(x^2)(8)+\frac(y^2)(2)-1\right)=0; \; d\venstre(\frac(x^2)(8) \right)+d\left(\frac(y^2)(2) \right)=0; \; \frac(x)(4)dx+ydy=0; \; dy=-\frac(xdx)(4y). $$
I prinsippet kan du her umiddelbart erstatte koordinatene til det stasjonære punktet $x=2$, $y=1$ og parameteren $\lambda=-10$, og dermed oppnå:
$$ F_(xx)^("")=\frac(-5)(2); \; F_(xy)^("")=-10; \; dy=-\frac(dx)(2).\\ d^2 F=F_(xx)^("")dx^2+2F_(xy)^("")dxdy+F_(yy)^(" ")dy^2=-\frac(5)(2)dx^2+10dx\cdot \left(-\frac(dx)(2) \right)-10\cdot \left(-\frac(dx) (2) \right)^2=\\ =-\frac(5)(2)dx^2-5dx^2-\frac(5)(2)dx^2=-10dx^2. $$
Men i andre problemer for et betinget ekstremum kan det være flere stasjonære punkter. I slike tilfeller er det bedre å representere $d^2F$ i en generell form, og deretter erstatte koordinatene til hvert av de funnet stasjonære punktene i det resulterende uttrykket:
$$ d^2 F=F_(xx)^("")dx^2+2F_(xy)^("")dxdy+F_(yy)^("")dy^2=\frac(\lambda) (4)dx^2+10\cdot dx\cdot \frac(-xdx)(4y) +\lambda\cdot \left(-\frac(xdx)(4y) \right)^2=\\ =\frac (\lambda)(4)dx^2-\frac(5x)(2y)dx^2+\lambda \cdot \frac(x^2dx^2)(16y^2)=\venstre(\frac(\lambda) )(4)-\frac(5x)(2y)+\frac(\lambda \cdot x^2)(16y^2) \right)\cdot dx^2 $$
Ved å erstatte $x=2$, $y=1$, $\lambda=-10$ får vi:
$$ d^2 F=\venstre(\frac(-10)(4)-\frac(10)(2)-\frac(10 \cdot 4)(16) \right)\cdot dx^2=- 10dx^2. $$
Siden $d^2F=-10\cdot dx^2< 0$, то точка $(2;1)$ есть точкой условного максимума функции $z=5xy-4$, причём $z_{\max}=10-4=6$.
Svar: ved punktet $(2;1)$ har funksjonen et betinget maksimum, $z_(\max)=6$.
I neste del tar vi for oss bruken av Lagrange-metoden for funksjoner mer variabler.
Kort teori
Lagrange multiplikatormetoden er en klassisk metode for å løse problemer matematisk programmering(spesielt konveks). Dessverre kl praktisk anvendelse Metoden kan støte på betydelige beregningsvansker, noe som begrenser omfanget av bruken. Vi vurderer her Lagrange-metoden hovedsakelig fordi det er et apparat som aktivt brukes for å underbygge ulike moderne numeriske metoder mye brukt i praksis. Når det gjelder Lagrange-funksjonen og Lagrange-multiplikatorene, spiller de en uavhengig og eksklusivt viktig rolle i teori og applikasjoner ikke bare matematisk programmering.
Ta i betraktning klassisk problem optimaliseringer:
Blant begrensningene for dette problemet er det ingen ulikheter, det er ingen betingelser for ikke-negativiteten til variablene, deres diskretitet og funksjonene og er kontinuerlige og har partielle derivater av minst andre orden.
Den klassiske tilnærmingen til å løse problemet gir et system av ligninger ( nødvendige forhold), som må tilfredsstilles av punktet som gir funksjonen et lokalt ekstremum på settet med punkter som tilfredsstiller begrensningene (for et konveks programmeringsproblem vil det funnet punktet også være et globalt ekstremum).
La oss anta at funksjon (1) har et lokalt betinget ekstremum på punktet og rangeringen av matrisen er lik . Deretter kan de nødvendige betingelsene skrives som:
er Lagrange-funksjonen; er Lagrange-multiplikatorene.
Det er også tilstrekkelige forhold, hvorunder løsningen av ligningssystemet (3) bestemmer ekstremumpunktet til funksjonen . Dette spørsmålet er løst på grunnlag av studiet av tegnet til den andre differensialen til Lagrange-funksjonen. Tilstrekkelige forhold er imidlertid hovedsakelig av teoretisk interesse.
Du kan spesifisere følgende prosedyre for å løse problem (1), (2) ved hjelp av Lagrange multiplikatormetoden:
1) komponer Lagrange-funksjonen (4);
2) finn de partielle deriverte av Lagrange-funksjonen med hensyn til alle variabler og lig dem
null. Dermed vil man få et system (3) bestående av ligninger Løs det resulterende systemet (hvis det viser seg å være mulig!) og finn dermed alle de stasjonære punktene til Lagrange-funksjonen;
3) fra stasjonære punkter tatt uten koordinater, velg punkter der funksjonen har betingede lokale ekstremer i nærvær av restriksjoner (2). Dette valget gjøres for eksempel ved å bruke tilstrekkelige betingelser lokalt ekstremum. Ofte forenkles studien hvis spesifikke forhold ved problemet brukes.
Eksempel på problemløsning
Oppgaven
Firmaet produserer to typer varer i mengder og . Den nyttige kostnadsfunksjonen er definert av relasjonen. Prisene på disse varene i markedet er like og hhv.
Bestem ved hvilke produksjonsvolumer maksimal fortjeneste oppnås og hva den er lik hvis de totale kostnadene ikke overstiger
Har du problemer med å forstå løsningsprosessen? Siden har en tjeneste Løse problemer ved metoder for optimale løsninger på bestilling
Løsningen på problemet
Økonomisk og matematisk modell av problemet
Fortjenestefunksjon:
Kostnadsgrenser:
Vi får følgende økonomiske og matematiske modell:
I tillegg, i henhold til oppgavens betydning
Lagrange multiplikatormetode
La oss komponere Lagrange-funksjonen:
Vi finner partielle deriverte av 1. orden:
Vi komponerer og løser ligningssystemet:
Siden da
Maksimal fortjeneste:
Svar
Dermed er det nødvendig å produsere enheter. varer av 1. type og enheter. varer av 2. type. I dette tilfellet vil fortjenesten være maksimal og vil være 270.
Et eksempel på å løse problemet med kvadratisk konveks programmering ved hjelp av en grafisk metode er gitt.
Løse et lineært problem med en grafisk metode
Ansett grafisk metode løse et lineært programmeringsproblem (LPP) med to variabler. På eksemplet med oppgaven, Detaljert beskrivelse bygge en tegning og finne en løsning.
Wilsons lagerstyringsmodell
På eksemplet med å løse problemet, vurderes hovedmodellen for lagerstyring (Wilson-modellen). Beregnet slike indikatorer på modellen som optimal størrelse bestillingspartier, årlige lagringskostnader, leveringsintervall og bestillingspunkt.
Direkte kostnadsforholdsmatrise og input-output matrise
På eksemplet med å løse problemet, vurderes Leontiev intersektorielle modell. Beregningen av matrisen av koeffisienter for direkte materialkostnader, matrisen "input-output", matrisen av koeffisienter for indirekte kostnader, vektorene for sluttforbruk og brutto produksjon er vist.
Oratorium som en prototype på journalistikk
Sitater om Napoleon - dslinkov — LiveJournal
Meg hevn Mannen på bulldoseren ødela byen