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