Метод неопределенных множителей лагранжа pdf. Метод неопределенных множителей лагранжа

Применяется для решения задач с аналитическим выражением для критерия оптимальности и при наличии ограничений на независимые переменные типа равенств. Для получения аналитического решения требуется, чтобы ограничения имели аналитический вид. Применение неопределенных множителей Лагранжа позволяет свести задачу оптимизации с ограничениями к задаче, решаемой методами исследования функций классического анализа. В этом случае порядок системы уравнений, решаемой для нахождения экстремума критерия оптимизации, повышается на число ограничений. Применение метода эффективно при количестве переменных три и менее. Метод используется и при количестве переменных более трех, если процесс описывается конечными уравнениями.

Пусть требуется найти экстремум функции, которая зависит от n переменных, связанных в свою очередь отношениями. Достигаемый функцией экстремум с учетом выполнения условий называется относительным, или условным. Если же число переменных равно числу соотношений (), то искомые неизвестные находятся решением системы уравнений, описываемых соотношениями. Решение задачи оптимизации сводится к проверке найденным таким способом значений переменных на функции. Таким образом, экстремальную задачу можно решить простым перебором переменных, удовлетворяющих условиям.

Если m < n , то можно из уравнений связи найти зависимость m переменных от n - m остальных переменных, т.е.

Функцию можно получить подстановкой полученных переменных в функцию. Тогда будет зависеть только от переменных, не связанных дополнительными условиями. Следовательно, снимая ограничения удается и уменьшить размерность исходной задачи оптимизации. Часто аналитически таким способом задачу решить не удается. Поэтому для решения задач отыскания экстремума функции многих переменных обычно используется метод неопределенных множителей Лагранжа.

При введении новых переменных, носящих название неопределенных множителей Лагранжа появляется возможность ввести новую функцию

т.е. функцию m + n переменных, в которую ограничения, накладываемые системой функций входят как составная часть.

Экстремальное значение функции совпадает с экстремальным значением функции, если выполняется условие по ограничениям. Необходимым условием экстремума функции многих переменных является равенство нулю дифференциала этой функции в экстремальной точке, т.е.

Для того, чтобы это выражение выполнялось при любых значениях независимых дифференциалов, необходимо равенство нулю коэффициентов при этих дифференциалах, что дает систему уравнений

При этом новых независимых определяются из условия

Объединение систем (4.3.1) и (4.3.2) можно получить

Таким образом, задача в форме (4.3.3) сводится к задаче: найти

Отдельно следует отметить, что в общем случае метод множителей Лагранжа позволяет найти лишь необходимые условия существования условного экстремума для непрерывных функций, имеющих непрерывные производные. Однако из физического смысла решаемой задачи обычно известно, идет ли речь о максимуме или минимуме функции, кроме того, как правило, в проектных задачах функция на рассматриваемом отрезке является унимодальной. Поэтому в проектных задачах нет необходимости значения переменных, найденные при решении рассмотренных систем уравнений, проверять на экстремум с помощью анализа производных более высокого порядка.

Теорема 1. Пусть точка является точкой условного экстремума функции при выполнении уравнений связи (3). Тогда существуют такие числа, что в точке выполняются условия

Следствие. Положим

где - числа, указанные в теореме. Функция (8) называется функцией Лагранжа. Если точка является точкой условного экстремума для функции, то она является стационарной точкой для функции Лагранжа, т.е. в этой точке

Доказательство теоремы. Пусть - точка условного экстремума для функции и пусть в этой точке для определенности выполняется условие (4). Тогда точка является точкой обычного экстремума для функции, поэтому в точке

откуда, пользуясь инвариантностью формы первого дифференциала, для точки имеем

Подставляя (5) в (3) и дифференцируя получившееся тождество в некоторой окрестности точки, а значит, и в самой точке, получим

В формуле (11), также как и в формуле (10), дифференциалы есть дифференциалы независимых переменных, а дифференциалы есть дифференциалы функций.

Каковы бы не были числа, умножая равенство (11) в точке для функции на, и складывая их между собой и с равенством (10), получим

Выбрав так, чтобы в точке выполнялись равенства

Это всегда возможно, так как (13) является системой линейных относительно уравнений с определителем

не равным нулю.

При таком выборе имеем

Здесь уже все дифференциалы есть дифференциалы независимых переменных и, значит, сами являются независимыми переменными, которые могут принимать любые значения. Беря, а все остальные дифференциалы, входящие в формулу (14), равными нулю, получим

Тем самым мы доказали существование таких, что выполняются условия (13) и (15), т.е. условия (7).

Теорема доказана.

Алгоритм нахождения экстремума функции методом множителей Лагранжа

Пусть требуется найти экстремум функции n переменных f(x 1 ,x 2 ,…,x n) при условии, что переменные x 1 ,x 2 ,…,x n связаны соотношениями (ограничениями)

среди которых количество m ограничений-равенств меньше числа n переменных, а количество и r ограничений-неравенств может быть произвольным.

Для нахождения значений {x 1 ,x 2 ,…,x n }=Х, необходимо доставляющих экстремумы функции f(X), можно воспользоваться методом неопределенных множителей Лагранжа:

• 1. Ограничения-неравенства g(X)0 приводятся к виду (Х)0, где (Х) = - g(X).
• 2. Полученные ограничения-неравенства

в свою очередь приводятся к ограничениям-равенствам путем введения +r дополнительных переменных

В результате задача поиска условного экстремума примет канонический вид:

в котором соотношение m++r < n++r указывает на возможность получения множества допустимых решений, а значит, и нахождения среди них тех, которые доставляют экстремум f(X).

3. Составляется функция Лагранжа:

Ф(x 1 ,…,x n , 1 ,…, m++r) = f(x 1 ,x 2 ,…,x n)+ 1 q 1 + 2 q 2 +…+ m++r q m++r,

в которой дополнительные переменные { 1 ,…, m++r }= называются неопределенными множителями Лагранжа.

Для составленной функции Лагранжа можно ставить задачу нахождения безусловного экстремума

результат решения которой будет совпадать с искомым решением исходной задачи нахождения условного экстремума.

4. Для функции Ф(Х,) составляются необходимые условия существования экстремума:

5. Полученную систему уравнений Ф(Х,)=0 решают, и в результате решения находят значения

удовлетворяющие необходимым условиям существования экстремума.

6. Для решения вопроса о том, существует ли в найденных точках максимумы или минимумы следует воспользоваться достаточными условиями существования экстремумов, которые для гладких функций Ф() формулируются следующим образом:

если в некоторой точке матрица вторых производных положительно определена, то в анализируемой точке лежит минимум функции f(Х);

Краткая теория

Метод множителей Лагранжа является классическим методом решения задач математического программирования (в частности выпуклого). К сожалению, при практическом применении метода могут встретиться значительные вычислительные трудности, сужающие область его использования. Мы рассматриваем здесь метод Лагранжа главным образом потому, что он является аппаратом, активно используемым для обоснования различных современных численных методов, широко применяемых на практике. Что же касается функции Лагранжа и множителей Лагранжа, то они играют самостоятельную и исключительно важную роль в теории и приложениях не только математического программирования.

Рассмотрим классическую задачу оптимизации:

Среди ограничений этой задачи нет неравенств, нет условий неотрицательности переменных, их дискретности, и функции и непрерывны и имеют частные производные по крайней мере второго порядка.

Классический подход к решению задачи дает систему уравнений (необходимые условия), которым должна удовлетворять точка , доставляющая функции локальный экстремум на множестве точек, удовлетворяющих ограничениям (для задачи выпуклого программирования найденная точка будет одновременно и точкой глобального экстремума).

Предположим, что в точке функция (1) имеет локальный условный экстремум и ранг матрицы равен . Тогда необходимые условия запишутся в виде:

есть функция Лагранжа; – множители Лагранжа.

Существуют также и достаточные условия, при выполнении которых решение системы уравнений (3) определяет точку экстремума функции . Этот вопрос решается на основании исследования знака второго дифференциала функции Лагранжа. Однако достаточные условия представляют главным образом теоретический интерес.

Можно указать следующий порядок решения задачи (1), (2) методом множителей Лагранжа:

1) составить функцию Лагранжа (4);

2) найти частные производные функции Лагранжа по всем переменным и приравнять их

нулю. Тем самым будет получена система (3, состоящая из уравнений. Решить полученную систему (если это окажется возможным!) и найти таким образом все стационарные точки функции Лагранжа;

3) из стационарных точек, взятых без координат выбрать точки, в которых функция имеет условные локальные экстремумы при наличии ограничений (2). Этот выбор осуществляется, например, с применением достаточных условий локального экстремума. Часто исследование упрощается, если использовать конкретные условия задачи.

Пример решения задачи

Условие задачи

Фирма производит товар двух видов в количествах и . Функция полезных издержек определена соотношением . Цены этих товаров на рынке равны и соответственно.

Определить, при каких объемах выпуска достигается максимальная прибыль и чему она равна, если полные издержки не превосходят

Испытываете сложности с пониманием хода решения? На сайте действует услуга Решение задач по методам оптимальных решений на заказ

Решение задачи

Экономико-математическая модель задачи

Функция прибыли:

Ограничения на издержки:

Получаем следующую экономико-математическую модель:

Кроме того, по смыслу задачи

Метод множителей Лагранжа

Составим функцию Лагранжа:

Находим частные производные 1-го порядка:

Составим и решим систему уравнений:

Так как , то

Максимальная прибыль:

Ответ

Таким образом необходимо выпускать ед. товара 1-го вида и ед. товара 2-го вида. При этом прибыль будет максимальной и составит 270.
Приведен образец решения задачи квадратичного выпуклого программирования графическим методом.

Решение линейной задачи графическим методом
Рассмотрен графический метод решения задачи линейного программирования (ЗЛП) с двумя переменными. На примере задачи приведено подробное описание построения чертежа и нахождения решения.

Модель управления запасами Уилсона
На примере решения задачи рассмотрена основная модель управления запасами (модель Уилсона). Вычислены такие показатели модели как оптимальный размер партии заказа, годовые затраты на хранение, интервал между поставками и точка размещения заказа.

Матрица коэффициентов прямых затрат и матрица "Затраты-выпуск"
На примере решения задачи рассмотрена межотраслевая модель Леонтьева. Показано вычисление матрицы коэффициентов прямых материальных затрат, матрицы «затраты-выпуск», матрицы коэффициентов косвенных затрат, векторов конечного потребления и валового выпуска.

Метод Лагранжа ─ это метод решения задачи условной оптимизации, при котором ограничения, записываемые как неявные функции, объединяются с целевой функцией в форме нового уравнения, называемого лагранжианом .

Рассмотрим частный случай общей задачи нелинейного программирования:

Дана система нелинейных уравнений (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 имеет минимум.

Рассмотрим задачу условной оптимизации, содержащую только ограничения в виде равенств

min

при наличии ограничений

,
.

Эта задача в принципе может быть решена как задача безусловной оптимизации, полученная путем исключения из целевой функции m независимых переменных с помощью заданных равенств. Наличие ограничений в виде равенств фактически позволяет уменьшить размерность исходной задачи. Новая задача может быть решена с помощью подходящего метода безусловной оптимизации.

Пример . Требуется минимизировать функцию

при ограничении

Исключив переменную с помощью уравнения, получим оптимизационную задачу с двумя переменными без ограничений:

минимизировать ,

которую можно решить одним из методов безусловной оптимизации.

Однако метод исключения переменных применим лишь в тех случаях, когда уравнения, представляющие ограничения, можно разрешить относительно некоторого набора переменных. При наличии большого числа ограничений в виде равенств процесс исключения переменных становится весьма трудоемкой процедурой. Кроме того, возможны ситуации, когда уравнение не удается разрешить относительно переменной. В этом случае целесообразно использовать метод множителей Лагранжа.

С помощью метода множителей Лагранжа по существу устанавливаются необходимые условия, позволяющие идентифицировать точки оптимума в задачах оптимизации с ограничениями в виде равенств.

Рассмотрим задачу

min

при наличии ограничений

,
.

Из курса математического анализа хорошо известно, что точка условного минимума функции совпадает с седловой точкой функции Лагранжа:

,

при этом седловая точка должна обеспечивать минимум по переменным и максимум по параметрам. Эти параметры называются множителями Лагранжа. Приравнивая частные производные функциипои пок нулю, получим необходимые условия стационарной точки:

,
,

,
.

Решение системы
уравнений определяет стационарную точку функции Лагранжа. Достаточные условия существования минимума исходной задачи содержат, кроме выше упомянутых, положительную определенность матрицы Гессе целевой функции.

4.2. Условия куна - таккера

Рассмотрим задачу нелинейного программирования с ограничениями в виде неравенств

min

при ограничениях

,
.

Сведем ограничения в виде неравенств к ограничениям-равенствам добавлением к каждому из них ослабляющих переменных ,
:

.

Сформируем функцию Лагранжа:

Тогда необходимые условия минимума принимают вид

,
;

,
;

,
.

Можно умножить последнее уравнение на и заменить ослабляющие переменные, выразив их из второго уравнения. Второе уравнение можно преобразовать, отбросив ослабляющие переменные и переходя к ограничениям-неравенствам. Следует добавить еще одно условие
, которое должно выполняться в точке условного минимума.

Окончательно получаем необходимые условия существования минимума задачи нелинейного программирования с ограничениями неравенствами, которые называются условиями Куна- Таккера:

,
; (1)

,
; (2)

,
; (3)

,
. (4)

Ограничение в виде неравенства
называется активным в точке, если оно превращается в равенство
, и называется неактивным, если
. Если существует возможность обнаружить до непосредственного решения задачи ограничения, которые неактивны в точке оптимума, то эти ограничения можно исключить из модели и тем самым уменьшить ее размеры.

Уравнение (3) означает, что либо
, либо
. Если
, то
и ограничение является активным и представляет собой ограничение равенство. С другой стороны, если ограничение является строгим неравенством
, то множитель Лагранжа будет иметь вид
т.е. ограничение
является неактивным и им можно пренебречь. Конечно, предварительно не известно какими ограничениями можно пренебречь.