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

Задача формулируется следующим образом. Необходимо найти точку , в которой целевая функция достигает min или max на заданном множестве значений , т.е.

. (1)

Допустимое множество, на котором определен критерий

.

Структура его зависит от соотношения числа уравнений и числа неизвестных . Соотношение называют дефектом системы.

При , если система уравнений является совместной, тогда представляет собой совокупность корней данной системы уравнений. В этом случае для решения задачи (1) достаточно просмотреть эту совокупность и выбрать ту точку, в которой достигает оптимального значения. Если система линейна, то система имеет единственный корень. Если нелинейна, то число корней может быть сколь угодно большим. Например,

 

Рис.1. Некоторое множество изолированных корней.

Рис.2. Бесконечное множество корней.

При положительном дефекте в случае линейной системы и множество представляет собой прямую, в случае – плоскость, при – многогранник типа конуса и т.д.

В случае нелинейной системы при множество представляет собой некоторую кривую, при – поверхность, при и более – конус.

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

Вообще говоря, задачу (1) можно решать и приближенно, переходя к задаче с ограничениями в виде неравенств

Решение находится с точностью .

Рис.4.

 

При для решения задачи (1) обычно, если это удается, поступают следующим образом. Пусть имеется задача (1) с системой ограничений

, (2)

 

причем , т.е. . Систем ограничений совместна и лишних ограничений нет. Тогда часть переменных, а именно , выразим в явном виде из (2) через другие , т.е.

(3)

В критерий вместо подставляем выражения из (3)

.

В результате получаем задачу безусловной оптимизации меньшей размерности

.

Следовательно, можем воспользоваться необходимыми условиями экстремума и найти решение задачи (1), решив систему

. (4)

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

Самое сложное при таком подходе разрешить систему ограничений, представив ее в виде (3). Далеко не всегда удается получить разрешение в форме (3) в элементарных функциях. Вопрос о том, когда функции существуют, дает теорема о неявных функциях.

Пусть все функции . Рассмотрим первые частные производные этих функций. Эти производные можно рассматривать как элементы прямоугольной матрицы размерности

.

Из нее можно выделить различных подматриц порядка . Например,

.

Эта матрица называется якобианом функций по переменным . Индекс указывает на точку, в которой вычислены элементы якобиана.

Пусть множество индексов из числа , не принадлежащих множеству .

Теорема о неявных функциях.

Пусть обладает следующими свойствами:

1. В некоторой -окрестности точки функции , .

2. .

3. Матрица - неособенная.

Тогда существует -окрестность ( >0) точки из такая, что для любой точки из этой -окрестности существуют однозначные и непрерывные в т очке функции , , …, , обладающие свойствами:

А) , .

Б) При любом из -окрестности значения , , вычисленные по вместе с компонентами вектора образуют вектор , удовлетворяющий .

В) В -окрестности функции дифференцируемы и при данных , , производные являются единственным решением системы уравнений

. (5)

Выведем необходимые условия, которым должна удовлетворять точка , доставляющая относительный максимум или минимум на множестве

.

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

Рассмотрим для начала функцию двух переменных с одним ограничением. Пусть имеем , . Найдем необходимые условия, которым должна удовлетворять точка , если в ней достигается относительный максимум (или минимум) при .

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

Следовательно, мы можем исключить в . Имеем

для . Но если имеет в точке относительный максимум при , то должно существовать такое число , , что для всех в -окрестности точки справедливо

.

Следовательно, имеет безусловный максимум в точке . (Аналогично для минимума).

Сложная функция дифференцируема в окрестности и

(6)

Дифференцируя как сложную функцию, получим

,

так как по теореме о неявных функциях

.

Из (6) следует

.

Обозначим

.

Таким образом, необходимо, чтобы точка удовлетворяла уравнениям

(7)

Т.е. удовлетворяла системе 3-х уравнений с тремя неизвестными: , и .

Решив систему, найдем все точки, где достигает относительного максимума или минимума при .

Необходимые условия (7) удобнее получать, составив следующую функцию

(8)

и приравняв 0 ее частные производные по , и .

.

Функцию называют функцией Лагранжа, а - множителем Лагранжа.

 

 

Рис. 3. Геометрическая иллюстрация: - относительные максимумы;

- относительный минимум

Рассмотрим общий случай с переменными и ограничениями. Пусть в точке функция имеет относительный максимум или минимум для . Далее предположим, что в точке ранг матрицы

равен . Для простоты будем считать, что матрица является неособенной (первые столбцов).

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

причем функции непрерывно дифференцируемы в окрестности точки и

, .

Функция имеет в точке безусловный относительный максимум или минимум. Поэтому . (9)

По правилу дифференцирования сложной функции , . (10)

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

, . (11)

Имеем таких систем. Можно, конечно, решить систему (11) и результаты подставить в (10). Но поступим следующим образом. Рассмотрим набор чисел , , являющийся решением системы уравнений , . (12)

Решение этой системы существует и единственно, так как матрица коэффициентов по предположению неособенная. Умножим -е уравнение из (11) на и просуммируем по . Для каждого , , получаем

. (13)

Из (9) и (10) следует , . (14)

Вычислим (13) в точке и вычтем из (14), получим

,

. (15)

Отсюда, используя (12), имеем , . (16)

Объединив (16) с (12) и ограничениями, получим, что точка , в которой достигается относительный максимум или минимум должна удовлетворять следующей системе из уравнений

(17)

Каждая точка , в которой достигается относительный максимум или минимум при , будет являться решением системы (17).Необходимые условия можно получить, составив функцию Лагранжа (18)

и приравняв 0 ее частные производные по всем , , и по всем , .

.

Построение таким образом необходимых условий называют методом множителей Лагранжа.