5 / 14
Для задач комбинаторной оптимизации она была предложена в рабо-
тах [5, 9].
Определение.
Параметрическая задача называется конечнознач-
ной на
[
a, b
]
, если существует такой набор интервалов
(
t
i
, t
i
+1
)
,
i
= 1
, . . . , N
−
1
, что
[
a, b
] =
{
a
} ∪ {
b
}
N
S
i
=1
{
t
i
}
N
−
1
S
i
=1
(
t
i
, t
i
+1
)
, и реше-
ние любой задачи в точке
t
∈
(
t
i
, t
i
+1
)
является ее решением на всем
интервале
(
t
i
, t
i
+1
)
,
i
= 1
, . . . , N
−
1
.
Интервалы в этом определении представляют собой аналоги обла-
стей устойчивости, а размер интервала — аналог радиуса устойчиво-
сти. В работе [9] проведен подробный анализ параметрических задач
оптимизации и получен критерий конечнозначности.
Пусть
ϕ
ij
(
t
) =
τ
i
(A(
t
))
−
τ
j
(A(
t
))
,
i, j
= 1
, . . . , q
. Множество этих
функций обозначим как
Φ
. Знак функции — это знаки “+”, “–” или “0”.
Точка
t
0
называется точкой перемены знака функции, если для любого
ε >
0
в любой
ε
-окрестности точки найдется точка
t
1
такая, что знаки
функции в этих точках разные.
Очевидно, что для задачи линейного программирования конечно-
значность обеспечивается. В работе [9] показано, что и для полиноми-
альной зависимости от параметра можно доказать конечнозначность
в случае линейного функционала и функционала на “узкие места”.
Получен ряд других достаточных условий конечнозначности, но они
имеют весьма специфический характер. Однако в случае этих функци-
оналов до сих пор неизвестен критерий (необходимое и достаточное
условие) конечнозначности, который бы формулировался только на
базе аналитических свойств функций
A(
t
)
. Приведем пример указан-
ного общего критерия, в котором необходимо учитывать структуру
множества траекторий задачи.
Содержательный смысл критерия состоит в возможности исключе-
ния из рассмотрения некоторого подмножества траекторий в окрест-
ности некоторых точек на интервале
[
a, b
]
. Этими точками являются
“точки сгущения точек перемен знака”, точки в полуокрестности ко-
торых некоторая функция
ϕ
ij
(
t
)
меняет знак бесконечное число раз.
Если удается установить, что в этой окрестности ни одна из траек-
торий
τ
i
(A(
t
))
,
τ
j
(A(
t
))
не может быть оптимальной, то получается
необходимое и достаточное условие конечнозначности задачи. Конеч-
нозначность дает возможность вместо решения задачи во всех точках
[
a, b
]
ограничиться ее решением в конечном числе точек этого интер-
вала.
Применение исследования устойчивости в математическом
моделировании.
Рассмотрим следующую ситуацию: моделируется
процесс
P
, происходящий во времени и имеющий несколько компо-
нент
K
1
, . . . , K
s
, математические модели которых представлены опти-
мизационными задачами или задачами вычислительной геометрии
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 5 65