WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 9 | 10 ||

Решение рассматриваемой антагонистической игры 2 2 можно найти геометрическим способом.

Пусть игрок В выбрал первую стратегию (j = 1). Значение целевой функции в этом случае будет Q = 1q11 + 2q21, или с учетом 1 = 1- Q = (1- 2) q11 + 2q21.

Как только первый игрок выберет стратегию 2, целевая функция Q приобретет определенное значение. В зависимости от значения 2 функция Q будет изменяться по прямой (рис. 6.6).

q Q q q q0 *2 Рис. 6.6 Геометрическое решение антагонистической игры 2 Если 2 = 0, то имеем чистую стратегию первого игрока i = 1 и значение целевой функции Q = qn.

Если 2 = 1, то имеем вторую стратегию первого игрока i = 2 и значение целевой функции Q = q21. При 0<2<1 имеем смешанную стратегию = (1,2) и определенные значения целевой функции Q. Так при выборе вторым игроком второй стратегии целевая функция будет Q = 1q12 + 2q22 = (1- 2) q12 + 2q22.

Таким образом, имеется две стратегии 1 и 2 второго игрока. Для каждого значения 2 второй игрок будет выбирать стратегию, которая уменьшает выигрыш первого игрока. На рис. 6.6 жирной линией обозначена линия минимумов целевой функции. Первый игрок, желая максимизировать выигрыш, выa a берет стратегию *2, соответствующую максимину. Следовательно, оптимальной стратегией является стратегия * = (1*, *2), где 1* = 1 – 2*. Соответствующее значение целевой функции Q есть цена игры. Стратегия второго игрока определяется численно из выражения * * q111 + q12(1- 1 ) = или графически a2 a* 1 =, * = a1 + a2 2 a1 + aгде a1 = q21 - q11, a2 = q12 - q22.

П р и м е р 6.1. Найти решение антагонистической игры 2 2, если платежная матрица имеет вид 1 Q =.

4 Как было показано выше i0 = 2, j0 = 2, = 2, = 3,.

Графическое решение задачи представлено на рис. 6.7.

Из рис. 6.7 имеем * * * = 0,5; = 2,5; 1 = 0,5; a1 = 3; a2 = 1; 1 = 1 4; * = 3 4.

2 Таким образом, первый игрок должен 50 % времени использовать свою первую стратегию и 50 % времени вторую чистую стратегию. Второй игрок 25 % времени использует свою первую стратегию и 75 % времени – вторую. При этом первый игрок выиграет 2,5 единицы (не меньше 2,5), второй проиграет не больше 2,5.

Q 1 стратегия игрока B 2 стратегия игрока А 0 Рис. 6.7 Геометрическое решение антагонистической игры 2 2 с платежной матрицей Q = 1 4 6.3.3.2 Игра 2 m m Рассматривается игра с платежной матрицей Q = qij 1 2 m 1 q11 q12 q1m … 2 q21 q22 q2m … Геометрическое решение задачи проводится аналогично игре 2 2. Для этого необходимо нанести линии, соответствующие 1, 2, …, m стратегиям второго игрока. Всего получается n линий (рис. 6.8) Q = q1 j1 + q2 j2 = q1 j (1- 2) + q2 j2.

Какую бы стратегию 2 не выбрал первый игрок, т.е. (1, 2), где 1 = 1 – 2, второй игрок минимизирует ее (выбирает стратегию, при которой выигрыш будет минимальным). Линия минимума на рис. 6.8 показана жирной линией, среди всех точек которой значение целевой функции Q будет максимально – это будет точка О.

По этой точке находится 2* и соответственно 1* = 1 – 2*, а также цена игры = Q (* ).

В оптимальном спектре первого игрока имеется две стратегии, следовательно, оптимальный спектр второго игрока также содержит две стратегии. Это стратегии а и б, проходящие через точку О. Использование этих двух стратегий вторым игроком не дает первому игроку выиграть больше, чем. Таким образом, игра свелась к игре 2 2, где у второго игрока имеются две существенные стратегии а и б.

Q qq1n q O q12 a б q2n q 2* Рис. 6.8 Геометрическое решение антагонистической игры 2 m П р и м е р 6.2. Требуется найти решение игры с платежной матрицей вида 1 2 3 4 1 –4 –1 2 5 6 – 2 11 5 6 3 –2 –10 4 5 5 a 6 Графическое решение задачи представлено на рис. 6.9.

Q = 2* Рис. 6.9 Геометрическое решение антагонистической игры 2 Из рисунка видно, что 2* = 0,5, =2, оптимальный спектр стратегий игроков составляют 2 и стратегии. При этом а2 = 6, а5 = 8 и a2* = 3/7, 5* = 4/7 ( * =, * = 1 - * ).

a2 + a5 5 Таким образом, игра свелась к матрице 2 1 –1 2 5 –Оптимальные стратегии * = (0,5; 0,5), * = (0, 3/7, 0, 0,4/7).

Аналогично ищется решение игры n 2. В этом случае строится график изменения значений целевой функции Q при чистых стратегиях первого игрока в зависимости от смешанной стратегии 2 и определяется минимаксная оптимальная стратегия второго игрока 2*.

6.3.3.3 Игра n m При решении матричной игры размерностью n m могут быть применены два приема:

1) сведение задачи к задаче 2 m или n 2;

2) сведение задачи к задаче линейного программирования.

Для упрощения задачи с матрицей n m используются определенные правила.

Говорят, что стратегия i1 первого игрока доминирует стратегию i2, если для всех j = 1, 2, …, m имеет место qi1 j qi2 j.

В этом случае стратегия i2 заведомо хуже стратегии i1. Стратегия i2 называется доминируемой и может быть исключена из рассмотрения.

Q Говорят, что стратегия j* доминирует стратегию j второго игрока, если для любого i справедливо qij* qij.

Здесь стратегия j заведомо хуже стратегии j*, она называется доминируемой и может быть удалена из рассмотрения.

На рис. 6.10 показано две стратегии первого игрока, вторая стратегия доминирует первую и поэтому может быть исключена из рассмотрения.

При решении игровых задач используются следующие Рис. 6.10 Иллюстрация важные теоремы.

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

Т е о р е м а Если некоторая чистая стратегия а, доминируется смешанной стратегией в, в спектре которой нет а, то удаление а приводит к тождественной игре.

В качестве примера рассмотрим игру, представленную на рис. 6.11. Здесь ни одна из стратегий или 2 не доминирует стратегию 3.

Рассмотрим смешанную стратегию = (0,5; 0,5; 0). Для этой стратегии имеем Q = Q10,5 + Q20,5, где Q1 – значение целевой функции для первой стратегии, а Q2 – для второй стратегии.

Значения целевой функции Q на рис. 6.11 показаны пунктирной линией и эта стратегия доминирует стратегию 3. Согласно теореме 2 стратегия 3 может быть удалена.

Т е о р е м а Решения игр будут тождественными, если каждый элемент платежной матрицы преобразуется следующим образом qij = kqij + b, где k > 0, b > 0 – любые числа.

Q Рис. 6.11 Иллюстрация теоремы Таким образом, без изменения оптимального решения каждый элемент платежной матрицы можно умножить на любое положительное число и сложить с любым положительным числом. При этом новая цена игры будет связана с реальной ценой соотношением = k + b.

П р и м е р 6.3. Рассматривается игра 4 5.

Необходимо провести последовательные преобразования платежной матрицы.

1 2 3 4 1 4p 4p 2p 3p 2p 2 1p 3p 1,5p 2p 4p 3 2p 2p 8p 4p 6p 4 2p 1p 1p 0,5p 0,5p Преобразование платежной матрицы складывается из следующих этапов.

1 Все элементы платежной матрицы делятся на р, в результате получается следующая матрица.

1 2 3 4 1 4 4 2 3 2 1 3 1,5 2 3 2 2 8 4 4 2 1 1 0,5 0,2 Третья стратегия первого игрока доминирует четвертую стратегию, следовательно четвертая стратегия может быть отброшена, и исходная матрица преобразуется к виду.

1 2 3 4 1 4 4 2 3 2 1 3 1,5 2 3 2 2 8 4 3 Вторая стратегия второго игрока доминирует первую стратегию, следовательно эта (первая) стратегия исключается и матрица преобразуется к матрице размерности 3 4.

2 3 4 1 4 2 3 2 3 1,5 2 3 2 8 4 4 В полученной матрице чистых доминирующих стратегий больше нет. Однако, первая и третья стратегии первого игрока образуют смешанную стратегию 1 = 0,5, 3 = 0,5, которая доминирует стратегию 2. Вторая стратегия удаляется и игра принимает размерность 2 5.

2 3 4 1 4 2 3 3 2 8 4 Игру 2 4 можно решать графически, но можно продолжить подобные преобразования дальше, они дадут последующее упрощение задачи.

5 В игре 2 4 пятая стратегия второго игрока доминирует третью, отбрасывание которой приводит к игре 2 3.

2 4 1 4 3 3 2 4 Смешанная стратегия второго игрока 2 = 0,5 и 5 = 0,5 доминирует четвертую стратегию, исключение которой приводит к игре 2 2.

2 1 4 3 2 6.4 РЕШЕНИЕ МАТРИЧНОЙ ИГРЫ МЕТОДОМ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Если нельзя методами упрощения свести игровую задачу к размерности 2 m или n 2, то ее заменяют задачей линейного программирования.

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

Пусть цена игры. Эта величина является максимальным гарантированным выигрышем первого игрока. Так, если первый игрок поддерживает оптимальную смешанную стратегию *, его выигрыш не может быть меньше. Однако, если первый игрок поддерживает не оптимальную стратегию *, а некоторую другую стратегию, то существует некоторый гарантированный выигрыш 1, т.е. при любой стратегии второго игрока, выигрыш первого не может быть меньше 1. При этом 1, и задача первого игрока найти такую стратегию *, при которой 1 примет максимальное значение, равное.

Геометрическую интерпретацию этого положения можно просмотреть на примере задачи 2 n (рис.

6.12).

Если взять 2 2*, гарантированный выигрыш 1 будет меньше цены игры.

Таким образом, задача матричной игры может быть сформулирована для первого игрока как задача нахождения такой стратегии * = (1*, …, n*), при которой максимизируется величина 1 : 1 max, при условии, что выигрыш первого игрока при любых чистых стратегиях j = 1, …, m второго игрока будет больше 1:

q111 + q212 + L + qn1n 1;

q121 + q222 + L + qn1n 1;

L (6.15) q1m1 + q2m2 + L + qnmn 1;

1 0,2 0, K, n 0.

Кроме того считают, что 1 > 0. Это всегда можно сделать, прибавив к составляющим матрицы qij одно и то же положительное число.

Q q1n O 2 2* Рис. 6.12 Геометрическая иллюстрация игры 2 n Разделив на 1 > 0 левые и правые части неравенств и введя новые переменные ui = i / 1, система неравенств преобразуется к виду q11u1 + q21u2 + L + qn1un 1;

q12u1 + q22u2 + L + qn1un 1;

(6.16) L q1mu1 + q2mu2 + L + qnmun 1;

u1 0, u2 0, K, un 0.

Очевидно, что n n n 1 = =, так как = 1, (6.17) ui i i 1 i=1 i=1 i=n тогда является критерием, обратным 1.

ui i=С учетом сказанного задача теории игр превращается в следующую задачу линейного программирования.

n Требуется найти такие ui*, i = 1, 2, …, n, при которых целевая функция принимает минимальui i=ное значение n min (6.18) ui i=и удовлетворяются ограничения q11u1 + q21u2 + L + qn1un 1;

q12u1 + q22u2 + L + qn1un 1;

(6.19) L q1mu1 + q2mu2 + L + qnmun 1;

u1 0, u2 0, K, un 0.

После решения этой задачи – задачи линейного программирования определяются цена игры и значения i* по следующим формулам n * = 1 ;

ui i =* (6.20) * = ui ;

i * * = (1, *, K, * ).

2 n Аналогично для определения оптимальной стратегии * = = (1*, …, m*) второго игрока решается следующая задача m x max (6.21) j j =при ограничениях n * qij > 1; то x* = 0. (6.22) ui j i=В результате решения задачи получают оптимальные значения х1*, х2*, …, хm*, которые позволяют определить оптимальную стратегию второго игрока по формулам = ;

m * x j j =* = u*; (6.23) j j * * = (1, *, K, * ).

2 m Задача линейного программирования для второго игрока двойственна задаче линейного программирования для первого игрока, а это означает, что m n * * =, (6.24) x j ui j=1 i=т.е. 1* = 2* и представляет цену игры.

Из двойственности задачи следует, что 1) если стратегия первого игрока является смешанной и ее спектр состоит из k чистых стратегий, то стратегия второго игрока также будет смешанной со спектром, состоящим из k чистых стратегий;

2) если для некоторого j выполняется строгое неравенство n * qij > 1; то x* = 0.

ui j i=3) если для некоторого i выполняется строгое неравенство m * qij > 1; то u* = 0.

x j j j=СПИСОК ЛИТЕРАТУРЫ 1 Акулич И.Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1993. 336 с.

2 Беллман Р. Динамическое программирование. М.: Издатинлит, 1960. 400 с.

3 Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М.: Наука, 1965.

458 с.

4 Бояринов А.И., Кафаров В.В. Методы оптимизации в химии и химической технологии. М.: Химия, 1975. 576 с.

5 Вентцель Е.С. Исследование операций. М.: Наука, 1980. 230 с.

6 Гасс С. Линейное программирование. М.: Физматиз, 1961. 304 с.

7 Дегтярев Ю.И. Исследование операций. М.: Высшая школа, 1986. 320 с.

8 Исследование операций / Под ред. Дж. Маддер, С. Элмагараби. М.: Мир, 1981. Т. 1. 712 с.

9 Карманов В.Г. Математическое программирование. М.: Физматмет, 2000. 264 с.

10 Кузин Л.Т. Основы кибернетики. М.: Энергия, 1973. Т. 1: Математические основы кибернетики.

504 с.

11 Нейман Дж. фон, Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970. с.

12 Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. М.: Высшая школа, 1998. 304 с.

13 Полак Э. Численные методы оптимизации. М.: Мир, 1997. 376 с.

14 Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике: В 2 ч. М.: Финансы и статистика, 1999. 224 с.

15 Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1975. 534 с.

16 Эддонс М., Стенсфильд Р. Методы принятия решений. М.: Аудит, ЮНИТИ, 1997. 590 с.

17 Юдин Д.Б. Вычислительные методы теории принятия решений. М.: Наука, 1989. 316 с.

18 Юдин Д.Б., Гальштейн Е.Г. Линейное программирование. Теория, методы и приложения. М.:

Наука, 1969. 424 с.

Pages:     | 1 |   ...   | 9 | 10 ||










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.