Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Решение игры без седловой точки




Игра двух лиц с нулевой суммой

  В1 В2 Вn
А1 а11 а12   а1n
А2 а21 a22   a2n
       
Аm am1 am2   amn

 

aij - выигрыш игрока А при выборе игроками А и В стратегий Аi и Вj соответственно.

Игрок А выбирает стратегию i. Его гарантированный выигрыш составит , где минимум берется по всем стратегиям игрока В.

V1 =

Игрок В среди всех своих стратегий выбирает ту, которая обеспечит ему минимальный гарантированный проигрыш

V2 =

Для матричной игры справедливо неравенство V1 V2.

Если V1=V2, то элемент платежной матрицы называется седловой точкой.

Пример. Определить нижнюю и верхнюю цену игры, заданной платежной матрицей

  В1 В2 В3 В4 min aij
A1  
A2  
A3  
A4  
max aij          

Решение игры без седловой точки

Пусть смешанные стратегии игроков А и В заданы векторами

SA=(p1,p2,….pm) и SB=(q1,q2,…….qn), где pi – вероятность (частота) применения игроком А чистой стратегии Аi, qj – вероятность (частота) применения игроком В чистой стратегии Bj. Т.к. речь идет о вероятностях, то справедливо равенство

.

 

Преобразование платежной матрицы

 

Рассмотрим игру без седловой точки

Р= .

Оптимальное решение существует и определяется парой смешанных стратегий SA =(p1, p2) и SB = (q1, q2).

       
   
 


SA = , SB =

a11p1+a21p2 = V

a12p1 +a22p2 =V

р12=1

 

р1 =

р2 =

V = .

Аналогично, при отыскании смешанной стратегии второго игрока,

a11q1+a12q2 = V

a21q1 +a22q2 = V

q1+q2 =1

 

Тогда оптимальная стратегия второго игрока определяется по формулам:

q1=

q2=

Графический метод решения игры

 

Игра (2 x n).

  q1 q2 qn
p1 a11 a12 a1n
p2=1-p1 a21 a22 a2n

 

Ожидаемый выигрыш первого игрока при применении вторым игроком 1-ой стратегии составит

a11p1+a21p2=a11p1+a21(1-p1)=(a11-a21)p1+a21.

Аналогично находятся ожидаемые выигрыши первого игрока при применении вторым игроком 2, 3, n-ой стратегий.

Чистые стратегии второго игрока Ожидаемые выигрыши первого игрока
(a11 - a21)p1+a21
(a12 – a22)p1+a22
n (a1n – a2n)p1+a2n

Пусть дана платежная матрица Р=

       
 
 
   


Примеры. 1. Дана платежная матрица

Чистые стратегии второго игрока Ожидаемый выигрыш первого игрока
(4-3)р1 + 3 = р1+3
(2-5)р1 + 5 = -3р1+5

 

р1=1/2 р2=1/2 SA=(1/2, 1/2). Цена игры V = 7/2.

 
 

 


Найдем оптимальную стратегию для второго игрока

Чистые стратегии первого игрока Ожидаемый проигрыш второго игрока
(4-2)q1 + 2 = 2q1+2
(3-5)q1 + 5 = -2q1+5

 

q1=3/4 q2=1/4 SB=(3/4, 1/4). Цена игры V = 7/2.

 
 

 

 


2. Найдем решение игры вида (2хn), заданной платежной матрицей

Чистые стратегии второго игрока Ожидаемый выигрыш первого игрока
 
 
 
 

 

Чистые стратегии первого игрока Ожидаемый проигрыш второго игрока
 
 

 

 

3. Найдем решение игры (mx2), заданной платежной матрицей

Р =

 

Чистые стратегии первого игрока Ожидаемый проигрыш второго игрока
 
 
 
 

 

Чистые стратегии второго игрока Ожидаемый выигрыш первого игрока
 
 

 

При решении любой игры рекомендуется:

1). Исключить заведомо невыгодные стратегии по сравнению с другими.

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

3). Если седловая точка отсутствует, то решение ищут в смешанных стратегиях.

Решение игр с помощью линейного программирования

Пусть дана платежная матрица

  В1 В2 Вn
А1 а11 а12   а1n
А2 а21 a22   a2n
       
Аm am1 am2   amn

 

a11p1 + a21p2 +…am1pm V,

………………………

a1np1 + a2np2 +…amnpm V,

p1 + p2 + …pm=1

Разделим все ограничения на V

a11 + a21 +… 1,

…………..

a1n + a2n + .. 1

Обозначим =xi, тогда

a11x1 + a21x2 +…am1xm 1,

………………………

a1nx1 + a2nx2 +…amnxm 1,

Т.к. =xi, и p1 + p2 + …pm=1, то x1 +x2 +…xm = , где V необходимо максимизировать, следовательно - минимизировать.

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

a11y1 + a12y2 +…a1nyn 1,

………………………

am1y1 + am2y2 +…amnyn 1,

Целевая функция Z(y) = y1 + y2 …yn стремится к максимуму.

Задача. Предприятие выпускает продукцию трех видов А1, А2, А3, получая прибыль, зависящую от спроса, который может быть в 4-х состояниях В1, В2, В3, В4. Дана матрица прибыли, которую получает предприятие при выпуске i- ой продукции с j –м состоянием спроса

 

  В1 В2 В3 В4
А1
А2
А3

 

Определить оптимальные пропорции в выпускаемой продукции, гарантирующие среднюю величину прибыли при любом спросе.

Решение.

Р=

V1 V2, оптимальное решение ищем в смешанных стратегиях.

SA=(p1, p2, р3) SB=(q1,q2,q3)

xi = , yj = , тогда

 

 

Решая систему, получим

Yопт.=(0,04; 0,15; 0), z(y) = 0,19.

Xопт.=(0,05; 0; 0,14), x1+x2+x3=0,19

Цена игры V= 5,4.

Игры с природой

 

1. Критерий Вальде.Рекомендуется применять максиминную стратегию:

max min aij

2. Критерий максимума.Он выбирается из условия

maxmaxaij

3.Критерий Гурвица.Критерий рекомендует стратегию, определяемую по формуле

max(α min aij + (1- α)max aij), где α – степень оптимизма, которая изменяется в диапазоне (0, 1).

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

Элемент матрицы рисков (rij) находится по формуле

rij = max aij – aij, где max aij – максимальный элемент в столбце исходной матрицы.

Оптимальная стратегия находится из выражения

min(max(max aij – aij)).


Поделиться:

Дата добавления: 2015-08-05; просмотров: 68; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты