Том 21, номер 2, 2014 г., Стр. 3–23

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

Аннотация:
Изучается математическая модель, в которой две соперничающие стороны последовательно размещают свои предприятия, имея целью захватить потребителей и максимизировать прибыль. Модель представляется в виде задачи двухуровневого целочисленного программирования. В качестве оптимальных решений исследуемой задачи рассматриваются оптимальные некооперативные решения. Для отыскания приближённых и оптимальных решений задачи предлагается алгоритм ветвей и границ. Результаты вычислительного эксперимента показывают применимость алгоритма к решению индивидуальных задач малой и средней размерности.
Табл. 2, библиогр. 6.

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

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

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

Литература

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

[2] Береснев В. Л. Верхние оценки для целевых функций дискретных задач конкурентного размещения предприятий // Дискрет. анализ и исслед. операций. - 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, N4. - P. 419–432.

[3] Береснев В. Л. Дискретные задачи размещения и полиномы от булевых переменных. - Новосибирск: Изд-во ин-та математики, 2005. - 408 с.

[4] Береснев В. Л., Гончаров Е. Н., Мельников А. А. Локальный поиск по обобщённой окрестности для задачи оптимизации псевдобулевых функций // Дискрет. анализ и исслед. операций. - 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.

[5] Береснев В. Л., Мельников А. А. Приближённые алгоритмы для задачи конкурентного размещения предприятий // Дискрет. анализ и исслед. операций. - 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.

[6] Васильев И. Л., Климентова К. Б. Метод ветвей и отсечений для задачи размещения с предпочтениями клиентов // Дискрет. анализ и исслед. операций. - 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. Indust. Math. - 2010. - Vol. 4, N3. - P. 441–454.

[7] Васильев И. Л., Климентова К. Б., Кочетов Ю. А. Новые нижние оценки для задачи размещения с предпочтениями клиентов // Журн. вычисл. математики и мат. физики. - 2009. - Т. 49, №6. - С. 1055–1066.
Vasilyev 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, N 6. - P. 1010–1020.

[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, N 6. - P. 994–1009.

[9] Плясунов А. В., Панин А. А. Задача ценообразования. Ч. 1. Точные и приближённые алгоритмы решения // Дискрет. анализ и исслед. операций. - 2012. - Т. 19, № 5. - С. 83–100.

[10] Плясунов А. В., Панин А. А. Задача ценообразования. Ч. 2. Вычислительная сложность // Дискрет. анализ и исслед. операций. - 2012. - Т. 19, № 6. - С. 56–71.

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

[12] 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.

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

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

[15] Hammer P. L., Rudeanu S. Pseudo-Boolean programming // Oper. Res. - 1969. - Vol. 17. - P. 233–261.

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

[17] Mitten L. G. Branch-and-bound method: general formulation and properties // Oper. Res. - 1970. - Vol. 18. - P. 24–34.

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