Заглавная страница
Избранные статьи
Случайная статья
Познавательные статьи
Новые добавления
Обратная связь
FAQ
Написать работу

ТОП 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 *

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

…

выбирается 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

⇐ Предыдущая 1 2 3 4 5 6 7 89