Том 26, номер 3, 2019 г., Стр. 27-45

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

Аннотация:
Рассматривается двухуровневая задача конкурентного размещения предприятий и ценообразования, которая формулируется в терминах игры Штакельберга. В ней участвуют два производителя: Лидер и Конкурент. Они последовательно размещают свои предприятия и назначают цены. Выбор цен основывается на модели ценовой конкуренции Бертрана и возможности раздела спроса потребителей, если это выгодно обоим игрокам. При этом спрос делится между игроками в заданной пропорции.
Исследуется сложность нахождения оптимального решения задачи и её частных случаев. Показано, что задача является $\Sigma_2^P$-трудной. Однако при определённых условиях на входные параметры сложность нахождения оптимального решения значительно уменьшается и в некоторых случаях задача становится полиномиально разрешимой.
Ил. 3, библиогр. 25.

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

DOI: 10.33048/daio.2019.26.638

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

Статья поступила 22 ноября 2018 г.
После доработки — 2 апреля 2019 г.
Принята к публикации 5 июня 2019 г.

Литература

[1] Hotelling H. Stability in competition // Econ. J. 1929. Vol. 39, No. 153. P. 41–57.

[2] Eiselt H. A., Laporte G., Thisse J.-F. Competitive location models: a framework and bibliography // Transp. Sci. 1993. Vol. 27, No. 1. P. 44–54.

[3] Eiselt H. A., Laporte G. Sequential location problems // Eur. J. Oper. Res. 1996. Vol. 96, No. 2. P. 217–242.

[4] Hamacher H. W., Nickel S. Classification of location models // Loc. Sci. 1998. Vol. 6, No. 1. P. 229–242.

[5] Plastria F. Static competitive facility location: an overview of optimisation approaches // Eur. J. Oper. Res. 2001. Vol. 129, No. 3. P. 461–470.

[6] Панин А. A., Пащенко М. Г., Плясунов А. В. Двухуровневые модели конкурентного размещения производства и ценообразования // Автоматика и телемеханика. 2014. № 4. С. 153–169.

[7] Kononov A., Panin A., Plyasunov A. A new model of competitive location and pricing with the uniform split of the demand // Optimization problems and their applications. (Eremeev A., Khachay M., Kochetov Y., Pardalos P., eds.) Cham: Springer, 2018. (Commun. Comput. Informa. Sci.; Vol. 871).

[8] Garcia M. D., Fernandez P., Pelegrin B. On price competition in location-price models with spatially separated markets // TOP. 2004. Vol. 12, P. 351–374.

[9] Pelegrin B., Fernandez P., Garcia M. D., Cano S. On the location of new facilities for chain expansion under delivered pricing // Omega. 2012. Vol. 40, No. 2. P. 149–158.

[10] Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M. Complexity and approximation: combinatorial optimization problems and their approximability properties. Berlin: Springer-Verl., 1999. 524 p.

[11] Alekseeva E., Kochetov Yu. Matheuristics and exact methods for the discrete ($r | p$)-centroid problem // Metaheuristics for bi-level optimization (TalbiEl-G. El-G., Brotcorne L., eds.) Berlin: Springer-Verl., 2013. (Stud. Comput. Intell.; Vol. 482). P. 189–219.

[12] Alekseeva E., Kochetov Yu., Plyasunov A. An exact method for the discrete ($r | p$)-centroid problem // J. Global Optim. 2015. Vol. 63, No. 3. P. 445–460.

[13] Береснев В. Л., Мельников А. А. Алгоритм генерации отсечений для задачи выбора оптимальных решений в конкурентной борьбе на рынке // Дискрет. анализ и исслед. операций. 2019. Т. 26, № 2. С. 5–29.

[14] Alekseeva E., Kochetov Yu., Plyasunov A. Complexity of local search for the $p$-median problem // Eur. J. Oper. Res. 2008. Vol. 191, No. 3. P. 736–752.

[15] Davydov I., Kochetov Y., Dempe S. Local search approach for the competitive facility location problem in mobile networks // Int. J. Artif. Intell. 2018. Vol. 16, No. 1. P. 130–143.

[16] Davydov I. A., Kochetov Y. A., Carrizosa E. A local search heuristic for the ($r | p$)-centroid problem in the plane // Comput. Oper. Res. 2014. Vol. 52. P. 334–340.

[17] Лавлинский С. М., Панин А. А., Плясунов А. В. Сравнение моделей планирования государственно-частного партнёрства // Дискрет. анализ и исслед. операций. 2016. Т. 23, № 3. С. 35–60.

[18] Кочетов Ю. А., Панин А. А., Плясунов А. В. Сравнение метаэвристик для решения двухуровневой задачи размещения предприятий и фабричного ценообразования // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 3. С. 36–54.

[19] Diakova Z., Kochetov Yu. A double VNS heuristic for the facility location and pricing problem // Electron. Notes Discrete Math. 2012. Vol. 39, No. 1. P. 29–34.

[20] Давыдов И. A., Кочетов Ю. А., Младенович Н., Уросевич Д. Быстрые метаэвристики для дискретной задачи о ($r | p$)-центроиде // Автоматика и телемеханика. 2014. № 4. С. 106–119.

[21] Alekseeva E., Kochetov Y., Talbi E.-G. A matheuristic for the discrete bilevel problem with multiple objectives at the lower level // Int. Trans. Oper. Res. 2017. Vol. 24, No. 5. P. 959–981.

[22] Davydov I., Kochetov Yu., Plyasunov A. On the complexity of the ($r | p$)-centroid problem in the plane // TOP. 2014. Vol. 22, No. 2. P. 614–623.

[23] Iellamo S., Alekseeva E., Chen L., Coupechoux M., Kochetov Yu. Competitive location in cognitive radio networks // 4OR. 2015. Vol. 13, No. 1. P. 81–110.

[24] Панин А. А., Плясунов А. В. О сложности двухуровневых задач размещения и ценообразования // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 5. С. 54–66.

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