40107

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

Доклад

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

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

Русский

2013-10-15

167.5 KB

26 чел.

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) оптимальные стратегии.


 

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

56424. Інфінітивні групи. Тести. (10-11 класи) 102.5 KB
  Ich habe... meine Hausaufgaben zu machen. meine Hausaufgaben zu mache. zu machen meine Hausaufgaben.
56425. Проектирование ресторана «Атлантида» 1.33 MB
  В настоящее время общественное питание достигло огромного прогресса, который не останавливается, а продолжает развиваться все с большей и большей скоростью. Это доказывается появлением и открытием большого количества ресторанов и баров разного класса, кафе, столовых, всевозможных закусочных и других предприятий
56426. ОРГАНИЗАЦИОННО-ЭКОНОМИЧЕСКАЯ ХАРАКТЕРИСТИКА СПК «ПОБЕДА» ЕРАВНИНСКОГО РАЙОНА 456.5 KB
  В последнее десятилетие произошли кардинальные изменения во многих сферах экономической деятельности, в том числе в системе оплаты труда и отчислений страховых взносов в социальные фонды.
56427. ДЕЯКІ ТАБЛИЦІ ТА АЛГОРИТМИ, ЯКІ ДОПОМАГАЮТЬ УЧНЯМ 36 KB
  Навчити учня вчитися, забезпечити його такою системою знань і умінь, які необхідні для подальшої самоосвіти, розвинути його творчу особистість повинна сьогодні школа. Вона не може дати людині запас знань на все життя...
56428. Внедрение информационных технологий в начальной школе - важный фактор развития способностей ребенка 32.5 KB
  Ведь с помощью компьютера можно получить увидеть или услышать определённую информацию: текст кроссворд картинку звук аудиозапись текстовый материал видеозапись просмотр любого развивающего...
56429. НАЙРОЗУМНІШИЙ 109 KB
  Питання охоплюють мовознавчий матеріал з тем Словосполучення та просте речення та Складносурядні та складнопідрядні речення оскільки бажано гру проводити під час тижня української мови...
56430. ПІДГОТОВКА ВЧИТЕЛЯ ДО РЕАЛІЗАЦІЇ ОЗДОРОВЧОЇ ФУНКЦІЇ ОСВІТИ 114 KB
  Актуальність статті передбачає пропаганду здорового способу життя дітей та молоді через проведення батьківських лекторіїв конференцій тренінгів круглих столів лекцій практичних занять для батьків та учнівської молоді.
56431. КРЕВСЬКА УНІЯ ТА СПРОБИ ЇЇ РЕАЛІЗАЦІЇ НА УКРАЇНСЬКИХ ЗЕМЛЯХ 311.5 KB
  Колишня київська Русь могла сплачувати щедру данину, мала розгалужені торговельні шляхи була спроможна надати Литві матеріальні ресурси і поповнення до війська. Не останню роль відігравав і династичний чинник - правляча литовська династія мала численних нащадків, що потребували власних уділів.
56432. Hörtexte und Aufgaben 138.5 KB
  Diese von mir gebildeten Aufgaben werden nach dem Hören des Textes gemacht. Sie haben nur eine Kontrollfunktion: Was haben die Schüler verstanden? Solche Aufgaben helfen dem Deutschlehrer bei der Arbeit an der Entwicklung der Sprechfertigkeit Hören.