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

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

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

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

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

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

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

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

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

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

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

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

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

При изложенном выше методе отыскания точек возможного условного экстремума мы нарушили симметрию в отношении переменных ут. Часть из этих переменных мы рассматривали как независимые, остальные - как функции этих переменных. В ряде случаев это приводит к усложнению выкладок. Лагранжем предложен метод, симметризирующий роль переменных. Изложению этого метода и посвящен настоящий пункт. Умножим равенства (13.47) соответственно на произвольные (и пока еще неопределенные) постоянные множители Полученные после умножения равенства сложим почленно с равенством (13.46). В результате получим следующее равенство:

где символом обозначена следующая функция:

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

сформулированные в предыдущем пункте, и что функция (13.40) дифференцируема, выберем множители так, чтобы выполнялись равенства

Это заведомо можно сделать, ибо равенства (13.52) приводят к линейной системе

определитель которой (якобиан отличен от нуля. В силу равенства (13.52) равенство (13.50) принимает вид

Поскольку при сделанных выше предположениях переменные являются независимыми, то из равенства (13.53) заключаем, что

Присоединяя к уравнениям (13.52) и (13.54) условия связи (13.41), мы получим систему уравнений

для определения координат точек возможного условного экстремума и множителей Хт. Практически при реализации этого метода поступают следующим образом. Составляют функцию Лагранжа (13.51) и для этой функции находят точки возможного безусловного экстремума. Для исключения множителей привлекают условия связи (13.41). Такой путь отыскания точек возможного условного экстремума является законным, ибо он приводит нас как раз к системе уравнений (13.55). Пример применения метода множителей Лагранжа будет рассмотрен в п. 4.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Так как , то

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

Ответ

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

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

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

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

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

min

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

,
.

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

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

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

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

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

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

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

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

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

min

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

,
.

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

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

,
,

,
.

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

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

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

min

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

,
.

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

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

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

,
;

,
.

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

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

,
; (1)

,
; (2)

,
; (3)

,
. (4)

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

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

Способ определения условного экстремума начинается с построения вспомогательной функции Лагранжа, которая в области допустимых решений достигает максимума для тех же значений переменных x 1 , x 2 , ..., x n , что и целевая функция z . Пусть решается задача определения условного экстремума функции z = f (X) при ограничениях φ i ( x 1 , x 2 , ..., x n ) = 0, i = 1, 2, ..., m , m < n

Составим функцию

которая называется функцией Лагранжа . X , - постоянные множители (множители Лагранжа ). Отметим, что множителям Лагранжа можно придать экономический смысл. Если f (x 1 , x 2 , ..., x n ) - доход, соответствующий плану X = (x 1 , x 2 , ..., x n ) , а функция φ i (x 1 , x 2 , ..., x n ) - издержки i-го ресурса, соответствующие этому плану, то X , - цена (оценка) i-го ресурса, характеризующая изменение экстремального значения целевой функции в зависимости от изменения размера i-го ресурса (маргинальная оценка). L(Х) - функция n + m переменных (x 1 , x 2 , ..., x n , λ 1 , λ 2 , ..., λ n ) . Определение стационарных точек этой функции приводит к решению системы уравнений

Легко заметить, что . Таким образом, задача нахождения условного экстремума функции z = f (X) сводится к нахождению локального экстремума функции L(X) . Если стационарная точка найдена, то вопрос о существовании экстремума в простейших случаях решается на основании достаточных условий экстремума - исследования знака второго дифференциала d 2 L(X) в стационарной точке при условии, что переменные приращения Δx i - связаны соотношениями

полученными путем дифференцирования уравнений связи.

Решение системы нелинейных уравнений с двумя неизвестными с помощью средства Поиск решения

Настройка Поиск решения позволяет находить решение системы нелинейных уравнений с двумя неизвестными:

где
- нелинейная функция от переменныхx и y ,
- произвольная постоянная.

Известно, что пара (x , y ) является решением системы уравнений (10) тогда и только тогда, когда она является решением следующего уравнение с двумя неизвестными:

С другой стороны, решение системы (10) - это точки пересечения двух кривых: f ] (x , y ) = C и f 2 (х, у) = С 2 на плоскости ХО Y .

Из этого следует метод нахождения корней системы. нелинейных уравнений:

Определить (хотя бы приближенно) интервал существования решения системы уравнений (10) или уравнения (11). Здесь необходимо учитывать вид уравнений, входящих в систему, область определения каждого их уравнений и т. п. Иногда применяется подбор начального приближения решения;

Протабулировать решение уравнения (11) по переменным x и y на выбранном интервале, либо построить графики функций f 1 (x , y ) = С, и f 2 (х,у) = С 2 (система(10)).

Локализовать предполагаемые корни системы уравнений - найти несколько минимальных значений из таблицы табулирование корней уравнения (11), либо определить точки пересечения кривых, входящих в систему (10).

4. Найти корни для системы уравнений (10) с помощью надстройки Поиск решения.