Используя метод множителей лагранжа найти экстремумы функции. Условные экстремумы и метод множителей лагранжа

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

(5.2)

где
– известные функции,

а
– заданные коэффициенты.

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

Преобразуем условия (5.2) таким образом, чтобы в левых или правых частях равенств стоял ноль :

(5.3)

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

Точки экстремума функции (5.4) являются точками экстремума исходной задачи и наоборот: оптимальный план задачи (5.1)-(5.2) является точкой глобального экстремума функции Лагранжа.

Действительно, пусть найдено решение
задачи (5.1)-(5.2), тогда выполняются условия (5.3). Подставим план
в функцию (5.4) и убедимся в справедливости равенства (5.5).

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

Определим частные производные функции (5.4)

,

.

После приравнивания нулю производных получим системуm+n уравнений сm+n неизвестными

,(5.6)

В общем случае система (5.6)-(5.7) будем иметь несколько решений, куда войдут все максимумы и минимумы функции Лагранжа. Для того чтобы выделить глобальный максимум или минимум, во всех найденных точках вычисляют значения целевой функции. Наибольшее из этих значений будет глобальным максимумом, а наименьшее – глобальным минимумом. В некоторых случаях оказывается возможным использование достаточных условий строгого экстремума непрерывных функций (см. ниже задачу 5.2):

пусть функция
непрерывна и дважды дифференцируема в некоторой окрестности своей стационарной точки(т.е.
)). Тогда:

а ) если
,
(5.8)

то – точка строгого максимума функции
;

б) если
,
(5.9)

то – точка строгого минимума функции
;

г ) если
,

то вопрос о наличии экстремума остается открытым.

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

Экономический смысл множителей Лагранжа. Оптимальное значение множителя
показывает на сколько изменится значение критерияZ при увеличении или уменьшении ресурсаj на одну единицу, так как

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

,

выполняют в несколько этапов:

1. Определяют стационарные точки целевой функции, для чего решают систему уравнений

.

2. Из стационарных точек отбирают те, координаты которых удовлетворяют условиям

3. Методом Лагранжа решают задачу с ограничениями-равенствами (5.1)-(5.2).

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

Задача 5.1 Решим методом Лагранжа задачу 1.3, рассмотренную в первом разделе. Оптимальное распределение водных ресурсов описывается математической моделью

.

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

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

,

Таким образом, получили систему линейных уравнений вида

Решение системы уравнений представляет собой оптимальный план распределения водных ресурсов по орошаемым участкам

, .

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

Максимальный дополнительный чистый доход от орошения составит

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

172391,02 (ден. ед.)

Задача 5.2 Решить задачу нелинейного программирования

Ограничение представим в виде:

.

Составим функцию Лагранжа и определим ее частные производные

.

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

.

Из первого уравнения следует

. (5.10)

Выражение подставим во второе уравнение

,

откуда следует два решения для :

и
. (5.11)

Подставив эти решения в третье уравнение, получим

,
.

Значения множителя Лагранжа и неизвестной вычислим по выражениям (5.10)-(5.11):

,
,
,
.

Таким образом, получили две точки экстремума:

;
.

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

,

. (5.12)

Для проверки условий строгого экстремума следует определить знак второй производной функции (5.11) в найденных нами экстремальных точках
и
.

,
;

.

Таким образом, (·)
является точкой минимума исходной задачи (
), а (·)
– точкой максимума.

Оптимальный план :

,
,
,

.

Способ определения условного экстремума начинается с построения вспомогательной функции Лагранжа, которая в области допустимых решений достигает максимума для тех же значений переменных 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) с помощью надстройки Поиск решения.

Рассмотрим линейное неоднородное дифференциальное уравнение первого порядка:
(1) .
Существует три способа решения этого уравнения:

  • метод вариации постоянной (Лагранжа).

Рассмотрим решение линейного дифференциального уравнения первого порядка методом Лагранжа.

Метод вариации постоянной (Лагранжа)

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

Рассмотрим уравнение:
(1)

Шаг 1 Решение однородного уравнения

Ищем решение однородного уравнения:

Это уравнение с разделяющимися переменными

Разделяем переменные - умножаем на dx , делим на y :

Интегрируем:

Интеграл по y - табличный :

Тогда

Потенцируем:

Заменим постоянную e C на C и уберем знак модуля, что сводится к умножению на постоянную ±1 , которую включим в C :

Шаг 2 Заменим постоянную C на функцию

Теперь заменим постоянную C на функцию от x :
C → u(x)
То есть, будем искать решение исходного уравнения (1) в виде:
(2)
Находим производную.

По правилу дифференцирования сложной функции:
.
По правилу дифференцирования произведения:

.
Подставляем в исходное уравнение (1) :
(1) ;

.
Два члена сокращаются:
;
.
Интегрируем:
.
Подставляем в (2) :
.
В результате получаем общее решение линейного дифференциального уравнения первого порядка:
.

Пример решения линейного дифференциального уравнения первого порядка методом Лагранжа

Решить уравнение

Решение

Решаем однородное уравнение:

Разделяем переменные:

Умножим на :

Интегрируем:

Интегралы табличные :

Потенцируем:

Заменим постоянную e C на C и убираем знаки модуля:

Отсюда:

Заменим постоянную C на функцию от x :
C → u(x)

Находим производную:
.
Подставляем в исходное уравнение:
;
;
Или:
;
.
Интегрируем:
;
Решение уравнения:
.

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

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

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)