Iii. Игровые модели принятия решения



Скачать 76.62 Kb.
Дата19.10.2012
Размер76.62 Kb.
ТипДокументы

Раздел III. ИГРОВЫЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЯ


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

Литература: [12-15]
§1. Основные сведения из теории матричных игр.
Любую конфликтную ситуацию принятия решения, в которой участвуют две стороны (игрока) с противоположными интересами и с конечным числом возможностей (стратегий), можно описать в виде матрицы

(1)

В этой модели выбор I игрока сводится к выбору строки (m чистых стратегий), выбор II игрока - к выбору столбца (n чистых стратегий); аij - выигрыш I игрока при стратегиях (i,j); выигрыш II игрока при тех же стратегиях есть число аij с противоположным знаком (игра антагонистическая). Каждый игрок выбирает свою стратегию так, чтобы получить как можно больший выигрыш.

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

Стратегия i* (j*) называется оптимальной чистой стратегией первого (второго) игрока, если для любых i = 1,2,...,m и j = 1,2...n выполнено неравенство

aij*≤ai*j*≤ai*j (2)

Пара оптимальных стратегий (i*j*) называется седловой точкой, а число ai*j* -значением (или ценой) игры (1).

Свойства матричных игр.

1. Седловая точка в матричных играх существует не всегда (примеры см. в [14]). Она существует тогда и только тогда, когда

(3)

Поэтому принципы оптимальности в матричных играх называются принципом минимакса (или максимина).

2. Значение игры, если оно существует, является наименьшим числом в своей строчке и наибольшим в своем столбике.

3. Оптимальные стратегии не изменятся, если ко всем элементам матрицы (1) прибавить или отнять одно и то же число или умножить все элементы матрицы на одно и то же положительное число.

4. Игра (1) может иметь несколько седловых точек. Если (i*,j*), () - седловые точки, то (i*,) и (,j*) - тоже седловые точки (взаимозаменяемость) и ai*j*=gif" name="object6" align=absmiddle width=27 height=21>== (эквивалентность).

5. Если игра (1) не имеет оптимальных чистых стратегий, то вводят смешанные стратегии:

x=(x1,…,xm): 0≤xi≤1, i=1,…,m; x1+…+xn=1 и

=(y1,…,yn): 0≤yj≤1, j=1,…,n; y1+…+yn=1;

х - смешанная стратегия 1 игрока; у - смешанная стратегия II игрока. Таких стратегий у игроков бесконечное множество.

6. В любой матричной игре существуют оптимальные смешанные стратегии x*,y*:

(4)

для любых стратегий х, у. Значением игры в смешанных стратегиях называется число



Решить игру (1) это значит найти пару оптимальных стратегий (чистых или смешанных) и значение игры.
§ 2. Решение игры в чистых стратегиях.
Пример 1. Найти оптимальные чистые стратегии и значения следующей матричной игры:



Чтобы упростить эту игру, умножим каждый элемент матрицы А на 12, а затем каждому элементу прибавим 6 (чтобы избавиться от отрицательных чисел) - см. свойство 3:



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






В этом случае говорят, что первая стратегия доминирует четвертую стратегию.

Так как II игрок (выбирающий столбики) минимизирует выигрыш I игрока, то, как видно из последней матрицы, вторая стратегия II игрока доминирует его первую и третью стратегии, а пятая - четвертую. В итоге исключения доминируемых стратегий получим игру



Игра А' эквивалентна исходной игре в том смысле, что в них оптимальные стратегии одинаковы (свойство 3), a ν(A') = 12ν(A)+6

В игре А' применяем принцип минимакса (3). Вычислим левую часть равенства (З):

max{6,1,3}=6.

Вычислим правую часть равенства (З):

min{l0,7} =7.

Так как равенство (3) не выполнено, то в игре А' и, значит, в игре А, оптимальных чистых стратегий нет.

Пример 2. Решить игру



Решение: max{-2,1,3,-6)=3,

min {3,6,5)=3.

Оптимальные стратегии: i*=3 (третья строка), j*=1 (первый столбик); значение игры ν(А)=3.

Пример 3. Решить игру



В этой игре четыре седловые точки: (1,2), (1,4), (2,1), (2,4); значение игры ν(А)=3. Алгоритм решения матричной игры в чистых стратегиях следующий;

1) выполнить доминирование стратегий для обоих игроков;

2) вычислить обе части равенства (3); если равенство выполнено, то игра имеет решение в чистых стратегиях; если не выполнено - то оптимальных чистых стратегий нет.

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

Для решения игры (1) в смешанных стратегиях сводят ее к паре двойственных задач линейного программирования, применяя неравенство (4). Прямая задача ЛП:

min z=ξ 1 2+...+ξ m (1)

при ограничениях

a11ξ 1+a21ξ 2+…+am1ξ m≥1,

a12ξ 1+a22ξ 2+…+am2ξ m≥1, (2)

………………………….

a1nξ 1+a2nξ 2+…+amnξ m≥1,

ξ 1≥0,…,ξ m≥0 (3)

где

ξ 1=xi*/ν, i=1,…,m; z=1/ν, (4)

a (x1*,…,xn*)=x* - оптимальная смешанная стратегия первого игрока. Задача (1)-(3) соответствует первому игроку, т.е. решая ее симплекс-методом находят оптимальную смешанную стратегию I игрока и значение игры по формулам (4).

Двойственная задача ЛП:

max w=1+2+…+n (5)

при ограничениях

a111+a212+…+am1m≥1,

a121+a222+…+am2m≥1, (6)

………………………….

a1n1+a2n2+…+amnm≥1,

1≥0,…, m≥0, (7)

где

j=yj*/ν, j=1,…,n; w=1/ν, (8)

a (у1*,...,уn*)=у* - оптимальная смешанная стратегия II игрока. Задача (5)-(7) соответствует второму игроку, т.е. решая ее симплекс-методом, находят оптимальную смешанную стратегию II игрока и значение игры по формулам (8).

Пример 4. Решить следующую игру



Решение: Доминируемых стратегий нет, т.е. упростить игру невозможно. Оптимальных чистых стратегий нет, т.к. равенство (3) не выполнено. Поэтому надо решить игру в смешанных стратегиях.

Чтобы исключить случай v≤0 (см. (4),(8)) избавимся от отрицательных элементов матрицы, прибавив ко всем элементам 4. Тогда получим эквивалентную игру



Задача (1)-(3) и (5)-(7) запишутся:

min z= ξ1+ ξ2+ ξ3

при ограничениях

1+3ξ2+2ξ3≥1,

1+6ξ2+ ξ3≥1,

1+7ξ2+8ξ3≥1,

1+4ξ2+ ξ3≥1,

ξ1≥0, ξ2≥0, ξ3≥0;
max w=1+2+3+4

при ограничениях

51+42+23+54≤1

31+62+73+44≤1

21+ 2+83+ 4≤1

1≤0,…,4≤0
Примеры решения таких задач ЛП приведены в разделе II в достаточном количестве. Поэтому подробное решение здесь приводить не будем.

Последняя (оптимальная) симплекс-таблица для двойственной задачи (задачи второго игрока) имеет вид:





1

2

3

4

5

6

7

w

7/29

0

5/29

0

3/29

4/29

3/29

0

1

5/29

1

16/29

0

27/29

7/29

-2/29

0

3

2/29

0

18/29

1

5/29

-3/29

5/29

0

7

3/29

0

144/29

0

65/29

10/29

36/29

1


Отсюда находим решение задачи ЛП: = (5/29,0, 2/29, 0 ) - точка максимума, w*=7/29 - максимальное значение целевой функции.

Оптимальную смешанную стратегию игрока П и значение игры А' находим по формулам (8):

v(A') =1/w* = 29/7; у* = (5/7, 0, 2/7, 0 ).

В исходной игре А: v(А)=v(A')-4=1/7.

В качестве упражнения найдите оптимальную смешанную стратегию I игрока, решая прямую задачу двухфазным симплекс-методом.





Похожие:

Iii. Игровые модели принятия решения iconИнтегрированный алгоритм когнитивной оценки и выбора оптимального варианта онтологической модели
В качестве инструмента оценки был выбран расчет метрик, позволяющий оценить когнитивные качества онтологии посредством анализа ее...
Iii. Игровые модели принятия решения iconИ. И. Гниломедов Использование муравьиного алгоритма для создания системы принятия экономических решений в автоматной модели производства
Мическая модель, представляющая процесс производства в виде конечного автомата. В данной работе описывается система принятия экономических...
Iii. Игровые модели принятия решения iconРабочая программа по курсу «теория принятия решения»
Цель изучения дисциплины состоит в ознакомлении студентов с основными понятиями и методами теории принятия решений, с классами задач,...
Iii. Игровые модели принятия решения iconРазработка системной модели технического объекта
Важным классом задач, решаемых в информационных системах являются задачи принятия решения. Методы и технологии на основаниях, которых...
Iii. Игровые модели принятия решения iconТест «Управленческие решения»
Отождествляет процесс принятия управленческого решения со всем процессом управления
Iii. Игровые модели принятия решения iconЗакон о порядке принятия решения об установлении налоговых льгот или их отмене в республике алтай принят
Настоящий Закон определяет порядок принятия решения об установлении налоговых льгот на территории Республики Алтай в случаях, предусмотренных...
Iii. Игровые модели принятия решения iconПрограмма "Олимп" дополнительного образования инженеров Квалификация "Менеджер производственных систем"
Вводятся основные понятия теории принятия решений: лица, принимающие решения (лпр), порядок подготовки решения (регламент), цели...
Iii. Игровые модели принятия решения icon4 Микроэкономические модели в теории принятия решений
При принятии решений на уровне предприятия весьма полезны соответствующие экономико-математические и эконометрические модели. Рассмотрим...
Iii. Игровые модели принятия решения iconПрограмма курса «дискретные задачи принятия решений»
Математические модели. Дискретные экстремальные задачи. Системы поддержки принятия решений
Iii. Игровые модели принятия решения iconТематический план лекций по специальностям: 05. 13. 01- «Системные анализ, управление и обработка информации»
Постановка задач принятия решений. Классификация задач принятия решений. Этапы решения задач
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org