Том 20, номер 5, 2013 г., Стр. 84-96

УДК 519.863
Шангин Р. Э.
Детерминированный алгоритм для решения задачи Вебера для n-последовательносвязной цепи

Аннотация:
Вводится класс n-последовательносвязных цепей. Предлагается алгоритм, находящий точное решение задачи Вебера для n-последовательносвязной цепи и конечного множества позиций размещения, основанный на динамическом программировании. Дан теоретический анализ предложенного алгоритма. На классе задач, сгенерированном случайным образом, проведён вычислительный эксперимент по анализу эффективности предложенного алгоритма в сравнении с пакетом IBM ILOG CPLEX.
Ил. 3, табл. 1, библиогр. 10.

Ключевые слова: задача Вебера, n-последовательносвязная цепь, динамическое программирование, точный алгоритм.

Шангин Роман Эдуардович ¹
1. Южно-Уральский гос. университет,
пр. Ленина, 76, 454080 Челябинск, Россия
е-mail: shanginre@gmail.com

Статья поступила 15 ноября 2012 г.
Исправленный вариант — 19 марта 2013 г.

Литература

[1] Быкова В. В. Вычислительные аспекты древовидной ширины графа // Прикл. дискрет. математика. - 2011. - № 3. - С. 65–79.

[2] Забудский Г. Г., Лагздин А. Ю. Полиномиальные алгоритмы решения минимаксной квадратичной задачи о назначениях на сетях // Дискрет. анализ и исслед. операций. - 2011. Т. 18, № 4. - С. 49–65.

[3] Забудский Г. Г., Филимонов Д. В. О минимакской и минисуммной задачах размещения на сетях // Тр. XII Байкальской междунар. конф. «Методы оптимизации и их приложения» (Иркутск, 24 июня–1 июля 2001 г.). - Иркутск: Изд-во ИГУ, 2001. - С. 150–155.

[4] Панюков А. В. Модели и методы решения задач построения и идентификации геометрического размещения. Дисс. ... д-ра физ.-мат. наук. - Челябинск: Южноуральский ун-т, 1999. - 260 с.

[5] Панюков А. В., Пельцвергер Б. Ф. Оптимальное размещение дерева в конечном множестве // Журн. вычисл. математики и мат. физики. - 1988. - Т. 28. - С. 618–620.

[6] Панюков А. В., Пельцвергер Б. Ф., Шафир А. Ю. Оптимальное размещение точек ветвления транспортной сети на цифровой модели местности // Автоматика и телемеханика. - 1990. - № 9. - С. 153–162.

[7] Сергеев С. И. Квадратичная задача о назначениях. I // Автоматика и телемеханика. - 1999. - № 8. - С. 127–147.

[8] Трубин В. А. Эффективный алгоритм для задачи Вебера с прямоугольной метрикой // Кибернетика. - 1978. - № 6. - С. 67–70.

[9] Филимонов Д. В. Решение дискретной минимаксной задачи размещения на древовидной сети // Мат. ежегод. науч. семинара аспирантов и студентов-выпускников. - Омск: Изд-во Омск. гос. ун-та, 2003. - С. 58–61.

[10] Шангин Р. Э. Исследование эффективности приближенных алгоритмов решения одного частного случая задачи Вебера // Экономика, статистика и информатика. Вестн. УМО. - 2012. - № 1. - С. 163–169.

[11] Шангин Р. Э. О некоторых свойствах n-последовательносвязной цепи // Вестн. ЮУрГУ. Сер. Вычисл. математика и информатика. - 2013. - Т. 2, № 1. - С. 106–113.

[12] Шангин Р. Э. Квазиполиномиальный алгоритм для решения задачи Вебера для
n-последовательносвязного цикла // Обозрение прикл. и пром. математики. - 2012. - Т. 19, вып. 4. - С. 122–124.

[13] Шангин Р. Э. Разработка и анализ алгоритмов для задачи Вебера // Тез. докл. междунар. конф. «Проблемы оптимизации и экономические приложения» (Омск, 2–6 июля 2012 г.) - Омск: Изд-во Омск. гос. ун-та, 2012. - С. 121.

[14] McKee T. A. On the chordality of a graph // J. Graph Theory. - 1993. - Vol. 17. - P. 221–232.

[15] Panyukov A. V., Pelzwerger B. V. Polynomial algorithms to finite Weber problem for a tree network // J. Comput. Appl. Math. - 1991. - Vol. 35. - P. 291–296.

[16] Zabudsky G. G., Filimonov D. V. An algorithm for minimax location problem on a tree with maximal distances // Proc. 2nd Int. Workshop Discrete Optimization Methods in Production and Logistics (DOM2004). - Omsk; Irkutsk: ISU Press, 2004. - P. 81–85.