Том 19, номер 6, 2012 г., Стр. 9-22
УДК 519.7
Гимади Э. Х., Курочкин А. А.
Эффективный алгоритм решения двухэтапной задачи размещения на древовидной сети
Аннотация:
Рассматривается двухэтапная задача размещения производства на древовидной сети при условии, что затраты на транспортировку единицы продукции из пункта в пункт равны сумме длин рёбер в цепи, соединяющей эти пункты. Предложен алгоритм для точного решения данной задачи с трудоёмкостью$O(nm^3)$ , где$n$ – число пунктов спроса конечного продукта,$m$ – ограничение сверху на число возможных пунктов размещения производства каждого этапа.
Ил. 3, библиогр. 7.
Ключевые слова: двухэтапная задача размещения производства, полиномиальный алгоритм, древовидная сеть.
Гимади Эдуард Хайрутдинович 1,2
Курочкин Александр Александрович 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2.
Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: gimadi@math.nsc.ru, alkurochkin@ngs.ru
Статья поступила 8 декабря 2011 г.
Исправленный вариант — 22 апреля 2012 г.
Литература
[1] Береснев В. Л., Гимади Э. Х., Дементьев В. Т. Экстремальные задачи стандартизации. — Новосибирск: Наука, 1978. — 333 с.
[2] Гимади Э. Х. Эффективные алгоритмы для решения многоэтапной задачи размещения на цепи // Дискрет. анализ и исслед. операций. Cep. 1. — 1995. — Т. 2, № 4. — С. 13–31.
[3] Ageev A., Ye Yi., Zhang J. Improved combinatorial approximation algorithms for the $k$-level facility location problem // SIAM J. Discrete Math. — 2004. — Vol. 18, N 1. — P. 207–217.
[4] Gimadi E. Kh. Exact algorithm for some multi-level location problems on a chain and a tree // Oper. Res. Proc. SOR’96 (Braunschweig, Germany, September 3–6, 1996). — Berlin: Springer-Verl., 1997. — P. 72–77.
[5] Discrete location theory // Wiley-Intersci. Ser. Discrete Math. Optimization. — New York; Chichester; Brisbane; Toronto; Singapour: Wiley & Sons Inc., 1990. — 555 p.
[6] Zhang J. Approximating the two-level facility location problem via a quasi-greedy approach // Proc. 15th ACM-SIAM Symp. Discrete Algorithms SODA (New Orleans, Louisiana, USA, January 11–14, 2004). — Philadelphia: SIAM, 2004. — P. 808–817.
[7] Bumb A. F., KernW. A simple dual ascent algorithm for the multilevel facility location problem // 4th Int. Workshop Approximation Algorithms Comb. Optimization. APPROX 2001 (Berkeley, CA, USA, August 18–20,
2001). — London: Springer-Verl., 2001. — P. 55–62. (Lect. Notes Comput. Sci.; Vol. 2129).
