Программная реализация метода приближенного решения матричных игр
Обзор программной реализации методов приближенного определения решений задач теории игр, представленных в матричной форме. Реализация метода фиктивного разыгрывания игры в системе программирования Delphi. Поиск оптимальных стратегий поведения игроков.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 31.07.2018 |
| Размер файла | 410,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Программная реализация метода приближенного решения матричных игр
Технические науки
Дмитриев Владислав Леонидович, кандидат наук, доцент, доцент
Тугузбаева Анжелика Рафаиловна, студент Башкирский государственный университет
При решении многих задач теории игр их обычно сводят к матричной форме. После этого полученную матрицу можно попытаться упростить, используя соотношение превосходства, и лишь затем приступить к решению задачи. Существует ряд точных способов получения решений задач матричных игр [2], среди которых и методы линейного программирования [3].
Однако для матриц большого размера методы линейного программирования малопригодны, т.к. приводят к значительным трудностям при вычислениях. Зачастую при решении задач теории игр точные решения не требуются, к тому же выигрыши игроков в каждой конкретной ситуации могут не всегда определяться точными значениями. Например, исходная платежная матрица игроков может быть получена на основе некоторых исходных данных (в том числе экспериментальных), уже содержащих в себе некоторые ошибки (связанные с погрешностями измерений). В итоге, числа матрицы уже сами по себе не будут являться точными значениями, и поэтому точность в определении значения цены игры и распределении стратегий игроков не будет оправдана. Кроме того, некоторая погрешность в оценке игроком своего выигрыша на практике не будет приводить к каким-либо серьезным последствиям: небольшое отклонение игрока от его истинной оптимальной стратегии не приведет к заметному изменению в его выигрыше.
В работе рассматривается программная реализация одного из методов приближенного определения решений задач теории игр, представленных в матричной форме. Программа может быть использована как в учебных целях при изучении дисциплин, связанных с теорией игр, так и при решении ряда практических задач.
В таких случаях лучше использовать приближенные методы решения. Одним из таких методов является метод фиктивного разыгрывания игры [1, 2], или метод Брауна-Робинсона, относящийся к итеративным методам.
Данный метод использует некоторую последовательность партий игры, в каждой из которых игроки выбирают такие стратегии, которые дают им максимальный суммарный выигрыш с учетом всех предыдущих партий. С ростом количества партий игры средний выигрыш на одну партию будет постепенно приближаться к цене игры, а относительные частоты применения стратегий игроками приближаться к вероятностям применения стратегий в оптимальных смешанных стратегиях игроков.
К преимуществ такого метода относится его простота, однако имеется и недостаток - малая скорость сходимости (причем она сильно зависит от значений элементов матрицы). Стоит также отметить, что сложность и объем вычислений относительно слабо растут с ростом размера матрицы (примерно пропорционально числу строк и столбцов матрицы).
Таким образом, рассматриваемый метод приближенного решения матричных игр позволяет находить цену игры и оптимальные стратегии поведения игроков с какой угодно степенью точности, зависящей лишь от количества выполненных итераций.
Метод Брауна-Робинсона удобно реализовать программно для определения решений игры с использованием ЭВМ. Ниже в работе представлена программа для получения приближенного решения матричных игр, реализованная в системе программирования Delphi. Программа поддерживает работу с матрицами размером до 100Ч100, окно программы изображено на рис. 1.
программный реализация задача игра
Рис. 1. Окно программы, реализующей метод приближенного решения матричных задач теории игр
В программе можно выбирать два варианта работы - указав или точность подсчета, или количество итераций до вывода полученных решений.
На рис. 2-4 показаны некоторые примеры работы с программой для матриц различных размеров.
Для рис. 2 точное решение имеет следующий вид: , , , для рис. 3: , , . Здесь X и Y - оптимальные стратегии первого и второго игроков соответственно, V - цена игры. Видно, что для рис. 2 требуемая точность достигается всего за 48 итераций, тогда как для рис. 3 - уже за 60030 итераций.
На рис. 4 рассмотрен пример для матрицы размером 7Ч8. Количество итераций для достижения указанной точности - более 10 млн.
Рис. 2. Пример 1: нахождение решений прямоугольной игры 3Ч3
Рис. 3. Пример 2: нахождение решений прямоугольной игры 3Ч3
Рис. 4. Пример 3: нахождение решений прямоугольной игры 7Ч8
Таким образом, описанная программа позволяет приближенно определять решения прямоугольных матричных игр и может быть использована при решении ряда практических задач в случаях, когда получение точных решений стандартными методами оказывается невозможным в силу значительной трудоемкости связанных с этим вычислений. Также программа может быть использована в учебных целях при изучении дисциплин, связанных с теорией игр.
Список литературы
1. Булатова З.А., Дмитриев В.Л. Практикум по теории игр и исследованию операций. Уфа: РИЦ БашГУ, 2011. - 124 с.
2. Дж. Мак-Кинси. Введение в теорию игр. М.: Государственное издательство физико-математической литературы, 1960. - 420 с.
3. Хачатрян С.Р., Пинегина М.В., Буянов В.П. Методы и модели решения экономических задач. М.: Изд-во «Экзамен», 2005. - 384 с.
Размещено на Allbest.ru
...Подобные документы
Особенности метода неопределенных множителей Лагранжа, градиентного метода и метода перебора и динамического программирования. Конструирование алгоритма решения задачи. Структурная схема алгоритма сценария диалога и описание его программной реализации.
курсовая работа [1010,4 K], добавлен 10.08.2014Реализация программы для решения матричных игр. Задание матрицы игры вручную и случайным образом, нахождение оптимальных стратегий игроков итерационным и методом чистых стратегий. Проектирование и листинг программного кода, сохранение матрицы игры.
контрольная работа [716,7 K], добавлен 11.06.2011Обзор разнообразных методов теории линейных систем: методов корреляционного и регрессионного анализа, косинор-анализа. Особенности применения факторного анализа. Программная реализация метода главных компонент. Разработка нелинейных регрессионных моделей.
дипломная работа [390,2 K], добавлен 03.09.2016Понятие графика функции и его представление на ЭВМ. Алгоритм реализации, блок-схема и функциональные тесты графического метода решения частного случая задачи нелинейного программирования, его математическая модель. Диалог программы с пользователем.
курсовая работа [1,6 M], добавлен 15.05.2012Обыкновенное дифференциальное уравнение первого порядка. Задача Коши, суть метода Рунге-Кутта. Выбор среды разработки. Программная реализация метода Рунге-Кутта 4-го порядка. Определение порядка точности метода. Применение языка программирования C++.
курсовая работа [163,4 K], добавлен 16.05.2016Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
курсовая работа [2,2 M], добавлен 29.05.2015Сущность построения, особенности применения и теоретическое обоснование алгоритмов приближенного решения математических задач. Основы численного метода, нахождение интерполяционного полинома методом Лагранжа. Руководство программиста и пользователя.
курсовая работа [527,6 K], добавлен 16.08.2012Разработка алгоритма аппроксимации данных методом наименьших квадратов. Средства реализации, среда программирования Delphi. Физическая модель. Алгоритм решения. Графическое представление результатов. Коэффициенты полинома (обратный ход метода Гаусса).
курсовая работа [473,6 K], добавлен 09.02.2015Реализация алгоритма метода сопряженных градиентов с матрично-векторным произведением по строкам в модели обмена сообщениями на языке программирования С++ с применением MPI для нахождения приближенного решения системы линейных алгебраических уравнений.
курсовая работа [107,7 K], добавлен 01.12.2010Понятие математической модели. Безусловные и условные типы задач оптимизации. Принципы, термины и преимущества объектно-ориентированного программирования. Характеристика среды разработки Delphi 7.0. Программная реализация метода кодирования Хаффмена.
курсовая работа [1,3 M], добавлен 05.10.2014Описание метода сжатия информации на основе двоичных кодирующих деревьев Хаффмана. Среда разработки Delphi версии 7.0. Понятия объектно-ориентированного программирования. Программа, разработанная в Delphi. Реализация на Delphi метода кодирования Хаффмана.
курсовая работа [2,1 M], добавлен 26.03.2013Рассмотрение двух методов нахождения приближенного корня дифференциального уравнения, применение их на практике. Графическая интерпретация метода Эйлера. Решение задачи усовершенствованным методом Эйлера. Программная реализация, блок-схемы и алгоритм.
курсовая работа [246,8 K], добавлен 17.06.2013Описание ДСМ-метода автоматического порождения гипотез. Исследование результатов влияния компонентов ДСМ-метода на качество определения тональности текстов. Алгоритм поиска пересечений. N-кратный скользящий контроль. Программная реализация ДСМ-метода.
курсовая работа [727,0 K], добавлен 12.01.2014Реализация алгоритма Гомори на языке программирования Object Pascal при использовании среды разработки Borland Delphi 7. Рассмотрение основных способов компьютерного осуществления решения задач целочисленного программирования симплексным методом.
курсовая работа [1,8 M], добавлен 28.03.2013Выбор методов обработки и сегментации изображений. Математические основы примененных фильтров. Гистограмма яркости изображения. Программная реализация комплексного метода обработки изображений. Тестирование разработанного программного обеспечения.
курсовая работа [1,3 M], добавлен 18.01.2017Методы решения задач линейного программирования. Вектор коэффициентов целевой функции. Простой однооконный интерфейс с набором всех необходимых инструментов для работы с программой. Структура программного модуля. Автоматический режим работы программы.
контрольная работа [1,6 M], добавлен 11.06.2011Особенности и тонкости программирования в среде Delphi. Специфика перехода от алгоритмического решения к непосредственной программной реализации на языке Object Pascal с использованием всех необходимых средств данного языка. Анализ полученных результатов.
реферат [246,2 K], добавлен 17.11.2012Использование математических и программных средств моделирования при решении задачи минимизации транспортных издержек. Использование метода потенциалов, разработка алгоритма программы на языке программирования Turbo Pascal 7.0. Методы реализации.
курсовая работа [156,6 K], добавлен 16.02.2016Реализация программы, позволяющей принять решение о выборе поставщика товаров, по аналогии с продукционной моделью представления знаний (сопоставления образцов и консиквентов). Математическая постановка задачи, программный алгоритм и этапы его разработки.
курсовая работа [812,8 K], добавлен 13.11.2012Определение с помощью метода Баранкина и Дорфмана оптимального набора цен, по которым следует реализовывать все виды продукции при условии получения наибольшей стоимости реализованной продукции. Программная реализация решения задачи в пакете GINO.
курсовая работа [126,7 K], добавлен 02.02.2014
