ГлавнаяАрхивАлгоритм точного решения дискретной задачи Вебера для простого цикла

Алгоритм точного решения дискретной задачи Вебера для простого цикла | Прикладная дискретная математика. 2013. № 4(22).

Предлагается полиномиальный алгоритм, находящий точное решение задачи Ве-бера в дискретной постановке для простого цикла и конечного множества позиций размещения, основанный на динамическом программировании. Проведен вычислительный эксперимент по анализу эффективности предложенного алгоритма в сравнении с пакетом IBM ILOG CPLEX.
  • Title Алгоритм точного решения дискретной задачи Вебера для простого цикла
  • Headline Алгоритм точного решения дискретной задачи Вебера для простого цикла
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 4(22)
  • Date:
  • DOI
Ключевые слова
задача Вебера, простой цикл, динамическое программирование, точный алгоритм, Weber problem, cycle, dynamic programming, exact algorithm
Авторы
Ссылки
Шангин Р. Э. Разработка и анализ алгоритмов для задачи Вебера // Проблемы оптимизации и экономические приложения. Омск, 2012. С. 121-122.
Panyukov А. V. and Pelzwerger B. V. Polynomial algorithms to finite Weber problem for a tree network // J. Comput. Appl. Math. 1991. V.35. P. 291-296.
Панюков А. В., Пельцвергер Б. Ф., Шафир А. Ю. Оптимальное размещение точек ветвления транспортной сети на цифровой модели местности // Автоматика и телемеханика. 1990. №9. С. 153-162.
Сергеев С. А. Квадратичная задача о назначениях I // Автоматика и телемеханика. 1999. №8. С. 127-147.
Панюков А. В. Модели и методы решения задач построения и идентификации геометрического размещения: дис.. д-ра физ.-мат. наук. Челябинск, 1999. 260 с.
Панюков А.В., Пельцвергер Б Ф. Оптимальное размещение дерева в конечном множестве // Журн. вычисл. математики и матем. физики. 1988. Т. 28. №2. С. 618-620.
Шангин Р. Э. Исследование эффективности приближенных алгоритмов решения одного частного случая задачи Вебера // Экономика, статистика и информатика. Вестник УМО. 2012. №1. С. 163-168.
Трубин В. А. Эффективный алгоритм для задачи Вебера с прямоугольной метрикой // Кибернетика. 1978. №6. С. 67-70.
Zabudsky G. G. and Filimonov D. V. An algorithm for minimax location problem on tree with maximal distances // Proc. Second Intern. Workshop "Discrete Optimization Methods in Production and Logistics" (D0M2004). Omsk, 2004. P. 81-85.
Забудский Г. Г., Филимонов Д. В. О минимаксной и минисуммной задачах размещения на сетях // Труды XII Байкальской Междунар. конф. «Методы оптимизации и их приложения». Омск, 2001. С. 150-155.
Филимонов Д. В. Решение дискретной минимаксной задачи размещения на древовидной сети // Материалы ежегодного научного семинара аспирантов. Омск, 2003. С. 58-61.
Алгоритм точного решения дискретной задачи Вебера для простого цикла | Прикладная дискретная математика. 2013. № 4(22).
Алгоритм точного решения дискретной задачи Вебера для простого цикла | Прикладная дискретная математика. 2013. № 4(22).
Полнотекстовая версия