Metóda dôkazu neurčitých Lagrangových multiplikátorov. Metóda neurčitých Lagrangových multiplikátorov

Zvážte problém podmienená optimalizácia obsahujúce iba obmedzenia vo forme rovnosti

min

podlieha obmedzeniam

,
.

V zásade je možné tento problém riešiť ako neobmedzený optimalizačný problém získaný odstránením m nezávislých premenných z cieľovej funkcie pomocou daných rovníc. Prítomnosť obmedzení rovnosti v skutočnosti umožňuje zmenšiť rozmer pôvodný problém. Nová výzva možno vyriešiť vhodnou neobmedzenou optimalizačnou metódou.

Príklad... Je potrebné minimalizovať funkciu

s obmedzením

Odstránenie premennej pomocou rovnice dostaneme optimalizačný problém s dvoma premennými bez obmedzení:

minimalizovať,

ktorý možno vyriešiť jednou z metód neobmedzenej optimalizácie.

Metóda eliminácie premenných je však použiteľná iba v prípadoch, keď rovnice reprezentujúce obmedzenia možno vyriešiť pre určitú množinu premenných. Pri veľkom množstve obmedzení v podobe rovnosti sa proces eliminácie premenných stáva veľmi prácnym postupom. Okrem toho sú možné situácie, keď rovnicu nemožno vyriešiť vzhľadom na premennú. V tomto prípade je vhodné použiť metódu Lagrangeovho multiplikátora.

Pomocou metódy Lagrangeovho multiplikátora sú v podstate stanovené potrebné podmienky, ktoré umožňujú identifikovať optimálne body v optimalizačných problémoch s obmedzeniami rovnosti.

Zvážte problém

min

podlieha obmedzeniam

,
.

Z kurzu matematická analýza je dobre známe, že bod podmieneného minima funkcie sa zhoduje so sedlovým bodom funkcie Lagrange:

,

v tomto prípade by mal sedlový bod poskytovať minimum v premenných a maximálne z hľadiska parametrov ... Tieto parametre sa nazývajú Lagrangeove multiplikátory. Prirovnávanie parciálnych derivácií funkcie na a podľa na nulu, dostaneme sa potrebné podmienky stacionárny bod:

,
,

,
.

Systémové riešenie
rovníc určuje stacionárny bod Lagrangeovej funkcie. Dostatočné podmienky pre existenciu minima pôvodného problému obsahujú okrem vyššie uvedených aj pozitívnu definitívnosť hessovskej matice. objektívna funkcia.

4.2. Podmienky mývalia - Tucker

Považujte problém nie lineárne programovanie s obmedzeniami nerovnosti

min

s obmedzeniami

,
.

Znížme obmedzenia nerovnosti na obmedzenia rovnosti pridaním oslabujúcich premenných ku každému z nich ,
:

.

Vytvorme Lagrangeovu funkciu:

Potom sa formujú nevyhnutné podmienky pre minimum

,
;

,
;

,
.

Poslednú rovnicu môžete vynásobiť a nahradiť tlmiace premenné ich vyjadrením z druhej rovnice. Druhá rovnica môže byť transformovaná odstránením tlmiacich premenných a prechodom na obmedzenia nerovnosti. Treba doplniť ešte jednu podmienku
, ktorý musí byť splnený v bode podmieneného minima.

Nakoniec získame potrebné podmienky na existenciu minima problému nelineárneho programovania s obmedzeniami nerovností, ktoré sa nazývajú Kuhn-Tuckerove podmienky:

,
; (1)

,
; (2)

,
; (3)

,
. (4)

Obmedzenie nerovnosti
v bode nazývaný aktívny ak sa zmení na rovnosť
, a nazýva sa neaktívny, ak
... Ak je možné pred priamym riešením problému odhaliť obmedzenia, ktoré sú v optimálnom bode neaktívne, potom je možné tieto obmedzenia z modelu vylúčiť a tým znížiť jeho veľkosť.

Rovnica (3) znamená, že buď
alebo
... Ak
, potom
a obmedzenie je aktívne a je to obmedzenie rovnosti. Na druhej strane, ak je obmedzením prísna nerovnosť
, potom bude mať Lagrangeov multiplikátor tvar
tie. obmedzenie
je neaktívna a zanedbateľná. Samozrejme, predtým nie je známe, aké obmedzenia možno zanedbať.

Lagrangeova multiplikačná metóda.

Metóda Lagrangeovho multiplikátora je jednou z metód, ktoré umožňujú riešiť problémy nelineárneho programovania.

Nelineárne programovanie je sekcia matematického programovania, štúdium metód na riešenie extrémnych problémov s nelineárnou cieľovou funkciou a oblasťou realizovateľných riešení definovaných nelineárnymi obmedzeniami. V ekonómii to zodpovedá skutočnosti, že výsledky (efektívnosť) rastú alebo klesajú úmerne so zmenou rozsahu využívania zdrojov (alebo, čo je rovnaké, rozsahu výroby): napríklad v dôsledku rozdelenia výrobné náklady v podnikoch na variabilné a podmienene konštantné; z dôvodu saturácie dopytu po tovare, kedy je každá ďalšia jednotka ťažšie predajná ako predchádzajúca atď.

Problém nelineárneho programovania je položený ako problém hľadania optima určitej účelovej funkcie

F (x 1, ... x n), F (X) → max

keď sú splnené podmienky

g j (x 1, ... x n) ≥0, g (X) ≤ b , X ≥ 0

kde X-vektor požadovaných premenných;

F (X) je objektívna funkcia;

g (X) - funkcia obmedzení (priebežne diferencovateľné);

b - vektor konštánt obmedzení.

Riešenie problému nelineárneho programovania (globálne maximum alebo minimum) môže patriť buď na hranicu alebo do vnútra prípustnej množiny.

Na rozdiel od problému lineárneho programovania, v probléme nelineárneho programovania nemusí optimum nevyhnutne ležať na hranici oblasti definovanej obmedzeniami. Inými slovami, problémom je vybrať také nezáporné hodnoty premenných podliehajúcich systému obmedzení v podobe nerovností, pri ktorých sa dosiahne maximum (alebo minimum) danej funkcie. Zároveň nie sú stanovené formy ani účelovej funkcie, ani nerovností. Možno rôzne prípady: cieľová funkcia je nelineárna a obmedzenia sú lineárne; účelová funkcia je lineárna a obmedzenia (aspoň jedno z nich) sú nelineárne; cieľová funkcia aj obmedzenia sú nelineárne.

Problém nelineárneho programovania sa vyskytuje v prírodné vedy, technika, ekonómia, matematika, v oblasti obchodných vzťahov a vo vede o vláde.

Nelineárne programovanie je napríklad spojené so základným ekonomickým problémom. Takže v probléme distribúcie obmedzených zdrojov sa maximalizuje buď efektívnosť, alebo, ak sa skúma spotrebiteľ, spotreba za prítomnosti obmedzení, ktoré vyjadrujú podmienky pre nedostatok zdrojov. V takomto všeobecnom prostredí sa matematická formulácia problému môže ukázať ako nemožná, ale v špecifických aplikáciách je možné kvantitatívnu formu všetkých funkcií určiť priamo. Napríklad, priemyselný podnik vyrába plastové výrobky. Efektívnosť výroby sa tu odhaduje ziskom a obmedzenia sa interpretujú ako dostupná pracovná sila, výrobný priestor, produktivita zariadení atď.

Do schémy nelineárneho programovania zapadá aj metóda nákladovej efektívnosti. Táto metóda bol vyvinutý na použitie pri rozhodovaní vo vláde. Spoločná funkcia efektívnosť je pohoda. Tu vznikajú dva problémy nelineárneho programovania: prvým je maximalizácia efektu pri obmedzených nákladoch, druhým je minimalizácia nákladov za predpokladu, že efekt je nad určitou minimálnou úrovňou. Táto úloha je zvyčajne dobre modelovaná pomocou nelineárneho programovania.

Výsledky riešenia problému nelineárneho programovania sú nápomocné pri rozhodovaní vlády. Získané riešenie je samozrejme odporúčané, preto je potrebné pred konečným rozhodnutím preskúmať predpoklady a presnosť formulácie problému nelineárneho programovania.

Nelineárne problémy sú zložité a často sa zjednodušujú tak, že vedú k lineárnym problémom. Na tento účel sa konvenčne predpokladá, že v určitej oblasti sa cieľová funkcia zvyšuje alebo znižuje úmerne so zmenou nezávislých premenných. Tento prístup sa nazýva metóda po častiach lineárnych aproximácií, je však použiteľný len pre niektoré typy nelineárnych problémov.

Nelineárne úlohy v určité podmienky sa riešia pomocou Lagrangeovej funkcie: nájsť to sedlový bod, čím sa nájde riešenie problému. Gradientové metódy zaujímajú dôležité miesto medzi výpočtovými algoritmami nelineárnych algoritmov. Neexistuje žiadna univerzálna metóda pre nelineárne problémy a zrejme ani nemusí byť, pretože sú veľmi rôznorodé. Obzvlášť ťažké je vyriešiť multiextrémne problémy.

Jednou z metód, ktorá nám umožňuje zredukovať problém nelineárneho programovania na riešenie sústavy rovníc, je metóda neurčitých Lagrangeových multiplikátorov.

Pomocou metódy Lagrangeovho multiplikátora sú v podstate stanovené potrebné podmienky, ktoré umožňujú identifikovať optimálne body v optimalizačných problémoch s obmedzeniami rovnosti. V tomto prípade sa problém s obmedzeniami transformuje na ekvivalentný problém neobmedzenej optimalizácie, v ktorom sa objavujú niektoré neznáme parametre, nazývané Lagrangeove multiplikátory.

Metóda Lagrangeovho multiplikátora je znížiť problémy na podmienený extrém k problémom pre bezpodmienečný extrém pomocná funkcia- tzv. Lagrangeove funkcie.

Pre problém extrému funkcie f(x 1, x 2, ..., x n) za podmienok (obmedzujúce rovnice) φ i(x 1, x 2, ..., x n) = 0, i= 1, 2,..., m, Lagrangeova funkcia má tvar

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)

Multiplikátory λ 1, λ 2, ..., λm volal Lagrangeove multiplikátory.

Ak množstvá x 1, x 2, ..., x n, λ 1, λ 2, ..., λm podstatou riešení rovníc, ktoré určujú stacionárne body Lagrangeovej funkcie, konkrétne pre diferencovateľné funkcie sú riešenia sústavy rovníc

potom za celkom všeobecných predpokladov x 1, x 2, ..., x n poskytnite extrém funkcie f.

Zvážte problém minimalizácie funkcie n premenných, berúc do úvahy jedno obmedzenie vo forme rovnosti:

Minimalizovať f (x 1, x 2 ... x n) (1)

pod obmedzeniami h 1 (x 1, x 2 ... x n) = 0 (2)

V súlade s metódou Lagrangeovho multiplikátora sa tento problém transformuje na nasledujúci neobmedzený optimalizačný problém:

minimalizovať L (x, λ) = f (x) -λ * h (x) (3)

kde funkcia L (x; λ) sa nazýva Lagrangeova funkcia,

λ je neznáma konštanta, ktorá sa nazýva Lagrangeov multiplikátor. Na značku λ nie sú kladené žiadne požiadavky.

Nech je pre danú hodnotu λ = λ 0 bezpodmienečné minimum funkcie L (x, λ) vzhľadom na x dosiahnuté v bode x = x 0 a x 0 spĺňa rovnicu h 1 (x 0) = 0. Potom, ako je ľahké vidieť, x 0 minimalizuje (1) berúc do úvahy (2), pretože pre všetky hodnoty x vyhovuje (2), h 1 (x) = 0 a L (x, λ) = min. f (x).

Samozrejme je potrebné zvoliť hodnotu λ = λ 0 tak, aby súradnica bodu nepodmieneného minima х 0 vyhovovala rovnosti (2). Dá sa to urobiť, ak uvažujeme λ ako premennú, nájdeme nepodmienené minimum funkcie (3) vo forme funkcie λ a potom zvolíme hodnotu λ, pri ktorej je splnená rovnosť (2). Ukážme si to na konkrétnom príklade.

Minimalizujte f (x) = x 1 2 + x 2 2 = 0

pod obmedzením h 1 (x) = 2x 1 + x 2 -2 = 0 = 0

Zodpovedajúci neobmedzený optimalizačný problém je napísaný takto:

minimalizovať L (x, λ) = x 1 2 + x 2 2 -λ (2x 1 + x 2 -2)

Riešenie. Ak priradíme dve zložky gradientu L k nule, dostaneme

→ x 1 0 = λ

→ x 2 0 = λ / 2

Aby sme skontrolovali, či stacionárny bod x ° zodpovedá minimu, vypočítame prvky Hessovej matice funkcie L (x; u), uvažované ako funkciu x,

čo sa ukazuje ako pozitívne definitívny.

To znamená, že L (x, u) je konvexná funkcia x. Preto súradnice x 1 0 = λ, x 2 0 = λ / 2 určujú bod globálneho minima. Optimálna hodnotaλ sa zistí dosadením hodnôt x 1 0 a x 2 0 do rovnice 2x 1 + x 2 = 2, odkiaľ 2λ + λ / 2 = 2 alebo λ 0 = 4/5. Podmienené minimum sa teda dosiahne pri x 1 0 = 4/5 a x 2 0 = 2/5 a rovná sa min f (x) = 4/5.

Pri riešení úlohy z príkladu sme uvažovali L (x; λ) ako funkciu dvoch premenných x 1 a x 2 a navyše predpokladali, že hodnota parametra λ je zvolená tak, aby bola splnená podmienka. Ak je riešenie systému

J = 1,2,3, ..., n

nemožno získať vo forme explicitných funkcií λ, potom hodnoty х a λ nájdeme riešením nasledujúceho systému pozostávajúceho z n + 1 rovníc s n + 1 neznámymi:

J = 1,2,3, ..., n, H1 (x) = 0

Ak chcete nájsť všetky možné riešenia Tento systém môže využívať numerické metódy vyhľadávania (napríklad Newtonovu metódu). Pre každé z riešení () by sa mali vypočítať prvky Hessovej matice funkcie L, považované za funkciu x, a zistiť, či je táto matica kladne definitná (lokálne minimum) alebo záporne definitná (lokálne maximum). ).

Metódu Lagrangeovho multiplikátora možno rozšíriť na prípad, keď má problém niekoľko obmedzení vo forme rovnosti. Zvážte všeobecný problém, ktorý si vyžaduje

Minimalizovať f (x)

pri obmedzeniach h k = 0, k = 1, 2, ..., K.

Lagrangeova funkcia má nasledujúcu formu:

Tu λ 1, λ 2, ..., λk-Lagrangeove multiplikátory, t.j. neznáme parametre, ktorých hodnoty je potrebné určiť. Prirovnaním parciálnych derivácií L vzhľadom na x k nule dostaneme nasledujúci systém n rovníc s n neznámymi:

Ak sa ukáže, že je ťažké nájsť riešenie vyššie uvedeného systému vo forme funkcií vektora λ, potom je možné systém rozšíriť zahrnutím obmedzení vo forme rovnosti

Riešenie rozšíreného systému pozostávajúceho z n + K rovníc s n + K neznámymi určuje stacionárny bod funkcie L. Potom sa implementuje postup kontroly minima alebo maxima, ktorý sa vykonáva na základe výpočtu prvky Hessovej matice funkcie L, uvažované ako funkcia x, podobne ako to bolo v prípade úlohy s jedným obmedzením. Pre niektoré problémy nemusí mať rozšírený systém n + K rovníc s n + K neznámymi riešenia a metóda Lagrangeovho multiplikátora sa ukáže ako nepoužiteľná. Treba však poznamenať, že s takýmito úlohami sa v praxi stretávame len zriedka.

Zvážte špeciálny prípad spoločná úloha nelineárne programovanie, za predpokladu, že systém obmedzení obsahuje iba rovnice, neexistujú podmienky pre nezápornosť premenných a - funkcie sú spojité spolu s ich parciálnymi deriváciami. Preto po vyriešení systému rovníc (7) získame všetky body, v ktorých funkcia (6) môže mať extrémne hodnoty.

Algoritmus Lagrangeovej multiplikačnej metódy

1. Vytvorte Lagrangeovu funkciu.

2. Nájdite parciálne derivácie Lagrangeovej funkcie vzhľadom na premenné x J, λ i a priraďte ich k nule.

3. Riešime sústavu rovníc (7), nájdeme body, v ktorých môže mať účelová funkcia úlohy extrém.

4. Medzi bodmi podozrivými z extrému nájdeme tie, v ktorých sa extrém dosiahne, a vypočítame hodnoty funkcie (6) v týchto bodoch.

Príklad.

Počiatočné údaje: Podľa výrobného plánu potrebuje podnik vyrobiť 180 produktov. Tieto produkty je možné vyrábať dvoma technologickými spôsobmi. Pri výrobe x 1 produktov metódou 1 sú náklady 4x 1 + x 1 2 rubľov a pri výrobe x 2 produktov metódou 2 sú to 8x 2 + x 2 2 rubľov. Určte, koľko produktov by sa mala vyrobiť každá z metód, aby náklady na výrobu produktov boli minimálne.

Objektívna funkcia pre danú úlohu má tvar
® min za podmienok x 1 + x 2 = 180, x 2 ≥0.
1. Vytvorte Lagrangeovu funkciu
.
2. Vypočítame parciálne derivácie vzhľadom na x 1, x 2, λ a prirovnáme ich k nule:

3. Pri riešení výslednej sústavy rovníc zistíme, že x 1 = 91, x 2 = 89

4. Substitúciou v účelovej funkcii x 2 = 180-x 1 dostaneme funkciu jednej premennej, a to f 1 = 4x 1 + x 1 2 +8 (180-x 1) + (180-x 1) 2

Vypočítajte alebo 4x 1 -364 = 0,

odkiaľ máme x 1 * = 91, x 2 * = 89.

Odpoveď: Počet výrobkov vyrobených prvou metódou sa rovná x 1 = 91, druhou metódou x 2 = 89, pričom hodnota účelovej funkcie je 17278 rubľov.

Dovoliť a byť dvakrát nepretržite diferencovateľné skalárne funkcie vektorového argumentu. Je potrebné nájsť extrém funkcie za predpokladu, že argument spĺňa systém obmedzení:

(posledná podmienka sa nazýva aj podmienka spojenia).

Väčšina jednoduchá metóda nájdenie podmieneného extrému znamená zredukovať problém na nájdenie nepodmieneného extrému riešením obmedzujúcej rovnice vzhľadom na m premenných a ich následná substitúcia v účelovej funkcii.

Príklad 3 Nájdite extrém poskytnutej funkcie.

Riešenie... Z rovnice obmedzenia vyjadríme x 2 naprieč x 1 a dosaďte výsledný výraz do funkcie pri:

Táto funkcia má jeden extrém (minimum) at x 1= 2. resp. x 2= 1. Teda bod podmieneného extrému (minimum) danú funkciu je pointa.

V uvažovanom príklade je rovnica obmedzenia ľahko riešiteľná vzhľadom na jednu z premenných. Avšak, viac ťažké prípady nie je vždy možné vyjadriť premenné. Preto vyššie opísaný prístup nie je použiteľný pre všetky úlohy.

Viac univerzálna metóda riešenie problémov hľadania podmieneného extrému je Lagrangeova multiplikačná metóda... Je založená na aplikácii nasledujúcej vety. Ak je bod extrémnym bodom funkcie v oblasti definovanej rovnicami, potom (pre niektorých dodatočné podmienky) existuje taká m-rozmerný vektor, že bod je stacionárnym bodom funkcie

Algoritmus Lagrangeovej multiplikačnej metódy

Krok 1... Vytvorte Lagrangeovu funkciu:

kde je Lagrangeov multiplikátor zodpovedajúci i obmedzenie.

Krok 2... Nájdite parciálne derivácie Lagrangeovej funkcie a prirovnajte ich k nule

Krok 3 Po vyriešení výsledného systému z n+m rovnice, nájdite stacionárne body.

Všimnite si, že nevyhnutná, ale nie postačujúca podmienka pre extrém funkcie je splnená v stacionárnych bodoch. Analýza stacionárneho bodu na prítomnosť extrému v ňom v tomto prípade dosť ťažké. Preto sa metóda Lagrangeovho multiplikátora používa najmä v prípadoch, keď je existencia minima alebo maxima skúmanej funkcie vopred známa z geometrických alebo zmysluplných úvah.

Pri riešení niektorých ekonomických problémov majú Lagrangeove multiplikátory určitý sémantický obsah. Ak teda ide o zisk podniku s výrobným plánom n tovar, - náklady i- teda zdroj l i- odhad tohto zdroja, ktorý charakterizuje rýchlosť zmeny optima účelovej funkcie v závislosti od zmeny i zdroj.

Príklad 4 Nájdite extrémy poskytnutej funkcie.

Riešenie... Funkcie a sú spojité a majú spojité parciálne derivácie. Zostavme Lagrangeovu funkciu:

Nájdime parciálne derivácie a prirovnajme ich k nule.

Získame dva stacionárne body:

Berúc do úvahy povahu účelovej funkcie, ktorej úrovňové čiary sú roviny, a funkcie (elipsy), sme dospeli k záveru, že v bode má funkcia minimálnu hodnotu a v bode maximum.

Príklad 5. V oblasti systémových riešení

nájsť maximálnu a minimálnu hodnotu poskytnutej funkcie.

Riešenie... Priesečník oblasti realizovateľných riešení a priamky je segment MN: M(0,6), N(6,0). Preto môže funkcia nadobúdať extrémne hodnoty buď v stacionárnych bodoch alebo v bodoch M a N... Na nájdenie stacionárneho bodu používame Lagrangeovu metódu. Zostavme Lagrangeovu funkciu

Nájdite parciálne derivácie Lagrangeovej funkcie a prirovnajte ich k nule

Vyriešením systému získame stacionárny bod K(2,2; 3,8). Porovnajme hodnoty cieľovej funkcie v bodoch K, M, N:

teda

Príklad 6. Známy je dopyt trhu po určitom produkte v množstve 180 kusov. Tento produkt môžu vyrábať dve továrne rovnakého koncernu. rôzne technológie... Vo výrobe x 1 výrobkov prvým podnikom, jeho náklady budú rub., a pri výrobe x 2 produkty druhého podniku, ktoré tvoria trieť.

Zistite, koľko produktov vyrobených pomocou jednotlivých technológií môže koncern ponúknuť, aby boli jeho celkové výrobné náklady minimálne.

Riešenie... Matematický model problému:

Nájsť minimálna hodnota poskytovaná objektívna funkcia x 1+ x 2= 180, t.j. bez ohľadu na požiadavku nezápornosti premenných zostavíme Lagrangeovu funkciu:

Nájdime prvé derivácie Lagrangeovej funkcie vzhľadom na x 1, x 2, l a prirovnáme ich k 0. Získame sústavu rovníc:

Pri riešení tohto systému nájdeme nasledujúce korene: , t.j. dostaneme súradnice bodu podozrivého z extrému.

Na určenie, či bod ( ) lokálne minimum, skúmame Hesseho determinant, pre ktorý vypočítame druhé parciálne derivácie účelovej funkcie:

Pretože

potom je Hesseho determinant pozitívne určitý; preto je účelová funkcia konvexná a v bode ( ) máme lokálne minimum:

Metóda Lagrangeovho multiplikátora je klasická metóda na riešenie problémov matematického programovania (najmä konvexných). Bohužiaľ, s praktické uplatnenie metóda môže naraziť na značné výpočtové ťažkosti, ktoré zužujú oblasť jej použitia. O Lagrangeovej metóde tu uvažujeme najmä preto, že ide o aparát aktívne používaný na zdôvodnenie rôznych moderných numerických metód, ktoré sú v praxi široko používané. Pokiaľ ide o funkciu Lagrange a multiplikátory Lagrange, hrajú nezávisle a výlučne dôležitá úloha v teórii a aplikáciách nielen v matematickom programovaní.

Zvážte klasický problém optimalizácie

max (min) z = f (x) (7,20)

Tento problém vyčnieva z úlohy (7.18), (7.19) tým, že medzi obmedzeniami (7.21) nie sú nerovnosti, neexistujú podmienky pre nezápornosť premenných, ich diskrétnosť a funkcie f (x) sú obe spojité a majú parciálne derivácie aspoň druhého rádu.

Klasický prístup k riešeniu úlohy (7.20), (7.21) dáva sústavu rovníc (nevyhnutné podmienky), ktoré musí spĺňať bod x *, čo dáva funkcii f (x) lokálny extrém na množine bodov vyhovujúcich obmedzeniam. (7.21) (pre problém konvexné programovanie nájdený bod x * v súlade s vetou 7.6 bude súčasne bodom globálneho extrému).

Predpokladajme, že v bode х * má funkcia (7.20) lokálny podmienený extrém a poradie matice sa rovná. Potom budú potrebné podmienky napísané vo forme:

(7.22)

existuje Lagrangeova funkcia; - Lagrangeove multiplikátory.

Sú aj dostatočné podmienky, za ktorých riešenie sústavy rovníc (7.22) určuje extrémny bod funkcie f (x). Táto otázka je vyriešená na základe štúdie znamienka druhého diferenciálu Lagrangeovej funkcie. Dostatočné podmienky sú však predovšetkým teoretické.

Metódou Lagrangeových multiplikátorov môžeme naznačiť nasledovné poradie riešenia úlohy (7.20), (7.21):

1) zostavte Lagrangeovu funkciu (7.23);

2) nájdite parciálne derivácie Lagrangeovej funkcie vo všetkých premenných a prirovnať ich k nule. Získame tak systém (7.22) pozostávajúci z rovníc. Vyriešte výsledný systém (ak sa ukáže, že je to možné!) A tak nájdite všetky stacionárne body Lagrangeovej funkcie;

3) zo stacionárnych bodov bez súradníc vyberte body, v ktorých má funkcia f (x) podmienené lokálne extrémy za prítomnosti obmedzení (7.21). Tento výber sa robí napríklad použitím dostatočných podmienok pre lokálny extrém. Výskum sa často zjednoduší, ak použijete špecifické podmienky problému.

Príklad 7.3... Nájsť optimálne rozloženie obmedzený zdroj v jednotke. medzi n spotrebiteľmi, ak sa zisk získaný pridelením x j jednotiek zdroja j-tému spotrebiteľovi vypočíta podľa vzorca.

Riešenie. Matematický model problému je nasledovný:

Zostavíme Lagrangeovu funkciu:

.

nachádzame parciálne derivácie Lagrangeovej funkcie a prirovnať ich k nule:

Vyriešením tohto systému rovníc dostaneme:

Ak teda j-tému spotrebiteľovi budú pridelené jednotky. zdroja, celkový zisk dosiahne maximálnu hodnotu a bude den. Jednotky

Uvažovali sme o Lagrangeovej metóde vo vzťahu k klasický problém optimalizácia. Túto metódu možno zovšeobecniť na prípad, keď premenné sú nezáporné a určité obmedzenia sú dané vo forme nerovností. Toto zovšeobecnenie má však prevažne teoretický význam a nevedie k špecifickým výpočtovým algoritmom.

Na záver dajme Lagrangeovým multiplikátorom ekonomický výklad. Aby sme to dosiahli, obrátime sa na najjednoduchší klasický optimalizačný problém

max (min) z=f(X 1 , NS 2); (7.24)

𝜑 (x 1, x 2) = b. (7,25)

Predpokladajme, že sa v určitom bode dosiahne podmienený extrém. Zodpovedajúca extrémna hodnota funkcie f(X)

Predpokladajme, že v obmedzeniach (7.25) množstvo b sa môže zmeniť, potom súradnice extrémneho bodu, a teda aj extrémna hodnota f * funkcie f(X) sa stávajú množstvami v závislosti od b, t.j. ,, a preto derivácia funkcie (7.24)

1.9 Metóda neurčitých Lagrangeových multiplikátorov

Prirodzene, riešenie obmedzených optimalizačných problémov je dôležité. ťažšie rozhodnutie neobmedzené problémy s optimalizáciou. Je prirodzené, že sa snažíme zredukovať problém podmienenej optimalizácie (hľadanie relatívneho extrému) na jednoduchší problém neobmedzenej optimalizácie (hľadanie absolútneho extrému). Tento postup sa vykonáva metódou Lagrange. Pozrime sa na podstatu tejto metódy.

Je potrebné nájsť podmienený extrém nelineárnej funkcie

n premenných pri m obmedzeniach

(1.56)

Obmedzenia nerovností sa prevedú na rovnosti a voľné členy sa prenesú na ľavé strany obmedzení, t.j. systém (1.56) sa zredukuje na formu

(1.57)

V súlade s Lagrangeovou metódou sa namiesto relatívneho extrému funkcie (1.55) s obmedzeniami (1.57) hľadá absolútny extrém Lagrangeovej funkcie, ktorý má nasledujúci tvar:

kde sú nedefinované Lagrangeove multiplikátory, ktoré sú rovnako ako premenné požadovanými premennými.

Je možné vidieť, že Lagrangeova funkcia zahŕňa účelovú funkciu plus každé obmedzenie vynásobené Lagrangeovým multiplikátorom.

Je dokázané, že relatívny extrém účelovej funkcie (1,55) pri obmedzeniach (1,57) sa zhoduje s absolútnym extrémom Lagrangeovej funkcie (1,58).

Vykoná sa hľadanie absolútneho extrému funkcie (1.58). známymi metódami... Najmä sú určené parciálne derivácie Lagrangeovej funkcie a rovnajú sa nule:

(1.59)

Posledných m rovníc sú obmedzenia (1.57) optimalizačného problému.

Sústava (1.59) obsahuje (m + n) rovníc a rovnaký počet neznámych.

Riešenie systému (1.59) dá súradnice absolútneho minima Lagrangeovej funkcie (1.58) alebo relatívneho minima účelovej funkcie (1.55) pri obmedzeniach (1.57).

Riešenie sústavy (1.59) sa uskutočňuje známymi metódami výpočtovej matematiky. Ak je sústava (1.59) lineárna, použije sa spravidla Gaussova metóda. Ak je systém (1.59) nelineárny - Newtonova metóda.

1.10 Výber metódy optimalizácie

Pred výberom metódy optimalizácie vykonáme stručná analýzaúlohy, ktoré má vyriešiť vyvinutý softvér:

program musí riešiť problém podmienenej minimalizácie, t.j. nájsť relatívny extrém, keďže v matematický model okrem lineárnych obmedzení budú prebiehať aj nelineárne;

keďže účelová funkcia je funkciou viacerých premenných, môže mať viacero extrémov a v tomto prípade musí program hľadať lokálne minimum.

Po analýze najčastejšie používaných optimalizačných metód bola na dosiahnutie tohto cieľa zvolená gradientová metóda kvadratického programovania, ktorá je z vyššie uvedených gradientových metód najefektívnejšia, modifikovaná metódami polynomiálnej aproximácie.

Predpokladá sa, že cieľová funkcia a okrajové podmienky sú aproximované kvadratickými závislosťami alebo polynómami druhého rádu. Táto metóda bude podrobnejšie diskutovaná neskôr v časti „Vývoj softvér optimalizačná metóda“.

Táto metóda vám umožňuje vytvárať spoľahlivý program ktorý spĺňa všetky vyššie uvedené požiadavky.

2. Vývoj optimalizačnej metódy pre re aktívny výkon

Celkový výkon kompenzačných zariadení požadovaný v elektrizačnej sústave (EPS) je určený z rovnice bilancie jalového výkonu (6.1). Tento výkon musí byť umiestnený v uzloch elektrickej siete s minimálne náklady.

kde je celkový jalový výkon generovaný v EPS vrátane jalového výkonu pochádzajúceho zo susedného EPS;

Celkový jalový výkon odberateľov EPS vrátane jalového výkonu dodávaného do susedného EPS;

Celkový jalový výkon pomocných potrieb elektrární;

Celkové straty jalového výkonu;

Celková spotreba jalového výkonu v EPS.

Zvážte najjednoduchšiu schému existujúcej siete(Obrázok 2.1). záťaž s výkonom S = P + jQ prijíma energiu zo zdroja s napätím U cez odpor siete R. Na záťažových zberniciach je inštalované kompenzačné zariadenie s výkonom Qk.

Obrázok 2.1 - Najjednoduchšia schéma kompenzácia jalového výkonu

Straty aktívneho výkonu vo vedení pri absencii kompenzačného zariadenia pre spotrebiteľa () sú

. (2.2)

Keď je u spotrebiteľa inštalované kompenzačné zariadenie (), tieto straty klesnú na hodnotu

. (2.3)

Kompenzácia jalového výkonu vám teda umožňuje znížiť stratu aktívneho výkonu v napájacom obvode a následne zlepšiť technické a ekonomické ukazovatele tohto obvodu.

Poďme odhadnúť vplyv CG na sieťové náklady.

Vyjadrenie celkových nákladov na prenos energie do záťaže počas inštalácie WHB bude nasledovné:

(2.4)

kde ЗК - náklady na КУ;

сoΔР - náklady na pokrytie strát činného výkonu v sieti;

co sú náklady na jednotku strateného aktívneho výkonu;

zk - jednotkové náklady pre KU.

Aby sme určili minimum funkcie 3, rovnáme sa nule jej derivácie premennej QK:

(2.5)

Z (2.5) sa určuje ekonomicky realizovateľný jalový výkon, ktorého prenos od zdroja k spotrebiteľovi spĺňa minimálne náklady З

(2.6)

Hodnota QE nezávisí od činného výkonu P, ale závisí len od pomeru ukazovateľov nákladov zk a co a parametrov siete U a R, cez ktorú sa výkon prenáša.

Problematika umiestnenia kompenzačných zariadení v elektrickej sieti reálneho EPS je zložitým optimalizačným problémom. Problém spočíva v tom, že energetické systémy sú veľké systémy vzájomne prepojených subsystémov. Nie je možné posudzovať oddelene každý samostatný subsystém, pretože vlastnosti veľké systémy sú určené charakterom prepojení jednotlivých subsystémov.

Pri analýze veľkých systémov sa používa systematický prístup, podľa ktorého sa analyzuje veľký systém sa vykonáva pri rozdelení na podsystémy, ktoré spolu priamo nesúvisia, ale prostredníctvom systému sa navzájom viac ovplyvňujú vysoký stupeň.

Vzhľadom na uvažovanú problematiku je uvedená elektrická sieť rôzne úrovne ako je znázornené na obr. 2.2. horná úroveň je elektrická sieť s napätím 110 kV a vyšším. Táto zložitá elektrická sieť, reprezentovaná úplným ekvivalentným obvodom, je znázornená na obr. 2.2 konvenčne ako ES1. Jalové výkony generované generátormi elektrární QES, kompenzačnými zariadeniami QK, elektrickými vedeniami QC, ako aj jalovými výkonmi prúdiacimi cez spoje so susednými ES2 a ES3 (Q12, Q21, Q13, Q31) poskytujú dostupný jalový výkon Qр1 v ES1.

Obrázok 2.2 - Rozloženie WHB v elektrickej sieti

Druhá úroveň je súbor n otvorených miestnych distribučných sietí s napätím 35 kV a nižším, pripojených na n uzlov elektrickej siete. špičková úroveň cez transformátory T. Tieto miestne distribučné siete nie sú navzájom priamo prepojené, ale sa navzájom ovplyvňujú cez sieť vyššej úrovne. Synchrónne generátory, kompenzátory a motory v každej takejto rozvodnej sieti sú zastúpené jedným ekvivalentným synchrónnym strojom G. Nízkonapäťové spotrebiče P + jQ sú napájané z miestnych elektrických sietí cez distribučné transformátory T1.

Kompenzačné zariadenia je možné inštalovať na zbernice vyššieho (jQkv) a nižšieho (jQks) napätia transformátorov T, ako aj na zbernice 0,4 kV distribučných transformátorov T1 a v samotnej sieti 0,4 kV (jQkn). Hodnota kapacít týchto KU sa má určiť.

V všeobecný pohľad je formulovaný problém optimalizácie umiestnenia CD nasledujúcim spôsobom: určiť jalový výkon dostupný v uzloch 6 ... 35 kV synchrónne stroje výkon G, KU v sieťach všetkých napätí Qkv, Qcs, Qkn, ako aj hodnoty jalových výkonov Qei (i = 1, 2,… n), prenášané v spotrebiteľskej sieti, pri ktorých sú minimálne celkové náklady je zabezpečená.

Výpočty kompenzácie jalového výkonu pre siete všetkých typov sa vykonávajú tak pri návrhu rozvoja elektrických sietí, ako aj v podmienkach ich prevádzky. Pri projektovaní sa stanovia kapacity WHB a rieši sa problém ich distribúcie v elektrickej sieti. V prevádzkových podmienkach určite optimálne režimy k dispozícii KU počas dňa. Kritériá optimálnosti sú v tomto prípade minimálne straty výkonu a energie a súlad napäťových odchýlok s prípustnými hodnotami.

Pri navrhovaní schémy napájania sú peňažné náklady na túto schému spravidla minimalizované. Zníženie strát výkonu v dôsledku inštalácie KU znižuje náklady na obvod, podľa nasledujúce dôvody:

každý stratený kW výkonu musí byť generovaný v elektrárňach, a teda aj vynaložený na to hotovosť;

výroba nedostatočne prijatého jalového výkonu v elektrárňach je oveľa drahšia ako spotreba (3x!).

Kompenzačné zariadenia sú však tiež drahé.

V tomto smere vzniká problém určiť optimálny výkon kompenzačných zariadení, ktorý spĺňa minimálne celkové náklady. Tento problém patrí k problému neobmedzenej optimalizácie a možno ho riešiť napríklad gradientovými metódami.

Zvážte takýto problém pre hlavný napájací obvod (obr. 2.3). Výkon kompenzačných zariadení QK1 a QK2 v uzloch 1 a 2 je potrebné určiť na základe podmienky minimálnych celkových nákladov na inštaláciu týchto zariadení a pokrytia strát činného výkonu v obvode.

Obrázok 2.3 - Schéma napájania

Počiatočné údaje:

napätie obvodu U;

odpor vedení R1 a R2;

reaktívne záťaže uzly 1 a 2 Q1 a Q2;

jednotkové náklady na inštaláciu kompenzačných zariadení zo;

jednotkové náklady na pokrytie strát činného výkonu z.

Objektívna funkcia, ktorou sú celkové náklady na inštaláciu kompenzačných zariadení a pokrytie strát činného výkonu v obvode, má nasledujúci tvar

kde a1 = R1 ∙ co ∙ 10-3 / U2 = 0,0006;

a2 = R2 ∙ co ∙ 10-3 / U2 = 0,0004.

Zavedenie číselného koeficientu 10-3 je potrebné na redukciu všetkých zložiek účelovej funkcie na jeden rozmer (c.u.).

Na vyriešenie problému zvolíme metódu zostupu súradníc. Definujme parciálne derivácie účelovej funkcie Z vzhľadom na premenné Q1 a Q2:

(2.8)

Zoberme si počiatočnú aproximáciu:

Pre tieto hodnoty vypočítame hodnoty účelovej funkcie a jej parciálne derivácie.

Predpokladajme, že účelová funkcia Z klesá výraznejšie v smere premennej Qk2 ako v smere premennej Qk1, t.j.

(2.10)

V smere premennej Qk2 a začnite klesať.

Zoberme si veľkosť kroku = 400 kvar. Prvá aproximácia (prvý krok) bude Qk11 = 0, Qk21 = 400 kvar. Vypočítame hodnotu účelovej funkcie Z1.

Druhý krok: Qk12 = 0, Qk22 = 400 kvar. Vypočítame hodnotu účelovej funkcie Z2.

Zostup pozdĺž súradnice Qk2 by mal pokračovať až po Zn

Urobme nový krok smerom k ďalšej premennej Qk1. Nájde sa nová hodnota účelovej funkcie Z. Zostup pozdĺž tejto premennej pokračuje rovnakým spôsobom ako v smere Qk2 - až po Zm

Bod so získanými súradnicami Qk1m-1, Qk2n-1 je v blízkosti minima účelovej funkcie Z. Pri prijatej dĺžke kroku = 400 kvar sa presnejšie riešenie nedá získať. Na získanie presnejšieho riešenia je potrebné znížiť krok a pokračovať v zostupe. Je absolútne isté, že čím menší krok, tým presnejší bude výsledok. Túto presnosť nemôžeme dosiahnuť pomocou manuálneho výpočtu. Na vyriešenie tohto problému bude vhodné použiť softvér určený na riešenie problému nelineárneho programovania s nelineárnymi obmedzeniami. Jedným z týchto programovacích jazykov je jazyk C++.

Toto sa považovalo za problém neobmedzenej optimalizácie, t.j. nájsť absolútne minimum. Pri riešení problému, aby sa našiel optimálny prevádzkový režim pre sieť OJSC „MMK pomenovaná po Iľjičovi“, je potrebné nájsť relatívne minimum, pretože systém obmedzení bude mať nelineárnu formu (pozri nižšie „Vývoj softvéru "). Stojíme teda pred problémom podmienenej optimalizácie z hľadiska jalového výkonu, na ktorý aplikujeme predtým zvolenú gradientovú metódu kvadratického programovania.

Informácie o práci „Analýza prevádzkových režimov elektrických sietí OJSC“ MMK pomenovaná po Ilyichovi „a vývoji adaptívneho riadiaceho systému pre režimy spotreby energie“