Дворецкий С.И. Компьютерное моделирование и оптимизация технологических процессов и оборудования
Подождите немного. Документ загружается.
Перепишем задачу (4.29) – (4.31) в терминах А-задач стохастического программирования: требует-
ся найти m -мерный вектор постоянных величин ),...,,(
**
2
*
1
*
m
ααα=α , векторы конструктивных
*
α
d
и
управляющих
*
α
z переменных такие, что
},),,(),,({minmin),(
1
,
**
JjzdgzdCzdC
jj
k
K
k
k
zd
∈α≤θθγ=
∑
=
Α∈α
αα
,
(4.32)
где },]0),,([,{ ρ≥≤θ∀α=Α
ααθ
zdgBep
jj
(4.33)
где
k
γ – веса, которые присвоены каждой точке
∑
=
=γθ
K
k
k
k
1
1, . Весовые коэффициенты могут быть ин-
терпретированы как вероятности того, что вектор неопределенных параметров θ принимает значения
)(,))(,
,
θθθθ=θθ
∫
PdP
zd
T
k
– плотность распределения случайной величины
θ
.
Идея такого подхода, в сущности, очень проста. Поясним ее на примере одномерной задачи стохас-
тического программирования с одним ограничением 0),(
≤
θ
zg . На рис 4.4, a заштрихована недопусти-
мая область ограничения. Пусть соотношение между целевой функцией )},({ θ
θ
zCM и ),(
θ
zg такое, как
показано на рис. 4.4, б. Следует заметить, что такое соотношение (кроме, конечно, экзотических случа-
ев) в оптимизационных задачах химической технологии бывает всегда, т.е. наиболее предпочтительные
значения целевой функции лежат в недопустимой области (рис. 4.4), поскольку в противном случае ог-
раничение было бы неактивным и его не следовало бы учитывать. В этом случае решение
z
′
традици-
онной задачи оптимизации достигается при 0),( =θ
′
zg . Очевидно, при реализации этого решения
z
′
зна-
чения ),( θ
′
zg будут иметь случайный разброс вследствие наличия случайной величины θ . На рис 4.4, в
показан этот разброс, который может имитироваться на вероятностной модели ),( θ
′
ℑ z .
В зависимости от вхождения случайной величины в функцию ),(
θ
′
zg закон распределения этой
функции может изменяться. Следовательно, эта вероятность может быть как меньше, так и больше 0,5.
Таким образом, при решении традиционной задачи при θ=θ мы даже не знаем, какова вероятность нару-
шения технологических ограничений.
В сформулированной выше задаче стохастической оптимизации мы требуем, чтобы эта вероятность
была меньше, чем некоторая заданная величина
зад
1
ρ
−
, где
зад
ρ
– заданное значение вероятности выпол-
нения ограничений.
Идея А-задач стохастического программирования заключается в следующем: исходное ограничение
задачи заменяется на ограничение вида
α
≤
α
),(zg , где 0
<
α
, т.е. исходное ограничение как бы ужесто-
чается (рис. 4.4, г). После этого решается детерминированная задача оптимизации с новыми ограниче-
ниями
}),(),({min
1
α≤θθ zgzC
z
.
При этом решение задачи
z
′′
будет соответствовать тому, что технологические ограничения ),( θ
′′
zg
будет равным
1
α (рис. 4.4, г). Соответственно, вероятность нарушения ограничения уменьшается по
сравнению с
1
ρ , т.е.
12
ρ<ρ , а значение целевой функции возрастает (рис. 4.4, б). Таким образом, мы при-
близились к оптимальному решению задачи, которое изображено на рис. 4.4, д. Отметим, что при выпол-
нении
a)
в)
б)
д)
г)
),(
θ
zg
g
g
g
g
{}
),(
θ
θ
zCM
)(
g
P
)(
g
P
)
(
g
P
0
0
0
0
∫
∞
==
0
11
)(
ρ
dggPS
0),(
=
′
θ
zg
)(
1212
ρ
ρ
<
<
S
S
0
1
<
α
**
),(
α
θ
=
zg
зад
S
ρ
ρ
−
=
=
1
33
Рис. 4.4 Геометрическая иллюстрация идеи решения А-задачи
стохастической оптимизации
этой процедуры мы не вычисляли вероятность выполнения (нарушения) ограничения на каждом шаге
поиска
*
z
. Вычисление ]0),([ ≤θ
θ
zgBep производится в оптимальной точке
*
z
для того, чтобы проверить
выполнение условия
зад
]0),([ ρ≥≤θ
θ
zgBep . В том случае, если эти условия не выполняются, выбирается
новое число
0
12
<α<α и вновь решается детерминированная задача оптимизации с ограничением
2
),( α≤θzg . Процедура продолжается до тех пор, пока не будет найдено такое
*
α , при котором
технологическое ограничение 0),(
≤
θ
zg выполняется с заданной вероятностью т.е.
зад
]0),([ ρ≥≤θ
θ
zgBep или
зад3
1 ρ
−
≤ρ .
Следует заметить, что возможность применения метода А-задач стохастического программирова-
ния должна всегда доказываться либо аналитическим доказательством выполнения достаточных усло-
вий, либо вычислительным экспериментом, подтверждающим выполнение достаточных условий.
В данном исследовании мы опираемся на результаты наших работ [59, 60], в которых сформулиро-
ваны достаточные условия, которым должны удовлетворять функции ),,( θzdg
j
,
]0),,([
≤
θ
θ
zdgBep
j
и при выполнении которых решение задачи (4.32), (4.33) –
)),(,,(
****
αααα
zdCzd
– будет являться реше-
нием задачи (4.29) – (4.31).
В соответствии с методом А-задач стохастической оптимизации нами разработан следующий алго-
ритм решения задачи (4.32), (4.33) [59].
Алгоритм 2.
Шаг 1. Задается начальное значение 0
=
ν
и вектора ),...,,(
)(
)(
2
)(
1
)( ν
νν
ν
ααα=α
m
.
Шаг 2. Методом последовательного квадратичного программирования решается задача НЛП
)),,(,,(min),(
1
,
k
K
k
k
zd
zdyzdCzdC θγ=
∑
=
αα
;
(4.34)
при связях
),,(
k
zdy θℑ= ;
(4.35)
и ограничениях
.,1,,0,)),,(,,(
)()(
KkJjzdyzdg
jj
k
j
=∈<αα≤θ
νν
(4.36)
Шаг 3. В точке (
),
)0()0(
αα
zd
, которая является решением задачи (4.34) – (4.36), вычисляются вероят-
ности выполнения ограничений с использованием имитационной модели
),,( θℑ= udy
и проверяется выполнение условий
JjyudgBep
j
∈ρ≥
≤
θ
,}0),,({
.
Шаг 4. Если вероятностные ограничения не выполняются, т.е. Λ∉α
ν)(
, включается алгоритм входа
в допустимую область Λ . Простейшим алгоритмом такого типа является уменьшение
)(ν
α
j
для нару-
шенных ограничений. Далее число
ν
увеличивается на 1, т.е. 1
+
ν
=
ν
и следует переход к шагу 2.
Шаг 5. Если вероятностные ограничения выполняются, то вектор
*
α находим из решения внешней
А-задачи оптимизации
),(min),(
**
αα
Λ∈α
αα
= zdCzdC .
(4.37)
В общем случае задача (4.37) может быть решена подходящим методом нелинейного программиро-
вания. Однако нами применялись простейший алгоритм коррекции вектора Λ∈α путем увеличения его
компонентов на величину
),]0)([(
)(
ρ−≤•λ=α∆
θ
ν
jj
gBep
где
)(ν
λ – шаг коррекции на
ν
– ой итерации, подбираемый опытным путем. Поиск
*
α прекращается,
если
j
α∆ для
j
∀ становится меньше заранее заданного малого числа
ε
(точность поиска
*
α
).
Вычисление вероятностных интегралов производится стандартными методами (Монте-Карло, на
аппроксимирующей сетке).
Задача 2. Имеются конструктивные и управляющие переменные. На этапе эксплуатации неопреде-
ленные параметры могут быть определены в некоторый момент времени и управляющие переменные
могут быть использованы для обеспечения выполнения ограничений.
Для этого случая использовать в качестве критерия выражение
{
}
),(
*
θ
θ
dCM , где
,,0),,(),,(min),(
*
JjzdgzdCdC
j
z
∈≤θθ=θ
которое мы применяли для задачи с жесткими ограничениями,
нельзя. Это связано с тем, что сам вид этого критерия предполагает выполнение всех ограничений при
всех θ из заданной области, т.е. жестким образом. Построим для этого случая критерий оптимизации.
Обозначим через
T
ˆ
множество значений
θ
из заданной области, при которых могут быть выполнены
ограничения задачи и
зад
]
ˆ
[ ρ≥∈θ
θ
TBep . Тогда в критерии оптимизации для исходного T
ˆ
∈θ переменную
z
следует выбирать из условия минимума ),,(
θ
zdC при условии выполнения ограничений
,,0),,( Jjzdg
j
∈≤θ
а при T
ˆ
∉
θ
либо просто из условия минимизации ),,(
θ
zdC , либо из условия миними-
зации функции, учитывающей величину ),,(
θ
zdC и штраф за нарушение ограничений
0),,( ≤θzdg
j
.
При этом будем использовать следующие обозначения:
*
,0),,,(maxmax),,(),,(
ˆ
*
JjzdgAzdCzdC
j
Jj
∈
θ+θ=θ
∈
,
(4.38)
где
А
– штрафной коэффициент;
*
J – множество индексов ограничений, за нарушение которых берется
штраф.
В этом случае задача оптимального проектирования может быть записана следующим образом:
)),()((min)(min
21
dCdCdC
dd
+=
θθ
∈≤θθ=
∫
dPJjzdgzdCdC
T
j
z
)(,0),,(),,(min)(
ˆ
1
;
,)(),,(
ˆ
min)(
ˆ
\
2
θθ
θ=
∫
dPzdCdC
TT
z
(4.39)
где
)(
ˆ
•C
определяется из (4.38) при
*
Jj ∈
;
∈θ≤θθ==
∈
TzdgdTT
j
Jj
z
,0),,(maxmin:)(
ˆˆ
,
(4.40)
зад
]
ˆ
[ ρ≥∈θ TBep .
(4.41)
Отметим, что если существует такое d , что 0),,(maxminmax
≤
θ
∈∈θ
zdg
j
Jj
z
T
при
1
зад
→ρ
имеем TT →
ˆ
и в
пределе при 1
зад
=ρ задача (4.39) – (4.41) переходит в двухэтапную задачу с жесткими ограничениями.
Решение двухэтапной задачи оптимизации (4.39) – (4.41) гораздо сложнее одноэтапной задачи
(4.29) – (4.31) и для ее решения также будем использовать метод дискретизации критерия для получе-
ния дискретного аналога задачи (4.39) – (4.41). С помощью квадратурной формулы функцию
∈≤θθ=θ
θ
JjzdgzdCdCM
j
z
,0),,(),,(min),(
*
можно приближенно заменить на функцию
{}
),,(),(
*
*
1
i
Ii
i
dCdCM θγ=θ
∑
∈
θ
где
i
θ – аппроксимационные точки;
1
I – множество индексов аппроксимационных точек.
Обозначим через
i
z
значение вектора
z
, являющиеся решением задачи
JjzdgzdCdC
j
z
∈≤θθ=θ ,0),,(),,(min),(
*
,
при
i
θ=θ .
Тогда
{
}
JjzdgzdCdC
ii
j
ii
z
i
Ii
i
i
Ii
i
∈≤θθγ=θγ
∑∑
∈∈
,0),,(),,(min),(
11
*
.
(4.42)
Поскольку под знаком суммы задачи оптимизации зависят каждая от своих поисковых переменных,
операции суммирования и минимизации можно поменять местами, и задача (4.39)-(4.41) может быть
представлена в следующем виде
[]
+
∈≤θθ
∑
∈
1
,0),,(),,(minmin
Ii
ii
j
ii
z
d
JjzdgzdC
i
∈θ+θ+
∑
∈
∈
2
*
),0),,,(max(max),,(min
Il
j
Jj
ll
z
JjzdgAzdC
l
,
зад
]
ˆ
[ ρ≥∈θ TBep .
или
[]
θ+θ+θ
∑∑
∈∈
∈
∈∈
12
21
)0),,,((max),,(),,(min
,,,,
IiIl
j
Jj
llii
IlIizzd
zdgAzdCzdC
li
;
(4.43)
при ограничениях
;,,0),,(
1
IiJjzdg
ii
j
∈∈≤θ
и
(4.44)
зад
]
ˆ
[ ρ≥∈θ TBep .
(4.45)
Решение сформулированной задачи возможно с использованием эффективных методов решения за-
дач нелинейного программирования и имитационного моделирования.
Нами разработан алгоритм решения задачи (4.42) – (4.45), базирующийся на методе имитационного
моделирования [59].
Задача 3. Имеются конструктивные и управляющие переменные. Вектор неопределенных парамет-
ров состоит из двух подвекторов
1
θ и
2
θ ( ),(
21
θθ=θ ). В подвектор
1
θ входят параметры, которые могут
быть только определены на стадии эксплуатации процесса, в подвектор
2
θ – параметры, имеющие не-
определенности на этапе эксплуатации те же, что и на этапе проектирования. Пусть при этом
11
T∈θ и
22
T∈θ .
Эта задача в большей степени соответствует реальным задачам проектирования, поскольку внешние
случайные факторы всегда будут иметь место не только на стадии проектирования, но и на стадии эксплуа-
тации производства. Математическая постановка задачи имеет вид:
[]
()
()
)
,)(0;0),,,(maxmax
),,,((min)(
),0),,,(),,,((min(min
1121
зад
ˆ
\
2111
зад
21
ˆ
21
2
*
2
22
θθ
≤θθ−ρ+
+θθ+θθ×
×∈ρ≥≤θθθθ
θ
∈
θ
θθ
∫
∫
dPzdgBepA
zdCMdP
JjzdgBepzdCM
j
Jj
TT
z
z
j
T
z
d
(4.46)
[]
[]
∈θ≤≤θθ−ρθ=
θ
∈
1121
зад
1
,00),,,(maxmin:
ˆ
2
*
TzdgBepT
j
Jj
z
,
(4.47)
где
A
– штрафной коэффициент;
*
J – множество индексов ограничений, за нарушение которых берется
штраф.
Здесь также отметим, что если существует Dd
∈
, при котором
[
]
(
)
00),,,(maxminmax
21
зад
2
11
≤≤θθ−ρ
θ
∈
∈θ
zdgBep
j
Jj
z
T
,
то существует
{}
∅≠d , при котором
TT =
ˆ
и
0)()(min
11
ˆ
\
2
=θθ•
θ
∫
dPM
TT
z
.
При этом сформулированная задача (4.46), (4.47) переходит в двухэтапную задачу с жесткими огра-
ничениями.
Задача 4. Имеются конструктивные и управляющие переменные. На этапе эксплуатации ХТП об-
ласть неопределенных параметров та же, что и на этапе проектирования. Этот случай соответствует за-
даче проектирования ХТП, когда на этапе эксплуатации область неопределенных параметров не может
быть уточнена.
Эта задача может быть сформулирована (в отличие от задачи 1) следующим образом):
{
}
),,(min
,
*
θ=
θ
zdCMC
zd
,
при условии
0),,(maxmax ≤θ
θ
zdg
j
j
или
.,0),,(max Jjzdg
j
∈≤θ
θ
Упростим сформулированную задачу. Для этого заменим математическое ожидание с помощью квад-
ратурной формулы некоторой суммой
{}
),,(),,(
)(
1
i
i
Il
zdCzdCM θν≈θ
∑
∈
θ
,
где
i
ν – весовые коэффициенты, ,1
1
∑
∈
=ν
Ii
i
1
I – множество аппроксимационных точек в области
T
.
Совокупность точек
1
)(
, Ii
i
∈θ , будем обозначать через
1
S , а множество критических точек на
ν
-ом ша-
ге – через
{
}
)(
2
)(
)(
2
:
νν
∈θ= IjS
j
.
Алгоритм 3.
Шаг 1. Положим 0=ν . Выбираем совокупность аппроксимационных точек
1
S и начальную сово-
купность критических точек
)(
2
ν
S .
Шаг 2. Решаем задачу
∑
∈
θγ
1
),,(min
)(
,
Ii
i
i
zd
zdC ;
)(
2
)(
;,1,0),,(
ν
∈=≤θ Iimjzdg
i
j
и определяем
)()(
,
νν
zd .
Шаг 3. Решаем m-задач
mjzdg
i
i
T
,1),,,(max
)()(
=θ
νν
∈θ
и определяем m точек mi
i
,1,
)*(
=θ .
Шаг 4. Образуем множество
{
}
0),,(:
)*()()()*()(
>θθ=
ννν i
j
i
udgR .
Если это множество пустое, то решение задачи получено. В противном случае перейдем к шагу 5.
Шаг 5. Определим
.
)(
)(
2
)1(
2
ν
ν+ν
∪= RSS
Положим 1+ν=ν и переходим к шагу 2.
Характерной чертой алгоритма 3 является увеличение числа критических точек на каждом шаге,
соответственно увеличивается число ограничений. Это является определенным недостатком, поскольку
в некоторых случаях при большом числе критических точек число ограничений может стать слишком
большим.
Остановимся подробнее на шаге 3. Как правило, характер функций
j
g неизвестен. В этом случае
можно использовать такой подход. Предполагаем на первом этапе, что функции
j
g выпуклы. В этом
случае решение задачи
mjzdg
i
i
T
,1),,,(max
)()(
=θ
νν
∈θ
.
находится в одной из вершин параллелепипеда T [42]. В начальное множество критических точек
)0(
2
S
включается некоторое количество угловых точек куба
T
, а на шаге 3 рассчитываются значения функ-
ций mjzdg
i
i
,1),,,(
)()(
=θ
νν
во всех угловых точках куба
T
, не принадлежащих множествам
)(
2
ν
S и
1
S . Сре-
ди этих точек выбираются
m
точек, в которых функции mjzdg
i
i
,1),,,(
)()(
=θ
νν
принимают наибольшие
значения. Далее определим множество критических точек
)(
)(
2
)1(
2
ν
ν+ν
∪= RSS
и переходим к шагу 2 алго-
ритма 2.
Задача 5. Имеются конструктивные и управляющие переменные. На этапе эксплуатации неопреде-
ленные параметры могут быть определены в каждый момент времени. Для обеспечения выполнения ог-
раничений Jjzdg
i
∈≤θ ,0),,( могут быть использованы конструктивные и управляющие переменные.
Для этого случая условие гибкости (работоспособности) можно записать в виде
]0),,([, ≤θ∈∀∃∈θ∀ zdgJjdzT
j
или
.0),,(maxminmax)(
,
≤θ=χ
∈∈θ
zdgd
j
Jj
dz
T
Изменение конструктивных переменных гибкого аппарата на стадии эксплуатации ХТП возможно
за счет его модульно-блочной структуры. Тогда оптимизационная задача в условиях неопределенности
на стадии проектирования будет иметь вид
θ=
θ
),,(min
,
*
zdCMC
zd
,
при условии (4.48).
Используя квадратурную формулу, функцию
{
}
•
θ
M можно приближенно заменить выражением
{
}
,),,(),,(
1
**
∑
∈
θ
θν≈θ
Ii
i
i
zdCzdCM
где
i
ν – весовые коэффициенты;
i
θ – аппроксимационные точки;
1
I – множество индексов аппроксима-
ционных точек.
Операции суммирования и минимизации можно поменять местами и задача может быть представ-
лена в следующем виде
,),,(min
1
,
*
∑
∈
θν=
Ii
iii
i
zd
zdCC
ii
при выполнении условии гибкости и JjIizdg
iii
j
∈∈≤θ ,,0),,(
1
.
Сформулированная задача также как и задача 4 относится к одноэтапным задачам оптимизации и
может быть решена с помощью алгоритма 3.
Задача 6. Формулировка этой задачи та же, что и задачи 2, за исключением того, что условие гиб-
кости (работоспособности) проекта ХТП записывается в логической форме
(
)
{
}
]0),,([ ≤θ∈∀∃θ∀ zdgJjz
j
или с учетом эквивалентных соотношений
;0)(0)(max ≤∀⇔≤ zgzzg
z
;0)(0)(max ≤
∃
⇔≤ zgzzg
z
в виде
0),,(maxminmax)( ≤θ=χ
∈∈θ
zdgd
j
Jj
z
T
.
(4.48)
В сформулированной задаче существенно различаются роли конструктивных d и технологических
переменных
z
на двух этапах. Переменные d , выбранные на этапе проектирования, естественно, оста-
ются неизменными на всем этапе функционирования процесса. С другой стороны, технологические ре-
жимные (управляющие) переменные на этапе функционирования могут настраиваться в зависимости от
того, какие значения принимают параметры
θ
. Фактически в данном случае решается задача выбора
оптимальных коэффициентов запаса для конструктивных переменных, обеспечивающих выполнение
технологических ограничений при любых значениях параметров T
∈
θ
. В данном случае также
можно считать переменные d и
z
равноправными и, используя одноэтапную стратегию, решить задачу.
Однако это делать невыгодно, поскольку мы неявно предполагаем, что один раз найденные на этапе
проектирования режимные переменные остаются затем неизменными независимо от того, какие
фактические значения примут параметры
θ
. Это может привести в излишне большим коэффициентам
запаса. В то же время использование возможности изменять параметры
z
(с помощью системы
управления) на этапе функционирования процесса "облегчает" переменным d удовлетворять
ограничениям, что, в свою очередь, позволит уменьшить коэффициенты запаса.
Двухэтапную задачу оптимального проектирования можно записать в виде
{
}
JjzdgzdCMC
j
zd
∈≤θθ=
θ
,0),,(),,(minmin
*
,
при ограничениях (4.48).
Используя прием дискретизации, перепишем последнюю задачу в виде
∑
∈
θν
1
)(
),,,(min
)()(
,
Il
ii
i
zd
zdC
l
(4.49)
;;,1,0),,(
1
)()(
Iimjzdg
ii
j
∈=≤θ
(4.50)
0),,(maxminmax)( ≤θ=χ
∈
∈
∈θ
zdgd
j
Jj
Zz
T
.
Решение задачи (4.48) – (4.50) прямыми методами не представляется возможным, поскольку вычис-
ление )(dχ в каждой точке может привести к очень большим объемам вычислений. В связи с этим здесь
будет рекомендована итерационная процедура, основанная на идеях метода "ветвей и границ" [61] и
обеспечивающая приближение значений целевой функции (4.49). При этом не требуется непосредст-
венно вычислять величину )(dχ .
В дальнейшем нам потребуются следующие два соотношения:
),(minmax),(maxmin yxfyxf
x
yy
x
≥ ;
(4.51)
),(maxmax),(maxmax yxfyxf
xyyx
= ,
(4.52)
где y
x
, – векторы дискретных или непрерывных переменных. Последнее соотношение является оче-
видным.
Введем функцию
).,,(max),,( θ=θϕ
∈
zdgzd
j
Jj
Тогда величина
)(dχ имеет вид
).,,(minmax)( θϕ=χ
∈θ
zdd
z
T
В соответствии с соотношением (4.51) имеем
)(),,(maxmin),,(minmax)( dzdzdd
U
T
zz
T
χ=θϕ≤θϕ=χ
∈θ∈θ
,
(4.53)
где
),,(maxmaxmin),,(maxmaxmin θ=θ=χ
∈θ∈∈∈θ
zdgzdg
j
TJj
z
j
JjT
z
U
.
Введем обозначение
),,,(max),(
ˆ
θ=ϕ
θ
zdgzd
jj
отсюда
).,(
ˆ
maxmin)( zdd
j
j
z
U
ϕ=χ
Известно, что задача вычисления )(d
U
χ может быть сведена к следующей
.),(
ˆ
min
,
α≤ϕα
α
zd
j
z
(4.54)
Из (4.53) следует, что если ,0)( ≤χ d
U
то 0)(
≤
χ
d . Поэтому условие
0)( ≤χ d
U
является достаточным условием допустимости (работоспособности) проекта, определяемого вектором
конструктивных параметров d .
Для определения величины
)(d
U
χ
необходимо решить задачу (4.54), тогда
*
)( α=χ d
U
, где
*
α – опти-
мальное значение переменных α .
Аналогично можно показать, что
),(),,(maxminmax)( dzdgd
j
Jj
Zz
T
χ
≥
θ
=χ
∈
∈
∈θ
где
),,(minmaxmax),,(minmaxmax)( θ=θ=χ
∈
∈θ∈
∈
∈∈θ
zdgzdgd
j
Zz
TJj
j
Zz
JjT
L
.
Отсюда следует, что если
,0)( ≥χ d
L
то и 0)( ≥χ d . Поэтому это условие является достаточным условием недопустимости (неработоспособно-
сти) проекта с вектором d . Для определения )(d
χ
необходимо решить
m
задач вида
.,1),,,(minmax mjzdg
j
Zz
T
∈θ
∈
∈θ
Каждая из этих задач эквивалентна следующей
.),,(minmax
,
α≤θα
∈
αθ
zdg
j
Zz
Таким образом, имеем
)()()( ddd
UL
χ≤χ≤χ .
(4.55)
Следовательно, вычислив значения
L
χ и
U
χ , получим оценки снизу и сверху величины
χ
–
критерия гибкости (работоспособности) Гроссмана.
Проанализируем физический смысл условия
.0)( ≤χ d
U
Будем искать такой вектор
z
, который обеспечивает допустимость вектора d при любых
θ
:
.0),,(,,
≤
θ
∀
θ
∀
∃ zdgz
jj
Таким образом, используя этот критерий, мы ищем единственный вектор
z
, который обеспечивает
допустимость вектора d при любых значениях
θ
. Напомним, что в критерии гибкости Гроссмана
)(d
χ
каждому значению θ соответствует свой вектор
z
, обеспечивающий допустимость вектора d .
Если разность
LU
χ−χ мала, то рассмотренный подход дает возможность оценить гибкость ХТП, в
противном случае необходима какая-либо регулярная процедура, позволяющая изменить эту разность.
Рассмотрим одну из этих процедур [61, 62]
Разобьем область
T
на N областей ).,1(, NiT
i
= Для каждой области определяем величину
).,,(maxmaxmin θ=χ
∈θ∈
∈
zdg
j
TJj
Zz
U
i
Для этого необходимо решить задачу
α
α,
min
z
,
(4.56)
.),,(max α≤θ
∈θ
zdg
j
T
i
Определим теперь величину
U
χ
следующим образом
).,,(maxmaxminmax θ=χ
∈θ∈
∈
zdg
j
TJj
Zz
i
U
i
Поскольку TT
i
⊂ , то имеет место неравенство
,
UU
i
χ≤χ
откуда
.max
UU
i
i
U
χ≤χ=χ
Далее можно показать, что
UU
χ≤χ≤χ
.
Следовательно, получена уточненная верхняя оценка критерия гибкости Гроссмана. Заметим, что
чем плотнее покрытие области T , тем ближе будет
U
χ к
χ
. Однако такой путь может приводить к ре-
шению большого числа задач (4.56). В связи с этим рассмотрим другой путь вычисления
)(dχ
. Для этого
представим критерий )(dχ в виде
),,(max)(
θ
ψ
=
χ
∈θ
dd
T
где
).,,(maxmin),(
θ
=
θ
ψ zdgd
j
j
z
Здесь вычисление
)(dχ
сводится к определению точки
*
θ , в которой функция ),(
θ
ψ d принимает
максимальное значение.
Для определения этой точки воспользуемся процедурой метода "ветвей и границ" [63]. Цель этой
процедуры будет состоять в том, чтобы разбивая область
T на все большее число подобластей
i
T , по-
стараться локализовать точку
*
θ .
Пусть на ν -ом шаге область
T
разбита на N областей
)()(
2
)(
1
)(
...:,1,
ννν
ν
ν
ν
∪∪∪==
N
i
TTTTNiT . Далее
выбирается одна из областей
)(ν
ν
k
T , которая в свою очередь разбивается на некоторое число областей.
Для простоты будем считать, что область
)(ν
ν
k
T делится на две области:
)1( +ν
S
T и )(
)1(
)1()(
)1( +ν
+νν
+ν
+=
ν
q
S
k
q
TTTT .
В качестве области
)(ν
ν
k
T берется та из областей ),1(,
)(
ν
ν
= NiT
i
, в которой с наибольшей вероятностью на-
ходится оптимальная точка
*
θ .
Вычислим для каждой области
)(ν
i
T величину
U
i
χ
),(max θψ≥χ
∈θ
d
i
T
U
i
.