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


 

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

57753. Мозок. Векторна графіка, багатошарові зображення, керуванням розміщенням об’єктів за шарами 1.62 MB
  Яку функцію виконує головний мозок в організмі ссавців Які відділи має головний мозок ссавців До якої частини нервової системи належить головний мозок Що таке біла речовина Що таке сіра речовина Таким чином головний мозок - важлива частина людського організму.
57754. Выпаривательная установка 2.09 MB
  Приведено обоснование технологической схемы производства электролитических щелоков, предложена новизна к конструкции выпарного аппарата. Приведены теоретические основы процесса выпаривания, выполнены технологические расчеты производства...
57755. Види мутацій. Мутагени 304 KB
  Мета: освітня: розширити знання учнів про мутації та їх види ознайомити з основними мутагенними факторами та їх впливом на живі організми. Актуалізація опорних знань і мотивація навчальної діяльності учнів...
57756. Населення світу. Природний і механічний рух населення 368.5 KB
  Мета: сформувати у учнів систему знань про чисельність, розміщення та склад населення планети; уявлення про відтворення населення, його типах, демографічних процесах в сучасному світі...
57757. Населення України 89.5 KB
  Актуалізація опорних знань та вмінь учнів План на мультимедійній дошці Кількість населення. Природний рух населення. Статевовікова структура населення.
57758. Запліднення. Будова насінини 52.5 KB
  Мета уроку: ознайомити учнів із процесом запліднення у квіткових рослин; розкрити його біологічне значення; дослідним шляхом ознайомити із будовою насінини на прикладі пшениці і квасолі...
57759. Фізика і хімія - науки, що визначають сучасний науково – технічний прогрес 50.5 KB
  Мета уроку: розкрити величезне визначальне значення наук фізики та хімії в розв’язанні глобальних проблем сучасності: енергетичної, продовольчої, технічної, проблеми збереження миру в усьому світі...
57760. Робота з рухомою картою зоряного неба 149.5 KB
  Рухома карта складається з двох частин: рухомого диска (зоряної карти), який може обертатись навколо вісі, що проходить через його центр, і нерухомо розташованого над ним накладного круга.
57761. Изучение звёздного неба 95 KB
  Цели урока: Создать условия для: изучения созвездий наблюдения интересных объектов в этих созвездиях отработки навыков уверенного нахождения созвездий и самых ярких звёзд северного неба...