Э.Н. Гордеев
2
и функционал задачи на узкие места:
( ) max .
i
i
e
A
a
Под дискретной оптимизационной задачей будем понимать тройку
(
E
,
D
n
,
A
) с определенным на ней типом функционала. Будем обозначать
через
Z
A
индивидуальную задачу массовой задачи (
E
,
D
n
,
A
), определяе-
мую путем задания вектора
A
.
Решениями задачи называются траектории, доставляющие экс-
тремум, например, минимум функционалу (оптимальные траекто-
рии). В указанную схему укладываются все задачи, так называемой,
комбинаторной оптимизации, в частности, все оптимизационные за-
дачи на графах, что подчеркивается выделением в определении зада-
ния множества
D
n
.
Множество номеров оптимальных траекторий задачи при взве-
шивании
A
обозначим через
(
A
), а длину оптимальной траектории
―
m
(
A
). Через
S
(
A
) обозначим открытый шар в
R
n
с центром в
A
и
радиуса
Под обратной задачей будем понимать тройку (
E
,
D
n
,
(
A
)). Ре-
шением обратной задачи будет матрица
A
, для которой заданный
набор траекторий
является множеством оптимальных траекторий
(или множество всех таких матриц
W
(
A
)). Будем обозначать через
Z
индивидуальную задачу массовой задачи (
E
,
D
n
,
(
A
)), определяемую
путем задания множества φ.
Пусть
R
0
= {
A
:
A
R
n
, |
(
A
)| =
m
} и в пространстве
R
n
задана нор-
ма. Назовем задачу
Z
A
-устойчивой, если для любого
R
n
выполняется условие
(
A
+
B
)
(
A
). Радиус устойчивости задачи
Z
A
,
A
R
0
, полагаем по определению равным нулю, в противном слу-
чае радиусом устойчивости назовем
sup
, где
sup
берется по всем
,
для которых
Z
A
является
-устойчивой. Обоснование, подробный
анализ введенных определений, а также исследование устойчивости
многих известных оптимизационных задач как с линейным, так и с
минимаксным функционалом при различных типах норм в
R
n
можно
найти, например, в [1–7].
Таким образом, радиус устойчивости задает предел возмущений
элементов весового вектора задачи
Z
A
, при которых не расширяется
множество оптимальных решений.
В [6] рассматривались задачи на матроидах и пересечении матро-
идов для случая чебышевской метрики в
R
n
. Для случая единствен-
ной оптимальной траектории формула для радиуса устойчивости при
некотором дополнительном условии получена в [5].
