Материал: основы проектирования хим произв дворецкий

ДВУХЭТАПНОЕИНТЕГРИРОВАННОЕПРОЕКТИРОВАНИЕХТСВУСЛОВИЯХИНТЕРВАЛЬНОЙ… 221

χ1(a, d) > 0 .

Описанная модификация позволяет использовать в алгоритме внешней аппроксимации только верхнюю и нижнюю границы функции гибкости χ1(a, d)

вместо вычисления самой этой функции, что приводит к существенному уменьшению вычислительных затрат.

Далее рассмотрим метод разбиений и границ для решения ДЗИП1 [23, 24], представляющий двухуровневую итерационную процедуру (рис. 7.1).

Он состоит из следующих блоков:

1) вычисление верхней границы С1U ,(ν) (см. задачу (7.34) – (7.36)) целевой функции задачи

Рис. 7.1. Блок-схема метода разбиений и границ

222 Глава 7. НОВЫЕ ПОДХОДЫ К АППАРАТУРНО-ТЕХНОЛОГИЧЕСКОМУ ОФОРМЛЕНИЮ…

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

На нижнем уровне вычисляются верхняя С1U ,(ν) и нижняя С1L,(ν) границы.

Сформулируем правила разбиения области Ξ на подобласти Ξi(ν) (i =1, ..., Nν) . Прямой путь состоит в систематическом дроблении всех областей

на каждой итерации, пока все подобласти не станут достаточно малыми. Однако такая стратегия разбиения неэффективна, так как в этом случае размерность задач (7.31) – (7.33) и (7.37) – (7.39) достаточно быстро может стать очень высокой.

Рассмотрим более эффективный способ дробления, основанный на следую-

щем эвристическом правиле: на ν-й итерации дробиться будут только те из областей Ξi(ν) (i =1, ..., Nν ) , для которых соответствующие ограничения (7.35)

задачи (7.34) – (7.36) будут активны. Так как задача (7.37) – (7.39) эквивалентна задаче (7.34) – (7.36), то это эвристическое правило может быть сформулировано

следующим образом: на ν-й итерации подобласть Ξl(ν) дробится, если выполняется условие

j J max g j (a(ν) , d (ν) , zl,(ν) , ξ) = 0 ,

ξ Ξl

где J = (1, ..., m); [a(ν) , d (ν) , zl,(ν) ] − решение задачи (7.37) – (7.39).

Вработе [38] показано, что дробление подобластей с неактивными ограничениями бесполезно, а удаление активных ограничений в задаче оптимизации улучшает оптимальное значение целевой функции.

Вкачестве множества S2(ν) можно использовать все критические точки, по-

лученные при решении задачи (7.37) – (7.39) вычисления верхней границы целевой функции ДЗИП1. Однако в этом случае размерность задачи (7.31) – (7.33) может стать очень высокой. Необходимо выбирать это множество таким обра-

зом, чтобы нижняя граница C1L (a, d) была как можно ближе к оптимальному

ДВУХЭТАПНОЕИНТЕГРИРОВАННОЕПРОЕКТИРОВАНИЕХТСВУСЛОВИЯХИНТЕРВАЛЬНОЙ… 223

Следовательно, целесообразно выбрать множество S2(ν) следующим обра-

зом: S2(ν) = SA(ν.P) . При этом можно уменьшить число точек, используемых для формирования S2(ν) . Действительно, при Nν → ∞ все точки одной подобласти стягиваются в одну точку. Следовательно, во множество S2(ν) можно включать только одну активную точку из всех точек, принадлежащих подобласти Ξl(ν) .

~(ν) (ν)

Всвязи с этим образуем множество S A.P из множества S A.P следующим образом.

Вкаждой подобласти Ξl(ν) из всех активных точек SAl,.(Pν) оставим только одну,

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

224 Глава 7. НОВЫЕ ПОДХОДЫ К АППАРАТУРНО-ТЕХНОЛОГИЧЕСКОМУ ОФОРМЛЕНИЮ…

Шаг 3. Определим множество Q(ν) = {Ξl(ν) : l IQ(ν) } подобластей Ξi(ν) , которым соответствуют активные ограничения в задаче (7.34) – (7.36):

χ1U,l (a(ν) , d (ν) ) = 0, Ξl(ν) Q(ν) .

Шаг 4. Если Q(ν) пустое множество, то решение ДЗИП1 найдено, алгоритм

заканчивает свою работу.

Шаг 5. Если выполняется условие

С1U ,(ν−1) − С1U ,(ν) ≤ ε1 С1U ,(ν) ,

то решение ДЗИП1 найдено, алгоритм заканчивает свою работу. В противном случае проверяем выполнение условия

С1U ,(ν−1) − С1U ,(ν) ≤ ε2 С1U ,(ν) ,

и если оно нарушается, то переходим к шагу 8, в противном случае переходим к шагу 6.

Шаг 6. Находим нижнюю границу С1L,(ν) , решая задачу (7.31) – (7.33). Здесь

мы полагаем S2(ν) = SA(ν.P) (см. шаг 9 алгоритма 7.4). Шаг 7. Если выполняется условие

C1U ,(ν−1) −C1U ,(ν) ≤ ε1 C1U ,(ν) ,

то решение ДЗИП1 найдено, алгоритм заканчивает свою работу. Шаг 8. Если выполняется условие

r(Ξi(ν) ) ≤ δ2 , i =1, ..., Nν ,

то решение ДЗИП1 найдено, алгоритм заканчивает свою работу.

Шаг 9. Если выполняется условие r(Ξl(ν) ) ≤ δ1 , l =1, ..., Nν , то переходим к шагу 11.

Шаг 10. Сформировать множество L(ν) . Найти множество V (ν) подобластей Ξi(ν) , принадлежащих одновременно множествам L(ν) и Q(ν) , т.е.

V (ν) = L(ν) IQ(ν) .

Разбить каждую подобласть Ξl(ν) V (ν) на две подобласти таким образом,

ДВУХЭТАПНОЕИНТЕГРИРОВАННОЕПРОЕКТИРОВАНИЕХТСВУСЛОВИЯХИНТЕРВАЛЬНОЙ… 225

Шаг 11. Положим δ1 = δ1 / 2 и переходим к шагу 9.

Шаг 12. Положим ν = ν +1 и переходим к шагу 2. Алгоритм 7.6 позволяет получить локальный минимум.

Определение начального разбиения области Ξ на подобласти на шаге 1 является непростой задачей. Конечно, начальное разбиение может состоять из всей области Ξ . Однако в этом случае задача (7.34) – (7.36) может не иметь решения. В связи с этим на шаге 1 можно вычислять значение индекса гибкости γ1 ХТС.

Эта величина находится решением задачи

имеет решение. Множество подобластей, найденное решением задачи (7.53), (7.54), может быть использовано как начальное разбиение области Ξ

на подобласти Ξi(1) на шаге 1 алгоритма 7.6.

До сих пор мы предполагали, что аппроксимационные точки в дискретном варианте ДЗИП1 (см. задачу (7.55) – (7.57)) задаются пользователем, и что число этих точек невелико. В данном случае главной проблемой является вычисление значения критерия, т.е. вычисление многомерного интеграла. Для этого используются два подхода.

Первый подход основывается на использовании квадратурных формул Гаусса. Предположим для простоты изложения, что вектор ξ имеет только две

компоненты (т.е. область Ξ − прямоугольник); тогда, если все неопределенные параметры независимы, необходимо вычислить интеграл