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