ВЕРОЯТНОСТНЫЙ АЛГОРИТМ ЛОКАЛЬНОГО ПОИСКА

ДЛЯ ПРОСТЕЙШЕЙ ЗАДАЧИ РАЗМЕЩЕНИЯ

Ю.А.Кочетов

В работе рассматривается простейшая задача размещения, которая формулируется следующим образом. Имеются множества I={1,2,...,I}, J={1,2,...,J}, вектор c_i 0, iI и матрица d_ij 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.

____________________________________________________________________

Кочетов Юрий Андреевич, Институт математики им. С.Л.Соболева СО РАН,

пр.Академика Коптюга 4, Новосибирск, 630090, Россия, тел. (8-383-2) 35-63-27,

факс (8-383-2) 35-06-52, E-mail: jkochet@math.nsc.ru