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

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

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

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

Z = f (x ₁,…, x_n)® mах,

g ₁(x ₁,…, x_n)= b ₁.

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

L (x ₁,…, x_n, λ) = f (x ₁,…, x_n) + λ (b ₁ – g ₁(x ₁,…, x_n))

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

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

Z = f (x ₁,…, x_n)® mах,

g ₂(x ₁,…, x_n)= b ₂.

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

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

Поиск по сайту: