Том 29, номер 3, 2022 г., Стр. 7-23

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

Аннотация:
Рассматривается задача конкурентного размещения предприятий в условиях неопределённости параметров спроса, для которого представлен конечный набор возможных сценариев. Задача формулируется в виде двухуровневой модели, построенной на основе игры Штакельберга и классической модели размещения предприятий. В двухуровневой модели первый игрок (Лидер) имеет две возможности для открытия предприятия. Предполагается, что предприятие Лидера может быть открыто либо до того, как фактический сценарий спроса будет выявлен, либо после. Фиксированные затраты, связанные с открытием предприятия, в первом случае ниже. Таким образом, постоянные затраты могут быть снижены путём принятия заблаговременного решения об открытии предприятий на первом этапе и коррекции его на втором.

Мы предлагаем процедуру вычисления верхней границы для значения прибыли Лидера в рассматриваемой модели. Подход основан на формировании семейства вспомогательных двухуровневых подзадач. Оптимальные решения подзадач образуют допустимое решение исходной задачи. Верхняя граница вычисляется путём применения процедуры генерации отсечений для усиления релаксаций подзадач.
Табл. 1, ил. 1, библиогр. 10.

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

DOI: 10.33048/daio.2022.29.740

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

Статья поступила 16 мая 2022 г.
После доработки — 18 мая 2022 г.
Принята к публикации 19 мая 2022 г.

Литература

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

[2] Ashtiani M. G., Makui A., Ramezanian R. A robust model for a leaderfollower competitive facility location problem in a discrete space // Appl. Math. Model. 2013. V. 37, No. 1–2. P. 62–71.

[3] Yu W. A leader-follower model for discrete competitive facility location problem under the partially proportional rule with a threshold // PLOS ONE. 2019. V. 14, No. 12, ID e0225693. 16 p.

[4] Иванов С. В., Морозова М. В.
Стохастическая задача конкурентного размещения предприятий с квантильным критерием // Автоматика и телемеханика. 2016. № 3. С. 109–122.

[5] Beresnev V. L., Melnikov A. A. $\epsilon$-Constraint method for bi-objective competitive facility location problem with uncertain demand scenario // EURO J. Comput. Optim. 2020. V. 8, No. 1. P. 33–59.

[6] Ivanov S. V., Akmaeva V. N. Two-stage stochastic facility location model with quantile criterion and choosing reliability level // Вестн. ЮУрГУ. Сер. Мат. моделирование и программирование. 2021. Т. 14, № 3. С. 5–17.

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

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

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

[10] Gurobi optimizer reference manual. Beaverton: Gurobi Optimization, 2021. Available at www.gurobi.com/documentation/9.5/refman/index.html (accessed May 16, 2022).