Задача НЛП с ограничениями-равенствами.

Метод Лагранжа

1

В НЛП особо рассматриваются задачи с ограничениями-равенствами:

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

2

или

где F() — целевая функция задачи (1), ( множители Лагранжа

3

Если все ограничения выполняются, то

Ф() = F().

Таким образом, задача минимизации нелинейной целевой функции с ограничениями-равенствами сводится к минимизации функции Лагранжа без ограничений.

Для ее решения используется классический прием — записываются необходимые условия существования экстремума:

4

5

или

6

После выполнения операций дифференцирования, получаем в общем случае систему нелинейных уравнений относительно xi и λi – неизвестных и

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

Решение системы (3) дает точки, подозрительные на экстремум. Их еще надо проверить с помощью достаточных признаков экстремума.

Рассмотрим некоторые из этих

признаков.

7

1. Пусть * — точка подозрительная на экстремум, полученная с помощью выражений (3).

Рассмотрим матрицу Гессе — матрицу H вторых производных в точке *:

8

Если эта матрица определена:

положительно, то точка * - минимум; отрицательно, то точка * - максимум;

знаконеопределена, то признак не дает ответа на вопрос;

полуопределена, то признак не дает ответа на вопрос.

9

2. Пусть — угловой минор матрицы Гессе k-го порядка:

a)если , , , ... — это достаточный признак минимума;

b)если , , , ... — это достаточный признак максимума (знаки строгих неравенств чередуются, начиная с отрицательного);

c)если же в определителях знаки ≥ и ≤, то это необходимый, а не достаточный признак, и вопрос об экстремуме не решается.

10