Сложность и алгоритмы решения дискретной задачи конкурентного размещения предприятий

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

Оглавление
Введение
Обзор литературы
Глава 1. Вычислительная сложность
1.1. Задача конкурентного размещения с нулевыми фиксированными затратами
1.2. Задача конкурентного размещения на графе-звезде
1.3. Основные результаты главы г
Глава 2. Метод ветвей и границ
2.1. Общая схема
2.2. Верхняя граница и функция ветвления
2.3. Реализация метода и результаты вычислительных экспериментов
2.4. Основные результаты главы
Глава 3. Методы локального поиска
3.1. Алгоритмы локального улучшения
3.2. Алгоритм поиска по обобщённой окрестности
3.3. Оценка значения целевой функции
3.4. Стохастический локальный поиск
3.5. Основные результаты главы
Заключение Список литературы
Введение
Актуальность работы. Задачи размещения предприятий имеют широкий круг приложений, возникающих при планировании и реконструкции производства, проектировании сетей обслуживания, в стандартизации, кластерном анализе и других областях. Значительный интерес к задачам так же связан с их высокой сложностью. Исследования в области задач размещения ведутся в Институте математики им. C.J1. Соболева СО РАН с конца 60-х годов прошлого столетия. Актуальность этих исследований обусловлена их важными практическими приложениями. Об этом свидетельствует большое число работ, посвященных задачам размещения. Среди них в первую очередь стоит отметить работы Береснева B.JL, Гимади Э.Х., Дементьева В.Т., Гермейера Ю.Б., Шамардина Ю.В., Колоколова A.A., Антипина A.C., Хамисова О.В., Васильева И.Л., Забудского Г.Г., Левановой Т.В. и др. В настоящее время область дискретной оптимизации, связанная с задачами размещения, активно развивается. Ведутся исследования структуры и вычислительной сложности задач, выделяются полиномиально разрешимые случаи, развиваются точные и приближенные методы их решения.
Цель диссертации состоит в установлении сложностного статуса дискретной задачи конкурентного размещения предприятий и разработке точных и приближенных алгоритмов её решения.
Объектом исследования диссертации является дискретная задача кон-

НИЯ ДЛЯ потребителя
Для каждого ъ € Z рассмотрим потребителя аъ Е Аъ . Положим: 1 Д — Ь%
Гг,а.с =
2к, г = а.

2к + 1,г —
; Рг,аг =

М + 1,1 е Ах
О,иначе
; гц, иначе
где 1]г — произвольные попарно различные числа, превосходящие 2т + 1. Для потребителя ах в описанных построениях заменим г на г.
Предпочтения потребителя Ьх и доходы от его обслуживания имеют схожий вид:
М = Ох
ГчЬх =
2/с, г = 6.

1Д Е Вг 0,иначе
; Рг,ьх = 0 Уг Е 7; =
2к + 1,г =
Д,иначе
где Д — произвольные попарно различные числа, превосходящие 2п+1. Заменой х на х получим устройство предпочтений и доходов для потребителя Дс-
Осталось описать поведение потребителей множества Т, соответствующее множеству термов формулы (р. Возьмем произвольный терм 1;, представляющий из себя конъюнкцию четырех литералов. Для определенности, пусть t = Х1&21&22&гз. Для потребителя jt положим: