3 / 14
исследования были проведены для широкого класса задач дискретной
оптимизации.
3.
Качественные исследования свойств задач дискретной опти-
мизации.
В ряде случаев результаты теории устойчивости могут быть
использованы для решения обратных задач, для табулирования ре-
шений множества задач, а также в задачах защиты информации и
робототехники.
4.
Решение прикладных задач.
Результаты теории устойчивости по-
зволяют, например, разработать методы защиты информации, строить
новые математические модели, в том числе и за счет параметризации
исходных данных, получать эвристические критерии оценки качества
моделей и т.д.
Последняя цель и является целью настоящей работы. В математи-
ческом моделировании возникают одновременно несколько различных
постановок задач, совокупность которых может быть единообразно
интерпретирована и проанализирована с позиции теории устойчиво-
сти.
Элементы теории устойчивости.
Изначально такой подход пред-
лагался для задач дискретной оптимизации, но оказалось, что его так-
же можно применить к задачам параметрического программирования,
вычислительной геометрии и математического моделирования. Пока-
жем на конкретных примерах тесную связь полученных результатов.
В простейшем виде схема выглядит так. Пусть
E
=
{
e
1
, . . . , e
m
}
—
некоторое множество,
D
m
=
{
t
1
, . . . , t
q
}
,
q >
1
— система подмножеств
множества
E
, называемых траекториями.
Элементам множества
E
приписаны веса
w
(
e
1
) =
a
1
, . . . , w
(
e
m
) =
=
a
m
. Пусть вектор
A = (
a
1
, . . . , a
m
)
, берется из пространства
<
m
.
На каждой траектории определяется функционал
τ
(
A
)
— длина траек-
тории при взвешивании вектора
A
. Например, линейный функционал
τ
(
A
) =
X
e
i
∈
τ
a
i
, или функционал задачи на “узкие места”
τ
(
A
) = max
e
i
∈
τ
a
i
.
Под задачей понимается тройка
(
E, D
m
,
A)
с определенным на
ней типом функционала. Пара
(
E, D
m
)
определяет “комбинаторику”
задачи. В связи с этим, если эта пара и функционал фиксированы, а ва-
рьируется лишь вектор
A = (
a
1
, . . . , a
m
)
в пространстве
<
m
(конфигу-
рационном пространстве), то получающуюся индивидуальную задачу
будем обозначать как Pr
A
.
Решениями задачи называются траектории, доставляющие экстре-
мум (например, минимум) функционалу (оптимальные траектории).
Множество номеров оптимальных траекторий задачи при взвеши-
вании вектора
А
обозначим через
ϕ
(A)
, длину оптимальной траекто-
рии —
m
(A)
, открытый шар в пространстве
<
m
с центром в векторе
A
и радиусом
Δ
—
S
Δ
(A)
.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 5 63