Применение лексикографической оптимизации в задачах логистики

Размещено на http://allbest.ru

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет «Санкт-Петербургская школа экономики и менеджмента»

Департамент прикладной математики и бизнес-информатики

БАКАЛАВРСКАЯ РАБОТА

Применение лексикографической оптимизации в задачах логистики

Выполнил: студентка Елнова Мария Игоревна

Руководитель: Старший преподаватель Н.В. Смирнова

Санкт-Петербург



ОГЛАВЛЕНИЕ

Введение

Глава 1. Логистика: горизонтальная и вертикальная кооперация

1.1 Логистика и история ее развития

1.2 Основные тенденции в логистике и особая роль интеграционных процессов

1.2.1 Горизонтальная кооперация

1.2.2 Вертикальная кооперация

Глава 2. Моделирование c использованием кооперативной теории игр

2.1 Теория кооперативных игр: основные понятия и свойства

2.1.1 ТП - игры

2.1.2 Определение решений в кооперативной теории игр

2.1.3 Свойства решений

2.2 Эксцессоподобные решения: N-ядро

2.2.1 Понятие эксцесса

2.2.2 N-ядро

2.2.3 Свойства N-ядра

2.2.4 N-ядро игры 3-х лиц

2.3 Другие эксцессоподобные решения

2.3.1 Понятие двойственной игры

2.3.2 Анти-N-ядро

2.3.3 SM-ядро

2.3.4 Modiclus

2.4 Примеры ТП - игр в логистике

2.4.1 Игра затрат в сфере транспортной логистики

2.4.1 Игра затрат для 3 лиц: влияние конструктивной и блокирующей силы коалиций

Глава 3. Моделирование ситуационной игры в логистике на практике

3.1 Постановка исследовательской задачи

3.1.1 Кооперационная структура P3

3.1.2 Игра 3 лиц: характеристическая функция

3.2 Вектор Шепли и SM-ядро

3.3 N-ядро (пред-N-ядро)

3.4 Анти-N-ядро

3.5 Анализ полученных результатов

Заключение

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



ВВЕДЕНИЕ

В современном мире трудно представить развитую экономику любой страны без грамотно организованного и систематически совершенствуемого логистического аппарата. Рыночная экономика РФ, которая в сравнении с другими странами была сформирована относительно недавно, имеет еще только развивающуюся сферу логистики и пока отстает по уровню от многих других стран. По данным на конец 2017 г. доля логистических издержек, приходящихся на долю расходов ВВП страны составляет 20% [26]. Важно отметить, что среднемировой уровень по данному виду затрат 13,8% от ВВП [26]. Слабая развитость данного сегмента в экономике может быть обусловлена требующей модернизации транспортной инфраструктурой, территориальными особенностями нашей страны, уровнем конкуренции в отрасли, забвением различных транспортных путей, а также различными последствиями кризисных и посткризисных периодов в России. Значительная доля расходов в области логистики, безусловно, при условии наращивания прибыли по другим направлениям, существенно снижает эффективность производства и торговли, отрицательно влияет на конкурентоспособность компаний и страны в целом. Если не минимизировать данные расходы, то многие коммерческие организации могут прекратить свою деятельность, в частности в труднодоступных регионах страны в виду низкой рентабельности, следовательно, вопрос снижения логистических затрат должен быть одним из ключевых в стратегии развития российского бизнеса.

Таким образом, на сегодняшний день высокие логистические расходы являются наиболее острой и актуальной проблемой, которая в перспективе может пошатнуть стабильность экономики. В данном вопросе также следует отметить взаимосвязь экономики и логистики, которая, в первую очередь, выражается через непосредственную функцию (задачу) логистики - рационализировать потоковые процессы в экономике. К сожалению, в России проводилось немного исследований по данной тематике, направленных на поиск оптимальных путей минимизации затрат, однако, в последнее время заметна тенденция в развитии и изучении этого направления [1], [3], [4], [5], [11], [19]. В качестве основного способа моделирования затрат в литературе и на практике эффект кооперации (взаимодействия) компаний рассматривается как ключевое средство, благодаря которому достигается бомльшая прибыль за счет сокращения издержек путем их перераспределения между компаниями. Вследствие этого, решениями данной проблемы могут служить разработки эффективных методов распределения затрат, в соответствии с которыми специалисты в области экономики и логистики смогли бы качественно изменить структуру работы в области транспортировки, используя новые методики ведения хозяйственной деятельности, и в значительной степени сократить долю расходов, что положительно повлияло бы как на показатели рентабельности в сфере логистики, так и на уровень ВВП в России.

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

Задачи исследования:

1. Изучить виды кооперации в сфере логистики и проанализировать пул логистических задач;

2. Исследовать различные методы логистической оптимизации в рамках математического моделирования с использованием концепций кооперативной теории игр;

3. Рассмотреть основные концепции кооперативной теории игр, применяемые для таких классов игр, как ТП-игры и связанные с ними игры затрат ;

4. Оценить и вычислить на основе реальных данных для сети судоходных компаний, занимающихся контейнерными перевозками, такие варианты распределения прибыли (в Главе 3 в качестве прибыли рассматривается объем TEUS контейнеров) как вектор Шепли, SM-ядро, N-ядро и анти-N-ядро;

5. Проанализировать результаты моделирования.

Гипотеза исследования: Методы распределения затрат и прибыли, основанные на эффекте синергии (объединения, кооперации) компаний являются наиболее эффективными, так как позволяют увеличивать прибыль не только коалиции, включающей всех игроков, но и каждого участника логистической системы в отдельности.

Основная часть данной работы состоит из обзора научных исследований на тему горизонтальной и вертикальной кооперации в логистике и описания методологии кооперативной теории игр, которая применяется в играх трансферабельной полезности (ТП-играх).

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

В заключении представлены основные выводы по работе. В качестве материала для анализа в работе используются научные статьи и учебные пособия таких авторов как Frisk M., Guajardo M., Maschler M., Jцrnsten K., Moulin H., Scarf H. E., Schemeidler D., Shapley L. S., Smirnova N. V., Southern R.N., Speranza M.G., Tarashnina S.I., Thun J. и других.

ГЛАВА 1. ЛОГИСТИКА: ГОРИЗОНТАЛЬНАЯ И ВЕРТИКАЛЬНАЯ КООПЕРАЦИЯ

1.1 Логистика и история ее развития

Логистика, являясь частью управления цепями поставок, планирует, реализует и контролирует прямые и обратные потоки товаров, хранение продуктов и другие услуги, направленные на обеспечение информацией клиентов в точках спроса и предложения товаров (в частности, например, в пунктах выгрузки и погрузки) [17]. Базовые концепции логистики и управления цепями поставок были разработаны и развивались в середине 20 века во время промышленного бума. В настоящее время в виду диджитализации экономики наблюдается основательная модернизация процессов в этой области, что делает ее задачи более масштабными и многофункциональными по своей структуре [6]. К основным операциям, которые отражают деятельность в сфере логистики, принято относить управление запасами, складирование, анализ погрузочно-разгрузочных работ, планирование спроса и предложения, транспортировку экспортных и импортных товаров, проектирование логистических сетей (в том числе работу третьих лиц - поставщиков логистических услуг), а также многое другое [17]. Исходя из задач логистики и ее базового функционала, очевидным образом следует, что для эффективной работы в этой области, требуется современное транспортное оборудование, а также возможность использовать различные пути сообщения, которые обеспечивают безопасное и качественное передвижение транспортных средств. Если раньше вопрос перевозок рассматривался в мире как ключевой с точки зрения национальной безопасности, то сейчас сообщение между основными населенными пунктами и стратегически важными объектами развито и, более того, чаще всего несколькими путями (воздушные, морские, речные, железнодорожные, автомобильные и другие перевозки). Вследствие этого ключевым вопросом для коммерческих предприятий стал вопрос о том, каким образом перевозить свои товары (сырье), а также, стоит ли вкладывать средства в инфраструктурные проекты, в случае если сеть не развита.

Проблемы в области транспорта и логистики, безусловно, решались ещё задолго до того, как были придуманы и внедрены инновационные компьютерные технологии для более грамотного принятия решений. Однако после того как были разработаны первые модели оптимизационных систем, инструменты оперативного поиска и соответствующее программное обеспечение, которые позволяют работать с большими объемами данных и обладают высокой вычислительной мощностью, эффективность и конкурентоспособность компаний со сложными проблемами в отношении логистики и транспорта значительно возросли. В настоящее время логистика и такое широкое направление как управление цепями поставок призваны выполнять основную бизнес-функцию - делать товары доступными там, где это необходимо и в нужных количествах [18].

Исследование операций (operational research, OP) в сфере транспорта и логистики были направлены на изучение и создание оптимальных методов решений, построенных на базе математического моделирования, история которых строилась вслед за интенсивным развитием информационных технологий. Начиная с 1960-х по 1970-е года, логистика еще только развивалась и в основном подразумевала под собой деятельность, связанную с распределением товаров и хранением запасов [18]. В этот же период времени были разработаны первые языки программирования, такие как, например, Fortran, которые начали широко использоваться, и получили хорошее практическое применение в данной области. В следующие 10 лет проводилось изучение грузоперевозок, за чем последовало возрождение морского и железнодорожного транспорта. Воздушный транспорт выступил также в качестве отдельной области для исследований в то время. В 1990-е года транспортировка подразумевала под собой пассажирские и грузовые перевозки, в то время как логистика развивалась с акцентом на операциях в управлении цепями поставок. В период 2000-2010 гг. транспортировка и логистика решали широкий спектр проблем. Разница между грузовыми и пассажирскими перевозками, а также традиционные барьеры в этой сфере становились все менее заметными [18]. Именно в этот отрезок времени наблюдались измеримые результаты исследований в области транспорта и логистики: большое количество опубликованных материалов, научных статей и организованных конференций приходится на этот период. Более того, множество проблем, которые в итоге выступили драйвером роста транспортной отрасли, способствовали выпуску набора моделей и алгоритмов, встроенных в дальнейшем в пакеты программного обеспечения.

1.2 Основные тенденции в логистике и особая роль интеграционных процессов

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

Системный подход в управлении цепями поставок подразумевает оптимизацию всей сети, где совместно моделируются и оптимизируются все составляющие ее звенья. Такой метод строится на предположении о том, что лучшие решения логистических проблем могут быть определены при изучении более глобальных направлений. Так, например, в последние годы в отличие от классических транспортных задач, построенных на основе поиска оптимальных маршрутных путей, которые располагают данными о местоположении, спросе покупателей и предложении поставщиков, временных ограничениях и требованиях, которые определены в договорах, многие аналитические задачи направлены уже на совмещение нескольких аспектов одновременно. Среди наиболее популярных можно выделить комбинирование задач в разрезе производства товаров (сырья, готовой продукции), маршрутизации и хранения запасов [18]. Таким образом, несколько компонентов в единой транспортной задаче совместно оптимизируются с дополнительными ограничениями (например, ограничением загрузки товаров). Это позволяет с большей точностью решать оптимизационные проблемы в отличие от независимых методов, так как последние могут допускать ошибки, которые могут привести в итоге к неоптимальному решению для комплексной задачи.

В последнее время также одним из популярных трендов в логистике стало изучение влияния интеграционных процессов на деятельность коммерческих компаний. Кооперация (интеграция) предполагает сотрудничество (взаимодействие) компаний, которое направлено на улучшение работы всех участников кооперационного (интеграционного) процесса и, которое изменяет структурные аспекты их деятельности [12]. Главной целью кооперативного сотрудничества является оптимизация работы всех участников. Соответственно, сокращение издержек и увеличение прибыли, как всего объединения, так и каждого участника в отдельности, являются основным результатом данной оптимизации. В логистике кооперация (интеграция) в основном рассматривается с точки зрения объединения транспортных компаний (в частности, перевозчиков), работающих в одной сфере, а также тех компаний, которые могут предоставлять дополнительные услуги по транспортировке товаров, но по своему функционалу имеют разные виды деятельности. Помимо уменьшения издержек для транспортных компаний кооперация также предоставляет экологические выгоды. Так, например, в случае с перевозчиками (к примеру, автомобильными) очень часто кооперация предполагает сокращение порожних перевозок при объединении в сеть нескольких компаний [6]. Тем самым, объем транспортных средств на дорогах сокращается, что уменьшает выбросы углекислого газа в атмосферу, а также аварии и время, затраченное на доставку товаров из пунктов предложения в пункты спроса [4]. Далее рассмотрим два основных вида кооперации, которые принято выделять в логистике: горизонтальная и вертикальная. Также в литературе можно встретить названия интегрированное (вертикальное) и совместное (горизонтальное) сотрудничество [4].

1.2.1 Горизонтальная кооперация

В настоящее время имеется большой объем опубликованных исследований, описывающих роль кооперации в транспортной отрасли, а также различных методов распределения затрат (прибыли) в кооперативных моделях экономической деятельности. Кроме того, количество статей, книг и учебных пособий по этим вопросам растет с каждым годом, в то время как многие исследования дополняют друг друга, выявляя новые подходы и методологию. Существенной вехой в развитии исследований распределения затрат стало применение кооперативной теории игр. На сегодня литература по проблеме распределения затрат, основанная на концепциях кооперативной теории игр, активно развивается и ориентирована преимущественно на изучение взаимодействия компаний посредством горизонтальной кооперации[1], [3], [4], [5], [7], [19].

Горизонтальная кооперация (интеграция) - это один из видов объединения компаний, в котором участники производственного процесса изготавливают однородные продукты и имеют идентичные стадии технологической цепочки [12].

Эффект горизонтальной кооперации (интеграции) компаний оценивается многими исследователями с помощью апостериорного анализа показателей, отражающих экономию на издержках и увеличение прибыли. В 2010 году Frisk, M., Gцthe-Lundgren, M., Jцrnsten, K. и Rцnnqvist, M. в своей работе проиллюстрировали результат действия горизонтальной кооперации на примере сотрудничества восьми компаний, работающих в области деревообрабатывающей промышленности в Швеции [3]. В статье под горизонтальной кооперацией авторы подразумевают процесс обмена товарами между компаниями (бартер), а также перевозку товаров (древесины) на целлюлозно-бумажные фабрики (пункты / точки спроса) тех поставщиков, с которыми входят в коалицию.

Sun, L., Rangarajan, A., Karwan, M. H.,Pinto, J. M. (2015) определяют термин коалиции как ряд всевозможных объединений участников игры друг с другом. В кооперативной теории игр коалиция принимает следующие формы: максимальная коалиция (grand coalition) - подразумевает кооперацию между всеми участниками игры и собственная коалиция (stand alone coalition) - в этом случае рассматривается объединение каждого участника с самим собой, другими словами, она отражает возможную прибыль либо убыток, которую компания получит, если не будет сотрудничать с другими [19]. Таким образом, результаты распределений доходов (издержек) от собственных коалиций являются наиболее показательными для компаний и учитываются при сравнении их с распределением в максимальной коалиции.

В статье Frisk, M., Gцthe-Lundgren, M., Jцrnsten, K., Rцnnqvist, M. (2010) каждая из компаний занимает свою территориальную позицию на юге Швеции, где занимается добычей и производством лесной продукции, таким образом, образуя свои пункты (точки) предложения. Кооперация путем бартерного обмена товарами в дальнейшем изменяет положение узлов спроса и предложения и, как следствие, сокращает затраты на транспортировку в связи со спецификой местоположения. В работе авторы исследуют гипотезу о том, что низкие транспортные издержки наблюдаются в таких коалициях, где зоны поставок компаний (точки предложения) перекрывают друг друга. Целью данного исследования является поиск оптимального способа распределения затрат (прибыли), при котором в наиболее равной степени учитываются интересы каждого участника коалиции. Таким образом, в работе рассматривается так называемая концепция справедливости («fairness concept»), которая предполагает, что каждый игрок получает примерно одинаковые издержки (доход) при их распределении. Для определения эффекта от кооперации в транспортировке древесины в статье приводятся различные способы распределения затрат, такие как вектор Шепли, N-ядро, распределение, основанное на объемах перевозки или автономных затратах, распределение на основе разделимых и неразделяемых затрат, а также распределение на основе теневых цен.

В первую очередь, перед описанием расчетов для каждого типа распределения, в работе даются определения базовой терминологии, которая относится к концепциям кооперативной теории игр. Авторы описывают понятие эксцесс как степень удовлетворенности коалицией определенным способом распределения. В эмпирической части исследования, применяя все вышеперечисленные способы моделирования затрат, максимизируется вектор эксцесса. Впоследствии авторами анализируются все распределения, а также дается оценка тем, которые принадлежат C-ядру (core) игры.

C-ядро для классических игр распределения прибыли (затрат) включает в себя распределения, для которых выполняются следующие условия: а. сумма распределений каждой коалиции не должна превышать затраты (прибыль) каждой коалиции; б. сумма распределений максимальной коалиции должна быть равна стоимости затрат (прибыли) этой коалиции [13]. Все распределения, принадлежащие C-ядру, называются стабильными. Это понятие означает, что набор распределений в заключительном соглашении между участниками игры, будет находиться в пределах С-ядра [14]. Однако, несмотря на то, что большинство распределений в статье относятся к С-ядру игры, в реальной жизни многие компании могут не согласиться на сотрудничество (кооперацию). Такое происходит в случае, если в долгосрочной перспективе организации получают меньшую прибыль (либо бомльшие издержки) по сравнению с другими компаниями. По этой причине Frisk, M., Gцthe-Lundgren, M., Jцrnsten, K., Rцnnqvist, M. (2010) предлагают новый метод распределения затрат, который соотносит в максимально равной степени прибыль между всеми игроками. Он носит название Equal Profit Method (EPM), что на русский язык может быть переведено как метод равной прибыли. В статье данный метод вычисляется в два этапа. На первом этапе авторы считают оптимальный объем транспортировки, который приводит к экономии затрат. На втором этапе минимизируется разница между максимальными издержками всех коалиций друг с другом. Согласно полученным результатам, на первом этапе распределение затрат является практически таким же, как и в векторе Шепли, однако авторы приводят довод о том, что подход EPM воспринимается лучше в аналитических отделах компаний по планированию. В результате исследования потенциальная экономия на затратах составила 14,2%. Когда были рассчитаны все методы распределения затрат, С-ядру игры принадлежали вектор Шепли, N-ядро и EPM. Все остальные способы не обеспечивали стабильных решений для некоторых коалиций и, как следствие, не принадлежали С-ядру игры. В указанной работе EPM считается наилучшим методом распределения затрат, поскольку позволяет достичь соглашение о сотрудничестве (кооперации) наиболее простым способом. Подводя итог своего исследования, авторы задают вектор для изучения следующих вопросов: во-первых, каким образом учитывать влияние географического положения пунктов (точек) спроса и предложения, в случае если игрок обнаруживает фундаментальную важность своего местоположения и, как следствие, делает запрос на бомльшую прибыль; во-вторых, как оценить влияние переговорных процессов относительно кооперации на принятие решений о распределении затрат.

Guajardo, M., Jцrnsten, K., Rцnnqvist, M. (2016) шестью годами позже продолжили данное исследование, дополнив его использованием такого понятия как блокирующая сила коалиции. Таким образом, авторы привели решение проблемы кооперативной игры, где участник(и) хотят прекратить сотрудничество (покинуть максимальную коалицию) для получения более высокого дохода. Блокирующая сила коалиции представляет собой вклад определенной коалиции в максимальную коалицию, которая содержит всех участников. [5] Иными словами, математически это можно представить как разницу между издержками (прибылью) максимальной коалиции и издержками (прибылью) максимальной коалиции без определенной коалиционной структуры. В статье блокирующая сила коалиции учитывается такими методами как SM-ядро и модифицированное N-ядро (modiclus). Конструктивная сила коалиции представляет собой ценность коалиции или прибыль, которую она может получить путем кооперации[5]. Многие исследования исходят из концепции конструктивной силы коалиции, которая основывается на таком распространенном методе распределения затрат в кооперативной теории игр как N-ядро. Стоит отметить, что Guajardo, M., Jцrnsten, K., Rцnnqvist, M. (2016) в качестве кооперации рассматривают только обмен товарами (бартер) при расчете множества распределений затрат в отличие от своих предшественников. В дополнение к исследованию, представленному в статье Frisk, M., Gцthe-Lundgren, M., Jцrnsten, K., Rцnnqvist, M. (2010), авторы в отдельности уделяют внимание блокирующей силе коалиции, которая при распределении учитывает в большей степени интересы тех игроков, которые расположены в периферийных районах по сравнению с другими компаниями. Его основная идея заключается в том, что такие игроки могут привести к дисбалансу кооперационную структуру, если решат покинуть максимальную коалицию. Вследствие этого, необходимо распределять издержки таким образом, чтобы избежать разрушения максимальной коалиции. В результате работы экономия на затратах составила 9%. Было выявлено, что компании, расположенные в центральном районе по сравнению с остальными, в значительной степени выигрывают от распределения N-ядра и обладают конструктивной силой. В то же время компании, находящиеся в периферийных районах, получают больший выигрыш от SM-ядра и modiclus, которые учитывают блокирующую силу коалиций. Однако, несмотря на наличие множества данных распределений, подводя итог, авторы заключили, что остается проблема отсутствия единого оптимального метода распределения затрат, который был бы лучше остальных.

1.2.2 Вертикальная кооперация

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

Данный тип сотрудничества в логистике носит название вертикальной кооперации. Этот вид интеграции подразумевает объединение компаний, в которых имеются последовательные стадии производственного цикла, начиная с добычи и заканчивая конечной реализацией товара (продукта) потребителям [12]. Среди характерных особенностей вертикальной кооперации принято выделять то, что в ней задействовано малое количество участников (по сравнению с горизонтальной кооперацией, где их число обычно большое), а основное внимание уделяется технологическим и техническим возможностям формирования коалиций [1]. Также вертикальная кооперация строит основу для управления цепями поставок, поскольку компании, которые находятся на разных уровнях в разрезе цепей поставок или действуют в различных отраслях, сотрудничают друг с другом [22] . Основной причиной объединения нескольких компаний в структуру вертикальной кооперации является снижение издержек максимальной коалиции (всего объединения участников) за счет снижения затрат, которые несли бы контрагенты, если бы действовали без образования коалиций. Происходит это в связи с тем, что партнеры в вертикальной кооперации отвечают индивидуально за конкретные этапы производства, следовательно, дублирование задач между ними маловероятно [1]. В отличие от горизонтальной кооперации, такой тип сотрудничества меньше изучен в литературе в рамках кооперативной теории игр. Причиной этого могут служить неоднородный состав участников в кооперации и разные источники затрат (прибыли). Вследствие этого, в разрезе единого метода распределения затрат (прибыли) сложно объединить в одну систему и проанализировать столь разнородные по видам своей хозяйственной деятельности субъекты. Однако в некоторых работах существуют решения, использующие методы лексикографической оптимизации [4], [11].

Классическим примером, который зачастую приводится во многих работах в качестве иллюстрации вертикальной кооперации в логистике, является объединение таких участников как производитель, дистрибьютор и дилер (продавец). Так, например, в своем исследовании Reyes P.M (2005) рассматривает логистическую сеть, состоящую из одного поставщика, трех дистрибьюторов и одного дилера (продавца). В работе для наглядности изображен график возможного передвижения товара от каждого участника игры, на котором указаны ограничения мощности для всех узлов, через которые проходит конечный продукт, прежде чем попасть от производителя к продавцу. Чтобы упростить расчеты все узлы были условно разделены между тремя (абстрактными) игроками, где первый игрок владеет двумя узлами, второй игрок - четырьмя, третий игрок - двумя соответственно. Исходя из значений характеристической функции, которая определялась количеством товара, встал вопрос, каким образом распределить максимальное количество товара, которым игроки обладают при кооперации среди всех участников кооперационного процесса [11]. Иными словами, была поставлена задача разобраться, каким объемом товара должен располагать каждый (абстрактный) участник игры, в распоряжении которого имеются несколько разных узлов, связывающие всю цепочку поставки товара. Целью этой задачи было увеличение размера поставок для всех игроков с учетом ограничения мощности. Для этого в качестве варианта решения предлагается использовать вектор Шепли. Таким образом, используя данный метод, было получено оптимальное распределения для каждого игрока, которое принадлежит С-ядру игры и, соответственно, является стабильным. В дальнейшем полученное соотношение позволяет рассмотреть, какое количество товара можно транспортировать на каждом узле перехода от производителя к дистрибьютору, и от дистрибьютора, соответственно, к продавцу в рамках заданной мощности. В результате исследования автор утверждает, что в задачах транспортировки управления цепями поставок вектор Шепли приводит динамические потоки в равновесие и является оптимальным методом распределения [11]. Однако, стоит отметить, что в реальности, по сравнению с примерами в горизонтальной интеграции, определить размер перевозимой продукции в случаях вертикальной кооперации сложнее в связи с разнородным составом участников игры.

Вследствие практических затруднений, возникающих при создании коалиций, а также ограниченной возможности применения кооперативной теории игр из-за различной природы игроков в структурах, построенных по принципам вертикальной кооперации, количество работ по данной тематике значительно ограничено. Таким образом, для решений проблем с перевозкой товаров в вертикальной кооперации, вектор Шепли рассматривается в качестве тактического метода поддержания стабильных условий в цепях поставок, в частности, что было представлено в работе Reyes P.M (2005). Тем не менее, стоит отметить, что в общем случае вектор Шепли может оказаться не внутри C-ядра, тем самым, стабильное состояние может быть нарушено. Именно это выступает основным недостатком данного типа распределения.

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

логистика двойственный игра перевозка



ГЛАВА 2. МОДЕЛИРОВАНИЕ C ИСПОЛЬЗОВАНИЕМ КООПЕРАТИВНОЙ ТЕОРИИ ИГР

2.1 Теория кооперативных игр: основные понятия и свойства

В настоящее время существует довольно масштабный спектр исследований, построенный на основе использования концепций кооперативной теории игр, который носит не только теоретизированный характер, но также направлен на практическое применение. Среди научных трудов в этой сфере наибольшей популярностью пользуются работы, в которых применяется целый ряд методов, позволяющий распределять затраты (прибыль) между всеми участниками игры посредством выбора наиболее оптимального способа кооперативного сотрудничества (например, [3], [5], [9], [19] и другие работы).

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

2.1.1 ТП - игры

В данной работе мы рассмотрим игры с трансферабельной полезностью (ТП - игры). Для начала дадим базовое определение, описывающее понятие коалиции.

Определение 1. Коалицией в кооперативной теории игр, называют любое непустое подмножество из , где является максимальной коалицией, включающей всех игроков [19].

Определение 2. Пусть - множество участников кооперативной игры. ТП-игра определяется как пара , где - класс кооперативных игр с участием лиц, - максимальная коалиция, - числовое выражение прибыли каждой коалиции , [9].

Стоит отметить, что очень часто интерпретируется как прибыль (выгода) коалиции , которую она может генерировать (получать) как при условии кооперативного сотрудничества, так и самостоятельно (т.е. не объединяясь с другими игроками - в этом случае такая коалиция рассматривается в качестве собственной, и на ее основе в том числе производится сравнение прибыли участника игры без кооперации, а также вклад игрока в максимальную коалицию) [16].

Существующие типы игр, нацеленные на исследование различных видов распределений, имеют общее значимое понятие, именуемое С-ядром игры, в рамках которого строится кооперативное сотрудничество игроков. С-ядро кооперативной игры можно интерпретировать как страхование всех игроков от отделения каких-либо коалиций от всеобщей кооперации за счет того, что оно состоит из тех распределений, которые предпочтительнее, чем собственные векторы полезностей игроков без кооперации. Также все распределения, принадлежащие С-ядру игры, называются стабильными, т.е. максимально устойчивыми для всех возможных коалиций [13]. Математически определение С-ядра игры можно выразить следующим образом:

Определение 3. В игре распределения затрат , где - класс кооперативных игр с участием лиц, - множество участников кооперативной игры, - затраты любой коалиции (которая определяется как непустое подмножество из ) (), С-ядром игры принято называть такое множество, которое удовлетворяет свойству: для любой , а также обозначает распределение затрат среди всех игроков кооперативного сотрудничества.

В ТП-играх С-ядром игры принято называть такое множество распределений , которое удовлетворяет свойству: для любой , при условии, что .

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

Определение 5. Игра называется супераддитивной, если для любых , где - коалиции из , при чем выполняется следующее выражение: , где обозначения отражают выигрыш каждой коалиции [9].

2.1.2 Определение решений в кооперативной теории игр

Среди наиболее популярных и часто используемых методов решений в кооперативной теории игр принято выделять такие способы поиска оптимальных распределений как вектор Шепли [15] и N-ядро [14], которые применяются практически во всех исследовательских работах. Другими концепциями решений, которые также известны, но представлены в меньшем объеме работ, являются SM-ядро, анти-N-ядро и modiclus, которые в дальнейшем будут подробно рассмотрены в этой Главе, а также в эмпирической части работы - в Главе 3.

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

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

Определение 6. Для множества игроков сбалансированным покрытием является отображение из (то есть множества собственных коалиций) в , при котором выполняется: Для , где - любой участник коалиции, а в сумму включаются все собственные коалиции, которые содержат агента . Отсюда условием сбалансированности игры (на примере ТП-игр) является

(Теорема Бондаревой-Шепли).

Важно упомянуть также и о принципах, на которых строятся различные методы решений. Так, например, согласно теории вектор Шепли основан на концепции, в которой затраты (прибыль) игроков распределяются в соответствии с вкладом каждого участника в коалицию и, следовательно, с вкладом каждой коалиционной структуры в максимальную коалицию. Эта концепция в литературе носит название концепции справедливости (или утилитаризма) [2], [9]. В отличие от этого оператора значений, N-ядро пытается удовлетворить интересы всех участников игры путем минимизации значений тех коалиций, в которых наблюдаются самые высокие затраты (или, в случае, если наблюдается небольшая прибыль у определенных коалиций, то максимизируется ее значение). Именно для этой цели рассчитывается вектор эксцессов, а концепция решения базируется на понятии стабильности игры (в литературе также можно встретить название эгалитаризма в качестве описания внутренней устойчивости решения такой игры) [2], [9]. Таким образом, вычисления, построенные на основе распределения N-ядра, обладают более сложной вычислительной техникой, чем вектор Шепли. Остальные методы распределений связаны с исследованием понятий конструктивной и блокирующей силы коалиций, описание которых чуть позже будут приведены в данной Главе.

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

Определение 7. Вектором Шепли в ТП-игре будем называть значение , которое вычисляется по формуле:

для ,

где определяется как мощность коалиции [15].

2.1.3 Свойства решений

Для того чтобы определить, какие методы решений подходят для конкретной задачи в рамках кооперативной игры, следует учитывать также и то, каким свойствам удовлетворяет то или иное решение. На примере игры (ТП-игра) приведем ряд основных свойств, соответствующих подмножеству , которое в игре образуется через отображение , которое является решением на всем множестве игр [23]:

1. Парето-оптимальность (PO): ;

2. Непустота (NE): ;

3. Анонимность (симметричность) (AN): для перестановки множества ;

4. Индивидуальная рациональность (IR): В случае если , то для всех ;

5. Свойство болвана (DUM): Игрок может быть назван болваном, если для выполняется . В этом случае справедливо следующее: ;

6. Аддитивность (ADD): Для выполняется следующее равенство: , где отражают решения в игре и .

7. Ковариантность относительно стратегически эквивалентных преобразований (COV): Для двух игр и , которые связаны между собой таким соотношением, как справедливо , где для коалиции выполняется ;

8. Единственность (SIVA): ;

Вектор Шепли удовлетворяет всем данным свойствам, и также стоит отметить, что свойство ADD является особенным, т.к. оно строго выполняется исключительно для данного распределения. Также еще стоит подчеркнуть, что свойство IR выполняется не на всех классах игр для вектора Шепли.

2.2 Эксцессоподобные решения: N-ядро

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

2.2.1 Понятие эксцесса

Определение 8. Для игры эксцесс коалиции будет принимать следующий вид , где - любая непустая коалиция из (все коалиции располагаются в невозрастающей последовательности), а - эксцесс, который интерпретируется как разница между выигрышем коалиции от кооперации () и ее собственной коалицией без кооперации () [8].

Другими словами, эксцесс определяет степень удовлетворенности каждой коалицией своим положением в игре. Таким образом, наименьшее значение, полученное в результате расчета вектора эксцесса, будет определять наиболее «обиженного» игрока в кооперационной структуре. В дальнейшем для того, чтобы поддерживать устойчивость таких коалиций, необходимо выполнить максиминную задачу, т.е. максимизировать все минимальные эксцессы. В игре затрат, напротив, для решения такого рода задач принято минимизировать максимальные эксцессы, что объясняется функциональной особенностью этого класса игр. Далее рассмотрим одно из таких решений, которое строится на основе расчета эксцесса.

2.2.2 N-ядро

Определение 9. Пусть , где - множество эффективных распределений (), существует вектор такой, что ), в котором эксцессы всех коалиций расположены в невозрастающем порядке. Во множестве существует единственное распределение , аналогичный вектор которого в смысле лексикографического порядка предпочтительнее . в этом случае называется N-яром ТП-игры, которое определяется как: [7].

Как уже упоминалось выше, данное эксцессоподобное решение направлено на максимизацию в ТП- игре всех эксцессов, которые являются минимальными по сравнению с другими коалициями. Математически решение, которое приводится на основе N-ядра, можно описать следующим образом: для всех [9]. В ходе решения N-ядро отбирает такое распределение, при котором максимальная прибыль (интерпретируемое здесь как недовольство решением) среди всех коалиций достигает своего минимального значения, что впоследствии приводит к единственному решению задачи распределения, которое и будет N-ядром.

2.2.3 Свойства N-ядра

N-ядро в качестве эксцессоподобного решения обладает следующим рядом свойств: PO, AN, DUM, COV, SIVA (подробное описание данных свойств приведено в разделе 3.3. данной Главы). В случае супераддитивной игры N-ядро также удовлетворяет свойству индивидуальной рациональности (IR), как и вектор Шепли [9].

Характеристической особенностью такого вида распределения является то, что оно не учитывает размер коалиции, а принимает в расчет только лишь ее вклад в общий выигрыш от кооперации. Такая особенность следует из принципов эгалитаризма, на основе которых строится данное распределение [2], [9].

Исходя из этого N-ядро отдает предпочтение при распределении более сильным игрокам, соответственно, как мы уже обсуждали ранее в разделе 2.1 Главы 1, такое распределение принимает во внимание исключительно конструктивную силу коалиции.

Стоит также отметить, что для игры, в которой участвуют только два игрока, N-ядро распределяет прибыль (издержки) в равнозначной степени между ними. Далее рассмотрим, каким образом выводится распределение N-ядра для классической игры 3 лиц.

2.2.4 N-ядро игры 3-х лиц

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

В качестве примера решения N-ядра с участием 3 игроков приведем ситуационную игру из книги Moulin H. (1991).

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

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

Так, например, она может быть равна для соответствующего пересечения.

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

Ввиду того, что все попарные коалиции в такой игре обладают значительной силой, то в ходе решения N-ядра рассчитываются только их эксцессы, т.к. значения собственных коалиций в такой игре равны нулю (). Таким образом, ставится следующая задача:

В данном случае сумма всех векторов эксцесса на множестве является константой, соответственно, чтобы посчитать распределение N-ядра, можно воспользоваться следующей формулой, которую приводит автор:



Отсюда, подставляя имеющиеся числовые значения , можно определить числовую форму N-ядра ().

Важно упомянуть, что для общего случая игры 3 лиц при техника вычисления гораздо сложнее. В этом случае необходимо рассматривать набор гипотез о том, какие коалиции являются наиболее «обиженными» в игре и при помощи расчета эксцессов проверять данную гипотезу, перебирая и решая все соответствующие неравенства. В отличие от вектора Шепли, который согласно концепции «справедливости» или утилитаризма распределяет выигрыш либо издержки в соответствии с ростом благосостояния всех игроков, увеличивая суммарный выигрыш, в N-ядре прибыль (издержки) от кооперации распределяются исходя из значений характеристической функции всех коалиций (т.е. их потенциального вклада в кооперационную структуру). Таким образом, распределение, которое дает N-ядро, в рамках одной задачи всегда будет определять неравнозначные доли выигрыша (затрат) в отличие от вектора Шепли, обычно слишком завышая либо занижая их.

2.3 Другие эксцессоподобные решения

Помимо N-ядра в кооперативной теории игр также существует целый ряд других способов распределений выигрышей, которые относятся к классу эксцессоподобных. В данной работе помимо N-ядра мы рассмотрим такие типы распределений как анти-N-ядро, SM-ядро и модифицированное N-ядро (modiclus). Проведенные исследования показывают, что результаты данных распределений строятся следующим образом: анти-N-ядро отдает предпочтение блокирующей силе коалиции, как и modiclus, N-ядро учитывает конструктивную силу коалиций, SM-ядро в свою очередь выдает среднее распределения между N-ядром и modiclus, таким образом, сглаживая действия конструктивной и блокирующей сил коалиций [21].

2.3.1 Понятие двойственной игры

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

В ТП-игре под блокирующей силой коалиции понимается следующее: пусть коалиция обладает блокирующей силой, тогда в числовом выражении это означает, что ее вклад в максимальную коалицию составляет: . Иными словами, это разница между выигрышем максимальной коалиции и количеством прибыли, которая останется в кооперационной структуре без этой коалиции [5].

Определение 10. Двойственной игрой по отношению к игре является такая игра, где справедливо для всех коалиций Отсюда вектор эксцесса для данной игры определяется как , где принадлежит множеству эффективных распределений () [21].

2.3.2 Анти-N-ядро

Приведем теперь распределение анти-N-ядра, которое соответствует этой двойственной игре.

Определение 11. Анти-N-ядром ТП-игры называется такое распределение, для которого справедливо:

, в котором вектор эксцессов располагается в невозрастающей последовательности [21].

Также стоит отметить, что анти-N-ядро игры , которое учитывает блокирующую силу коалиции, может быть определено как пред-N-ядро двойственной игры . Соответственно, многие подходы к вычислению, а также свойства, справедливые для N-ядра, выполняются и для анти-N-ядра. Например, COV, SIVA, PO, NE, DUM.

2.3.3 SM-ядро

Следующее решение, относящееся к классу эксцессоподобных - это SM-ядро. Как и предыдущее решение, SM-ядро также принято относить к типу распределений, учитывающих блокирующую силу коалиции и старается уравнивать соотношения прибыли (затрат) для всех участников. В качестве вектора эксцесса в данном случае принимается взвешенная сумма и с весом .

Определение 12. SM-ядром ТП-игры , в которой эксцесс принимает вид: , называется такое распределение, для которого справедливо следующее:

,

где вектор эксцессов располагается в невозрастающей последовательности.

В соответствии с этим, в данной игре вес определяет влияние конструктивной и блокирующей сил коалиций (в других играх значения веса может быть произвольным). Также было доказано, что SM-ядро совпадает со значением вектора Шепли в игре для 3 лиц [20].



2.3.4 Modiclus

Еще одним распределением, которое отдает предпочтение блокирующей силе коалиции, является modiclus.

Определение 13. Пусть в игре затрат существуют коалиции , такие что . Тогда существует такая функция (в англоязычной литературе она носит название «envy function») . Эта функция отражает разницу в эксцессах коалиции , т.е. насколько больше (меньше) получает коалиция по сравнению с . Определим такой вектор эксцесса, что , где . Таким образом, modiclus в данной игре будем называть такое распределение, которое в смысле лексикографического порядка будет минимизировать разницу между «envy function» всех коалиционных пар [5]:

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

2.4 Примеры ТП - игр в логистике

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

...