Студопедия

КАТЕГОРИИ:

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



Игровые модели




Читайте также:
  1. D – технология параметрического моделирования .
  2. GPSS World – общецелевая система имитационного моделирования
  3. Априорный анализ и его роль в статистическом моделировании
  4. Б16 В2 Использование имитационного моделирования в инвестиционных процессах.
  5. Б18 В1 МЕТОДОЛОГИЯ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ РАСПРЕДЕЛЕННЫХ ИНТЕЛЛЕКТУАЛЬНЫХ ИНФОРМАЦИОННЫХ СИСТЕМ
  6. БАЗОВЫЕ МОДЕЛИ КАЧЕСТВА
  7. Базовые условия формирования теоретической модели таможенного дела.
  8. Базы данных как аппарат моделирования.
  9. Балансовые модели в задачах анализа трудовых показателей и показателей использования основных фондов.
  10. Более сложные элементы ER-модели

 

Часто возникают ситуации, в которых различные участники имеют не совпадающие между собой интересы. Математические модели и методы для исследования таких так называемых конфликтных ситуаций получили название теории игр [18].

Приведем простейшие понятия и результаты этой теории. Под словом «игра» понимается совокупность правил, руководствуясь которыми игроки-участники принимают решения. Предположим, что результатом игры является плата, которую в соответствии с правилами проигравший участник платит выигравшим. Для простоты ограничимся сначала так называемыми «играми двух лиц с нулевой суммой». Для того чтобы полностью определить такую игру, нужно задать таблицу платежей – платежную матрицу, например, следующую матрицу размера 3х4:

 

Эта запись означает, что игрок А выбирает одну из строк этой матрицы, а игрок В, не зная выбора А, выбирает один из столбцов матрицы. Число на пересечении выбранных строки и столбца определяет выигрыш первого игрока (соответственно проигрыш второго). Например, если А выбрал вторую строку, а В – третий столбец, то А выиграл 5 единиц, а В их проиграл. Если же А выбрал третью строку, а В – второй столбец, то А проиграл 2 единицы, а В их выиграл.

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

Прежде чем сформулировать ответ, вернемся к рассматриваемой матрице. Сразу видно, что игроку А выгоднее всего выбрать первую строку, так как все ее элементы больше соответствующих элементов остальных строк. Точно так же игроку В выгоднее всего выбрать второй столбец, так как все элементы этого столбца меньше соответствующих элементов остальных столбцов. Следовательно, в данном примере оптимальными стратегиями будут следующие: для А – выбор первой строки, а для В – выбор второго столбца. Число 4, стоящее на пресечении первой строки и второго столбца, носит название цены игры, т. е. платы, которую получает оптимально играющий игрок. Таким образом, в этом примере гарантированный выигрыш А – не менее 4-х единиц и гарантированный проигрыш В – не более 4-х единиц (он равен 4 единицам, если оба игрока играют оптимально).



Если оказывается, что для данной платежной матрицы минимум в какой-либо строке совпадает с максимумом в каком-либо столбце, то эти строка и столбец называются оптимальными, а их пересечение – седловой точкой платежной матрицы. Соответствующее число и будет ценой игры.

Однако далеко не каждая матрица имеет седловую точку, например, матрица седловой точки не имеет. Говорить здесь о максимизации наименьшего возможного выигрыша (минимизации наибольшего возможного проигрыша) возможно только при использовании так называемой смешанной стратегии при многократной игре с одной и той же платежной матрицей. Суть этой стратегии заключается в выборе разных стратегий с определенными частотами. Итак, пусть А выбирает первую строку с частотой х, а вторую – с частотой (1 – х). Аналогично для В соответствующие частоты обозначим через у и (1 –у). Тогда средний выигрыш А, обозначаемый через Е (х, у), равен

Е(х,у)=4(1-х)у+х(1-у)=х+4у-5ху. (11.17)

Нас интересует величина max min E(x,y). Имеем

x y

Еу=4-5х, (11.18)



откуда Еу>0 при , Ey=0 при х= и Еу<0 при . Значит,

(график на рис. 11.7). Следовательно,

(11.19)

 

и оптимальной смешанной стратегией для А будет выбор первой строки с частотой и второй строки – с частотой . Средний проигрыш В, обозначаемый F(x,y), очевидно равен –Е (х, у). Нас интересует величина где

F(x,y)=5xy-x-4y. (11.20)

Имеем Fx=5y-1, откуда Fx< 0 при , Fx = 0 при y = и Fx>0 при < у ≤ 1. Значит,

(график на рис. 11.8). Следовательно,

(11.21)

и оптимальной стратегией для А будет выбор первого столбца с частотой и второго столбца – с частотой .

При оптимальных смешанных стратегиях выигрыш А и соответственно проигрыш В в пять раз меньше максимально возможного при одиночной игре.

 

Отметим также, что в рассмотренном примере мы показали существование оптимальных стратегий и установили равенство

; (11.22)

при этом величину Е(х,у) можно трактовать как математическое ожидание выигрыша, а величину v = определить как цену игры.

Рассмотрим теперь общий случай прямоугольной матрицы

.

При любой допустимой стратегии игрока A: x1 ≥ 0, ...,хm ≥ 0, x1 +x2+…+xm=1 и любой допустимой стратегии игрока В: y1 ≥ 0, ...,ym ≥ 0, y1 +y2+…+ym=1 математическое ожидание выигрыша равно

(11.23)

Множество допустимых стратегий x = (x1,…,xn) игрока А обозначим через X, а множество допустимых стратегий у=(у1,...,yn) игрока В обозначим через Y.

Рассмотренные выше примеры являются частными случаями общих теорем [18] для игр с прямоугольными матрицами (прямоугольными играми); из них, в частности, вытекает:

1. Величины существуют и равны между собой; при этом величина



(11.24)

является ценой игры.

2. Всякая прямоугольная игра имеет цену; каждый игрок в прямоугольной игре всегда имеет оптимальную стратегию.

3. Пусть Е – математическое ожидание выигрыша в прямоугольной игре с матрицей С, имеющей цену v. Тогда для того, чтобы элемент х* =(х1*,...,х*m)Î Х был оптимальной стратегией для игрока А, необходимо и достаточно, чтобы для всякого j =1, 2,...,n базисного вектора y(j) = имело место неравенство

v ≤ E (x*, y(j)). (11.25),

Аналогично для того чтобы элемент у* =(y*1,...,y*n)ÎY был оптимальной стратегией для игрока В, необходимо и достаточно, чтобы для всякого элемента базисного вектора x(i) = имело место неравенство

E (x(i), y*) ≤ v. (11.26)

Покажем теперь на двух примерах, как можно применить эти утверждения для вычисления цен и определения оптимальных стратегий для прямоугольных игр. В качестве таких примеров рассмотрим стратегии ловли на удочку и питания рыбы1.

1 Идея примера взята из книги Вильямса [8], которая также может служить хорошим введением в теорию игр.

 

Представим себе, что существование такого вида рыб, питающихся у поверхности воды, зависит от наличия трех видов летающих насекомых, которые обозначим через т12 и m3 соответственно; насекомые появляются в зоне захвата с частотами 15п, 5п и п (т. е. насекомых т2 в 5 раз больше чем m3, а насекомых т1 в 3 раза больше чем т2).

Допустим, что рыбак В ловит рыбу А на насекомых одного из этих видов, насаживая их на крючок. Тогда матрица стратегий С ловли на удочку и питания рыб имеет следующий вид (табл. 11.1):

 

На основании изложенных утверждений достаточно найти неотрицательные числа х123, y1,y2,y3 и число, удовлетворяющее следующим условиям:

x1+x2+x3=l, y1+y2+y3=1, (11.27)

v ≤ -2x1, -2y1 v,

v ≤ -6x2, -6у2 v,

v ≤ -30x3, -30у3v.

Заменим последние шесть неравенств на равенства. Тогда имеем

х11= , x2=y2= , x33= . (11.28)

Подставляя эти значения в равенства (11.27), получим

v = . (11.29)

. (11.30)

(11.31)

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

Несколько усложним задачу. Предположим, что рыболов иногда использует приманку т4, которая может быть принята по ошибке за одно из трех насекомых, но которая вдвое чаще вызывает подозрение у рыб. Тогда матрица С стратегий ловли на удочку и питания рыб примет вид табл. 11.2:

 

Теперь достаточно найти неотрицательные числа х123, y1,y2,y3,y4 и число v, удовлетворяющие следующим условиям:

x1+x2+x3=l, y1+y2+y3+y4=1, (11.27)

v ≤ -2x1, -y4 –2y1 v,

v ≤ -6x2, -3y4 – 6у2 v,

v ≤ -30x3, -15y4 30у3v.

v ≤ -x1 –3x2 –15 x3

Левая система неравенства переопределена, а правая недоопределена (в левой неизвестных больше, чем неравенств, а в правой меньше). Заметим, что если последнее неравенство в правой колонке

-15y4 30у3v. будет выполнено при у3=0, то оно будет выполнено и при всех у3>0. Следовательно, полагая у3 = 0, правую систему неравенств можно заменить системой трех линейных уравнений

-y4 –2y1 = v, -3y4 – 6у2 = v, -15y4 30у3 = v

с тремя неизвестными y1, у2, у4. Ее решение, очевидно, имеет вид

Подставляя полученные выражения в равенство (11.32), где у3 =0, получим , т. е. цена игры для рыбы отрицательна и равна

, (11.33)

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

(11.34)

Изучим теперь оптимальную стратегию для рыбы, так как у3, = 0, то и x3 = 0, т. е. насекомые m3 слишком опасны для жизни. Тогда из системы четырех неравенств выпадают третье и четвертое, которое при x3 = 0 является следствием двух первых (их полусуммой). Таким образом, для определения x1, х2 и v имеем систему трех уравнений с тремя неизвестными

x1 + x2 + x3 = 1, v = -2x1, v = -6x2,

откуда

и, с учетом x3 = 0,

(11.35)

Значит, оптимальная стратегия для рыбы равна

(11.36)

цена же ее в силу (11.35) равна , т. е. совпадает с (11.34), что, вообще говоря, вытекает из общей теории.

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

 

Контрольные задания

 

1. Рассмотрим задачу об «оптимальном рационе» в случае трех продуктов питания (например, хлебные, молочные и мясные продукты) и трех полезных веществ (углеводы, белки, жиры). Ценовой вектор с = 1, с2, c3) (руб.) примерно равен (10; 20; 50), а вектор b = (b1, b2, b3) минимально необходимого месячного потребления полезных веществ (кг) равен (1,2; 4; 1,5). Будем предполагать также, что матрица имеет вид .

Решить задачу f1(x)= → min при ограничениях Ах ≤ b, х ≥ 0.

2. При тех же ограничениях решить задачу f2(x) = х2 → max .

3. Решить двухкритериальную задачу f1(x)→min, f2(x)→max, заменяя ее минимизацией суперкритерия f(x)=Θf1(x)-(1-Θ)f2(x). Рассмотреть случаи .

4. Привести геометрическую интерпретацию задач 1–3.

5. Рассмотреть задачу поиска в случае трех районов и соотношения = 1 : 2 : 3. Найти условия на параметры p1, р2, p3, при которых задача имеет решение в каждом из районов, т.е. t1 = Т, t2=Т, t3 = Т , и в случае, когда время поиска в каждом из районов одно и то же (t1 = t2 = t3 = T/3).

6. Найти оптимальную стратегию рыбака, использующего в качестве наживки мух и живца, если матрица стратегий имеет вид:

 

 

7. Найти оптимальную стратегию рыбака, если он дополнительно использует искусственных мух и блесну, а матрица стратегий в этом случае имеет вид:

 

 


Дата добавления: 2015-01-05; просмотров: 9; Нарушение авторских прав







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