ВЕРХНЯЯ ГРАНИЦА ДЛЯ ДЭ301

Пусть область Т разбита на Nk подобластей Т-к), Т-к) = {0: ;0i,/.(*) <0<0tU(*)}

где к - номер итерации алгоритма решения ДЭ301, который будет рассмотрен позднее.

Обозначим через Т(к) совокупность всех подобластей Т-к), i = ,...,Nk.

Поскольку

то одно ограничение эквивалентно Nk ограничениям

где функции Xi,0O определяются формулами (6.17).

Поэтому в задаче (7.3) можно заменить ограничение (7.4) на Nk ограничений (7.20). Тогда получим

Заменим в этой задаче ограничения (7.22) на ограничения

где Хи(^)> i = h—>Nk дается формулой (6.21).

В частности, когда Nk = 1, ограничение “/,(<7) < 0 заменяется ограничением хГ(б0^0. Подставив выражение (6.21) для Хи в формулу (7.24), получим

Используем теорему П.6. Добавляя новые поисковые переменные z1, I = Nk , соответствующие областям Т[к преобразуем эту задачу к виду

В соответствии с теоремой П.З заменим каждое ограничение (7.26) следующими m ограничениями:

Следовательно, задача (7.25) может быть переписана в виде

Пусть есть решение задачи (7.27), тогда [d(k

z'-w] есть решение задачи (7.23). Обозначим через 0у/ решение задачи

Будем называть точку (У1 активной, если соответствующее неравенство (7.28) является активным в точке решения задачи (7.27), т.е. имеет место равенство

Ясно, что условие (7.30) эквивалентно условию ytfj(d(k)) = 0.

Аналогично множеству активных точек $АР задачи ДЭЗО1 введем множество активных точек S[kp задачи (7.27)

Будем называть область Tj-k) активной, если ей соответствует хотя бы одно равенство (7.30). Активной области с номером / соответствует условие

Ясно, что число активных областей не может быть больше размерности вектора d

Используя теорему П.6, можно записать задачу (7.27) в виде

Рассмотрим некоторые свойства задачи (7.23).

Свойство 1. flu'(k) есть верхняя граница оптимального значения целевой функции ДЭ301.

Сравним задачи (7.21) и (7.23). Используя неравенство (6.22), на основе теоремы П.2 получим

Поэтому мы будем называть задачи (7.23) и (7.27) задачами вычисления верхней границы ДЭ301.

Свойство 2. Если Т{рЛ) получается разбиением некоторых подобластей множества Т^, т.е. выполняется условие

Из формы функции у, , [см. формулу (6.21)] видно, что

Отсюда в соответствии с теоремой П.2 получаем неравенство (7.35). Таким образом, дробление некоторых подобластей множества Т(р) не ухудшает верхнюю границу ДЭ301. В большинстве случаев она улучшается.

Свойство 3. Пусть область Т разбита на достаточно малые подобласти Г/**. Тогда решение задачи (7.23) будет достаточно близко к решению задачи ДЭ301 [см. формулу (7.3)]. В пределе решение задачи (7.23) будет стремиться к решению задачи ДЭ301

Дадим нестрогое доказательство этого свойства. Для достаточно малых подобластей Tfl = 1,..., Nk) получаем

где 0/ принадлежит области Т/к

Следовательно, в этом случае

Подставляя это выражение в задачу (7.23), получим задачу, близкую к задаче ДЭ301 в форме (7.3). Поэтому fXk) будет близко к /,.

Если maxr(7’/*)) —»0 (при Л—»оо и условии, что соотношение (7.19)

удовлетворяется), то приближенное равенство (7.35) будет стремиться к точному и задача (7.23) будет стремиться к задаче (7.3).

Свойство 4. Если размеры каждой подобласти стремятся к нулю, то множество SAP стремится к множеству SAP.

Если размеры всех подобластей 7’/*) стремятся к нулю, то согласно свойству 3 задача (7.23) стремиться к ДЭ301, и ограничения (7.24) превращаются в ограничения (7.6). Поэтому множество S(AP активных точек задачи (7.23) стремится к множеству активных точек задачи ДЭЗО1.

Рассмотрим теперь алгоритм вычисления верхней границы оптимального значения целевой функции ДЭ301 [решения задачи (7.23)]. Так как эта задача имеет вид (3.1), то для ее решения можно использовать алгоритм внешней аппроксимации (см. главу 3). Этот алгоритм имеет следующие два главных шага на каждой итерации:

  • - вычисление нижней границы величины
  • - проверка критерия окончания итерационной процедуры. В случае необходимости продолжения итерационной процедуры алгоритм увеличивает множество критических точек для улучшения аппроксимации ограничений (7.28).

Будем использовать решение задачи (3.3), которая в данном случае имеет вид

Обозначим через S^jp) множество критических точек, принадлежащих подобласти Г/*', где р - номер итерации в алгоритме внешней аппроксимации решения задачи (7.23), а к- номер итерации в алгоритме решения ДЭЗО 1. Множество S^lP) будет образовываться автоматически при решении задачи (7.23). Пусть

Заметим, что задача (7.40) получается из задачи (7.23) заменой ограничений (7.24) ограничениями (7.41). Из рассуждений главы 3 еледует, что задача (7.40) дает нижнюю границу оптимального значения целевой функции задачи (7.23).

Сравним задачу (7.40) с задачей, дающей нижнюю границу оптимального значения целевой функции ДЭ301 [см. формулу (7.18)]. В задаче (7.40) один и тот же вектор zl используется во всех точках 0/<7, принадлежащих множеству S^l'p), в то время как в задаче (7.18) каждой

точке 0; соответствует свой вектор z . Алгоритм вычисления верхней границы оптимального значения целевой функции ДЭ301 [решения задачи (7.23)] имеет следующий вид.

Алгоритм 7.1

Шаг 1. Положить р = 1. Задать множество подобластей Г/А), / = 1, ...,Nk (число к - фиксировано, следовательно, число подобластей и их размеры остаются постоянными в этом алгоритме). Задать начальные значения z‘,(0 z,.(°), /°) G /j г / = i, ...,Nk ) соответствующих переменных. Также задать достаточно малое число 8 > 0.

Шаг 2. Создать начальное множество критических точек

для всех подобластей 7], / = 1,..., Nk

Шаг 3. Решить задачу (7.40) для определения нижней границы yic/,(<:) величины Пусть [d(pz'^pzl'(p) ] есть

решение этой задачи.

Шаг 4. Решить mNk задач

Обозначим через Ql,J^p) решение этой задачи при фиксированных [l,j ].

Шаг 5. Проверить условия

Если все неравенства выполняются, то решение задачи (7.23) получено, перейти к шагу 9, в противном случае перейти к шагу 6.

Шаг 6.

Шаг 7.

Шаг 8. Шаг 9.

Создать новые множества критических точек

Создать множества RIXp), / = 1,..., Nk , точек 0,,-/,(р), для которых условия (7.43) нарушаются

которые будут использоваться на следующей итерации. Положить р = р +1, перейти к шагу 3.

Создать и запомнить множество активных точек, соответствующих последней итерации

где р‘ - номер последней итерации этого алгоритма.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >