Уравнения Лагранжа

максимально:

и = и (х₀, х₁,..., х _n) → тах.

Если в задаче нет ограничений, то максимум
ищется на всей области определения функции и. Чаще
рассматривается задача с ограничением

g ₁(x) = 0, g₂(x) = 0,..., g_m(x) = 0

или, обозначив g = (g₁, g₂,..., g_m)^T,

g(x) = 0.

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

1⁰ . Выписать необходимое условие максимума

ди/дx_i = 0 для i = 0, 1,..., n.

2⁰. Найти стационарные точки функции и, решив
уравнения

ди/дх_i = 0, i = 0, 1,..., n.

3⁰. Перебрать все стационарные значения функции
и и найти среди них максимальное или показать, что
решения нет.

Если в задаче
есть ограничение,
то необходимо, что-
бы решение удовлетворяло условиюограничения.

Для геометрической иллюстрации удобнее рассмотреть функцию двух переменны-
х.В случае n переменных рас-смотрение и рас-суждения аналогичны. На рис. 5.2 изображена поверх-
ность, задаваемая целевой функцией двух переменных и
= и(х₁, х₂). Точка А соответствует максимальному зна-
чению функции при отсутствии ограничений. Проекция
точки А на плоскость (х₁,х₂) - точка А₁ - решение за-
дачи нахождения максимума без ограничений. Пусть
линия с_I — Рис. 5.2

график функции g(x)=0, задающей ограничение. Тогда необходимо искать максимальную точку не
на всей поверхности функции и, а только на той её части,
которая удовлетворяет ограничению. Это — линия с. Из
рисунка видно, что точка В соответствует максимально-
му значению функции и при условии g(x) = 0. Проекция
точки В — точка В ₁ — решение задачи нахождения мак-
симума при ограничении g(x) = 0.

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

Пусть функции и (х) = и(х₀, х₁,..., х_n) и g₁(х) =
g ₁ (x ₀, x₁,..., х_n),..., g_m(х) = g_m(x₀, х₁,..., х_n) непрерывны и
дифференцируемы. В соответствии с обозначениями

Требуется найти максимум функции и

при условии g(x) =0:

и = u(x_o, х₁,..., х_n) → тах, (5.5)

g(x_o, х₁,..., х_n) = 0.

Идея метода Лагранжа состоит в следующем:

из
рис. 5.2 видно, что в точке В₁, соответствующей точке В
- решению задачи нахождения максимума при ограни- чении g(x) = 0 — функция и не имеет максимума. Это
означает, что частные производные функции и по пере-
менным х₀, х₁..., х_n отличны от 0:

ди/дx_i
≠ 0
,

«Подправим» функцию и так, чтобы в точке В₁
принималось максимальное значение. Для этого добавим
к ней функции-ограничения, умноженные на неопреде-
лённые множители: зададим числа ( =( ₁,..., _m)) и
рассмотрим функцию

L(x, ) = u(х) — g(х). (5.6)

Здесь g(х) — скалярное произведение векторов
и g(х):

g(х) = ₁g₁(х) + ₂g₂(x)+ _mg_m(х)=

На рис. 5.3 плоскость
(х₁, х₂) изображена пря-мой g(x), функция L полу-чена по формуле (5.6) и имеет максимум в точке В.
Функция L диффе-ренцируема как разность двух дифференцируемых
функций. Поскольку она достигает максимума в точке
В, то

Рис. 5.3

i = 0, 1 ,..., n

или по формуле (5.6)

, i = 0, 1 ,..., n (5.7)

Добавив условия ограничения

g(x) = 0 (5.8)

к этим уравнениям, получим систему, из которой определяется решение.

Функция L (x, ) = L (x₀, x₁,..., х_n, ₁,..., _m) называется функцией Лагранжа, переменные — множителями Лагранжа, а уравнения

, i =0, 1, …, n

— уравнениями Лагранжа.

Сформулируем теорему:

решение задачи (5.5)
удовлетворяет условиям (5.7) и (5.8).

Приведённые выше соображения, разумеется, не являются доказательством. Рассмотрим доказательство этой теоремы:

Пусть задача имеет решение в точке х^* и функция ограничений удовлетворяет условию Якоби. Перенумеруем переменные так, чтобы в окрестности точки х разрешить систему ограничений g (x)=0 относительно последних т переменных. Это
можно сделать по теореме о неявной функции. Обозначим эти m
переменных вектором х⁽²⁾, а оставшиеся (n — т)переменных— х⁽¹⁾. Тогда ограничения можно записать в виде:

Х⁽²⁾ = h(х⁽¹⁾).

Здесь h — m-мерный вектор-столбец. Так задача оптимизации (5.5) cвелась к задаче оптимизации функции H(x⁽¹⁾)
при отсутствии ограничений:

H(x⁽¹⁾) = и (х⁽¹⁾, h(х^(1~)) → тах.

Необходимое условие существования максимума функции H(x⁽¹⁾) имеет вид:

5.9

Здесь — (и — т) -мерная вектор-строка, а — матрица размера m*(n — т). Условие g(x) = 0 равносильно условию g(x⁽¹⁾, h(x⁽¹⁾)) = 0. Дифференцируя
последнее, получим:

5.10

Матрица обратима, т.к. выполнено условие Якоби, и можно разрешить уравнение (5.10):

Подставим эту формулу в уравнение (5.9):

Кроме того,

(5.11)

Здесь второе слагаемое равно первому, умноженному на
единичную матрицу.

-m-мерная вектор-строка.

Обозначим -
её .

Тогда уравнения (5.9) и (5.11) можно записать в виде: .

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

Рассмотрим алгоритм решения задачи (5.5) нахождения максимума функции нескольких переменных при
наличии ограничения, методом Лагранжа.

1. Вводятся множители Лагранжа λ и определяется функция Лагранжа L(x, λ) = u(х) — λg (х) - и(х₀, х₁ ,...,х _n) - (х₀, х₁,..., х _n).

2. Выписывается система уравнений (5.8) и (5.7):

i= 0, 1, …., n

g (x)=0

3. Решается полученная система уравнений. Решения системы — стационарные
точки функции Лагранжа — при выполнении некоторых
достаточных условий являются решением задачи (5.5).

4. Среди стационарных точек отыскивается решение — точка х =(), в которой функция и
принимает максимальное значение, или доказывается,
что решения нет.

Если ограничение задаётся одной функцией
g₁ (х)=0, то рассматривается только один множитель
Лагранжа и функция Лагранжа имеет вид:

L (х, ) = u(х) — ₁ g ₁(x).

Рассмотрим в этом случае частную производную L по ₁

т.е. равенство = 0 – другая форма записи ограничения g ₁(х) = 0. -

Поэтому при т = 1уравнения Лагранжа записывают в виде:

=0, i= 0, 1, …, n; = 0 (5.8')