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