Нахождения оптимального решения игры двух лиц с нулевой суммой. Читать текст оnline - КУРСОВАЯ РАБОТАпо дисциплине . Описательная часть, содержащая: Алгоритм решения задачи; Описание программы; Контрольный пример; Руководство по эксплуатации и сопровождению; Заключение, которое отражает достигнутые результаты. Список используемой литературы. Пояснительная записка также включает в себя раздел . Расчетная часть. 1. Постановка задачи. Математическая модель. Описание метода решения задачи. Итеративный метод Брауна - Робинсона. Монотонный итеративный алгоритм решения матричных игр. Алгоритм программы и ее реализация. Алгоритма Брауна-Робинсона на Visual Basic (VB NET). В итоге родилась программа «BrawnRob, интерфейс которой приведен на рис. Итерационный метод Брауна-Робинсона. Этот метод ориентирован на произвольную игру G(m. Наука: Контрольные работы Пример использования разработанной программы, решение задачи К таким методам в теории игр относится и метод Брауна - Робинсон. Остальное читайте тут . Поэтому возникает потребность в разработке численных методов решения матричных игр. 1.3 Описание метода решения задачи. 2.2 Описание программы. Для того, чтобы описать первый метод решения матричных игр, нам понадобится сле- дующая. Метод Брауна-Робинсон (фиктивного разыгрывания). Информационное обеспечение. Описательная часть. Алгоритм решения задачи. Описание программы. Контрольный пример. Руководство пользователя. Заключение. Список литературы. Введение. Проблема выполнения различных вычислений была актуальна во все времена. По мере развития общественно- экономических отношений усложнялись постановленные задачи, которые для своего решения требовали разработки новых методов вычислений. На смену простейшим арифметическим и геометрическим вычислениям пришли алгебраические и тригонометрические вычисления. Организация современного производства требует не только наличия современных станков и оборудования, но и разработки новых технологических процессов и современных методов управлением производством. Для решения каждой из поставленных задач разрабатываются математические модели, анализируя которые удается найти наилучшее решение поставленной задачи. Создание математической модели - сложная кропотливая работа, которая в современных условиях под силу коллективам разработчиков. Для создания математической модели одного и того же объекта различные коллективы могут использовать различный математический аппарат. В коллектив разработчиков математических моделей привлекаются высококвалифицированные специалисты, которые, с одной стороны, хорошо знают физические процессы, протекающие при работе объекта, и, с другой стороны, глубоко и всесторонне владеют соответствующим математическим аппаратом. После создания математической модели специалистами- аналитиками за дело принимаются специалисты- программисты, которые реализуют созданную модель в виде программных кодов. Далее с математической моделью работают специалисты- практики, целенаправленно воздействуя на модель, они изучают её поведение и подбирают оптимальный режим работы для реального объекта. Наиболее полно разработан математический аппарат игр с нулевой суммой, когда выигрыш одного игрока равен выигрышу другого игрока, т. При построении игровых моделей предполагается, что каждый из игроков будет выбирать только лучшую (для себя) стратегию. Результатом исследования игровой модели является определение наиболее осторожной стратегии поведения игрока либо обеспечение гарантированного выигрыша. Риски при получении большего выигрыша не учитываются и не оцениваются. Таким образом, результат исследования игровых моделей указывает на оптимальную стратегию поведения (гарантированный выигрыш), а какой стратегией воспользуется игрок в реальной жизни - дело самого игрока. В данном курсовом проекте для реализации решения задачи используется метод Брауна- Робинсона решения игровых задач с нулевой суммой. Суть данного метода заключается в многократном фиктивном разыгрывании игры с заданной матрицей выигрыша. Целью данного курсового проекта является: научиться от словесного описания задачи перейти к абстрактной математической модели, реализовать математическую модель в виде программных кодов, провести исследование математической модели и получить вектор входных воздействий, доставляющих оптимальное решение. Речь идет о простых математических моделях, позволяющих решить элементарные задачи. Расчетная часть. 1. Постановка задачи. Теория игр - математическая теория конфликтных ситуаций. Экономические соревнования, спортивные встречи, боевые операции - примеры конфликтных ситуаций. Простейшие модели конфликтных ситуаций - это салонные и спортивные игры. В игре могут сталкиваться интересы двух противников (игра парная или игра двух лиц), интересы n (n > 2) противников (игра множественная или игра n лиц). Существуют игры с бесконечным множеством игроков. Игра называется парной, если в ней сталкиваются интересы двух противников. Игра называется с нулевой суммой, если один игрок выигрывает столько, сколько второй проигрывает в той же партии. Задача первого игрока - максимизировать свой выигрыш. Задача второго игрока - максимизировать свой выигрыш - сводится к минимизации проигрыша второго, что эквивалентно задаче минимизации выигрыша первого игрока. Необходимо создать программу для автоматизированного решения данной задачи с использованием ЭВМ. Математическая модель. Матричной называют парную игру с нулевой суммой при условии, что каждый игрок имеет конечное число чистых стратегий. Матричные игры относятся к разряду так называемых антагонистических игр, т. В зависимости от числа возможных стратегий игры делятся на конечные и бесконечные. Каждая фиксированная стратегия, которую может выбрать игрок, называется его чистой стратегией. Процесс игры состоит в выборе каждым игроком i одной своей стратегии. В результате сложившейся ситуации s игрок i получает выигрыш. Процесс игры состоит в выборе каждым игроком i одной своей стратегии. В результате сложившейся ситуации s игрок i получает выигрыш. Игры, в которых целью каждого участника является получение по возможности большего индивидуального выигрыша, называются бескоалиционными в отличие от коалиционных, в которых действия игроков направлены на максимизацию выигрышей коллективов (коалиции) без дальнейшего разделения выигрыша между участниками. Ситуация s в игре называется приемлемой для игрока i, если этот игрок, изменяя в ситуации s свою стратегию si на какую- либо другую si', не может увеличить своего выигрыша. Ситуация s, приемлемая для всех игроков, называется ситуацией равновесия. Процесс нахождения ситуации равновесия в бескоалиционной игре есть процесс решения игры. Рассмотрим игру, в которой участвуют два игрока, причем каждый их них имеет конечное число стратегий. Обозначим для удобства одного из игроков через А, а другого через В. Предположим, что игрок А имеет m стратегий: А1, А2, . Будем считать, что выбор игроками стратегий Аi и Bj. Поэтому при анализе такой игры можно рассматривать выигрыши только одного из игроков. Пусть это будет, например, выигрыши игрока А. Если нам известны значения aij выигрыша при каждой паре стратегий , i = 1,2. Общий вид платёжной матрицы матричной игры. Полученная матрица имеет размер m n и называется матрицей игры или платежной матрицей. Описание метода решения задачи. Решение данной задачи будет искать, используя метод Брауна- Робинсона (метод фиктивного разыгрывания). Часто в практических задачах нет необходимости находить точное решение матричной игры. Достаточно найти приближённое решение, которое даёт средний выигрыш, близкий к цене игры и приближённые оптимальные стратегии игроков. Ориентировочное значение цены игры может дать уже простой анализ матрицы выигрышей и определение нижней и верхней цен игры. Если они близки, то поисками точного решения заниматься не обязательно, так как достаточно выбрать чистые минимаксные стратегии. Если же они не близки, можно получить приемлемое для практики решение с помощью численных методов решения игр, из которых рассмотрим метод итераций. Пусть разыгрывается матричная игра ГА с матрицей А=. Идея метода - многократное фиктивное разыгрывание игры с заданной матрицей. Одно разыгрывание игры будем называть партией, число которых неограниченно. В 1- ой партии оба игрока выбирают совершенно произвольные чистые стратегии. Пусть игрок 1 выбрал i- ю стратегию, а игрок 2 - j- ю стратегию. Во второй партии игрок 1 отвечает на ход игрока 2 той своей стратегией, которая даёт ему максимальный выигрыш. В свою очередь, игрок 2, отвечает на этот ход игрока 1 своей стратегией, которая обращает его проигрыш в минимум. Далее третья партия. С ростом числа шагов процесса смешанные стратегии, которые приписываются игрокам, приближаются к их оптимальным стратегиям. Этот процесс приближённого нахождения оптимальных стратегий игроков называется итеративным, а его шаги - итерациями. Итак, предположим, что за первые k разыгрываний игрок 1 использовал i- ю чистую стратегию ik раз (i=1. Тогда их смешанными стратегиями будут векторы . Игрок 1 следит за действиями игрока 2 и с каждым своим ходом желает получить как можно больший выигрыш. Поэтому в ответ на применение игроком 2 своей смешанной стратегии yk, он будет использовать чистую стратегию ik+1, которая обеспечит ему лучший результат при разыгрывании (k+1) - ой партии. Игрок 2 поступает аналогично. В худшем случае каждый из них может получить: Где - наибольшее значение проигрыша игрока 2 и - наименьшее значение выигрыша игрока 1. Рассмотрим отношения, которые определяют средние значения проигрыша игрока 2 и выигрыша игрока 1: Пусть ? Её значение будет больше выигрыша игрока 1, но меньше проигрыша игрока 2, т. Для всякой матрицы А и . Осталось показать равенство пределов n. Это следует из неравенства (2). Итак, . 1. 4 Информационное обеспечение. Входными данными для задачи является матрица игры, содержащая значения выигрыша при выбранных стратегиях для игроков 1 и 2. Выходной информацией является значение цены игры и вероятностные показатели эффективности стратегий игры для игроков 1 и 2. Описательная часть. Алгоритм решения задачи. Рис. Блок- схема алгоритма. Описание программы. Программа реализована на языке программирования C++ в среде программирования Borland C++ Builder 6. Программа состоит из одного модуля Unit. Таблица 2. Процедуры и функции. Название. Входные параметры. Выходные параметры. Описаниеvoid Up. Date. Matrix () нетнет. Вывод заголовков матрицыint Min (float *Buf, int n) Buf - массив значений n - размер массива. Минимальное число из массива. Поиск наименьшего числа в заданном массивеint Max (float *Buf, int n) Максимальное число из массива. Поиск наибольшего числа в заданном массиве. Form. Activateнетнет. Инициализация программы. CSpin. Edit. 1Changeнетнет. Изменение количества стратегий игрока 2. CSpin. Edit. 2Changeнетнет. Изменение количества стратегий игрока 2. Find. Bit. Btn. Clickнетнет.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. Archives
December 2016
Categories |