Содержание к диссертации
Введение
Глава 1. Вычислительная сложность 29
1.1. Задача конкурентного размещения с нулевыми фиксированными затратами 30
1.2. Задача конкурентного размещения на графе-звезде 44
1.3. Основные результаты главы 47
Глава 2. Метод ветвей и границ 48
2.1. Общая схема 49
2.2. Верхняя граница и функция ветвления 52
2.3. Релизация метода и результаты вычислительных экспериментов 61
2.4. Основные результаты главы 68
Глава 3. Методы локального поиска 69
3.1. Алгоритмы локального улучшения 70
3.2. Алгоритм поиска по обобщённой окрестности 77
3.3. Оценка значения целевой функции 83
3.4. Стохастический локальный поиск 92
3.5. Основные результаты главы 101
Заключение 104
Список литературы
- Задача конкурентного размещения на графе-звезде
- Основные результаты главы
- Релизация метода и результаты вычислительных экспериментов
- Алгоритм поиска по обобщённой окрестности
Задача конкурентного размещения на графе-звезде
Задачи размещения формируют обширный класс математических моделей исследования операций. В приложениях данные модели возникают при создании коммуникационных сетей, размещении средств обслуживания, магазинов, складов, постов служб экстренного реагирования. Ввиду тесной связи с фундаментальными проблемами исследования операций, задачи размещения являются богатой темой для теоретических и экспериментальных исследований [27]. В большинстве таких моделей лицо, принимающее решение, максимизирует получаемую прибыль или минимизирует затраты на обслуживание клиентов. Данная ситуация может быть обобщена на случай, когда несколько лиц (игроков), действуя в общем для них пространстве, принимают решения независимо. Целевые функции игроков как правило находятся в противоречии друг с другом, поэтому подобные постановки относятся к области конкурентных задач размещения. Первой работой в данном направлении является статья Хоттелинга [41], рассматривающая эгоистическое поведение двух игроков, обслуживающих клиентов, располагающихся на линии (шоссе, побережье и т.п.). Позже появились более богатые модели, интересные как для экономики и теории игр, так и для методов оптимизации и исследования операций. Обзоры таких моделей представлены, например, в [35, 39, 46].
В настоящее время область конкурентных задач размещения бурно развивается, и разнообразие постановок стремительно увеличивается. Между собой постановки различаются по области возникновения, количеству игроков, правилам совершения ими хода, виду их целевых функций, пространству, в котором происходит игра. Отличаются также модели поведения потребителей, ограничения на открытие предприятий, вид этих предприятий и другие аспекты.
Область возникновения. Модели конкурентного размещения возникают в теории голосования. В [20] пользователи и места возможного размещения предприятий образуют подмножества множества вершин некоторой сети. Две стороны последовательно, сначала одна, а затем вторая, открывают по р предприятий в некоторых из возможных мест размещения. Каждый потребитель предпочитает сторону, которой принадлежит ближайшее к нему предприятие. Задача по поиску множества Кондорсе [38] состоит в отыскании таких р предприятий, которые предпочитались бы простым большинством потребителей при любом размещении предприятий второй стороны. Очевидно, такое множество существует не всегда. Задача по поиску множества Симпсона [34] состоит в выборе таких р предприятий, которые предпочитались бы наибольшим числом потребителей при условии, что вторая сторона действует оптимальным образом.
Другим источником постановок является анализ худшего случая. В [14] рассматривается задача размещения постов экстренных служб. Размещающая сторона выбирает места открытия постов, а также защищает некоторые из них от разрушения. Затем атакующая сторона выбирает не более г незащищенных постов, которые будут разрушены. После нападения потребители услуг будут перераспределены между уцелевшими постами, и стоимость оказания им услуг изменится. Проблема состоит в выборе мест размещения постов, а также в выборе тех постов, которые должны быть защищены, с тем, чтобы минимизировать суммарные затраты на открытие и защиту постов, а также на оказание услуг потребителям после нападения. Предполагается, что атакующая сторона действует наиболее невыгодным для размещающей образом. Модели защиты от нападения рассматриваются также в [50, 65, 72].
Количество игроков и правила совершения ими хода. Наиболее популярным в литературе является случай двух игроков, однако встречаются и иные постановки. В [52] рассматривается ситуация единовременного размещения предприятий п игроками. Каждый игрок размещает единственное предприятие в некоторой точке компактного подмножества К. . Целевые функции игроков имеют схожий вид и выражают суммарные затраты на транспортировку продукции к остальным открываемым предприятиям, а также потребителям, располагающимся в конечном множестве точек. Затраты — полунепрерывные снизу функции расстояния. Показано, что для расстояний, заданных / -нормой в задаче существует равновесие Нэша.
В [53] фирма, входящая на рынок, представленный сетью, открывает в вершинах данной сети свои предприятия, устанавливает на них объемы производства и определяет схему доставки продукции к потребителям. Полагается, что консолидированная реакция присутствующих на рынке конкурирующих фирм представляется равновесием Курно-Нэша [73], использующим решение входящей фирмы в качестве параметров. Реакция конкурентов описывается системой вариационных равенств, которая используется в модели для вычисления прибыли входящей фирмы.
В работа [67] рассматривается отрезок прямой, на котором с известной плотностью распределен потребительский спрос. Три конкурирующие фирмы размещают на отрезке по одному предприятию. Предприятие захватывает те точки, для которых оно является ближайшим из открытых. Авторы отмечают, что равновесия Нэша в данной ситуации не существует, однако при фиксированном порядке открытия предприятий равновесие Штакельберга выражается в явном виде.
Ситуации одновременного принятия решений зачастую рассматривают двухэтапными. На первом этапе конкурирующие фирмы выбирают места размещения своих предприятий, после чего, когда результат выбора известен, принимается решение о количестве производимой продукции или цене на нее. Условия существования равновесия, а также его свойства в таких постановках изучаются в [49, 64].
В [13] предлагается выигрышная стратегия для второго игрока в следующей игре. Игровое поле представляет собой отрезок прямой или окружность. За ход игрок размещает в некоторой точке поля ровно одно свое предприятие. После того, как игроки по очереди сделают поп ходов, каждая точка игрового поля переходит к тому из игроков, чьё предприятие оказывается к ней ближе. Игрок, захвативший большую часть игрового поля, побеждает. Поскольку области обслуживания предприятий образуют диаграмму Вороного [61], игра была названа авторами игрой Вороного и рассматривалась также в однораундовом варианте, когда за один ход игроки, сначала первый, а затем второй, размещают все п своих предприятий [22]. В однораундовом случае уже первый игрок имеет выигрышную стратегию.
Основные результаты главы
Бурно развернувшееся в конце XX в. исследование надклассов класса NP полиномиальной иерархии привело к появлению множества результатов о вычислительной сложности актуальных задач [66]. Среди таковых следует выделить работы [23, 55], посвященные вычислительной сложности конкурентных задач размещения. Обзор результатов о сложности задач, связанных с задачей о (гр)-центроиде можно найти в [2].
Специфика игры Штакельберга, связанная с наличием самостоятельно действующего игрока, совершающего ход вторым, определяет её двухуровневую природу. Первый игрок может вычислить значение своей целевой функции только узнав, каким будет ход конкурента, решающего свою оптимизационную задачу. Таким образом, естественной формализацией подобных игровых постановок становятся модели двухуровневого математического программирования [24]. В вычислительном плане двухуровневые модели оказываются сложнее большинства известных NP-трудных задач, размещаясь на более высоких ступенях полиномиальной иерархии [71]. Класс задач S2 содержит задачи распознавания, разрешимые за полиномиальное время недетерминированной машиной Тьюринга с оракулом для класса NP. В разд. 1.1 показано, что задача CompFLP является Х -трудной в случае, когда фиксированные затраты на открытие предприятий равны нулю, а матрицы доходов от обслуживания потребителей булевы.
В [6] рассматривается частный случай задачи CompFLP, в котором множество потребителей и множетво мест, доступных для открытия предприятий, совпадают со множеством вершин некоторого графа. Для потребителей более предпочтительными полагаются предприятия, расположенные к ним ближе в смысле расстояний в данном графе. В случае, когда доход от обслуживания потребителя не зависит от обслуживающего его предприятия, а граф является цепью или простым циклом, в [6] предлагается схема динамического программирования, имеющая полиномиальную трудоемкость. В разд. 1.2 показано, что задача CompFLP становится NP-труд-ной на графах-звездах.
Задача конкурентного размещения с нулевыми фиксированными затратами Пусть задано множество булевых переменных V = X U Z, где X = {xi,...,xTO}, Z = {zi,...,zn}, ХП Z = 0. Рассмотрим формулу Ф = Зхі ... 3xTOVzi. .. Vzn( без свободных переменных. Задача по определению выполнимости формулы Ф («существует ли такое означивание 7 переменных множества X, что для любого означивания а переменных множества Z верно ( т 7)ty? = true?») получила в литературе обозначение 3ySat.
Теорема 1 (О вычислительной сложности ЗУ Sat, [66]) Задача ЗУ Sat является Sf-полной. Литералом над множеством переменных V назовем переменную v Є V или ее отрицание v, а термом — конъюнкцию литералов. Далее будем полагать, что формула ср имеет вид ip = \/&=і Ь гДе каждый терм t& содержит ровно один литерал над множеством переменных X и три литерала над множеством Z. Задачу ЗУ Sat с перечисленными ограничениями на вид формулы ip обозначим 3\izSat.
Утверждение 1. Задача BiizSat является Т -полной. Доказательство. Без ограничения общности можно считать, что формула р задана в 3-ДНФ [32] и все термы формулы ср содержат переменные множества Z. Далее термы вида t = (xi&X2&z) заменим на Vzt(xi&zt&z) V (x2&zt&z) для новой переменной zt, которую добавим ко множеству Z. Термы вида t = (Z1&Z2&Z3) заменим на 3xt(xt&Zi&Z2&Z3) для новой переменной Xt, которую добавим ко множеству X. Теперь все термы, содержащие три литерала, имеют виді = (X&Z1&Z2). Каждый такой терм заменим на Vzt(x&Zi&Z2&zt) V (x&Zi&Z2&zt) для новой переменной Zt, которую мы добавим ко множеству Z. Таким образом, произвольный пример задачи BWSat сводится к примеру задачи 3ii Sat.
Рассмотрим пример задачи B Saf, в котором требуется установить выполнимость формулы Ф. Построим пример задачи CompFLP с нулевыми затратами на открытие предприятий, по оптимальному решению которого можно однозначно судить о выполнимости формулы Ф. Для этого нам требуется определить множество потребителей J, множество доступных мест размещения предприятий /, матрицы доходов Лидера и Последователя, (pij) и (qij). Стоимости открытия предприятий Лидера и Последователя, fi и gi, будут нулевыми для всех і Є I. Предпочтения потребителей будем задавать / х -матрицей (г ). Для каждого фиксированного j Є J будем полагать, что числа г , і Є I попарно различны. Тогда для любых і, к Є / соотношение f ij f kj эквивалентно і j к.
Для каждой переменной х Є X и ее отрицания х заведем по одному потребителю. Обозначим их ах и а соответственно. Аналогично, для каждой переменной z Є Z и ее отрицания z заведем по одному потребителю, которых обозначим bz и bz соответственно. Положим Ах = {«х5 Q-x х Є X}, Bz = {bz,bz I z Є Z}. Определим множество предприятий: / = Ах U -Bz-Далее мы подстроим значения числовых параметров задачи таким образом, что в оптимальном решении Лидер откроет свои предприятия в точках множества Ах, а Последователь — в точках Bz, причем предприятие будет открыто ровно в одной из двух точек, соответствующих каждой булевой переменной. Тогда размещению предприятий Лидера можно будет естественным образом сопоставить означивание переменных множествах, а размещению предприятий Последователя — означивание переменных из Z. Здесь и далее под размещением предприятий Лидера и Последователя будем иметь в виду набор значений переменных х = (ХІ),І Є /и z = (z{),i Є / соответственно. Под распределением потребителей будем понимать соответствующие значения переменных (xij) и (%), і Є /, j Є J. Заметим, что они однозначно определяются размещениями ж и z сторон. Для того, чтобы Лидеру было невыгодно открывать предприятия в точках Bz, для каждой переменной z Є Z и ее отрицания z заведем еще по одному потребителю, которых обозначим az и а% соответственно. Положим Az = {cLz,ttz I z Є Z}. При открытии предприятия множества Bz Лидер будет терять доход от обслуживания соответствующего потребителя множества Az, что повлечет неоптимальность такого решения. Аналогично, для каждой переменной х Є X и ее отрицания х заведем еще по одному потребителю. Обозначим их 6Х и Ьх соответственно. Пусть Вх = {&х, &х х Є X}.
Сопоставим каждому терму t формулы (р своего потребителя, jf Множество таких потребителей обозначим Т. Потребитель jt принесет доход Лидеру в случае, если при означивании переменных, соответствующем размещению предприятий сторон, терм t принимает значение true. В противном случае потребитель jt принесет доход Последователю. Таким образом, Последователь будет выбирать размещение, максимизирующее число захваченных потребителей множества Т. В терминах задачи о выполнимости он минимизирует число термов, принимающих значение true. Если ему не удастся сделать это число равным нулю, формула Ф выполнима.
На этом построение множества потребителей завершено. Положим J = AxU xUAzU zUT. Как было анонсировано, поведение потребителя зависит от того, к какому из данных пяти множеств он принадлежит.
Релизация метода и результаты вычислительных экспериментов
Исследуемая задача (,#) представляется в виде задачи максимизации некоторой псевдобулевой функции f(x). Алгоритм ветвей и границ для данной задачи включает начальный шаг и конечное число основных шагов.
Исследование качеств предлагаемого метода производилось на случайно сгенерированных тестовых примерах задачи конкурентного размещения предприятий на сети в виде дерева, взятых в классе примеров TreeNЕ библиотеки тестовых примеров «Дискретные задачи размещения» [12]. Для данных примеров множества I и J совпадают с множеством V вершин некоторого случайного дерева. Процедура построения дерева итеративна и начинается с дерева, состоящего из единственной вершины. На каждой следующей итерации к уже построенному дереву добавляется новая висячая вершина, которая присоединяется к случайной вершине текущего дерева «коротким» ребром с вероятностью 0.9, либо «длинным» ребром с вероятностью 0.1. Длины «коротких» рёбер — случайные числа из интервала [1,15], а «длинных» рёбер — из интервала [100,150]. Стоимость fi и д открытия предприятия в вершине і Є V для Лидера и Последователя — случайно выбранное целое число из интервала [30, 39] и [20, 29] соответственно. Для каждого потребителя j Є J в полученном дереве с заданными длинами ребер более предпочтительным из двух предприятий г, к Є / является то, расстояние до которого меньше. Из целочисленного интервала [5, 9] случайно выбирается значение его бюджета bj потребителя j Є J. Доход pij = qij от обслуживания потребителя j предприятием і полагается равным bj в случае, если расстояние от j до і не превосходит 100. Для значений т, равных 20, 30, 40, 50 и 60, сгенерированы по 20 наборов входных данных задачи конкурентного размещения. Параллельная (многопоточная) реализация алгоритма осуществлена на языке программирования C f. Тестирование проводилось на компьютере под управлением операционной системы Windows Server 2008 R2 с двумя шестиядерными процессорами Intel Xeon Х5675 с тактовой частотой ядер 3.07 ГГц и объёмом ОЗУ 96 Гб. Для решения задач ЦЛП использовалась библиотека классов Microsoft Solver Foundation 3.1 с решателем Gurobi 4.5. В качестве начального приближения выбиралось решение, полученное с помощью алгоритма из [7]. Время работы алгоритма ветвей и границ ограничено одним часом для каждого из примеров.
В табл. 2.1 и 2.2 приведены ключевые показатели работоспособности алгоритма при поиске (1 — е)-приближённого решения для различного числа рабочих потоков: m — число точек на плоскости в примерах данной группы; Р — число рабочих потоков; є — гарантированная относительная погрешность решения; S — число решённых примеров данной группы из 20 возможных; Pavg — средняя по всем примерам данной группы доля отброшенных решений в процентах; mim avg и max — минимальное, среднее и максимальное время в секундах, затраченное алгоритмом на решение примера из данной группы; - "mim avg и Nmax — минимальное, среднее и максимальное числа вершин дерева ветвления, просмотренных алгоритмом при решении примеров данной группы;
GAPm[n, GAP&vg и GAPm&x — минимальное, среднее и максимальное по всем примерам данной группы значения величины H/LTec, где Н — зна " "Г гее чение верхней границы на всем множестве допустимых решении, a L — рекордное значение целевой функции на момент остановки алгоритма; VL&vg — среднее по всем примерам данной группы значение целевой функции Лидера на лучшем найденном гарантированном решении; VF&vg — среднее по всем примерам данной группы значение целевой функции Последователя на лучшем найденном гарантированном решении; l lavg — среднее по всем примерам данной группы число открытых предприятий Лидера в лучшем найденном гарантированном решении; 1 1 avg — среднее по всем примерам данной группы число открытых предприятий Последователя в лучшем найденном гарантированном решении.
Как видно из табл. 2.1, тестовые примеры размерности 20 оказываются простыми: (1 — е)-приближённое гарантированное решение для всех рассматриваемых значений є находится быстрее чем за 10 секунд. При этом алгоритм, работающий в одном потоке, справляется с задачами быстрее, и при росте є время его работы сокращается, как и следовало ожидать. В случае двенадцати потоков время работы возрастает: при балансировке нагрузки рабочих потоков производится дополнительная работа, которая оказывается излишней. Уже на размерности 30 работа в параллельных потоках даёт преимущество, однопоточная реализация начинает проигрывать в скорости. Ускорение, однако, оказывается не двенадцатикратным: время работы сокращается приблизительно в три раза, что опять же является следствием неоптимальной балансировки нагрузки. Время, требуемое для доказательства оптимальности решения в примерах данного класса, исчисляется в зависимости от примера считанными секундами, либо несколькими минутами, но не превышает 15 минут для Р = 1 и 4 минут — для Р = 12. Перелом наблюдается при т = 40. Однопоточная реализация алгоритма доказывает оптимальность найденного решения только для трёх из двадцати предложенных примеров. Однако увеличение числа рабочих потоков, а также увеличение є приводят к существенному росту продуктивности. Для того чтобы в этом убедиться, обратим внимание на значениеpavg, показывающее, какая доля от общего числа решений в среднем по примерам данного класса оказывается просмотренной алгоритмом за отведённое ему время
Алгоритм поиска по обобщённой окрестности
Доказательство. Построение множеств j на 0 шаге процедуры требует ( ) операций. Дальнейшее исполнение процедуры предполагает проход цикла, перед входом в который множество совпадает со множеством потребителей , а условием выхода из которого является отсутствие элементов в . Поскольку на каждом витке цикла из множества удаляется не менее одного элемента, выход из цикла будет достигнут не более чем за шагов. Каждый подобный шаг подразумевает итеративное построение множества t- На каждой итерации происходит просмотр элементов множества , для каждого из которых проверяется пустота множества k Г\ S\. Это требует ( ) операций, следовательно, трудоемкость итерации ( ). В случае, если во время итерации множество t было изменено, условие выхода из цикла не выполнено и алгоритм повторит выполнение процедур итерации. Множество при этом будет иметь меньшую мощность, поэтому таких повторений может быть не более , а трудоемкость самого шага
Множества t образуют разбиение множества , поскольку на этапе инициализации = и каждый элемент множества перед своим исключением добавляется в некоторое множество t, причем только в одно.
Остается доказать утверждения, касающиеся множеств t. Предполо 86 жим, для некоторых t\ VL t2i t\ ф t имеем Itx П It2 7 0. Поскольку no построению, It = [Lj Sj, то найдется J2 Jt2 такой, что St2 П Itx 0-Но в таком случае на шаге 8 элемент J2 должен быть добавлен ко множеству Jiv В силу дизъюнктности набора {Jt} приходим к противоречию. Предположим, что для некоторых і Є I, j Є J выполнено і j ij(x), где X — заданное решение Лидера. По доказанному ранее найдется t такое, что j Є Jt- Из определения множеств Sj имеем і Є Sj, следовательно, і Є If-Что и требовалось доказать. В силу леммы 6 для любого t = 1,... ,Т, любого j Є Jt и любого допустимого решения Z = ((zi),(zij)) задачи $(Х) при фиксированном решении Лидера х имеем
Тогда вместо задачи $(Х) рассмотрим набор подзадач { (Х)}, где каждая подзадача $t{X) получена из $(Х) ограничением множества индексов на множество потребителей Jt и множество предприятий If. В силу (3.1) и леммы 6 целевую функцию (5) задачи $(Х) можно переписать следующим образом: и максимизировать сумму для каждого t отдельно. Пусть F{X) — оптимальное значение целевой функции задачи (Х). Аналогично для каждого t = 1,... ,Т рассмотрим ограничение задачи $(Х) на множество потреби 87 телей Jt и множество предприятий It с F(X) в правой части ограничения (10). Обозначим полученную подзадачу (Х). Повторяя рассуждения для набора подзадач { (Х)}, получаем следующее.
Лемма 7 (О декомпозиции задачи Последователя) Для t = 1,... , Т пусть F(X) — оптимальное значение целевой функции задачи $t(X), а z1 = (zj) — оптимальное размещение предприятий во вспомогательной задаче $t(X). Тогда для оптимального значения F (X) целевой функции задачи $(Х) и оптимального размещения предприятий (zi) задачи $(Х) выполнено:
Поскольку основная часть решений Лидера, просматриваемых в результате работы алгоритма локального поиска, является лишь промежуточным этапом вычислений, откажемся от трудоемкого поиска оптимального решения Последователя Z и заменим его быстрой приближенной процедурой. В качестве оценки значения целевой функции в таком случае будет выступать величина L(X,Zo), вычисленная для приближенного решения ZQ задачи $(Х). Заметим, что по отношению к истинному значению целевой функции, вычисляемому для оптимального некооперативного решения Последователя , вообще говоря, может выполняться любое из соотношений: ( , 0) = ( , ) ( , ).
Приближенное решение Q будем собирать в соответствии с леммой 7 из приближенных решений задач &( ). Для Є {1,... , } таких, что \ t\ 15, нахождение такого приближенного решения организуем по схеме локального поиска с рандомизированной окрестностью (для остальных отыскание оптимального решения не требует значительных временных затрат). В качестве базовой выбрана окрестность Flip(-) U Swap(-).
Процедура поиска стартует со случайного решение и производит 5 однотипных итераций, каждая из которых состоит из фаз диверсификации, обычного поиска и интенсификации. Фазы отличаются степенью рандомизации окрестности, которая задается двумя параметрами — величинами и . Условно говоря, их значение характеризует относительное качество выбираемого из окрестности решения (например, если = 0, 7, то выбранное решение лучше 70% решений окрестности) и вероятность того, что это качество будет достигнуто. Нетрудно убедиться, что при равновероятном выборе решений из окрестности, достаточно выбрать лучшее из случайно взятых с повторениями = [log (1 — ) \ решений. В фазах диверсификации и обычного поиска совершается переходов в лучшее из 2 решений, из которых случайным образом взяты из множества Flip( ) и из множества Swap( ), где — текущее решение. Для фазы диверсификации = , = 0, 6, = 0, 5. Для обычного поиска = п , = 0,8, = 0, 8. На фазе интенсификации в качестве начального решения выбирается лучшее из найденных на фазах диверсификации и обычного поиска. Далее производится поиск с параметрами = Ц , = 0,95, = 0,95. Посещенные на данной фазе решения запоминаются и запрещаются для дальнейшего рассмотрения во избежание зацикливания.
Для оценки эффективности предложенной процедуры рассмотрим набор входных данных, принадлежащий классу примеров Plain 100, полученных следующим образом. Генерируется 100 точек, соответствующих реализациям равномерно распределенных на единичном квадрате случайных векторов. Совокупность точек образует множество . Множество потребителей , а также множество мест возможного размещения предприятий положим равными множеству . Для каждого Є и произвольных і, 2 Є будем полагать, что \ j 2 тогда и только тогда, когда евклидово расстояние между точками и на плоскости.
Для каждого случайным образом выберем целое число j из интервала [5,9], и положим для всех Стоимости i и i открытия предприятия Лидера и Последователя в месте— случайные целые числа из интервалов [30,39] и [20,29] соответственно. Здесь и далее случайные величины равномерно распределены на соответствующем множестве.
Похожие диссертации на Сложность и алгоритмы решения дискретной задачи конкурентного размещения предприятий
