ГлавнаяАрхивРешение макси-суммной задачи размещения на сети с ограничением на транспортные затраты

Решение макси-суммной задачи размещения на сети с ограничением на транспортные затраты | Прикладная дискретная математика. 2023. № 60. DOI: 10.17223/20710410/60/11

Рассматривается задача оптимального размещения объекта на неориентированной взвешенной сети. Каждому ребру приписан положительный вес, а вершинам - два положительных параметра. Первый параметр отражает требование размещать объект как можно ближе к вершине, а второй - как можно дальше. Задано ограничение на суммарное взвешенное расстояние от объекта до вершин с учётом первого параметра. Необходимо найти допустимые места размещения объекта на рёбрах сети с максимальной суммой взвешенных расстояний от них до вершин с учётом второго параметра (локальные экстремумы). Предложен полиномиальный алгоритм поиска всех локальных экстремумов на рёбрах сети.
  • Title Решение макси-суммной задачи размещения на сети с ограничением на транспортные затраты
  • Headline Решение макси-суммной задачи размещения на сети с ограничением на транспортные затраты
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 60
  • Date:
  • DOI 10.17223/20710410/60/11
Ключевые слова
задача размещения, макеи-суммный критерий, опасный объект, сеть
Авторы
Ссылки
Tamir A. Obnoxious facility location on graphs // SIAM J. Discrete Math. 1991. V. 4. No.4. P. 550-567.
Drezner Z. Facility Location. A Survey of Applications and Methods. N.Y.: Springer, 1995. 571 p.
Eiselt H. A. and Marianov V. Foundations of Location Analysis. N.Y.: Springer, 2011. 509 p.
Zabudsky G. G. and Lisina M. S. Approximately algorithm for maximin location problem on network // Dynamics of Systems, Mechanisms and Machines. XII Intern. Conf. Omsk, Russia, 13-15 November 2018. https://ieeexplore.ieee.org/document/8601502.
Church R. L. and Garfinkel R. S. Locating an obnoxious facility on a network // Trans. Sci. 1978. V. 12. No. 2. P. 107-118.
Hakimi S. L. Optimal location of switching centers and the absolute centers and medians of a graph // Oper. Res. 1964. V. 12. No.3. P.450-459.
Berman O. and Drezner Z. A note on the location of an obnoxious facility on a network // Eur. J. Oper. Res. 2000. V. 120. No. 1. P.215-217.
Забудский Г. Г. Размещение опасного объекта на сети с ограничением на транспортные затраты // Проблемы машиноведения. VI Междунар. науч.-техн. конф. Омск, 22-23 марта 2022. С. 162-165.
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.
Ху T. Целочисленное программирование и потоки в сетях. М.: Мир, 1974. 519 с.
Решение макси-суммной задачи размещения на сети с ограничением на транспортные затраты | Прикладная дискретная математика. 2023. № 60. DOI: 10.17223/20710410/60/11
Решение макси-суммной задачи размещения на сети с ограничением на транспортные затраты | Прикладная дискретная математика. 2023. № 60. DOI: 10.17223/20710410/60/11