Приближённые алгоритмы для задачи конкурентного размещения предприятий

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