Презентация на тему: Теория игр

Теория игр
Литература
Введение в теорию игр
Основные понятия ТИ
Определение теории игр
Виды стратегий
Решение игры
Классификация игр
Классификация игр
Классификация игр
Классификация игр
Антагонистические игры
Антагонистическая игра
Пример 1.
Пример 1. Решение.
Платежная матрица игры
Дополнительные условия
Классификация антагонистических игр
Игры с седловой точкой
Верхняя и нижняя границы игры
Пример 2
Игра с седловой точкой
Задача 1.
Игры без седловой точки
Смешанная стратегия -
Зависимости строк (столбцов)
Пример 3.
Сокращение платежной матрицы
Графический метод решения игр
Пример 3. Решение для игрока А
Пример 3. Решение для игрока B
Пример 3. Решение
Решение игр 2 ×n или m×2
Пример 4.
Пример 4.
Пример 4.
Сведение матричных игр к задачам линейного программирования
Игра в форме задачи линейного программирования
Игра в форме ЗЛП
Преобразование модели игры
Игра в форме ЗЛП
Пример 5.
Пример 5.
Пример 5.
Алгоритм решения игры
Игры с «природой»
Игры с «природой»
Принятие решений в условиях неопределенности
Пример 6.
Пример 6.
Пример 6.
Пример 6.
Пример 6.
Пример 6.
1/54
Средняя оценка: 4.4/5 (всего оценок: 20)
Код скопирован в буфер обмена
Скачать (259 Кб)
1

Первый слайд презентации

Теория игр

Изображение слайда
2

Слайд 2: Литература

Василевич Л.Ф. Теория игр. - КИИМ, 2000. Печерский С.Л., Беляева А.А. Теория игр для экономистов. Вводный курс. Данилов В.И. Лекции по теории игр. – М.,2002. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. – М.:Наука, 1985. Мулен Э. Теория игр с примерами из математической экономики. – М.: Мир, 1985

Изображение слайда
3

Слайд 3: Введение в теорию игр

«Что наша жизнь? – Игра.» А.С. Пушкин «Пиковая дама»

Изображение слайда
4

Слайд 4: Основные понятия ТИ

Игра – математическая модель конфликтной ситуации; Игроки – стороны, участвующие в конфликте; Выигрыш – исход конфликта, характеризующий игру с количественной стороны; Стратегия игрока – совокупность правил (программ действий), определяющих поведение игрока на каждом ходе в зависимости от сложившейся в игре ситуации

Изображение слайда
5

Слайд 5: Определение теории игр

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

Изображение слайда
6

Слайд 6: Виды стратегий

Чистая – стратегия, которую выбирают неслучайным образом. Смешанная – набор стратегий, которые рекомендуется выбирать игроку случайным образом в зависимости от ситуации. Активная – стратегия, входящая в смешанную стратегию. Оптимальная стратегия – такая стратегия, которая при многократном повторении игры обеспечивает максимальный средний выигрыш (минимальный средний проигрыш).

Изображение слайда
7

Слайд 7: Решение игры

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

Изображение слайда
8

Слайд 8: Классификация игр

Изображение слайда
9

Слайд 9: Классификация игр

Изображение слайда
10

Слайд 10: Классификация игр

Изображение слайда
11

Слайд 11: Классификация игр

Изображение слайда
12

Слайд 12: Антагонистические игры

и методы их решения

Изображение слайда
13

Слайд 13: Антагонистическая игра

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

Изображение слайда
14

Слайд 14: Пример 1

Правила игры: Игрок А выкладывает монету на стол; Игрок В угадывает ее верхнюю сторону. Если В угадывает – получает от А 1 очко, Не угадывает – уплачивает штраф 1 очко в пользу А. Построить платежную матрицу игры.

Изображение слайда
15

Слайд 15: Пример 1. Решение

Стратегии игрока А: А 1 – выложить герб А 2 – выложить решку Стратегии игрока В: В 1 – назвать герб В 2 – назвать решку В 1 В 2 А 1 -1 1 А 2 1 -1

Изображение слайда
16

Слайд 16: Платежная матрица игры

Изображение слайда
17

Слайд 17: Дополнительные условия

Цель игрока А – получить наибольший выигрыш; Цель игрока В – получить наименьший проигрыш.

Изображение слайда
18

Слайд 18: Классификация антагонистических игр

Изображение слайда
19

Слайд 19: Игры с седловой точкой

Изображение слайда
20

Слайд 20: Верхняя и нижняя границы игры

С позиции игрока А : Минимумы по строкам α i =min a ij ; Игрок А выберет стратегию, чтобы α = max α i α = max (min a ij ) – гарантированный выигрыш – нижняя граница игры С позиции игрока В : Максимумы по столбцам β i =max a ij ; Игрок В выберет стратегию, чтобы β = min β i β = min (max a ij ) – наибольший проигрыш – верхняя граница игры Для любой игры верно: α ≤ ν ≤ β

Изображение слайда
21

Слайд 21: Пример 2

B 1 B 2 B 3 B 4 B 5 α i А 1 3 4 5 2 3 А 2 1 8 4 3 4 А 3 10 3 1 7 6 А 4 4 5 3 4 8 β j α = β =

Изображение слайда
22

Слайд 22: Игра с седловой точкой

Если α = β, то минимаксы А i и В j будут устойчивыми; пара (А i ; В j ) называется седловой точкой ; цена игры ν = α = β ; решение игры - (А i 0 ; В j 0 ; ν )

Изображение слайда
23

Слайд 23: Задача 1

α = ; β = ; Решение игры: (А ; В ; ν = ) B 1 B 2 B 3 B 4 α i А 1 2 4 7 5 А 2 7 6 8 7 А 3 5 3 4 1 β j

Изображение слайда
24

Слайд 24: Игры без седловой точки

Изображение слайда
25

Слайд 25: Смешанная стратегия -

набор чистых стратегий с указанными вероятностями их применения в игре. Общий вид: Краткая форма:

Изображение слайда
26

Слайд 26: Зависимости строк (столбцов)

Стратегия А k называется доминирующей над стратегией А р, если все выигрыши в строке А k не меньше соответствующих выигрышей в строке А р. Стратегия В k называется доминирующей над стратегией В р, если все проигрыши в столбце В k не больше соответствующих проигрышей в столбце В р. Две стратегии называются дублирующими, если все соответствующие выигрыши (проигрыши) одинаковы.

Изображение слайда
27

Слайд 27: Пример 3

B 1 B 2 B 3 B 4 B 5 А 1 4 7 2 3 4 А 2 3 5 6 8 9 А 3 4 4 2 2 8 А 4 3 6 1 2 4 А 5 3 5 6 8 9 А 1 доминирует над А 4 А 2 дублирует А 5 В 1 доминирует над В 2 В 1 доминирует над В 5 В 3 доминирует над В 4 А 1 дублирует А 3

Изображение слайда
28

Слайд 28: Сокращение платежной матрицы

B 1 B 2 B 3 B 4 B 5 А 1 4 7 2 3 4 А 2 3 5 6 8 9 А 3 4 4 2 2 8 А 4 3 6 1 2 4 А 5 3 5 6 8 9 B 1 B 3 А 1 4 2 А 2 3 6

Изображение слайда
29

Слайд 29: Графический метод решения игр

Применяется для Игр без седловой точки Игр, в которых хотя бы один игрок имеет только две активные стратегии (размерность платежной матрицы 2 ×n или m×2 )

Изображение слайда
30

Слайд 30: Пример 3. Решение для игрока А

Схема для игрока А: 3 6 4 2 р 1 р 2 р 0 1 В 1 В 2 р 1 4 2 р 2 =1-р 1 3 6 При В 1 : 4р 1 +3(1-р 1 ) При В 2 : 2р 1 +6(1-р 1 ) Условие оптимума: 4р 1 +3(1-р 1 )= 2р 1 +6(1-р 1 )

Изображение слайда
31

Слайд 31: Пример 3. Решение для игрока B

Схема для В q 1 q 3 =1-q 1 A 1 4 2 A 2 3 6 2 6 4 3 q 1 q 3 q 0 1 При А 1 : 4 q 1 + 2 (1- q 1 ) При A 2 : 3q 1 +6(1- q 1 ) Условие оптимума: 4 q 1 + 2 (1- q 1 ) = 3q 1 +6(1- q 1 )

Изображение слайда
32

Слайд 32: Пример 3. Решение

Найдём значения p 1 и q 1, решая уравнения: Найдём цену игры, подставляя найденные значения р или q в любое из выражений: ν =4*0,6+3*0,4=3,6 Ответ (в полной игре): S A 0 =(0.6, 0.4, 0, 0, 0); S B 0 =(0.8, 0, 0.2, 0, 0); ν =3.6 4 q 1 + 2 (1- q 1 )= 3q 1 +6(1- q 1 ) ~ q 1 =0.8 ~ q 3 =0.2 4р 1 +3(1-р 1 )= 2р 1 +6(1-р 1 ) ~ p 1 =0.6 ~ p 2 =0.4

Изображение слайда
33

Слайд 33: Решение игр 2 ×n или m×2

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

Изображение слайда
34

Слайд 34: Пример 4

Решить игру Строим схему игры

Изображение слайда
35

Слайд 35: Пример 4

Выделяем нижнюю границу выигрыша В 1 МNВ 3 ′ и находим наивысшую точку М этой границы; ордината точки М равна цене игры ν. Определяем пару стратегий, пересекающихся в точке оптимума М. В этой точке пересекаются отрезки В 2 В 2 ′ и В 1 В 1 ′, соответствующие стратегиям В 1 и В 2 игрока B. Следовательно, стратегию В 3 ему применять невыгодно. Исключаем из матрицы третий столбец и решаем полученную игру 2x2

Изображение слайда
36

Слайд 36: Пример 4

Ответ: S A 0 =(1/2; 1/2); S B 0 =(1/6; 5/6; 0); ν =7/2.

Изображение слайда
37

Слайд 37: Сведение матричных игр к задачам линейного программирования

Изображение слайда
38

Слайд 38: Игра в форме задачи линейного программирования

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

Изображение слайда
39

Слайд 39: Игра в форме ЗЛП

Для первого игрока модель игры - выигрыш при ограничениях - выигрыш не меньше цены игры - вероятности использования стратегий

Изображение слайда
40

Слайд 40: Преобразование модели игры

Разделим каждое ограничение на ν : Обозначим X i =x i /v. Если, то

Изображение слайда
41

Слайд 41: Игра в форме ЗЛП

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

Изображение слайда
42

Слайд 42: Пример 5

Торговая фирма разработала несколько вариантов плана продажи товаров на ярмарке с учетом конъюнктуры рынка и спроса покупателей. Показатели дохода представлены в таблице. Определить оптимальный план продажи товаров.

Изображение слайда
43

Слайд 43: Пример 5

Модель для первого игрока (торговой фирмы): при ограничениях Обозначим: вероятность применения торговой фирмой стратегии П 1 — x 1, стратегии П 2 — x 2, П 3 — х 3 ; вероятность использования стратегии К 1 — у 1, стратегии К 2 — y 2, К 3 — у 3. Модель для второго игрока (коньюнктуры рынка): при ограничениях

Изображение слайда
44

Слайд 44: Пример 5

Найдем оптимальное решение задачи для первого игрока симплексным методом*. Получим Ответ: фирма должна придерживаться стратегии при этом она получит доход не менее v = 1/L(X)= 196/45 Х опт = (5/49, 11/196, 1/14), L(X ) min = 45/196 x i = X i * v v =196/45≈4,36 ден. ед.

Изображение слайда
45

Слайд 45: Алгоритм решения игры

Исключить из платежной матрицы заведомо невыгодные стратегии. Определить верхнюю и нижнюю границу игры, проверить наличие седловой точки. Если она есть, решить задачу в чистых стратегиях. Если седловая точка отсутствует, а игра имеет размерность 2 ×n или m×2, решить ее графическим методом. При отсутствии седловой точки и большей размерности матрицы, свести игру к задаче линейного программирования.

Изображение слайда
46

Слайд 46: Игры с «природой»

Изображение слайда
47

Слайд 47: Игры с «природой»

Основная особенность: информация об условиях осуществления действия (хода) отсутствует или неопределенна Игроки: Человек – игрок, действующий целенаправленно (обычно первый игрок) Природа – игрок, действующий случайно;

Изображение слайда
48

Слайд 48: Принятие решений в условиях неопределенности

Критерии выбора стратегии Вальде (пессимистический): max (min a ij ) максимума (оптимистический): max (max a ij ) Гурвица : max ( α * min a ij + (1- α )* max a ij )), α – степень оптимизма Сэвиджа : 1)строится матрица рисков R: r ij = ( max a ij )–a ij 2)критерий min (max r ij )

Изображение слайда
49

Слайд 49: Пример 6

Фирма "Фармацевт" производит медикаменты. Известно, что пик спроса на лекарственные препараты 1-й группы приходится на летний период (сердечно-сосудистой группы, анальгетики), на препараты 2-й группы — на осенний и весенний периоды (антиинфекционные, противокашлевые). Затраты на производство 1 ед. продукции за сентябрь-октябрь составили: по 1-й группе — 20 р.; по 2-й группе— 15 р. при цене продажи 40 р. и 30 р. соответственно. Службой маркетинга установлено, что фирма может реализовать в условиях теплой погоды 3050 ед. продукции 1-й группы и 1100 ед. продукции 2-й группы; в условиях холодной погоды — 1525 ед. продукции 1-й группы и 3690 ед. 2-й группы. Определить стратегию фирмы в выпуске продукции, обеспечивающую максимальный доход от её реализации.

Изображение слайда
50

Слайд 50: Пример 6

Фирма располагает двумя стратегиями: A 1 — в этом году будет теплая погода; A 2 — погода будет холодная. Рассматривая фирму и погоду в качестве двух игроков, получим платежную матрицу Цена игры лежит в диапазоне 16 500 р. ≤ v ≤ 77 500 р.

Изображение слайда
51

Слайд 51: Пример 6

Обозначим: x 1 – вероятность применения фирмой стратегии А 1, x 2 — стратегии А 2, причем х 1 = 1— х 2. Решим игру графическим методом, получим Х опт = (0,56; 0,44), при этом цена игры v = 46 986 р. Оптимальный план производства лекарственных препаратов составит Ответ: фирме целесообразно производить в течение сентября и октября 2379 ед. препаратов 1-й группы и 2239,6 ед. препаратов 2-й группы, тогда при любой погоде она получит доход не менее 46 986 р.

Изображение слайда
52

Слайд 52: Пример 6

Если не представляется возможным использовать смешанную стратегию (договоры с другими организациями), для определения оптимальной стратегии фирмы используем критерии: Критерий Вальде : фирме целесообразно использовать стратегию A 1. Критерий максимума : целесообразно использовать стратегию А 2.

Изображение слайда
53

Слайд 53: Пример 6

Критерий Гурвица : для определенности примем α = 0,4, тогда для стратегии фирмы А 1 для стратегии А 2 фирме целесообразно использовать стратегию А 2

Изображение слайда
54

Последний слайд презентации: Теория игр: Пример 6

Критерий Сэвиджа. Максимальный элемент в первом столбце — 77 500, во втором столбце — 85 850. Элементы матрицы рисков найдём по формуле Матрица рисков имеет вид целесообразно использовать стратегию A 1 или А 2

Изображение слайда