Stručná teorie

Metoda Lagrangeových multiplikátorů je klasickou metodou pro řešení problémů matematického programování (zejména konvexních). Bohužel při praktické aplikaci metody mohou nastat značné výpočetní potíže, které zužují oblast jejího použití. Uvažujeme zde o Lagrangeově metodě především proto, že se jedná o aparát aktivně používaný k ospravedlnění různých moderních numerických metod, které jsou v praxi široce používány. Co se týče Lagrangeovy funkce a Lagrangeových multiplikátorů, hrají samostatnou a nesmírně důležitou roli v teorii a aplikacích nejen matematického programování.

Zvažte klasický optimalizační problém:

Mezi omezeními tohoto problému nejsou žádné nerovnosti, neexistují podmínky pro nezápornost proměnných, jejich diskrétnost a funkce a jsou spojité a mají parciální derivace alespoň druhého řádu.

Klasický přístup k řešení úlohy dává systém rovnic (nezbytné podmínky), které musí splňovat bod, který funkci poskytuje lokální extrém na množině bodů splňujících omezení (pro konvexní programovací problém nalezený bod bude zároveň globálním extrémním bodem).

Předpokládejme, že funkce (1) má v bodě lokální podmíněný extrém a hodnost matice je rovna . Pak lze nezbytné podmínky zapsat jako:

je Lagrangeova funkce; jsou Lagrangeovy multiplikátory.

Jsou také dostatečné podmínky, za kterých řešení soustavy rovnic (3) určuje krajní bod funkce . Tato otázka je řešena na základě studia znaménka druhého diferenciálu Lagrangeovy funkce. Dostatečné podmínky jsou však především teoretického zájmu.

Můžete zadat následující postup řešení problému (1), (2) metodou Lagrangeova multiplikátoru:

1) sestavte Lagrangeovu funkci (4);

2) najděte parciální derivace Lagrangeovy funkce vzhledem ke všem proměnným a srovnejte je

nula. Získáme tak soustavu (3) složenou z rovnic, kterou vyřešíme (pokud to bude možné!) a najdeme tak všechny stacionární body Lagrangeovy funkce;

3) ze stacionárních bodů odebraných bez souřadnic vyberte body, ve kterých má funkce podmíněné lokální extrémy za přítomnosti omezení (2). Tato volba se provádí například pomocí dostatečných podmínek pro lokální extrém. Studie se často zjednoduší, pokud se použijí specifické podmínky problému.

Příklad řešení problému

Úkol

Firma vyrábí dva druhy zboží v množství a . Funkce užitečných nákladů je definována vztahem . Ceny tohoto zboží na trhu jsou stejné resp.

Určete, při jakých objemech výkonu je dosaženo maximálního zisku a čemu se rovná, pokud celkové náklady nepřekročí

Řešení problému

Ekonomický a matematický model problému

Zisková funkce:

Limity nákladů:

Získáme následující ekonomický a matematický model:

Navíc podle smyslu úkolu

Lagrangeova multiplikační metoda

Složme Lagrangeovu funkci:

Najdeme parciální derivace 1. řádu:

Skládáme a řešíme soustavu rovnic:

Od té doby

Maximální zisk:

Odpovědět

Je tedy nutné vyrábět jednotky. zboží 1. druhu a jednotek. zboží 2. druhu. V tomto případě bude zisk maximální a bude 270.

Považováno grafická metodařešení úlohy lineárního programování (LPP) se dvěma proměnnými. Na příkladu úkolu Detailní popis vytvoření výkresu a nalezení řešení.

Wilsonův model řízení zásob
Na příkladu řešení problému je uvažován hlavní model řízení zásob (Wilsonův model). Vypočítané takové ukazatele modelu jako optimální velikost objednávky šarží, roční náklady na skladování, interval dodání a místo objednávky.

Matice přímého poměru nákladů a matice vstupů a výstupů
Na příkladu řešení problému je uvažován Leontievův mezisektorový model. Je znázorněn výpočet matice koeficientů přímých materiálových nákladů, matice "input-output", matice koeficientů nepřímých nákladů, vektorů konečné spotřeby a hrubého výkonu.

Klasifikace úloh matematického programování

PROGRAMOVÁNÍ

METODY ŘEŠENÍ PROBLÉMŮ NELINEÁRNÍCH

testové otázky do oddílu 4

Schéma řešení dopravního problému

Uveďme si hlavní etapy řešení dopravního problému.

1. Zkontrolujte stav uzavření. Pokud je úkol otevřený, je tabulka dopravy doplněna buď o sloupec fiktivního odběrného místa, nebo o řádek fiktivního dodavatele.

2. Sestavte základní plán.

3. Zkontrolujte základní plán na nedegeneraci. Pokud není dostatek obsazené buňky pro splnění podmínky nedegenerace, jedna z buněk transportní tabulky se zaplní zásobou rovnou nule. V případě potřeby je přípustné evidovat nulové dodávky ve více buňkách.

4. Plán je zkontrolován z hlediska optimálnosti.

5. Pokud nejsou splněny podmínky optimality, přejděte k dalšímu plánu přerozdělením zásob. Proces výpočtu se opakuje, dokud není získán optimální plán.

1. Jaký význam má účelová funkce v matematickém modelu dopravní úlohy?

2. Jaký význam mají omezení v matematickém modelu dopravní úlohy?

3. Je možné aplikovat metodu potenciálů k řešení otevřeného (neuzavřeného) dopravního problému?

4. Jaké změny je třeba provést v původní transportní tabulce, aby bylo možné problém vyřešit potenciální metodou?

5. Co je podstatou metody minimálního prvku? Jaká fáze řešení dopravního problému bude provedena v důsledku aplikace této metody?

6. Jak poznáte, že je plán přepravy optimální?

7. V jakém případě a jak je nutné přerozdělit dodávky z hlediska přepravy?

8. Předpokládejme, že sestrojený dopravní plán je zdegenerovaný. Je možné pokračovat v řešení problému metodou potenciálů a co je pro to potřeba udělat?

Obecný problém matematického programování byl formulován v části 1.1. V závislosti na typu funkcí obsažených v modelu (1.1)-(1.3) se problém vztahuje k jednomu nebo druhému typu matematického programování. Existuje lineární programování (všechny funkce jsou lineární), celočíselné (řešení jsou celá čísla), kvadratické (objektivní funkce je kvadratická forma), nelineární (alespoň jedna z funkcí problému je nelineární) a stochastické programování ( pravděpodobnostní parametry jsou zahrnuty).

Třída problémů nelineárního programování je širší než třída lineární modely. Například výrobní náklady ve většině případů nejsou úměrné objemu produkce, ale závisí na něm nelineárně, příjem z prodeje výrobních produktů se ukazuje jako nelineární funkce cen atd. Kritéria v problémech optimálního plánování jsou často maximální zisk, minimální náklady, minimální kapitálové náklady. Objemy produkce různých typů produktů působí jako proměnné. Mezi omezení patří produkční funkce, které charakterizují vztah mezi výstupem a cenou práce a materiálových zdrojů, jejichž objem je omezený.

Na rozdíl od lineárního programování, které využívá univerzální metodařešení (simplexní metoda), existuje celá řada metod pro řešení nelineárních problémů v závislosti na podobě funkcí obsažených v modelu. Z celé řady metod budeme uvažovat pouze dvě: Lagrangeova metoda a metoda dynamického programování.

Z Podstatou Lagrangeovy metody je redukovat problém podmíněného extrému na řešení problému nepodmíněného extrému. Zvažte model nelineárního programování:

(5.2)

kde jsou známé funkce,

A jsou uvedeny koeficienty.

Všimněte si, že v této formulaci problému jsou omezení dána rovností a není zde žádná podmínka, aby proměnné byly nezáporné. Kromě toho předpokládáme, že funkce jsou spojité se svými prvními parciálními derivacemi.

Transformujme podmínky (5.2) tak, aby levá nebo pravá část rovnosti obsahovala nula:

(5.3)

Pojďme složit Lagrangeovu funkci. Zahrnuje účelovou funkci (5.1) a pravé strany omezení (5.3), v tomto pořadí s koeficienty . V problému bude tolik Lagrangeových koeficientů, kolik bude omezení.

Extrémní body funkce (5.4) jsou extremní body původního problému a naopak: optimální plán úlohy (5.1)-(5.2) je globální extremní bod Lagrangeovy funkce.

Opravdu, ať se najde řešení problém (5.1)-(5.2), pak jsou splněny podmínky (5.3). Pojďme nahradit plán do funkce (5.4) a ověřte platnost rovnosti (5.5).

Abychom tedy našli optimální plán původního problému, je nutné prozkoumat Lagrangeovu funkci pro extrém. Funkce má extrémní hodnoty v bodech, kde jsou její parciální derivace stejné nula. Takové body se nazývají stacionární.

Definujeme parciální derivace funkce (5.4)

,

.

Po vyrovnání nula deriváty dostaneme systém m+n rovnice s m+n neznámý

, (5.6)

V obecném případě bude mít systém (5.6)-(5.7) několik řešení, která zahrnují všechna maxima a minima Lagrangeovy funkce. Aby bylo zvýrazněno globální maximum nebo minimum, jsou hodnoty cílové funkce vypočteny ve všech nalezených bodech. Největší z těchto hodnot bude globální maximum a nejmenší bude globální minimum. V některých případech se ukazuje možné použití dostatečné podmínky pro přísný extrém spojité funkce (viz problém 5.2 níže):

nechť je funkce spojitá a dvakrát diferencovatelná v nějakém okolí jejího stacionárního bodu (tj. )). Pak:

A) pokud,(5.8)

potom je striktní maximální bod funkce;

b) pokud,(5.9)

potom je striktní minimální bod funkce;

G ) pokud,

pak zůstává otázka přítomnosti extrému otevřená.

Navíc některá řešení systému (5.6)-(5.7) mohou být záporná. Což není v souladu s ekonomickým významem proměnných. V tomto případě by měla být analyzována možnost nahrazení záporných hodnot nulou.

Ekonomický význam Lagrangeových multiplikátorů. Optimální hodnota multiplikátoru ukazuje, jak moc se změní hodnota kritéria Z při zvyšování nebo snižování zdroje j na jednotku, protože

Lagrangeovu metodu lze také použít, když jsou omezeními nerovnosti. Takže hledání extrému funkce za podmínek

,

se provádí v několika fázích:

1. Určete stacionární body účelové funkce, pro které řeší soustavu rovnic

.

2. Ze stacionárních bodů se vyberou ty, jejichž souřadnice splňují podmínky

3. K řešení problému s omezeními rovnosti (5.1)-(5.2) se používá Lagrangeova metoda.

4. Prozkoumejte globální maximální body nalezené ve druhé a třetí fázi: porovnejte hodnoty cílové funkce v těchto bodech – nejvyšší hodnotu odpovídá optimálnímu plánu.

Úkol 5.1 Vyřešme problém 1.3, uvažovaný v první části, Lagrangeovou metodou. Je popsáno optimální rozložení vodních zdrojů matematický model

.

Sestavte Lagrangeovu funkci

Najděte nepodmíněné maximum této funkce. K tomu vypočítáme parciální derivace a přirovnáme je k nule

,

Tak jsme získali soustavu lineárních rovnic tvaru

Řešení soustavy rovnic je optimálním plánem rozložení vodních zdrojů na zavlažované plochy

Hodnoty se měří ve stovkách tisíc metrů krychlových. - výše čistého příjmu na sto tisíc metrů krychlových závlahové vody. Proto je mezní cena 1 m 3 závlahové vody doupě. Jednotky

Maximální dodatečný čistý příjem ze zavlažování bude

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

172391,02 (den. jednotky)

Úkol 5.2 Vyřešte problém nelineárního programování

Omezení reprezentujeme jako:

.

Sestavte Lagrangeovu funkci a určete její parciální derivace

.

Abychom určili stacionární body Lagrangeovy funkce, měli bychom přirovnat její parciální derivace k nule. Výsledkem je soustava rovnic

Podívejme se nejprve na případ funkce dvou proměnných. Podmíněný extrém funkce $z=f(x,y)$ v bodě $M_0(x_0;y_0)$ je extrém této funkce dosažený za podmínky, že proměnné $x$ a $y$ v okolí tohoto bodu splňuje omezující rovnici $\ varphi(x,y)=0$.

Název "podmíněný" extrém je způsoben tím, že na proměnné je uvalena dodatečná podmínka $\varphi(x,y)=0$. Je-li možné vyjádřit jednu proměnnou pomocí druhé z rovnice spojení, pak se problém určení podmíněného extrému redukuje na problém obvyklého extrému funkce jedné proměnné. Pokud například $y=\psi(x)$ vyplývá z omezující rovnice, pak dosazením $y=\psi(x)$ do $z=f(x,y)$ dostaneme funkci jedné proměnné $ z=f\left (x,\psi(x)\right)$. V obecném případě je však tato metoda málo použitelná, takže je zapotřebí nový algoritmus.

Metoda Lagrangeových multiplikátorů pro funkce dvou proměnných.

Metoda Lagrangeových multiplikátorů spočívá v tom, že k nalezení podmíněného extrému se Lagrangeova funkce skládá: $F(x,y)=f(x,y)+\lambda\varphi(x,y)$ (parametr $\lambda $ se nazývá Lagrangeův multiplikátor). Potřebné extrémní podmínky jsou dány soustavou rovnic, ze kterých jsou určeny stacionární body:

$$ \left \( \begin(zarovnáno) & \frac(\částečné F)(\částečné x)=0;\\ & \frac(\částečné F)(\částečné y)=0;\\ & \varphi (x,y)=0.\konec(zarovnáno)\vpravo.$$

Znak $d^2 F=F_(xx)^("")dx^2+2F_(xy)^("")dxdy+F_(yy)^("" )dy^2$. Pokud je ve stacionárním bodě $d^2F > 0$, pak má funkce $z=f(x,y)$ v tomto bodě podmíněné minimum, ale pokud $d^2F< 0$, то условный максимум.

Existuje další způsob, jak určit povahu extrému. Z omezující rovnice dostaneme: $\varphi_(x)^(")dx+\varphi_(y)^(")dy=0$, $dy=-\frac(\varphi_(x)^("))( \varphi_ (y)^("))dx$, takže v jakémkoli stacionárním bodě máme:

$$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_(yy)^("")\left(-\frac(\varphi_(x)^("))(\varphi_(y)^("))dx\right)^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)^ ("")\vpravo)$$

Druhý faktor (umístěný v závorkách) může být znázorněn v této podobě:

Prvky $\left| \begin(array) (cc) F_(xx)^("") & F_(xy)^("") \\ F_(xy)^("") & F_(yy)^("") \end (pole) \right|$ což je hessián Lagrangeovy funkce. Pokud $H > 0$, pak $d^2F< 0$, что указывает на условный максимум. Аналогично, при $H < 0$ имеем $d^2F >0 $, tzn. máme podmíněné minimum funkce $z=f(x,y)$.

Poznámka k tvaru determinantu $H$. zobrazit/skrýt

$$ H=-\left|\begin(pole) (ccc) 0 & \varphi_(x)^(") & \varphi_(y)^(")\\ \varphi_(x)^(") & F_ (xx)^("") & F_(xy)^("") \\ \varphi_(y)^(") & F_(xy)^("") & F_(yy)^("") \ end(pole) \right| $$

V této situaci se výše formulované pravidlo změní následovně: pokud $H > 0$, pak má funkce podmíněné minimum a pro $H< 0$ получим условный максимум функции $z=f(x,y)$. При решении задач следует учитывать такие нюансы.

Algoritmus pro studium funkce dvou proměnných pro podmíněný extrém

1. Sestavte Lagrangeovu funkci $F(x,y)=f(x,y)+\lambda\varphi(x,y)$
2. Vyřešte systém $ \left \( \begin(zarovnáno) & \frac(\částečné F)(\částečné x)=0;\\ & \frac(\částečné F)(\částečné y)=0;\\ & \ varphi(x,y)=0.\end(zarovnáno)\vpravo.$
3. Určete povahu extrému v každém ze stacionárních bodů nalezených v předchozím odstavci. Chcete-li to provést, použijte některou z následujících metod:
   • Složte determinant $H$ a zjistěte jeho znaménko
   • S ohledem na omezující rovnici vypočítejte znaménko $d^2F$

Metoda Lagrangeova multiplikátoru pro funkce n proměnných

Předpokládejme, že máme funkci $n$ proměnných $z=f(x_1,x_2,\ldots,x_n)$ a $m$ omezujících rovnic ($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,$$

Označením Lagrangeových multiplikátorů jako $\lambda_1,\lambda_2,\ldots,\lambda_m$ vytvoříme Lagrangeovu funkci:

$$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$$

Nezbytné podmínky pro přítomnost podmíněného extrému jsou dány systémem rovnic, ze kterých se nacházejí souřadnice stacionárních bodů a hodnoty Lagrangeových multiplikátorů:

$$\left\(\begin(zarovnáno) & \frac(\částečné F)(\částečné x_i)=0; (i=\overline(1,n))\\ & \varphi_j=0; (j=\ overline(1,m)) \end(zarovnáno) \right.$$

Je možné zjistit, zda má funkce v nalezeném bodě podmíněné minimum nebo podmíněné maximum, jako dříve, pomocí znaménka $d^2F$. Pokud je v nalezeném bodě $d^2F > 0$, pak má funkce podmíněné minimum, ale pokud $d^2F< 0$, - то условный максимум. Можно пойти иным путем, рассмотрев следующую матрицу:

Maticový determinant $\left| \begin(pole) (ccccc) \frac(\částečné^2F)(\částečné x_(1)^(2)) & \frac(\částečné^2F)(\částečné x_(1)\částečné x_(2) ) & \frac(\částečné^2F)(\částečné x_(1)\částečné x_(3)) &\ldots & \frac(\částečné^2F)(\částečné x_(1)\částečné x_(n)) \\ \frac(\částečné^2F)(\částečné x_(2)\částečné x_1) & \frac(\částečné^2F)(\částečné x_(2)^(2)) & \frac(\částečné^2F )(\částečné x_(2)\částečné x_(3)) &\ldots & \frac(\částečné^2F)(\částečné x_(2)\částečné x_(n))\\ \frac(\částečné^2F )(\částečné x_(3) \částečné x_(1)) & \frac(\částečné^2F)(\částečné x_(3)\částečné x_(2)) & \frac(\částečné^2F)(\částečné x_(3)^(2)) &\ldots & \frac(\partial^2F)(\částečné x_(3)\částečné x_(n))\\ \ldots & \ldots & \ldots &\ldots & \ ldots\\ \frac(\částečné^2F)(\částečné x_(n)\částečné x_(1)) & \frac(\částečné^2F)(\částečné x_(n)\částečné x_(2)) & \ frac(\částečné^2F)(\částečné x_(n)\částečné x_(3)) &\ldots & \frac(\částečné^2F)(\částečné x_(n)^(2))\\ \end( pole) \right|$ zvýrazněné červeně v matici $L$ je Hessian Lagrangeovy funkce. Používáme následující pravidlo:

• Jsou-li znaky rohových nezletilých $H_(2m+1),\; H_(2m+2),\ldots,H_(m+n)$ matice $L$ se shodují se znaménkem $(-1)^m$, pak studovaný stacionární bod je podmíněným minimálním bodem funkce $z =f(x_1,x_2,x_3,\ldots,x_n)$.
• Jsou-li znaky rohových nezletilých $H_(2m+1),\; H_(2m+2),\ldots,H_(m+n)$ se střídají a znaménko vedlejšího $H_(2m+1)$ se shoduje se znaménkem čísla $(-1)^(m+1 )$, pak studovaný stacionární bod je podmíněným maximálním bodem funkce $z=f(x_1,x_2,x_3,\ldots,x_n)$.

Příklad #1

Najděte podmíněný extrém funkce $z(x,y)=x+3y$ pod podmínkou $x^2+y^2=10$.

Geometrický výklad tohoto problému je následující: je potřeba najít největší a nejmenší hodnotu aplikace roviny $z=x+3y$ pro body jejího průsečíku s válcem $x^2+y^2 = 10 $.

Vyjádřit z omezující rovnice jednu proměnnou druhou a dosadit ji do funkce $z(x,y)=x+3y$ je poněkud obtížné, proto použijeme Lagrangeovu metodu.

Označením $\varphi(x,y)=x^2+y^2-10$ vytvoříme Lagrangeovu funkci:

$$ F(x,y)=z(x,y)+\lambda \varphi(x,y)=x+3y+\lambda(x^2+y^2-10);\\ \frac(\částečné F)(\částečné x)=1+2\lambda x; \frac(\částečné F)(\částečné y)=3+2\lambda y. $$

Zapišme si soustavu rovnic pro určení stacionárních bodů Lagrangeovy funkce:

$$ \left \( \začátek(zarovnáno) & 1+2\lambda x=0;\\ & 3+2\lambda y=0;\\ & x^2+y^2-10=0. \end (zarovnáno)\vpravo.$$

Pokud předpokládáme $\lambda=0$, pak první rovnice bude: $1=0$. Výsledný rozpor říká, že $\lambda\neq 0$. Za podmínky $\lambda\neq 0$ z první a druhé rovnice máme: $x=-\frac(1)(2\lambda)$, $y=-\frac(3)(2\lambda) $. Dosazením získaných hodnot do třetí rovnice dostaneme:

$$ \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); \left[ \begin(zarovnáno) & \lambda_1=-\frac(1)(2);\\ & \lambda_2=\frac(1)(2). \end(zarovnáno) \vpravo.\\ \begin(zarovnáno) & \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(zarovnáno) $$

Systém má tedy dvě řešení: $x_1=1;\; y_1=3;\; \lambda_1=-\frac(1)(2)$ a $x_2=-1;\; y_2=-3;\; \lambda_2=\frac(1)(2)$. Zjistěme povahu extrému v každém stacionárním bodě: $M_1(1;3)$ a $M_2(-1;-3)$. K tomu vypočítáme determinant $H$ v každém z bodů.

$$ \varphi_(x)^(")=2x;\; \varphi_(y)^(")=2y;\; F_(xx)^("")=2\lambda;\; F_(xy)^("")=0;\; F_(yy)^("")=2\lambda.\\ H=\left| \begin(array) (ccc) 0 & \varphi_(x)^(") & \varphi_(y)^(")\\ \varphi_(x)^(") & F_(xx)^("") & F_(xy)^("") \\ \varphi_(y)^(") & F_(xy)^("") & F_(yy)^("") \end(pole) \right|= \left| \begin(pole) (ccc) 0 & 2x & 2y\\ 2x & 2\lambda & 0 \\ 2y & 0 & 2\lambda \end(pole) \right|= 8\cdot\left| \begin(pole) (ccc) 0 & x & y\\ x & \lambda & 0 \\ y & 0 & \lambda \end(pole) \right| $$

V bodě $M_1(1;3)$ dostáváme: $H=8\cdot\left| \begin(pole) (ccc) 0 & x & y\\ x & \lambda & 0 \\ y & 0 & \lambda \end(pole) \right|= 8\cdot\left| \begin(pole) (ccc) 0 & 1 & 3\\ 1 & -1/2 & 0 \\ 3 & 0 & -1/2 \end(array) \right|=40 > 0$, takže v bodě $M_1(1;3)$ funkce $z(x,y)=x+3y$ má podmíněné maximum, $z_(\max)=z(1;3)=10$.

Podobně v bodě $M_2(-1;-3)$ najdeme: $H=8\cdot\left| \begin(pole) (ccc) 0 & x & y\\ x & \lambda & 0 \\ y & 0 & \lambda \end(pole) \right|= 8\cdot\left| \begin(pole) (ccc) 0 & -1 & -3\\ -1 & 1/2 & 0 \\ -3 & 0 & 1/2 \end(pole) \right|=-40$. Od $ H< 0$, то в точке $M_2(-1;-3)$ имеем условный минимум функции $z(x,y)=x+3y$, а именно: $z_{\min}=z(-1;-3)=-10$.

Podotýkám, že místo výpočtu hodnoty determinantu $H$ v každém bodě je mnohem pohodlnější jej otevřít obecně. Abych nezahltil text detaily, schovám tento způsob pod poznámku.

Determinant $H$ zápis v obecném tvaru. zobrazit/skrýt

$$ H=8\cdot\left|\begin(pole)(ccc)0&x&y\\x&\lambda&0\\y&0&\lambda\end(pole)\right| =8\cdot\left(-\lambda(y^2)-\lambda(x^2)\vpravo) =-8\lambda\cdot\left(y^2+x^2\vpravo). $$

V zásadě je již zřejmé, které znaménko $H$ má. Protože žádný z bodů $M_1$ nebo $M_2$ se neshoduje s počátkem, pak $y^2+x^2>0$. Znaménko $H$ je tedy opačné než znaménko $\lambda$. Můžete také dokončit výpočty:

$$ \začátek(zarovnáno) &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\left((-3)^2+(-1)^2\vpravo)=-40. \end(zarovnáno) $$

Otázku po povaze extrému ve stacionárních bodech $M_1(1;3)$ a $M_2(-1;-3)$ lze vyřešit bez použití determinantu $H$. Najděte znaménko $d^2F$ v každém stacionárním bodě:

$$ d^2 F=F_(xx)^("")dx^2+2F_(xy)^("")dxdy+F_(yy)^("")dy^2=2\lambda \left( dx^2+dy^2\vpravo) $$

Podotýkám, že zápis $dx^2$ znamená přesně $dx$ umocněné na druhou mocninu, tzn. $\left(dx\right)^2$. Máme tedy: $dx^2+dy^2>0$, takže pro $\lambda_1=-\frac(1)(2)$ dostaneme $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$.

Odpovědět: v bodě $(-1;-3)$ má funkce podmíněné minimum, $z_(\min)=-10$. V bodě $(1;3)$ má funkce podmíněné maximum, $z_(\max)=10$

Příklad č. 2

Najděte podmíněný extrém funkce $z(x,y)=3y^3+4x^2-xy$ pod podmínkou $x+y=0$.

První způsob (metoda Lagrangeových multiplikátorů)

Označením $\varphi(x,y)=x+y$ složíme Lagrangeovu funkci: $F(x,y)=z(x,y)+\lambda \varphi(x,y)=3y^3+4x ^2 -xy+\lambda(x+y)$.

$$ \frac(\částečné F)(\částečné x)=8x-y+\lambda; \; \frac(\částečné F)(\částečné y)=9y^2-x+\lambda.\\ \left \( \begin(zarovnáno) & 8x-y+\lambda=0;\\ & 9y^2-x+\ lambda=0;\\&x+y=0.\end(zarovnáno)\vpravo.$$

Řešením systému dostaneme: $x_1=0$, $y_1=0$, $\lambda_1=0$ a $x_2=\frac(10)(9)$, $y_2=-\frac(10)(9 )$, $\lambda_2=-10$. Máme dva stacionární body: $M_1(0;0)$ a $M_2 \left(\frac(10)(9);-\frac(10)(9) \right)$. Zjistime povahu extrému v každém stacionárním bodě pomocí determinantu $H$.

$$ H=\left| \begin(array) (ccc) 0 & \varphi_(x)^(") & \varphi_(y)^(")\\ \varphi_(x)^(") & F_(xx)^("") & F_(xy)^("") \\ \varphi_(y)^(") & F_(xy)^("") & F_(yy)^("") \end(pole) \right|= \left| \begin(pole) (ccc) 0 & 1 & 1\\ 1 & 8 & -1 \\ 1 & -1 & 18y \end(pole) \right|=-10-18y $$

V bodě $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$, takže v tomto okamžiku má funkce podmíněné maximum, $z_(\max)=\frac(500)(243)$.

Zkoumáme povahu extrému v každém z bodů jinou metodou na základě znaménka $d^2F$:

$$ d^2 F=F_(xx)^("")dx^2+2F_(xy)^("")dxdy+F_(yy)^("")dy^2=8dx^2-2dxdy+ 18ydy ^2 $$

Z omezující rovnice $x+y=0$ máme: $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 $$

Protože $ d^2F \Bigr|_(M_1)=10 dx^2 > 0$, pak $M_1(0;0)$ je podmíněný minimální bod funkce $z(x,y)=3y^3+ 4x^ 2-xy$. Podobně $d^2F \Bigr|_(M_2)=-10 dx^2< 0$, т.е. $M_2\left(\frac{10}{9}; -\frac{10}{9} \right)$ - точка условного максимума.

Druhý způsob

Z omezující rovnice $x+y=0$ dostaneme: $y=-x$. Dosazením $y=-x$ do funkce $z(x,y)=3y^3+4x^2-xy$ získáme nějakou funkci proměnné $x$. Označme tuto funkci jako $u(x)$:

$$ u(x)=z(x,-x)=3\cdot(-x)^3+4x^2-x\cdot(-x)=-3x^3+5x^2. $$

Redukovali jsme tedy problém hledání podmíněného extrému funkce dvou proměnných na problém určení extrému funkce jedné proměnné.

$$ 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).$$

Získali jste body $M_1(0;0)$ a $M_2\left(\frac(10)(9); -\frac(10)(9)\right)$. Další výzkum je znám z průběhu diferenciálního počtu funkcí jedné proměnné. Zkoumáním znaménka $u_(xx)^("")$ v každém stacionárním bodě nebo kontrolou změny znaménka $u_(x)^(")$ v nalezených bodech získáme stejné závěry jako v prvním řešení . Například zaškrtněte znak $u_(xx)^("")$:

$$u_(xx)^("")=-18x+10;\\ u_(xx)^("")(M_1)=10;\;u_(xx)^("")(M_2)=- 10, $ $

Protože $u_(xx)^("")(M_1)>0$, pak $M_1$ je minimální bod funkce $u(x)$, zatímco $u_(\min)=u(0)=0 $ . Od $u_(xx)^("")(M_2)<0$, то $M_2$ - точка максимума функции $u(x)$, причём $u_{\max}=u\left(\frac{10}{9}\right)=\frac{500}{243}$.

Hodnoty funkce $u(x)$ za dané podmínky připojení se shodují s hodnotami funkce $z(x,y)$, tzn. nalezené extrémy funkce $u(x)$ jsou požadované podmíněné extrémy funkce $z(x,y)$.

Odpovědět: v bodě $(0;0)$ má funkce podmíněné minimum, $z_(\min)=0$. V bodě $\left(\frac(10)(9); -\frac(10)(9) \right)$ má funkce podmíněné maximum, $z_(\max)=\frac(500)(243 )$.

Uvažujme ještě jeden příklad, ve kterém zjistíme povahu extrému určením znaménka $d^2F$.

Příklad č. 3

Najděte maximální a minimální hodnoty funkce $z=5xy-4$, pokud jsou proměnné $x$ a $y$ kladné a splňují omezující rovnici $\frac(x^2)(8)+\frac( y^2)(2) -1=0$.

Složte Lagrangeovu funkci: $F=5xy-4+\lambda \left(\frac(x^2)(8)+\frac(y^2)(2)-1 \right)$. Najděte stacionární body Lagrangeovy funkce:

$$ F_(x)^(")=5y+\frac(\lambda x)(4); \; F_(y)^(")=5x+\lambda y.\\ \left \( \begin(zarovnáno) & 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(zarovnáno) \right.$$

Všechny další transformace se provádějí s přihlédnutím k $x > 0; \; y > 0 $ (to je stanoveno v podmínce problému). Z druhé rovnice vyjádříme $\lambda=-\frac(5x)(y)$ a nalezenou hodnotu dosadíme do první rovnice: $5y-\frac(5x)(y)\cdot \frac(x)( 4)=0$, $4y^2-x^2=0$, $x=2y$. Dosazením $x=2y$ do třetí rovnice dostaneme: $\frac(4y^2)(8)+\frac(y^2)(2)-1=0$, $y^2=1$, $y = 1 $.

Protože $y=1$, pak $x=2$, $\lambda=-10$. Povaha extrému v bodě $(2;1)$ je určena ze znaménka $d^2F$.

$$ F_(xx)^("")=\frac(\lambda)(4); \; F_(xy)^("")=5; \; F_(yy)^("")=\lambda. $$

Protože $\frac(x^2)(8)+\frac(y^2)(2)-1=0$, pak:

$$ d\left(\frac(x^2)(8)+\frac(y^2)(2)-1\right)=0; \; d\left(\frac(x^2)(8) \right)+d\left(\frac(y^2)(2) \right)=0; \; \frac(x)(4)dx+ydy=0; \; dy=-\frac(xdx)(4y). $$

V zásadě zde můžete okamžitě dosadit souřadnice stacionárního bodu $x=2$, $y=1$ a parametr $\lambda=-10$, čímž získáte:

$$ 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) \vpravo)^2=\\ =-\frac(5)(2)dx^2-5dx^2-\frac(5)(2)dx^2=-10dx^2. $$

V jiných problémech pro podmíněný extrém však může existovat několik stacionárních bodů. V takových případech je lepší znázornit $d^2F$ v obecném tvaru a poté dosadit souřadnice každého z nalezených stacionárních bodů do výsledného výrazu:

$$ 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)=\left(\frac(\lambda )(4)-\frac(5x)(2y)+\frac(\lambda \cdot x^2)(16y^2) \right)\cdot dx^2 $$

Dosazením $x=2$, $y=1$, $\lambda=-10$ dostaneme:

$$ d^2 F=\left(\frac(-10)(4)-\frac(10)(2)-\frac(10 \cdot 4)(16) \right)\cdot dx^2=- 10dx^2. $$

Protože $d^2F=-10\cdot dx^2< 0$, то точка $(2;1)$ есть точкой условного максимума функции $z=5xy-4$, причём $z_{\max}=10-4=6$.

Odpovědět: v bodě $(2;1)$ má funkce podmíněné maximum, $z_(\max)=6$.

V další části se budeme zabývat aplikací Lagrangeovy metody pro funkce více proměnné.

Z Podstatou Lagrangeovy metody je redukovat problém podmíněného extrému na řešení problému nepodmíněného extrému. Zvažte model nelineárního programování:

(5.2)

kde
jsou známé funkce,

A
jsou uvedeny koeficienty.

Všimněte si, že v této formulaci problému jsou omezení dána rovností a není zde žádná podmínka, aby proměnné byly nezáporné. Kromě toho předpokládáme, že funkce
jsou spojité se svými prvními parciálními derivacemi.

Transformujme podmínky (5.2) tak, aby levá nebo pravá část rovnosti obsahovala nula:

(5.3)

Pojďme složit Lagrangeovu funkci. Zahrnuje účelovou funkci (5.1) a pravé strany omezení (5.3), v tomto pořadí s koeficienty
. V problému bude tolik Lagrangeových koeficientů, kolik bude omezení.

Extrémní body funkce (5.4) jsou extremní body původního problému a naopak: optimální plán úlohy (5.1)-(5.2) je globální extremní bod Lagrangeovy funkce.

Opravdu, ať se najde řešení
problém (5.1)-(5.2), pak jsou splněny podmínky (5.3). Pojďme nahradit plán
do funkce (5.4) a ověřte platnost rovnosti (5.5).

Abychom tedy našli optimální plán původního problému, je nutné prozkoumat Lagrangeovu funkci pro extrém. Funkce má extrémní hodnoty v bodech, kde jsou její parciální derivace stejné nula. Takové body se nazývají stacionární.

Definujeme parciální derivace funkce (5.4)

,

.

Po vyrovnání nula deriváty dostaneme systém m+n rovnice s m+n neznámý

,(5.6)

V obecném případě bude mít systém (5.6)-(5.7) několik řešení, která zahrnují všechna maxima a minima Lagrangeovy funkce. Aby bylo zvýrazněno globální maximum nebo minimum, jsou hodnoty cílové funkce vypočteny ve všech nalezených bodech. Největší z těchto hodnot bude globální maximum a nejmenší bude globální minimum. V některých případech je možné použít dostatečné podmínky pro přísný extrém spojité funkce (viz problém 5.2 níže):

nechat funkci
je spojitý a dvakrát diferencovatelný v nějakém sousedství svého stacionárního bodu (ti.
)). Pak:

A ) pokud
, (5.8)

pak je striktní maximální bod funkce
;

b) -li
, (5.9)

pak je striktní minimální bod funkce
;

G ) pokud
,

pak zůstává otázka přítomnosti extrému otevřená.

Navíc některá řešení systému (5.6)-(5.7) mohou být záporná. Což není v souladu s ekonomickým významem proměnných. V tomto případě by měla být analyzována možnost nahrazení záporných hodnot nulou.

Ekonomický význam Lagrangeových multiplikátorů. Optimální hodnota multiplikátoru
ukazuje, jak moc se změní hodnota kritéria Z při zvyšování nebo snižování zdroje j na jednotku, protože

Lagrangeovu metodu lze také použít, když jsou omezeními nerovnosti. Takže hledání extrému funkce
za podmínek

,

se provádí v několika fázích:

1. Určete stacionární body účelové funkce, pro které řeší soustavu rovnic

.

2. Ze stacionárních bodů se vyberou ty, jejichž souřadnice splňují podmínky

3. K řešení problému s omezeními rovnosti (5.1)-(5.2) se používá Lagrangeova metoda.

4. Body nalezené ve druhém a třetím stupni se zkoumají na globální maximum: porovnávají se hodnoty účelové funkce v těchto bodech - největší hodnota odpovídá optimálnímu plánu.

Úkol 5.1 Vyřešme problém 1.3, uvažovaný v první části, Lagrangeovou metodou. Optimální rozložení vodních zdrojů popisuje matematický model

.

Sestavte Lagrangeovu funkci

Najděte nepodmíněné maximum této funkce. K tomu vypočítáme parciální derivace a přirovnáme je k nule

,

Tak jsme získali soustavu lineárních rovnic tvaru

Řešení soustavy rovnic je optimálním plánem rozložení vodních zdrojů na zavlažované plochy

, .

Množství
měřeno ve stovkách tisíc metrů krychlových.
- výše čistého příjmu na sto tisíc metrů krychlových závlahové vody. Proto je mezní cena 1 m 3 závlahové vody
doupě. Jednotky

Maximální dodatečný čistý příjem ze zavlažování bude

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

172391,02 (den. jednotky)

Úkol 5.2 Vyřešte problém nelineárního programování

Omezení reprezentujeme jako:

.

Sestavte Lagrangeovu funkci a určete její parciální derivace

.

Abychom určili stacionární body Lagrangeovy funkce, měli bychom přirovnat její parciální derivace k nule. Výsledkem je soustava rovnic

.

Z první rovnice vyplývá

. (5.10)

Výraz dosadit do druhé rovnice

,

z nichž existují dvě řešení pro :

a
. (5.11)

Dosazením těchto řešení do třetí rovnice získáme

,
.

Hodnoty Lagrangeova multiplikátoru a neznáma vypočítat pomocí výrazů (5.10)-(5.11):

,
,
,
.

Dostali jsme tedy dva extrémní body:

;
.

Abychom zjistili, zda jsou tyto body maximální nebo minimální, používáme dostatečné podmínky pro přísný extrém (5.8)-(5.9). Předvýraz pro , získaný z omezení matematického modelu, dosadíme do účelové funkce

,

. (5.12)

Abychom zkontrolovali podmínky pro striktní extrém, měli bychom určit znaménko druhé derivace funkce (5.11) v extrémních bodech, které jsme našli
a
.

,
;

.

Takto, (·)
je minimální bod původního problému (
), a (·)
- maximální bod.

Optimální plán:

,
,
,

.

LAGRANGEOVA METODA

Metoda redukce kvadratické formy na součet čtverců, kterou v roce 1759 naznačil J. Lagrange. Ať je dáno

z proměnných x 0 , X 1 ,..., x n. s koeficienty z oboru k charakteristika Je požadováno uvést tento formulář do kanonické podoby. mysl

s pomocí nedegenerovat lineární transformace proměnné. L. m. se skládá z následujícího. Můžeme předpokládat, že ne všechny koeficienty tvaru (1) jsou rovny nule. Jsou tedy možné dva případy.

1) Pro některé G, diagonální Pak

kde tvar f 1 (x) neobsahuje proměnnou x g . 2) Pokud všechny ale pak

kde tvar f 2 (x) neobsahuje dvě proměnné x g a x h . Tvary pod čtvercovými znaménky v (4) jsou lineárně nezávislé. Aplikací transformací tvaru (3) a (4) se tvar (1) po konečném počtu kroků zredukuje na součet čtverců lineárně nezávislých lineárních tvarů. Pomocí parciálních derivací lze vzorce (3) a (4) zapsat jako

Lit.: G a n t m a h e r F. R., Teorie matic, 2. vyd., Moskva, 1966; K u o sh A. G., Kurz vyšší algebry, 11. vyd., M., 1975; Alexandrov P.S., Přednášky o analytické geometrii..., M., 1968. I. V. Proskuryakov.

Matematická encyklopedie. - M.: Sovětská encyklopedie. I. M. Vinogradov. 1977-1985.

Podívejte se, co je "LAGRANGE METODA" v jiných slovnících:

Lagrangeova metoda- Lagrangeova metoda - metoda pro řešení řady tříd úloh matematického programování nalezením sedlového bodu (x *, λ *) Lagrangeovy funkce, čehož dosáhneme vyrovnáním parciálních derivací této funkce vzhledem k . ... ... Ekonomický a matematický slovník

Lagrangeova metoda- Metoda pro řešení řady tříd úloh matematického programování nalezením sedlového bodu (x*,?*) Lagrangeovy funkce, čehož se dosáhne nulováním parciálních derivací této funkce vzhledem k xi a?i . Viz Lagrangian. )