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

Приведенные выше условия оптимальности (теорема 5), лежат в основе метода множителей Лагранжа. который позволяет свести решение задачи (8) – (9) к решению задачи безусловной оптимизации ее функции Лагранжа. Для этого следует выполнить следующие действия.

1. Составить функцию Лагранжа по формуле (10).

2. Найти стационарные точки функции Лагранжа. Для этого нужно выписать частные производные по всем переменным xj и λi и приравнять их к нулю. Получается система n + m уравнений, представленная формулами (11) – (12). Все ее решения являются стационарными точками функции Лагранжа.

3. Любое решение (x*, λ*) системы (11) – (12) определяет точку x*, которая может быть локальным оптимумом ЦФ в задаче (8) – (9). Поэтому, найдя все решения системы (11) – (12), мы получим все точки, в которых ЦФ может иметь локальный оптимум.

4. Среди этих точек после дополнительного анализа отбираются такие, которые действительно являются точками локального оптимума. После сравнения значений ЦФ в этих точках находится точка, являющаяся глобальным оптимумом.

Следует иметь в виду, что если (х*, λ*) — стационарная точка функции Лагранжа, то не обязательно точка х* — локальный оптимум задачи (8) – (9). Это верно лишь тогда, когда исходная задача является задачей ВП. Более того, в этом случае х* — точка глобального оптимума этой задачи. Справедлива следующая теорема.

Теорема 6. Предположим, что задача (8) – (9) является задачей ВП, т.е. все ее ограничения линейные и ищется минимум выпуклой (максимум вогнутой) функции. Тогда, если (х*, λ*) — решение системы (11) – (12), то х* — точка глобального оптимума задачи (8) – (9).

Обобщенный метод множителей Лагранжа.

Для решения задачи (14) – (15) можно использовать обобщенный метод множителей Лагранжа. Основная идея этого метода заключается в последовательном учете ограничений. Предположим для определенности, что решается задача максимизации ЦФ.

Сначала все ограничения отбрасываются, и решается задача безусловной максимизации ЦФ. Находится ее стационарная точка и проверяется ее допустимость. Если оказалось, что эта точка принадлежит ОДР, то процесс вычислений завершается, так как в силу выпуклости задачи (14) – (15) найденная точка является ее решением.

Если же найденная точка не допустима, то формируется новая задача, которая состоит в максимизации ЦФ с учетом первого ограничения задачи. Однако это ограничение записывается не как неравенство, а как равенство.

Получаем классическую задачу условной оптимизации вида:

Z = f (x1,…, xn) ® mах,

g1(x1,…, xn) = b1.

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

L(x1,…, xn, λ) = f (x1,…, xn) + λ (b1 g1 (x1,…, xn))

и решается система уравнений, определяющая стационарные точки этой функции:

Если в результате получен вектор решения такой, что вектор допустим в исходной задаче и λ* ≥ 0, то это означает, что — искомая точка оптимума. Если же оказалось, что λ* < 0 или вектор недопустим в исходной задаче, то вместо первого ограничения берется второе ограничение и рассматривается задача

Z = f (x1,…, xn) ® mах,

g2(x1,…, xn) = b2.

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

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

На практике метод множителей Лагранжа применяется в различных областях. Например, для отыскания минимальных издержек (пример).

загрузка...