Научная электронная библиотека

Монографии, изданные в издательстве Российской Академии Естествознания

Прикладные методы оптимизации

Шукаев Д. Н.,

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

Дана задача нахождения максимума (для конкретности) функции f(x) при ограничениях

gi(x) ≤ 0, i = 1, 2, …, m.

Ограничения x ≥ 0, если таковые имеются, предполагаются включенными в состав m ограничений. Идея метода заключается в том, что если решение безусловной задачи не выполняется для всех заданных ограничений, то условный оптимум должен находиться в граничной точке допустимой области. Это означает, что одно или несколько ограничений из m должны выполняться как равенства. Тогда алгоритм будет состоять из следующих шагов [37]:

Шаг 1. Решить задачу безусловной оптимизации заданной целевой функции и решение проверить по всем m ограничениям. Если ограничения не нарушаются, то оптимальное решение найдено. В противном случае принять k = 1 и перейти к шагу 2.

Шаг 2. Сделать любые k ограничений равенствами и найти оптимум по методу множителей Лагранжа. Если полученное решение будет допустимым по отношению к остальным ограничениям, то оптимальное решение найдено. Если нет, то активными надо сделать k = k + 1 ограничений и повторить шаг 2.

Шаг 3. Если k = m – прекратить вычисления, так как допустимых решений нет.