47732 (Нелинейное программирование), страница 2

Рассмотрим следующую общую задачу не­линейного программирования:

минимизировать (0)

при ограничениях (1)

(2)

Определение:

Ограничение в виде неравенства называется активным, или связывающим, в точке , если , и неактивным, или несвязывающим, если

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

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

3.1. Условия Куна—Таккера и задача Куна—Таккера

Найти векторы ,удовлетворяющие следующим условиям

(3)

(4)

(5)

(6)

(7)

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

Пример 3

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

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

Решение.

Записав данную задачу в виде задачи нелиней­ного программирования (0)-(2), получим

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

откуда

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

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

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

Таким образом, этой задачи условия Куна—Танкера записываются в следующем виде:

3.2. Интерпретация условий Куна — Таккера

Для того чтобы интерпретировать условия Куна — Таккера, рассмотрим задачу нелинейного программирования с ограничения­ми в виде равенств:

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

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

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

(8)

(9)

Далее рассмотрим функцию Лагранжа для задачи нелинейного программирования с ограничениями в виде равенств

Для этой функции условия оптимальности первого порядка запи­сываются в виде

Нетрудно видеть, что условия Куна-Таккера (8) и (9) совпадают с условиями оптимальности первого порядка для задачи Лагранжа.

Рассмотрим задачу нелинейного программирования с ограни­чениями в виде неравенств:

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

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

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

Соответствующая функция Лагранжа имеет вид

Условия оптимальности первого порядка записываются как

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

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

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

3.3. Теоремы Куна—Таккера

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

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

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

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

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

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

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

Пример 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 можно также использовать для доказательства оптимальности данного решения задачи нелинейного программирования. В качестве иллюстрации опять рассмотрим пример: