Условные экстремумы и метод множителей лагранжа. Метод Лагранжа (метод вариации произвольных постоянных)
Краткая теория
Метод множителей Лагранжа является классическим методом решения задач математического программирования (в частности выпуклого). К сожалению, при практическом применении метода могут встретиться значительные вычислительные трудности, сужающие область его использования. Мы рассматриваем здесь метод Лагранжа главным образом потому, что он является аппаратом, активно используемым для обоснования различных современных численных методов, широко применяемых на практике. Что же касается функции Лагранжа и множителей Лагранжа, то они играют самостоятельную и исключительно важную роль в теории и приложениях не только математического программирования.
Рассмотрим классическую задачу оптимизации:
Среди ограничений этой задачи нет неравенств, нет условий неотрицательности переменных, их дискретности, и функции и непрерывны и имеют частные производные по крайней мере второго порядка.
Классический подход к решению задачи дает систему уравнений (необходимые условия), которым должна удовлетворять точка , доставляющая функции локальный экстремум на множестве точек, удовлетворяющих ограничениям (для задачи выпуклого программирования найденная точка будет одновременно и точкой глобального экстремума).
Предположим, что в точке функция (1) имеет локальный условный экстремум и ранг матрицы равен . Тогда необходимые условия запишутся в виде:
есть функция Лагранжа; – множители Лагранжа.
Существуют также и достаточные условия, при выполнении которых решение системы уравнений (3) определяет точку экстремума функции . Этот вопрос решается на основании исследования знака второго дифференциала функции Лагранжа. Однако достаточные условия представляют главным образом теоретический интерес.
Можно указать следующий порядок решения задачи (1), (2) методом множителей Лагранжа:
1) составить функцию Лагранжа (4);
2) найти частные производные функции Лагранжа по всем переменным и приравнять их
нулю. Тем самым будет получена система (3, состоящая из уравнений. Решить полученную систему (если это окажется возможным!) и найти таким образом все стационарные точки функции Лагранжа;
3) из стационарных точек, взятых без координат выбрать точки, в которых функция имеет условные локальные экстремумы при наличии ограничений (2). Этот выбор осуществляется, например, с применением достаточных условий локального экстремума. Часто исследование упрощается, если использовать конкретные условия задачи.
Пример решения задачи
Условие задачи
Фирма производит товар двух видов в количествах и . Функция полезных издержек определена соотношением . Цены этих товаров на рынке равны и соответственно.
Определить, при каких объемах выпуска достигается максимальная прибыль и чему она равна, если полные издержки не превосходят
Испытываете сложности с пониманием хода решения? На сайте действует услуга Решение задач по методам оптимальных решений на заказ
Решение задачи
Экономико-математическая модель задачи
Функция прибыли:
Ограничения на издержки:
Получаем следующую экономико-математическую модель:
Кроме того, по смыслу задачи
Метод множителей Лагранжа
Составим функцию Лагранжа:
Находим частные производные 1-го порядка:
Составим и решим систему уравнений:
Так как , то
Максимальная прибыль:
Ответ
Таким
образом необходимо выпускать
ед. товара 1-го вида и
ед. товара 2-го вида. При этом прибыль будет
максимальной и составит 270.
Приведен образец решения задачи квадратичного выпуклого программирования графическим методом.
Решение линейной задачи графическим методом
Рассмотрен графический метод решения задачи линейного программирования (ЗЛП) с двумя переменными. На примере задачи приведено подробное описание построения чертежа и нахождения решения.
Модель управления запасами Уилсона
На примере решения задачи рассмотрена основная модель управления запасами (модель Уилсона). Вычислены такие показатели модели как оптимальный размер партии заказа, годовые затраты на хранение, интервал между поставками и точка размещения заказа.
Матрица коэффициентов прямых затрат и матрица "Затраты-выпуск"
На примере решения задачи рассмотрена межотраслевая модель Леонтьева. Показано вычисление матрицы коэффициентов прямых материальных затрат, матрицы «затраты-выпуск», матрицы коэффициентов косвенных затрат, векторов конечного потребления и валового выпуска.
Сегодня на уроке мы научимся находить условные или, как их ещё называют, относительные экстремумы функций нескольких переменных, и, прежде всего, речь пойдёт, конечно же, об условных экстремумах функций двух итрёх переменных , которые встречаются в подавляющем большинстве тематических задач.
Что нужно знать и уметь на данный момент? Несмотря на то, что эта статья находится «на окраине» темы, для успешного усвоения материала потребуется не так уж и много. На данный момент вы должны ориентироваться в основных поверхностях пространства , уметь находить частные производные (хотя бы на среднем уровне) и, как подсказывает беспощадная логика, разбираться в безусловных экстремумах . Но даже если у вас низкий уровень подготовки, не спешите уходить – все недостающие знания/навыки реально «подобрать по пути», причём безо всяких многочасовых мучений.
Сначала проанализируем само понятие и заодно осуществим экспресс-повторение наиболее распространённых поверхностей . Итак, что же такое условный экстремум? …Логика здесь не менее беспощадна =) Условный экстремум функции – это экстремум в обычном понимании этого слова, который достигается при выполнении определённого условия (или условий).
Представьте произвольную «косую» плоскость в декартовой системе . Никакого экстремума здесь нет и в помине. Но это до поры до времени. Рассмотрим эллиптический цилиндр , для простоты – бесконечную круглую «трубу», параллельную оси . Очевидно, что эта «труба» «высечет» из нашей плоскости эллипс , в результате чего в верхней его точке будет максимум, а в нижней – минимум. Иными словами, функция, задающая плоскость, достигает экстремумов при условии , что её пересёк данный круговой цилиндр. Именно «при условии»! Другой эллиптический цилиндр, пересекающий эту плоскость, почти наверняка породит иные значения минимума и максимума.
Если не очень понятно, то ситуацию можно смоделировать реально (правда, в обратном порядке) : возьмите топор, выйдите на улицу и срубите… нет, Гринпис потом не простит – лучше порежем «болгаркой» водосточную трубу =). Условный минимум и условный максимум будут зависеть от того, на какой высоте и под каким (негоризонтальным) углом осуществлён разрез.
Настало время облачить выкладки в математическое одеяние. Рассмотрим эллиптический параболоид , который имеет безусловный минимум в точке . Теперь найдём экстремум при условии . Данная плоскость параллельна оси , а значит, «высекает» из параболоида параболу . Вершина этой параболы и будет условным минимумом. Причём плоскость не проходит через начало координат, следовательно, точка останется не при делах. Не представили картинку? Срочно идём по ссылкам! Потребуется ещё много-много раз.
Вопрос: как найти этот условный экстремум? Простейший способ решения состоит в том, чтобы из уравнения (которое так и называют – условием
или уравнением связи
) выразить, например: – и подставить его в функцию:
В результате получена функция одной переменной, задающая параболу, вершина которой «вычисляется» с закрытыми глазами. Найдём критические точки
:
– критическая точка.
Далее проще всего использовать второе достаточное условие экстремума
:
В частности: , значит, функция достигает минимума в точке . Его можно вычислить напрямую: , но мы пойдём более академичным путём. Найдём «игрековую» координату:
,
запишем точку условного минимума , удостоверимся, что она действительно лежит в плоскости (удовлетворяет уравнению связи)
:
и вычислим условный минимум функции :
при условии
(«добавка» обязательна!!!)
.
Рассмотренный способ без тени сомнения можно использовать на практике, однако, он обладает рядом недостатков. Во-первых, далеко не всегда понятна геометрия задачи, а во-вторых, зачастую бывает невыгодно выражать «икс» либо «игрек» из уравнения связи (если вообще есть возможность что-то выразить) . И сейчас мы рассмотрим универсальный метод нахождения условных экстремумов, получивший название метод множителей Лагранжа :
Пример 1
Найти условные экстремумы функции при указанном уравнении связи на аргументы .
Узнаёте поверхности? ;-) …Я рад видеть ваши счастливые лица =)
Кстати из формулировки данной задачи становится ясно, почему условие называют уравнением связи – аргументы функции связаны дополнительным условием, то есть найденные точки экстремума должны обязательно принадлежать круговому цилиндру.
Решение
: на первом шаге нужно представить уравнение связи в виде и составить функцию Лагранжа
:
, где – так называемый множитель Лагранжа.
В нашем случае и:
Алгоритм нахождения условных экстремумов весьма похож на схему отыскания «обычных» экстремумов
. Найдём частные производные
функции Лагранжа, при этом с «лямбдой» следует обращаться, как с константой:
Составим и решим следующую систему:
Клубок распутывается стандартно:
из первого уравнения выразим 
;
из второго уравнения выразим 
.
Подставим в уравнение связи и проведём упрощения:
В результате получаем две стационарные точки. Если , то:
если , то:
Легко видеть, что координаты обеих точек удовлетворяют уравнению 
. Щепетильные люди могут выполнить и полную проверку: для этого нужно подставить 
в первое и второе уравнения системы, и затем сделать то же самое с набором 
. Всё должно «сойтись».
Проверим выполнение достаточного условия экстремума для найденных стационарных точек. Я разберу три подхода к решению данного вопроса:
1) Первый способ – это геометрическое обоснование.
Вычислим значения функции в стационарных точках:
Далее записываем фразу примерно такого содержания: сечение плоскости круговым цилиндром представляет собой эллипс, в верхней вершине которого достигается максимум, а в нижней – минимум. Таким образом, бОльшее значение – есть условный максимум, а меньшее – условный минимум.
По возможности лучше применять именно этот метод – он прост, и такое решение засчитывают преподаватели (большим плюсом идёт то, что вы показали понимание геометрического смысла задачи) . Однако, как уже отмечалось, далеко не всегда понятно, что с чем и где пересекается, и тогда на помощь приходит аналитическая проверка:
2) Второй способ основан на использовании знаков дифференциала второго порядка . Если окажется, что в стационарной точке , то функция достигает там максимума, если же – то минимума.
Найдём частные производные второго порядка
:
и составим этот дифференциал:
При , значит, функция достигает максимума в точке ;
при , значит, функция достигает минимума в точке 
.
Рассмотренный метод очень хорош, но обладает тем недостатком, что в ряде случаев практически невозможно определить знак 2-го дифференциала (обычно так бывает, если и/или – разных знаков) . И тогда на помощь приходит «тяжёлая артиллерия»:
3) Продифференцируем по «икс» и по «игрек» уравнение связи:
и составим следующую симметричную
матрицу
:
Если в стационарной точке , то функция достигает там (внимание! ) минимума, если – то максимума.
Запишем матрицу для значения и соответствующей точки :
Вычислим её определитель
:
, таким образом, функция имеет максимум в точке .
Аналогично для значения и точки :
Таким образом, функция имеет минимум в точке .
Ответ
: при условии :
После обстоятельного разбора материала просто не могу не предложить вам пару типовых задач для самопроверки:
Пример 2
Найти условный экстремум функции , если её аргументы связаны уравнением
Пример 3
Найти экстремумы функции при условии
И вновь настоятельно рекомендую разобраться в геометрической сути заданий, особенно, это касается последнего примера, где аналитическая проверка достаточного условия – не подарок. Вспомните, какую линию 2-го порядка задаёт уравнение , и какую поверхность эта линия порождает в пространстве. Проанализируйте, по какой кривой цилиндр пересечёт плоскость и где на этой кривой будет минимум, а где – максимум.
Решения и ответы в конце урока.
Рассматриваемая задача находит широкое применение в различных областях, в частности – далеко ходить не будем, в геометрии. Решим всем понравившуюся задачу о поллитровке (см. Пример 7 статьи Экстремальные задачи ) вторым способом:
Пример 4
Каковы должны быть размеры консервной банки цилиндрической формы, чтобы на изготовления банки пошло наименьшее количество материала, если объем банки равен
Решение
: рассмотрим переменный радиус основания , переменную высоту и составим функцию площади полной поверхности банки:
(площадь двух крышек + площадь боковой поверхности)
|
Метод Лагранжа ─ это метод решения задачи условной оптимизации, при котором ограничения, записываемые как неявные функции, объединяются с целевой функцией в форме нового уравнения, называемого лагранжианом .
Рассмотрим частный случай общей задачи нелинейного программирования:
Дана система нелинейных уравнений (1):
(1) gi(x1,x2,…,xn)=bi (i=1..m),
Найти наименьшее (или наибольшее) значение функции (2)
(2) f (х1,х2,…,хn),
если отсутствуют условия неотрицательности переменных и f(х1,х2,…,хn) и gi(x1,x2,…,xn) ─ функции, непрерывные вместе со своими частными производными.
Чтобы найти решение этой задачи, можно применить следующий метод: 1. Вводят набор переменных λ1, λ2,…, λm, называемых множителями Лагранжа, составляют функцию Лагранжа (3)
(3) F(х1,х2,…,хn , λ1,λ2,…,λm) = f(х1,х2,…,хn)+ λi .
2. Находят частные производные от функции Лагранжа по переменным xi и λi и приравнивают их нулю.
3. Решая систему уравнений, находят точки, в которых целевая функция задачи может иметь экстремум.
4.Среди точек, подозрительных не экстремум, находят такие, в которыхдостигается экстремум, и вычисляют значения функции в этих точках.
4. Сравнить полученные значения функции f и выбрать наилучшее.
По плану производства продукции предприятию необходимо изготовить 180 изделий. Эти изделия могут быть изготовлены двумя технологическими способами. При производстве х1 изделия I способом затраты равны 4*х1+х1^2 руб., а при изготовлении х2 изделий II способом они составляют 8*х2+х2^2 руб. Определить, сколько изделий каждым из способов следует изготовить, так чтобы общие затраты на производство продукции были минимальными.
Решение: Математическая постановка задачи состоит в определении наименьшего значения функции двух переменных:
f = 4*x1+x1^2 +8*x2 +x2^2, при условии x1 +x2 = 180.
Составим функцию Лагранжа:
F(x1,x2,λ) = 4*x1+x1^2+8*x2+x2^2+λ*(180-x1-x2).
Вычислим ее частные производные по х1,х2, λ и приравняем их к 0:
Перенесем в правые части первых двух уравнений λ и приравняем их левые части, получим 4 + 2*x1 = 8 + 2*x2, или x1 − x2 = 2.
Решая последнее уравнение совместно с уравнением x1 + x2 = 180, находим x1 = 91, x2 = 89, то есть получили решение, удовлетворяющее условиям:
Найдем значение целевой функции f при этих значениях переменных:
F(x1, x2) = 17278
Эта точка является подозрительной на экстремум. Используя вторые частные производные, можно показать, что в точке (91,89) функция f имеет минимум.
Метод множителей Лагранжа (в англ. литературе «LaGrange"s method of undetermined multipliers») ˗ это численный метод решения оптимизационных задач, который позволяет определить «условный» экстремум целевой функции (минимальное или максимальное значение)
при наличии заданных ограничений на ее переменные в виде равенств (т.е. определена область допустимых значений)
˗ это значения аргумента функции (управляемые параметры) на вещественной области при котором значение функции стремится к экстремуму. Применение названия «условный» экстремум связано с тем, что на переменные наложено дополнительное условие, которое ограничивает область допустимых значений при поиске экстремума функции.
Метод множителей Лагранжа позволяет задачу поиска условного экстремума целевой функции на множестве допустимых значений преобразовать к задаче безусловной оптимизации функции.
В случае если функции 
и 
непрерывны вместе со своими частными производными, то существуют такие переменные λ не равные одновременно нулю, при которых выполняется следующее условие:
Таким образом, в соответствии с методом множителей Лагранжа для поиска экстремума целевой функции на множестве допустимых значений составляю функцию Лагранжа L(х, λ), которую в дальнейшем оптимизируют:
где λ ˗ вектор дополнительных переменных, называемых неопределенными множителями Лагранжа.
Таким образом, задача нахождения условного экстремума функции f(x) свелась к задаче поиска безусловного экстремума функции L(x, λ).
и 
Необходимое условие экстремума функции Лагранжа задается системой уравнений (система состоит из «n + m» уравнений):
Решение данной системы уравнений позволяет определить аргументы функции (Х), при которых значение функции L(x, λ), а также значение целевой функции f(x) соответствуют экстремуму.
Величина множителей Лагранжа (λ) имеет практический интерес в случае, если ограничения представлены в форме со свободным членом уравнения (константой). В этом случае можно рассматривать дальнейшее (увеличение/уменьшение) значения целевой функции за счет изменения значения константы в системе уравнения . Таким образом, множитель Лагранжа характеризует скорость изменения максимума целевой функции при изменении ограничивающей константы.
Существует несколько способов определения характера экстремума полученной функции:
Первый способ: Пусть – координаты точки экстремума, а - соответствующее значение целевой функции. Берется точка , близкая к точке , и вычисляется значение целевой функции :
Если 
, то в точке имеет место максимум.
Если 
, то в точке имеет место минимум.
Второй способ: Достаточным условием, из которого можно выяснить характер экстремума, является знак второго дифференциала функции Лагранжа. Второй дифференциал функции Лагранжа определяется следующим образом:
Если в заданной точке 
минимум
, если же 
, то целевая функция f(x) имеет в данной точке условный максимум.
Третий способ: Также характер экстремума функции можно выяснить рассмотрев гессиан функции Лагранжа. Матрица Гессе представляет собой симметричную квадратную матрицу вторых частных производных функции в точке , в которой элементы матрицы симметричны относительно главной диагонали.
Для определения типа экстремума (максимум или минимум функции) можно воспользоваться правилом Сильвестра:
1. Для того, чтобы второй дифференциал функции Лагранжа был знакоположителен 
необходимо, чтобы угловые миноры функции были положительными . При таких условиях функция в этой точке имеет минимум.
2. Для того, чтобы второй дифференциал функции Лагранжа был знакоотрицателен 
, необходимо, чтобы угловые миноры функции чередовались, причем первый элемент матрицы должен быть отрицательнsv . При таких условиях функция в этой точке имеет максимум.
Под угловым минором понимаем минор, расположенный в первых k строках и k столбцах исходной матрицы.
Основное практическое значение метода Лагранжа заключается в том, что он позволяет перейти от условной оптимизации к безусловной и, соответственно, расширить арсенал доступных методов решения задачи. Однако задача решения системы уравнений, к которой сводится данный метод, в общем случае не проще исходной задачи поиска экстремума. Такие методы называются непрямыми. Их применение объясняется необходимостью получить решение экстремальной задачи в аналитической форме (допустим, для тех или иных теоретических выкладок). При решении конкретных практических задач обычно используются прямые методы, основанные на итеративных процессах вычисления и сравнения значений оптимизируемых функций.
Методика расчета
1 шаг : Определяем функцию Лагранжа из заданной целевой функции и системы ограничений:
Вперёд
Для того, чтобы добавить Ваш комментарий к статье, пожалуйста, зарегистрируйтесь на сайте.
Метод Множителей Лагранжа является классическим методом решения задач математического программирования (в частности выпуклого). К сожалению, при практическом применении метода могут встретиться значительные вычислительные трудности, сужающие область его использования. Мы рассматриваем здесь метод Лагранжа главным образом потому, что он является аппаратом, активно используемым для обоснования различных современных численных методов, широко применяемых на практике. Что же касается функции Лагранжа и множителей Лагранжа, то они играют самостоятельную и исключительно важную роль в теории и приложениях не только математического программирования.
Рассмотрим классическую задачу оптимизации
max (min) z=f(x) (7.20)
Эта задача выделяется из задачи (7.18), (7.19) тем, что среди ограничений (7.21) нет неравенств, нет условий неотрицательности переменных, их дискретности, и функции f(x) и непрерывны и имеют частные производные по крайней мере второго порядка.
Классический подход к решению задачи (7.20), (7.21) дает систему уравнений (необходимые условия), которым должна удовлетворять точка х*,доставляющая функции f(x)локальный экстремум на множестве точек, удовлетворяющих ограничениям (7.21) (для задачи выпуклого программирования найденная точка х*в соответствии с теоремой 7.6 будет одновременно и точкой глобального экстремума).
Предположим, что в точке х* функция (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 . Найти оптимальное распределение ограниченного ресурса в a ед. между n потребителями, если прибыль, получаемая при выделении j-му потребителю x j единиц ресурса, вычисляется по формуле .
Решение. Математическая модель задачи имеет следующий вид:
Составляем функцию Лагранжа:
.
Находим частные производные функции Лагранжа и приравниваем их нулю:
Решая эту систему уравнений, получаем:
Таким образом, если j-му потребителю будет выделено ед. ресурса, то суммарная прибыль достигнет максимальной величины и составит ден. ед.
Мы рассмотрелиметод Лагранжа применительно к классической задаче оптимизации. Можно обобщить этот метод на случай, когда переменные неотрицательны и некоторые ограничения заданы в форме неравенств. Однако это обобщение имеет преимущественно теоретическое значение и не приводит к конкретным вычислительным алгоритмам.
В заключение дадим множителям Лагранжа экономическую интерпретацию. Для этого обратимся к простейшей классической задаче оптимизации
max (min) z =f (x 1 , х 2); (7.24)
𝜑(x 1 , х 2)=b. (7.25)
Предположим, что условный экстремум достигается в точке . Соответствующее экстремальное значение функции f (x )
Допустим, что в ограничениях (7.25) величина b
может меняться, тогда координаты точки экстремума, а следовательно, и экстремальное значение f*
функции f
(x
) станут величинами, зависящими от b
, т. е. 
,
, а поэтому производная функции (7.24)
