авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 |

Алгоритмы и программный комплекс решения задач теории кооперативных игр. ядерные решения дискретных кооперативных игр

-- [ Страница 1 ] --

На правах рукописи

Оганян Лев Сергеевич

Алгоритмы и программный комплекс

решения задач теории кооперативных игр.

Ядерные решения дискретных кооперативных игр

специальность 05.13.18 – «Математическое моделирование,

численные методы и комплексы программ»

Автореферат

диссертации на соискание ученой степени

кандидата технических наук

Ростов-на-Дону – 2010

Работа выполнена на кафедре высшей математики и исследования операций факультета математики, механики и компьютерных наук Южного федерального университета

Научный руководитель: кандидат технических наук, доцент

Мермельштейн Геннадий Гавриилович

Официальные оппоненты: доктор технических наук, профессор

Лябах Николай Николаевич

кандидат физико-математических наук,

профессор Ерусалимский Яков Михайлович

Ведущая организация: Южно-Российский государственный технический университет (ЮРГТУ-НПИ)

Защита диссертации состоится 14 мая 2010 г. в 13:00 часов на заседании диссертационного совета Д 218.010.03 при Ростовском государственном университете путей сообщения по адресу: 344038, г. Ростов-на-Дону, пл. Ростовского Стрелкового Полка Народного Ополчения, 2.

С диссертацией можно ознакомиться в научной библиотеке РГУПС по адресу: 344038, г. Ростов-на-Дону, пл. Ростовского Стрелкового Полка Народного Ополчения, 2.

Автореферат разослан «___» апреля 2010 г.

Ученый секретарь

диссертационного совета Д 218.010.03

доктор технических наук, профессор Бутакова М.А.

Актуальность темы

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

Большой вклад в развитие теории кооперативных игр внесли Фон Нейман Дж., Моргенштерн О., Нэш Дж., Шепли Л.С., Воробьев Н.Н., Бондарева О.Н., Мулен Э., Петросян Л.А., Яновская Е.Б. и др.

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

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

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

Актуальной задачей является получение условий сбалансированности игр малой размерности и исключение зависимых неравенств из условий сбалансированности. Для компактного описания вершин многогранника, определяющего условия сбалансированности, используются минимальные сбалансированные покрытия и векторы их коэффициентов, что позволяет создать эффективный алгоритм расчета, реализованный в комплексе проблемно-ориентированных программ. В литературе приведены все минимальные сбалансированные покрытия для игр трех и четырех лиц. Для игры четырех лиц наборы минимальных сбалансированных покрытий, приведенные в работах Бондаревой О.Н. и Мулена Э., не совпадают. Общего описания минимальных сбалансированных покрытий игры n лиц в литературе пока нет.

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

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

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

Для достижения этих целей в работе решены следующие задачи:

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

2. Доказана неприемлемость непосредственного применения стандартного отношения доминирования для определения сбалансированности дискретных игр.

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

4. Выведены достаточные условия непустоты С-ядра дискретной игры.

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

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

Методы диссертационного исследования основываются на применении аппаратов теории игр и исследования операций, теории многогранников, теории графов.

Научная новизна работы состоит в следующих результатах:

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

2. Выведены необходимые и достаточные условия непустоты множества дележей, множества двойственных дележей, множества Вебера и СС-ядра дискретной игры, а также исследованы соотношения между этими множествами.

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

4. Получены достаточные условия непустоты С-ядра дискретной игры.

5. Разработан программный комплекс, позволяющий решать основные задачи теории кооперативных игр.

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

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

Апробация работы. Основные положения диссертации докладывались на второй международной конференции «Математическое моделирование социальной и экономической динамики» (г. Москва, 2007 г.); на всероссийском симпозиуме «Математические модели и информационные технологии в экономике» (г. Кисловодск, 2007 г.); на конференции «Современные информационные технологии в образовании: Южный Федеральный Округ» (г. Ростов-на-Дону, 2007 г.); на XVI международной конференции «Математика. Экономика. Образование» (г. Ростов-на-Дону, 2008 г.); на всероссийской конференции «Современные проблемы прикладной математики и математического моделирования» (г. Воронеж, 2007 г.),; на всероссийской научно-практической конференции «Современная математика и проблемы математического образования» (г. Орел, 2009 г.); на третьей международной конференции «Теория игр и менеджмент» (г. Санкт-Петербург, 2009 г.); на Х всероссийском симпозиуме по прикладной и промышленной математике (г.Сочи, 2009 г.).

Публикации. По материалам диссертации опубликовано 11 печатных работ общим объемом 2.5 п.л., из них 3 – в изданиях, рекомендованных ВАК.

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, двух приложений и списка литературы. Объем диссертационной работы 146 страниц. Библиографический список содержит 99 наименований.

Содержание работы

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

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

=<N,>, N={1,…,n} – множество игроков, – характеристическая функция, (S1)+(S2) (S1S2), S1S2= с трансферабельной полезностью. Возможная пустота С-ядра кооперативной игры является главным ограничением этого понятия, поэтому важной проблемой кооперативной теории игр является вывод условий его существования. Каждая существенная игра с трансферабельной полезностью стратегически эквивалентна своей (0-1)-редуцированной форме (i)=0, iN; (N)=1; 0(S)1, SN.

Игра имеет непустое С-ядро тогда и только тогда, когда она сбалансирована, т.е. 1, , где , , – вершины многогранника , , заданного условиями , ( – характеристический вектор коалиции S).

Из 1, , следует, что проблема аналитического описания множества сбалансированных, супераддитивных, (0-1)-редуцированных игр сводится к задаче нахождения всех вершин вспомогательного многогранника . Размерность многогранника экспоненциально растет при увеличении числа игроков, но количество ненулевых компонент его вершин не больше n. Поэтому, задают в виде пары (,), где = – семейство коалиций, соответствующих положительным компонентам вершины (минимальное сбалансированное покрытие), = – вектор положительных компонент вершины (вектор коэффициентов). Минимальное сбалансированное покрытие называется несущественным, если соответствующее ему неравенство системы 1, , является следствием остальных неравенств этой системы и условий супераддитивности. В противном случае минимальное сбалансированное покрытие называется существенным(СМСП).

  1. СМСП игры трех лиц:
Существенное минимальное сбалансированное покрытие Количество покрытий Коэффициенты покрытия
1 {1,2},{1,3},{2,3} 1 (1/2, 1/2, 1/2)
  1. СМСП игры четырех лиц:
Существенное минимальное сбалансированное покрытие Количество покрытий Коэффициенты покрытия
1 {1,2},{1,3},{1,4},{2,3,4} 4 (1/3, 1/3, 1/3, 2/3)
2 {1,2,3},{1,2,4},{3,4} 6 (1/2, 1/2, 1/2)
3 {1,2,3},{1,2,4},{1,3,4},{2,3,4} 1 (1/3, 1/3, 1/3, 1/3)
  1. СМСП игры пяти лиц:
Существенное минимальное сбалансированное покрытие Количество покрытий Коэффициенты покрытия
1 {1,2},{1,3,4,5},{2,3,4,5} 10 (1/2,1/2,1/2)
2 {1,2,4},{2,3,5},{1,3,4,5} 15 (1/2,1/2,1/2)
3 {{1,2},{1,3},{2,3},{4,5} 10 (1/2,1/2,1/2,1)
4 {1,2,3},{1,4,5},{2,4,5},{3,4,5} 10 (2/3,1/3,1/3,1/3)
5 {2,4},{3,4},{1,4,5},{1,2,3,5} 30 (1/3,1/3,1/3,2/3)
6 {1,5},{2,5},{3,5},{4,5},{1,2,3,4} 5 (1/4,1/4,1/4,1/4,3/4)
7 {4,5},{1,2,5},{1,3,5},{2,3,5},{1,2,3,4} 20 (2/5,1/5,1/5,1/5,3/5)
8 {1,4,5},{2,4,5},{3,4,5},{1,2,3,4},{1,2,3,5} 10 (1/5,1/5,1/5,2/5,2/5)
9 {1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5} 1 (1/4,1/4,1/4,1/4,1/4)
10 {1,2},{1,3,4},{2,3,4},{2,3,5},{1,4,5} 60 (1/4,1/4,1/4,1/2,1/2)
11 {1,2,4},{2,3,4},{1,3,5},{2,3,5},{1,4,5} 12 (1/3,1/3,1/3,1/3,1/3)
12 {2,4},{3,4},{1,2,3},{2,3,5},{1,4,5} 30 (1/5,1/5,2/5,2/5,3/5)


Pages:   || 2 |
 





 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.