Пример 4 решение

Минимизировать

при ограничениях

Решение.

На рис.1 изображена область допустимых ре­шений сформулированной выше нелинейной задачи. Ясно, что оптимальное решение этой задачи есть . Пока­жем, что условие линейной независимости не выполняется в точке оптимума.

Рис.1 Допустимая область в задаче 4

Так как

Легко видеть, что векторы линейно зависимы, т. е. условие линейной независимости в точке не выпол­няется.

Запишем условия Куна—Таккера и проверим, выполняются ли они в точке (1, 0). Условия (3), (6) и (7) принимают сле­дующий вид;

(11)

(12)

(13)

(14)

(15)

(16)

При из уравнения (11) следует, что , тогда как уравнение (14) дает , Следовательно, точка оптимума не является точкой Куна — Таккера. Заметим, что нарушение условия линейной независимости не обязательно означает, что точка Куна—Таккера не существует. Для того чтобы подтвердить это, заменим целевую функцию из этого примера функцией . При этом оптимум по-прежнему достигается в точке (1,0), в которой условие линейной независимости не выполняется. Условия Куна—Так­кера (12) - (16) остаются неизменными, а уравнение (11) принимает вид

Нетрудно проверить, что точка является точкой Куна—Таккера, т. е. удовлетворяет условиям Куна—Таккера.

Теорема о необходимости условий Куна—Таккера позволяет идентифицировать неоптимальные точки. Другими словами, тео­рему 1 можно использовать для доказательства того, что задан­ная допустимая точка, удовлетворяющая условию линейной неза­висимости, не является оптимальной, если она не удовлетворяет условиям Куна—Таккера. С другой стороны, если в этой точке условия Куна—Таккера выполняются, то нет гарантии, что най­дено оптимальное решение нелинейной задачи. В качестве примера рассмотрим следующую задачу нелинейного программирования.

Следующая теорема устанавливает условия, при выполнении которых точка Куна—Таккера автоматически соответствует оптимальному решению задачи нелинейного программирования.

Теорема.2 Достаточность условий Куна—Таккера

Рассмотрим задачу нелинейного программирования (0) — (2). Пусть целевая функция выпуклая, все ограничения в виде неравенств содержат вогнутые функции , а ограничения в виде равенств содержат линейные функции . Тогда если существует решение , удовлет­воряющее условиям Куна—Таккера (3) — (7), то х* — оп­тимальное решение задачи нелинейного программирования.

Если условия теоремы 2 выполняются, то нахождение точки Куна—Таккера обеспечивает получение оптимального решения задачи нелинейного программирования.

Теорему 2 можно также использовать для доказательства оптимальности данного решения задачи нелинейного программирования. В качестве иллюстрации опять рассмотрим пример:

Минимизировать

при ограничениях

С помощью теоремы 2 докажем, что решение является оптимальным. Имеем

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

чтобы показать, что функция является вогнутой, вычислим

Поскольку матрица отрицательно определена, функция является вогнутой. Функция входит в линейное ограни­чение в вяде равенства. Следовательно, все условия теоремы 2 выполнены; если мы покажем, что - точка Куна-Так­кера, то действительно установим оптимальность решения . Условия Куна-Таккера для примера 2 имеют вид

(22)

(23)

(24)

(25)

, (26)

, (27)

(28)

(29)

Точка удовлетворяет ограничениям (24) — (26) и, следовательно, является допустимой. Уравнения (22) и (23) принимают следующий вид:

Положив ,получим и . Таким образом, реше­ние х*=(1, 5), удовлетворяет условиям Куна—Таккера. Поскольку условия теоремы 2 выполнены, то оптимальное решение задачи из примера 3. Заметим, что существуют также и другие значения и , которые удов­летворяют системе (22) -(29).