Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 13.4. МЕТОД r-ВОЗМУЩЕНИЙОдин из способов устранения заклинивания, как было указано выше, заключается в том, что при определении направления Рассмотрим задачу НЛП
где
Множество Подзадача. На каждой итерации при заданной допустимой точке х и 80 алгоритм будет решать следующую подзадачу линейного программирования:
где точка х фиксирована, а Рассмотрим эту подзадачу несколько подробнее. Следует обратить внимание на то, что точка Пусть
и
Согласно выражению (13.23) перемещение в направлении При
и
Кроме того, выбирая масштаб для
и, значит, утверждения (13.24) и (13.25) эквивалентны. Но согласно положениям, высказанным в гл. 2, (13.25) равносильно утверждению, что в точке х выполняются условия Куна — Таккера. Таким образом, мы доказали, что Следующие две леммы также разъясняют поведение подзадачи. Первая из них анализирует множество Лемма 13.3. Пусть
где а) Если
Кроме того, при достаточно больших
для любого б) Если дано фиксированное
Доказательство, а. Для любого
потому что согласно определению
Для всех достаточно больших Следующая лемма дает более подробное описание решений подзадач. Лемма 13.4. Пусть
для любого Кроме того, существует такое
Рис. 13.4. Геометрическая иллюстрация соотношения Доказательство. Определим в так же, как в части (а) леммы 13.3. Сначала анализируем задачу
(Обратите внимание на то, что здесь вместо
удовлетворяет условиям
Из непрерывности
Поэтому Теперь рассмотрим для достаточно больших
Пусть Согласно части (а) леммы
при Достаточно Для завершения доказательства рассмотрим ограничения в (13.28). Очевидно
Кроме того, так Лемма доказана. Замечание. Лемма 13.4 дает определяющее свойство, необходимое в предположениях теоремы 13.2. В частности, предположим, что
Если Таким образом, из теоремы 13.2 заключаем, что Алгоритм
Если При Далее вычисляется
Поиск завершается, если Сходимость. Установим сходимость с помощью теоремы сходимости для методов возможных направлений. Напомним, что Нетрудно видеть, что условие 1 теоремы сходимости выполняется. Установим выполнение условия 2. Пусть
где
Справедливость условия 2а установлена. Для того, чтобы убедиться в соблюдении условий 2б и 2в, мы должны сначала проанализировать последовательность
Наша первая и основная задача заключается в том, чтобы доказать
Теперь рассмотрим произвольную подпоследовательность, сходящуюся к
где Отсюда, воспользовавшись теоремой 13.2, получим, что вся последовательность сходится к
Пусть
Из леммы 13.4 уравнений (13.31) и (13.32) следует, что
Из (13.33) непосредственно вытекает следующее: поскольку
Более того, так как неравенство
то
Условие 26. Из выражения (13.35) легко следует условие 26. Анализ ограничений подзадачи обнаруживает, что
Тогда согласно непрерывности
Условие 2в. Благодаря части (б) леммы 13.3 и соотношению (13.34) для всех достаточно больших
Вследствие того, что
Учитывая далее непрерывность, видим, что не только
но также существует такое
Отсюда, учитывая, что
Рис. 13.5. Геометрическая иллюстрация процедуры Интерпретируя этот результат, видим, что если Замечания. Значительную часть доказательства составляет установление положительности Упражнения(см. скан) (см. скан) (см. скан) (см. скан) Примечания и ссылки§ 13.1 и 13.2. Здесь употребляется слово «заклинивание», хотя ранее Зойтендейк (1960) предложил выражение «зигзагообразное движение». Термин «заклинивание» кажется более выразительным, поскольку показывает, что что-то не работает — произошло заклинивание или, если использовать НЛП, нет сходимости. Многие алгоритмы приводят к зигзагообразному движению в смысле геометрического описания пути, но все же сходятся. Наиболее ранние обсуждения явления заклинивания содержатся в работах Зойтендейка (1960) и Розена (1961). См. также работы Вольфа (1966) и Зангвилла (1967h). То, что отображение М, не будучи замкнутым, может вызвать заклинивание, является новым наблюдением. Пример процедуры, которая приводит к заклиниванию, был предложен Вольфом (1966). Упражнение 13.1 оснозано на его примере. Другой пример, сформулированный в геометрических терминах, см. в работе Зангвилла (1967h). § 13.3. В работе Топкиса и Вейнотта приведена теорема, родственная теореме сходимости для методов возможных направлений, но несколько отличная от нее. Упр. 13.10 также основано на этой работе Топкиса и Вейнотта. § 13.4. Несмотря на то, что доказательство является новым, этот метод был предложен в работе Зойтендейка (1960).
|
1 |
Оглавление
|