Том 17, номер 6, 2010 г., Стр. 3-19
УДК 519.725
Береснев В. Л., Мельников А. А.
Приближённые алгоритмы для задачи конкурентного размещения предприятий
Аннотация:
Рассматривается задача конкурентного размещения предприятий, в которой две соперничающие стороны (Лидер и Последователь) открывают последовательно свои предприятия, а каждый потребитель выбирает одно из открытых предприятий, исходя из своих предпочтений. Задача состоит в том, чтобы выбрать размещение предприятий Лидера так, чтобы получить максимальную прибыль, учитывая последующее размещение предприятий Последователем, который также стремится получить максимальную прибыль. Задача формулируется как задача двухуровневого целочисленного программирования. Предлагается способ вычисления верхней границы для величины максимальной прибыли Лидера. Соответствующий алгоритм состоит в построении классической задачи размещения предприятий на максимум и отыскании оптимального решения этой задачи. Одновременно с вычислением верхней границы строится начальное приближённое решение задачи конкурентного размещения предприятий. Предлагаются алгоритмы локального поиска для улучшения начального приближённого решения. Приводятся результаты вычислительного эксперимента с предложенными алгоритмами, позволяющие оценить точность получаемых приближённых решений и дать сравнительную оценку качества рассматриваемых алгоритмов построения приближённых решений исследуемой задачи.
Табл. 1, библиогр. 13.
Ключевые слова: задача двухуровневого программирования, оптимальное некооперативное решение, верхняя граница, приближённое решение, локальный поиск.
Береснев Владимир Леонидович 1,2
Мельников Андрей Андреевич 2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2.
Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: beresnev@math.nsc.ru, a.a.melnikov@hotmail.com
Статья поступила 10 мая 2010 г.
