Алгоритмы локального поиска для задачи о (r/p)-центроиде

• Автор: Давыдов, Иван Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Новосибирск
• Количество страниц: 113 с. : ил.

Оглавление
Введение

1 Вычислительная сложность задачи о (г|р)-центроиде

1.1 Математическая модель

1.2 Сложность задачи на плоскости

1.3 Сложность задачи конкурента

1.4 Основные результаты первой главы

2 Поиск с чередующимися окрестностями для задачи о (г|р)-центроиде на плоскости

2.1 Постановка задачи

2.2 Задача конкурента

2.3 Альтернирующая эвристика

2.4 Подзадача для одного предприятия лидера
2.5 Локальный поиск
2.6 Вычислительные эксперименты
2.7 Основные результаты второй главы
3 Локальный поиск с запретами для дискретной задачи о (г|р)-центроиде

3.1 Постановка задачи
3.2 Лагранжева релаксация
3.3 Метод локального поиска с запретами
3.4 Экспериментальные исследования
3.5 Стохастический поиск с запретами для задачи конкурента
3.6 Основные результаты третьей главы
Заключение
Литература

Введение
Актуальность темы. Задачи размещения предприятий имеют широкий круг приложений, возникающих при планировании и реконструкции производства, проектировании сетей обслуживания, в стандартизации, кластерном анализе и других областях. Значительный интерес к задачам так же связан с их высокой сложностью. Исследования в области задач размещения ведутся в Институте математики им. C.JI. Соболева СО РАН с конца 60-х годов прошлого столетия. Актуальность этих исследований обусловлена их важными практическими приложениями. Об этом свидетельствует большое число работ, посвященных задачам размещения. Среди них в первую очередь стоит отметить работы Береснева
B.JL, Гимади Э.Х., Дементьева В.Т., Гермейера Ю.Б., Шамардина Ю.В., Колоколова А. А., Антипина A.C., Хамисова О.В., Васильева И.Л., Забуд-ского Г.Г., Левановой Т.В. и др. В настоящее время область дискретной оптимизации, связанная с задачами размещения, активно развивается. Ведутся исследования структуры и вычислительной сложности задач, выделяются полиномиально разрешимые случаи, развиваются точные и приближенные методы их решения.
Цель диссертации состоит в разработке и исследовании методов локального поиска для решения задач о (г|р)-центронде и о

Глава 1. Вычислительная сложность

Р Т Г Т
Рис. 1.1: Цикл из кругов
Теорема 1 Задача о (гр)-центроиде на двухмерной евклидовой плоскости является Ті2 -трудной.
Доказательство. При сведении задачи ЗУЗ, Аваї к задаче о центроиде каждой булевой переменной будет соответствовать цикл, состоящий из кругов единичного радиуса (см. рис. 1.1). Каждому кругу соответствуют два клиента. Один находится в центре и имеет вес юх или ииу, в зависимости от того, какому типу переменных соответствует цикл. Второй клиент находится на границе круга и имеет вес ИЛ Будем считать, что И/ > 2юу > и)х > -Шу. Расстояние между центрами кругов равно 2-е для достаточно малого положительного є. Число кругов четно, скажем 2д. Если р = 2д, г = д и цикл соответствует некоторой переменной у7, то оптимальное решение лидера состоит в размещении всех предприятий на границе кругов в местах расположения клиентов с весом ИЛ Его доход в этом случае равен р]У. Оптимальное решение конкурента ри)у может быть получено двумя способами. Размещая свое предприятие на пересечении кругов, он получает двух клиентов в центрах этих кругов. Так как разбиение на такие пары можно сделать двумя способами, то у конкурента два оптимальных решения. Одно решение будет соответствовать