Материал: основы проектирования хим произв дворецкий
216Глава 7. НОВЫЕ ПОДХОДЫ К АППАРАТУРНО-ТЕХНОЛОГИЧЕСКОМУ ОФОРМЛЕНИЮ…
3)если разбить область Ξ на достаточно малые подобласти Ξi(ν) , то решение задачи (7.34) – (7.36) будет достаточно близко к решению задачи ДЗИП1:
lim CU ,(ν) = C1 ;
r(Ξi(ν) )→0 1
4) если размеры всех подобластей Ξi(ν) стремятся к нулю, то согласно свой-
ству 3 задача (7.34) – (7.36) стремится к ДЗИП1 и ограничения (7.39) превращаются в ограничения h(a, d, ξ) ≤ 0, ξ Ξ . Поэтому множество активных точек
S A(ν.P) задачи (7.37) – (7.39) стремится к множеству активных точек ДЗИП1.
Рассмотрим алгоритм вычисления верхней границы оптимального значения целевой функции ДЗИП1 (решения задачи (7.37) – (7.39)). Обозначим через
S2(kl , p) множество критических точек, принадлежащих подобласти Ξl(ν) , где p − номер итерации в алгоритме внешней аппроксимации решения задачи (7.37) – (7.39); ν – номер итерации в алгоритме решения задачи ДЗИП1.
Множество S2(kl , p) образуется автоматически при решении задачи (7.34) –
(7.36). Пусть S2(ν, p) = S2(ν,1, p) US2(ν,2, p) U...US2(ν,N, pν) .
В алгоритме используем решение вспомогательной задачи:
С1U L, (ν) = mini |
|
l |
∑γi C(a, d, zi , ξi ) ; |
(7.40) |
||
|
|
a,d , z , z |
|
i I1 |
|
|
g |
j |
(a, d, zi , ξi ) ≤ 0, j =1, ..., m, i I ; |
(7.41) |
|||
|
|
|
|
1 |
|
|
g(a, d, zl , ξl,q ) ≤ 0, |
ξl,q S2(ν,l, p) , l =1, ..., Nν . |
(7.42) |
||||
Задача (7.40) – (7.42) дает нижнюю границу оптимального значения целевой функции задачи (7.37) – (7.39). Сравним задачу (7.40) – (7.42) с задачей, дающей нижнюю границу оптимального значения целевой функции ДЗИП1 (см. задачу
(7.25) – (7.27)). В задаче (7.40) – (7.42) один вектор zl соответствует всем точкам ξl,q , принадлежащим множеству S2(ν,l, p) , в то время как в задаче (7.31) – (7.33)
каждой точке ξi соответствует единственный вектор zi . Приведем описание ал-
горитма вычисления верхней границы оптимального значения целевой функции ДЗИП1 (решения задачи (7.37) – (7.39)).
Алгоритм 7.4.
Шаг 1. Положим p =1 . Зададим множество подобластей Ξl(ν) (l =1, ..., Nν )
(число ν фиксировано, следовательно, число подобластей и их размеры остаются постоянными в этом алгоритме). Зададим начальные значения zi,(0) , zl,(0) , a(0) , d (0) (i I1, l =1, ..., Nν ) соответствующих переменных и достаточно малое число ε > 0 .
ДВУХЭТАПНОЕИНТЕГРИРОВАННОЕПРОЕКТИРОВАНИЕХТСВУСЛОВИЯХИНТЕРВАЛЬНОЙ… 217
Шаг 2. Сформируем начальное множество S2(ν,l,1) критических точек для всех
подобластей Ξl |
(l =1, ..., N1) |
|
|
|
|
|
S2(ν,l,1) ={ξl, j,(1) , |
j =1, ..., m : g j (a(0) , d (0) , zi,(0) , ξl, j,(1) ) > 0} , |
|
||||
где ξl, j,(1) есть решение задачи |
|
|
|
|
||
|
|
max |
g j (a(0) , d (0) , zl,(0) , ξ) . |
|
||
|
|
ξ Ξ(ν) |
|
|
|
|
|
|
l |
|
|
|
|
Шаг 3. Решим задачу (7.40) – (7.42) и определим нижнюю границу СUL,(ν) |
||||||
|
|
|
|
|
|
1 |
величины СU ,(ν) . Пусть [a( p) , d ( p) , zi,( p) , zl,( p) ] − решение этой задачи. |
|
|||||
1 |
|
|
|
|
|
|
Шаг 4. |
Решим |
mNν |
задач |
max |
g j (a( p) , d ( p) , zl,( p) , ξ) , |
где |
|
|
|
|
ξ Ξ(ν) |
|
|
Ξl(ν) = {ξ : ξL,l,(ν) ≤ ξ ≤ ξU ,l,(ν) }. |
|
l |
|
|
||
Обозначим через |
ξl, j,( p) решение этой задачи |
|||||
при фиксированных [l, j]. |
|
|
|
|
|
|
Шаг 5. Проверим выполнение условия |
|
|
|
|||
g j (a( p) , d ( p) , zl,( p) , ξl, j,( p) ) ≤ ε, |
j =1, ..., m; l =1, ..., Nν . |
|
||||
Если все неравенства выполняются, решение задачи (7.37) – (7.39) получено, перейти к шагу 9; в противном случае перейти к шагу 6.
Шаг 6. Создадим множества Rl,( p) (l =1, ..., Nν ) точек ξl, j,( p) , для которых
ограничения нарушаются: |
|
Rl,( p) |
={ξl, j,( p) : g j (a( p), d( p), zi,( p), ξl, j,( p) ) > 0, j =1, ..., m; l =1, ..., Nν}. |
Шаг 7. |
Сформируем новые множества критических точек |
|
S2(νl , p+l) = S2(νl , p) URl,( p) (l =1, ..., Nν ), |
которые будут использоваться на следующей итерации. |
|
Шаг 8. |
Положим p := p +1 и перейдем к шагу 3. |
Шаг 9. |
Сформируем и запомним множество активных точек |
SA(ν.P) ={ξl, j,( pˆ ) : g j (a( p), d( p), zi,( p), ξl, j,( pˆ ) ) = 0, l =1, ..., Nν; j =1, ..., m }, |
|
где pˆ – есть номер последней итерации этого алгоритма.
Перейдем к описанию алгоритма решения ДЗИП1 в следующей постановке:
С1 |
= mini |
∑γiC(a, d, zi , ξi ) ; |
(7.43) |
|
a, d , z |
i I1 |
|
218 Глава 7. НОВЫЕ ПОДХОДЫ К АППАРАТУРНО-ТЕХНОЛОГИЧЕСКОМУ ОФОРМЛЕНИЮ…
g(a, d, zi , ξi ) ≤ 0, i I |
; |
(7.44) |
1 |
|
|
max h(a, d, ξ) ≤ 0 . |
|
(7.45) |
ξ Ξ |
|
|
Задача (7.43) – (7.45) имеет вид задачи полубесконечного программирования и для ее решения можно использовать алгоритм внешней аппроксимации.
Вначале рассмотрим упрощенную задачу полубесконечного программирования:
|
|
= min C(x) ; |
(7.46) |
С |
|||
|
|
x X |
|
max g j (x, ξ) ≤ 0; j =1, ..., m , |
(7.47) |
||
ξ Ξ |
|
||
где Ξ = {ξ: ξL ≤ ξ ≤ ξU }. Преобразуя ограничения задачи с помощью соотноше-
ния max g(x) ≤ 0 g(x) ≤ 0 , x X , получим задачу
x X
С = min C(x) ,
x X
g j (x, ξ) ≤ 0, j =1, ..., m; ξ Ξ ,
в которой число поисковых переменных конечно, а число ограничений бесконечно. Введем понятие множества критических точек S ( p) ={ξi : ξi Ξ, i I ( p)},
где I ( p) − множество индексов точек ξi . Оно используется в алгоритме для по-
строения некоторой аппроксимации ограничений в задаче полубесконечного программирования (7.47).
Алгоритм внешней аппроксимации.
Шаг 1. Положим p =1 . Задаем начальное значение x(0) и начальное мно-
жество критических точек S (0) . Шаг 2. Решаем задачу
C( p) = min C(x) ; |
|
x X |
|
g j (x, ξi ) ≤ 0, j =1, ..., m; ξi S( p−1) . |
|
Пусть x( p) − решение этой задачи. |
|
Шаг 3. Решаем m задач |
|
max g j (x( p) , ξ) |
(7.48) |
ξ Ξ |
|
и пусть ξ(jp) ( j =1, ..., m) − решения этих задач.
ДВУХЭТАПНОЕИНТЕГРИРОВАННОЕПРОЕКТИРОВАНИЕХТСВУСЛОВИЯХИНТЕРВАЛЬНОЙ… 219
Шаг 4. Проверяем выполнение условий |
|
g j (x( p) , ξ(jp) ) ≤ 0, j =1, ..., m . |
(7.49) |
Если все эти условия выполняются, то решение найдено.
Шаг 5. Сформируем множество R( p) , которое содержит все точки ξ(jp) , в которых условия нарушаются:
R( p) = {ξ(jp) : g j (x( p) , ξ(jp) ) > 0, j =1, ..., m }.
Шаг 6. Сформируем новое множество критических точек
S ( p) = S ( p−1) UR( p) .
Шаг 7. Полагаем p = p +1 и переходим к шагу 2.
Этот алгоритм дает решение задачи (7.46)–(7,47), если операции на шагах 2 и 3 выполняются в глобальном смысле.
На каждой итерации этот алгоритм выполняет две основные операции. Первая операция связана с определением нижней границы целевой функции за-
дачи (7.46)–(7,47). Вторая операция связана с проверкой, является ли точка x( p) решением задачи (7.46)–(7,47). Здесь алгоритм решает задачу (7.48) m раз. Если условие (7.49) удовлетворяется, то решение задачи (7.46)–(7,47) найдено.
В противном случае точки ξ(jp) , в которых условия (7.49) нарушаются, добавля-
ются в множество S ( p) .
Существенный недостаток описанного алгоритма состоит в необходимости решения m задач (7.48) на каждой итерации. Можно заменить m задач максимизации (7.48) одной задачей максимизации функции F(g) :
max F(g) ,
|
ξ |
|
|
F(g) = |
|
m |
|
1 ln ∑eρg j , |
|||
|
ρ |
|
|
|
|
j =1 |
|
где ρ – некоторый параметр. При этом установлено, что F(x, ρ) ≥ max (g j (x)), |
|
|
j |
ρ ≥ 0 , lim |
F(x, ρ) → max (g j (x)) . |
ρ→∞ |
j |
Теперь вернемся к решению задачи (7.43) – (7.45). Она имеет вид задачи полубесконечного программирования и для ее решения можно использовать описан-
ный выше алгоритм внешней аппроксимации. Поскольку max h(a, d, θ) = χ1(a, d ) ,
ξ Ξ
то на каждой итерации необходимо вычислять функцию гибкости χ1(a, d) (шаг 3 алгоритма внешней аппроксимации).
220 Глава 7. НОВЫЕ ПОДХОДЫ К АППАРАТУРНО-ТЕХНОЛОГИЧЕСКОМУ ОФОРМЛЕНИЮ…
Совокупность аппроксимационных точек ξi , i I |
1 |
, обозначим через S1, |
|
|
|
а множество критических точек на ν-м шаге – через S2(ν) |
={ξi : i I2(ν)} . |
|
Алгоритм 7.5. |
|
|
Шаг 1. Положим ν =1. Задаем множество аппроксимационных точек S1, на- |
||
чальное множество критических точек S2(0) , начальные приближения a(0) , d (0) и
достаточно малое число ε > 0 .
Шаг 2. Решаем задачу (7.28) – (7.30) для определения нижней границы С1L,(ν) оптимального значения величины C1 . Пусть a(ν) , d (ν) − решение этой задачи.
Шаг 3. Находим значение χ1(a(ν) , d (ν) ) и пусть ξ(ν) – решение этой задачи.
Шаг 4. Если выполняется условие χ1(a(ν) , d (ν) ) ≤ 0 , то решение найдено.
В противном случае находим точку ξ(ν) , для которой нарушаются ограничения g j (a(ν) , d (ν) , ξ(ν) ) > 0, j =1, ..., m , и переходим к шагу 5.
Шаг 5. Образуем новое множество критических точек S2(ν+1) , добавляя точ-
ку ξ(ν) к множеству S2(ν) : S2(ν+1) = S2(ν) U{ξ(ν) }. Шаг 6. Полагаем ν = ν +1 и переходим к шагу 2.
Для вычисления значения χ1(a(ν) , d (ν) ) функции гибкости можно использовать метод ветвей и границ. Можно использовать на шаге 3 следующее прибли-
~ |
(a |
(ν) |
, d |
(ν) |
) |
значения χ1(a |
(ν) |
, d |
(ν) |
) : |
|
|
|
|
|
|||||||
жение χ1 |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
U ,( |
ν) |
, |
|
|
|
|
если |
|
|
U ,(ν) |
< 0 ; |
|
|
|
|
|
|
|
|
|
|
|
χ |
|
|
|
|
|
|
|
χ |
|
||||
|
|
|
|
|
|
|
|
|
1 |
|
χ1U ,(ν) + χ1L,(ν) |
|
|
1 |
|
|
||||||
|
~ |
(a |
(ν) |
, d |
(ν) |
|
|
|
|
U ,(ν) |
L,(ν) |
|
||||||||||
|
|
|
|
|
||||||||||||||||||
|
χ1 |
|
|
|
|
) = χ1 = |
|
|
|
|
|
|
, если |
|
χ1 |
− χ1 |
< ε ; |
|||||
|
|
|
|
|
|
|
2 |
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L,(ν) |
|
|
||
|
|
|
|
|
|
|
|
|
L,(ν) |
, |
|
|
|
|
если |
χ |
≥ ε , |
|
||||
|
|
|
|
|
|
|
|
|
χ |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
1 |
|
|
||
где χU ,(ν) , |
χL,(ν) |
|
являются |
|
|
верхней |
и нижней границей функции гибкости |
|||||||||||||||
1 |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
χ (a(ν) , |
d (ν) ) . В случае использования метода ветвей и границ величина χU ,(ν) |
||||||
1 |
|
|
|
|
|
|
1 |
определяется по формуле |
χ1U (a, d ) = min max max g j (a, d, z, ξ) , в которой на |
||||||
|
|
|
z Z j J |
ξ Ξ |
|
|
|
каждой итерации величины |
χU ,(ν) известны для каждой подобласти. |
Величина |
|||||
|
|
|
1,i |
|
|
|
|
χL,(ν) получается с помощью формулы χL,(ν) (a, d) = max χL |
. Заметим, что если |
||||||
1 |
|
|
1 |
i |
1,i |
|
|
|
|
|
|
|
|
|
|
условие |
χU ,(ν) ≤ 0 |
выполняется, то тем |
более выполняется |
условие |
|||
|
1 |
|
|
|
|
|
|