Метаэвристические методы решения двухуровневой стохастической задачи размещения предприятий ¹⁵⁶

Формулируется стохастическая двухуровневая задача размещения предприятий, в которой фигурируют два игрока: лидер и последователь. Первым свои предприятия размещает лидер, а затем последователь. Доход, получаемый от потребителей, предполагается случайным. На этапе принятия решения игрокам известен только закон распределения случайного дохода. Цель обоих игроков состоит в максимизации гарантированной с заданной вероятностью прибыли. Для случая гауссовского распределения случайных параметров задача сводится к детерминированной двухуровневой задаче. Для решения полученной задачи предлагаются два алгоритма, основанные на адаптации метаэвристических методов: метода имитации отжига и метода поиска с чередующимися окрестностями. На примере задачи размещения электростанций проводится сравнение эффективности двух разработанных алгоритмов.

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

Рубрика: Методы оптимизации

Тип: научная статья

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

1. Береснев В.Л., Мельников А.А. Приближенные алгоритмы для задачи конкурентного размещения предприятий//Дискрет. анализ и исслед. операций. 2010. Т. 17. №6. С. 3-10.
2. Иванов С.В. Морозова М.В. Стохастическая задача конкурентного размещения предприятий с квантильным критерием // АиТ. 2016. № 3. С. 109-122.
3. Кибзун А.И., Кан Ю.С. Задачи стохастического программирования с вероятностными критериями. М.: Физматлит, 2009.
4. Bard J.F. Practical Bilevel Optimization: Algorithms and Applications. // Dordrecht: Kluwer Acad. Publ., 1998.
5. Dempe S, Kalashnikov V, Pérez-Valdés GA, Kalashnykova N. Bilevel Programming Problems - Theory, Algorithms and Applications to Energy Network. // Springer Verlag: Berlin, Heidelberg, 2015.
6. Melnikov A., Beresnev V. Upper Bound for the Competitive Facility Location Problem with Quantile Criterion // Lecture Notes in Computer Science. 2016. V. 9869. P. 373-387.
7. Snyder L.V. Facility location under uncertainty: a review // IIE Transact. 2006. V. 38. No. 7. P. 547–564.