Том 21, номер 4, 2014 г., Стр. 62-79

УДК 519.87
Мельников А. А.
Вычислительная сложность дискретной задачи конкурентного размещения предприятий

Аннотация:
Рассматривается дискретная задача конкурентного размещения предприятий, в которой заданы конечное множество потребителей и конечное множество мест, доступных для открытия предприятий. Две конкурирующие фирмы последовательно — сначала первая, а затем вторая — размещают в некоторых из этих мест предприятия, стремясь получить максимальную прибыль от обслуживания потребителей, каждый из которых для своего обслуживания выбирает среди открытых фирмами предприятий ровно одно, исходя из своих известных предпочтений. Установлена вычислительная сложность задачи в двух частных случаях.
Библиогр. 16.

Ключевые слова: полиномиальная иерархия, игра Штакельберга, двухуровневое программирование.

Мельников Андрей Андреевич ^1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: a.a.melnikov@hotmail.com

Статья поступила 18 марта 2014 г.
Исправленный вариант — 24 мая 2014 г.

Литература

[1] Береснев В. Л. Верхние оценки для целевых функций дискретных задач конкурентного размещения предприятий // Дискрет. анализ и исслед. операций. - 2008. - Т. 15, № 4. - С. 3–24.
Beresnev V. L. Upper bounds for objective functions of discrete competitive facility location problems // J. Appl. Industr. Math. - 2009. - Vol. 3, N 4. - P. 419–432.

[2] Береснев В. Л. Алгоритмы локального поиска для задачи конкурентного размещения предприятий // Автоматика и телемеханика. - 2012. - №3. - C. 12–27.
Beresnev V. L. Local search algorithms for the problem of competitive location of enterprises // Autom. Remote Control. - 2012. - Vol. 73, N 3. - P. 425–439.

[3] Береснев В. Л., Гончаров Е. Н., Мельников А. А. Локальный поиск по обобщённой окрестности для задачи оптимизации псевдобулевых функций // Дискрет. анализ и исслед. операций. - 2011. - Т. 18, №4. - С. 3–16.
Beresnev V. L., Goncharov E. N., Mel’nikov A. A. Local search with a generalized neighborhood in the optimization problem for pseudo-Boolean functions // J. Appl. Industr. Math. - 2012. - Vol. 6, N1. - P. 22–30.

[4] Береснев В. Л., Мельников А. А. Приближённые алгоритмы для задачи конкурентного размещения предприятий // Дискрет. анализ и исслед. операций. - 2010. - Т. 17, № 6. - С. 3–19.
Beresnev V. L., Melnikov A. A. Approximate algorithms for the competitive facility location problems // J. Appl. Industr. Math. - 2011. - Vol. 5, N 2. - P. 180–190.

[5] Васильев И. Л., Климентова К. Б. Метод ветвей и отсечений для задачи размещения с предпочтениями клиентов // Дискрет. анализ и исслед. операций. - 2009. - Т. 16, № 2. - С. 21–41.
Vasil’ev I. L., Klimentova K. B. The branch and cut method for the facility location problem with clients’ preferences // J. Appl. Industr. Math. - 2010. - Vol. 4, N3. - P. 441–454.

[6] Васильев И. Л., Климентова К. Б., Кочетов Ю. А. Новые нижние оценки для задачи размещения с предпочтениями клиентов // Журн. вычисл. математики и мат. физики. - 2009. - Т. 49, №6. - С. 1055–1066.
Vasil’ev I. L., Klimentova K. B., Kochetov Yu. A. New lower bounds for the facility location problem with clients’ preferences // Comput. Math. Math. Phys. - 2009. - Vol. 49, N6. - P. 1010–1020.

[7] Гермейер Ю. Б. Игры с непротивоположными интересами. - М.: Наука, 1976. - 328 c.

[8] Кононов А. В., Кочетов Ю. А., Плясунов А. В. Конкурентные модели размещения производства // Журн. вычисл. математики и мат. физики. - 2009. - Т. 49, №6. - С. 1037–1054.
Kononov A. V., Kochetov Yu. A., Plyasunov A. V. Competitive facility location models // Comput. Math. Math. Phys. - 2009. - Vol. 49, N6. - P. 994–1009.

[9] Beresnev V. Branch-and-bound algorithm for competitive facility location problem // Comput. Oper. Res. - 2013. - Vol. 40. - P. 2062–2070.

[10] Canovas L., Garcia S., Labbe M., Marin A. A strengthened formulation for the simple plant location problem with order // Oper. Res. Lett. - 2007. - Vol. 35. - P. 141–150.

[11] Davydov I., Kochetov Yu., Plyasunov A. On the complexity of the (r|p)-centroid problem in the plane // TOP. - 2013. - DOI: 10.1007/s11750-013-0275-y.

[12] Dempe S. Foundations of bilevel programming. - Dordrecht: Kluwer Acad. Publ., 2002. - 332 p.

[13] Garey M. R., Johnson D. S. Computers and intractability: a guide to the theory of NP-completeness. - San Francisco: W. H. Freeman Co., 1979. - 338 p.

[14] Krarup J., Pruzan P. M. The simple plant location problem: survey and synthesis // Eur. J. Oper. Res. - 1983. - N12. - P. 36–81.

[15] Stackelberg H. The theory of the market economy. - Oxford: Oxford Univ. Press, 1952. - 289 p.

[16] Stockmeyer L. J. The polynomial-time hierarchy // Theor. Comput. Sci. - 1977. - N3. - P. 1–22.