Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрации Техника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ? Влияние общества на человека Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления

Главная Избранные Случайная статья Познавательные Новые добавления Обратная связь FAQ Итерационный метод решения матричных игр ⇐ ПредыдущаяСтр 9 из 9   Суть статистического метода решения задач в условиях конфликта при заданных условиях исходных данных в виде платёжной матрицы A размерности m× n, у которой m > 2 и n > 2, состоит в многократном розыгрыше партий и носит название метода итераций. В этом методе последовательно чередуются партии, причём в каждом розыгрыше первый игрок А при выборе своей оптимальной стратегии руководствуется принципом максимина, а второй игрок В – минимакса. Разыгрывается большое число партий (k > 30 и чем больше – тем точнее), чтобы результаты объективно отражали истинное значение, т.е. подчинялись нормальному закону распределения. Затем полученные накопленные выигрыши игрока А и проигрыши игрока В статистически обрабатываются (определяются выборочные средние, мода, медиана, СКО и т.п.) с целью получения, как правило, математического ожидания цены игры и определения оптимальных смешанных стратегий каждого игрока. Рассмотрим подробнее метод статистических испытаний применительно к условиям неопределенности в конфликтных ситуациях. Алгоритм итерационного метода (правила розыгрыша). 1. Первый игрок А выбирает чистую стратегию или делает случайный ход. Второй игрок В, зная ход игрока А, анализирует создавшуюся ситуацию и делает ответный ход, выбирая такую чистую стратегию, которая делает его проигрыш минимальным. На этом розыгрыш первой партии заканчивается и производится переход ко второй (последующей) партии. 2. Первый игрок А, анализируя ход игрока В в предыдущей партии, делает второй (следующий) ход, выбирая такую стратегию, которая бы обеспечивала ему максимальный накопленный выигрыш в итоге двух (всех предыдущих) партий. Аналогично игрок В  делает свой ход и выбирает стратегию, исходя из условия, чтобы его накопленный проигрыш в итоге второй (всех предыдущих) партий был минимальным. Далее процедура повторяется до требуемого числа k итераций или до тех пор, пока расхождение между верхней и нижней ценами игры будет больше принятого допуска по точности. Сходимость решения при применении метода итераций может оказаться медленной и потребует большого количества разыгрываемых партий. По этому этот метод предполагает использование ЭВМ большой производительности и достаточным объёмом памяти. Для ручных расчётов результаты удобно представлять в виде таблицы 5.1 (согласно исходной матрицы A  размерности m× n):   Таблица 5.1 – Результаты ручных расчетов

№ итерации

№ стратегии игрока А

Накопленный проигрыш игрока В

№ стратегии игрока В

Накопленный выигрыш игрока А

Нижняя цена игры a

Верхняя цена игры b

Цена игры n *

Отклонение ВЦИ от НЦИ Δ ν = β - α

…

…

1

2

k

                          выбирается min         выбирается max

где:

a – нижняя цена игры (НЦИ), определяемая следующим выражением:

 

                                                  (5.9)

b – верхняя цена игры (ВЦИ), определяемая следующим выражением:

 

                                                  (5.10)

 

n* – цена игры в смешанных стратегиях, определяемая следующим выражением:

 

                                                      (5.11)

 

Поскольку матричная игра имеет решение в смешанных стратегиях и определённую цену игры ν, то при бесконечном увеличении числа итераций справедливо следующее соотношение:

 

                                        (5.12)

 

При решении задач методом итераций число k естественно ограничено, поэтому имеет место следующее соотношение:

 

                                      (5.13

 

Количество итераций можно назначить в зависимости от требуемой точности ε получения цены игры ν, определяемой следующим значением отклонения Δν верхней цены игры от нижней цены игры:

 

                                         (5.14)

 

Пример 6.2. Рассмотрим реализацию метода итераций на примере следующей платёжной матрицы при требуемой точности ε = 0,05:

Произведем анализ платежной матрицы с точки зрения первого игрока. Найдем в каждой строке i = 1, 2, 3 согласно максиминного (5.5) критерия минимальный элемент:

Теперь выберем максимальное значение выигрыша первого игрока из этих трех элементов – (НЦИ):

В данном примере первому игроку безразличен номер стратегии, который ему необходимо применить против второго игрока, т.к. в соответствии с максиминным критерием он имеет гарантированный выигрыш не менее «1» при применении любой из своих стратегий. Аналогично произведем анализ платежной матрицы с точки зрения второго игрока. Второй игрок, т.к. его цель прямо противоположна цели первого игрока, должен применить стратегию, гарантирующую минимальный проигрыш – минимаксный (5.6) критерий и найдем в каждом столбце платежной матрицы j = 1, 2, 3 максимальный элемент:

Теперь выберем минимальное значение проигрыша второго игрока из этих трех элементов – (ВЦИ):

Нетрудно видеть, что оптимальное значение j * = 3 что гарантирует минимальный проигрыш второго игрока при самом разумном поведении первого. Если второй игрок выберет какую-либо другую стратегию, то он при разумном поведении первого проиграет большую сумму по сравнению с а₁₃ = 3 (или а₂₁ = 4, или а₃₂ = 5). Таким образом, условие (5.7) для седловой точки о чистой цене игры не выполняется, а также имеется размерность исходной платежной матрицы «больше двух» (a = 1; b = 3; 3 ´ 3). Поэтому решим задачу в смешанных стратегиях методом итераций для первого А игрока, заполнив таблицу 5.2 согласно правилам розыгрыша.

Определим приближенные значения оптимальных смешанных стратегий первого P* и второго Q* игроков, полученных при помощи метода итераций для k = 20  т.к. при этом D n = ε = 0,05:

где N_i – сколько раз выбирается стратегия А_i в таблице 5.2;

N_j – сколько раз выбирается стратегия В_j в таблице 5.2.

A: p₁* = 9/20; p₂* = 7/20; p₃* = 4/20  Þ i* = i₁  с вероятностью P* (выбирается p_i* = max);

B: q₁* = 5/20; q₂* = 5/20; q₃* = 10/20 Þ j* = j₃ с вероятностью Q* (выбирается q_i* = max).

 

Таблица 5.2 – Решение задачи согласно правилам розыгрыша

№ итерации	№ стратегии игрока А	Накопленный проигрыш игрока В			№ стратегии игрока В	Накопленный выигрыш игрока А			Нижняя цена игры a	Верхняя цена игры b	Цена игры n *	Отклонение ВЦИ от НЦИ Δ ν = β - α
k	i				j				a	β	ν*	D n
1	1	1	2	3	1	1	4	2	1,00	4,00	2,5	3,00
2	2	5	3	5	2	3	5	7	1,50	3,50	2,50	2,00
3	3	7	8	6	3	6	7	8	2,00	2,67	2,34	0,67
4	3	9	13	7	3	9	9	9	1,75	2,25	2,00	0,50
5	1	10	15	10	3	12	11	10	2,00	2,40	2,20	0,40
6	1	11	17	13	1	13	15	12	1,83	2,50	2,17	0,67
7	2	15	18	15	1	14	19	14	2,13	2,71	2,42	0,58
8	2	19	19	17	3	17	21	15	2,12	2,63	2,37	0,51
9	2	23	20	19	3	20	23	16	2,11	2,55	2,33	0,44
10	2	27	21	21	2	22	24	21	2,10	2,44	2,25	0,30
11	2	31	21	23	2	24	25	26	1,90	2,36	2,13	0,46
12	3	33	26	24	3	27	27	27	2,00	2,25	2,12	0,25
13	1	34	28	27	3	30	29	28	2,08	2,30	2,19	0,22
14	1	35	30	30	2	32	30	33	2,14	2,35	2,50	0,21
15	3	37	35	31	3	35	32	34	2,08	2,33	2,20	0,25
16	1	38	37	34	3	38	34	35	2,12	2,38	2,25	0,26
17	1	39	39	37	3	41	36	36	2,18	2,41	2,29	0,23
18	1	40	41	40	1	42	40	38	2,22	2,33	2,27	0,11
19	1	41	43	43	1	43	44	40	2,16	2,32	2,24	0,16
20	2	45	44	45	2	45	45	45	2,20	2,25	2,23	0,05