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

Размещено на http://www.allbest.ru/

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

Цель работы: Создать матрицу размерности 15х15, содержащую 6 седловых точек. Найти нижнюю м верхнюю цену игры, значение седловой точки, а также координаты седловых точек.

1 Постановка задачи

Необходимо cформировать шаблон, где 6 седловых точек.

1. Сформировать матрицу размерности 15х15. Формирование матрицы задается случайным образом во всем диапазоне размерности матрицы (0 ..100).

2. Выбрать значение седловой точки случайным образом. Расположить n седловых точек в матрицу, в зависимости. Все элементы матрицы, кроме седловых, заполняются по схеме minmax, как минимальный элемент строки является максимальным элементом столбца.

3. Нахождение верхней и нижней цены (седловые точки и их координаты) игры с использованием метода максимина и минимакса.

2 Теоретическая часть

Рассмотрим игру с платёжной матрицей:

Таблица

Если каждый из игроков выбирает одну из своих стратегий и в дальнейшем в процессе игры не может её менять, то говорят, что игрок применяет чистую стратегию. Необходимо определить наилучшие чистые стратегии игроков и , которые в дальнейшем будут применяться постоянно. Под наилучшей чистой стратегией понимается стратегия, которая приносит игроку максимально возможный выигрыш (игроку минимально возможный проигрыш).

Вначале найдём наилучшую чистую стратегию игрока . Пусть он использует чистую стратегию . Какой при этом у него будет гарантированный выигрыш? Очевидно, это будет зависеть от того, какую стратегию использует игрок . Он может применять самую невыгодную для игрока стратегию. Следовательно, гарантированный выигрыш игрока будет равен

.

матрица сумма оптимальный

Но, так как он сам выбирает какую чистую стратегию использовать, то он будет применять ту чистую стратегию, которая даёт ему наибольший гарантированный выигрыш. Для этого ему нужно среди значений найти наибольший выигрыш . Таким образом, гарантированный выигрыш игрока вычисляется как максимин на платёжной матрице:

Пусть максимум по в выражении (1) достигается при , то есть .

Тогда стратегия является наилучшей чистой стратегией игрока , и она называется максимальной стратегией, которая даёт игроку наибольший гарантированный выигрыш.

Величина называется нижней ценой игры. При максиминной стратегии игрок гарантирует себе выигрыш не меньший при любом поведении противника, поэтому величина и называется «нижней ценой игры».

Теперь найдём наилучшую чистую стратегию игрока . Допустим он использует свою стратегию . Его проигрыш будет зависеть от действий игрока , который может применить стратегию, дающую ему наибольший выигрыш. Поэтому гарантированный проигрыш игрока будет равен

Естественно игрок будет выбирать ту стратегию, которая обеспечит ему минимальный проигрыш. Величина гарантированного минимального проигрыша определяется как

Пусть минимум по в выражении (2) достигается при . Тогда стратегия является наилучшей чистой стратегией игрока . Она называется минимальной стратегией, а величина игрока - верхней ценой игры.

3 Алгоритм выполнения программы

Программа разработана в среде PascalABC.net Для решения поставленной задачи использован следующий алгоритм:

1. Объявление переменных;

2. Формирование матрицы , где допускаемый диапазон для составляет от 0 до 100.

3. Поиск значения в массиве.

4. Генерируется значение седловой точки.

5. Генерируются координаты седловых точек и запись в них значений.

6. Генерируется остальная матрица.

6.1 Если столбец и строка седловые - ничего не происходит.

6.2 Если столбец и строка седловые - сгенерировать меньше/ больше значений.

7. Нахождение минимум в строках и максимум в столбцах.

8. Нахождение максимального элемента из минимального и минимального элемента из максимальных.

9. Вывод значений.

10. Вывод координат седловых точек.

Анализ результатов

В лабораторной работе разработана программа для формирования матрицы антагонистической игры с заданными свойствами. В матрице расположены k седловых точек, k=6. Поскольку, количество седловых точек четное, они могут располагаться в одной строке и в одном столбце по равному количеству седловых точек.

В результате на окне вывода распечатана матрица с размерностью 15х15 (Приложение А). Адреса седловых точек: а₃₃=82, а₃₁=82, а₁₅₃=82, а₁₅₁=82, а₂₃=82, а₈₁=82. Также, для нахождения нижней и верхней цены игры, были определены минимальные элементы каждой строки и максимальные элементы каждого столбца. В конце распечатаны . Программа работает корректно. Текст программы представлен в приложении Б.

Приложение А

Результаты программы

Рисунок А.1. Скрин результатов программы

Приложение Б

матрица сумма оптимальный

Текст программы

Размещено на Allbest.ru