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


 

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

15810. Проблема інтересу до навчання в історії російської педагогічної думки 73.5 KB
  УДК 372.4 Аспірант Баранова Анастасія Миколаївна Луганський національний університет імені Тараса Шевченка Проблема інтересу до навчання в історії російської дореволюційної педагогічної думки Проблема інтересу до навчання в історії російської педаго
15811. Проблема інтересу до навчання у педагогічній спадщині Г. Сковороди та О. Духновича 43.5 KB
  Проблемі формування в учнів інтересу до навчання в Україні протягом різних історичних епох приділялося велике значення. Зміст, особливості організації та проведення пізнавального процесу завжди обумовлювались розвитком духовної культури, суспільними взаємовідносинами та прогресивними ідеями
15812. Деловые игры как средство формирования интереса к обучению у студентов ВНЗ 75.5 KB
  Деловые игры как средство формирования интереса к обучению у студентов ВУЗа Баранова А. Н. Значимость образования и его роль в обществе считается приоритетом всестороннего развития современного общества. Образовательные системы в любой стране мира должны способст
15813. ОПРЕДЕЛЕНИЕ ОПТИЧЕСКИХ КОНСТАНТ ПЛЕНОК НА ПОДЛОЖКАХ ИЗ КРЕМНИЯ 1.22 MB
  Среди фундаментальных характеристик вещества одно из основных мест принадлежит оптическим константам ОК показателю преломления n и показателю поглощения. Показатели преломления и поглощения...
15814. ИССЛЕДОВАНИЕ ОПТИЧЕСКИХ ПЛЕНОК ФТОРИДОВ И БИФТОРИДОВ 655.5 KB
  ИССЛЕДОВАНИЕ ОПТИЧЕСКИХ ПЛЕНОК ФТОРИДОВ И БИФТОРИДОВ Со времен своего возникновения технология изготовления многослойных интерференционных покрытий ИП занимающая целую отрасль в оптическом приборостроении претерпела значительные изменения. Современные средства...
15815. МЕТОДЫ АНАЛИЗА УСТОЙЧИВОСТИ ОПТИЧЕСКИХ ИНТЕРФЕРЕНЦИОННЫХ ПОКРЫТИЙ 3.56 MB
  МЕТОДЫ АНАЛИЗА УСТОЙЧИВОСТИ ОПТИЧЕСКИХ ИНТЕРФЕРЕНЦИОННЫХ ПОКРЫТИЙ При решении задач проектирования и изготовления тонкопленочных оптических интерференционных покрытий особое внимание уделяется исследованию воспроизводимости их спектральных характеристик [17]. ...
15816. Microsoft Sql Server 2005. Представления 117 KB
  Microsoft Sql Server 2005. Представления Представления Представления – это именованные запросы на выборку данных инструкции SELECT на языке TSQL хранящиеся в базе данных. В запросах представления можно использовать так же как и таблицы независимо от сложности их инструкций SELECT.
15817. Microsoft SQL Server 2005. Хранимые процедуры 87 KB
  Microsoft SQL Server 2005. Хранимые процедуры Хранимые процедуры Хранимая процедура это наиболее часто используемая в базах данных программная структура представляющая собой оформленный особым образом сценарий вернее пакет который хранится в базе данных а не в отдельном ...
15818. SQL Server 2005. Программирование на T-SQL 78.5 KB
  SQL Server 2005. Программирование на TSQL Программирование на TSQL Синтаксис и соглашения TSQL. Правила формирования идентификаторов Все объекты в SQL Server имеют имена идентификаторы. Примерами объектов являются таблицы представления хранимые процедуры и т.д. Идентификато