Metoda za određivanje uslovnog ekstremuma počinje konstruisanjem pomoćne Lagrangeove funkcije, koja u području izvodljivih rješenja dostiže maksimum za iste vrijednosti varijabli x 1 , x 2 , ..., x n , što je isto što i ciljna funkcija z . Neka je riješen problem određivanja uslovnog ekstremuma funkcije z = f(X) pod ograničenjima φ i ( x 1 , x 2 , ..., x n ) = 0, i = 1, 2, ..., m , m < n
Sastavimo funkciju
koji se zove Lagrangeova funkcija. X , - konstantni faktori ( Lagrangeovi množitelji). Imajte na umu da se Lagrangeovim množiteljima može dati ekonomsko značenje. Ako f(x 1 , x 2 , ..., x n ) - prihod u skladu sa planom X = (x 1 , x 2 , ..., x n ) , i funkciju φ i (x 1 , x 2 , ..., x n ) - troškovi i-tog resursa koji odgovara ovom planu, zatim X , je cijena (procjena) i-tog resursa, koja karakterizira promjenu ekstremne vrijednosti ciljne funkcije u zavisnosti od promjene veličine i-tog resursa (marginalna procjena). L(X) - funkcija n+m varijable (x 1 , x 2 , ..., x n , λ 1 , λ 2 , ..., λ n ) . Određivanje stacionarnih tačaka ove funkcije dovodi do rješavanja sistema jednačina
|
|
Lako je to vidjeti
. Dakle, zadatak pronalaženja uslovnog ekstremuma funkcije z = f(X)
svodi se na pronalaženje lokalnog ekstremuma funkcije L(X)
. Ako se pronađe stacionarna tačka, onda se pitanje postojanja ekstrema u najjednostavnijim slučajevima rješava na osnovu dovoljnih uvjeta za ekstrem - proučavanjem predznaka drugog diferencijala d
2
L(X)
u stacionarnoj tački, pod uslovom da se varijabla povećava Δx
i
- povezani odnosima
|
|
dobijeno diferenciranjem jednadžbi sprege.
Rješavanje sistema nelinearnih jednačina u dvije nepoznate pomoću alata Find Solution
Postavke Pronalaženje rješenja omogućava vam da pronađete rješenje za sistem nelinearnih jednačina sa dvije nepoznanice:
Gdje 
- nelinearna funkcija varijabli x
I
y
,
- proizvoljna konstanta.
Poznato je da je par ( x , y ) je rješenje sistema jednadžbi (10) ako i samo ako je rješenje sljedeće jednačine sa dvije nepoznanice:
WITH s druge strane, rješenje sistema (10) je presjek dvije krive: f ] (x, y) = C I f 2 (x, y) = C 2 na površini XOY.
Ovo dovodi do metode za pronalaženje korijena sistema. nelinearne jednadžbe:
Odrediti (barem približno) interval postojanja rješenja sistema jednačina (10) ili jednačine (11). Ovdje je potrebno uzeti u obzir vrstu jednačina uključenih u sistem, domen definicije svake njihove jednačine, itd. Ponekad se koristi izbor početne aproksimacije rješenja;
Tablični prikaz rješenja jednadžbe (11) za varijable x i y na odabranom intervalu ili konstruirajte grafove funkcija f 1 (x, y) = C, i f 2 (x,y) = C 2 (sistem(10)).
Lokalizirajte pretpostavljene korijene sistema jednadžbi - pronađite nekoliko minimalnih vrijednosti iz tabele koja tabelarno prikazuje korijene jednadžbe (11), ili odredite točke presjeka krivulja uključenih u sistem (10).
4. Pomoću dodatka pronađite korijene za sistem jednačina (10). Pronalaženje rješenja.
Lagrangeova metoda množenja.
Lagrangeova metoda množitelja je jedna od metoda koja vam omogućava da riješite probleme nelinearnog programiranja.
Nelinearno programiranje je grana matematičkog programiranja koja proučava metode za rješavanje ekstremnih problema s nelinearnom ciljnom funkcijom i područjem izvodljivih rješenja definiranih nelinearnim ograničenjima. U ekonomiji to odgovara činjenici da se rezultati (efikasnost) povećavaju ili smanjuju nesrazmjerno promjenama u obimu korištenja resursa (ili, što je isto, obima proizvodnje): na primjer, zbog podjele troškova proizvodnje u preduzeća na varijabilna i polufiksna; zbog zasićenja potražnje za robom, kada je svaku narednu jedinicu teže prodati od prethodne itd.
Problem nelinearnog programiranja se postavlja kao problem nalaženja optimuma određene ciljne funkcije
F(x 1 ,…x n), F (x) → max
kada se steknu uslovi
g j (x 1 ,…x n)≥0, g (x) ≤ b , x ≥ 0
Gdje x-vektor traženih varijabli;
F (x) -objektivna funkcija;
g (x) - funkcija ograničenja (kontinuirano diferencibilna);
b - vektor konstanti ograničenja.
Rješenje problema nelinearnog programiranja (globalni maksimum ili minimum) može pripadati ili granici ili unutrašnjosti dopuštenog skupa.
Za razliku od problema linearnog programiranja, u problemu nelinearnog programiranja optimum ne leži nužno na granici područja definiranog ograničenjima. Drugim riječima, zadatak je odabrati takve nenegativne vrijednosti varijabli, podložne sistemu ograničenja u obliku nejednakosti, pod kojima se postiže maksimum (ili minimum) date funkcije. U ovom slučaju, oblici ni ciljne funkcije ni nejednakosti nisu specificirani. Mogu postojati različiti slučajevi: funkcija cilja je nelinearna, ali ograničenja su linearna; ciljna funkcija je linearna, a ograničenja (barem jedno od njih) su nelinearna; i ciljna funkcija i ograničenja su nelinearni.
Problem nelinearnog programiranja nalazi se u prirodnim naukama, inženjerstvu, ekonomiji, matematici, poslovnim odnosima i vladi.
Nelinearno programiranje, na primjer, povezano je sa osnovnim ekonomskim problemom. Dakle, u problemu alokacije ograničenih resursa, ili efikasnost ili, ako se proučava potrošač, potrošnja je maksimizirana uz prisustvo ograničenja koja izražavaju uslove oskudice resursa. U takvoj opštoj formulaciji, matematička formulacija problema može biti nemoguća, ali u specifičnim primenama kvantitativni oblik svih funkcija može se odrediti direktno. Na primjer, industrijsko poduzeće proizvodi plastične proizvode. Efikasnost proizvodnje se ovdje mjeri profitom, a ograničenja se tumače kao raspoloživa radna snaga, proizvodni prostor, produktivnost opreme itd.
Metoda isplativosti se takođe uklapa u šemu nelinearnog programiranja. Ova metoda je razvijena za korištenje u donošenju odluka u vladi. Uobičajena funkcija efikasnosti je dobrobit. Ovdje se javljaju dva problema nelinearnog programiranja: prvi je maksimiziranje efekta uz ograničene troškove, drugi je minimiziranje troškova pod uvjetom da je učinak iznad određenog minimalnog nivoa. Ovaj problem se obično dobro modelira korištenjem nelinearnog programiranja.
Rezultati rješavanja problema nelinearnog programiranja pomažu u donošenju vladinih odluka. Rezultirajuće rješenje se, naravno, preporučuje, pa je prije donošenja konačne odluke potrebno ispitati pretpostavke i tačnost problema nelinearnog programiranja.
Nelinearni problemi su složeni; često se pojednostavljuju dovodeći do linearnih. Da bi se to postiglo, konvencionalno se pretpostavlja da se u određenom području ciljna funkcija povećava ili smanjuje proporcionalno promjeni nezavisnih varijabli. Ovaj pristup se naziva metodom komadno linearnih aproksimacija, ali je primjenjiv samo na određene vrste nelinearnih problema.
Nelinearni problemi pod određenim uvjetima rješavaju se pomoću Lagrangeove funkcije: pronalaženjem njene sedla, na taj način se pronalazi rješenje problema. Među računskim algoritmima za naučna istraživanja, gradijentne metode zauzimaju veliko mjesto. Ne postoji univerzalna metoda za nelinearne probleme i, očigledno, možda i ne postoji, jer su izuzetno raznoliki. Posebno je teško riješiti multiekstremne probleme.
Jedna od metoda koja vam omogućava da problem nelinearnog programiranja svedete na rješavanje sistema jednačina je Lagrangeova metoda neodređenih množitelja.
Koristeći Lagrangeovu metodu množitelja, u suštini se uspostavljaju neophodni uslovi koji omogućavaju identifikaciju optimalnih tačaka u problemima optimizacije sa ograničenjima jednakosti. U ovom slučaju, ograničeni problem se transformira u ekvivalentan bezuvjetni optimizacijski problem, koji uključuje neke nepoznate parametre koji se nazivaju Lagrangeovi množitelji.
Metoda Lagrangeovog množitelja sastoji se u svođenju problema na uslovnom ekstremumu na probleme na bezuslovnom ekstremumu pomoćne funkcije - tzv. Lagrangeove funkcije.
Za problem ekstremuma funkcije f(x 1, x 2,..., x n) pod uslovima (jednačine ograničenja) φ i(x 1 , x 2 , ..., x n) = 0, i= 1, 2,..., m, Lagrangeova funkcija ima oblik
L(x 1, x 2… x n,λ 1, λ 2,…λm)=f(x 1, x 2… x n)+∑ i -1 m λ i φ i (x 1, x 2… x n)
Multiplikatori λ 1 , λ 2 , ..., λm pozvao Lagrangeovi množitelji.
Ako vrijednosti x 1 , x 2 , ..., x n , λ 1 , λ 2 , ..., λm suština rješenja jednadžbi koje određuju stacionarne točke Lagrangeove funkcije, naime, za diferencijabilne funkcije su rješenja sistema jednadžbi
onda, pod prilično opštim pretpostavkama, x 1 , x 2 , ..., x n daju ekstremum funkcije f.
Razmotrimo problem minimiziranja funkcije od n varijabli koje podliježu jednom ograničenju u obliku jednakosti:
Minimiziraj f(x 1, x 2… x n) (1)
pod ograničenjima h 1 (x 1, x 2… x n)=0 (2)
Prema metodi množitelja Lagrangea, ovaj problem se transformira u sljedeći problem neograničene optimizacije:
minimizirati L(x,λ)=f(x)-λ*h(x) (3)
gdje se funkcija L(x;λ) naziva Lagrangeova funkcija,
λ je nepoznata konstanta, koja se zove Lagrangeov množitelj. Ne postoje zahtjevi za predznak λ.
Neka se za datu vrijednost λ=λ 0 bezuslovni minimum funkcije L(x,λ) u odnosu na x postigne u tački x=x 0 i x 0 zadovoljava jednadžbu h 1 (x 0)=0 . Tada, kao što je lako vidjeti, x 0 minimizira (1) uzimajući u obzir (2), budući da za sve vrijednosti x koje zadovoljavaju (2), h 1 (x)=0 i L(x,λ)=min f(x).
Naravno, potrebno je odabrati vrijednost λ=λ 0 tako da koordinata bezuslovne minimalne tačke x 0 zadovoljava jednakost (2). Ovo se može učiniti ako se, smatrajući λ kao varijabla, pronađe bezuslovni minimum funkcije (3) u obliku funkcije λ, a zatim izabere vrijednost λ pri kojoj je jednakost (2) zadovoljena. Ilustrujmo to konkretnim primjerom.
Minimizirajte f(x)=x 1 2 +x 2 2 =0
pod ograničenjem h 1 (x)=2x 1 +x 2 -2=0=0
Odgovarajući problem neograničene optimizacije piše se na sljedeći način:
minimizirati L(x,λ)=x 1 2 +x 2 2 -λ(2x 1 +x 2 -2)
Rješenje. Izjednačavajući dvije komponente gradijenta L sa nulom, dobijamo
→ x 1 0 =λ
→ x 2 0 =λ/2
Da bismo provjerili da li stacionarna tačka x° odgovara minimumu, izračunavamo elemente Hesove matrice funkcije L(x;u), koja se smatra funkcijom od x,
što se ispostavilo kao pozitivno definitivno.
To znači da je L(x,u) konveksna funkcija od x. Prema tome, koordinate x 1 0 =λ, x 2 0 =λ/2 određuju globalnu minimalnu tačku. Optimalna vrijednost λ nalazi se zamjenom vrijednosti x 1 0 i x 2 0 u jednačinu 2x 1 + x 2 =2, iz koje je 2λ+λ/2=2 ili λ 0 =4/5. Dakle, uslovni minimum se postiže pri x 1 0 =4/5 i x 2 0 =2/5 i jednak je min f(x) = 4/5.
Prilikom rješavanja primjera problema, L(x;λ) smo razmatrali kao funkciju dvije varijable x 1 i x 2 i uz to pretpostavili da je vrijednost parametra λ odabrana tako da je ograničenje zadovoljeno. Ako je rješenje sistema
J=1,2,3,…,n
λ se ne može dobiti u obliku eksplicitnih funkcija, tada se vrijednosti x i λ nalaze rješavanjem sljedećeg sistema koji se sastoji od n+1 jednadžbi sa n+1 nepoznatih:
J=1,2,3,…,n., h 1 (x)=0
Da biste pronašli sva moguća rješenja za dati sistem, možete koristiti numeričke metode pretraživanja (na primjer, Newtonov metod). Za svako od rješenja (), trebali bismo izračunati elemente Hessiove matrice funkcije L, smatranu funkcijom od x, i saznati da li je ova matrica pozitivno određena (lokalni minimum) ili negativno određena (lokalni maksimum ).
Metoda Lagrangeovog množitelja može se proširiti na slučaj kada problem ima nekoliko ograničenja u obliku jednakosti. Razmotrite opšti problem koji zahteva
Minimiziraj f(x)
pod ograničenjima h k =0, k=1, 2, ..., K.
Lagrangeova funkcija ima sljedeći oblik:
Evo λ 1 , λ 2 , ..., λk-Lagranžovi množitelji, tj. nepoznati parametri čije vrijednosti treba odrediti. Izjednačavanjem parcijalnih izvoda od L u odnosu na x na nulu, dobijamo sljedeći sistem od n jednačina sa n nepoznatih:
Ako se pokaže da je teško pronaći rješenje za gornji sistem u obliku funkcija vektora λ, onda možete proširiti sistem uključivanjem ograničenja u obliku jednakosti
Rješenje proširenog sistema, koji se sastoji od n + K jednadžbi sa n + K nepoznatih, određuje stacionarnu tačku funkcije L. Zatim se implementira postupak provjere minimuma ili maksimuma koji se provodi na osnovu izračunavanja elementi Hesove matrice funkcije L, posmatrani kao funkcija od x, slično kao što je urađeno u slučaju problema sa jednim ograničenjem. Za neke probleme, prošireni sistem od n+K jednačina sa n+K nepoznatih možda neće imati rješenja, a metoda Lagrangeovog množitelja se ispostavi da je neprimjenjiva. Međutim, treba napomenuti da su takvi zadaci prilično rijetki u praksi.
Razmotrimo poseban slučaj opšteg problema nelinearnog programiranja, pod pretpostavkom da sistem ograničenja sadrži samo jednačine, ne postoje uslovi za nenegativnost varijabli i i i su kontinuirane funkcije zajedno sa njihovim parcijalnim derivatima. Dakle, rješavanjem sistema jednadžbi (7) dobijamo sve tačke u kojima funkcija (6) može imati ekstremne vrijednosti.
Algoritam za Lagrangeovu metodu množitelja
1. Sastavite Lagrangeovu funkciju.
2. Naći parcijalne izvode Lagrangeove funkcije u odnosu na varijable x J ,λ i i izjednačiti ih sa nulom.
3. Rješavamo sistem jednačina (7), nalazimo tačke u kojima ciljna funkcija problema može imati ekstrem.
4. Među tačkama sumnjivim za ekstrem, nalazimo one u kojima je ekstremum dostignut i izračunavamo vrednosti funkcije (6) u tim tačkama.
Primjer.
Početni podaci: Prema planu proizvodnje, preduzeće treba da proizvede 180 proizvoda. Ovi proizvodi se mogu proizvoditi na dva tehnološka načina. Prilikom proizvodnje x 1 proizvoda po 1. metodi, troškovi su 4x 1 +x 1 2 rublje, a kod proizvodnje x 2 proizvoda po 2. metodi oni su 8x 2 +x 2 2 rublje. Odredite koliko proizvoda treba proizvesti korištenjem svake metode kako bi troškovi proizvodnje bili minimalni.
Funkcija cilja za navedeni problem ima oblik
® min pod uslovima x 1 + x 2 =180, x 2 ≥0.
1. Sastavite Lagrangeovu funkciju
.
2.
Izračunavamo parcijalne derivate u odnosu na x 1, x 2, λ i izjednačavamo ih sa nulom: 
3.
Rješavajući rezultujući sistem jednačina, nalazimo x 1 =91,x 2 =89
4. Nakon što smo izvršili zamjenu u funkciji cilja x 2 =180-x 1, dobijamo funkciju jedne varijable, odnosno f 1 =4x 1 +x 1 2 +8(180-x 1)+(180-x 1 ) 2
Računamo ili 4x 1 -364=0 ,
odakle imamo x 1 * =91, x 2 * =89.
Odgovor: Broj proizvoda proizvedenih po prvoj metodi je x 1 =91, po drugoj metodi x 2 =89, dok je vrijednost funkcije cilja jednaka 17.278 rubalja.
Metoda množenjaLagrange(u engleskoj literaturi “LaGrangeova metoda neodređenih množitelja”) ˗ je numerička metoda za rješavanje problema optimizacije koja vam omogućava da odredite “uslovni” ekstremum funkcije cilja (minimalna ili maksimalna vrijednost)
u prisustvu određenih ograničenja na njegove varijable u obliku jednakosti (tj. definiran je raspon dozvoljenih vrijednosti)
˗ ovo su vrijednosti argumenta funkcije (kontroliranih parametara) na realnoj domeni u kojoj vrijednost funkcije teži ekstremumu. Upotreba naziva "uslovni" ekstrem je posljedica činjenice da se na varijable nameće dodatni uvjet, koji ograničava raspon dopuštenih vrijednosti pri traženju ekstremuma funkcije.
Metoda Lagrangeovog množitelja omogućava da se problem traženja uvjetnog ekstrema ciljne funkcije na skupu dopuštenih vrijednosti transformiše u problem bezuvjetne optimizacije funkcije.
U slučaju funkcija 
I 
su kontinuirane zajedno sa svojim parcijalnim derivatima, onda postoje takve varijable λ koje nisu istovremeno jednake nuli, pod kojima je zadovoljen sljedeći uvjet:
Dakle, u skladu sa metodom Lagrangeovog množitelja, za pronalaženje ekstrema ciljne funkcije na skupu dozvoljenih vrijednosti, sastavljam Lagrangeovu funkciju L(x, λ), koja se dalje optimizira:
gdje je λ ˗ vektor dodatnih varijabli koje se nazivaju neodređeni Lagrangeovi množitelji.
Dakle, problem nalaženja uslovnog ekstremuma funkcije f(x) sveden je na problem nalaženja bezuslovnog ekstremuma funkcije L(x, λ).
I 
Neophodan uslov za ekstremum Lagranžove funkcije je dat sistemom jednačina (sistem se sastoji od “n + m” jednačina):
Rješavanje ovog sistema jednadžbi omogućava nam da odredimo argumente funkcije (X) kod kojih vrijednost funkcije L(x, λ), kao i vrijednost ciljne funkcije f(x) odgovaraju ekstremumu.
Veličina Lagrangeovih množitelja (λ) je od praktičnog interesa ako su ograničenja predstavljena u obliku sa slobodnim članom u jednadžbi (konstanta). U ovom slučaju možemo dalje razmatrati (povećanje/smanjenje) vrijednost ciljne funkcije promjenom vrijednosti konstante u sistemu jednačina. Dakle, Lagrangeov množitelj karakterizira brzinu promjene maksimuma ciljne funkcije kada se promijeni granična konstanta.
Postoji nekoliko načina da se odredi priroda ekstrema rezultirajuće funkcije:
Prvi metod: Neka su koordinate tačke ekstrema i odgovarajuća vrijednost ciljne funkcije. Uzima se tačka blizu tačke i izračunava se vrednost funkcije cilja:
Ako 
, tada postoji maksimum u tački.
Ako 
, tada postoji minimum u tački.
Druga metoda: Dovoljan uslov iz kojeg se može odrediti priroda ekstrema je znak drugog diferencijala Lagrangeove funkcije. Drugi diferencijal Lagrangeove funkcije definiran je na sljedeći način:
Ako u datom trenutku 
minimum, ako 
, tada ciljna funkcija f(x) ima uslov maksimum.
Treći metod: Takođe, priroda ekstrema funkcije može se odrediti razmatranjem Hessiana Lagrangeove funkcije. Hessian matrica je simetrična kvadratna matrica drugih parcijalnih izvoda funkcije u tački u kojoj su elementi matrice simetrični u odnosu na glavnu dijagonali.
Da biste odredili vrstu ekstrema (maksimum ili minimum funkcije), možete koristiti Sylvesterovo pravilo:
1. Da bi drugi diferencijal Lagrangeove funkcije bio pozitivnog predznaka 
neophodno je da ugaoni minori funkcije budu pozitivni. Pod takvim uslovima, funkcija u ovoj tački ima minimum.
2. Da bi drugi diferencijal Lagrangeove funkcije bio negativan predznaka 
, potrebno je da se kutni minori funkcije izmjenjuju, a prvi element matrice mora biti negativanv. Pod takvim uslovima, funkcija u ovoj tački ima maksimum.
Pod kutnim minorom podrazumijevamo minor koji se nalazi u prvih k redova i k stupaca originalne matrice.
Glavni praktični značaj Lagrangeove metode je u tome što vam omogućava da prijeđete s uvjetne optimizacije na bezuvjetnu optimizaciju i, shodno tome, proširite arsenal dostupnih metoda za rješavanje problema. Međutim, problem rješavanja sistema jednačina na koji se ova metoda svodi nije, u opštem slučaju, ništa jednostavniji od prvobitnog problema nalaženja ekstrema. Takve metode se nazivaju indirektne. Njihova upotreba se objašnjava potrebom da se dobije rješenje ekstremnog problema u analitičkom obliku (na primjer, za određene teorijske proračune). Prilikom rješavanja konkretnih praktičnih problema obično se koriste direktne metode zasnovane na iterativnim procesima izračunavanja i poređenja vrijednosti funkcija koje se optimiziraju.
Metoda kalkulacije
1 korak: Lagrangeovu funkciju određujemo iz date funkcije cilja i sistema ograničenja:
Naprijed
Da biste dodali svoj komentar na članak, molimo vas da se registrujete na sajtu.
LAGRANGE METODA
Metoda za svođenje kvadratne forme na zbir kvadrata, koju je 1759. naznačio J. Lagrange. Neka se da
iz varijabli x 0 , x 1 ,..., x str.
sa koeficijentima iz terena k karakteristike Potrebno je dovesti ovaj oblik u kanonski. um
koristeći nedegenerisanu linearnu transformaciju varijabli. L. m. sastoji se od sljedećeg. Možemo pretpostaviti da nisu svi koeficijenti oblika (1) jednaki nuli. Stoga su moguća dva slučaja.
1) Za neke g, dijagonala Onda
pri čemu oblik f 1 (x) ne sadrži varijablu x g . 2) Ako sve 
Ali
To
pri čemu oblik f 2 (x) ne sadrži dvije varijable x g I x h . Oblici pod predznacima kvadrata u (4) su linearno nezavisni. Primjenom transformacija oblika (3) i (4), oblik (1) se nakon konačnog broja koraka svodi na zbir kvadrata linearno nezavisnih linearnih oblika. Koristeći parcijalne izvode, formule (3) i (4) se mogu napisati u obliku
Lit.: G a n t m a k h e r F. R., Teorija matrica, 2. izd., M., 1966; K u r o sh A. G., Kurs više algebre, 11. izd., M., 1975; Aleksandrov P. S., Predavanja iz analitičke geometrije..., M., 1968. I. V. Proskuryakov.
Matematička enciklopedija. - M.: Sovjetska enciklopedija. I. M. Vinogradov. 1977-1985.
Pogledajte šta je "LAGRANGE METODA" u drugim rječnicima:
Lagrangeova metoda- Lagrangeova metoda je metoda za rješavanje niza klasa matematičkih programskih problema pronalaženjem sedla (x*, λ*) Lagrangeove funkcije, što se postiže izjednačavanjem parcijalnih izvoda ove funkcije s nulom u odnosu na ... ... Ekonomsko-matematički rječnik
Lagrangeova metoda- Metoda za rješavanje više klasa problema matematičkog programiranja pronalaženjem sedla (x*, ?*) Lagrangeove funkcije, što se postiže izjednačavanjem parcijalnih izvoda ove funkcije u odnosu na xi i?i na nulu . Vidi Lagranžian. )
