![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
Eng | Rus | Ukr | ![]() |
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
![]() |
![]() |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
Исследование операций
|
19.09.2004
|
![]() |
![]() |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
6.5. МЕТОДЫ ВОЗМОЖНЫХ НАПРАВЛЕНИЙЭтот класс методов решения задач НП основан на движении из одной допустимой точки к другой с лучшим значением целевой функции. Типичная стратегия поиска в алгоритмах этого класса состоит в следующем. Возьмем текущую допустимую точку После нахождения допустимого направления Метод ЗойтендейкаТипичным представителем класса методов возможных направлений является метод Зойтендейка. На каждой итерации метода находят возможное направление спуска, а затем проводят оптимизацию вдоль этого направления. Для изложения идеи метода введем ряд необходимых понятий [2; 8]. Определение 6.1. Рассмотрим задачу минимизаци Ненулевой вектор Вначале рассмотрим случай, когда ограничения линейные и задача НП имеет вид: минимизировать при условиях
где Справедливо следующее утверждение. Лемма 6.1. Рассмотрим задачу минимизаци (6.5.1)-(6.5.3). Пусть Ненулевой вектор Доказательство этого утверждения очень простое. Предлагаем читателю выполнить это самостоятельно. Проиллюстрируем геометрически множество возможных направлений спуска на следующем примере. Пример 6.3. Минимизировать
На рис. 6.11. изображена совокупность этих направлений, образующая конус возможных направлений. Здесь 1 - конус возможных направлений; 2 - конус возможных направлений спуска; 3 - линии уровня целевой функции; 4 - полупространство направлений спуска. Если вектор Построение возможных направлений спускаПусть задана текущая допустимая точка Следовательно, в задачу должно быть включено условие, которое бы ограничивало вектор Задача при условиях
![]() Задача при условиях
![]() Задача при условиях
![]() Задачи Так как Лемма 6.2. Рассмотрим задачу минимизаци где Доказательство. Как следует из теоремы Куна-Таккера (гл.5),
Согласно следствию из леммы Фаркаша система (6.5.4) разрешима тогда и только тогда, когда система неравенств Итак, мы показали, как найти возможное направление спуска. Пусть теперь минимизировать при условиях
Предположим, что минимизировать при условии
где
Алгоритм метода Зойтендейка в случае
|
|
|
. (6.5.13)
Если , то остановиться, и
- оптимальное решение (точка Куна-Таккера). В противном случае перейти ко второму шагу.
Второй шаг. Положить равным оптимальному решению приведенной ниже задачи одномерной оптимизации:
минимизировать
при условии ,
где задается формулой (6.5.9).
Для решения этой задачи можно применить любой метод одномерного поиска, например метод Фибоначчи.
Вычислить , определить новое множество активных ограничений для решения
и переопределить
и
. Заменить
на
и перейти к первому шагу следующей итерации.
Рассмотрим задачу, в которой допустимая область задается системой ограничений-неравенств нелинейного типа:
минимизировать (6.5.14)
при условиях (6.5.15)
В следующей теореме формулируются достаточные условия, при которых вектор является возможным направлением спуска. [2; 18].
Теорема 6.2. Рассмотрим задачу НП (6.5.14), (6.5.15). Пусть - допустимая точка, а
- множество индексов активных в этой точке ограничений, т.е.
. Предположим, кроме того, что функции
для
дифференцируемы в точке
, а функции
для
непрерывны в этой точке. Если
,
при
, то вектор
является возможным направлением спуска.
Доказательство. Пусть вектор удовлетворяет неравенствам
,
при
. Сначала укажем, что для
выполняются неравенства
и так как
непрерывны в точке
, то
для достаточно малых
. В силу дифференцируемости функции
,
имеем
, где
при
. Так как
, то
при достаточно малых
. Следовательно, точка
допустима для малых значений
. Аналогично из
следует, что для достаточно малых
.
Таким образом, вектор является возможным направлением спуска.
На рис. 6.12 показана совокупность возможных направлений в точке
. Здесь использованы такие обозначения: 1 - первое ограничение, 2 - третье ограничение, 3 - четвертое ограничение, 4 - второе ограничение, 5 - возможные направления спуска, 6 - линии уровня целевой функции. Вектор
, удовлетворяющий равенству
, является касательным к кривой линии (или поверхности)
. Поскольку функции
нелинейны, то движение вдоль такого
вектора может привести в недопустимую точку, что вынуждает требовать выполнения строгого неравенства .
Чтобы найти вектор , удовлетворяющий неравенствам
,
для
, вполне естественно минимизировать максимум из величин
и
для
. Обозначим этот максимум через
. Вводя нормирующие условия
, для всех
, приходим к следующей вспомогательной задаче нахождения возможного направления спуска:
минимизировать (6.5.16)
при условиях
, (6.5.17)
, (6.5.18)
. (6.5.19)
Пусть - оптимальное решение этой задачи ЛП. Если
, то, очевидно,
- возможное направление спуска. Если же
, то, как будет показано ниже, точка
является точкой Куна-Таккера.
Докажем это утверждение. Оптимальное значение целевой функции в задаче (6.5.16)-(6.5.19) равно нулю тогда и только тогда, когда система неравенств
,
при
несовместна. Но, согласно следствию из леммы Фаркаша, для того чтобы эта система не имела решения, необходимо и достаточно, чтобы существовали такие числа
, что
(6.5.20)
и либо , либо
для некоторого
, а это одно из условий оптимальности теоремы Куна-Таккера.
Предварительный этап. Выбрать точку , для которой
. Положить
и перейти к основному этапу.
Основной этап. Первый шаг. Положить и решить задачу:
минимизировать (6.5.20)
при условиях
, (6.5.21)
. (6.5.22)
Пусть - оптимальное решение задачи (6.5.20) - (6.5.22). Если
, то конец алгоритма и точка
- оптимальное решение такой задачи одномерной оптимизации. Если
, то перейти ко второму шагу.
Второй шаг.
минимизировать (6.5.23)
при условии , (6.5.24)
где . (6.5.25)
Положить , заменить
на
и перейти к первому шагу следующей итерации.
Пример 6.4. Рассмотрим задачу:
минимизировать
при условиях
Будем решать эту задачу методом Зойтендейка, начиная поиск из точки . Заметим, что
Первая итерация. Первый шаг. В точке имеем
, а множество индексов активных ограничений есть
. При этом
. Задача нахождения возможного направления имеет вид
минимизировать
при условиях
Можно проверить, решая эту задачу симплекс-методом, что оптимальным решением этой задачи является вектор и
.
Второй шаг. Линейный поиск. Любая точка по направлению из точки
может быть представлена в виде
, а соответствующее ей значение целевой функции равно
. Максимальное значение
, для которого точка
остается допустимой, равно
. Итак, решаем задачу одномерной минимизации:
минимизировать
при условии
Оптимальное значение . Итак,
.
Вторая итерация. Первый шаг. В точке имеем
. Активных ограничений в этой точке нет, поэтому задача определения направления спуска имеет вид:
минимизировать
при условиях
Оптимальным решением является вектор , а
.
Второй шаг. Легко проверить, что , при котором точка
допустима, равна 0.3472. При этом активным становится ограничение
. Оптимальное значение
находим в результате решения задачи:
минимизировать
при условии
Оно равно 0.3472, так что . Остальные итерации проводятся аналогично. Результаты вычислений на первых четырех итерациях метода приведены в табл. 6.5.
На рис. 6.13 показан процесс поиска оптимума. Заметим, что следующей точкой будет , а значение целевой функции в этой точке равно -
-6.544, тогда как в оптимальной точке значение ц.ф. равно -6.559.
|
|
|
Поиск направления Линейный поиск |
|||||
|
|
|
|
|
|
|||
1 |
0.00;-0.75 |
-3.375 |
-5.50;-3.00 |
1.000;-1.000 |
-1.000 |
0.4140 |
0.2088 |
0.2083;-0.5417 |
2 |
0.208;-0.541 |
-3.635 |
-4.25;-4.25 |
1.000;-1.000 |
-8.5 |
0.3472 |
0.3472 |
0.555;-0.889 |
3 |
0.555;-0.889 |
-6.346 |
-3.556;-3.555 |
1.000;-0.533 |
-1.663 |
0.0924 |
0.0924 |
0.648;-0.840 |
4 |
0.648;-0.840 |
-6.468 |
-3.088;-3.937 |
-0.517; 1.000 |
-2.340 |
0.0343 |
0.0343 |
0.630;-0.874 |
Метод возможных направлений может быть модифицирован на случай, когда кроме ограничений неравенств имеются нелинейные ограничения-равенства. Для иллюстрации обратимся к рис. 6.14, который отвечает единственному ограничению-равенству. Для заданной допустимой точки в этом случае не существует ненулевого направления
такого, что
при
, для некоторого
. Это затруднение можно преодолеть, если двигаться вдоль касательного направления
, для которого
, а затем скорректировать это движение и вернуться в допустимую область (рис. 6.14.).
Поясним этот подход на примере:
минимизировать (6.5.26)
при условиях
,
. (6.5.27)
Пусть - допустимая точка и
. Будем решать следующую задачу ЛП:
минимизировать (6.5.28)
при условиях
, (6.5.29)
. (6.5.30)
Искомое направление является касательным к ограничениям-равенствам и к некоторым активным нелинейным ограничениям-неравенствам. Линейный поиск вдоль
и последующее возвращение в допустимую область приводят в точку
, после чего процесс поиска повторяется. Один из существенных недостатков рассмотренного варианта метода состоит в том, что если точка
, которая задает текущее решение, окажется близка к границе, определяемой одним из ограничений, а оно не используется в процессе нахождения направления движения, то может оказаться, что сделав лишь небольшой шаг, мы окажемся на границе, определяемой этим ограничением. Поэтому оказывается целесообразным расширить множество активных ограничений
, определив его так:
, где
- достаточно малое число.
Анализ алгоритма Зойтендейка показал, что он может не сходиться к точке Куна-Таккера. Трудность здесь заключается в том, что длина шагов вдоль генерируемых направлений стремится к нулю, вызывая 'заедание' процесса в неоптимальной точке. Во избежание этого Топкинс и Кейнотт [4] разработали модификацию метода возможных направлений. Эта модификация гарантирует сходимость алгоритма к точке Куна-Таккера. Итак, рассмотрим задачу:
минимизировать
при условиях .
При заданной допустимой точке возможное направление находят, решая следующую задачу ЛП:
минимизировать (6.5.31)
при условиях
, (6.5.32)
, (6.5.33)
. (6.5.34)
Как видим, в этой модификации при определении направления движения учитываются все ограничения как активные, так и неактивные.
В отличие от метода возможных направлений, описанного выше, здесь мы не сталкиваемся с неожиданным изменением направления, когда приближаемся к границе множества допустимых решений, определяемой неактивным в текущей точке ограничением .
Дадим описание модифицированного алгоритма возможных направлений.
Начальный этап. Выбрать начальную точку , для которой
при
. Положить
и перейти к основному этапу.
Основной этап. Первый шаг. Положить равным оптимальному решению задачи ЛП:
минимизировать (6.5.35)
при условиях , (6.5.36)
, (6.5.37)
. (6.5.38)
Если , то остановиться,
является точкой Куна-Таккера. В противном случае (при
) перейти ко второму шагу.
Второй шаг. Положить равным оптимальному решению задачи:
минимизировать (6.5.39)
при условии ,
где . (6.5.40)
Положить , заменить
на
и перейти к первому шагу.
Пример 6.5. Рассмотрим задачу:
минимизировать
при условиях
Применим для решения модифицированный алгоритм возможных направлений. Выберем в качестве начальной точки . Заметим, что в этой точке
, а градиенты функций-ограничений соответственно равны
.
Первая итерация. Первый шаг. В точке имеем
. Задача поиска направления спуска имеет вид:
минимизировать
при условиях
В правой части ограничений этой задачи, кроме первого, стоят значения . Заметим, что одно из ограничений (
) повторяется дважды, следовательно, одно из ограничений можно опустить. Оптимальным решением этой задачи является вектор
, при котором
.
Второй шаг (линейный поиск). Решаем задачу:
минимизировать
Максимальное значение , для которого точка
допустима, определяется соотношением (6.5.40) и равно
. Тогда оптимальным решением задачи (6.5.41) будет
.
Таким образом, .
Вторая итерация. Первый шаг. В точке имеем
. В качестве направления
берется оптимальное решение следующей задачи:
минимизировать
при условиях
Оптимальным решением этой задачи является вектор .
Второй шаг. Максимальное значение
, для которого точка
допустима, равно
. Легко можно проверить, что
достигает минимума на отрезке
в точке
. Следовательно,
. Далее этот процесс повторяется. В табл. 6.6 приведены результаты вычислений на первых пяти итерациях. Траектория движения точки, задающей текущее решение, показана на рис. 6.15. В конце пятой итерации получена точка
со значением целевой функции -6.559. Заметим, что в оптимальной точке
значение целевой функции равно -6.613.
|
|
|
Первый шаг Второй шаг |
|||||
|
|
|
|
|
|
|||
1 |
0.00;-0.75 |
-3.375 |
-5.50;-3.00 |
0.714;-0.0357 |
-0.714 |
0.84 |
0.84 |
0.600;-0.720 |
2 |
0.600;-0.720 |
-5.827 |
-3.04; -4.32 |
-0.0712; -0.117 |
-0.288 |
1.562 |
1.562 |
0.489;-0.902 |
3 |
0.489;-0.902 |
-6.145 |
-3.849;-3.369 |
0.0957;-0.0555 |
-0.1816 |
1.564 |
1.564 |
0.6385;-0.8154 |
4 |
0.6385;-0.8154 |
-6.343 |
-5.63 ;-4.02 |
-0.016;-0.0433 |
-0.0840 |
1419 |
1.419 |
0.616;- 0.877 |
5 |
0.616;-0.877 |
-6.508 |
-3.29;-3.725 |
0.0268;-0.0132 |
-0.0303 |
1.455 |
1.455 |
0.655;-0.858 |