Preview

Информатика

Расширенный поиск

О РАДИУСЕ УСТОЙЧИВОСТИ ВЕКТОРНОЙ ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Полный текст:

Аннотация

Находятся верхняя и нижняя оценки радиуса устойчивости векторной задачи целочисленного линейного программирования с паретовским принципом оптимальности при возмущении параметров векторного критерия в пространстве с метрикой l1. Доказана достижимость нижней оценки. В качестве следствия приводится формула радиуса устойчивости задачи с единственным оптимальным решением.

Об авторах

В. А. Емеличев
Белорусский государственный университет
Беларусь


К. Г. Кузьмин
Белорусский государственный университет
Беларусь


Список литературы

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.


Для цитирования:


Емеличев В.А., Кузьмин К.Г. О РАДИУСЕ УСТОЙЧИВОСТИ ВЕКТОРНОЙ ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. Информатика. 2006;(2(10)):84-93.

For citation:


., . . Informatics. 2006;(2(10)):84-93. (In Russ.)

Просмотров: 23


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)