E-Book Overview
Новосибирск, 2009. - 267 с.
В диссертации получены следующие основные результаты. 1. Разработаны и исследованы новые вероятностные методы локального поиска для решения NP-трудных задач о p-медиане, простейшей и многостадийной задач размещения, размещения с предпочтениями клиентов, задач стандартизации и унификации, а также для решения более сложной задачи о (r; p)-центроиде (конкурентной задачи о p-медиане), являющейся NP–трудной. Эти итерационные методы позволяют находить оптимальные решения и в ряде случаев применяются для доказательства оптимальности получаемых решений. 2. Предложены и обоснованы итерационные методы вычисления апостериорных оценок точности получаемых приближенных решений для указанных выше труднорешаемых задач. В основе этих методов лежат оригинальные точные методы решения релаксированных задач. 3. Установлена вычислительная сложность нахождения локальных оптимумов для ряда задач размещения с полиномиально проверяемыми окрестностями. Показано, что эти задачи принадлежат классу PLS и являются наиболее трудными в этом классе. Получена экспоненциальная нижняя оценка на число итераций для алгоритмов локального улучше- ния при любом правиле выбора направления спуска. Доказана PSPACE-полнота задачи локального поиска при заданной стартовой точке. 4. Для задач размещения в игровой постановке установлена PLS-полнота задачи нахождения равновесных решений по Нэшу в чистых стратегиях. Получены достаточные условия эффективного вычисления приближенных равновесных решений. Показано, что в общем случае поиск приближенных равновесных решений является столь же сложной задачей, что и поиск самих равновесий по Нэшу. 5. Для экспериментального исследования численных методов и тестирования комплексов программ разработана электронная библиотека Дискретные задачи размещения. В ней представлены тесты разной вычислительной сложности, оптимальные решения и результаты численных исследований для точных и итерационных методов локального поиска.
E-Book Content
РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им. С.Л. СОБОЛЕВА
На правах рукописи УДК 519.21
Кочетов Юрий Андреевич
МЕТОДЫ ЛОКАЛЬНОГО ПОИСКА ДЛЯ ДИСКРЕТНЫХ ЗАДАЧ РАЗМЕЩЕНИЯ
05.13.18 — математическое моделирование, численные методы и комплексы программ
Диссертация на соискание учёной степени доктора физико-математических наук
Новосибирск — 2009
Оглавление Введение
5
1 Дискретные модели размещения 1.1 Простейшая задача размещения . . . . . . . . . . . . . . . 1.2 Многостадийная задача размещения . . . . . . . . . . . . . 1.3 Задачи размещения с предпочтениями клиентов . . . . . . 1.4 Антагонистические размещения . . . . . . . . . . . . . . . 1.5 Задачи стандартизации и унификации . . . . . . . . . . . . 1.5.1 Задача выбора состава системы технических средств 1.5.2 Двухуровневые системы технических средств . . . . 1.5.3 Динамическая задача с ограничениями на мощности 1.5.4 Задача выбора состава системы с частичным внешним финансированием . . . . . . . . . . . . . . . . .
27 28 33 37 42 46 47 49 51
2 Лагранжевы релаксации 2.1 Общая схема . . . . . . . . . . . . . . . . . . 2.1.1 Методы субградиентной оптимизации 2.1.2 Геометрическая интерпретация . . . 2.1.3 Лагранжева декомпозиция . . . . . . 2.2 Лагранжевы релаксации для задачи ВCC . . 2.2.1 Сильные и слабые формулировки . . 2.2.2 Нижние оценки оптимума . . . . . . . 2.2.3 Алгоритм решения задачи LR1 (λ) . . 2.2.4 Построение допустимого решения . . 2.2.5 Численные эксперименты . . . . . . . 2.3 Лагранжевы релаксации для задачи B2CC . 2.3.1 Две нижние оценки . . . . . . . . . . . 2.3.2 Cоотношение величин F и H . . . . . 2.3.3 Результаты тестовых расчетов . . . . 2.4 Лагранжевы релаксации для задачи ВДСС .
58 59 60 61 63 64 64 65 68 73 75 76 77 81 82 83
2