Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 9 лет назад пользователемБорис Мишагин
1 Теория игр
2 Теория игр – это совокупность математических методов анализа и оценки конфликтных ситуаций. Задача теории игр состоит в выборе такой линии поведения игрока, отклонение от которой может лишь уменьшить его выигрыш.
3 Моделями теории игр можно описать экономические, правовые, классовые, военные конфликты, взаимодействие человека с природой. Все такие модели в теории игр принято называть играми.
4 Если имеется несколько конфликтующих сторон(лиц),каждая из которых принимает некоторое решение, определяемое заданным набором правил, и каждому из лиц известно возможное конечное состояние конфликтной ситуации с заранее определенными для каждой из сторон платежами, то говорят, что имеет место игра
5 Определения
6 1. Ситуация наз-ся конфликтной, если в ней участвуют стороны, интересы которых полностью или частично противоположны. 2. Игра - это действительный или формальный конфликт, в котором имеется по крайне мере два участника, каждый из которых стремится к достижению собственных целей.
7 3. Допустимые действия каждого из игроков, направленные на достижение некоторой цели, называются правилами игры. 4. Количественная оценка результатов игры называется платежом. 5. Игра называется парной, если в ней участвуют только два лица.
8 6. Парная игра называется игрой с нулевой суммой, если проигрыш одного игрока равен выигрышу второго. 7. Однозначное описание выбора игрока в каждой из возможных ситуаций, при которой он должен сделать личный ход, называется стратегией игрока.
9 8. Стратегия игрока называется оптимальной, если при многократном повторении игры она обеспечивает игроку максимально возможный средний выигрыш ( минимально возможной средний проигрыш).
10 Рассмотрим простейшую модель – игру, в которой участвуют два игрока, множество стратегий каждого игрока конечно, а выигрыш одного игрока равен проигрышу другого (бескоалиционная, конечная, антагонистическая игра двух лиц). Такую игру называют матричной.
11 Пусть 1-й игрок имеет всего m стратегий (i=1,2, …, m), а 2-й – n стратегий (j=1,2,…, n). Тогда игра полностью определяется заданием матрицы, где a ij – выигрыш 1-го игрока при условии, что он выбрал стратегию i (т.е. строку) а 2-й игрок – стратегию j (т.е. столбец). Эти стратегии называют чистыми). Матрица А называется матрицей игры или платежной матрицей.
14 Схема:
15 Например, Соответствующие стратегии: i 0 =1(максиминная), j 0 =1;2 (минимаксная).
16 Теорема. Нижняя цена игры всегда не превосходит верхней цены игры:
18 Например, (2,3)-ситуация равновесная, v =4 – цена игры, i*=2, j*=3 – оптимальные стратегии 1-го и 2-го игроков. Выбрав их, 1-й игрок обеспечит себе выигрыш не менее 4 ед., а 2-й игрок проиграет не более 4 ед. при любом выборе другого игрока.
19 Опр. Вектор, каждая из компонент которого показывает относительную частоту (вероятность) использования игроком соответствующей чистой стратегии, называется смешанной стратегией данного игрока.
24 Пусть – платежная матрица игры. Если она не имеет седловой точки, то единственное решение игры можно найти
25 1) решив две системы:
26 2) по формулам: или
27 Найдем, например, решение игры с платежной матрицей, которая не имеет седловой точки.
28 1) Составим системы: Решив системы, получим: то есть -решение игры.
29 2) Найдем решение по формулам:
30 Сведение матричной игры к двойственной задаче линейного программирования
31 Пусть матрица игры имеет вид
37 (1)
41 Пример. Найти решение игры с матрицей
42 Решение. Перейдем к положительной матрице, прибавив 3 ко всем элементам матрицы А:
43 Составим двойственную задачу линейного программирования:
44 Решим задачу симплексным методом
45 Базис С0С0 P0P q1q1 q2q2 q3q3 q4q4 q5q5 q6q6 1-я итерация q4q q5q q6q
46 Базис С0С0 P0P q1q1 q2q2 q3q3 q4q4 q5q5 q6q6 2-я итерация q4q4 02/301/37/310-1/3 q5q5 02/3 0 7/3 4/301-1/3 q1q1 11/3 1 2/3 001/ /3 001/3
47 Базис С0С0 P0P q1q1 q2q2 q3q3 q4q4 q5q5 q6q6 3-я итерация q4q4 04/70015/71-1/7-2/7 q2q2 12/7 0 14/703/7-1/7 q1q1 11/7 10 2/70-2/73/ /701/72/7
48 Базис С0С0 P0P q1q1 q2q2 q3q3 q4q4 q5q5 q6q6 4-я итерация q3q3 14/150017/15-1/15-2/15 q2q2 12/ /157/15-1/15 q1q1 11/ /15-4/157/ /152/154/15
49 Получаем решение двойственной задачи:
50 Тогда решение игры с матрицей Решение исходной игры:
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.