4 / 14
Пусть
R
0
=
{
A : A
∈ <
m
,
|
ϕ
(A)
|
=
q
}
и в пространстве
<
m
задана норма. Назовем задачу
Pr
A
ε
-устойчивой, если для любого
B
∈ <
m
,
k
B
k
< ε
, выполняется условие
ϕ
(A +
B
)
⊆
ϕ
(A)
. Радиус
устойчивости задачи Pr
A
,
A
∈
R
0
, полагаем по определению равным
нулю, в противном случае радиусом устойчивости назовем
sup
ε
, где
супремум берется по всем
ε
, для которых радиус Pr
A
является
ε
-
устойчивым.
Обозначим радиус устойчивости задачи Pr
A
через
ρ
(A)
. Вектор
B
будем называть
возмущающим вектором
, или
возмущением
.
Обоснование, подробный анализ введенных определений, а также
исследование устойчивости многих известных оптимизационных за-
дач как с линейным, так и с минимаксным функционалом при различ-
ных типах норм в пространстве
<
m
можно найти, например, в работах
[1–5]. Таким образом, радиус устойчивости задает предел возмущений
элементов весового вектора задачи Pr
A
, при которых не расширяется
множество оптимальных решений.
Оказалось, что кроме задач дискретной оптимизации в описанную
выше схему укладываются многие задачи вычислительной геометрии,
а методика исследования устойчивости имеет содержательные и прак-
тически значимые последствия. Примеры этого подхода можно найти
в работах [6–8]. Допустимые решения задачи — некоторые геометри-
ческие объекты в некотором пространстве (пространство задачи). Эти
объекты и будут траекториями
D
m
=
{
τ
1
, . . . , τ
q
}
,
q >
1
. В индивиду-
альной задаче они описываются числовыми характеристиками через
координаты точек
E
=
{
e
1
, . . . , e
m
}
пространства задачи. Значения
указанных координат
A = (
a
1
, . . . , a
m
)
могут подвергаться возмуще-
нию. Под решением задачи понимается объект с определенными свой-
ствами. Если можно ввести понятие эквивалентности объектов и неко-
торую норму в конфигурационном пространстве, то возникает аналог
шара устойчивости, внутри которого решения задачи эквивалентны.
Следует отметить, что геометрия исходного пространства самой
задачи вычислительной геометрии и норма конфигурационного про-
странства различны. Кроме того, связь между траекториями и эле-
ментами
E
=
{
e
1
, . . . , e
m
}
не прямая, а опосредованная структурой
исходных данных.
Согласно изложенному, наблюдается единообразие подходов к
оценке устойчивости в оптимизационных и геометрических задачах.
Пусть элементы вектора
A
зависят от параметра
A(
t
) = (
a
1
(
t
)
, . . .
. . . , a
m
(
t
))
. Здесь норма конфигурационного пространства уже роли
не играет, а “близость” задач определяется близостью значений пара-
метра. Устойчивость задачи предполагает сохранение комбинаторики
ее решений при незначительных изменениях параметра. Для задачи
линейного программирования такая постановка является классиче-
ской, а методы решения параметрической задачи хорошо известны.
64 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 5