Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте www.za4et.net.ru

Математика Математика

Методы приближённого решения матричных игр

Наклейки для поощрения "Смайлики 2".
Набор для поощрения на самоклеящейся бумаге. Формат 95х160 мм.
19 руб
Раздел: Наклейки для оценивания, поощрения
Забавная пачка "5000 дублей".
Юмор – настоящее богатство! Купюры в пачке выглядят совсем как настоящие, к тому же и банковской лентой перехвачены... Но вглядитесь
60 руб
Раздел: Прочее
Ночник-проектор "Звездное небо, планеты", черный.
Оригинальный светильник-ночник-проектор. Корпус поворачивается от руки. Источник света: 1) Лампочка (от карманных фанариков); 2) Три
350 руб
Раздел: Ночники

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ВЯТСКИЙ ГОСУДАРСТВЕННЫЙ ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ Математический факультет Кафедра алгебры и геометрии Выпускная квалификационная работаМетоды приближённого решения матричных игр Выполнила студентка V курса математического факультета Ветошкина Е. Н. /подпись/ Научный руководитель: к. ф.-м. н., доцент, Ковязина Е. М. /подпись/ Рецензент: к. ф.-м. н., доцент, Караулов В.М. /подпись/ Допущена к защите в ГАК Зав. кафедрой Вечтомов Е. М. « » 2003 г.Декан факультета Варанкина В. И. « » 2003 г.Киров 2003СОДЕРЖАНИЕ Введение 3 §1. Основные понятия 5 §2. Итеративный метод Брауна-Робинсона .10 §3. Монотонный итеративный алгоритм решения матричных игр 16 Приложение .21 Список литературы 24Введение «Теория игр – раздел математики, предметом которого является изучение математических моделей принятия оптимальных решений в условиях конфликта.». Математическая теория игр способна не только указать оптимальный путь к решению некоторых проблем, но и прогнозировать их исход. Матричные игры серьёзно изучаются специалистами, так как они довольно просты и к ним могут быть сведены игры общего вида. Поэтому теория матричных игр хорошо развита, существуют различные методы поиска решения игр. Но в большинстве случаев решение матричных игр представляет собой трудный и громоздкий процесс. Есть примеры, когда даже для матриц размера 3ґ3, процесс поиска решения довольно трудоёмкий. Кроме того, выигрыши игроков в каждой ситуации не всегда определяются точными измерениями. В процессе сбора данных об изучаемом явлении, анализа этих данных и введения при построении модели различных предположений накапливаются ошибки. Они же могут выражаться числами в матрице выигрышей. Поэтому точность в определении значения игры и оптимальных стратегий игроков оправдана не всегда. А также, следует заметить, что погрешность в оценке игроком своего выигрыша не может привести к практически серьёзным последствиям и небольшое отклонение игрока от оптимальной стратегии не влечёт за собой существенного изменения в его выигрыше. Поэтому возникает потребность в разработке численных методов решения матричных игр. В настоящее время в теории игр известны несколько способов приближенного решения матричных игр. Цель выпускной квалификационной работы изучить некоторые методы приближённого решения матричных игр, обосновать их алгоритмы, и, по возможности, реализовать на языке программирования. Работа состоит из введения, трёх параграфов и приложения, в котором приведена программа на языке urbo Pascal, позволяющая находить приближённое решение матричной игры. В первом параграфе приведены основные понятия и утверждения теории матричных игр. Параграф второй посвящён изложению приближённого решения игры методом Брауна-Робинсона (метод фиктивного разыгрывания) и его обоснованию. Приведён пример применения алгоритма для конкретной матричной игры. В третьем параграфе рассмотрен ещё один метод – монотонный итеративный алгоритм приближённого решения матричных игр.§1. Основные понятия Будем рассматривать только парные антагонистические игры, т. е. игры в которых участвуют только два игрока – две противоборствующие стороны и выигрыш одного из игроков равен проигрышу другого.

Кроме того, будем считать, что каждый игрок имеет лишь конечное число стратегий: U1={a1, a2,., am} – множество стратегий первого игрока; U2={b1, b2, . b } – множество стратегий второго игрока. Будем называть эти стратегии чистыми в отличие от смешанных, которые будут введены далее. Множество U1ЧU2 – декартово произведение множеств стратегий игроков называется множеством ситуаций в игре. Для каждой ситуации должен быть определён итог игры. Так как игра антагонистическая достаточно определить выигрыш а одного из игроков, скажем первого. Тогда выигрыш второго игрока будет равен (-а). Таким образом, имеем матрицу выигрышей первого игрока ( для второго игрока матрица выигрышей будет -А): A= Определение. Система Г={U1, U2, A} называется матричной игрой двух лиц. Разыгрывание матричной игры сводится к выбору игроком 1 i-ой строчки матрицы выигрышей, а игроком 2 - j-го столбца. После этого игрок 1 получает выигрыш равный аij, а игрок 2 – (-аij). При правильной игре игрок 1 может всегда гарантировать себе выигрыш, который назовём нижним значением цены игры. Обозначим его: . В свою очередь, игрок 2 может гарантировать себе проигрыш, который назовём верхним значением цены игры. Обозначим его: . Чистые стратегии i и j , соответствующие называются максиминной и минимаксной стратегиями. Лемма 1. В матричной игре . Определение. Ситуация (i , j ) называется ситуацией равновесия, если для iО1,2, ,m, jО1,2, , выполняется неравенство: . Ситуация равновесия это такая ситуация, от которой ни одному из игроков не выгодно отклоняться. В этом случае стратегии i , j называют оптимальными стратегиями игроков. Чтобы такая ситуация существовала необходимо и достаточно равенство верхней и нижней цен игры, т. е. . Определение. Пусть(i , j ) - ситуацией равновесия в матричной игре. Тогда число называется значением или ценой игры. Например, в игре ГА с матрицей А= существует не одна ситуация равновесия. В данной игре их две: (1, 1) и (1, 3). Множество всех ситуаций равновесия в матричной игре обозначим через Z(Г). Лемма о масштабе 1. Пусть Г и Г/ - две матричные игры с матрицей выигрышей А={aij} и A/={a/ij}, причём А/=bА a, b=co s , a=co s . Тогда Z(Г)=Z(Г/) и /= b a (где / - значение цены игры Г/, - значение цены игры Г). Эта лемма имеет большое практическое значение, так как большинство алгоритмов для решения матричных игр основано на предположении, что матрица игры положительна. В случае, когда матрица имеет неположительные элементы, следует прибавить ко всем элементам матрицы число наибольшее по абсолютной величине, из всех отрицательных элементов. Существуют игры, в которых ситуации равновесия в чистых стратегиях не существует. Тогда игрокам бывает не выгодно придерживаться своих минимаксных и максиминных стратегий, так как они могут получить больший выигрыш, отклонившись от них. В этом случае игрокам разумно действовать случайно, т. е. выбирать стратегии произвольно и не сообщать о выборе сопернику. Такие стратегии игроков будем называть смешанными. Определение. Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий.

Так если игрок 1 имеет m чистых стратегий, то его смешанная стратегия x – это набор чисел x=(x1,x2, ,xm), которые удовлетворяют соотношениям , =1. Аналогичным образом определяется смешанная стратегия y игрока 2. Определение. Оптимальными стратегиями игроков называются стратегии, которые при многократном повторении обеспечивают игрокам максимально возможный средний выигрыш (или минимально возможный средний проигрыш). Таким образом, процесс игры при использовании игроками своих смешанных стратегий превращается в случайное испытание, которое назовём ситуацией в смешанных стратегиях. Она обозначается так (x, y), где x и y – смешанные стратегии игроков 1 и 2 соответственно. Для ситуации в смешанных стратегиях каждый игрок определяет для себя средний выигрыш, который выражается в виде математического ожидания его выигрышей:. От матричной игры пришли к новой игре ={X, Y, K}, где X, Y – множества смешанных стратегий игроков, а K – функция выигрышей в смешанных стратегиях. Такую игру называют смешанным расширением матричной игры. Цели игроков остаются прежними: игрок 1 желает получить максимальный выигрыш, а игрок 2 стремится свести свой проигрыш к минимуму. Поэтому для смешанного расширения игры, аналогичным образом определяются верхнее и нижнее значение цены игры, только теперь игроки выбирают свои смешанные стратегии. Обозначим их: В этом случае остаётся справедливой лемма 1, т. е. . Определение. Ситуация (x , y ) в игре образует ситуацию равновесия, если для всех x ОX, yОY выполняется равенство: K(x, y )≤K(x ,y )≤K(x ,y). Чтобы ситуация равновесия в смешанном расширении игры существовала необходимо и достаточно равенство верхней и нижней цен игры, т. е. , где - цена игры. Для случая смешанного расширения игры также справедлива лемма о масштабе. Лемма о масштабе 2. Пусть ГА и ГА/ - две матричные игры А/=aА В, , a=co s , В – матрица с одинаковыми элементами b, т. е. b ij=b для всех i, j. Тогда Z()=Z(ГА/) и А/= a А b (где А/ - значение цены игры ГА/, А - значение цены игры ГА). Теорема. В смешанном расширении матричной игры всегда существует ситуация равновесия. §2. Итеративный метод Брауна-Робинсона (метод фиктивного разыгрывания) Часто в практических задачах нет необходимости находить точное решение матричной игры. Достаточно найти приближённое решение, которое даёт средний выигрыш, близкий к цене игры и приближённые оптимальные стратегии игроков. Ориентировочное значение цены игры может дать уже простой анализ матрицы выигрышей и определение нижней и верхней цен игры. Если они близки, то поисками точного решения заниматься не обязательно, так как достаточно выбрать чистые минимаксные стратегии. Если же они не близки, можно получить приемлемое для практики решение с помощью численных методов решения игр, из которых рассмотрим метод итераций. Пусть разыгрывается матричная игра ГА с матрицей А={aij} размера (mґ ). Идея метода – многократное фиктивное разыгрывание игры с заданной матрицей. Одно разыгрывание игры будем называть партией, число которых неограниченно. В 1-ой партии оба игрока выбирают совершенно произвольные чистые стратегии.

Условный момент, приложенный к звену приведения, называется моментом приведения. Момент приведения равен совокупности всех моментов и сил, приложенных к звеньям механизма. Условный момент инерции звена приведения называется приведённым моментом инерции. Кинетическая энергия звена приведения равна сумме кинетических энергий всех звеньев механизма. Аналогично определяют приведённые силу и массу в точке приведения (рис., а):   где Мп — приведённый момент; Jп — приведённый момент инерции; Рп — приведённая сила; mп — приведённая масса; M1, M2, P2, P3 — моменты и силы, приложенные к звеньям механизма; w1, w2 — угловые скорости звеньев; uB, uC — скорости точек В и С механизма; uS2 — скорость центра тяжести звена 2; uK — скорость точки К приложения силы P2; a2 — угол между векторами P2 и uK; a3 — угол между векторами P3 и uC. Уравнение движения для данного случая:   т. е, Мп в общем случае зависит от времени, положения, скорости.   Уравнения движения обычно являются нелинейными. Методов точного решения их не существует, поэтому пользуются приближёнными графическими, графо-аналитическими и численными методами интегрирования

1. Разработка программы поиска решения системы дифференциальных уравнений двумя методами: Рунге-Кутта и Рунге-Кутта-Мерсона

2. Решение дифференциальных уравнений 1 порядка методом Эйлера

3. Решение систем линейных алгебраических уравнений методом Гаусса и Зейделя

4. Решение задач линейной оптимизации симплекс – методом

5. Сущность и методы принятия управленческих решений

6. Математические модели и методы обоснования управленческих решений и сферы их применения в практике управления
7. Методы анализа управленческих решений
8. Коллективные методы принятия управленческих решений

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

10. Решение систем нелинейных алгебраических уравнений методом Ньютона

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

12. Методы оптимизации при решении уравнений

13. Методы планирования управленческих решений

14. Методы принятия управленческих решений для конкретной проблемы

15. Экспертные методы оценки управленческого решения

16. Решение задачи линейного программирования симплекс-методом

Термо ланч-бокс "Bento" (арт. TK 0049).
Термо ланч-бокс "Бенто" предназначен для тех, кто ценит комфорт при обеде, но не обладает большим количеством времени. Быстро
617 руб
Раздел: Штучно
Зеркальце карманное "Котик", 8x7 см.
Симпатичное карманное зеркало станет Вашим незаменимым помощником и с легкостью разместится даже в небольшой женской сумочке или кармане.
354 руб
Раздел: Зеркала, расчески, заколки
Коробка подарочная "Цветы и павлиньи перья".
Коробка подарочная. Материал: мелованный, ламинированный, негофрированный картон плотностью 1100 г/м2. Отделка: полноцветный декоративный
302 руб
Раздел: Коробки

17. Решения задачи планирования производства симплекс методом

18. Процесс принятия решений. Интуитивная и рациональная технология принятия решений

19. Психолого-педагогические особенности тестовой формы контроля и методы составления тестовых заданий; их практическое применение при обучении студентов зубоврачебного отделения

20. Методы обработки корневых каналов зубов с применением современных медикаментозных средств при лечении периодонтита

21. Система методов менеджмента. Методы управления организацией

22. Метод отдельного случая (кейс-стади) и его использование в практике социальной работы
23. Практическое применение дидактических игр на уроках английского языка
24. Практическое применение теории игр

25. Сравнительная характеристика методов принятия решений относительно инвестиционных программ

26. Билеты, решения и методичка по Информатике (2.0)

27. Лабораторная работа №7 по "Основам теории систем" (Решение задачи коммивояжера методом ветвей и границ)

28. Решение задач - методы спуска

29. Решение систем дифференциальных уравнений методом Рунге-Куты 4 порядка

30. Решение нелинейного уравнения методом касательных

31. Метод последовательных уступок (Теория принятия решений)

32. Методы решения систем линейных неравенств

Электрощетка аккумуляторная телескопическая "Суперуборщик".
Очистка сантехники, кафеля и полов – самая раздражающая хозяйку часть уборки, ведь это занимает много времени и отнимает силы. Больше
1498 руб
Раздел: Щётки для уборки пыли
Фотобумага "Lomond" для струйной печати, А4, 200 г/м2, 50 листов, односторонняя, глянцевая.
Формат: А4 (210х297 мм). Плотность - 200 г/м2. Глянцевая. Односторонняя. Упаковка - 50 листов.
470 руб
Раздел: Фотобумага для цветной печати
Багетная рама "Regina" (цвет - черный + серебряный), 30х40 см.
Багетные рамы предназначены для оформления картин, вышивок и фотографий. Оформленное изделие всегда становится более выразительным и
558 руб
Раздел: Размер 30x40

33. Решение транспортной задачи методом потенциалов

34. Составление и решение нестандартных уравнений графоаналитическим методом

35. Метод Алексея Юрьевича Виноградова для решения краевых задач

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

37. Проблемы и методы принятия решений

38. Методы экспертных оценок при разработке и принятии управленческих решений
39. Современные методы решения экологических проблем на предприятии (на примере ООО "Волготрансгаз" - дочерней структуры ОАО "ГАЗПРОМ")
40. Методология и методы принятия решения

41. Совершенствование методов проектирования кораблей и обоснование проектных решений

42. Метод касательных решения нелинейных уравнений

43. Методы решения некорректно поставленных задач

44. Построение приближенного решения нелинейного уравнения методом Ван-дер-Поля

45. Приближенное решение уравнений методом хорд и касательных

46. Решение задачи Дирихле для уравнения Лапласа методом сеток

47. Нестандартные методы решения тригонометрических уравнений: графический и функциональный

48. Управленческие ситуации и методы их решения

Книга-сейф "Английский словарь", цвет: черный, 24 см.
Этот сейф-шкатулка - точная имитация книги. Будучи поставленным на книжную полку, он ловко затеряется среди настоящей литературы, сохранив
711 руб
Раздел: Копилки
Карандаши для левшей "EasyColors", 12 цветов.
Эти эргономичные цветные карандаши позволяют подготовить руку к письму и сформировать навык работы с пишущими инструментами. Специальные
1517 руб
Раздел: 7-12 цветов
Муфта для коляски Bambola (шерстяной мех + плащевка + кнопки), черная.
Муфта на ручку коляски очень легко одевается и защищает Ваши руки от холода. Ткань муфты водоотталкивающая, она утеплена мехом и небольшим
489 руб
Раздел: Муфты на ручку

49. Эвристические методы решения творческих задач

50. Кинезиология как Метод решения психологических проблем

51. Решение задачи методами линейного, целочисленного, нелинейного и динамического программирования.

52. Выбор методов и моделей принятия решений в управлении инвестиционным процессом на региональном уровне

53. Критерии принятия инвестиционных решений и методы оценки инвестиционных проектов

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

57. Метод касательных. Решения нелинейных уравнений. Паскаль 7.0

58. Классификация методов разработки и принятия управленческих решений

59. Метод программирования и схем ветвей в процессах решения задач дискретной оптимизации

60. Модели и методы принятия решения

61. Принятие решений методом анализа иерархий

62. Решение прикладных задач методом дихотомии

63. Решение систем линейных алгебраических уравнений (прямые методы)

64. Решение системы линейных уравнений методом Гаусса и Жордана-Гаусса

Гель для укрепления зубов R.O.C.S. "Medical Minerals" для детей и подростков, со вкусом клубники, 45.
Благодаря определенным добавкам он формирует стабильную невидимую пленку на зубах, обеспечивает постепенное проникновение минералов в
354 руб
Раздел: Зубные пасты
Кино-хлопушка.
Реальная кино-хлопушка. Материалы: мдф, фанера. Качественная трафаретная окраска.
418 руб
Раздел: Прочее
Папка для тетрадей "Чемпионат мира по футболу 2018. Талисман", красная, А4.
Формат: А4. Застежка: молния.
365 руб
Раздел: Канцтовары, хобби

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

66. Численные методы решения систем линейных уравнений

67. Антивирусные программы. Матричный принцип печати. Решение задач на ЭВМ

68. Методы принятия решений в маркетинге

69. Исследование методов решения системы дифференциальных уравнений с постоянной матрицей

70. Итерационные методы решения систем нелинейных уравнений
71. Логические задачи и методы их решения
72. Метод замены неизвестного при решении алгебраических уравнений

73. Методы предварительных эквивалентных преобразований и итерационные методы с минимизацией невязки для решения СЛАУ

74. Методы решения алгебраических уравнений

75. Методы решения систем линейных уравнений

76. Нахождение корня нелинейного уравнения. Методы решения системы нелинейных уравнений

77. Методы экономического обоснования принимаемых решений по выходу на внешний рынок

78. Использование нормативного метода при принятии управленческого решения

79. Методы и модели принятия решений

80. Методы проведения экспертиз при разработке управленческих решений

Стержень для роллеров, синие чернила, F.
Стержень для роллера Parker с чернилами синего цвета, толщина линии — 0,5 мм, длина стержня — 112 мм, длина шарика — 0,8 мм. Цвет чернил:
343 руб
Раздел: Стержни для ручек
Маркер выделитель текста Edding "E-345/6S", 6 цветов 1-5 мм.
Для выделения слов или текста в книгах, брошюрах, письмах и т.п. Практически для любой бумаги для копирования и факсов. Высокая
361 руб
Раздел: Текстовыделители
Кружка-хамелеон "Чеширский кот".
Вам нравятся необычные вещи? Любите удивляться и удивлять всех вокруг? Кружка-хамелеон "Чеширский кот" будет поднимать
304 руб
Раздел: Кружки

81. Методика обучения решению текстовых задач алгебраическим методом

82. Методы решения логических задач

83. Эвристические методы решения творческих задач

84. Графический метод решения химических задач

85. Применение методов экономической статистики при решении задач

86. Графический метод и симплекс-метод решения задач линейного программирования
87. Оптимизационные методы решения экономических задач
88. Решение оптимизационных управленческих задач на основе методов и моделей линейного программирования

89. Математические методы в решении экономических задач

90. Методы решения уравнений линейной регрессии

91. Теория игр и принятие решений

92. Теория игр и принятие решений

93. Производственная программа предприятия и методы ее расчета

94. Электрофизиологические корреляты центральных программ при решении простых моторных задач у лиц с различным профилем асимметрии

95. Выполнение спуска полос в программе PageMaker по "Кварковскому" методу

96. Метод обучения командной игре в "короткий" пас

Папка для чертежей "Городская площадь", А3.
Папка для чертежей и рисунков, с ручками. Формат: А3. Материал: пластик. Застежка: на молнии.
441 руб
Раздел: Папки-портфели, папки с наполнением
Планшетик "Всё обо всём".
Ваш малыш любит умные игры-викторины? Тогда этот планшетик для него! 200 вопросов, 20 разнообразных тем, 3 уровня сложности ждут
432 руб
Раздел: Планшеты и компьютеры
Дополнительный набор "Магнитные истории. Времена года".
«Времена года» - познавательная для Вашего ребенка игра, позволяющая познакомиться с временами года, научиться понимать, чем зима, весна,
323 руб
Раздел: Игры на магнитах

97. Вредоносные программы, классификация. Методы защиты

98. Новый подход к построению методов межпроцедурного анализа программ

99. Разработка программы для решения систем линейных уравнений

100. Разработка формата хранения данных программ и решение задач


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.