Том 22, номер 3, 2015 г., Стр. 18−35

УДК 519.854
Гордеев Э. Н.
Сравнение трёх подходов к исследованию устойчивости решений задач дискретной оптимизации и вычислительной геометрии

Аннотация:
В 1970–80-х гг. в работах В. К. Леонтьева и Э. Н. Гордеева предложен и исследован подход к анализу устойчивости решений. В ряде более поздних статей этот подход был развит и на его основе анализировалась устойчивость решений. Сам подход носит достаточно общий характер, но изначально связывался с задачами дискретной оптимизации. В дальнейшем похожие результаты, хотя и в иных терминах, публиковались для различных классов задач. В данной работе показана близость некоторых подходов как на уровне постановок задач, так и при интерпретации результатов.
Библиогр. 18.

Ключевые слова: устойчивость решения, радиус устойчивости, псевдобулев полином, матроид, геометрическая конфигурация.

DOI: 10.17377/daio.2015.22.461

Гордеев Эдуард Николаевич ¹
1. МГТУ им. Н. Э. Баумана
2-я Бауманская ул., 5, 105005 Москва, Россия
е-mail: tatmigor@gmail.com

Статья поступила 10 сентября 2014 г.
Исправленный вариант — 9 февраля 2015 г.

Литература

[1] Алюшкевич В. Б., Сотсков Ю. Н. Устойчивость в задачах календарного планирования // Изв. АН БССР. Сер. физ.-мат. науки. 1989. № 3. С. 102–107.

[2] Артеменко В. И., Гордеев Э. Н., Журавлев Ю. И. и др. Метод формирования оптимальных программных траекторий робота-манипулятора // Кибернетика и систем. анализ. 1996. № 5. C. 82–104.

[3] Береснев В. Л. Дискретные задачи размещения и полиномы от булевых переменных. Новосибирск: Ин-т математики СО РАН, 2005. 408 с.

[4] Вялый М. Н., Гордеев Э. Н., Тарасов С. П. Об устойчивости диаграммы Вороного // Журн. вычисл. математики и мат. физики. 1996. Т. 36, № 3. С. 147–158.

[5] Гордеев Э. Н. Алгоритмы полиномиальной сложности для вычисления радиуса устойчивости в двух классах траекторных задач // Журн. вычисл. математики и мат. физики. 1987. Т. 27, № 7. С. 984–992.

[6] Гордеев Э. Н. Устойчивость решений в задаче о кратчайшем пути на графе // Дискрет. математика. 1989. Т. 1, № 3. С. 39–46.

[7] Гордеев Э. Н. Об устойчивости решений в задачах вычислительной геометрии // Тез. докл. междунар. науч. конф. .Интеллектуальная обработка информации.. Симферополь: Крым. Акад. Наук, 1996. С. 8.

[8] Гордеев Э. Н. Исследование устойчивости задачи о кратчайшем остове в метрике l₁ // Журн. вычисл. математики и мат. физики. 1999. T. 39, № 5. C. 770–778.

[9] Гордеев Э. Н. Исследование устойчивости в оптимизационных задачах на матроидах в метрике l₁ // Кибернетика и систем. анализ. 2001. № 2. С. 132–144.

[10] Гордеев Э.Н. Использование радиуса устойчивости оптимизационных задач для скрытия и проверки корректности информации // Инженерный журн.: наука и инновации. 2013. № 11. C. 14–19.

[11] Гордеев Э. Н., Леонтьев В. К. Общий подход к исследованию устойчивости решений в задачах дискретной оптимизации // Журн. вычисл. математики и мат. физики. 1996. Т. 36, № 1. C. 66–72.

[12] Девятерикова М. В., Колоколов А. А., Косарев Н. А. Анализ устойчивости по целевой функции некоторых алгоритмов целочисленного программирования // Изв. вузов. Математика. 2011. № 4. С. 47–53.

[13] Емеличев В. А., Коротков В. В. О радиусе устойчивости векторной квадратичной булевой задачи на узкие места // Дискрет. анализ и исслед. операций. 2011. Т. 18, № 6. С. 3–16.

[14] Емеличев В. А., Коротков В. В. Анализ устойчивости парето-оптимального портфеля многокритериальной инвестиционной задачи с минимаксными критериями Вальда // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 6. С. 23–36.

[15] Колоколов А. А., Девятерикова М. В. Анализ устойчивости L-разбиения множеств в конечномерном пространстве // Дискрет. анализ и исслед. операций. Сер. 2. 2000. Т. 7, № 2. С. 47–53.

[16] Леонтьев В. К. Устойчивость в линейных дискретных задачах // Пробл. кибернетики. 1979. Вып. 35. C. 169–185.

[17] Леонтьев В. К., Гордеев Э. Н. Качественное исследование траекторных задач // Кибернетика. 1986. № 5. C. 82–90.

[18] Cheng E., Cunningham W. H. A faster algorithm for computing the strength of a network // Inf. Process. Lett. 1994. Vol. 49. Р. 209–212.

[19] Cunningham W. H. Testing membership in matroid polyhedra // J. Comb. Theory. Ser. B. 1984. Vol. 36. P. 161–188.

[20] Fredericson G. N., Solis-Oba R. Increasing the weight of minimum spanning trees // Proc. 7th Ann. ACM-SIAM Symp. Discrete Algorithms. Philadelphia, PA: SIAM, 1996. P. 539–546.

[21] Fredericson G. N., Solis-Oba R. Efficient algorithms for robustness in matroid optimization // Proc. 8th Ann. ACM-SIAM Symp. Discrete Algorithms. Philadelphia, PA: SIAM, 1997. P. 659–668.

[22] Gallo G., Grigoriadis M. D., Tarjan R. E. A fast parametric maximum flow algorithm and application // SIAM J. Comput. 1989. Vol. 18, No. 1. P. 30–55.

[23] Narayanan H. A rounding technique for the polymatroid problem // Linear Algebra Appl. 1995. Vol. 221. P. 41–57.

[24] Sotskov Yu. N., Leont’ev V. K., Gordeev E. N. Some concepts of stability analysis in combinatorial optimization // Discrete Appl. Math. 1985. Vol. 58. P. 169–190.

[25] Tarjan R. E. Sensitivity analysis of minimum spanning trees and shortest paths trees // Inf. Process. Lett. 1982. Vol. 14, No. 1. Р. 30–33.