Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 2.4. НЕОБХОДИМЫЕ УСЛОВИЯ КУНА—ТАККЕРАЕсли 2.1.1, так как из точки х можно было двигаться в направлении Условия Куна — Таккера представляют собой обобщение следствия 2.1.1 на задачи с ограничениями. По существу они утверждают, что при движении от х в любом направлении, пока точка находится в допустимой области, целевая функция не может увеличиваться. Чтобы выразить эту мысль точнее, начнем с введения понятия возможного направления. При рассмотрении этого вопроса все функции предполагаются дифференцируемыми. Возможные направления. Пусть х является допустимой точкой. Мы определяем возможное направление в точке х как любое направление свойством, что
Если выразить это словами, то направление Вывод условий Куна — Таккера. Следующая лемма определяет поведение целевой функции на направлениях, входящих в Рис. 2.3. (см. скан) Примеры множеств возможных направлений. Лемма 2.11. Пусть Доказательство. Допустим противоположное, т. е. существование Грубо говоря, в оптимальной точке производная целевой функции по направлению указывает на уменьшение в любом возможном направлении. Как будет показано в следующем следствии, этот результат справедлив также для всех направлений из множества Напомним, что множество Следствие 2.11.1. Пусть х — оптимальная точка для задачи НЛП. Тогда
Доказательство. Направление
Так как
Переход к пределу дает
и так как Таким образом, мы видим, что лемма 2.11 справедлива для Доказательство этой теоремы содержит два основных момента. Сначала мы выразим множество Рассмотрим множество Чтобы выразить Следующая лемма утверждает, что если Лемма Доказательство. Рассмотрим множество возможных направлений Условия регулярности. К сожалению, существуют случаи (упр. 12), когда имеются направления из Если С условием регулярности делается первый шаг, а именно такая модификация множества возможных направлений, чтобы оно могло быть выражено через ограничения. В явной форме Резюмируя эти результаты и воспользовавшись следствием 2.11.1, получаем следующее утверждение. Лемма 2.13. Пусть х — оптимальная точка задачи НЛП. Тогда при наличии условия регулярности для любого Теперь можно применить лемму Фаркаша, которая приводится в приложении. Утверждение, что
Отсюда непосредственно следует теорема Куна — Таккера. Теорема 2.14. Рассмотрим задачу НЛП нахождения
где все функции дифференцируемы. Пусть х — оптимальная точка (решение) и предположим, что имеет место условие регулярности. Тогда справедливы следующие три утверждения: 1) х — допустимая точка. Существуют множители
Доказательство. Условия 1 теоремы Куна — Таккера тривиальны, а 2 и 3 являются просто переформулировкой равенства (2.14). Действительно, если Условия 1—3 называются условиями Куна — Таккера. По существу условия Куна — Таккера заменяют заявление о том, что Таким образом, условия Куна — Таккера являются точной математической формулировкой следующей интуитивной концепции: в любом возможном направлении производная Геометрическая интерпретация условий Куна — Таккера дана на рис. 2.4. В оптимальной точке х отрицательный градиент
Условия Куна — Таккера для ограничений-равенств. Часто задача НЛП пишется с ограничениями как в виде равенств, так и в виде неравенств: найти
Рис. 2.4. Геометрическая интерпретация условий Куна—Таккера. В качестве упр. 2.16 предлагается показать, что условиями Куна — Таккера для этой задачи являются 1) х — допустимая точка. Существуют множители
Следует обратить внимание, что неотрицательные множители соответствуют ограничениям-неравенствам, тогда как множители для ограничений-равенств допускаются отрицательными, положительными или нулевыми. Условия Куна — Таккера 2 относятся к ограничениям-неравенствам. Условия Куна—Таккера имеют важнейшее значение в НЛП, и мы будет постоянно пользоваться ими в книге. Замечание. Необходимо подчеркнуть, что условия Куна — Таккера могут установить только неоптимальность точки, так как они являются необходимыми, но недостаточными условиями. К проблеме достаточности мы подойдем с двух сторон. В следующем параграфе будут выведены достаточные условия из соображений по существу геометрических, тогда как далее другие достаточные условия будут получены из теории двойственности.
|
1 |
Оглавление
|