Том 26, номер 2, 2019 г., Стр. 5-29

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

Аннотация:
Исследуется математическая модель конкурентной борьбы на рынке между двумя соперничающими сторонами. Стороны последовательно предлагают рынку свою продукцию и стремятся получить максимальную прибыль. Модель построена на основе игры Штакельберга и записывается в виде задачи двухуровневого целочисленного программирования. Эта задача сводится к задаче конкурентного размещения предприятий (CompFLP) с предписанным выбором поставщиков, относящейся к семейству двухуровневых моделей, обобщающих классическую задачу размещения предприятий. Для задачи CompFLP с предписанным выбором поставщиков предлагается алгоритм поиска пессимистического оптимального решения, представляющий собой итеративную процедуру последовательного усиления оценочных задач дополнительными ограничениями. Оценочная задача даёт верхнюю границу для целевой функции задачи CompFLP и получается из двухуровневой модели исключением «внутренней» целевой функции. Для усиления оценочных задач предлагается новая система дополнительных ограничений. Приводятся результаты вычислительных экспериментов на тестовых примерах задачи CompFLP с предписанным выбором поставщиков, демонстрирующие вычислительные возможности предложенного алгоритма.
Табл. 2, библиогр. 17.

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

DOI: 10.33048/daio.2019.26.642

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

Статья поступила 17 декабря 2018 г.
После доработки — 11 января 2019 г.
Принята к публикации 27 февраля 2019 г.

Литература

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

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

[3] Береснев В. Л., Мельников А. А. Алгоритм генерации отсечений для дискретной задачи конкурентного размещения предприятий // Докл. АН. 2018. Т. 80, № 5. С. 515–518.

[4] Береснев В. Л., Суслов В. И. Математическая модель конкурентной борьбы на рынке // Сиб. журн. индустр. математики. 2009. Т. 12, № 1. С. 11–24.

[5] Библиотека тестовых примеров «Дискретные задачи размещения». http://old.math.nsc.ru/AP/benchmarks/index.html.

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

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

[8] Beresnev V. L., Melnikov A. A. Exact method for the capacitated competitive facility location problem // Comput. Oper. Res. 2018. Vol. 95. P. 73–82.

[9] Beresnev V. L., Melnikov A. A. Approximation of the competitive facility location problem with MIPs // Comput. Oper. Res. 2019. Vol. 104. P. 139–148.

[10] Cánovas L., García S., Labbé M., Marín A. A strengthened formulation for the simple plant location problem with order // Oper. Res. Lett. 2007. Vol. 35, No. 2. P. 141–150.

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

[12] Gurobi optimizer reference manual. Gurobi Optimization, 2018. http://www.gurobi.com.

[13] Hanjoul P., Peeters D. A facility location problem with clients’ preference orderings // Reg. Sci. Urban Econ. 1987. Vol. 17, No. 3. P. 451–473.

[14] Hemmati M., Smith J. C. A mixed-integer bilevel programming approach for a competitive prioritized set covering problem // Discrete Optim. 2016. Vol. 20. P. 105–134.

[15] Moore J. T., Bard J. F. The mixed integer linear bilevel programming problem // Oper. Res. 1990. Vol. 38, No. 5. P. 911–921.

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

[17] Vasilyev I., Klimentova X., Boccia M. Polyhedral study of simple plant location problem with order // Oper. Res. Lett. 2013. Vol. 41, No. 2. P. 153–158.