40107

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

Доклад

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

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

Русский

2013-10-15

167.5 KB

24 чел.

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


 

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

6724. Цель определения страны происхождения товара. Товары, полностью происходящие с территории государства 25.74 KB
  Цель определения страны происхождения товара. Товары, полностью происходящие с территории государства. СПТ считается страна, в кот товары были полностью произведены или подвергнуты достаточной переработке в соответствии с установленными критериями, ...
6725. Критерий достаточной переработки (КДП). Операции, не отвечающие КДП. 27.81 KB
  Критерий достаточной переработки (КДП). Операции, не отвечающие КДП. Если в производстве товаров участвуют 2 страны и более СПТ считается страна, в кот были осуществлены последние операции по существенной переработки или изготовлении товаров достато...
6726. Производственные и технологические операции, при выполнении которых товар считается происходящим из той страны, где эти операции имели место 27.25 KB
  Производственные и технологические операции, при выполнении которых товар считается происходящим из той страны, где эти операции имели место. Одним из критериев достаточной переработки является выполнение необходимых условий определенных производств...
6727. Документы, подтверждающие страну происхождения товаров. Декларация о происхождении товара 26.77 KB
  Документы, подтверждающие страну происхождения товаров. Декларация о происхождении товара. При ввозе на таможенную территорию РБ товаров, страна их происхождения определяется на основании сведений, указанных в декларации о происхождении товаров или ...
6728. Сертификаты о происхождении товара и их виды 27.43 KB
  Сертификаты о происхождении товара и их виды. Документом, свидетельствующим о СПТ, является сертификат о происхождении товаров, выданный полномочными, компетентными органами или организациями данной страны или страны вывоза, если в стране вывоза сер...
6729. Условия обязательного представления документов, подтверждающих страну происхождения товаров 26.42 KB
  Условия обязательного представления документов, подтверждающих страну происхождения товаров. Для подтверждения СПТ сертификат о происхождении товара предоставляется в обязательном порядке в случае: предоставление таможенных преференций в отнош...
6730. Определение страны происхождения товаров из стран, которым Республика Беларусь (государства-участники Таможенного союза) во взаимной торговле предоставляет (-ют) преференциальный торговый режим 30.14 KB
  Определение страны происхождения товаров из стран, которым Республика Беларусь (государства-участники Таможенного союза) во взаимной торговле предоставляет (-ют) преференциальный торговый режим. На единой территории государств-участников ТС в отноше...
6731. Определение страны происхождения товаров из стран, которым Республика Беларусь (государства-участники Таможенного союза) во взаимной торговле предоставляет (-ют) торговый режим свободной торговли 28.4 KB
  Определение страны происхождения товаров из стран, которым Республика Беларусь (государства-участники Таможенного союза) во взаимной торговле предоставляет (-ют) торговый режим свободной торговли. На основании соглашения о создании зоны свободной то...
6732. Правовые основы определения таможенной стоимости товаров 29.82 KB
  Правовые основы определения таможенной стоимости товаров. Таможенная стоимость товаров применяется в качестве основы для обложения товаров таможенными пошлинами и налогами, исчисляемыми по адвалорной ставке либо адвалорной составляющей комбинированн...