Том 23, номер 1, 2016 г., Стр. 35-50

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

Аннотация:
Рассматривается математическая модель, относящаяся к задачам конкурентного последовательного размещения предприятий. В этих задачах две соперничающие стороны последовательно открывают свои предприятия, стремясь «захватить» потребителей и максимизировать свою прибыль. В предлагаемой модели предполагается, что возможности предприятий по обслуживанию «захваченных» потребителей ограничены заданными объёмами производства этих предприятий. Модель формулируется в виде задачи двухуровневого целочисленного программирования, для которой исследуется вопрос поиска оптимального (кооперативного) решения. Показано, что данная задача может быть представлена как задача максимизации некоторой псевдобулевой функции с числом переменных, равным числу возможных мест размещения предприятий. Предлагается также способ вычисления верхней границы значений псевдобулевой функции на подмножествах решений, заданных частичными (0,1)-векторами, основанный на использовании системы оценочных подмножеств.
Библиогр. 15.

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

DOI: 10.17377/daio.2016.23.493

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

Статья поступила 20 мая 2015 г.
Исправленный вариант — 22 июня 2015 г.

Литература

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

[2] Береснев В. Л. Алгоритмы локального поиска для задачи конкурентного размещения предприятий // Автоматика и телемеханика. 2012. № 3. С. 12–27.

[3] Береснев В. Л. О задаче конкурентного размещения предприятий со свободным выбором поставщиков // Автоматика и телемеханика. 2014. № 4. C. 94–105.

[4] Береснев В. Л., Гончаров Е. Н., Мельников А. А. Локальный поиск по обобщённой окрестности для задачи оптимизации псевдобулевых функций // Дискрет. анализ и исслед. операций. 2011. Т. 18, №4. С. 3–16.

[5] Береснев В. Л., Мельников А. А. Приближённые алгоритмы для задачи конкурентного размещения предприятий // Дискрет. анализ и исслед. операций. 2010. Т. 17, № 6. С. 3–19.

[6] Береснев В. Л., Мельников А. А. Алгоритм ветвей и границ для задачи конкурентного размещения предприятий с предписанным выбором поставщиков // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 2. С. 3–23.

[7] Кононов А. В., Кочетов Ю. А., Плясунов А. В. Конкурентные модели размещения производства // Журн. вычисл. математики и мат. физики. 2009. Т. 49, № 6. C. 1037–1054.

[8] Мельников А. А. Рандомизированный локальный поиск для дискретной задачи конкурентного размещения предприятий // Автоматика и телемеханика. 2014. № 4. С. 134–152.

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

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

[11] Beresnev V. L. Branch-and-bound algorithm for a competitive facility location problem // Comput. Oper. Res. 2013. Vol. 40, No. 8. P. 2062–2070.

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

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

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

[15] Von Stackelberg H. The theory of the market economy. London: Hedge, 1952. 289 p.