Автоматика и телемеханика, № 4, 2014
© 2014 г. А.А. ПАНИН
(Институт математики им. С.Л. Соболева СО РАН, Новосибирск Новосибирский государственный университет),
М.Г. ПАЩЕНКО, канд. физ.-мат. наук (Новосибирский государственный университет), А.В. ПЛЯСУНОВ, канд. физ.-мат. наук (Институт математики им. С. Л. Соболева СО РАН, Новосибирск Новосибирский государственный университет)
ДВУХУРОВНЕВЫЕ МОДЕЛИ КОНКУРЕНТНОГО РАЗМЕЩЕНИЯ ПРОИЗВОДСТВА И ЦЕНООБРАЗОВАНИЯ1
Предлагаются новые модели конкурентного размещения производства и ценообразования в виде задач двухуровневого линейного булевого программирования. Получены результаты, характеризующие сложность задачи, в которой доход монополиста на любом из рынков задается монотонно не возрастающей функцией от себестоимости обслуживания. Для этой задачи также предложено два приближенных алгоритма решения, основанных на идеях альтернирующих эвристик и локального поиска. Приводятся результаты вычислительного эксперимента, показывающие возможность быстрого вычисления приближенных решений задачи.
1. Введение
Задачи размещения — это широкий и многообразный класс задач математического программирования [1, 2]. Последние десятилетия все большее внимание привлекают проблемы, в которых решение о размещении принимают игроки, конкурирующие между собой [3-5]. Исследования в области конкурентных задач размещения были начаты в [6], где рассматривался процесс выбора размещения предприятий и выбор политики ценообразования двумя конкурентами.
Рассматриваемые в настоящее время постановки во многом основываются на представлениях, развитых в теории игр [3, 4, 7-11]. Игроки могут принимать решения одновременно или последовательно. Конкуренция может развиваться в пространстве и во времени, когда игроки по очереди меняют свои решения, оценивая действия конкурента. Первые исследования в области последовательной конкуренции в задачах размещения были проведены в [7, 8]. Отличительная черта этих постановок - наличие двух типов игроков. Первый тип - лидер, он принимает решение о размещении первым. Второй тип - конкурент, он принимает решение о размещении вторым, учитывая решение лидера. Также в этих постановках могут быть несколько лидеров и
1 Работа выполнена в Новосибирском госуниверситете при финансовой поддержке Министерства образования и науки РФ (договор № 02.G25.31.0054).
несколько конкурентов. В качестве концепции решения используется равновесие Штакельберга [9]. Примером конкурентной задачи размещения, в которой игроки принимают решения последовательно, является известная задача о (г|р)-центроиде (конкурентная задача о p-медиане) [12-14]. В постановках, в которых игроки принимают решения одновременно, как в [6], в качестве концепции решения используется равновесие Нэша.
Очень важное и интересное направление в этой области, связанное с теорией игр, - это постановки, в которых конкурирующие фирмы не только размещают производство, но и назначают цены на производимый товар [3, 4, 10, 11]. При этом обычно рассматриваются следующие три стратегии ценообразования:
- фабричное ценообразование (mill pricing) [15-17];
- равномерное ценообразование (uniform pricing) [15];
-дискриминационное ценообразование (discriminator pricing) [15].
Когда используется первая стратегия ценообразования, на каждом предприятии устанавливается своя цена. При равномерном ценообразовании на всех пунктах обслуживания устанавливается одна и та же цена. Дискриминационное ценообразование - стратегия ценообразования, при которой могут быть ущемлены интересы каких-то групп покупателей, т.е. на каждом пункте обслуживания могут устанавливаться разные цены для разных покупателей.
В представленной статье продолжается начатый ранее цикл исследований в области оптимального размещения предприятий и выбора цен на их продукцию и предлагается новая математическая модель для соответствующей игры Штакельберга [14, 16, 17]. Как и в задаче о центроиде, два игрока, лидер и его конкурент, открывают предприятия для обслуживания клиентов на рынках. Сначала делает ход лидер, затем конкурент. После открытия предприятий, на рынках начинается ценовая конкуренция. Она описывается известной моделью Бертрана. В результате этой конкуренции на каждом рынке один из игроков устанавливает свою монополию и определяет цену на продукцию. Цель игры - найти размещение предприятий лидера, позволяющее ему получить максимальный доход после наиболее сильного ответного хода конкурента. Ранее близкие по смыслу модели исследовались только для случая, когда лидер уже сделал свой ход и требовалось найти ответный ход конкурента с учетом ценовой модели Бертрана.
Исследование в рамках одного контекста процессов ценообразования и размещения приводит к более сложным в вычислительном отношении задачам. Таким образом возникает необходимость в проведении исследований для разработки эффективных методов их решения. Ситуация еще больше усложняется при исследовании процессов ценообразования и размещения в рамках двухуровневых моделей, которые вычислительно еще сложнее, чем классические одноуровневые оптимизационные модели [18]. Однако интерес к ним постоянно растет, так как подобные модели оказываются более адекватными в сравнении с одноуровневыми при исследовании изучаемых процессов в случае конкурирующих игроков, которые принимают решение последовательно [10, 11, 16, 17, 19, 20].
В данной работе рассматриваются модели дискриминационного ценообразования, которые позволяют разделить процессы ценообразования и размещения, и таким образом получить более простые в вычислительном отношении модели. Идея такого разделения заключается в том, что при фиксированном выборе размещения предприятий лидера и конкурента задача ценообразования для каждого рынка может быть решена независимо, с помощью какой-нибудь модели ценовой конкуренции, которая приводит к равновесию Нэша [21]. Далее в этом качестве будет использоваться известная модель Бертрана [21].
Предлагаемые в работе новые модели конкурентного размещения производства и ценообразования формулируются в виде задач двухуровневого линейного булевого программирования [18]. Для этих моделей предлагаются приближенные алгоритмы на основе идей, изложенных в [22]. Подход к моделированию процессов размещения и ценообразования, реализованный в данной работе, позволяет анализировать разные постановки. В частности, можно исследовать вопросы, связанные с эластичностью спроса, эффектом каннибализации спроса, расширением рынка [10, 19, 23-25].
Во втором разделе приводится содержательная постановка задачи. Вводятся основные обозначения и соглашения. В третьем разделе описывается процесс ценовой конкуренции, связанный с ним раздел рынков и вычисление монопольных цен. Четвертый раздел содержит математические постановки двух моделей конкурентного размещения производства и ценообразования. В первой модели использован более развитый механизм формирования монопольных цен, чем во второй, что позволяет использовать ее для исследования эластичности спроса, эффекта каннибализации спроса и т.д. Во второй постановке использован простой механизм, связывающий себестоимость обслуживания рынка монополистом и его доход. Именно эта постановка будет использоваться в дальнейшем в качестве модельной для разработки приближенных алгоритмов и оценки вычислительной сложности. Пятый раздел содержит результаты о вычислительной сложности задачи. В шестом и седьмом разделах приводится описание альтернирующей метаэвристики и результаты вычислительных экспериментов.
2. Содержательная постановка. Основные обозначения и соглашение
Приведем описание процесса размещения и ценообразования в виде следующей игры Штакельберга. Пусть задано конечное множество пунктов размещения предприятий и конечное множество рынков. Предполагается, что предприятия производят однородный продукт. Первым ходом лидер размещает свои предприятия, затем свой выбор делает конкурент. У каждого игрока имеются ограничения на бюджет для открытия предприятий. Для каждого рынка и предприятия известна себестоимость обслуживания данного рынка. После того как выбраны предприятия процесс ценообразования на каждом рынке реализуется на основе модели ценовой конкуренции Бертрана. В этой модели игроки конкурируют между собой, изменяя цены на продукцию, стремясь к себестоимости производимой продукции. В данной работе, как и в ряде других работ [11, 25], идеология классической модели Бертрана исполь-
зуется для раздела рынков между игроками. В результате ценовой конкуренции рынки будут поделены между лидером и конкурентом. На любом из рынков побеждает тот из соперников, у которого наименьшая себестоимость обслуживания данного рынка. В случае, когда наименьшая себестоимость обслуживания рынка достигается и лидером, и конкурентом, рынок монополизируется лидером. Монополист на каждом своем рынке в отличие от модели Бертрана устанавливает оптимальную - монопольную - цену и получает прибыль, равную произведению величины спроса на разность монопольной цены и себестоимости. Прибыль игрока складывается из прибыли с каждого из монополизированных им рынков. Цель игры лидера - выбрать такое множество пунктов размещения при заданном бюджетном ограничении, которое позволяет монополизировать рынки, доставляющие максимальную суммарную прибыль.
В качестве бюджетных ограничений далее используются медианные ограничения на количество выбранных предприятий лидера и конкурента.
Введем обозначения:
I = {1,... ,т} — множество пунктов размещения для предприятий лидера и конкурента;
К = {1,... , п} — множество рынков;
ш^ах ^ 0 — максимальная цена, которую готовы платить клиенты рынка к за продукт;
Цк(-) ^ 0 — функция спроса для рынка к, зависящая от цены продажи ш, 0 < ш < ш^ах;
р — количество предприятий, размещаемых лидером;
г — количество предприятий, размещаемых конкурентом;
Сгк — себестоимость обслуживания к-го рынка из пункта г.
Будем считать, что для любого рынка к и любого пункта г выполняются неравенства сгк ^ ш^ах.
Для описания выбора лидера и конкурента будем использовать следующие переменные:
1, если лидер размещает в
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.