12 / 14
Теорема 1.
Диаграмма Вороного является неустойчивой тогда и
только тогда, когда выполнено хотя бы одно из двух условий
:
1)
существует вершина
v
∈
V
степени более 3
;
2)
множество
J
{
P
)
не пусто.
Итак, если задача неустойчива, то
r
(
Р
) = 0
. Для устойчивой задачи
следующее утверждение дает формулу вычисления радиуса устойчи-
вости. Пусть
l
(
P
) = min(
δ
(
P
)
,
β
(
P
)
,
π
(
P
))
.
Теорема 2.
Существует равенство
r
(
P
) =
l
(
P
)
. Можно по-
казать, что проверка устойчивости задачи и нахождение радиуса
устойчивости могут быть осуществлены за линейное время
.
Достижение цели 2 (без учета технических характеристик обору-
дования и физики задачи) также обеспечивается с использованием
устойчивости. Наиболее просто это выглядит для случая выхода из
строя одной точки доступа. Тогда задача сводится к предыдущей.
ЛИТЕРАТУРА
1.
Гордеев Э.Н.
,
Леонтьев В.К.
Общий подход к исследованию устойчивости ре-
шений в задачах дискретной оптимизации // ЖВМиМФ. 1996. № 36. С. 66–72.
2.
Леонтьев В.К.
Устойчивость в линейных дискретных задачах. В кн.: Проблемы
кибернетики. М.: Наука, 1979. Вып. 35. С. 169–185.
3.
Гордеев Э.Н.
Алгоритмы полиномиальной сложности для вычисления радиуса
устойчивости в двух классах траекторных задач // ЖВМиМФ. 1987. Т. 27. № 7.
С. 984–992.
4.
Гордеев Э.Н.
Устойчивость решений в задаче о кратчайшем пути на графе //
Дискретная математика. 1989. Т. 1. № 3. С. 39–46.
5.
Леонтьев В.К.
,
Гордеев Э.Н.
Качественное исследование траекторных задач.
Кибернетика и системный анализ. 1986. № 5. С. 82–90.
6.
Гордеев Э.Н.
Об устойчивости решений в задачах вычислительной геометрии //
Тезисы докладов международ. научн. конф. “Интеллектуальная обработка ин-
формации”. Крымская Академия Наук. 1996. С. 8.
7.
Вялый М.Н.
,
Гордеев Э.Н.
,
Тарасов С.П.
Об устойчивости диаграммы Вороно-
го // ЖВМиМФ.1996. Т. 36. № 3. С. 405–414.
8.
Метод
формирования оптимальных программных траекторий робота-
манипулятора / Артеменко В.И., Гордеев Э.Н., Журавлев Ю.И. и др. // Ки-
бернетика и системный анализ. 1986. № 5. С. 84–107.
9.
Гордеев Э.Н
.,
Леонтьев В.К.
Траекторные параметрические задачи //
ЖВМиМФ. 1984. № 24. С. 37–46.
10.
Гордеев Э.Н.
Использование радиуса устойчивости оптимизационных задач
для скрытия и проверки корректности информации. Инженерный журнал: наука
и инновации. 2013. Вып. 11. URL:
http://engjournal.ru/catalog/it/hidden/993.html(дата обращения: 15.09.2014).
11.
Гордеев Э.Н.
,
Липкин Л.И.
О единственности решения некоторых комбинатор-
ных задач выбора Методы дискретного анализа. Сб. труд. Новосибирск, 1989.
Вып. 49. С. 13–31.
72 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 5