Използвайки метода на неопределените множители на Лагранж, намерете условния екстремум. Метод на умножителя на Лагранж за функции на две променливи
Метод на умножителя на Лагранже класически метод за решаване на проблеми математическо програмиране(по-специално изпъкнал). За съжаление кога практическо приложениеМетодът може да срещне значителни изчислителни затруднения, стесняващи обхвата на неговото използване. Разглеждаме метода на Лагранж тук главно защото той е апарат, който се използва активно за обосноваване на различни съвременни числени методи, широко използвани в практиката. Що се отнася до функцията на Лагранж и множителите на Лагранж, те играят независима и изключителна функция важна роляв теорията и приложенията не само на математическото програмиране.
Нека помислим класически проблемоптимизация
макс. (мин.) z=f(x) (7.20)
Този проблем се отличава от проблем (7.18), (7.19) по това, че сред ограниченията (7.21) няма неравенства, няма условия променливите да бъдат неотрицателни, тяхната дискретност и функциите f(x) са непрекъснати и имат частни производни по отношение на поневтора поръчка.
Класическият подход за решаване на задача (7.20), (7.21) дава система от уравнения ( необходимите условия), което трябва да бъде удовлетворено от точката x*, която осигурява на функцията f(x) локален екстремум върху множеството от точки, удовлетворяващи ограничения (7.21) (за проблема с изпъкнало програмиране, намерената точка x*, в съответствие с Теорема 7.6, ще бъде едновременно точката на глобалния екстремум).
Да приемем, че в точката x* функцията (7.20) има локал условна крайности рангът на матрицата е. Тогава необходимите условия ще бъдат записани във формата:
(7.22)
има функция на Лагранж; - Множители на Лагранж.
Също така има достатъчни условия, при което решението на системата от уравнения (7.22) определя точката на екстремума на функцията f(x). Този въпрос се решава въз основа на изследването на знака на втория диференциал на функцията на Лагранж. Достатъчните условия обаче представляват предимно теоретичен интерес.
Можете да зададете следната процедура за решаване на задача (7.20), (7.21), като използвате метода на умножителя на Лагранж:
1) съставете функцията на Лагранж (7.23);
2) намерете частните производни на функцията на Лагранж по отношение на всички променливи 
и ги задайте равни на нула. Това ще доведе до система (7.22), състояща се от уравнения. Решете получената система (ако това се окаже възможно!) и по този начин намерете всички стационарни точки на функцията на Лагранж;
3) от стационарни точки, взети без координати, изберете точки, в които функцията f(x) има условни локални екстремуми при наличие на ограничения (7.21). Този избор се прави, например, като се използват достатъчни условия за локален екстремум. Често изследването се опростява, ако се използват специфични условия на проблема.
Пример 7.3. намирам оптимално разпределениеограничен ресурс в единица. между n потребители, ако печалбата, получена от разпределянето на x j единици ресурс на j-тия потребител, се изчислява по формулата .
Решение.Математическият модел на задачата има следния вид:
Съставяме функцията на Лагранж:
.
Намираме частични производни на функцията на Лагранж и ги приравняваме към нула:
Решавайки тази система от уравнения, получаваме:
Така, ако на j-тия потребител са разпределени единици. ресурс, тогава общата печалба ще достигне максималната си стойност и ще възлиза на ден. единици
Разгледахме метода на Лагранж, приложен към класически оптимизационен проблем. Този метод може да се обобщи за случая, когато променливите са неотрицателни и някои ограничения са дадени под формата на неравенства. Това обобщение обаче е предимно теоретично и не води до конкретни изчислителни алгоритми.
В заключение, нека дадем множителите на Лагранж икономическа интерпретация. За да направим това, нека се обърнем към най-простия класически проблем за оптимизация
макс. (мин.) z=f(х 1 , х 2); (7.24)
𝜑(x 1, x 2)=b. (7,25)
Да приемем, че условният екстремум е достигнат в точка . Съответната екстремна стойност на функцията f(х)
Да приемем, че в ограниченията (7.25) количеството bмогат да се променят, тогава координатите на екстремалната точка и следователно екстремната стойност е*функции f(х) ще станат количества в зависимост от b, т.е. 
,
и следователно производната на функция (7.24)
Метод на множителяЛагранж(в англоезичната литература „Методът на LaGrange на неопределените множители“) ˗ е числен метод за решаване на оптимизационни проблеми, който ви позволява да определите „условния“ екстремум на целевата функция (минимална или максимална стойност)
при наличието на определени ограничения върху неговите променливи под формата на равенства (т.е. площта приемливи стойности)
˗ това са стойностите на аргумента на функцията (контролируеми параметри) в реалната област, при която стойността на функцията клони към екстремум. Използването на наименованието „условен“ екстремум се дължи на факта, че променливите са подчинени на допълнително условие, което ограничава обхвата на приемливите стойности при търсене на екстремума на функция.
Методът на умножителя на Лагранж позволява проблемът за търсене на условен екстремум на целева функция върху набор от допустими стойности да се трансформира в проблема безусловна оптимизацияфункции.
В случай, че функциите 
И 
са непрекъснати заедно с техните частни производни, тогава има такива променливи λ, които не са едновременно равни на нула, при които е изпълнено следното условие:
Така, в съответствие с метода на умножителя на Лагранж, за да намеря екстремума на целевата функция върху множеството от допустими стойности, съставям функцията на Лагранж L(x, λ), която е допълнително оптимизирана:
където λ ˗ е вектор от допълнителни променливи, наречени неопределени множители на Лагранж.
Така проблемът за намиране на условния екстремум на функцията f(x) се свежда до проблема за намиране на безусловния екстремум на функцията L(x, λ).
И 
Необходимото условие за екстремума на функцията на Лагранж се дава от система от уравнения (системата се състои от „n + m“ уравнения):
Решаването на тази система от уравнения ни позволява да определим аргументите на функцията (X), при които стойността на функцията L(x, λ), както и стойността на целевата функция f(x) съответстват на екстремума.
Големината на множителите на Лагранж (λ) е от практически интерес, ако ограниченията са представени във вид със свободен член в уравнението (константа). В този случай можем да разгледаме допълнително (увеличаване/намаляване) стойността на целевата функция чрез промяна на стойността на константата в системата от уравнения. По този начин множителят на Лагранж характеризира скоростта на промяна на максимума на целевата функция при промяна на ограничаващата константа.
Има няколко начина да се определи естеството на екстремума на получената функция:
Първи метод: Нека е координатите на екстремалната точка и е съответната стойност на целевата функция. Взема се точка, близка до точката, и се изчислява стойността на целевата функция:
Ако 
, тогава има максимум в точката.
Ако 
, тогава има минимум в точката.
Втори метод: Достатъчно условие, от което може да се определи естеството на екстремума, е знакът на втория диференциал на функцията на Лагранж. Вторият диференциал на функцията на Лагранж се дефинира, както следва:
Ако в дадена точка 
минимум, ако 
, тогава целевата функция f(x) има условие максимум.
Трети метод: Също така, природата на екстремума на функцията може да се определи чрез разглеждане на Хесиана на функцията на Лагранж. Матрицата на Хесен е симетрична квадратна матрицавтори частни производни на функция в точката, в която матричните елементи са симетрични спрямо главния диагонал.
За да определите вида на екстремума (максимум или минимум на функция), можете да използвате правилото на Силвестър:
1. За да бъде вторият диференциал на функцията на Лагранж с положителен знак 
необходимо е ъгловите минори на функцията да са положителни. При такива условия функцията в тази точка има минимум.
2. За да бъде вторият диференциал на функцията на Лагранж с отрицателен знак 
, необходимо е ъгловите минори на функцията да се редуват, а първият елемент на матрицата трябва да е negativesv. При такива условия функцията в тази точка има максимум.
Под ъглов минор имаме предвид минора, разположен в първите k реда и k колони на оригиналната матрица.
Основното практическо значение на метода на Лагранж е, че ви позволява да преминете от условна оптимизация към безусловна оптимизация и съответно да разширите своя арсенал налични методиразрешаване на проблема. Въпреки това, проблемът за решаване на система от уравнения, който се свежда до този метод, като цяло не е по-просто първоначален проблемтърсене на екстремум. Такива методи се наричат индиректни. Използването им се обяснява с необходимостта да се получи решение на екстремален проблем в аналитична форма (например за определени теоретични изчисления). При решаване на конкретни практически проблемиОбикновено се използват директни методи, базирани на итеративни процеси на изчисляване и сравняване на стойностите на функциите, които се оптимизират.
Метод на изчисление
1 стъпка: Определяме функцията на Лагранж от дадената целева функция и система от ограничения:
Напред
За да добавите коментар към статията, моля, регистрирайте се на сайта.
Помислете за ограничен оптимизационен проблем, съдържащ само ограничения под формата на равенства
мин 
предмет на ограничения
,
.
Този проблем по принцип може да бъде решен като неограничен оптимизационен проблем, получен чрез елиминиране на m независими променливи от целевата функция, като се използват дадени равенства. Наличието на ограничения под формата на равенства всъщност прави възможно намаляването на размерността на първоначалния проблем. Новият проблем може да бъде решен с помощта на подходящ неограничен метод за оптимизация.
Пример. Необходимо е да се минимизира функцията
когато е ограничен
Чрез изключване на променливата 
използвайки уравнението, получаваме оптимизационен проблем с две променливи без ограничения:
минимизиране,
които могат да бъдат решени с помощта на един от методите за безусловна оптимизация.
Методът на елиминиране на променливите обаче е приложим само в случаите, когато уравненията, представляващи ограниченията, могат да бъдат решени по отношение на определен набор от променливи. Ако има голям брой ограничения под формата на равенства, процесът на елиминиране на променливите се превръща в много трудоемка процедура. Освен това може да има ситуации, при които уравнението не може да бъде решено по отношение на променлива. В този случай е препоръчително да използвате метода на умножителя на Лагранж.
Използвайки метода на умножителя на Лагранж, по същество се установяват необходимите условия, за да се позволи идентифицирането на оптимални точки в оптимизационни проблеми с ограничения на равенството.
Нека разгледаме проблема
мин 
предмет на ограничения
,
.
От курса на математическия анализ е добре известно, че условната минимална точка на функцията 
съвпада със седловата точка на функцията на Лагранж:
,
в този случай седловата точка трябва да осигурява минимум по отношение на променливите 
и максимални параметри 
. Тези параметри се наричат множители на Лагранж. Приравняване на частни производни на функции 
от 
и от 
до нула, получаваме необходимите условия за неподвижна точка:
,
,
,
.
Системно решение 
уравнения определя стационарната точка на функцията на Лагранж. Достатъчните условия за съществуването на минимум от първоначалния проблем съдържат, в допълнение към споменатите по-горе, положителната определеност на матрицата на Хесиан на целевата функция.
4.2. Условия на Coon-tucker
Нека не разглеждаме проблема линейно програмиранес ограничения под формата на неравенства
мин 
под ограничения
,
.
Нека намалим ограниченията под формата на неравенства до ограничения за равенство, като добавим отслабващи променливи към всяко от тях 
,
:
.
Нека формираме функцията на Лагранж:
Тогава се оформят необходимите условия за минимум
,
;
,
;
, 
.
Можете да умножите последното уравнение по 
и заменете отслабващите променливи, като ги изразите от второто уравнение. Второто уравнение може да се трансформира чрез отхвърляне на отслабващите променливи и преминаване към ограничения на неравенството. Трябва да се добави още едно условие 
, която трябва да бъде изпълнена в условната минимална точка.
Накрая получаваме необходимите условия за съществуването на минимум проблем с нелинейно програмиране с ограничения на неравенството, които се наричат условия на Kuhn-Tucker:
,
;
(1)
,
;
(2)
,
;
(3)
,
.
(4)
Ограничение на неравенството 
наречен активен в точка 
, ако се превърне в равенство 
, и се нарича неактивен, ако 
. Ако е възможно да се открият, преди директно решаване на проблема, ограничения, които са неактивни в оптималната точка, тогава тези ограничения могат да бъдат изключени от модела и по този начин да се намали неговият размер.
Уравнение (3) означава, че или 
, или 
. Ако 
, Че 
и ограничението е активно и представлява ограничение за равенство. От друга страна, ако ограничението е строго неравенство 
, тогава множителят на Лагранж ще има формата 
тези. ограничение 
е неактивен и може да бъде игнориран. Разбира се, не е известно предварително какви ограничения могат да бъдат пренебрегнати.
Описание на метода
Където . Обосновка
Следното оправдание за метода на умножителя на Лагранж не е строго доказателство за него. Той съдържа евристични разсъждения, за да помогне за разбирането геометричен смисълметод.
Двуизмерен калъф
Нивелирани линии и крива.
Нека се изисква да се намери екстремумът на някаква функция на две променливи при условието, определено от уравнението 
. Ще приемем, че всички функции са непрекъснато диференцируеми и това уравнение дефинира гладка крива Сна повърхността. Тогава задачата се свежда до намиране на екстремума на функцията fна кривата С. Това също ще приемем Сне преминава през точки, където градиентът fсе превръща в 0.
Нека начертаем линии на функционално ниво на равнината f(тоест криви). От геометричните съображения става ясно, че екстремумът на функцията fна кривата Сможе да има само точки, в които допирателните към Си съответната линия на ниво съвпадат. Наистина, ако кривата Спресича линията на нивото fв точка напречно (тоест под някакъв ненулев ъгъл), след което се движи по кривата Сот точка можем да стигнем до линиите на нивото, съответстващи на по-голяма стойност f, и по-малко. Следователно такава точка не може да бъде точка на екстремум.
Следователно необходимо условие за екстремум в нашия случай ще бъде съвпадението на допирателните. За да го напишете в аналитична форма, имайте предвид, че е еквивалентно на паралелизма на градиентите на функциите fи ψ в дадена точка, тъй като векторът на градиента е перпендикулярен на допирателната към линията на нивото. Това условие се изразява в следната форма:
където λ е ненулево число, което е множител на Лагранж.
Нека сега да разгледаме Функция на Лагранж, в зависимост от и λ:
Необходимо условие за неговия екстремум е градиентът да е равен на нула. В съответствие с правилата за диференциация се записва във формуляра
Получихме система, чиито първи две уравнения са еквивалентни на необходимото условие за локален екстремум (1), а третото е еквивалентно на уравнението . Можете да го намерите от него. Освен това, тъй като в противен случай градиентът на функцията fизчезва в точката 
, което противоречи на нашите предположения. Трябва да се отбележи, че така намерените точки може да не са желаните точки на условния екстремум – разглежданото условие е необходимо, но не достатъчно. Намиране на условен екстремум с помощта на спомагателна функция Ли формира основата на метода на умножителя на Лагранж, приложен тук за най-простия случай на две променливи. Оказва се, че горните разсъждения са обобщени за случая произволен бройпроменливи и уравнения, които задават условия.
Въз основа на метода на умножителя на Лагранж е възможно да се докажат някои достатъчни условия за условен екстремум, които изискват анализ на вторите производни на функцията на Лагранж.
Приложение
- Методът на умножителя на Лагранж се използва за решаване на проблеми с нелинейното програмиране, които възникват в много области (например в икономиката).
- Основният метод за решаване на проблема с оптимизирането на качеството на кодиране на аудио и видео данни при даден среден битрейт (оптимизация на изкривяването - английски. Rate-Distortion оптимизация).
Вижте също
Връзки
- Зорич В. А. Математически анализ. Част 1. - изд. 2-ро, рев. и допълнителни - М.: ФАЗИС, 1997.
Фондация Уикимедия. 2010 г.
Вижте какво представляват „множителите на Лагранж“ в други речници:
Множители на Лагранж- допълнителни трансформиращи фактори целева функцияекстремен проблем на изпъкнало програмиране (по-специално линейно програмиране), когато се решава от един от класически методиметод за разрешаване на множители...... Икономико-математически речник
Множители на Лагранж- Допълнителни фактори, които трансформират целевата функция на проблем с екстремално изпъкнало програмиране (по-специално линейно програмиране), когато се решава с помощта на един от класическите методи, методът за разрешаване на множители (метод на Лагранж).... ... Ръководство за технически преводач
Механика. 1) Уравнения на Лагранж от 1-ви род, диференциални уравнения на механичното движение. системи, които са дадени в проекции върху правоъгълни координатни оси и съдържат т.нар. Множители на Лагранж. Получено от J. Lagrange през 1788 г. За холономна система, ... ... Физическа енциклопедия
Обикновена механика диференциални уравнения 2-ри ред, описващ движенията на механ. системи под въздействието на приложени към тях сили. Л.у. установен от J. Lag диапазон в две форми: L. u. 1-ви вид, или уравнения в декартови координати с... ... Математическа енциклопедия
1) в хидромеханиката, уравнението на движението на течност (газ) в променливи на Лагранж, които са координатите на средата. Получи френски учен J. Lagrange (ок. 1780). От Л. у. законът за движение на средата се определя под формата на зависимости... ... Физическа енциклопедия
Метод на умножителя на Лагранж, метод за намиране на условния екстремум на функцията f(x), където, спрямо m ограничения, i варира от едно до m. Съдържание 1 Описание на метода ... Wikipedia
Функция, използвана при решаване на проблеми с условния екстремум на функции на много променливи и функционали. С помощта на L. f. записват се необходимите условия за оптималност при задачи върху условен екстремум. В този случай не е необходимо да се изразяват само променливи... Математическа енциклопедия
Метод за решаване на задачи върху условен екстремум; L.M.M. се състои в свеждането на тези задачи до задачи върху безусловния екстремум на спомагателна функция, т.нар. Функции на Лагранж. За проблема за екстремума на функцията f (x1, x2,..., xn) за... ...
Променливи, с помощта на които се конструира функцията на Лагранж при изследване на задачи върху условен екстремум. Използването на линейни методи и функцията на Лагранж ни позволява да получим необходимите условия за оптималност в проблеми, включващи условен екстремум по еднакъв начин... Математическа енциклопедия
1) в хидромеханиката, уравненията на движение на течна среда, записани в променливи на Лагранж, които са координатите на частиците на средата. От Л. у. законът за движение на частиците на средата се определя под формата на зависимости на координатите от времето и от тях... ... Велика съветска енциклопедия
Кратка теория
Методът на умножителя на Лагранж е класически метод за решаване на задачи по математическо програмиране (по-специално изпъкнали). За съжаление, практическото приложение на метода може да срещне значителни изчислителни затруднения, стесняващи обхвата на неговото използване. Тук разглеждаме метода на Лагранж главно защото това е апарат, който се използва активно за обосноваване на различни съвременни числени методи, които се използват широко в практиката. Що се отнася до функцията на Лагранж и множителите на Лагранж, те играят независима и изключително важна роля в теорията и приложенията не само на математическото програмиране.
Помислете за класически оптимизационен проблем:
Сред ограниченията на тази задача няма неравенства, няма условия за неотрицателност на променливите, тяхната дискретност, а функциите са непрекъснати и имат частни производни поне от втори ред.
Класическият подход за решаване на проблема предоставя система от уравнения (необходими условия), които трябва да бъдат удовлетворени от точката, която осигурява на функцията локален екстремум върху множеството от точки, които удовлетворяват ограниченията (за проблем с изпъкнало програмиране, намерената точка ще бъде и глобалната екстремна точка).
Да приемем, че в точка функция (1) има локален условен екстремум и рангът на матрицата е равен на . Тогава необходимите условия ще бъдат записани във формата:
има функция на Лагранж; – Множители на Лагранж.
Съществуват и достатъчни условия, при които решението на системата от уравнения (3) определя точката на екстремума на функцията. Този въпрос се решава въз основа на изследването на знака на втория диференциал на функцията на Лагранж. Достатъчните условия обаче представляват предимно теоретичен интерес.
Можете да зададете следната процедура за решаване на задача (1), (2) с помощта на метода на умножителя на Лагранж:
1) съставете функцията на Лагранж (4);
2) намерете частичните производни на функцията на Лагранж по отношение на всички променливи и ги приравнете
нула. Така ще се получи система (3), състояща се от уравнения Решете получената система (ако това се окаже възможно!) и така намерете всички стационарни точки на функцията на Лагранж;
3) от стационарни точки, взети без координати, изберете точки, в които функцията има условни локални екстремуми при наличие на ограничения (2). Този избор се прави, например, като се използват достатъчни условия за локален екстремум. Често изследването се опростява, ако се използват специфични условия на проблема.
Пример за решение на проблем
Задачата
Фирмата произвежда два вида стоки в количества и . Функцията на полезния разход се определя от отношението . Цените на тези стоки на пазара са еднакви и съотв.
Определете при какви обеми на продукцията се постига максимална печалбаи на какво е равно, ако общите разходи не надвишават
Имате проблеми с разбирането на напредъка на дадено решение? Уебсайтът предлага услуга Решаване на проблеми с помощта на методи за оптимални решения по поръчка
Решението на проблема
Икономически и математически модел на задачата
Функция печалба:
Ограничения на разходите:
Получаваме следния икономико-математически модел:
Освен това според смисъла на задачата
Метод на умножителя на Лагранж
Нека съставим функцията на Лагранж:
Намираме частичните производни от 1-ви ред:
Нека създадем и решим система от уравнения:
От тогава
Максимална печалба:
Отговор
По този начин е необходимо да се освободи храна. стоки от 1-ви вид и бр. стоки от 2-ри вид. В този случай печалбата ще бъде максимална и ще възлиза на 270.
Даден е пример за решаване на задача от квадратично изпъкнало програмиране с помощта на графичен метод.
Решаване на линейна задача по графичен метод
Разглеждан графичен методрешаване на задача за линейно програмиране (LPP) с две променливи. Дава се примерна задача Подробно описаниеконструиране на чертеж и намиране на решение.
Моделът на Уилсън за управление на запасите
Използвайки примера за решаване на проблема, се разглежда основният модел за управление на запасите (модел на Уилсън). Изчислени са следните показатели на модела: оптимален размерколичества за поръчка, годишни разходи за съхранение, интервали на доставка и точка на поръчка.
Матрица на съотношението на директните разходи и матрица на входно-изходните данни
Използвайки примера за решаване на проблем, се разглежда междусекторният модел на Леонтиев. Показано е изчисляването на матрицата на коефициентите на преките материални разходи, матрицата на „вложените ресурси“, матрицата на коефициентите на непреките разходи, векторите на крайното потребление и брутната продукция.