Реферат Теория игр, рафический метод в теории игр
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Челябинский юридический колледж
Кафедра математических и естественнонаучных дисциплин
КУРСОВАЯ РАБОТА
по дисциплине «Математические методы»
Теория игр. Графический метод решения теории игр
| Работу выполнила студентка гр. ПО-001-06 | А.В. Егорова |
| | |
| Руководитель | Н.Р. Хабибуллина |
Челябинск
2009
Содержание
| 1. Введение 2. Основные методы решений 2.1.Основные понятия теории игр2.2.Матричные игры2.3.Решение матричной игры в чистых стратегиях2.4.Принцип доминирования2.5.Решение матричной игры 2×2 в смешанных стратегиях3. Геометрическое решение игры3.1.Решение игр с платежной матрицей 2×n3.2.Решение игр с платежной матрицей m×24. Практическая часть 5. Заключение 6. Список литературы | 3 4 5 7 11 12 15 18 |
Введение
Непрерывное и последовательное развитие социалистического общества, его производительных сил и производительных отношений, повышение эффективности общественного производства непрерывно связанно с совершенствование системы планирования и управления. Современные достижения науки и техники все шире используются в практике для получения научно обоснованных наиболее эффективных решений в сфере планирования и управления.
При решении ряда практических задач (в разных областях деятельности) приходится анализировать ситуации, где налицо две ( или более) враждующие стороны, преследующие противоположные цели, причем результат каждого мероприятия одной из сторон зависит от того, какой образ действия выберет противник.
Необходимость анализировать подобные ситуации вызвала к жизни специальные математический аппарат. Теория игр по существу представляет собой не что иное, как математическую теорию конфликтных ситуаций.
Целью данной работы является рассмотрение не только теории игр в общем, но и ее графический метод решения.
Для наиболее оптимального изучения и рассмотрения поставлены следующие задачи:
1. Кратко изложить понятие о теории игр в целом;
2. Рассмотреть основные методы решений задач теории игр;
3. Детально изучить графический метод решения задач теории игр.
4. Привести примеры задач, решенных с помощью этого метода..
Основные методы решений
1.Основные понятия теории игр
Многие социально-экономические ситуации, в которых рассматриваются вопросы о выборе решения, обладают тем свойством, что в них сталкиваются не мнение двух сторон с различными интересами, каждая из которых для достижения своей цели имеет возможность действовать различными способами,
выбор которых при некоторых условиях может осуществляться в зависимости от
действий противоборствующей стороны. Такие ситуации называют конфликтными.
Математическая модель конфликтной ситуации называется игрой. Теория игр занимается математическими моделями принятия оптимальных решений в условиях конфликта. Любое возможное в игре действие игрока называется его стратегией. Игра называется конечной, если множество стратегий каждого игрока конечно. В противном случае (т.е. когда множество стратегий хотя бы одного игрока бесконечно), игра называется бесконечной. В дальнейшем будем рассматривать только конечные игры двух лиц.
Основной целью теории игр является выявление для каждого из игроков «оптимальных стратегий».
Оптимальной называется стратегия, которая при многократно повторяющейся игре гарантирует игроку максимально возможный средний выигрыш (или, эквивалентно, минимально возможный средний проигрыш). Выбор оптимальной стратегии базируется на принципе, предполагающем, что оба игрока разумны в одинаковой степени и поведение каждого из них направлено на противодействие противнику в достижении его цели. Таким образом, теория игр абстрагируется от ошибок, просчетов, азарта и риска, присущих игрокам, реальных конфликтах.
Будем считать, что выигрыш одного игрока равен в точности проигрышу
второго игрока, такая игра называется игрой с нулевой суммой. Конечная игра двух игроков с ненулевой суммой, в которой выигрыши каждого игрока задаются матрицами отдельно для соответствующего игрока, называется биматричной игрой.
2.Матричные игры
Матричной игрой называется конечная игра двух игроков с нулевой
суммой, в которой задается выигрыш игрока 1 в виде матрицы, строка матрицы
соответствует номеру применяемой стратегии игрока 1, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы
находится выигрыш игрока 1, соответствующий применяемым стратегиям.
Пусть играют 2 игрока P1 и P2. Матрица
элементы aij – выигрыш игрока P1, если P1 – выбирает i строку, а P2 – выбирает j столбец, называется платежной матрицей игры.
Пусть игрок P1 выбирает i строку с вероятностью xi, P2 выбирает j столбец с
вероятностью yj, тогда
Замечание: так как компонентами смешанных стратегий X и Y являются
вероятности, то
Пример. Представить смешанную стратегию в виде выпуклой
комбинации чистых стратегий.
Решение.
Платежной функцией
ожидание его выигрыша, т.е.
Решением матричной игры называют пару смешанных стратегий
число v называемое ценой игры, удовлетворяющих следующим условиям:
1)
Если P1 придерживается своей оптимальной стратегии X*, то какую бы
чистую стратегию не принимал второй игрок P2, P1 получит выигрыш не меньше чем цена игры v.
2)
Если P2 придерживается своей оптимальной стратегии Y*, то какую бы чистую стратегию не применял второй игрок P1, то P2 проиграет не более чем цена игры v.
Теорема
1. Если игрок P1 придерживается своей оптимальной стратегии X*,
а P2 придерживается своей оптимальной стратегии Y*, то
Теорема
2. Любая матричная игра имеет решение в смешанных стратегиях.
3.Решение матричной игры в чистых стратегиях
Рассмотрим матричную игру с игроками P1 и P2 и платежной матрицей
1) Перед игроком P1 стоит задача выбора чистой стратегии, в результате применения которой он получит максимально возможный гарантированный
выигрыш. Если игрок P1 выбрал стратегию
матрицы, в зависимости от выбранной стратегии игроком P2. Предполагая поведение игрока P1 крайне осмысленным, необходимо считать, что игрок P2 сыграет наилучшим для себя образом и на выбор игроком P1 стратегии Xi выберет ту стратегию Yj, при которой выигрыш игрока P1 окажется минимальным.
Обозначим минимальный среди выигрышей через αi:
Продолжая действовать разумно, игрок P1 должен выбрать ту стратегию,
которая максимизирует показатель эффективности, т.е. для которой число αi максимально.
Обозначим:
Число α называется нижней ценой игры в чистых стратегиях, а стратегия
Xi0, которая максимизирует показатель эффективности αi называется максиминной стратегией игрока P1.
Таким образом, если игрок P1 в игре будет следовать максиминной стратегии, то ему при любой игре противника P2 гарантирован выигрыш в чистых стратегиях, не меньший α.
2) Рассмотрим игру с точки зрения игрока P2, который стремиться минимизировать выигрыш игрока P1. Если P2 выберет стратегию
Таким образом, для любой стратегии Yj игрока P2 наибольший его проигрыш равен βj. В интересах игрока P2 выбрать стратегию с минимальным показателем неэффективности. Наименьшее из чисел βj обозначим β:
Число β называется верхней ценой игры в чистых стратегиях, а стратегия Yj0, которая максимизирует показатель неэффективности βj называется минимаксной стратегией игрока P2.
Теорема
3. Для элементов платежной матрицы имеют место неравенства:
Пример. Найти решение игры, заданной платежной матрицей.
Решение:
Решим игру. Пусть
Рассмотрим матрицу
min
max 6 7 4 10
min (6,7,5,10)=5=
Если
A=
Теорема
4. (о разрешимости матричной игры в чистых стратегиях) Если платежная матрица A имеет седловой элемент
i
0 чистая стратегия, а для второго – Yj0 чистая стратегия, а цена игры v =
Пример. Найти решение игры, заданной платежной матрицей A=
Решение:
Решим игру. Пусть
Рассмотрим матрицу
min
max 2 3
оптимальная стратегия первого игрока:
оптимальная стратегия второго игрока:
Ответ: оптимальные стратегии игроков
4.Принцип доминирования
Рассмотрим игру с платежной матрицей
A=
Если
Если
Пример. Упростить платежную матрицу A=
Решение.
1 способ:
доминируемая строка
2 способ:,
5.Решение матричной игры 2×2 в смешанных стратегиях
Решить игру с платежной матрицей
Платежная функция
Решить игру с платежной матрицей
Положим
решения матричной игры
Решая систему, получим
Аналогично для второго игрока:
Если
Решая систему, получим
Пример. Найти решение игры заданной платежной матрицей A=
Решение:
Решим игру. Пусть
Ответ: оптимальные стратегии игроков
Геометрическое решение игры
1.Решение игр с платежной матрицей 2×n
Решить игру с платежной матрицей A=
Алгоритм:
1) Через концы горизонтального отрезка [0;1] провести два перпендикуляра к нему: левый и правый. Каждой точке отрезка [0;1] будем ставить некоторую смешанную стратегию (x;1− x).
2) На левом перпендикуляре от точки 0 отложить элементы
Замечание. Масштабы на левом и правом перпендикулярах должны быть
одинаковы, не обязательно совпадающие с масштабом горизонтального отрезка [0;1].
3) Соединить отрезками элементы .
4) Выделить нижнюю огибающую всех построенных отрезков, и найти максимальную точку (точки). Пусть точка является пересечением отрезков
Решить игру с платежной матрицей A=
Решение:
1. Через концы горизонтального отрезка [0;1] проведем 2 перпендикуляра к нему. Каждой точке отрезка [0;1] будем ставить смешанную стратегию (x; 1− x).
2. На левом перпендикуляре от точки 0 отложить элементы 2, 3, 11. На правом перпендикуляре от точки 1 отложить элементы 7, 5, 2.
3. Соединить отрезками элементы 2 и 7, 3 и 5, 11 и 2.
4. Выделим нижнюю огибающую всех построенных отрезков, и найдем
максимальную точку. Точка является пересечением отрезков [3;5] и [11;2]. Тогда оптимальную стратегию можно найти при помощи матрицы
Решим игру с платежной матрицей
Оптимальные стратегии игроков и цену игры можно найти, решив системы:
Ответ: оптимальные стратегии игроков оптимальные стратегии игроков
2.Решение игр с платежной матрицей m×2
Решить игру с платежной матрицей A=
Алгоритм:
1) Через концы горизонтального отрезка [0;1] провести два перпендикуляра к нему: левый и правый. Каждой точке отрезка [0;1] будем ставить некоторую смешанную стратегию (y;1− y).
2) На левом перпендикуляре от точки 0 отложить элементы
3) Соединить отрезками элементы .
4) Выделить верхнюю огибающую всех построенных отрезков, и найти минимальную точку (точки). Пусть точка является пересечением отрезков Тогда оптимальную стратегию можно найти при помощи матрицы
Пример. Решить игру с платежной матрицей A=
Решение:
Решим графическим методом.
1. Через концы горизонтального отрезка [0;1] проведем 2 перпендикуляра к нему. Каждой точке отрезка [0;1] будем ставить смешанную стратегию (y; 1− y).
2. На левом перпендикуляре от точки 0 отложить элементы 6, 4, 2, 1. На правом перпендикуляре от точки 1 отложить элементы 5, 6, 7, 8.
3. Соединить отрезками элементы 6 и 5, 4 и 6, 2 и 7, 1 и 8.
4. Выделим верхнюю огибающую всех построенных отрезков, и найдем минимальную точку. Точка является пересечением отрезков [6;5] и [1;8]. Тогда оптимальную стратегию можно найти при помощи матрицы
Решим игру с платежной матрицей
Ответ: оптимальные стратегии игроков оптимальные стратегии игроков
Практическая Часть
1. Решить Систему
1.1 По формулам Крамера
Решение.
1)Составим определитель
2)Тогда по теореме Крамера:
3)Проверка:
Ответ:
1.2 Методом Гаусса
Решение.
1)Составим расширенную матрицу системы:
2)Преобразим расширенную матрицу к ступенчатому виду:
3)Расширенная приведена к расширенному виду. Получили следующую систему уравнений:
Ответ:
4. Решить транспортную задачу, заданную таблицей . Спланировать перевозки так, чтобы общая их стоимость была минимальной.
| Пункт отправления | В1 | В2 | В3 | B4 | В5 | Запасы, аi (тонн) |
| А1 | 14 | 8 | 17 | 5 | 3 | 120 |
| А2 | 21 | 10 | 7 | 11 | 6 | 180 |
| А3 | 3 | 5 | 8 | 4 | 9 | 230 |
| Потребности, bj (тонн) | 70 | 120 | 105 | 125 | 110 | 530 |
| | | | | | | | ||
| | | | | | ||||
| | | | | | | | | |
| | ||||||||
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | ||
5. Распределить а=100 единиц средств по четырём предприятиям с целью получения максимальной суммарной прибыли.
| x | g 1 | g 2 | g 3 | g 4 |
| 0 | 0 | 0 | 0 | 0 |
| 20 | 18 | 59 | 81 | 72 |
| 40 | 94 | 39 | 66 | 64 |
| 60 | 52 | 115 | 98 | 81 |
| 80 | 143 | 67 | 139 | 140 |
| 100 | 111 | 116 | 126 | 133 |
Решение.
1)Условная оптимизация.
1.1)Пусть k=4, тогда
| | 0 | 20 | 40 | 60 | 80 | 100 | | |
| 0 | 0 | | | | | | 0 | 0 |
| 20 | | 72 | | | | | 72 | 20 |
| 40 | | | 64 | | | | 64 | 40 |
| 60 | | | | 81 | | | 81 | 60 |
| 80 | | | | | 140 | | 140 | 80 |
| 100 | | | | | | 133 | 133 | 100 |
1.2) Пусть k=3
| | 0 | 20 | 40 | 60 | 80 | 100 | | |
| 0 | 0+0 | | | | | | 0 | 0 |
| 20 | 0+72 | 81+0 | | | | | 81 | 20 |
| 40 | 0+64 | 81+72 | 66+0 | | | | 153 | 20 |
| 60 | 0+81 | 81+64 | 66+72 | 98+0 | | | 145 | 20 |
| 80 | 0+140 | 81+81 | 66+64 | 98+72 | 139+0 | | 170 | 60 |
| 100 | 0+133 | 81+140 | 66+81 | 98+64 | 139+72 | 126+0 | 221 | 20 |
1.3) Пусть k=2
| | 0 | 20 | 40 | 60 | 80 | 100 | | |
| 0 | 0+0 | | | | | | 0 | 0 |
| 20 | 0+81 | 59+0 | | | | | 81 | 0 |
| 40 | 0+153 | 59+81 | 39+0 | | | | 153 | 0 |
| 60 | 0+145 | 59+153 | 39+81 | 115+0 | | | 212 | 20 |
| 80 | 0+170 | 59+145 | 39+153 | 115+81 | 67+0 | | 204 | 20 |
| 100 | 0+221 | 59+170 | 39+145 | 115+153 | 67+81 | 116+0 | 268 | 60 |
1.4) Пусть k=1
| | 0 | 20 | 40 | 60 | 80 | 100 | | |
| 0 | 0+0 | | | | | | 0 | 0 |
| 20 | 0+81 | 18+0 | | | | | 81 | 0 |
| 40 | 0+153 | 18+81 | 94+0 | | | | 153 | 0 |
| 60 | 0+212 | 18+153 | 94+81 | 52+0 | | | 212 | 0 |
| 80 | 0+204 | 18+212 | 94+153 | 52+81 | 143+0 | | 247 | 40 |
| 100 | 0+268 | 18+204 | 94+212 | 52+153 | 143+81 | 111+0 | 306 | 40 |
2) Безусловная оптимизация
2.1)
Прибыль: 306
Так как
2.2)
2.3)
2.4)
Ответ:
Заключение
На основании проведенного исследования можно сделать следующие выводы:
· Теория игр является очень сложной областью знания. При обращении к ней надо соблюдать осторожность и четко знать границы применения.
· Теория игр пытается предсказать результат на основе интерактивных моделей, в которых решения каждой стороны влияют на решения других сторон.
· Смысл «игры» здесь является следующим: действие со стороны одного игрока приводит к действиям со стороны других.
· Теория игр полезна, когда требуется определить наиболее важные и требующие учета факторы в ситуации принятия решений в условиях конкурентной борьбы.
Графический метод является одним из основных методов решения задач теории игр. Главной особенностью этого метода является графической изображение задачи. Именно эта особенность и делает этот метод наиболее простым для восприятия человеком задачи, которую ему нужно решить.
Литература
1.Просветов Г. И. Математические методы в экономике: Учебно-методическое
пособие. – М.: Изд-во РДЛ, 2004.
2. Бережная Е. В., Бережной В. И. Математические методы моделирования
экономических систем: Учеб пособие. – М.: Финансы и статистика, 2003.
3. Экономико-математическое моделирование. / Под ред. И. Н. Дрогобыцкого. –
М.: Изд-во «Экзамен», 2004.
4. Гончарова Г. А., Молчалин А. А. Элементы дискретной математики: Учебное
пособие. – М.: ФОРУМ: ИНФРА-М, 2004.
5. Высшая математика для экономистов: Учебник / Под ред Н. Ш. Кремера –
М.: ЮНИТИ, 2002.
