Локальный поиск с запретами для дискретной задачи о $(r|p)$-центроиде

Для дискретной задачи о $(r|p)$-центроиде разработан вероятностный метод локального поиска с запретами. Получены ограничения на список запретов, при которых алгоритм обладает следующим свойством: с ростом числа итераций вероятность отыскания глобального оптимума стремится к единице. Для оценки значений целевой функции используется метод лагранжевых релаксаций. Показано, что такая оценка не уступает оценке линейной релаксации. Исследуются различные алгоритмы субградиентной оптимизации для поиска оптимальных множителей Лагранжа. Проведены экспериментальные исследования на тестовых примерах из электронной библиотеки “Дискретные задачи размещения”. Результаты экспериментов свидетельствуют о высокой частоте получения глобального оптимума разработанным методом. Ил. 4, табл. 5, библиогр. 21.