Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
shpory_po_MO.doc
Скачиваний:
46
Добавлен:
17.04.2019
Размер:
528 Кб
Скачать
☆

43. Правила упрощения матричной игры

Определение оптимальных стратегий и цены игры и составляет процесс нахождения решения игры. Задача решения игры, если ее матрица не содержит седловой точки, тем сложнее, чем больше значения m и n. Сократить размерность матрицы можно, исключая дублирующие и заведомо невыгодные доминирующие стратегии.

Дублирующими называются стратегии, которым соответствуют одинаковые значения элементов в платежной матрице, т. е. матрица содержит одинаковые строки (столбцы). Если все элементы i-й строки матрицы меньше соответствующих элементов k-й строки, то i-я стратегия для игрока А называется доминирующей. Если же элементы r-го столбца матрицы не меньше соответствующих элементов j-го столбца, то для игрока B стратегия Br — доминирующая.

Таким образом, при решении игры m×n следует:

a) проверить, не содержит ли матрица седловой точки;

б) если седловой точки нет, то нужно сравнить между собой элементы строк и столбцов для исключения дублирующих и доминирующих стратегий.

44. Решение матричной игры 2x2

Матрица А игры имеет вид

А= .

Если седловой точки нет, то решением игры являются смешанные стратегии U=(u1, u2), Z=(z1,z2).

Согласно основной теореме теории игр, применение оптимальной стратегии U=(u1, u2) обеспечивает для игрока А получение выигрыша v при любых стратегиях игрока В. Оптимальная стратегия для игрока В также смешанная. Поэтому, если игрок А применяет свою оптимальную стратегию, то при этом игрок В может использовать одну из чистых стратегий, величина выигрыша игрока А останется неизменной. Запишем систему уравнений

Так как u1+u2=1, то решение таково:

u1= , u2= . (4.3)

Подставляя значения u1 и u2 в одно из уравнений (2.1), получаем

v= . (4.4)

Составляя аналогичную систему уравнений, можно найти оптимальную стратегию для игрока В:

z1= , z2= (4.5)

45. Геометрическое решение матричной игры Mx2, 2xN

Используя геометрическую интерпретацию, можно найти решение игр, заданных матрицей 2n. Каждой из n стратегий игрока В соответствует прямая. Построив эти прямые, находят нижнюю границу выигрыша. Точка К, лежащая на нижней границе, для которой величина выигрыша наибольшая, определяет цену игры и ее решение. При этом определяется активные стратегии игрока В (соответствующие им прямые пересекаются в точке К): из геометрических соображений можно найти значения zj, соответствующие активным стратегиям игрока В.

Аналогично может быть решена игра с матрицей m2, только в этом случае строят верхнюю границу выигрыша и на ней определяют минимум.

46. Приведение матричной игры к задаче линейного программирования

чтобы найти решение данной игры, определяемой матрицей А, нужно составить пару двойственных задач и найти их решение.

процесс нахождения решения игры с использованием методов линейного программирования включает следующие этапы:

1. Составляют пару двойственных задач линейного программирования, эквивалентных матричной игре.

2. Определяют оптимальные планы пары двойственных задач.

3. Используя соотношение между планами пары двойственных задач и оптимальными стратегиями и ценой игры, находят решение игры.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]