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


 

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

18207. Загальна характеристика права інтелектуальної власності 114.5 KB
  Тема: Загальна характеристика права інтелектуальної власності План Інтелектуальна діяльністьяк об’єкт правої охорони Поняття права інтелектуальної власності Субєкти та об’єкти права інтелектуальної власності Система права інтелектуальної власност
18208. Авторське право. Особливості і види договірних відносин у галузі реалізації результатів творчої діяльності 171.5 KB
  Тема №3. Авторське право Вступ 1. Поняття і джерела авторського права. 2. Об'єкти авторського права. 3. Суб'єкти авторських відносин. 4. Суб'єктивне авторське право його зміст і межі. 5. Особливості і види договірних відносин у галузі реалізації результатів творчої ді
18209. Право промислової власності 35.22 KB
  Тема: Право промислової власності. План Поняття промислової власності Патентне право: поняття юридичний механізм види патентів Реєстрація патентів. І. Поняття промислової власності За Паризькою конвенцією про охорону промислової власності від...
18210. Суміжні права. Права виконавців. Права виробників фонограм 35.93 KB
  Тема: Суміжні права 1. Поняття суміжних прав 2. Суб’єкти і об’єкти суміжних прав 3. Виникнення і здійснення суміжних прав 4. Критерії для надання охорони суміжних прав 5. Права виконавців. Права виробників фонограм Поняття суміжних прав Сумі́жні права́...
18211. Засоби фізичного виховання 143 KB
  Змістовий модуль 1 Тема 3. Засоби фізичного виховання Визначення поняття засоби€ основні та допоміжні засоби фізичного виховання рух€ рухова дія€ рухова діяльність€. Фізичні вправи як основний засіб фізичного виховання. 2.1. Визначення понятт
18212. Методи фізичного виховання 154.5 KB
  Змістовий модуль 1 Тема 4. Методи фізичного виховання. Вихідні поняття метод€ методичний прийом€ методика€ методичний підхід€ методичний напрямок€. Методи навчання рухових дій. Методи вдосконалення та закріплення рухових дій. Методи вдоск...
18213. Основи методики фізкультурно-оздоровчих занять із школярами 158 KB
  Змістовий модуль 6 Тема 12. Основи методики фізкультурнооздоровчих занять із школярами. Здоров’я та фактори що на нього впливають. 1.1. Визначення поняття здоров’я€. Здоров’я в ієрархії потреб людини. 1.2. Здоровий спосіб життя та фактори що впливають на здор
18214. Організаційно-методичні особливості проведення уроку фізичної культури в школі 183.5 KB
  Змістовий модуль 5 Тема 11. Організаційнометодичні особливості проведення уроку фізичної культури в школі. План. Зміст навчальної дисципліни Фізична культура€. 1.1. Аналіз шкільної базової програми Основи здоров’я та фізична культура€ Київ 2001 року. ...
18215. Організація і методика фізичного виховання дітей та підлітків з ослабленим здоров’ям 87 KB
  Змістовий модуль 6 Тема 13. Організація і методика фізичного виховання дітей та підлітків з ослабленим здоров’ям. Особливості організації фізкультурнооздоровчих занять учнів підготовчої і спеціальної медичної груп. 1.1. Організація занять фізичними вправами ...