Том 21, номер 5, 2014 г., Стр. 23-39
УДК 519.8
Курочкин А. А.
Задача размещения с ограниченными объёмами производства на случайных входных данных
Аннотация:
Рассматривается задача размещения с ограничениями на объёмы производства на случайных входных данных. Предполагается, что элементы матрицы транспортных расходов заданы независимыми случайными величинами с равномерной функцией распределения на целочисленном сегменте$[1,r]$ . Для задачи с одинаковыми ограничениями на объёмы производства построен приближённый алгоритм решения и проведён вероятностный анализ его работы. Представлены условия, при которых алгоритм является асимптотически точным и имеет временную трудоёмкость$O(n\ln m)$ , где$n$ – число потребителей,$m$ – число возможных пунктов производства. Для задачи с произвольными ограничениями построен алгоритм с трудоёмкостью порядка$O(n^{2(1-\theta)}m)$ и определены условия его асимптотической точности для некоторого$\theta<\frac12$ .
Ил. 1, библиогр. 17.
Ключевые слова: задача размещения производства, полиномиальный алгоритм, вероятность, асимптотическая точность.
Курочкин Александр Александрович 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: alkurochkin@ngs.ru
Статья поступила 28 октября 2013 г.
Исправленный вариант — 5 мая 2014 г.
Литература
[1] Агеев А. А., Гимади Э. Х., Курочкин А. А. Полиномиальный алгоритм решения задачи размещения на цепи с одинаковыми производственными мощностями предприятий // Дискрет. анализ и исслед. операций. - 2009. - Т. 16, №5. - C. 3–18.
[2] Вознюк И. П., Гимади Э. Х., Филатов М. Ю. Асимптотически точный алгоритм для решения задачи размещения с ограниченными объёмами производства // Дискрет. анализ и исслед. операций. Сер. 2. - 2001. - Т. 8, №2. - С. 3–16.
[3] Гимади Э. Х. Эффективный алгоритм решения задачи размещения с областями обслуживания, связными относительно ациклической сети // Управляемые системы. - 1983. - Вып. 23. - С. 12–23.
[4] Гимади Э. Х. Математические модели и методы исследования операций. Учебн. пособие. - Новосибирск: СибГУТИ, 2009. - 122 c.
[5] Гимади Э. Х., Курочкин А. А. Одна задача размещения с одинаковыми объёмами производства на случайных входных данных // Вестн. Новосиб. гос. ун-та. - 2011. - T. 11, вып. 1. - С. 15–34.
Gimadi E. Kh., Kurochkin A. A. Uniform capacitated facility location problem with random input data // J. Math. Sci. - 2013. - Vol. 188, N4. - P. 359–377.
[6] Гимади Э. Х., Перепелица В. А. Асимптотический подход к решению задачи коммивояжера // Сб. научн. тр. - Новосибирск: Ин-т математики СО АН СССР, 1974. - Вып. 12. - C. 35–45.
[7] Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа. - М.: Наука, 1969. - 494 c.
[8] Ageev A. A. A polynomial-time algorithm for the facility location problem with uniform hard capacities on path graphs // Proc 2nd Int. Workshop Discrete Optimization Methods in Production and Logistics (DOM’2004, Omsk–Irkutsk, July 20–27, 2004). - Omsk: Nasledie; Dialog-Sibir, 2004. - P. 28–32.
[9] Aikens C. H. Facility location models for distribution planning // Eur. J. Oper. Res. - 1985. - Vol. 22, N3. - P. 263–279.
[10] Akinc U., Khumawala B. M. An efficient branch and bound algorithm for the capacitated warehouse location problem // Manage. Sci. - 1977. - Vol. 23, N6. - P. 585–594.
[11] Angluin D., Valiant L. G. Fast probabilistic algorithms for Hamiltonian circuits and matchings // J. Comput. Syst. Sci. - 1979. - Vol. 18, N2. - P. 155–193.
[12] Chudak F., Williamson D. Improved approximation algorithms for capacitated facility location problems // Math. Program. - 2005. - Vol. 102, N2. - P. 207–222.
[13] Garey M. R., Johnson D. S. Computers and intractablity. - San Francisco: Freeman, 1979. - 340 p.
[14] Karp R. M. The probabilistic analysis of some combinatorial algorithms // Algorithms and complexity: new directions and recent results. - New York: Acad. Press, 1976. - P. 1–19.
[15] Korupolu M., Plaxton C., Rajaraman R. Analysis of a local search heuristic for facility location problems // J. Algorithms. - 2000. - Vol. 37, N1. - P. 146–188.
[16] Kuehn A. A., Hamburger M. J. A heuristic program for locating warehouses // Manage. Sci. - 1963. - Vol. 9, N4. - P. 643–66.
[17] Piersma N. A probabilistic analysis of the capacitated facility location problem // J. Comb. Optim. - 1999. - Vol. 3, N1. - P. 31–50.
