Главная
Новости
Статьи
Ремонт
Каркасный дом
Несущие конструкции
Металлические конструкции
Прочность дорог
Дорожные материалы
Стальные конструкции
Грунтовые основания
Опорные сооружения




28.01.2022


27.01.2022


27.01.2022


27.01.2022


27.01.2022


26.01.2022


26.01.2022





Яндекс.Метрика

Матричные игры

01.01.2022

В математике под матричными играми понимается игра двух лиц с нулевой суммой, имеющих конечное число стратегий. Выигрыш определяется матрицей игры (матрицей платежей), она же является Нормальной формой игры.

Матричная игра и линейное программирование

Пусть матричная игра задана множеством стратегий первого игрока M {displaystyle M} , множеством стратегий второго игрока N {displaystyle N} и матрицей платежей A [ M , N ] {displaystyle A[M,N]} .

Рассмотрим две задачи линейного программирования

Задача 1

Найти максимум 1 T [ N ] y [ N ] {displaystyle 1^{T}[N]y[N]}

При ограничениях

A [ M , N ] y [ N ] ≤ 1 [ M ] {displaystyle A[M,N]y[N]leq 1[M]}

y [ N ] ≥ 0 [ N ] {displaystyle y[N]geq 0[N]}

Задача 2 (двойственная)

Найти минимум 1 T [ M ] x [ M ] {displaystyle 1^{T}[M]x[M]}

При ограничениях

A T [ N , M ] x [ M ] ≥ 1 [ N ] {displaystyle A^{T}[N,M]x[M]geq 1[N]}

x [ M ] ≥ 0 [ M ] {displaystyle x[M]geq 0[M]}

Известно, что следующие утверждения эквивалентны

1. Матричная игра имеет положительную цену игры

2. Задачи 1 и 2 разрешимы, при этом, если v {displaystyle v} — цена игры,

x [ M ] {displaystyle x[M]} и y [ N ] {displaystyle y[N]} — оптимальные решения,

то 1 / v = 1 T [ N ] y [ N ] = 1 T [ M ] x [ M ] {displaystyle 1/v=1^{T}[N]y[N]=1^{T}[M]x[M]}

и 1 T [ N ] y [ N ] {displaystyle 1^{T}[N]y[N]} , 1 T [ M ] x [ M ] {displaystyle 1^{T}[M]x[M]} будут оптимальными смешанными стратегиями игроков.


Замечание: При v <= 0 {displaystyle v<=0} можно прибавить ко всем элементам матрицы (достаточно большую) константу, что не меняет стратегии игроков. Можно, например, найти минимальный элемент (отрицательный) и использовать его абсолютное значение в качестве добавки.


Имя:*
E-Mail:
Комментарий: