Численное построение решений в классе неантагонистических позиционных дифференциальных игр тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Кувшинов, Дмитрий Рустамович

• Кувшинов, Дмитрий Рустамович
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Кувшинов, Дмитрий Рустамович

Введение.

Список обозначений.

Глава 1. Сведения из теории неантагонистических дифференциальных игр.

1.1. Система и траектории.

1.2. Вспомогательные антагонистические игры.

1.3. Равновесное по Нэшу решение.

1.4. Неулучшаемое равновесное по Нэшу решение.

1.5. Решение по Штакельбергу.

1.6. Реализация согласованных ломаных Эйлера, порожденных решениями игры.

Глава 2. Теоретические основы численных алгоритмов и их описание

2.1. Общая идея

2.2. Аппроксимация множеств уровня функции цены антагонистической дифференциальной игры.

2.2.1. И/*-алгоритм

2.2.2. 1У+-алгоритм.

2.3. Неулучшаемые решения по Нэшу.

2.3.1. Внешний цикл.'

2.3.2. Внутренний цикл.

2.3.3. Множество незапрещенных позиций.

2.4. Решения по Нэшу.

2.5. Решение по Штакельбергу.

2.5.1. Внешний цикл.

2.5.2. Множество незапрещенных позиций.

2.6. Восстановление траектории.

2.7. Алгоритмы вычислительной геометрии.

2.7.1. Теоретико-множественные операции.

2.7.2. Алгебраическая сумма.

Глава 3. Программная реализация алгоритмов.

3.1. Общий подход.

3.2. Струкура программной реализации.

3.2.1. Элементы геометрии.

3.2.2. Система.

3.2.3. Задачи и методы решения.

3.2.4. Алгоритмы

3.2.5. Внешний цикл Р-алгоритма.

3.3. Поддержка параллельных вычислений.

Глава 4. Результаты вычислительного эксперимента.

4.1. Пример 1.

4.1.1. Модельный пример: ц= ь>.

4.1.2. Случай \х ф и.

4.2. Пример 2.

Введение диссертации (часть автореферата) на тему «Численное построение решений в классе неантагонистических позиционных дифференциальных игр»

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

Показатели качества участников процесса управления представляют величины, определённые как некоторые функционалы от воздействий и/или состояния системы.

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

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

Современный облик теории дифференциальных игр сформировался в значительной степени под влиянием работ отечественных и зарубежных математиков Р. Айзекса [1], Н. Н. Красовского [25, 26, 82, 83], Л. С. Понтрягина [42], У. Флеминга.

Крупный вклад в развитие теории дифференциальных игр внесли Э. Г. Альбрехт, М. Барди, В. Д. Батухтин, Е. Н. Баррон, Т. Башар, Р. Беллман, А. Брайтон, Н. Л. Григоренко, Р. В. Гамкрелидзе, В. И. Жуковский, М. И. Зеликин,

Н. Калтон, А. Ф. Клейменов, А. Н. Красовский, А. В. Кряжимский, А. Б. Кур-жанский, Дж. Лейтман, П. Л. Лионе, Н. Ю. Лукоянов, А. А. Меликян, Е. Ф. Мищенко, М. С. Никольский, Г. Ольсдер, Ю. С. Осипов, А. Г. Пашков, В. С. Пацко, Н. Н. Петров, Л. А. Петросян, Г. К. Пожарицкий, Б. Н. Пшеничный, А. И. Субботин, Н. Н. Субботина, А. М. Тарасьев, В. Е. Третьяков, В. И. Ухоботов, В. Н. Ушаков, А. Фридман, Хо-Ю-Ши, А. Г. Ченцов, Ф. Л. Черноусько, А. А. Чикрий, С. В. Чистяков, Р. Эллиот и многие другие.

Первые работы по статическим играм относятся к периоду 30-50-х гг. двадцатого века и принадлежат таким авторам как Дж. фон Нейман, О. Моргенштерн, Дж. Нэш, Г. фон Штакельберг. Принципиальным вопросом в неантагонистической игре является выбор понятия решения, отвечающего содержанию задачи и опирающегося на соответствующий выбор принципа оптимальности. Обычно рассматриваются равновесное решение по Нэшу [34] и решения по Штакельбергу [94].

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

Неантагонистическим дифференциальным играм посвящены работы X. Абу-Кандила (Н. Abou-Kandil), Т. Башара (Т. Basar), Н. Н. Данилова, В. И. Жуковского, В. В. Захарова, П. Кардалиге (P. Cardaliaguet), А. Ф. Клейменова, А. Ф. Ко-ноненко, Дж. Круза (J. В. Cruz), В. Н. Лагунова, Дж. Лейтмана (G. Leitmann), С. В. Лутманова, О. А. Малафеева, Г. Олсдера (G. J. Olsder), А. Ори (A. Haurie), Л. А. Петросяна, А. А. Чикрия, С. В. Чистякова, Г. Янка (G. Jank) и других. Необходимо также упомянуть работы М. Фальконе (М. Falcone) и его сотрудников

66, 70] по численным алгоритмам в дифференциальных играх и Д. В. Камзолкина по приближенному вычислению функции цены [15].

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

Среди перечисленных авторов существенное влияние на методологию текущего исследования оказали работы А. Ф. Кононенко, Л. А. Петросяна и А. Ф. Клейменова. Так, для игры двух лиц А. Ф. Кононенко [23] устанавливает необходимые условия существования решения по Нэшу в классе позиционных стратегий. Там же устанавливаются достаточные условия, почти совпадающие с необходимыми. В этой же работе описана структура равновесных по Нэшу решений, использующих идею Ю. Б. Гермейера о применении стратегий наказания. Структура решений основана на совместном выборе игроками взаимовыгодной траектории, реализуемой с помощью программных управлений, а также на применении позиционных стратегий, составляющих универсальную седловую точку во вспомогательных антагонистических играх, в случае отклонения игрока от выбранной траектории. Последнее может быть интерпретировано как наказание игрока, уклоняющегося от отслеживания выбранной траектории. При этом факт отклонения партнера каждый игрок устанавливает по информации о текущем фазовом векторе системы. Полученная теорема о достаточных условиях фактически является теоремой существования равновесных по Нэшу решений.

Важным является условие динамической устойчивости решений в неантагонистической игре, введенное Л. А. Петросяном [41].

В работах А. Ф. Клейменова [16] получены следующие результаты, послужившие теоретическим фундаментом предлагаемой диссертации: 1) необходимые и достаточные условия существования равновесных по Нэшу решений и решений по Штакельбергу, 2) описание указанных типов решений в терминах решений нестандартных задач оптимального управления.

На этой основе С. И. Осиповым [36, 37] был разработан численный алгоритм построения'решений по Штакельбергу в линейной игре двух лиц с цилиндрическими терминальными показателями качества.

В настоящей диссертации разработан алгоритм приближенного построения равновесных по Нэшу (и, в частности, неулучшаемых) решений для класса позиционных дифференциальных игр с терминальными показателями качества игроков. Произведено обобщение упомянутого алгоритма С. И. Осипова построения приближенных решений по Штакельбергу на более широкий класс систем. При этом построение решений того или иного типа производилось в два этапа: 1) нахождение концов траекторий, порождаемых искомыми решениями, 2) построение траекторий и программных управлений игроков (составляющих решение соответствующих нестандартных задач оптимального управления). Общим для этих двух этапов является понятие множества незапрещенных позиций, внутри которого содержатся траектории решений. Создана программная реализация разработанных алгоритмов и проведен численный эксперимент.

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

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

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

Методы исследования. Исследования проводятся в рамках подхода, разрабатываемого в научной школе Н. Н. Красовского по оптимальному управлению и дифференциальным играм. Оптимальные стратегии в неантагонистических играх строятся на основе решений соответствующих нестандартных задач (оптимального) управления [16]. Алгоритмы предполагают дискретное представление времени, а также представление множеств в фазовом пространстве в виде многогранников, к которым применяются теоретико-множественные операции: объединения, пересечения, алгебраической суммы и другие. Например, для построения решений игры на плоскости используется представление множеств в виде набора плоских многоугольников, задающих многокомпонентные многосвязные фигуры. Ввиду ограниченной поддержки алгоритмами вычислительной геометрии пространств размерности больше двух, программная реализация предлагаемых алгоритмов ориентируется на решение игр в плоскости.

Заметим, что алгоритмы численного решения антагонистических позиционных дифференциальных игр, используемые в предлагаемых алгоритмах построения решений для неантагонистических игр, были разработаны в научных коллективах, руководимых В. Н. Ушаковым и В. С. Пацко. В частности, был использован алгоритм построения множества позиционного поглощения в антагонистической игре с нелинейной динамикой, предложенный в статье А. М. Тарасьева, В. Н. Ушакова и А. П. Хрипунова [51].

Разработанный в диссертации алгоритм нахождения равновесных по Нэшу решений, является развитием идеи, заложенной при разработке алгоритма С. И. Осипова [36] построения решений Штакельберга.

Программная реализация опирается на парадигму обобщенного программирования в рамках языка программирования С++, проектирование основано на идиоме «концепция-модель» и использовании политик для отделения концептуально-независимых компонент [2, 47, 91].

Научная новизна.

1. Разработан новый численный алгоритм построения приближенных равновесных по Нэшу решений для класса позиционных дифференциальных игр двух лиц с терминальными показателями качества игроков. Новым^являет-ся также вариант этого алгоритма, предназначенный для построения только неулучшаемых равновесных решений.

2. Алгоритм численного построения решений Штакельберга разработан для более общей постановки, чем в оригинальной работе [36].

3. Создана программная реализация разработанных алгоритмов в виде расширяемой библиотеки программных компонент с применением современных подходов к проектированию программных комплексов.

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

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

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

На защиту выносятся следующие основные результаты и положения.

1. Предложен новый алгоритм численного построения равновесных по Нэшу решений для класса нелинейных позиционных дифференциальных игр с терминальными показателями качества игроков.

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

3. Разработана программная реализация алгоритмов построения равновесных по Нэшу решений и решений Штакельберга в виде расширяемой библиотеки программных компонент (классов-шаблонов и функций-шаблонов) с применением современных подходов к проектированию программных комплексов.

4. Показана работоспособность разработанных алгоритмов и их программных реализаций на расчете двух примеров, один из которых ранее изучался аналитическими методами в [16].

Апробация работы. Основные результаты диссертации обсуждались и докладывались на научном семинаре отдела динамических систем ИММ УрО РАН, научном семинаре кафедры теоретической механики Уральского государственного университета, научном семинаре кафедры дифференциальных уравнений Удмуртского государственного университета, научном семинаре кафедры теории управления и оптимизации Челябинского государственного университета, а также на следующих научных конференциях.

1. Международная научная конференция «Устойчивость, управление и моделирование динамических систем», Екатеринбург, УрГУПС, 15 - 17 ноября, 2006.

2 The Second International Conference "Game Theory and Management", Gradúate School of Management, St. Petersburg State University, 26 - 27 июня, 2008.

3. International Joint Conferences on Computer, Information, and System Sciences, and Engineering (CISSE), 5-13 декабря, 2008.

4. 40-я Всероссийская молодежная школа-конференция «Проблемы теоретической и прикладной математики», Екатеринбург, 26 - 30 января, 2009.

5. САО'09, IFAC Workshop on Control Applications of Optimisation, University of Jyvaskyla, Agora, Finland, 6-8 мая, 2009.

6. Всероссийская конференция «Динамические системы, управление и наноме-ханика», Ижевск, УдГУ, 24 - 28 июня, 2009,

7. Международная конференция «Актуальные проблемы теории устойчивости и управления», Екатеринбург, ИММ УрО РАН, 21 - 26 сентября, 2009.

Публикации. Основные материалы диссертации опубликованы в 13 работах [19-21, 27-30, 77-81, 85].

В совместных работах [20, 21, 77-81] А. Ф. Клейменову принадлежит постановка задачи, алгоритм построения равновесных по Нэшу решений, основанный на решении последовательности вспомогательных биматричных игр, названный в работах БМ-процедурой (в диссертацию он не был включен), и общее руководство исследованием; в этих же работах С. И. Осипову принадлежит алгоритм построения решений Штакельберга и первая его программная реализация. Кроме того, в [21] Череповым А. С. была проведена предварительная работа по программной реализации алгоритма.

Совместная работа [19], по сути резюмирующая весь цикл работ, содержит обзор алгоритма построения решений Штакельберга С. И. Осипова и ВМ-процедуру А. Ф. Клейменова. Остальные результаты статьи, включая алгоритм построения равновесных по Нэшу решений и вариант для неулучшаемых равновесных по Нэшу решений, получены автором.

Отметим, что в работах 2008 и 2009 годов использовалась программная реализация, созданная полностью автором диссертации на языке С++, с учетом опыта, полученного при работе над результатами, представленными в [21, 27].

В [27] представлены результаты, полученные после перехода на библиотеку GLU в качестве библиотеки алгоритмов вычислительной геометрии.

Работы [28-30, 85] посвящены алгоритму построения равновесных по Нэшу решений, заявленному как основной результат диссертации, при этом работа [29] является основной.

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Кувшинов, Дмитрий Рустамович

Заключение

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

Представляют интерес дальнейшие теоретические изыскания в следующих направлениях.

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

• Увеличение числа игроков сверх двух. Возможно, удастся использовать разработанные алгоритмы как основу для новых алгоритмов с большим числом игроков.

• Более общий вид показателей качества, включающий интегральный член, зависящий от управлений, выбираемых игроками: в о

Решение подобных задач требует создания новых подходов к построению решений.

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

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

В некоторых случаях (если не во всех, где он применим в соответствии с условиями, указанными в главах 1 и 2) Р-алгоритм может давать внешнюю границу множества концов всех iV-траекторий (чего может быть достаточно для его описания, если это множество односвязно). Этот вопрос также требует дальнейшего изучения.

Разработанную автором диссертации библиотеку программ (названную GDGT — «Geometrical Differential Game Template Library»1), рассмотренную в главе 3, предполагается разместить на одной из основных площадок разработчиков открытого программного обеспечения в Интернете, а именно SourceForge.net или Google Code, сделав ее доступной по лицензии семейства MIT [87], в соответствии с которой допускается свободное использование ПО без ограничений, включая неограниченное право на использование, копирование, изменение, добавление, публикацию, распространение и сублицензирование.

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

1 Букв, «библиотека шаблонов геометрических дифференциальных игр

Список литературы диссертационного исследования кандидат физико-математических наук Кувшинов, Дмитрий Рустамович, 2010 год

1. Айзеке Р. Дифференциальные игры. — М.: Мир, 1967.— 479 с.

2. Александреску А. Современное проектирование на С++. — М.; СПб.; Киев: Издательский дом «Вильяме», 2002. — 336 с.

3. Альбрехт Э. Г. Об экстремальных стратегиях в нелинейных дифференцц^ альных играх // Прикл. математика и механика. — 1986.— Т. 50, № 3.—-С. 339-345.

4. Боресков А. В., Харламов А. А. Основы работы с технологией С1ЮА. — ]у . ДМК Пресс, 2010. 232 с.

5. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. — 2 изд. — М.; СПб.: Издательство Бином — Невский Диалект, 1998. 560 с.

6. Буч Г., Рамбо Дою., Джекобсон А. Язык 11МЬ. Руководство пользователя. 2 изд. М.: ДМК Пресс; СПб.: Питер, 2004. - 432 с.

7. Вайсблат П. М., Клейменов А. Ф. Решение одной иерархической дифферец. циальной игры двух лиц // Управление с гарантированным результатом. — Свердловск, 1987. С. 15-27.

8. Вахрушев В. А., Тарасьев А. М., Ушаков В. Н. Алгоритмы построения пересечения и объединения множеств на плоскости // Управление с гарантированным результатом / Под ред. Субботина А. И., Ушакова В. Н. — Свердловск: МММ УНЦ АН СССР, 1987. С. 28-36.

9. Вержбицкий В. М. Основы численных методов: учебник для вузов. — 2 изд. — М.: Высшая школа, 2005. — 840 с.

10. Данилов Н. Н. Решение задачи динамической устойчивости в кооперативной дифференциальной игре с побочными платежами // Прикладная математика и механика. — 1989. —■ Т. 53, вып. 1. — С. 45-59.

11. Жуковский В. И., Чикрий А. А. Линейно-квадратичные дифференциальные игры. — Киев: Наукова думка, 1994. — 320 с.

12. Использование видеокарт для вычислений, http: / /www. gpgpu. ru/.

13. Камзолкин Д. В. Численный метод приближенного вычисления функции цены для задачи оптимального управления с терминальным функционалом // Вычислительные методы и программирование — 2004. Т. 5, № 2. -С. 121-132.

14. Клейменов А. Ф. Позиционные дифференциальные неантагонистические игры. — Екатеринбург: Наука, 1993. — 184 с.

15. Клейменов А. Ф. О решениях в неантагонистической позиционной дифференциальной игре // Прикладная математика и механика, — 1997.— Т. 61, № 5. С. 739-746.

16. Клейменов А. Ф. Различные типы решений в позиционной неантагонистической дифференциальной игре // Вестник Тамбовского ун-та. Серия Естественные и технические науки. — 2007. Вып. 4. — С. 464-466.

17. Клейменов А. Ф, Кувшинов Д. Р., Осипов С. И. Численное построение решений Нэша и Штакельберга в линейной неантагонистической позиционной дифференциальной игре двух лиц // Труды Института математики и механики УрО РАН. 2009. - Т. 15, № 4. - С. 120-133.

18. Клейменов А. Ф., Осипов С. И., Черепов А. С., Кувшинов Д. Р. Численное решение одной иерархической дифференциальной игры двух лиц // Известия Уральского ун-та. — Екатеринбург, 2006. — 46. — С. 160-170.

19. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа, — 7 изд. — М.: Физматлит, 2004. — 572 с.

20. Кононенко А. Ф. О равновесных позиционных стратегиях в неантагонистических дифференциальных играх // Докл. АН СССР. — 1976. — Т. 231, № 2. — С. 285-288.

21. Красовский Н. А., Тарасьев А. М. Поиск точек максимума векторного критерия с декомпозиционными свойствами // Труды Института математики и механики. 2009. - Т. 15, № 4. - С. 167-182.

22. Красовский Н. Н. Управление динамической системой. Задача о минимуме гарантированного результата. — М.: Наука, 1985.— 520 с.

23. Красовский Н. Н., Субботин А. Я. Позиционные дифференциальные игры. — М.: Наука, 1974.- 456 с.

24. Кувшинов Д. Р. Алгоритм численного построения решений по Нэшу в позиционной дифференциальной игре двух лиц // Тез. докл. Всероссийской конференции «Динамические системы, управление и наномеханика». — Ижевск: 2009.- С. 42.

25. Кувшинов Д. Р. Алгоритм численного построения решений по Нэшу в позиционной дифференциальной игре двух лиц // Вестник Удмуртского университета (Математика. Механика. Компьютерные науки).— 2009. — № 3.— С. 81-90.

26. Кувшинов Д. Р. Численное построение нэшевских решений в линейной позиционной дифференциальной игре двух лиц // Тез. докл. 40-й Всероссийской молодежной шк.-конф. «Проблемы теоретической и прикладной математики». Екатеринбург: 2009.- С. 236-240.

27. Лагунов В. Н. Игры преследования и введение в теорию игр. — Тверь: Изд-во Твер. гос. ун-та, 1993. — 146 с.

28. Мейерс С. Эффективное использование STL. — СПб.: Питер, 2003.— 224 с.117

29. Нэш Дж. Бескоалиционные игры // Матричные игры.— М.: Физматг^д 1961.-С. 205-221.

30. Осипов С. И. Алгоритм построения алгебраической суммы невыпуклого 0д носвязного и выпуклого многоугольников // Проблемы теоретической и Прикладной математики. — Свердловск: ИММ УНЦ АН СССР, 1989. — С. 11—12

31. Осипов С. И. О реализации алгоритма построения решений для класса иерар„хических игр Штакельберга // Автоматика и телемеханика. — 2007.11.-С. 195-208.

32. Осипов С. И. Решение одного класса иерархических дифференциальных игр (методы, алгоритмы, программы): дис. . кандидата физ.-мат. наук.—- Екатеринбург: УрГУ, 2007. 128 с.

33. Пахотинских В. Ю., Ушаков В. Н. Аппроксимация стабильных мостов в дифференциальных играх с ограничениями на фазовый вектор // Изв. Уральского гос. ун-та. 2002. - Т. 26, № 5. - С. 158-169.

34. Петров Н. Н. Об одной задаче группового преследования с фазовыми ограничениями // Изв. вузов. Математика. — 1994. — № 4. — С. 24-29.

35. Петросян Л. А. Дифференциальные игры преследования. — Л.: Издат. Ленинградского ун-та, 1977. — 222 с.

36. Петросян Л. А. Устойчивость решений в дифференциальных играх со многими участниками // Вестник ЛГУ. — 1977. — № 19. — С. 46-52.

37. Понтрягии Л. С. Линейные дифференциальные игры преследования // Мат. Сб. 1980. - Т. 112, № 3. - С. 307-330.

38. Понтрягин Л. С., Болтянский В. Г., Гамкрелидзе Р. В., Мищенко Е. Ф. Математическая теория оптимальных процессов. — М.: Физматгиз, 1961. — 391 с.

39. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. — М.: Мир, 1989. 489 с.

40. Саттер Г. Решение сложных задач на С++. — М.; СПб.; Киев: Издательский дом «Вильяме», 2002.— 400 с.

41. Система автоматической генерации документации из исходного кода Doxy-gen. http: //www. stack. nl/~dimitri/doxygen/.

42. Страуструп Б. Язык программирования С++, — 3 изд. — СПб.; М.: Невский Диалект — Издательство Бином, 1999. — 991 с.

43. Субботин А. И. Минимаксные неравенства и уравнения Гамильтона-Яко-би. М.: Наука, 1991. - 216 с.

44. Субботин А. И., Чепцов А. Г. Оптимизация гарантии в задачах управления.— М.: Наука. Гл. ред. физ.-мат. лит., 1981. — 288 с.с

45. Тан К. Ш., Стиб В.-Х., Харди И. Символьный С++: Введение в компьютерную алгебру с использованием объектно-ориентированного программирования. 2 изд. - М.: Мир, 2001. - 622 с.

46. Тарасьев А. М., Ушаков В. Н., Хрипунов А. П. Об одном вычислитеа^ЬНОм алгоритме решения игровых задач управления // Прикладная математика и механика. 1987. - Т. 51, № 2. - С. 216-222.

47. У хоботов В. И. Дифференциальная игра с простым движением // ву зов. Математика. — 1991. — № 8. — С. 69-72.

48. Ушаков В. П. К задаче построения стабильных мостов в дифференци^ЛЬНО£игре сближения-уклонения // Изв. АН СССР. Техн. кибернетика. — 1980.4. С. 29-36.

49. Ушаков В. П., Хрипунов А. П. О приближенном построении решений в игровых задачах управления // Прикладная математика и механика. — 1997.1. Т. 61, № 3. С. 413-421.

50. Хайрер Э., Ваннер Г. Решение обыкновенных дифференциальных уравнений Жесткие и дифференциально-алгебраические задачи. Пер. с англ. — М.: Мир 1999.- 685 с.

51. Хлопин Д. В. Пошаговая аппроксимация и конструктивные движения в задачах оптимизации // Проблемы теоретической и прикладной математики: Труды 40-й Всероссийской молодежной конференции. — Екатеринбург: ИММ УрО РАН, 2009. С. 271-275.

52. Чистяков С. В. Элементы динамической теории классических кооперативных игр // Численные и качественные методы прикладной математики (вопросы механики и процессов управления, вып.23). — СПб.: Изд-во С.-Петерб. ун-та, 2004. С. 14-40.

53. Шориков А. Ф. Минимаксное оценивание и управление в дискретных динамических системах. — Екатеринбург: Изд-во Урал, ун-та, 1997. — 242 с.

54. Abou-Kandil H. Solution of N-person Stackelberg games with nearly cooperating leaders // International Journal of Control — 1987. — Vol. 45, no. 3. — Pp. 1043-1050.

55. Agarwal P. K., Flato E., Halperin D. Polygon decomposition for efficient construction of Minkowski sums // Computational Geometry: Theory and Applications. —2002.-Vol. 21.- Pp. 39-61.

56. Bardi M., Dolcetta I. C. Optimal Control and Viscosity Solutions of Hamil-ton-Jacobi-Bellman Equations. — Boston: Birkhâuser, 1997. — 570 pp.

57. Basar T., Olsder G. J. Dynamic Noncooperative Game Theory. — Philadelphia, PA: SIAM, 1999.- 536 pp.

58. Boolean Operations on 3D Selective Nef Complexes: Data Structure, Algorithms, and Implementation / M. Granados, P. Hachenberger, S. Hert et al. // Proc. of the 11th Annu. European Sympos. Algorithms (ESA'03).— Budapest: 2003,— September. — Pp. 654-666.

59. Boost C++ Libraries, http://www.boost.org/.

60. Cardaliaguet P., Plaskacz S. Existence and uniqueness of a Nash equilibrium feedback for a simple non-zero-sum differential game // Int. J. Game Theory. —2003.- Vol. 32.- Pp. 33-71.

61. Carlini E., Falcone M., Ferretti R. An efficient algorithm for Hamilton-Jaco-bi equations in high dimensions // Computing and Visualization in Science.—2004. Vol. 7. - Pp. 15-29.

62. Chen C. I., Cruz J. B. Stackelberg solution for two person games with biased information patterns // IEEE Trans. Automat. Contr.— 1972. — AC-17, N. 6.— Pp. 791-798.

63. Computational Geometry: Algorithms and Applications / M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. — 2 edition. — Berlin: Springer-Verlag, 2000. — 367 pp.

64. Computational Geometry Algorithms Library, http: / /www. cgal. org/.

65. Falcone M. Numerical Methods for Differential Games via PDEs // International Game Theory Review. 2006. - Vol. 8, no. 2. - Pp. 231-272.

66. Guibas L. J., Ramshaw LStolfi J. A Kinetic Framework for Computational Geometry // In. Proc. 24th Annu. IEEE Sympos. Found. Computer Science. — 1983.-Pp. 100-111.

67. Hansen E., Walster G. W. Global Optimization Using Interval Analysis.— 2 edition. N.Y., Basel: Marcel Dekker, Inc., 2004. — 492 pp.

68. Hoffmann C. M. Geometric and solid modeling: an introduction. — San Francisco: Morgan Kaufmann Publishers Inc., 1989. — 338 pp.

69. International Standard ISO/IEC-14882: Programming Languages — C++ / ISO/IEC. 2 edition. - 2003. - October 15. - 786 pp.

70. Jank G., Kun G. Optimal control of disturbed linear-quadratic differential games // European Journal of Control. — 2002. — Vol. 8(2). — Pp. 152-162.

71. Kleimenov A. F., Osipov S. /., Kuvshinov D. R. Numerical Construction of Nash and Stackelberg trajectories in a linear positional differential game // Me^fl.

72. Конф. «Диф. уравнения и топология», поев. 100-летию со дня рождения Л.С.Понтрягина. Тезисы докладов. — М.: 2008. — С. 259.

73. Krasovskii A. N., Krasovskii N. N. Control under Lack of Information. — Berlin: ■ Birkháuser, 1995. 322 pp.

74. Krasovskii N. N., Subbotin A. I. Game-Theoretical Control Problems.— NY. Berlin: Springer-Verlag, 1988. — 517 pp.

75. Kumkov S. S., Patsko V. S., Shinar J. On level sets with "narrow throats" in linear differential games // International Game Theory Review. — 2005. — September. — Vol. 7, no. 3. Pp. 285-312.

76. Melikyan A. A. Generalized Characteristics of First Order PDEs: Applications in Optimal Control and Differential Games. — Boston: Birkhäuser, 1998. — 310 pp.

77. MIT License, http://opensource.org/licenses/mit-license.php.

78. Myers N. C. Traits: a new and useful template technique // C++ Report.— 1995. — June, http: //www. cantrip. org/traits. html.

79. Nef polyhedra in 3-dimensional space, http://www.win.tue.nl/~phachenb/ Nef/.

80. Ramkumar G. D. An Algorithm to Compute the Minkowski Sum Outer-face of Two Simple Polygons //In Proc. 12th Annu. ACM Symos. Computational Geometry.- 1996,- Pp. 234-241.

81. Siek J., Lumsdaine A. Concept Checking: Binding Parametric Polymorphism in C++ // First Workshop on C++ Template Programming, Erfurt, Germany.— 2000. — October 10. http://oonumerics.org/tmpw00/.

82. The OpenGL Graphics System Utility Library (Version 1.3) / N. Chin, C. Frazier, P. Ho et al.; Ed. by J. Leech; Silicon Graphics, Inc.— 1998. — November 4.— 42 pp.

83. Tolwinski B., Haurie A., Leitmann G. Cooperative equilibria in differential games // J. Math. Anal. AppL- 1986. Vol. 119.- Pp. 182-202.94. von Stackelberg H. The theory of the market economy. — London: William Hodge, 1952. — 328 pp.

84. Zakharov V. Game theory approach in communication networks // OASIS: Distributed Search System in the Internet — 1999.