40107

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

Доклад

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

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

Русский

2013-10-15

167.5 KB

29 чел.

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


 

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

11444. Правила измерения физических величин и определение погрешностей измерений 61 KB
  Лабораторная работа №2 Правила измерения физических величин и определение погрешностей измерений Цель работы: изучить правила определения погрешностей измерений физических величин. Расчетные формулы ...
11445. Проверка закона сохранения энергии 109.5 KB
  Лабораторная работа №3 Проверка закона сохранения энергии Цель работы: проверка с помощью маятника Обербека закона сохранения энергии при поступательном и вращательном движении. Приборы и инструменты: маятник Обербека секундомер масштабная линейка штангенц
11446. Изучение закона сохранения импульса в механике 67 KB
  Лабораторная работа №4 Изучение закона сохранения импульса в механике Цель: экспериментальная проверка закона сохранения импульса при центральном упругом ударе шаров. Приборы и инструменты: экспериментальная установка набор шаров течнические весы л
11447. Изучение колебаний математического маятника и измерение ускорения свободного падения 96.5 KB
  Лабораторная работа №5 Изучение колебаний математического маятника и измерение ускорения свободного падения ...
11448. Измерение длины звуковых волн в воздухе и определение показателя адиабаты 93.5 KB
  Лабораторная работа №8 Измерение длины звуковых волн в воздухе и определение показателя адиабаты Цель работы: измерение длины звуковых волн резонансным методом определение скорости звука в воздухе и термодинамического отношения теплоемкостей. Приборы и принад...
11449. Определение универсальной газовой постоянной 137.5 KB
  Лабораторная работа №16 Определение универсальной газовой постоянной Цель работы: изучение свойств идеального и реального газа экспериментальное определение универсальной газовой постоянной. Приборы и принадлежности: баллон откачивающий насос манометр для изм...
11450. ВИВЧЕННЯ БУДОВИ, ПРИНЦИПУ ДІЇ ТА ВИКОРИСТАННЯ ЛАЗЕРІВ 226.5 KB
  Лабораторна робота №4 ВИВЧЕННЯ БУДОВИ ПРИНЦИПУ ДІЇТА ВИКОРИСТАННЯ ЛАЗЕРІВ Мета роботи: вивчення принципу роботи і визначення довжини хвилі випромінювання газового лазера. Прилади та обладнання: лазер ЛГ209 дифракційна решітка лінійка міліметровий папір. Тео
11451. КВАНТОВА ФІЗИКА 194.5 KB
  КВАНТОВА ФІЗИКА 1. ВСТУП Закони квантової фізики квантової механіки складають фундамент вивчення будови речовини. Вони дозволили зясувати будову атомів встановити природу хімічного звязку властивості напівпровідників та ін. Квантова фізика наука про будов
11452. Исследование скважин методом последовательной смены установившихся притоков 750 KB
  ЛАБОРАТОРНАЯ РАБОТА №1 Исследование скважин методом последовательной смены установившихся притоков. Целью данного исследования скважин является определение коэффициента продуктивности скважин гидропроводности и проницаемости призабойной части пласта. В з