В работе рассматривается
простейшая задача размещения, которая
формулируется следующим образом. Имеются
множества I={1,2,..., I}, J={1,2,...,J}, вектор
ci 
0, i
I и матрица dij
0, iI, jJ. Требуется найти подмножество
S
I,
для которого функция
достигает минимального значения по всем непустым подмножествам множества I. Данная задача является NP-трудной в сильном смысле [1]. Для нее разработаны точные алгоритмы, приближенные полиномиальные алгоритмы с гарантированной оценкой точности, Лагранжевы эвристики, ассимптотически точные алгоритмы и др. [2]. Однако точные алгоритмы имеют экспоненциальную трудоемкость. Погрешность полиномиальных алгоритмов растет в худшем случае как логарифм от размерности задачи. Ассимптотичeски точные алгоритмы имеют хорошие характеристики только при стремлении размерности к бесконечности. В связи с этим представляет интерес разработка новых алгоритмов и, в частности, так называемых метаэвристик [3], которые стремятся как можно быстрее найти оптимальное решение и не заботятся о доказательстве, является ли найденное решение таковым или нет. В работе предлагается один из таких алгоритмов, основанный на идеях поиска с запретами. Формулируются достаточные условия на параметры алгоритма, при выполнении которых вероятность получения точного решения задачи стремится к единице с ростом числа итераций. Обсуждаются результаты численных экспериментов на трудных в вычислительном отношении классах исходных данных.
Работа поддержана грантом РФФИ 02-01-00890.
ЛИТЕРАТУРА
1. М.Гэри, Д.Джонсон. Вычислительные машины и
труднорешаемые задачи. М.: Мир. 1982.
2. J.Krarup, P.M.Pruzan The Simple Plant Location Problem: Survey and
Synthesis // European J. of Oper. Res.1983 V.12. P. 36-81.
3. E.Aarts, J.K.Lenstra (eds.) Local Search in Combinatorial Optimization.
Wiley-Interscience Serias in Discrete Mathematics and Optimization, 1997.