О РАДИУСЕ УСТОЙЧИВОСТИ ВЕКТОРНОЙ ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Abstract
Находятся верхняя и нижняя оценки радиуса устойчивости векторной задачи целочисленного линейного программирования с паретовским принципом оптимальности при возмущении параметров векторного критерия в пространстве с метрикой l1. Доказана достижимость нижней оценки. В качестве следствия приводится формула радиуса устойчивости задачи с единственным оптимальным решением.
About the Authors
В. Емеличев
Белорусский государственный университет
Belarus
Belarus
К. Кузьмин
Белорусский государственный университет
Belarus
Belarus
References
1. Ehrgott, M. A survey and annotated bibliography of multiobjective combinatorial optimization / M. Ehrgott, X. Gandibleux // OR Spectrum. – 2000. – Vol. 22. – № 4. – P. 425–460.
2. Greenberg, N.J. An annotated bibliography for post-solution analysis in mixed integer and combinatorial optimization / N.J. Greenberg // Advances in computational and stochastic optimization, Logic Programming and Heuristic Search. – Boston: Kluwer Academic Publishers, 1998. – P. 97–148.
3. Сергиенко, И.В. Исследование устойчивости и параметрический анализ дискретных оптимизационных задач / И.В. Сергиенко, Л.Н. Козерацкая, Т.Т. Лебедева. – Киев: Наукова думка, 1995. – 170 с.
4. Сергиенко, И.В. Задачи дискретной оптимизации. Проблемы, методы решения, исследования / И.В. Сергиенко, В.П. Шило. – Киев: Наукова думка, 2003. – 261 с.
5. Сотсков, Ю.Н. Теория расписаний. Системы с неопределенными числовыми параметрами / Ю.Н. Сотсков, Н.Ю. Сотскова. – Минск: ОИПИ НАН Беларуси, 2004. – 290 с.
6. Sotskov, Yu.N. Some concepts of stability analysis in combinatorial optimization / Yu.N. Sotskov, V.K. Leontev, E.N. Gordeev // Discrete Applied Mathematics. – 1995. – Vol. 58. – № 2. – P. 169–190.
7. Sotskov, Yu.N. Stability radius of an optimal schedule: a survey and recent developments / Yu.N. Sotskov, V.S. Tanaev, F. Werner // Industrial applications of combinatorial optimization. – Kluwer Academic Publishers, 1998. – Vol. 16. – P. 72–108.
8. Сотсков, Ю.Н. Исследование устойчивости оптимальных расписаний / Ю.Н. Сотсков // Информатика. – 2004. – № 4. – С. 65–75.
9. Chakravarti, N. Calculation of stability radius for combinatorial optimization problems / N. Chakravarti, A. Wagelmans // Operations Research Letters. – 1998. – Vol. 23. – № 1. – P. 1–7.
10. Stability aspects of the traveling salesman problem based on -best solutions / M. Libura [et al.] // Discrete Applied Mathematics. – 1998. – Vol. 87. – P. 159–185.
11. Van Hoesel, S. On the complexity of postoptimality analysis of 0-1 programs / S. Van Hoesel, A. Wagelmans // Discrete Applied Mathematics. – 1999. – Vol. 91. – P. 251–263.
12. Гордеев, Э.Н. Исследование устойчивости в оптимизационных задачах на матроидах в метрике / Э.Н. Гордеев // Кибернетика и системный анализ. – 2001. – № 2. – С. 132–144.
13. Колоколов, А.А. Анализ устойчивости некоторых алгоритмов дискретной оптимизации / А.А. Колоколов, М.В. Девятерикова // Автоматика и телемеханика. – 2004. – № 3. – С. 48–54.
14. Емеличев, В.А. О количественной мере устойчивости векторной задачи целочисленного программирования / В.А. Емеличев, Д.П. Подкопаев // Журнал вычислительной математики и математической физики. – 1998. – Т. 38. – № 11. – С. 1801–1805.
15. Емеличев, В.А. Устойчивость и регуляризация векторных задач целочисленного линейного программирования / В.А. Емеличев, Д.П. Подкопаев // Дискретный анализ и исследование операций. Сер. 2. – 2001. – Т. 8. – № 1. – С. 47–69.
16. Stability and regularization of vector problems of integer linear programming / V.A. Eme-lichev [et al.] // Optimization. – 2002. – Vol. 51. – № 4. – P. 645–676.
17. Emelichev, V.A. The stability radius of an efficient solution in minimax Boolean programming problem / V.A. Emelichev, V.N. Krichko, Yu.V. Nikulin // Control and Cybernetics. – 2004. – Vol. 33. – № 1. – P. 127–132.
18. Емеличев, В.А. Устойчивость в векторных комбинаторных задачах оптимизации / В.А. Емеличев, К.Г. Кузьмин, А.М. Леонович // Автоматика и телемеханика. – 2004. – № 2. – C. 79–92.
19. Гордеев, Э.Н. Исследование устойчивости задачи о кратчайшем остове в метрике / Э.Н. Гордеев // Журнал вычислительной математики и математической физики. – 1990. – Т. 39. – С. 770–778.
20. Подиновский, В.В. Парето-оптимальные решения многокритериальных задач / В.В. Поди-новский. – М.: Наука, 1982. – 256 с.
21. Tanino, T. Stability of nondominated solutions in multicriteria decision-making / T. Tanino, Y. Sawaragi // Journal of Optimization Theory and Applications. – 1980. – Vol. 30. – № 2. – P. 229–253.
22. Козеpацкая, Л.Н. Задачи целочисленного пpогpаммиpования с вектоpным кpитеpием: паpаметpический анализ и исследование устойчивости / Л.Н. Козеpацкая, Т.Т. Лебедева, Т.И. Сеpгиенко // Доклады АН СССР. – 1989. – Т. 307. – № 3. – С. 527–529.
23. Емеличев, В.А. О регуляризации многокритериальной задачи целочисленного линейного программирования / В.А. Емеличев, О.А. Янушкевич // Известия вузов. Математика. – 1999. – № 12. – С. 38–42.
Review
For citations:
, . Informatics. 2006;(2(10)):84-93. (In Russ.)
Views: 508
Email this article 