Решение задач нелинейного программирования методом множителей Лагранжа

Рассмотрим ЗНП, в которых условия – ограничения (15.2) (см. Лекцию 15) не содержат неравенств:

(16.1)

при условиях

, (16.2)

. (16.3)

Уравнения (16.2) называют уравнениями связи, а про целевую функцию , достигающую экстремальное значение в точке , удовлетворяющей уравнениям связи, говорят, что она имеет условный экстремум.

Положим, что функции и , непрерывны вместе со своими частными производными первого порядка.

Составим вспомогательную функцию

(16.4)

которая называется функцией Лагранжа.

Здесь – постоянные множители (множители Лагранжа).

– функция переменных. Найдем ее стационарные точки (необходимое условие экстремума), решая следующую систему уравнений:

или (16.5)

Вопрос существования экстремума в стационарных точках (достаточное условие экстремума) сводится к исследованию знака полного приращения функции Лагранжа в окрестности этих точек.

Действительно, пусть

, и , – приращения аргументов функции Лагранжа,

– полное приращение самой функции в стационарной точке .

Функция Лагранжа имеет в ней локальный максимум (минимум), если существует такое, что при

выполняется неравенство .

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

Экстремумы целевой функции и функции Лагранжа совпадают.

Проверку достаточного условия экстремума вспомогательной функции (16.4) можно заменить проверкой достаточного условия экстремума целевой функции (16.1).

С этой целью удалим из координат стационарной точки вспомогательной функции (16.4) координаты , . Получим укороченную точку , для которой исследуют знак второго дифференциала целевой функции

и проверяют условия (16.3).

В частности, для случая знак , а вместе с ним и существование экстремума находят по следующему алгоритму:

• вычисляют определитель , где , , ;

• если , то в точке целевая функция имеет экстремум, причем максимум при и минимум при ;

• если , то экстремума нет;

• если , то вопрос экстремума остается открытым.

Методом множителей Лагранжа находят только локальные экстремумы целевой функции.

Перейдем к примерам.

Решим методом множителей Лагранжа задачу из Примера 2 Лекции 15.

Имеем

при условии

.

Составим функцию Лагранжа:

.

Найдем стационарную точку из системы уравнений:

или

Отсюда , , .

Исследуем знак .

Имеем

Так как по условию

или

,

то .

Подставляя это соотношение в , получим

.

Это доказывает, что , , функция Лагранжа имеет минимум . Следовательно, и целевая функция имеет минимум в укороченной точке .

Теперь воспользуемся алгоритмом нахождения экстремума целевой функции, зависящей от двух переменных.

Имеем , , .

Отсюда, , , .

Составим определитель

.

Следовательно, целевая функция имеет экстремум в укороченной точке , причем минимум, т. к. . Находим .

Отметим еще один прием нахождения условного экстремума, когда из уравнений связи (16.2) m переменных , например, , можно явно выразить через оставшиеся переменных:

. (16.6)

Подставив полученные выражения для в целевую функцию, получим функцию от переменных

Задача свелась к нахождению экстремума функции . Пусть точка доставляет экстремум этой функции. Тогда целевая функция имеет условный экстремум в точке .

Обратимся к примеру 2 из Лекции 15.

Из уравнения связи

найдем

и подставим в целевую функцию:

заданную на отрезке .

Найдем стационарную точку:

, .

Сравнивая три числа

,

,

,

получим

.

Следовательно, при и .

В заключение отметим, что множителям Лагранжа можно придать экономический смысл.

Пусть – доход, соответствующий плану , а функция – издержки i-го ресурса, соответствующие этому плану. Тогда – цена (оценка) i-го ресурса, характеризующая изменение экстремального значения целевой функции в зависимости от изменения размера i-го ресурса.