Введение 3
Постановка задачи 5
Обзор литературы 6
Глава 1. Нахождение N-ядра с использованием теоремы Колберга 7
1.1. Основные понятия и определения 7
1.2. Метод построения N-ядра, основанный на теореме Колберга 9
1.3. Численный пример для N =1, 2, 3 11
Глава 2. Альтернативный алгоритм нахождения N-ядра 15
2.1. Основные утверждения и описание алгоритма 15
2.2. Алгоритм построения N-ядра [1] 21
2.3. Численный пример для N = {1,2,3} 24
2.4. Программная реализация алгоритма 26
2.5. Пример для реальных данных 2015 года 27
Заключение 29
Список литературы 30
Приложение 32
В данной работе рассматривается задача, в которой конкурирующие авиакомпании объединяются для обслуживания взлетно-посадочной полосы. Существуют разные самолеты, для которых нужны разные длины полос. Соответственно, нет никакого смысла авиакомпаниям оплачивать обслуживание той части полосы, которой они не пользуются. Также есть множество других факторов, которые стоит учесть: количество посадочных мест (чем больше мест, тем больше самолет, следовательно больше вес самолета, очевидно, что тогда он сильнее влияет на износ взлетно-посадочной полосы, поэтому денежный вклад в обслуживание должен быть больше), количество полетов. В работе эти факторы учитываются в виде двух значений: затраты и доход.
Такая проблема в Теории игр называется Игрой Аэропорт с прибылью [1]. Игроки - это авиакомпании, которые объединяются, для минимизации своих затрат. В формулировке проблемы Аэропорта, которую изначально предложили Littlechild S. C. и Owen G. [2], не учитывается доход авиакомпаний, важный в учете распределения средств на обслуживание, поскольку ни одна из авиакомпаний не согласится заплатить больше своего дохода. В данной работе это учитывается.
Проблемы с распределением затрат возникают во многих реальных жизненных ситуациях, когда люди со своими собственными целями, решают работать вместе. Например, построение асфальтированной дороги в частном секторе, проведение водопровода на нескольких жильцов. В этих ситуациях возникает проблема, как разделить между участниками совместные затраты, которые являются результатом сотрудничества. Существует много видов предложений по решению проблемы распределения затрат.
В качестве решения в данной работе выбрано N-ядро. Такой выбор был связан, во-первых, с тем, что это решение определяется единственным образом. Во-вторых, принадлежит C-ядру, и если оно существует, то есть N-ядро является недоминируемым дележом.
В работе рассматривается два способа построения N-ядра: с использованием теоремы Колберга [3] и с помощью алгоритма, предложенного в статье [1], который разработан специально для Игры Аэропорт с прибылью.
В ходе данной работы были выполнены все поставленные задачи. Изучены два алгоритма построения N-ядра, получено N-ядро в игре Аэропорт с прибылью двумя способами: на основании Теоремы Колбер- га и с использованием алгоритма, предложенного авторами Branzei R., Inarra E., Tijs S., Zarzuelo J. M. [1], разработанным специально для Игры Аэропорт с прибылью. Были найдены реальные данные: прибыль и расходы российских авиакомпаний за 2015 год [10]-[13], и посчитано решение по этим данным. Предложенное решение позволило уменьшить затраты всех авиакомпаний.
Решения, полученные разными способами, оказались одинаковыми. При использовании теоремы Колберга необходимо рассмотреть много сбалансированных наборов, особенно для большого количества игроков, а так же решать системы линейных уравнений. При n > 3 целесообразнее использовать второй алгоритм.
Результатом проведенного исследования является программная реализация альтернативного алгоритма.
