Том 28, номер 4, 2021 г., Стр. 90-116

УДК 519.816+519.854.2
Захаров А. О., Коваленко Ю. В.
Сужение множества Парето специальной структуры в дискретных задачах с двумя критериями

Аннотация:
Исследуются дискретные задачи оптимизации с двумя критериями в контексте аксиоматического подхода к сужению множества Парето. Строятся оценки степени сужения множества Парето специальной структуры и в общем случае в зависимости от значений коэффициента компромисса лица, принимающего решение. Проводится апробация результатов на семействах задач о покрытии и маршрутизации.
Ил. 4, библиогр. 19.

Ключевые слова: дискретная оптимизация, двухкритериальная задача, сужение множества Парето, отношение предпочтения лица, принимающего решение.

DOI: 10.33048/daio.2021.28.712

Захаров Алексей Олегович ¹
Коваленко Юлия Викторовна ²
1. Санкт-Петербургский гос. университет,
Университетская наб., 7–9, 199034 Санкт-Петербург, Россия
2. Институт математики им. С. Л. Соболева,
ул. Певцова, 13, 644099 Омск, Россия
е-mail: zakh.alexey@gmail.com, julia.kovalenko.ya@yandex.ru

Статья поступила 19 апреля 2021 г.
После доработки — 8 июня 2021 г.
Принята к публикации 10 июня 2021 г.

Литература

[1] Ларичев О. И. Теория и методы принятия решений, а также хроника событий в волшебных странах. М.: Логос, 2006. 392 с.

[2] Лотов А. В., Поспелова И. И. Многокритериальные задачи принятия решений. М.: МАКС Пресс, 2008. 197 с.

[3] Петровский А. Б. Теория принятия решений. М.: Изд. центр «Академия», 2009. 400 с.

[4] Ishizaka A., Nemery P. Multi-criteria decision analysis: Methods and software. Hoboken, NJ: Wiley, 2013. 328 p.

[5] Ehrgott M., Figueira J. L., Greco S. Trends in multiple criteria decision analysis. New York: Springer, 2010. 412 p.

[6] Greco S., Ehrgott M., Figueira J. L. Multiple criteria decision analysis: State of the art surveys. New York: Springer, 2016. 1347 p.

[7] Ларичев О. И. Вербальный анализ решений. М.: Наука, 2006. 181 с.

[8] Ногин В. Д. Сужение множества Парето. Аксиоматический подход. М.: ФИЗМАТЛИТ, 2016. 272 с.

[9] Zakharov A. O., Kovalenko Yu. V. Reduction of the Pareto set in bicriteria Asymmetric Traveling Salesman Problem // Optimization Problems and Their Applications. Rev. Sel. Pap. 7th Int. Conf. (Omsk, Russia, July 8–14, 2018). Cham: Springer, 2018. P. 93–105. (Commun. Comput. Inf. Sci.; Vol. 871).

[10] Zakharov A. O., Kovalenko Yu. V. Construction and reduction of the Pareto set in asymmetric travelling salesman problem with two criteria // Вестн. С.-Петербург. ун-та. Сер. Прикл. математика. Информатика. Процессы управления. 2018. Т. 14, № 4. С. 378–392.

[11] Zakharov A. O., Kovalenko Yu. V. Structures of the Pareto set and their reduction in bicriteria discrete problems // J. Phys. Conf. Ser. 2019. Vol. 1260, No. 8. P. 082007:1–082007:8.

[12] Christofides N. Graph theory: An algorithmic approach. London: Acad. Press, 1975. 400 p.

[13] Еремеев А. В., Заозерская Л. А., Колоколов А. А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискрет. анализ и исслед. операций. Сер. 2. 2000. Т. 7, №2. С. 22–46.

[14] Нечепуренко М. И., Попков В. К., Майнагашев С. М., Кауль С. М., Проскуряков В. А., Кохов В. А., Грызунов А. Б. Алгоритмы и программы решения задач на графах и сетях. Новосибирск: Наука, 1990. 521 с.

[15] Kolokolov A. A., Zaozerskaya L. A. Solving a bicriteria problem of optimal service centers location // J. Math. Model. Algorithms. 2013. Vol. 12. P. 105–116.

[16] Saksena J. Mathematical model for scheduling clients through welfare agencies // J. Can. Oper. Res. Soc. 1970. Vol. 8. P. 185–200.

[17] Henry-Labordere A. The record balancing problem: A dynamic programming solution of a generalized traveling salesman problem // Rev. Franç. Inform. Rech. Opér. 1969. Vol. 3, No. B-2. P. 43–49.

[18] Хачай М. Ю., Незнахина Е. Д. Приближенные схемы для обобщенной задачи коммивояжера // Тр. Ин-та математики и механики. 2016. Т. 22, № 3. C. 283–292.

[19] Ченцов А. Г., Хачай М. Ю., Хачай Д. М. Точный алгоритм с линейной трудоемкостью для одной задачи обхода мегаполисов // Тр. Ин-та математики и механики. 2015. Т. 21, № 3. С. 309–317.