Рандомизированный локальный поиск для дискретной задачи конкурентного размещения предприятий

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

Статья представлена к публикации членом редколлегии: А. И. Кибзун