Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике Глава 12. МЕТОДЫ ШТРАФНЫХ ФУНКЦИЙ И БАРЬЕРОВС помощью методов штрафных функций и барьеров задача нелинейного программирования решается путем исследования последовательности задач без ограничений, т. е. по существу подавлением ограничений. Вследствие того, что методы штрафных функций и барьеров не оперируют ограничениями в явном виде, они оказались эффективными в вычислительном отношении для задач НЛП с нелинейными ограничениями. В этой главе мы покажем, как методы штрафных функций и барьеров возникают из некоторой задачи без ограничений, которая эквивалентна задаче НЛП, но тем не менее не может быть решена непосредственно. Вместо этого методы штрафных функций и барьеров аппроксимируют эту задачу последовательностью связанных с ней задач без ограничений, каждая из которых может быть решена с помощью имеющихся алгоритмов оптимизации. Кроме представления этих двух методов мы анализируем их двойственные свойства. Метод штрафных функций, в частности, интересен тем, что он порождает двойственную задачу, принципиально отличную от рассмотренной в гл. 2. По существу, при этом вводится новая обобщенная форма функции Лагранжа. 12.1. ОСНОВЫ МЕТОДОВ ШТРАФНЫХ ФУНКЦИЙ И БАРЬЕРОВМетоды штрафных функций и барьеров используются для решения задачи НЛП
Они преобразуют задачу (12.1), задачу с ограничениями, в последовательность задач, каждая из которых не имеет ограничений. Если бы задача (12.1) не имела ограничений, т. е. если
Чтобы решить задачу (12.1) при
Рис. 12.1. Бесконечно большой штраф. В качестве иллюстрации этого подхода рассмотрим функцию
где Комбинируя
Иначе, вызывает бесконечно большой штраф за выход из допустимой области (рис. 12.1). Ясно, что х является оптимальной для задачи (12.1) тогда и только тогда, когда х решает также задачу без ограничений:
Таким образом, задача (12.1) преобразована в эквивалентную задачу без ограничений. К сожалению, задача без ограничений этого конкретного вида практически не может быть решена. Величину
где Методы штрафных функций и барьеров аппроксимируют
Рис. 12.2. Представление функции этих функций, скажем непрерывных и дифференцируемых, эти методы обходят вычислительные трудности, связанные с использованием Идея метода штрафных функций. Чтобы построить метод штрафных функций, рассмотрим сначала частный случай штрафной функции
Очевидно, что
При этом, если Метод штрафных функций использует последовательность для которой для всех Определим
(мы полагаем, что эти
Задача (12.1) с помощью метода штрафных функций решается следующим образом. При заданном
Рис. 12.3. Методы штрафных функций. Показаны точки Таким образом, вырабатывается последовательность Как будет доказано, предел любой сходящейся подпоследовательности При строгом доказательстве используется более общая форма функции С помощью метода решения задачи без ограничений исходя из точки Вообще, методы штрафных функций аппроксимируют Идея метода барьеров. Методы барьеров аппроксимируют
Очевидно, что Рассмотрим функцию
и последовательность такую, что
(Обратите внимание на то, что здесь в отличие от метода штрафных функций вместо
Рис. 12.4. Метод барьеров. что Несмотря на то, что задача максимизации Аналогично с помощью метода поиска решения для задач без ограничений, отправляясь от точки Завершив на этом пояснение идей метода штрафных функций и метода барьеров, мы приступаем к подробному обсуждению и обоснованию метода штрафных функций.
|
1 |
Оглавление
|