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

• Автор: Кочетов, Юрий Андреевич
• Шифр специальности: 05.13.18
• Научная степень: Докторская
• Год защиты: 2009
• Место защиты: Новосибирск
• Количество страниц: 267 с. : ил.

Оглавление
Введение
1 Дискретные модели размещения
1.1 Простейшая задача размещения
1.2 Многостадийная задача размещения
1.3 Задачи размещения с предпочтениями клиентов
1.4 Антагонистические размещения
1.5 Задачи стандартизации и унификации
1.5.1 Задача выбора состава системы технических средств
1.5.2 Двухуровневые системы технических средств
1.5.3 Динамическая задача с ограничениями на мощности
1.5.4 Задача выбора состава системы с частичным внешним финансированием
2 Лагранжевы релаксации
2.1 Общая схема
2.1.1 Методы субградиентной оптимизации
2.1.2 Геометрическая интерпретация
2.1.3 Лагранжева декомпозиция
2.2 Лагранжевы релаксации для задачи ВСС
2.2.1 Сильные и слабые формулировки
2.2.2 Нпжние оценки оптимума
2.2.3 Алгоритм решения задачи LR{А)
2.2.4 Построение допустимого решения
2.2.5 Численные эксперименты
2.3 Лагранжевы релаксации для задачи В2СС
2.3.1 Две нижние оценки
2.3.2 Соотношение величин F и Н
2.3.3 Результаты тестовых расчетов
2.4 Лагранжевы релаксации для задачи ВДСС

2.4.1 Нижние оценки
2.4.2 Общая схема алгоритма
2.4.3 Задачи с ограничениями на номенклатуру изделий
2.4.4 Задачи с фактором серийности
2.4.5 Результаты тестовых расчетов
3 Метаэвристики
3.1 Метаэвристики для задач комбинаторной
оптимизации
3.2 Вероятностные жадные алгоритмы
3.2.1 Алгоритм «лидер группы»
3.2.2 Условия дополняющей нежесткости
3.2.3 Алгоритм «случайный аутсайдер»
3.2.4 Принцип ветвления
3.2.5 Модификации алгоритмов ЛГ и СА
3.3 Вероятностный поиск с запретами
3.3.1 Общая схема
3.3.2 Асимптотические свойства
3.3.3 Варианты алгоритмов
3.3.4 Вычислительные эксперименты
3.3.5 Направления дальнейших исследований
3.4 Генетический локальный поиск
3.4.1 Генетический алгоритм
3.4.2 Генетический алгоритм для задачи МПК
3.4.3 Тестовые примеры
3.4.4 Выбор параметров алгоритма
3.4.5 Нижние оценки оптимума
3.5 Гибридные методы
3.5.1 Гибридный генетический локальный поиск
3.5.2 Верхние оценки
3.5.3 Тестовые расчеты
4 Вычислительная сложность локального поиска
4.1 Задачи локального поиска
4.2 Класс РГЛ
4.3 РЬБ-полные задачи размещения
4.4 Временная сложность локального спуска
4.5 Локально седловые точки
Введение

4.6 Приближенный локальный поиск
4.7 Погрешность локальных оптимумов
5 Равновесия по Нэшу в игровых моделях размещения
5.1 Игровая модель размещения предприятий
5.2 Связь с локальными оптимумами
5.3 Сложность нахождения равновесных решений
5.4 Поиск приближенных равновесий
5.5 Сложность алгоритмов локального улучшения
6 Электронная библиотека «Дискретные задачи размещения»
6.1 Структура библиотеки
6.2 Простейшая задача размещения
6.2.1 Полиномиально разрешимые примеры
6.2.2 Примеры с экспоненциальным числом строгих локальных минимумов
6.2.3 Примеры с большим разрывом целочисленное
6.2.4 Поведение метаэвристик
6.3 Примеры с кластеризацией локальных минимумов
6.4 Примеры для конкурентной задачи о р-медиане
Заключение
Литература

Глава 1. Дискретные модели размещения

Сформулированная задача является NP-трудной в сильном смысле и тесно связана с задачами стандартизации [10], задачей минимизации полиномов от булевых переменных [11] и двухуровневой задачей выбора номенклатуры изделий [24]. Если каждая цепочка р £ Р содержит только одно предприятие, то получаем простейшую задачу размещения. В работах [9, 10, 203] вместо условия ^Zpep. xpj — г' € 1, i 6 J, используется условие
Xpj <хи ре Pi, г £ I, j £ J,
что приводит к более слабой линейной релаксации. Такой же эффект получается введением переменных
Г 1, если выпускается продукция по технологической цепочке р, 0 в противном случае,
и заменой условия ]СРер, xpj <хи г Г 1, j £ J, на ограничения
Ур > xpj, j£j,pEP,
Хг>Ур, р е Pi,i е I.
Новая формулировка дает ту же оценку линейного программирования, что и предыдущая, но эта оценка может оказаться в произвольное число раз хуже исходной [39].
Заметим, что в математической постановке задачи нигде не отражается тот факт, что множество I разбито на непересекагощиеся подмножества. Множество Р явным образом задает все технологические цепочки и, вообще говоря, может иметь произвольную структуру. Например, оно может содержать цепочки разной длины и с несколькими вхождениями одного и того же предприятия. В работе [22] с величинами Cpj, р £ Р, j Е J, связывались затраты на транспортировку продукции между предприятиями и затраты на доставку ее потребителю. Сюда же включались и затраты на обработку и выпуск продукции каждым предприятием из данной технологической цепочки. Легко видеть, что такой подход позволяет моделировать ситуацию произвольных цепочек с любым маршрутом продукции по предприятиям. В этом смысле ситуация близка к задачам Job Shop из теории расписаний, где допускается произвольная последовательность обработки деталей на станках.
Предложенная модель не всегда удобна при решении практических задач, так как множество Р может оказаться экспоненциально большим.