Сложность и алгоритмы решения дискретной задачи конкурентного размещения предприятий тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Мельников, Андрей Андреевич

• Мельников, Андрей Андреевич
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Мельников, Андрей Андреевич

Оглавление

Введение

Обзор литературы

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

Цель диссертации состоит в установлении сложностного статуса дискретной задачи конкурентного размещения предприятий и разработке точных и приближенных алгоритмов её решения.

Объектом исследования диссертации является дискретная задача кон-

курентного размещения предприятий. Предмет исследования — вычислительная сложность данной задачи и ее частных случаев, а также алгоритмы неявного перебора и локального поиска для ее решения.

Методы исследования. В диссертации использованы современные методы исследования операций, включающие в себя построение математических моделей, теорию вычислительной сложности, идеи неявного перебора и локального поиска, а также методологию экспериментальных исследований с применением вычислительной техники и пакетов прикладных программ для решения задач целочисленного программирования.

Научная новизна. Оригинальность и научная новизна полученных результатов состоит в следующем.

1. Рассмотрена и изучена новая модель конкурентного размещения предприятий. Исследована ее вычислительная сложность. Показано, что задача поиска ее оптимального решения является более сложной, чем большинство известных ИР^грудных задач.

2. Предложен алгоритм неявного перебора для поиска точных и приближенных решений дискретной задачи конкурентного размещения предприятий с гарантированной оценкой точности. Предложена процедура вычисления верхней границы для целевой функции исследуемой задачи. Установлены важные свойства оптимальных решений конкурирующих сторон.

3. Предложены алгоритмы локального поиска для нахождения приближенных решений дискретной задачи конкурентного размещения предприятий. Алгоритм поиска по обобщенной окрестности, позволяющий по-

I 1

лучать близкие к оптимальным решения. Алгоритм стохастического локального поиска, использующий процедуру разбиения исходной задачи и процедуру внутреннего локального поиска, позволяющий получать качественные решения для примеров большой размерности.

Основные результаты диссертации. 1. Установлено, что дискретная задача конкурентного размещения предприятий Е^-трудна в случае нулевых затрат на открытие предприятий и булевых матриц доходов от обслуживания потребителей. Показано, что задача конкурентного размещения на графах-звездах КР-трудна в случае, когда доход от обслуживания каждого из потребителей не зависит от обслуживающего предприятия.

2. Разработан алгоритм ветвей и границ для поиска оптимальных и приближенных решений с гарантированной оценкой точности для дискретной задачи конкурентного размещения предприятий. Построен алгоритм вычисления верхних границ целевой функции на подмножествах, заданных частичными решениями. Найдены легко проверяемые достаточные условия равенства нулю компонент оптимальных решений задач Лидера и Последователя на подмножествах, задаваемых частичными решениями.

3. Разработаны алгоритмы локального поиска для построения приближенных решений дискретной задачи конкурентного размещения предприятий. Предложена процедура локального поиска с использованием обобщенных окрестностей, позволяющая получать близкие к оптимальным приближенные решения. Предложен алгоритм стохастического локального поиска, использующий процедуру разбиения задачи нижнего уровня на подзада-

чи и позволяющий находить качественные решения примеров недоступной для разработанных ранее алгоритмов размерности.

Личный вклад. Основные научные результаты получены автором лично. Вклад соискателя заключается в исследовании сложности поставленных задач, разработке и анализе эффективности точных и приближенных алгоритмов, их реализации и проведении вычислительного эксперимента. Представление изложенных в диссертации результатов, полученных в совместных исследованиях, с соавторами согласовано.

Практическая и теоретическая ценность. Работа носит теоретический и экспериментальный характер. Предложена новая модель конкурентного размещения. Установлена вычислительная сложность поиска ее оптимального решения. Получены численные методы поиска ее точных и приближенных решений. Разработанные методы реализованы в виде программ. Они показали свою эффективность и могут применяться при решении практических задач, а также при преподавании курсов «Исследование операций» и «Теория принятия решений».

Апробация работы. Все разделы диссертации прошли апробацию на следующих конференциях в России и за рубежом:

— Международная конференция «Дискретная оптимизация и исследование операций», Новосибирск, 2013;

— Международная конференция по исследованию операций ЕСС02013, Париж, Франция, 2013;

— Международная конференция по исследованию операций ЕШ1О2012,

Вильнюс, Литва, 2012;

— Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омск, 2012;

— Российская конференция «Дискретная оптимизация и исследование операций», Новосибирск, Алтай, 2010;

— V Азиатская международная школа-семинар «Проблемы оптимизации сложных систем», Кыргызская Республика, г. Бишкек, 2009;

— Научные семинары Института математики им. С.Л. Соболева СО РАН;

Публикации. По теме диссертации автором опубликовано 11 работ, в том числе 5 статей в журналах из списка ВАК.

Объем и структура диссертации. Диссертация состоит из введения, обзора литературы, трех глав, заключения и списка литературы (74 наименования). Объем диссертации — 112 страниц.

Содержание работы. Во введении формулируются цель и задачи исследования, обосновывается актуальность выбранной темы и указываются основные методы решения поставленной задачи. Отмечена новизна полученных результатов и их практическая и теоретическая ценность. Приводятся сведения об апробации работы и публикациях. Кратко излагается содержание работы.

Дискретная задача конкурентного размещения предприятий, которую далее будем для краткости обозначать СотрРЬР, является задачей игрока, именуемого Лидером, в следующей игре Штакельберга [70]. Два игрока, Лидер и Последователь, открывают предприятия с целью «захвата» потре-

бителей и оптимизации своих целевых функций. Вид целевых функций игроков аналогичен целевой функции задачи размещения предприятий с порядком [3, 4, 21, 44]. Требуется отыскать множество предприятий, открытие которых максимизирует прибыль Лидера при условии, что часть потребителей будет захвачена Последователем, который, зная решение Лидера, откроет свои предприятия максимизируя свою прибыль.

Для формальной записи задачи введем обозначения. / = {1,... , т} — множество предприятий (мест возможного размещения предприятий);

3 = {1,..., п} — множество потребителей;

/г, г £ I — затраты Лидера на открытие предприятия г;

г £ I — затраты Последователя на открытие предприятия г; Рг7-,г £ 1,э Е 3 — доход, получаемый предприятием Лидера г при обслуживании потребителя

€ /,^ е 3 — доход, получаемый предприятием Последователя г при обслуживании потребителя 3.

Полагается, что выбор предприятия, обслуживающего потребителя 3^3 производится с учётом предпочтений потребителя 3. Будем считать, что они задаются отношением линейного порядка >4 на множестве I. Для г, к € I отношение г У^ к означает, что из двух открытых предприятий г и к для потребителя 3 е 3 более предпочтительным является предприятие г. Отношение г ^ к означает, что либо г к, либо г = к.

Введем следующие переменные, аналогичные переменным классиче-

ской задачи размещения предприятий:

Х{ — переменная, равная единице, если Лидер открывает предприятие г Е /, и принимающая значение ноль в противном случае;

Хц — переменная, принимающая значение единица, ?сли предприятие I € /, открытое Лидером, оказывается наиболее предпочтительным для потребителя з 3 среди всех открытых Лидером предприятий, и ноль в противном случае;

Х[ — переменная, равная единице, если Последователь открывает предприятие г € и принимающая значение ноль в противном случае; хц — переменная принимающая значение единица, если предприятие г е /, открытое Последователем, оказывается наиболее предпочтительным для потребителя з € 3 среди всех предприятий, открытых как Лидером, так и Последователем, и ноль в противном случае.

С использованием введенных переменных задача СотрРЬР формулируется как следующая задача двухуровневого программирования [24]:

шах

(24)1(243)

(1)

(2)

Х{ ^ Хц, 2 £ I, ] б 3, х^ху е {0,1}, 1е1,зеЗ\

((хг), (¿¿¿)) — оптимальное решение задачи (5)—(8);

(3)

(4)

+ ^ 1> ге1,з е 3\

(6)

^ ) 2 £ /, £ «7 5 е {0,1}, г & I,] е ■}.

(7)

(8)

Сформулированная задача (1)-(8) включает задачу верхнего уровня (1)-(4) и задачу нижнего уровня (5)—(8), в которой допустимое решение задачи (1)-(4) выступает в качестве параметров. Задачу верхнего уровня будем обозначать через £. Её допустимое решение ((хг-), (х^)) далее будем обозначать через X. Задачу нижнего уровня при фиксированном X — через а задачу (1)-(8) целиком, соответственно, через (£,5). Целевую функцию (1) задачи £ будем считать целевой функцией задачи (£,#).

Целевая функция (1) задачи £ выражает величину прибыли, получаемой Лидером с учетом потери части потребителей, захваченных Последователем. Ограничения (2)-(4) являются ограничениями задачи размещения с порядком. Неравенства (2) гарантируют, что в случае, если предприятие г открыто Лидером, потребитель з не будет обслуживаться в предприятии менее привлекательном, чем г. Эти же неравенства гарантируют, что для обслуживания каждого потребителя может быть выбрано только одно предприятие, открытое Лидером. Целевая функция (5) задачи $(Х) выражает величину прибыли, получаемой Последователем. Неравенства (6) реализуют условия захвата потребителей Последователем при известном решении

Лидера. Также эти ограничения показывают, что Последователь не может открыть свое предприятие в месте, где уже открыто предприятие Лидера. Остальные ограничения задачи $(Х) являются ограничениями классической задачи размещения предприятий.

Допустимым решением задачи (£, 39 будем считать пару (X, 2), где X — допустимое решение задачи = ((¿¿)> (%)) ~ оптимальное реше-

ние задачи $(Х). Значение целевой функции (1) на допустимом решении (Х,2) задачи (£,3) обозначим через Ь{Х,2).

Поскольку при некоторых допустимых решениях X задачи £ задача $(Х) может иметь несколько оптимальных решений, вопрос выбора решения Последователя требует конкретизации. В литературе [8, 24] принято выделять два случая: среди оптимальных решений задачи нижнего уровня выбирается то, которое является наиболее либо же наименее выгодным с точки зрения целевой функции (1). Формально, допустимое решение (X, 2) задачи (£, 39 называется гарантированным (в других источниках пессимистическим) решением задачи (£, 5Г), если Ь(Х,2) ^ Ь(Х,2) для всякого оптимального решения 2 задачи ${Х). Допустимое решение (X, 2) задачи (£, 3) называется оптимистическим решением задачи (£, 5Г), если Ь(Х, 2) > Ь(Х, 2) для всякого оптимального решения 2 задачи $(Х).

Заметим, что в случае, когда X нулевое, для построения допустимого гарантированного (оптимистического) решения задачи (£, 39 достаточно взять любое оптимальное решение задачи $(Х). Для любого ненулевого допустимого решения X задачи £ соответствующее допустимое гаранти-

рованное (оптимистическое) решение (X, 2) может быть построено в два этапа. На этапе 1 при фиксированном решении X решается задача $(Х) и вычисляется оптимальное значение Г*(Х) ее целевой функции. Далее, для каждого з £ 7 через г^{х) обозначим наиболее предпочтительное для ] предприятие, открытое Лидером, то есть такое к £ /, что Хк = 1 и к { для всех г £ / таких, что Х{ = 1. На этапе 2 при фиксированном X решается следующая вспомогательная задача ^(Х):

ХХ'ОФ'Х , е#г(9)

зез <6/

- + X) £ ^ ^ (X); (10)

¿е/ ге/

Х1 + г1+ ^ 1» г £/,.?'£«/; (11)

^ Яу, г £7,7 £7; (12)

£ {0,1}, (13)

Ограничение (10) обеспечивает то, что в качестве допустимых решений выступают только оптимальные решения задачи $(Х). Целевая функция (9) выражает величину дохода, которую теряет Лидер при открытии предприятий Последователя: для гарантированных решений (9) максимизируется, а для оптимистических минимизируется. Оптимальное решение 2 = {{'¿г), (%)) этой задачи дает допустимое решение (X, 2) задачи (£,#). При этом величина Ь(Х, 2) будет одной и той же при любом оптимальном решении 2 вспомогательной задачи 3(Х).

Допустимое гарантированное решение (X*, 2*) будем называть оптимальным гарантированным решением, если Ь(Х*,2*) ^ Ь(Х,2) для всякого допустимого гарантированного решения (X, 2). Приближенным гарантированным решением будем называть произвольное допустимое гарантированное решение. Приближенное гарантированное решение (X, 2) будем называть (1 — е) -приближенным гарантированным решением, если Ь(Х, 2) ^ (1 — е)Ь(Х*, 2*), где (X*, 2*) — оптимальное гарантированное решение. Аналогичную терминологию будем применять, говоря о допустимых оптимистических решениях.

В обзоре литературы, представленном в данной работе, даются описание области конкурентных задач размещения, разнообразие постановок и направления их исследования. Приводится классификация моделей по количеству игроков, правилам совершения ими хода, виду их целевых функций, пространству, в котором происходит игра, модели поведения потребителей и другим факторам.

Глава 1 посвящена вычислительной сложности задачи СотрРЬР. Дается краткий обзор известных результатов, касающихся вычислительной сложности задач конкурентного размещения. В разд. 1.1 рассматривается частный случай исследуемой задачи, в котором стоимости открытия предприятий равны нулю. Доказана

Теорема 2. Задача СотрРЬР при = $ = 0 для всех г € I и

€ {0,1} для всех г £ 1,3 € 3 является Е^-трудной. Разд. 1.2 посвящён важному случаю задачи СотрРЬР, в котором по-

требители и места возможного размещения предприятий располагаются в вершинах некоторого графа с заданными длинами ребер. Предпочтения потребителей в таком случае задаются расстояниями в данном графе. Доказана

Теорема 4. Задача СотрРЬР на графе-звезде при р^ = для всех г Е Е 3 и Рщ = рщ для всех £ 7, ^ Е 7 является ЫР-трудной.

Вторая глава посвящена алгоритму поиска решений с априорной оценкой точности для задачи СотрРЬР. В разд. 2.1 приводится общая схема метода ветвей и границ. Разд. 2.2 посвящен описанию процедуры вычисления верхней границы для оптимальных значений целевой функции задачи СотрРЬР.

Для всех з Е .7 матрицы доходов полагаем монотонными относительно порядка то есть для любых г, к Е 7, г У] к имеем р^ ^ р^, ^ ^

Вектор у Е {0,1, *}то назовем частичным решением. Вектор х Е Вт назовем продолжением у, если х^ = уг- для всех г Е 7 таких, что г/г Ф *. Положим 1°{у) = {г Е 1\у{ = 0}, 1\у) = {г Е 7|уг- = 1}. Задачу (£,£) с ограничениями Х{ = уг \/г Е 7°(у) и /1(у) будем обозначать (£(г/),#).

В основе вычисления верхней границы Н (у) для значений целевой функции задачи (£(у), 5Г) лежит построение системы подмножеств {7)(у)}, где 1^{у) С 7 для всех Е .7, с использованием которой удается сформулировать достаточные условия захвата потребителей Последователем.

Лемма 4. Пусть (Х,2), X = ((я,-), (а?у)), Я = (г^)), — <?о-пустимое гарантированное решение задачи (£(?/),#) для частичного ре-

шения у. Для всякого £ 7 такого, что Рщ0Хщ0 > 0 для некоторого г0 1]0{у), выполняется равенство = 1-

Рассмотрим следующую задачу, которую будем называть оценочной и обозначать 03(у):

ж, гЕ^+ЕЕ ^

^ ъ £ 11

Х{ = у{, I 6 и 11(у)',

хьщ е {о, 1}, г е е з.

Теорема 5. Пусть у — частичное решение, (X, 2) — оптимальное некооперативное решение задачи (£(у),$), Х° — оптимальное решение задачи 03(у). Справедливо неравенство Ь(Х,2) ^ В(Х°).

В разд. 2.3 приводится детальное описание схемы метода ветвей и границ с результатами её экспериментального исследования.

Третья глава посвящена алгоритмам локального поиска для задачи СотрРЬР. В разд. 3.1 приводится процедура локального поиска поиска по окрестности специального вида и сравниваются различные стратегии просмотра данной окрестности. В разд. 3.2 на основе данной процедуры локального поиска строится метод поиска по обобщенной окрестности.

Многократное вычисление значения целевой функции в процессе просмотра окрестности является затратной процедурой и не может применяться для решения примеров большой размерности. Разд. 3.3 посвящен процедуре быстрой оценки значения целевой функции.

Зафиксируем решение Лидера X = ((а:г), (х^)), и пусть Х{0 = 1 для некоторого «о € I- Тогда для всех ] € <7 для г £ / таких, что ¿о г, в силу ограничений (6) имеем г^ = 0. Пользуясь этим свойством задачи &(Х), удается предложить процедуру разбиения, для которой верна

Лемма 6. Процедура разбиения имеет трудоемкость 0(п3т) и даёт на выходе разбиение множества потребителей {и набор попарно не пересекающихся множеств предприятий Для каждого £ = 1,..., Т и каждого ] £ если i г^{х) для некоторого гб/, то г £ .

Рассматривая вместо задачи $(Х) набор подзадач где каж-

дая подзадача &(Х) получена из ограничением множества индексов на множество потребителей <7* и множество предприятий в силу леммы 6, целевую функцию (5) задачи ^(Х)

- ^ +Е Е = Е ( ~ Е +Е Е

г'е/ Ш Í=l \ iz.lt /

можно максимизировать для каждого £ отдельно.

Для дальнейшего сокращения вычислительных затрат, вместо поиска наименее выгодного для Лидера оптимального решения Последователя для каждой полученной подзадачи, алгоритм использует процедуру внутреннего локального поиска. В разд. 3.4 излагается метод стохастического

локального поиска, использующий описанную процедуру оценки значения целевой функции при просмотре соседних решений.

Предложенные алгоритмы реализованы на языке программирования С#. Численные эксперименты показали, что предложенные методы способны находить качественные локальные оптимумы в условиях строгих временных ограничений. Использование процедур сокращения вычислительных затрат, описанных в разд. 3.3, позволяет существенно повысить размерность успешно решаемых примеров.

В заключении приводятся основные результаты диссертации.

Публикации автора по теме диссертации.

1. В. Л. Береснев, А. А. Мельников. Приближённые алгоритмы для задачи конкурентного размещения предприятий. Дискретн. анализ и исслед. опер., 2010, Т. 17, №6, С. 3-19.

2. В. Л. Береснев, Е. Н. Гончаров, А. А. Мельников. Локальный поиск по обобщённой окрестности для задачи оптимизации псевдобулевых функций. Дискретн. анализ и исслед. опер., 2011, Т. 18, №4, С. 3-16.

3. В. Л. Береснев, А. А. Мельников. Метод ветвей и границ для некооперативной задачи конкурентного размещения предприятий. Дискретн. анализ и исслед. опер., 2014, Т. 21, №2, С. 3-23.

4. А. А. Мельников. Рандомизированный локальный поиск для дискретной задачи конкурентного размещения предприятий. Автоматика и телемеханика, 2014, №4. С 134-152.

5. А. А. Мельников. Вычислительная сложность дискретной задачи конкурентного размещения предприятий. Дискретн. анализ и исслед. опер., 2014, Т. 21, №4, С. 62-79.

6. Melnikov A., Beresnev V., Kochetov Yu., Computational complexity of the discrete competitive facility location problem. ECC02013 Conf. Proc. 2013. P. 88.

7. А. А. Мельников. Рандомизированный локальный поиск для дискретной задачи конкурентного размещения предприятий. Материалы конференции «Дискретная оптимизация и исследование операций». Новосибирск: Изд-во ин-та математики. 2013. С. 61.

8. Melnikov A., Beresnev V. Branch and bound method for the competitive facility location problem. EUR02012 Conf. Proc. 2012. P. 204.

9. А. А. Мельников. Результаты экспериментального исследования алгоритма ветвей и границ для задачи конкурентного размещения предприятий. Материалы конференции «Проблемы оптимизации и экономические приложения». Омск: Изд-во Ом. гос. ун-та. 2012. С. 152.

10. В. JI. Береснев, А. А. Мельников. Алгоритмы локального поиска по обобщенной окрестности для задачи конкурентного размещения предприятий. Материалы конференции «Дискретная оптимизация и исследование операций». Новосибирск: Изд-во ин-та математики. 2010. С. 110.

11. Мельников А. Метод ветвей и границ для задачи конкурентного размещения предприятий. Материалы конференции «Проблемы оптимизации сложных систем». 2009. Новосибирск: Труды ИВМ и МГ. С. ???

Обзор литературы

Задачи размещения формируют обширный класс математических моделей исследования операций. В приложениях данные модели возникают при создании коммуникационных сетей, размещении средств обслуживания, магазинов, складов, постов служб экстренного реагирования. Ввиду тесной связи с фундаментальными проблемами исследования операций, задачи размещения являются богатой темой для теоретических и экспериментальных исследований [27]. В большинстве таких моделей лицо, принимающее решение, максимизирует получаемую прибыль или минимизирует затраты на обслуживание клиентов. Данная ситуация может быть обобщена на случай, когда несколько лиц (игроков), действуя в общем для них пространстве, принимают решения независимо. Целевые функции игроков как правило находятся в противоречии друг с другом, поэтому подобные постановки относятся к области конкурентных задач размещения. Первой работой в данном направлении является статья Хоттелинга [41], рассматривающая эгоистическое поведение двух игроков, обслуживающих клиентов, располагающихся на линии (шоссе, побережье и т.п.). Позже появились более богатые модели, интересные как для экономики и теории игр, так и для методов оптимизации и исследования операций. Обзоры таких моделей представлены, например, в [35, 39, 46].

В настоящее время область конкурентных задач размещения бурно развивается, и разнообразие постановок стремительно увеличивается. Меж-

ду собой постановки различаются по области возникновения, количеству игроков, правилам совершения ими хода, виду их целевых функций, пространству, в котором происходит игра. Отличаются также модели поведения потребителей, ограничения на открытие предприятий, вид этих предприятий и другие аспекты.

Область возникновения. Модели конкурентного размещения возникают в теории голосования. В [20] пользователи и места возможного размещения предприятий образуют подмножества множества вершин некоторой сети. Две стороны последовательно, сначала одна, а затем вторая, открывают по р предприятий в некоторых из возможных мест размещения. Каждый потребитель предпочитает сторону, которой принадлежит ближайшее к нему предприятие. Задача по поиску множества Кондорсе [38] состоит в отыскании таких р предприятий, которые предпочитались бы простым большинством потребителей при любом размещении предприятий второй стороны. Очевидно, такое множество существует не всегда. Задача по поиску множества Симпсона [34] состоит в выборе таких р предприятий, которые предпочитались бы наибольшим числом потребителей при условии, что вторая сторона действует оптимальным образом.

Другим источником постановок является анализ худшего случая. В [14]| рассматривается задача размещения постов экстренных служб. Размещающая сторона выбирает места открытия постов, а также защищает некоторые из них от разрушения. Затем атакующая сторона выбирает не более

г незащищенных постов, которые будут разрушены. После нападения потребители услуг будут перераспределены между уцелевшими постами, и стоимость оказания им услуг изменится. Проблема состоит в выборе мест размещения постов, а также в выборе тех постов, которые должны быть защищены, с тем, чтобы минимизировать суммарные затраты на открытие и защиту постов, а также на оказание услуг потребителям после нападения. Предполагается, что атакующая сторона действует наиболее невыгодным для размещающей образом. Модели защиты от нападения рассматриваются также в [50, 65, 72].

Количество игроков и правила совершения ими хода. Наиболее популярным в литературе является случай двух игроков, однако встречаются и иные постановки. В [52] рассматривается ситуация единовременного размещения предприятий п игроками. Каждый игрок размещает единственное предприятие в некоторой точке компактного подмножества К2. Целевые функции игроков имеют схожий вид и выражают суммарные затраты на транспортировку продукции к остальным открываемым предприятиям, а также потребителям, располагающимся в конечном множестве точек. Затраты — полунепрерывные снизу функции расстояния. Показано, что для расстояний, заданных ^-нормой в задаче существует равновесие Нэша.

В [53] фирма, входящая на рынок, представленный сетью, открывает в вершинах данной сети свои предприятия, устанавливает на них объемы

производства и определяет схему доставки продукции к потребителям. Полагается, что консолидированная реакция присутствующих на рынке конкурирующих фирм представляется равновесием Курно-Нэша [73], использующим решение входящей фирмы в качестве параметров. Реакция конкурентов описывается системой вариационных равенств, которая используется в модели для вычисления прибыли входящей фирмы.

Список литературы диссертационного исследования кандидат наук Мельников, Андрей Андреевич, 2014 год

Список литературы

1. Береснев В. Л. Верхние оценки для целевых функций дискретных задач конкурентного размещения предприятий // Дискрет, анализ и ис-след. операций. 2008. Т. 15, № 4. С. 3-24.

2. Береснев В. Л. Дискретные задачи размещения и полиномы от булевых переменных. Новосибирск: Изд-во ин-та математики, 2005. 408 с.

3. Береснев В. Л., Гончаров Е. Н., Мельников А. А. Локальный поиск по обобщённой окрестности для задачи оптимизации псевдобулевых функций // Дискрет, анализ и исслед. операций. 2011. Т. 18, № 4. С. 3-16.

4. Васильев И. Л., Климентова К. Б. Метод ветвей и отсечений для задачи размещения с предпочтениями клиентов // Дискрет, анализ и исслед. операций. Т. 16, № 2. С. 21-41.

5. Васильев И. Л., Климентова К. Б., Кочетов Ю. А. Новые нижние оценки для задачи размещения с предпочтениями клиентов // Журнал вычислительной математики и математической физики. 2009. Т. 49, № 6. С. 1055-1066.

6. Давыдов И. А. Алгоритмы локального поиска для задачи о (г|р)-центроиде: Кандидатская диссертация / ИМ СО РАН. 2013.

7. Давыдов И. А. Локальный поиск с запретами для дискретной задачи о (г|р)-центроиде // Дискретный анализ и исследование операций. 2012. Т. 19, № 2. С. 19-40.

8. Гермейер Ю. Б. Игры с непротивоположными интересами. Москва:

Наука, 1976. 328 с.

9. Aboolian R., Berman О., Krass D. Competitive facility location and design problem // European J. Oper. Res. 2007. Vol. 182. P. 40-62.

10. Aboolian R., Berman O., Krass D. Optimizing pricing and location decisions for competitive service facilities charging uniform price // Journal of the Operational Research Society. 2008. Vol. 59. P. 1506-1519.

11. Aboolian R., Berman O., Krass D. Optimizing pricing and location decisions for competitive service facilities charging uniform price // Journal of the Operational Research Society. 2008. Vol. 59. P. 1506-1519.

12. Библиотека тестовых примеров «Дискретные задачи размещения». URL: http: //math. nsc. ru/АР/benchmarks/index. html.

13. Ahn H.-K., Cheng S.-W., Cheong O. et al. Competitive facility location: the Voronoi game // Theoret. Comput. Sci. 2004. Vol. 310. P. 457-467.

14. Aksen D., Aras N. A bilevel fixed charge location model for facilities under imminent attack // Сотр. Oper. Res. 2012. Vol. 39. P. 1364-1381.

15. Alekseeva E., Kochetov Y. Matheuristics and exact methods for the discrete (rjp)-centroid problem // Metaheuristics for bi-level optimization / Ed. by E.-G. Talbi, L. Brotcorne. Berlin: Springer, 2013.

16. Ashtiani M. G., Makui A., Ramezanian R. A robust model for a leader-follower competitive facility location problem in a discrete space // Applied Mathematical Modelling. 2013. P. 62-71.

17. Benati S. An Improved Branch &; Bound Method for the Uncapacitated Competitive Location Problem // Annals of Operations Research. 2003.

Vol. 122. P. 43-58.

18. Bhadury J., Eiselt H. A., Jaramillo J. An alternating heuristic for medianoid and centroid problems in the plane // Сотр. Oper. Res. 2003. Vol. 30. P. 553-565.

19. Campos-Rodriguez C., Santos-Peate D., Moreno-Perez J. An exact procedure and LP formulations for the leader—follower location problem // TOP. 2010. Vol. 18, no. 1. P. 97-121.

20. Campos-Rodriguez С. M., Moreno-Pérez J. A. Multiple voting location problems // European J. Oper. Res. 2008. Vol. 191, no. 2. P. 437-453.

21. Canovas L., Garcia S., Labbe M., Marin A. A strengthened formulation for the simple plant location problem with order // Operations Research Letters. 2007. Vol. 35. P. 141-150.

22. Cheong O., Har-Peled S., Linial N., Matousek J. The One-Round Voronoi Game // Discrete Comput. Geom. 2004. Vol. 31. P. 125-138.

23. Davydov I., Kochetov Y., Carrizosa E. [!! найти выходные данные!!]А local search heuristic for the (r|p)-centroid problem in the plane // Сотр. Oper. Res. 2013.

24. Dempe S. Foundations of Bilevel Programming. Dortrecht: Kluwer Acad. Publ., 2002. 332 p.

25. Drezner Т., Drezner Z. Finding the optimal solution to the Huff based competitive location model // Computational Management Science. 2004. Vol. 1. P. 193-208.

26. Drezner Z. Competitive location strategies for two facilities // Regional

science and urban economics. 1982. Vol. 12. P. 485-493.

27. Drezner Z. Facility Location. A Survey of Applications and Methods. Berlin: Springer, 1995.

28. Eiselt H. A., Laporte G. Sequential location problems // European J. Oper. Res. 1996. Vol. 96. P. 217-231.

29. Fernandez J., Hendrix E. M. Recent insights in Huff-like competitive facility location and design // European J. Oper. Res. 2013. Vol. 227. P. 581-584.

30. Fernandez J., Pelegrin B., Plastria F., Toth B. Solving a Huff-like competitive location and design model for profit maximization in the plane // European J. Oper. Res. 2007. Vol. 179. P. 1274-1287.

31. Friesz T. L., Tobin R. L., Miller T. Existance Theory for Spatially Competitive Network Facility Location Models // Annals of Operations Research. 1989. Vol. 18. P. 267-276.

32. Garey M. R., Johnson D. S. Computers and intractability: a guide to the theory of NP-completeness. San Francisco, Calif.: W. H. Freeman and Company., 1979. 338 p.

33. Glover F., Laguna M. Tabu search. Dordrecht: Kluwer Academic, 1997.

34. Hakimi S. On locating new facilities in a competitive environment // European J. Oper. Res. 1983. Vol. 12. P. 29-35.

35. Hakimi S. Locations with spatial interactions: competitive locations and games // Discrete Location Theory / Ed. by P. Mirchandani, R. Francis. Wiley, 1990. P. 439-478.

36. Hakimi S. L. p-Median theorems for competitive locations // Annals of

Operations Research. 1986. Vol. 6. R 77-98.

37. Hansen P., Mladenovic N. Variable neighborhood search: principles and applications // European J. Oper. Res. 2001. Vol. 130. P. 449-467.

38. Hansen P., Thisse J.-F. Outcomes of voting and planning // Journal of Public Economics. 1981. Vol. 16. P. 1-15.

39. Hansen P., Thisse J.-F., Wendell R. Equilibrium analysis for voting and competitive location problems // Discrete Location Theory / Ed. by P. Mirchandani, R. Francis. Wiley, 1990. P. 479-502.

40. Hoos H. H., Stutzle T. Stochastic Local Search: Foundations and Applications. Morgan Kaufmann Publishers, 2005.

41. Hotelling H. Stability in competition // Economic J. 1929. Vol. 39. P. 41-57.

42. Kernigan B.W. L. S. An efficient heuristic procedure for partitioning graphs // Bell Syst. Technical J. 1970. Vol. 49. P. 291-307.

43. Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by simulated annealing // Science. 1983. Vol. 220. P. 671-680.

44. Krarup J., Pruzan P. M. The simple plant location problem: survey and synthesis // Europ. J. Oper. Res. 1983. no. 12. P. 36-81.

45. Kress D., Pesch E. (r|p)-centroid problems on networks with vertex and edge demand // Comp. Oper. Res. 2012. Vol. 39. P. 2954-2967.

46. Kress D., Pesch E. Sequential competitive location on networks // European J. Oper. Res. 2012. Vol. 217. P. 483-499.

47. Kucukaydin H., Aras N., Altinel I. K. Competitive facility location problem with attractiveness adjustment of the follower: A bilevel programming

model and its solution // European J. Oper. Res. 2011. Vol. 208. R 206-220.

48. Kucukaydin H., Aras N., Altinel I. K. A leader-follower game in competitive facility location // Comp. Oper. Res. 2012. Vol. 39. R 437-448.

49. Labbe M., Hakimi S. L. Market and locational equilibrium for two competitors // Operations Research. 1991. Vol. 39, no. 5. R 749-756.

50. Liberatore F., Scaparra M. R, Daskin M. S. Analysis of facility protection strategies against an uncertain number of attacks: The stochastic R-interdiction median problem with fortification // Comp. Oper. Res. 2011. Vol. 38. P. 357-366.

51. Local search in combinatorial optimization / Ed. by E. H. L. Aarts, J. K. Lensrta. Chichester: John Wiley and sons, 1997. 512 p.

52. Mallozzi L. Noncooperative facility location games // Operations Research Letters. 2007. Vol. 35. P. 151-154.

53. Miller T. C., Friesz T. L., Tobin R. L., Kwon C. Reaction Function Based Dynamic Location Modeling in Stackelberg-Nash-Cournot Competition // Netw. Spat. Econ. 2007. Vol. 7. P. 77-97.

54. Mitten L. G. Branch-and-bound method: general formulation and properties // Oper. Res. 1970. Vol. 18. P. 24-34.

55. Noltemeier H., Spoerhase J., Wirth H. Multiple voting location and single voting location on trees // European J. Oper. Res. 2007. Vol. 181. P. 654-667.

56. Panin A. A., Pashchenko M. G., Plyasunov A. V. Bilevel competitive facility

location and pricing problems // Automation and Remote Control. 2014. Vol. 75. P. 715-727.

57. Pelegrin B., Fernandez P., Perez M. D. G., Hernandez S. C. On the location of new facilities for chain expansion under delivered pricing // Omega. 2012. Vol. 40. P. 149-158.

58. Perez M. D. G., Fernandez P., Pelegrin B. On Price Competition in Location-Price Models with Spatially Separated Markets // TOP. 2004. Vol. 12, no. 2. P. 351-374.

59. Plastria F., Vanhaverbeke L. Aggregation without Loss of Optimality in Competitive Location Models // Netw. Spat. Econ. 2007. Vol. 7. P. 3-18.

60. Plastria F., Vanhaverbeke L. Discrete models for competitive location with foresight // Comp. Oper. Res. 2008. Vol. 35. P. 683-700.

61. Preparata F. P., Shamos M. I. Computational Geometry: An Introduction. New York: Springer-Verlag, 1985.

62. Saiz M. E., Hendrix E. M. T., Fernandez J., Pelegrin B. On a branch-and-bound approach for a Huff-like Stackelberg location problem // OR Spectrum. 2009. Vol. 31. P. 679-705.

63. Santos-Penate D. R., Suarez-Vega R., Dorta-Gonzalez P. The Leader-Follower Location Model // Netw. Spat. Econ. 2007. Vol. 7. P. 45-61.

64. Sarkar J., Gupta B., Pal D. Location equilibrium for cournot oligopoly in spatially separated markets //J. Reg. Sci. 1997. Vol. 37, no. 2. P. 195-212.

65. Scaparra M. P., Church R. L. A bilevel mixed-integer program for critical

©

infrastructure protection planning // Comp. Oper. Res. 2008. Vol. 35. P. 1905-1923.

66. Schaefer M., Umans C. Completeness in the polynomial-time Hierarchy: Part I: A compendium // ACM Sigact News, Complexity Theory Column. 2002. Vol. 37, no. 33. P. 32-49.

67. Shiode S., Yeh K.-Y., Hsia H.-C. Optimal location policy for three competitive facilities // Computers and Industrial Engineering. 2012. Vol. 62. P. 703-707.

68. Slater P. I. Maximin facility location // Journal of Research of the National Bureau of Standards. Sect. B. 1975. Vol. 79. P. 107-115.

69. Spoerhase J. Competitive and Voting Location: Ph.D. thesis / Julius-Maximilians-Universitat Wurzburg. 2010.

70. Stackelberg H. The Theory of the Market Economy. Oxford: Oxford Univ. Press, 1952. 289 p.

71. Stockmeyer L. J. The polynomial-time hierarchy // Theoretical computer science. 1977. Vol. 3. P. 1-22.

72. Uno T., Katagiri H. Single- and multi-objective defensive location problems on a network // European J. Oper. Res. 2008. Vol. 188. P. 76-84.

73. Wie B., Tobin R. A dynamical spatial Cournot-Nash equilibrium model and an algorithm // Comput. Econ. 1997. Vol. 10. P. 15-45.

74. Yao A. Probabilistic computations: Toward a unified measure of complexity // Proc. 18th IEEE Sympos. Foundat. Comput. Sci. (FOCS). 1977. P. 222-227.