40107

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

Доклад

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

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

Русский

2013-10-15

167.5 KB

32 чел.

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


 

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

24998. Клавиатура (Keyboard) 31.69 KB
  Принцип действия клавиатуры Основным элементом клавиатуры являются клавиши. Сигнал при нажатии клавиши регистрируется контроллером клавиатуры и передается в виде так называемого скэнкода на материнскую плату. На материнской плате ПК для подключения клавиатуры также используется специальный контроллер. Когда скэнкод поступает в контроллер клавиатуры инициализируется аппаратное прерывание процессор прекращает свою работу и выполняет процедуру анализирующую скэнкод.
24999. Принцип работы модемов 62.47 KB
  Современные модемы обеспечивают гораздо большую скорость передачи данных. Применяемые в них протоколы передачи данных и коррекции ошибок обеспечивают надежную связь даже на не очень хороших телефонных линиях. В процессе передачи компьютерных данных по большинству линий связи выполняется двойное их ' преобразование: поток данных из компьютера побайтно преобразуется в последовательность отдельных бит которая далее превращается в сигнал при годный для передачи по телефонным линиям. Принимаемые данные претерпевают обратное преобразование: из...
25000. О мониторах - подробнее 131 KB
  Количество точек по горизонтали и по вертикали которые могут изображаться на экране монитора называется его разрешением. Принцип работы электроннолучевого монитора стеклянная колба сигналы управления лучом электронная пушка покрытие из люминофора электронный луч же монитора может меняться за счет объединения соседних триад. Количество раз которое сменится изображение на экране электроннолучевого монитора за 1 секунду называется частотой кадровой развертки.
25001. Манипуляторы 37.71 KB
  Наиболее распространенным из них является так называемая Мышь Она служит для ввода данных или одиночных команд выбираемых из меню ли текстограмм графических оболочек выведенных на экран монитора. Мышь представляет собой небольшую коробочку с двумя или тремя клавишами и утопленным свободно вращающимся в любом направлении шариком на нижней поверхности. Для работы с мышью необходима плоская поверхность с этой целью используют резиновые коврики Mouse Pad. Так как с помощью мыши нельзя вводить в компьютер серии команд поэтому мышь и...
25002. Текстовый редактор. Назначение и основные возможности 59.21 KB
  Обычно текстовыми редакторами принято называть программы выполняющие простейшие операции по редактированию текста а процессорами программы обладающие расширенными по сравнению с редакторами средствами для компьютерной обработки текста. В процессе подготовки текстовых документов можно выделить следующие этапы: набор текста; редактирование; форматирование текста разметка страниц; печать просмотр перед печатью текста на экране печать на бумаге. Основные функции текстовых процессоров: создание документов; редактирование документов...
25003. ПОЧЕМУ РАБОТА ЗА КОМПЬЮТЕРОМ ЧАСТО ПРИВОДИТ К БОЛИ 82.5 KB
  Выплачиваемые компенсации достигают астрономических размеров а некоторым пострадавшим от работы за компьютерам приходится расплачиваться жестокими болями в течение всей жизни. Недавние исследования показали что примерно 20 нарушений здоровья связанных с работой за компьютером вызваны не вредностью компьютера как такового а незнанием основных правил работы с ним а также неправильной организацией рабочего места. В 1996 году Государственный комитет санитарноэпидемиологического надзора утвердил Гигиенические требования к видеодисплейным...
25004. Понятие информации. Информационные процессы 48.19 KB
  Мы говорим: я получил важную информацию у меня недостаточно информации для принятия решения кто владеет информацией правит миром не особенно задумываясь о том что же такое информация. В этом заключена одна из особенностей понятия информации: оно относится к числу базовых понятий таких как число в математике которые можно пояснять уточнять использовать но нельзя однозначно определить. Юристы например используют определение из закона Об информации информатизации и защите информации: информация сведения о лицах предметах...
25005. Принтер — основное устройство для вывода инфор 48.5 KB
  Во время печати на его поверхность подается высокое напряжение которое распределяет статический заряд по поверхности барабана. У цветных лазерных принтеров соответствующие и стоимость и скорость печати. Поскольку лазер формирует прообраз изображения целиком на барабане то к моменту печати он уже полностью должен быть в памяти принтера. Большой объем памяти требуется при печати большого потока документов.
25006. Сканеры. Принцип действия и классификация сканеров 137.87 KB
  В процессе сканирования оригинал освещается источником света. В основном все планшетные сканеры рассчитаны на получение копии с одного оригинала однако к некоторым моделям сканеров прилагаются дополнительные приспособления для последовательной подачи и сканирования нескольких оригиналов. К преимуществам планшетных сканеров следует отнести простоту использования возможность сканирования как плоских оригиналов в широком диапазоне размеров так и небольших трех мерных объектов. При необходимости сканирования оригиналов нестандартного большого...