Нахождение оптимального решения матричных игр двух лиц с нулевой суммой
Рассмотрение основных способов нахождения оптимального решения матричных игр двух лиц с нулевой суммой. Общая характеристика этапов создания матрицы размерности 15х15, содержащей 6 седловых точек. Знакомство с особенностями игры с платежной матрицей.
| Рубрика | Математика |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 18.06.2020 |
| Размер файла | 683,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на 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 (Приложение А). Адреса седловых точек: а33=82, а31=82, а153=82, а151=82, а23=82, а81=82. Также, для нахождения нижней и верхней цены игры, были определены минимальные элементы каждой строки и максимальные элементы каждого столбца. В конце распечатаны . Программа работает корректно. Текст программы представлен в приложении Б.
Приложение А
Результаты программы
Рисунок А.1. Скрин результатов программы
Приложение Б
матрица сумма оптимальный
Текст программы
Размещено на Allbest.ru
...Подобные документы
Теория игр - математическая теория конфликтных ситуаций. Разработка математической модели игры двух лиц с нулевой суммой, ее реализация в виде программных кодов. Метод решения задачи. Входные и выходные данные. Программа, руководство пользователя.
курсовая работа [318,4 K], добавлен 17.08.2013Принятие решений как особый вид человеческой деятельности. Рациональное представление матрицы игры. Примеры матричных игр в чистой и смешанной стратегиях. Исследование операций: взаимосвязь задач линейного программирования с теоретико-игровой моделью.
курсовая работа [326,4 K], добавлен 05.05.2010Общая характеристика примеров нахождения точки пересечения двух прямых. Знакомство с условиями параллельности и перпендикулярности прямых, рассмотрение особенностей решения уравнений. Анализ способов нахождения углового коэффициента искомой прямой.
презентация [97,6 K], добавлен 21.09.2013Теория игр – раздел математики, предметом которого является изучение математических моделей принятия оптимальных решений в условиях конфликта. Итеративный метод Брауна-Робинсона. Монотонный итеративный алгоритм решения матричных игр.
дипломная работа [81,0 K], добавлен 08.08.2007Составление платежной матрицы, поиск нижней и верхней чисты цены игры, максиминной и минимаксной стратегии игроков. Упрощение платежной матрицы. Решение матричной игры с помощью сведения к задаче линейного программирования и надстройки "Поиск решения".
контрольная работа [1010,3 K], добавлен 10.11.2014Базовые действия над матрицами. Решение матричных уравнений с помощью обратной матрицы и с помощью элементарных преобразований. Понятия обратной и транспонированной матриц. Решение матричных уравнений различных видов: АХ=В, ХА=В, АХВ=С, АХ+ХВ=С, АХ=ХА.
курсовая работа [172,0 K], добавлен 09.09.2013Использование системы MathCAD как средства описания алгоритмов решения основных математических задач. Рассмотрение законов Кеплера и понятия о всемирном тяготении. Аналитические и численные решения задачи трех тел (материальных точек), вывод уравнений.
курсовая работа [287,2 K], добавлен 04.06.2013Знакомство с особенностями возникновения тригонометрии, рассмотрение этапов развития. Анализ способов решения треугольников, основанных на зависимостях между сторонами и углами треугольника. Характеристика аналитической теории тригонометрических функций.
презентация [654,4 K], добавлен 24.06.2014Определение матричных игр в чистых стратегиях. Смешанные стратегии и их свойства. Решения игр матричным методом. Метод последовательного приближения цены игры. Отыскание седлового элемента. Антагонистические игры как первый класс математических моделей.
контрольная работа [855,7 K], добавлен 01.06.2014Понятие равных матриц, их суммы и произведения. Нахождение элемента матрицы, свойства ее произведения. Расположение вне главной диагонали элементов квадратной матрицы. Понятие обратной матрицы, матричные уравнения. Теорема о базисном миноре, ранг матрицы.
реферат [105,3 K], добавлен 21.08.2009Знакомство с уравнениями линейной регрессии, рассмотрение распространенных способов решения. Общая характеристика метода наименьших квадратов. Особенности оценки статистической значимости парной линейной регрессии. Анализ транспонированной матрицы.
контрольная работа [380,9 K], добавлен 05.04.2015Анализ особенностей разработки вычислительной программы. Общая характеристика метода простых итераций. Знакомство с основными способами решения нелинейного алгебраического уравнения. Рассмотрение этапов решения уравнения методом половинного деления.
лабораторная работа [463,7 K], добавлен 28.06.2013Составление уравнения Эйлера, нахождение его общего решения. Нахождение с использованием уравнения Эйлера-Лагранжа оптимального управления, минимизирующего функционал для системы. Использование метода динамического программирования для решения уравнений.
контрольная работа [170,3 K], добавлен 01.04.2010Рассмотрение основных методов решения школьных задач на движение двух тел в разных и одинаковых направлениях: анализ и синтез, сведение к ранее решенным, математическое моделирование (знаковые, графические модели), индукция, исчерпывающая проба.
презентация [11,8 K], добавлен 08.05.2010Изучение общих сведений о матричных и антагонистических играх. Понятие позиционной игры, дерева, информационного множества. Рассмотрение принципа максимина и принципа равновесия. Оптимальность по Парето. Позиционная неантагонистическая игра, ее свойства.
курсовая работа [1,4 M], добавлен 17.10.2014Суть задачи коммивояжера, ее применение. Общая характеристика методов ее решения: метод полного перебора, "жадные" методы, генетические алгоритмы и их обобщения. Особенности метода ветвей и границ и определение наиболее оптимального решения задачи.
курсовая работа [393,2 K], добавлен 18.06.2011Приведение уравнений к специальному виду. Устойчивость относительно переменных с одним нулевым и парой чисто мнимых корней в частном случае. Критический случай двух нулевых корней, одного нулевого и пары чисто мнимых корней, двух пар чисто мнимых корней.
дипломная работа [2,5 M], добавлен 13.07.2015Виды точек регулярной поверхности. Удельная кривизна выпуклой поверхности. Сфера как единственная овальная поверхность постоянной средней кривизны. Основные понятия и свойства седловых поверхностей. Неограниченность седловых трубок и проблема Плато.
лабораторная работа [1,6 M], добавлен 29.10.2014Классификация способов нахождения обратной матрицы, полученной в системе MathCAD с помощью миноров и алгебраических дополнений: разбиения ее на клетки и на произведение 2-х треугольных матриц; с помощью модели Гаусса. Вычисление погрешности методов.
лабораторная работа [380,9 K], добавлен 31.10.2012Определение собственного вектора матрицы как результата применения линейного преобразования, задаваемого матрицей (умножения вектора на собственное число). Перечень основных действий и описание структурной схемы алгоритма метода Леверрье-Фаддеева.
презентация [55,2 K], добавлен 06.12.2011
