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

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

Схема реализации обобщенного метода множителей Лагранжа

Реализация метода состоит в выполнении следующих шагов.

Шаг 1. Параметр k (число учитываемых ограничений задачи) полагается равным нулю. Исходная задача решается без учета ограничений. Если найденная экстремальная точка удовлетворяет всем ограничениям исходной задачи, то она запоминается. Параметр k увеличивается на единицу: . Переход на шаг 2.

Шаг 2. Формируется система из k ограничений-равенств текущей задачи: произвольные k ограничений-неравенств исходной задачи делаются «активными» посредством замены знака неравенства на знак равенства и включаются в формируемую систему ограничений. Переход на шаг 3.

Шаг 3. Полученная на предыдущем шаге текущая задача с исходной целевой функцией и системой «активных» ограничений-равенств решается каким-либо подходящим методом (например, обычным методом множителей Лагранжа). Если найденная экстремальная точка удовлетворяет ограничениям исходной задачи, то она запоминается. Переход на шаг 4.

Шаг 4. а) Если (число активных ограничений меньше числа ограничений исходной задачи), то формируется такая система из k активных ограничений, которая еще не разу не присутствовала в решаемых перед этим задачах, после чего производится переход на шаг 3. В том случае, когда все возможные наборы из k активных ограничений перед этим рассмотрены, а соответствующие задачи решены, параметр k увеличивается на единицу: . Переход на шаг 2.

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

Замечание 4.1. Возможности применения метода для решения практических задач без применения компьютера ограничены, поскольку для его реализации требуется вместо одной исходной задачи решать большое число задач с ограничениями-равенствами. Например, если число ограничений в (4.2) , а число активных ограничений , то тогда на шаге 2 надо будет решить

задач с тремя ограничениями-равенствами.

Условия Куна-Таккера

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