40107

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

Доклад

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

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

Русский

2013-10-15

167.5 KB

28 чел.

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


 

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

11645. Измерение потерь напряжения в проводах. 108 KB
  Измерение потерь напряжения в проводах Цель работы: Ознакомление с общими принципами передачи электрической энергии на большие расстояния и определение потерь напряжения в моделях электрических линий. Теоретическое введение. Передача электрической эне...
11646. Определение удельного сопротивления Резистивного провода. 42.5 KB
  Определение удельного сопротивления Резистивного провода Цель работы : Измерение сопротивления техническим методом и определение удельного сопротивления резистивного провода. Установка : измерение R техническим методом с точным измерением силы тока...
11647. Разработка технологического процесса механической обработки детали типа Вал 43.25 KB
  2 Практическая работа №1Разработка технологического процесса механической обработки детали типа Вал 1.Определение типа производства Определяем тип производства по [3 стр. 6 табл. 1.1]: Исходя из массы детали 1 кг и объема производства 3000 шт/год...
11648. Разработка генератора линейной псевдослучайной последовательности на сигнальном процессоре семейства TSM320C54xx 158.75 KB
  ОТЧЁТ по лабораторной работе №1 Разработка генератора линейной псевдослучайной последовательности на сигнальном процессоре семейства TSM320C54xx Цель работы Изучение процесса создания программ линейных генераторов псевдослучайной последовательности ГПСП н
11649. Разработка генератора нелинейной псевдослучайной последовательности на сигнальном процессоре семейства TMS320C54xx 264 KB
  ОТЧЕТ по лабораторной работе № 2 Разработка генератора нелинейной псевдослучайной последовательности на сигнальном процессоре семейства TMS320C54xx 1 Цель работы Изучение процесса создания программ нелинейных ГПСП на сигнальных процессорах семейства TMS320C54xx фирмы Texas ...
11650. Формирование гармонического колебания на сигнальном процессоре семейства TMS320C54xx 55.5 KB
  ОТЧЕТ по лабораторной работе № 3 Формирование гармонического колебания на сигнальном процессоре семейства TMS320C54xx 1 Цель работы Изучение методов цифрового формирования гармонического колебания и его реализации формирования на цифровом сигнальном процессоре. ...
11651. Разработка КИХ-фильтра на сигнальном процессоре семейства TMS320C54xx 107 KB
  ОТЧЕТ по лабораторной работе №4 Разработка КИХфильтра на сигнальном процессоре семейства TMS320C54xx 1 Цель работы Изучение и исследование программной реализации цифровых фильтров с конечной импульсной характеристикой КИХ на сигнальных процессорах семейства TMS320C54xx ...
11652. Шифры простой замены 801 KB
  Лабораторная работа № 1. Шифры простой замены Описание программы CHANGE Программа CHANGE предназначена для выполнения операций зашифровывания/дерасшифровывания на основе шифра простой замены в русском алфавите. Алфавит являющийся внутренними данными программы включае
11653. Осциллограф однолучевой (одноканальный) 211.5 KB
  Осциллограф однолучевой одноканальный МЕРЫ БЕЗОПАСНОСТИ для пользователя Устанавливать осциллограф на рабочем месте так чтобы во время работы обеспечивалась свободная вентиляция. Вентиляционные отверстия корпуса не должны быть закрыты другими предметами. ...