ГлавнаяАрхивПриближённое решение максиминной задачи размещения объектов на сети с ограничениями на минимальные расстояния

Приближённое решение максиминной задачи размещения объектов на сети с ограничениями на минимальные расстояния | Прикладная дискретная математика. 2025. № 68. DOI: 10.17223/20710410/68/8

Рассматривается задача оптимального размещения объектов на неориентированной взвешенной сети, расположенной на плоскости. Вершинам приписаны положительные веса, а рёбра представлены отрезками. Вес вершины отражает требование размещать объекты как можно дальше от неё. Заданы ограничения на минимально допустимые расстояния от вершин до объектов. Необходимо найти такие точки на рёбрах сети для размещения объектов, чтобы минимальное взвешенное расстояние от вершин до объектов было максимальным. Предложен алгоритм решения задачи с заданной точностью для двух объектов.
  • Title Приближённое решение максиминной задачи размещения объектов на сети с ограничениями на минимальные расстояния
  • Headline Приближённое решение максиминной задачи размещения объектов на сети с ограничениями на минимальные расстояния
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 68
  • Date:
  • DOI 10.17223/20710410/68/8
Ключевые слова
выпуклая оболочка, задача размещения, максиминный критерий, опасный объект, сетъ
Авторы
Ссылки
Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 432 с.
Drezner Z. Facility Location. A Survey of Applications and Methods. N.Y.: Springer, 1995. 571 p.
Nickel S. Location Theory. A Unified Approach. Berlin: Springer Verlag, 2005. 437 p.
Farani R. Z. and Flekmatfar M. Facility Location: Concepts, Models, Algorithms and Case Studies. Berlin: Springer Verlag, 2009. 549 p.
Eiselt H. A. and Marianov V. Foundations of Location Analysis. N.Y.: Springer, 2011. 509 p.
Church R. L. and Garfinkel R. S. Locating an obnoxious facility on a network // Trans. Sci. 1978. V. 12. No. 2. P.107-118.
Забудский Г. Г. Решение макси-суммной задачи размещения на сети с ограничениями на транспортные затраты // Прикладная дискретная математика. 2023. №60. С. 120-127.
Melachrinoudis Е. and Zhang G. An O(mn) algorithm for the 1-maximin problem on a network // Comput. & Oper. Res. 1999. V.26. No.9. P.849-869.
Heydari R. and Melachrinoudis E. Location of a semi-obnoxious facility with elliptic maxmin and network minisum objectives // Eur. J. Oper. Res. 2012. V.223. No. 2. P.452-460.
Zabudsky G. and Lisina M. Approximately algorithm for maximin location problem on network // Proc. XII Intern. Conf. "Dynamics of Systems, Mechanisms and Machines". 13-15 November 2018, Omsk, Russia. P. 1-6.
Tamir A. Obnoxious facility location on graphs // SIAM J. Discrete Math. 1991. V. 4. No. 4. P. 550-567.
Welch S. В. and Wesolowsky S. The obnoxious p facility network location problem with facility interaction // Eur. J. Oper. Res. 1997. V. 102. No.2. P.302-319.
Tamir A. Locating two obnoxious facilities using the weighted maximin criterion // Oper. Res. Let. 2006. V.34. No.l. P.97-105.
Яглом И. M., Болтянский И. М. Выпуклые фигуры. М.: Технике-теоретическая литература, 1951. 344 с.
Shamos М. I.Computational Geometry. PhD Thesis. New Haven, Yele University, 1978. 236 p.
Пpepapama Ф., Шеймос M. Вычислительная геометрия: Введение. M.: Мир, 1989. 478 с.
Приближённое решение максиминной задачи размещения объектов на сети с ограничениями на минимальные расстояния | Прикладная дискретная математика. 2025. № 68. DOI: 10.17223/20710410/68/8
Приближённое решение максиминной задачи размещения объектов на сети с ограничениями на минимальные расстояния | Прикладная дискретная математика. 2025. № 68. DOI: 10.17223/20710410/68/8