Методы локального поиска для дискретных задач размещения

Новосибирск, 2009. - 267 с.В диссертации получены следующие основные результаты.
1. Разработаны и исследованы новые вероятностные методы локального поиска для решения NP-трудных задач о p-медиане, простейшей и многостадийной задач размещения, размещения с предпочтениями клиентов, задач стандартизации и унификации, а также для решения более сложной задачи о (r; p)-центроиде (конкурентной задачи о p-медиане), являющейся NP–трудной. Эти итерационные методы позволяют находить оптимальные решения и в ряде случаев применяются для доказательства оптимальности получаемых решений.
2. Предложены и обоснованы итерационные методы вычисления апостериорных оценок точности получаемых приближенных решений для указанных выше труднорешаемых задач. В основе этих методов лежат оригинальные точные методы решения релаксированных задач.
3. Установлена вычислительная сложность нахождения локальных оптимумов для ряда задач размещения с полиномиально проверяемыми окрестностями. Показано, что эти задачи принадлежат классу PLS и являются наиболее трудными в этом классе. Получена экспоненциальная нижняя оценка на число итераций для алгоритмов локального улучше-
ния при любом правиле выбора направления спуска. Доказана PSPACE-полнота задачи локального поиска при заданной стартовой точке.
4. Для задач размещения в игровой постановке установлена PLS-полнота задачи нахождения равновесных решений по Нэшу в чистых стратегиях. Получены достаточные условия эффективного вычисления приближенных равновесных решений. Показано, что в общем случае поиск приближенных равновесных решений является столь же сложной
задачей, что и поиск самих равновесий по Нэшу.
5. Для экспериментального исследования численных методов и тестирования комплексов программ разработана электронная библиотека Дискретные задачи размещения. В ней представлены тесты разной вычислительной сложности, оптимальные решения и результаты численных исследований для точных и итерационных методов локального поиска.