EN|RU

Том 19, номер 2, 2012 г., Стр. 19-40

УДК 510.53
Давыдов И. А. 
Локальный поиск с запретами для дискретной задачи о (r|p)–центроиде

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

Ключевые слова: конкурентные размещения, игры Штаккельберга, двухуровневое программирование.

Давыдов Иван Александрович 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: iadavydov@math.nsc.ru

Статья поступила 31 марта 2011 г.
Исправленный вариант — 26 декабря 2011 г.

 © Институт математики им. С. Л. Соболева, 2015