Э.Н. Гордеев
2
В [1–7] используются следующие терминология и обозначения.
Пусть
1
, ...,
m
E e
e
—
некоторое множество,
1
, ...,
m
q
D
1,
q
—
система подмножеств множества
E
, называемых
траекто-
риями
. Элементам из
E
приписаны веса
1
1
, ...,
m m
w e a
w e a
.
Пусть вектор
1
, ...,
m
a
a
A
берется из пространства
.
m
R
На каж-
дой траектории определяется функционал
A
—
длина траектории
при взвешивании
A
, например линейный функционал
.
j
j
e
a
A
(1)
Под дискретной оптимизационной задачей будем понимать тройку
,
,
m
E D
A
с определенным на ней типом функционала. Пара
,
m
E D
определяет «комбинаторику» задачи, поэтому, если эта пара и функ-
ционал фиксированы, а варьируется лишь вектор
1
, ...,
m
a a
A
в
,
m
R
то получаемую при этом индивидуальную задачу будем обозначать
через Pr .
A
Множество оптимальных траекторий задачи при взвешивании
A
обозначим через
A
.
Пусть
0
:
,
m
R
R
q
A A
A
и в пространстве
m
R
задана
норма. Назовем задачу Pr
A
ε
-
устойчивой
, если для любого вектора
,
m
R
В
,
В
выполняется условие
A В A
. Радиус
устойчивости задачи Pr
A
,
0
,
R
A
полагаем по определению равным
нулю, в противном случае радиусом устойчивости назовем
sup
, где
supremum берется по всем ,
для которых
Pr
A
является
-устойчивой.
Вышеупомянутый вектор
В
будем называть
возмущающим век-
тором
или
возмущением
.
Таким образом, радиус устойчивости задает предел возмущений
элементов весового вектора задачи Pr ,
A
при которых не расширяется
множество оптимальных решений.
В [6] рассматривались задачи на матроидах и пересечении матро-
идов для случая чебышевской метрики в
,
m
R
в [1]
—
метрика
1
l
.
В [9, 10] рассматривается задача максимизации веса оптимально-
го решения в рамках фиксированного бюджета. Эта постановка, по
сути, очень близка к анализу устойчивости, разработанному в [1–7],
но не эквивалентна ему.
Для случая чебышевской метрики результаты [9, 10] следуют
непосредственно из результатов работы [6]. В случае же метрики
1
l
