Сведение решения игры к решению пары взаимно двойственных задач линейного программирования.

 

Исходные данные:

 

 

Для начала проедем анализ на доминирование. i-я строка доминирует j-ю, если все элементы i-той строки больше или равны соответствующим элементам j-той сроки. Т.к. строки выбирает первый игрок, мы убираем из платежной матрицы доминирумые строки. В нашем случае 1-я строка доминирует 3-ю, следовательно, нужно исключить третью строку:

 

 

В полученной платежной матрице 3-й столбец доминирует 5-ый. Т.к. столбцы выбирает второй игрок, мы исключаем из платежной матрицы пятый столбец. В результате получена платежная матрица 3 на 4, которую упростить уже невозможно:

 

Далее проводится анализ игры на седловую точку. Для этого находятся минимальные значения по строкам и максимальные значения по строкам:

 

 

Таким образом, нижняя цена игры , верхняя цена игры . Т.к. , решения игры в чистых стратегиях нет, следовательно, нужно искать решение игры в смешанных стратегиях. Для этого нужно сделать все элементы матрицы неотрицательными, прибавив к каждому элементу число 9. Решение при этом не изменится, а цена игры возрастет на 9 и станет неотрицательной. Матрица примет следующий вид:

 

Решение игры сводится к нахождению решений симметричной пары двойственных задач линейного программирования. Пусть ; – стратегии игроков. Сначала найдем стратегию Q*.

Если второй игрок примет свою оптимальную стратегию, то первый игрок не может улучшить свое положение, отступая от своей оптимальной стратегии. Заставим первого игрока отступить от своей оптимальной стратегии, пользуясь чистыми стратегиями , при этом второй игрок придерживаться своей оптимальной стратегии. В любом случае проигрыш второго игрока не будет больше, чем цена игры V.

 

 

Разделим каждое из неравенств системы (9.1.) на V > 0 и введем обозначения:

В результате замены получим следующую систему:

Поскольку , то переменные удовлетворяют условию:

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

Найти вектор , который обеспечивает максимум целевой функции

(9.1.)

При следующих линейных ограничениях:

(9.2.)

И условии неотрицательности переменных:

(9.3.)

Решение полученной задачи линейного программирования находится симплексным методом. Неравенства системы (9.2.) следует превратить в равенства, для этого добавляются дополнительные базисные переменные:

 

 

 

Последняя симплексная таблица.

	Б	Н
		0, 032	1, 00	0, 00	-0, 07	0, 00	0, 18	-0, 11	-0, 03	--	--
		0, 026	0, 00	0, 00	0, 62	1, 00	-0, 13	0, 15	0, 00	--	--
		0, 065	0, 00	1, 00	1, 23	0, 00	0, 01	-0, 01	0, 07	--	--
		0, 122	0, 00	0, 00	0, 77	0, 00	0, 056	0, 033	0, 033	--	--

 

Получено решение: , .

Цену игры и Q* найдем по формуле

Теперь найдем оптимальную стратегию P* первого игрока. Если первый игрок применяет свою оптимальную стратегию, то второй игрок не может улучшить свое положение, отступая от своей оптимальной стратегии. В случае использования втором игроком своих чистых стратегий , а первым игроком своей оптимальной стратегии P*, выигрыш первого будет не меньше, чем цена игры:

 

Разделим каждое из неравенств системы (9.1.) на V > 0 и введем обозначения:

В результате замены получим следующую систему:

Поскольку , то переменные удовлетворяют условию:

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

Найти вектор , который обеспечивает минимум целевой функции

(9.4.)

При следующих линейных ограничениях:

(9.5.)

И условии неотрицательности переменных:

(9.6.)

Полученная задача является двойственной по отношению к задаче нахождения стратегии второго игрока. Решение двойственной задачи можно взять из последней сиплексной таблицы решения задачи (1).

Аналогичным образом получена цена игры и стратегию P*:

Теперь вернемся к исходной матрице :

Решение этой игры имеет вид:

 

34. Некооперативные биматричные игры, основные понятия и определения. Анализ биматричной игры в некооперативном варианте.

 

Игры, в которых отсутствует обмен информацией между игроками, называются матричными некооперативными.

Игры, в которых игроки вступают непосредственный контакт, называются коопекративными (переговоры, вследствие которых создаются коалиции)

Коалиционные – игроки создают коалиции (2 игрока могут создать три коалиции: только 1, только 2, оба вместе).

Биматричные игры – интересы игроков неполностью противоположны. Они создают две матрицы:

 

На биматричные игры распространяются термины чистой и смешанной стратегии.

 

Биматричная игра в некооперативном варианте

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

Множество пар смежных стратегий игроков

- стратегия игрока А

- стратегия игрока В

Если два игрока выбрали смешанные стратегии соответственно, то математические ожидания выигрышей игроков равны

 

⇐ Предыдущая234567891011Следующая ⇒

Поделиться:

Популярное:

1. I. Иммунология. Определение, задачи, методы. История развитии иммунологии.
2. I. Цели и задачи библиотеки на 2015 год
3. II. 36. Основные задачи семеноводства.
4. II. ЦЕЛИ, ЗАДАЧИ И ВИДЫ ДЕЯТЕЛЬНОСТИ ОРГАНИЗАЦИИ.
5. V1: Предмет, цели и задачи товароведения
6. VII. Задачи научного руководителя дипломной работы
7. А. Сведение всего к абстракциям и количеству
8. Абсолютно твердое тело - система материальных точек, расстояние между которыми не изменяются в данной задаче. Абсолютно твердое тело обладает только поступательными и вращательными степенями свободы.
9. Активные методы обучения (деловые игры, научные проекты)
10. Алгоритм Симплекс-метода для решения задачи линейного программирования об оптимальном использовании ресурсов.
11. Алматова Г. - Экосистема (по мотивам настольной игры «Эволюция»)
12. Ассоциативность памяти и задача распознавания образов