Автоматика и телемеханика, № 3, 2012
Приложения математического
пр о граммир ования
© 2012 г. В.Л. БЕРЕСНЕВ, д-р физ.-мат. наук (Институт математики им. О. Л. Соболева СО РАН, Новосибирск)
АЛГОРИТМЫ ЛОКАЛЬНОГО ПОИСКА ДЛЯ ЗАДАЧИ КОНКУРЕНТНОГО РАЗМЕЩЕНИЯ ПРЕДПРИЯТИЙ1
Рассматривается математическая модель, обобщающая известную задачу размещения предприятий и представленная в виде задачи двухуровневого математического программирования. В этой модели две соперничающие стороны последовательно размещают предприятия и каждая из сторон стремится максимизировать свою прибыль. В качестве оптимальных решений исследуемой задачи рассматриваются оптимальные кооперативные и оптимальные некооперативные решения. Предлагается метод вычисления верхних границ значений целевой функции задачи на оптимальных кооперативных и некооперативных решениях. Одновременно с вычислением верхней границы строится начальное приближенное решение. Предлагаются алгоритмы локального поиска для улучшения этого решения. Алгоритмы включают два этапа: на первом строится локально-оптимальное решение, а на втором - локально-оптимальное решение относительно окрестности, названной обобщенной. Приводятся результаты вычислительных экспериментов, демонстрирующие возможности предложенных алгоритмов.
1. Введение
Рассматривается задача, являющаяся обобщением известной задачи дискретной оптимизации - задачи размещения предприятий (средств обслуживания) [1, 2]. В этой модели в отличие от классической задачи размещения предприятий имеются две соперничающие стороны, которые последовательно открывают свои предприятия, стремясь "захватить" потребителей и максимизировать получаемую прибыль. При этом правила "захвата" потребителя одной из сторон устанавливаются с учетом предпочтений потребителя.
Принятие решений соперничающими сторонами при конкурентном размещении предприятий можно рассматривать как игру Штакельберга [3], а стороны, следуя терминологии этой игры, называть Лидером и Последователем. Задача Лидера в этой игре состоит в определении такого множества открываемых им предприятий, которое дает максимальную прибыль при условии, что часть потребителей будет "захвачена" Последователем. Получаемая математическая модель представляет собой задачу двухуровневого целочисленного программирования [4], включающую задачи верхнего и нижнего уровней. При этом оптимальное решение задачи нижнего уровня зависит от допустимого решения задачи верхнего уровня и используется для вычисления значения ее целевой функции.
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проекты №09-01-00059, 11-07-00474).
Дополнительные трудности при исследовании таких моделей возникают и в силу возможной неединственности оптимального решения задачи нижнего уровня, что требует конкретизации понятия оптимального решения задачи двухуровневого программирования .
Список литературы, посвященной построению и исследованию математических моделей конкурентного размещения предприятий, можно считать обширным [3, 5-10]. Большое внимание в этих работах уделяется, в частности, различным концепциям оптимальности решений, принимаемых Лидером и Последователем. Вместе с тем предложения по построению работоспособных алгоритмов решения задачи конкурентного размещения предприятий без существенных дополнительных ограничений, например на число открываемых предприятий, отсутствуют. Близкой к рассматриваемой является задача о (г/р)-центроиде [11]. В этой модели целевые функции Лидера и Последователя отличаются только знаком и заданы ограничения в виде равенств на число предприятий, открываемых как Лидером, так и Последователем. Для вычисления верхней границы значений целевой функции задачи о (г/р)-центроиде в [5, 12] предлагается подход, состоящий в ее сведении к задаче (0,1)-программирования с экспоненциальным числом переменных и ограничений. В [12] рассматривается эвристическая процедура, позволяющая выбрать "небольшое" число существенных переменных и ограничений такой задачи. Оптимальное решение полученной таким образом релаксированной задачи даёт искомую верхнюю границу.
Для исследуемой в работе задачи конкурентного размещения предприятий в качестве оптимальных решений рассматриваются так называемые оптимальные кооперативные и некооперативные решения. Предлагается метод вычисления верхних границ значений целевой функции на оптимальных кооперативных и некооперативных решениях. Идея метода изложена в [13] и численно апробирована в [14, 15]. В настоящей работе показано, что предложенный метод может быть использован для построения верхней границы как в случае некооперативных, так и кооперативных решений. Одновременно с вычислением верхней границы строится соответствующее допустимое кооперативное или некооперативное решение задачи конкурентного размещения предприятий. Это решение может рассматриваться как начальное приближенное решение. Предлагается алгоритм улучшения такого решения. Для этого задачи поиска оптимального кооперативного и оптимального некооперативного решений представляются в виде задачи максимизации некоторой псевдобулевой функции [1, 16]. Алгоритм поиска "хорошего" решения такой задачи включает два этапа. На первом этапе стандартным алгоритмом локального поиска [17] по окрестности специального вида начальное приближенное решение преобразуется в локально- оптимальное. На втором этапе с использованием алгоритма локального поиска по так называемой обобщенной окрестности [15] строится искомое приближенное решение. Это решение является не только локально-оптимальным, но и наилучшим в сравнении с другими локально-оптимальными решениями, "окружающими" найденное решение. Приводятся результаты вычислительного эксперимента, показывающие существенное улучшение решения в результате использования обобщенной окрестности.
В разделе 2 приводится формулировка задачи конкурентного размещения предприятий в виде задачи двухуровневого целочисленного программирования. В разделе 3 даются определения оптимального кооперативного и оптимального некооперативного решений задачи. Раздел 4 посвящен описанию метода вычисления верхних границ значений целевой функции задачи на оптимальном кооперативном и оптимальном некооперативном решениях. В разделе 5 задача поиска оптимального кооперативного (некооперативного) решения представляется как задача максимизации псевдобулевой функции и рассматривается стандартный алгоритм локального поиска для этой задачи, использующий окрестность специального вида. Раздел 6
посвящен описанию алгоритма локального поиска с обобщенной окрестностью. Там же приводятся результаты вычислительных экспериментов, демонстрирующих возможности предложенных алгоритмов.
2. Задача конкурентного размещения предприятий
Задача конкурентного размещения предприятий, как уже отмечалось, является математической моделью, возникающей при исследовании более общей ситуации, чем в случае классической задачи размещения. Здесь также имеется множество потенциальных предприятий (мест размещения предприятий) и некоторое множество потребителей. Но в отличие от классической задачи размещения предприятий имеются две соперничающие стороны, которые последовательно размещают (открывают) свои предприятия, стремясь "захватить" потребителей и достичь своих, вообще говоря, различных целей.
Принятие решений соперничающими сторонами при конкурентном размещении предприятий будем рассматривать как игру Штакельберга [3], а соперничающие стороны называть соответственно Лидером и Последователем.
Задача Лидера в этой игре состоит в определении такого множества открываемых предприятий, которое максимизирует его целевую функцию при условии, что часть потребителей будет "захвачена" Последователем.
Для формальной записи задачи Лидера введем обозначения и сформулируем необходимые допущения. Как и в классической задаче размещения предприятий [1, 2], обозначим через I = {1,..., т} множество предприятий (возможных мест открытия предприятий), а через . = {1,... ,п} - множество потребителей. Считаем, что предприятие г € I может быть открыто как Лидером, так и Последователем. Поэтому для всякого г € I предполагаем заданными величины и д^ равные фиксированным затратам на открытие предприятия г соответственно Лидером и Последователем. Если по каким-то причинам Лидер или Последователь не может открыть предприятие г, то полагаем /.I = то или д^ = то.
Для любых г € I, 3 € . через р^- обозначим величину прибыли, получаемой предприятием г при обслуживании потребителя 3.
Будем считать, что выбор открываемого предприятия для обслуживания потребителя з € . производится с учетом предпочтений потребителя 3. Считаем, что предпочтения потребителя 3 € . задаются отношением порядка на множестве I. Для г, к € I отношение г к означает, что из двух открытых предприятий г и к для потребителя 3 € . более предпочтительным является предприятие г. Отношение г к означает, что либо г Уj к, либо г = к.
При определении стороны, захватывающей потребителя 3 € ., принимается следующее правило. Пусть г^- есть наиболее предпочтительное предприятие для потребителя 3 среди всех предприятий, открытых Лидером, т.е. такое, что г^- г для всякого предприятия г € I, открытого Лидером. Аналогично пусть есть наиболее предпочтительное для потребителя 3 предприятие среди всех, открытых Последователем. Полагаем, что потребителя 3 € . "захватывает" Лидер, если г^ Уj kj, и "захватывает" Последователь, если ^ Уj гj.
Если потребитель 3 € . "захвачен" Лидером, то будем считать, что для обслуживания данного потребителя Лидер использует предприятие гj. Если же потребитель 3 € . "захвачен" Последователем, то будем считать, что при выборе предприятия для обслуживания данного потребителя Последователь имеет некоторую свободу и может выбрать любое открытое им предприятие к € I, но такое, что к Уj г^-.
Будем считать, что целью как Лидера, так и Последователя является получение максимальной прибыли. Прибыль Лидера и Последователя складывается из прибылей всех открытых соответственно Лидером и Последователем предприятий. В свою
очередь, прибыль каждого открытого пред
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.