40107

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

Доклад

Менеджмент, консалтинг и предпринимательство

Пусть игра определена матрицей и ценой игры V. – оптимальная стратегия 1 игрока х является первой координатой некоторой седловой точки фции выигрыша Мх у. СЛЕДСТВИЕ: Если для смешанных стратегий и числа V одновременно выполняются 1 и 2 то будут оптимальными стратегиями игроков а V– цена игры. Докво: умножим 1 на y и просуммируем: умножим 2 на x и просуммируем: Получаем Тогда по следствию Т о седловой точке точка – седловая и –...

Русский

2013-10-15

167.5 KB

22 чел.

22. Теорема о необходимых и достаточных условиях оптимальности смешанных стратегий.

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

Т. [о необходимых и достаточных условиях оптимальности смешанных стратегий]

Пусть игра определена матрицей   и ценой игры V. Для того, чтобы смешанная стратегия  была оптимальной стратегией 1-го игрока  выполнение следующего неравенства:

,    (1)

Для того, чтобы смешанная стратегия  была оптимальной стратегией 2-го игрока  выполнение следующего неравенства:  

    (2). 

Док-во: Рассмотрим с точки зрения 2-го игрока.  

 – оптимальная стратегия 1 игрока  х* является первой координатой некоторой седловой точки  ф-ции выигрыша М(х, у). Тогда по определению седловой точки:

, .

.    

Так как это неравенство выполняется для , то оно выполняется и для   k = 1..n.

Остается    к=1,n. ЧТД.

Вып-ся (1):

,  .

Выделим  смешанную стратегию . Умножим каждое j неравенство на уj и просуммируем. Эти у – неотр.     

.

эта функция имеет седловую точку, выберем  седловую точку (). Для нее вып-ся: . Следовательно

 

В таком случае (по следствию Т о седловой точке) для  х, у   ,     седловая точка  х* – оптимальная стратегия для 1 игр. ЧТД.

СЛЕДСТВИЕ: Если для смешанных стратегий () и числа V одновременно выполняются (1) и (2), то () будут оптимальными стратегиями игроков, а V– цена игры.

Док-во: умножим (1) на y и просуммируем:

умножим (2) на x и просуммируем:

Получаем

 

Тогда по следствию Т о седловой точке точка () – седловая и  – цена игры.

следует из того, что последнее неравенство выполняется для ; если подставить , то получим

ЧТД.

Метод сведения решения игр к решению задачи линейного программирования. (I метод)

Пусть игра определена матрицей   и ценой игры V. По следствию теоремы

Если для смешанных стратегий () и числа V одновременно выполняются (1) и (2), то

– оптимальные стратегии игроков   (*)

Требуется, чтобы V > 0. Если все aij > 0, то V > 0. Если  aij < 0, то ко всем aij прибавляем |min aij|, тогда получим эквивалентные игры, то есть новое V = V +|min aij|, а стратегии те же.

1) Рассмотрим левую часть:

V > 0 необходимо здесь, чтобы не менялся знак, так как делим на V.

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

решение систем равенств и неравенств – задача оптимизации с целевой функцией, составленной с помощью одного равенства/неравенства и систем ограничений в виде других равенств/неравенств:

(1)

На max, потому что стратегия 2-го игрока  

2) Рассмотрим правую часть (аналогично):

  разделим на V > 0:   (2)

Задачи (1) и (2) – двойственные, т.е. решение одной можно найти из решения другой (в последней симплекс-таблице в строке оценок). Значения линейных форм совпадут:

Обозначим некоторое число  (3)

И в качестве  возьмем  (4)

Покажем, что  – компоненты оптимальных смешанных стратегий игроков, а число V – цена игры с матрицей A.

     – смешанные стратегии. Покажем оптимальность:

Умножив неравенства задач (1) и (2) на V получим (*) при полученных нами  – оптимальное решение, а V – цена игры.

Алгоритм:

  1.  по матрице А составить (1) и (2)
  2.  найти решения
  3.  по (3) найти цену игры, по (4) оптимальные стратегии.


 

А также другие работы, которые могут Вас заинтересовать

59828. ПРАЗДНИК ВЕСНЫ 54.5 KB
  А превращу-ка я вас в цветы. Весна-Красна А я тебе на подмогу цветы привел. Что-то подозрительные цветы на этой поляне. Вижу вы настоящие цветы.
59829. Весна на пташиних крилах 46.5 KB
  Мета: Пізнавальний розвиток: продовжувати формувати уявлення дітей про життя птахів комах тварин їх ознакиповедінка зовнішній вигляд вчити встановлювати причинно-наслідкові зв’язки в природі прищеплювати любов до природи...
59830. Свято зустрічі весни. Виховний захід 3 клас 52.5 KB
  Синичка дівчинка Ще в нашому лісі сніги лежать та перший струмочок сьогодні продзвенів мені що весна близько. Йде весна йде весна чарівниченька. Учениця Ось весна вже зовсім близько З гір біжить шумить потік...
59831. «ВЕСНЯНА ФАНТАЗІЯ» В. МОЦАРТА 32.5 KB
  Мета: з’ясувати чи можна побачити живописний образ природи через сприйняття музичного твору Весняна фантазія В. Завдання: навчити учнів співвідносити живописні образи з музичними; узагальнити поняття про образність і виразність у музиці...
59833. Вибір цінностей 54 KB
  Візитна картка уроку: Не збирайте собі скарбів на землі де міль і хробацтво нівечить і де підкопують злодії і викрадають. Збирайте собі скарби на небі де ні міль ані хробацтво не нівечить і де злодії не пробивають стін і не викрадають. Бо де твій скарб там буде і твоє серце. Що таке скарб Що маємо на увазі під земними скарбами Що свідчить про те що вони не вічні Скарби на небі – що це Чи піддаються вони таким небезпекам Чому Робота в групах.
59835. Мати берегиня родини 70 KB
  Хто ж його береже Головною берегинею родини завжди була мати її святою називали. Тарас Шевченко писав: У нашім раї на землі Нічого кращого немає Як тая мати молодая З своїм дитяточком малим
59836. Ich ab Geburt bis Abitur 49 KB
  Весь урок ведеться німецькою мовою, що відповідає вимогам міністерства освіти для 11 класу. Мова вчителя чітка, зрозуміла, ключові фрази повторюються для їх кращого розуміння. Темп уроку задовільний для того, щоб діти встигли прочитати, повторити і записати нові слова.