Пример. Минимизировать

при ограничении .

Соответствующая задача безусловной оптимизации записывается в следующем виде.

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

Приравняв две компоненты градиента L к нулю, получим:

Поставив полученные значения в уравнение, получимт.е.. Следовательно,

2.5. Метод куна – таккера

2.5.1. Условия Куна–Таккера

Метод множителей Лагранжа можно использовать при построении критериев оптимальности для задач с ограничениями в виде равенств. Кун и Таккер обобщили этот подход на случай общей задачи нелинейного программирования с ограничениями как в виде равенств, так и в виде неравенств. Рассмотрим следующую общую задачу нелинейного программирования

Минимизировать f(x) при ограничениях ,

,

где .

Ограничения в виде неравенства называется активным, или связывающим, в точке, если, и неактивным, или не связывающим, еслигде- допустимая точка, то есть удовлетворяющая всем ограничениям. Если существует возможность обнаружить ограничения, которые неактивны в точке оптимума, до непосредственного решения задачи, то эти ограничения можно исключить из модели и тем самым уменьшить ее размеры.

Кун и Таккер построили необходимые и достаточные условия оптимальности для задач нелинейного программирования, исходя из предположения о дифференцируемости функций Итак, задача Куна–Таккера состоит в том, чтобы найти векторыудовлетворяющие следующим условиям:

Прежде всего, проиллюстрируем условия Куна–Таккера на примере.

Минимизировать при ограничениях

Записав данную задачу в виде задачи линейного программирования, можно получить

Уравнение (2.1), входящее в состав условий Куна–Таккера, принимает следующий вид:

откуда

Неравенства (2.2) и уравнения (2.3) задачи Куна–Таккера в данном случае записываются в виде

Уравнения (2.4), известные как условие дополняющей нежесткости, принимают вид

Заметим, что на переменные U₁ и U₂ накладывается требование неотрицательности, тогда как ограничение на знак отсутствует. Таким образом, для данной задачи условия Куна–Таккера записываются в следующем виде:

2.5.2. Необходимость условий Куна–Таккера

Теорема 1. Пусть f, g_j и h_k – дифференцируемые функции, а x^* - допустимое решение данной задачи. Далее пусть илинейно независимы. Еслиx^* - оптимальное решение задачи нелинейного программирования, то существует такая пара векторов чтоявляется решением задачи Куна–Таккера.

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

1. Все ограничения в виде равенств и неравенств содержат линейные функции.

2. Все ограничения в виде неравенств содержат вогнутые функции, все ограничения - равенства – линейные функции, а также существует по крайней мере одна допустимая точка , которая расположена во внутренней части области, определяемой ограничениями- равенствами.

Другими словами, существует такая точка , что

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

Рассмотрим пример.

Минимизировать при ограничении

Запишем условия Куна–Таккера:

Так как ограничения содержат линейные функции, условие линейной независимости выполняется во всех допустимых точках. Легко видеть, что х = 3 – точка оптимума. Рассмотрим допустимое решение х = 2. Для того чтобы доказать его неоптимальность, проверим выполнение условий Куна–Таккера. Из уравнений (2.8) и (2.9) следует, что U₁=U₂=0; однако значения х=2, U₁=U₂=0 не удовлетворяют уравнению (2.6). Следовательно, исходя из необходимых условий Куна-Таккера, точка х=2 не может быть оптимальной.

С другой стороны, решение х=U₁=U₂=0, то есть х – другая точка из допустимой области, удовлетворяет системе уравнений (2.6)-(2.10) и, следовательно, определяет точку Куна–Таккера, однако оптимальным не является. Условия Куна–Таккера должны выполняться в точке оптимума х=3. Нетрудно проверить, что решение х=3 и U₁=0, U₂=6 удовлетворяет условиям Куна–Таккера (2.6)–(2.10).