Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 14.2. ВОГНУТЫЙ АЛГОРИТМ ОТСЕЧЕНИЙВогнутый метод отсечений относится к задаче Преобразование задачи. Рассмотрим задачу
Вводя скалярную величину
По существу, добавлением одного ограничения и одной переменной мы заменили задачу (14.15) задачей с линейной целевой функцией. Пусть
Тогда задача (14.16) эквивалентна задаче
Следовательно, мы свели задачу (14.15) к задаче с одним ограничением и линейной целевой функцией. Кроме того, согласно свойству Меняя обозначения, видим, что достаточно рассмотреть задачу
где Предположения. Вогнутый алгоритм отсечений для задачи (14.17) предполагает, что допустимое множество задачи (14.17) содержится в компактном множестве
Мы тйкже предполагаем, что функция ограничения
Равномерная ограниченность означает, что существует положительное число М, такое, что Теперь мы полностью определим отображения, которые составляют вогнутый метод отсечений. Детализация алгоритма. При заданном множестве
Тогда отображение Г имеет следующий вид:
Для заданной точки
где Отображение
Воспользовавшись введенными обозначениями, получаем: если
Для того чтобы начать поиск, положим, что Процедура формирования
и множество
Как было отмечено в § 14.1, все подзадачи — задачи ЛП. Построение метода выборл Прежде чем установить сходимость алгоритма, докажем следующую лемму. Лемма 14.1. Для всех Доказательство. Пусть
Следовательно, Но так как
и по предположению Теперь сходимость будет установлена с помощью теоремы сходимости для метода отсечений. Условие I. Для всех к Условие 2. Очевидно из определения Г. Условие 3. Отображение А замкнуто согласно упр. 2. Ясно, что Условие 4. Если
Кроме того, согласно лемме 14.1
Алгоритм сходится. Интерпретация сходимости. Пусть х — решение задачи (14.17). Тогда из леммы 14.1 и вида задачи (14.20) следует, что
Значит, если 14.2.1. Действие вогнутого метода отсеченийПусть
и имеет решение На рис. 14.2 показано
и имеет решение На рис. 14.3 показано С геометрической точки зрения гиперплоскости
используются для отсечения части множества. Отсюда и происходит название алгоритма отсечений. Вогнутый метод отсечений существенно зависит от вогнутости
Рис. 14.1. Исходные данные.
Рис. 14.2. Первая итерация.
|
1 |
Оглавление
|