Как решать теорию игр в excel

Решение игровых задач с нулевой суммой с помощью Microsoft Excel

Захарова, Т. Н. Решение игровых задач с нулевой суммой с помощью Microsoft Excel / Т. Н. Захарова. — Текст : непосредственный // Актуальные задачи педагогики : материалы I Междунар. науч. конф. (г. Чита, декабрь 2011 г.). — Чита : Издательство Молодой ученый, 2011. — С. 176-181. — URL: https://moluch.ru/conf/ped/archive/20/1343/ (дата обращения: 05.10.2022).

Рассмотрим общий случай игровой задачи m x n с нулевой суммой, когда модель задачи не имеет седловой точки. Такую модель можно представить в виде матрицы (табл.1):

Стратегии

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

Поскольку при оптимальной стратегии средний выигрыш не меньше v при любой стратегии противника, то справедлива система n неравенств:

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

Для этого необходимо максимизировать целевую функцию F = v при ограничениях

Введем новые неизвестные:

Разделим левую и правую части неравенств (1) и (2) на v, получим:

В силу того что

задача принимает вид

F = x 1 + x 2 +…+ x m → min ( 4 )

Для второго игрока (игрока В) оптимальная стратегия определяется из условия:

q 1 + q 2 +…+ q n = 1

Эта задача записывается как симметричная двойственная задача линейного программирования к задаче игрока A (4), (5):

L = y 1 + y 2 +… + y n → max (6)

Задачи игроков A и В решают симплекс-методом.

Использование возможностей Microsoft Excel позволяет существенно облегчить и ускорить решение этой задачи.

Сначала нужно создать исходную таблицу:

Затем, на основе этой таблицы записать формулы для нахождения решения:

Для нахождения решения используется надстройка Поиск решения. Нужно выделить ячейку, в которой вычисляется значение функции F и вызвать надстройку Поиск решения. Заполнить окно поиска решения:

В поле Ограничения нужно задать формулы для всех ограничений. Затем нажать кнопку Параметры и отметить поля Линейная модель и Неотрицательные значения. Нажать кнопку ОК, затем Выполнить.

Чтобы найти значения вероятностей и цену игры нужно записать формулы:

Решение задачи для игрока В выполняется по аналогичной схеме согласно формулам (6), (7).

Рассмотрим пример решения задачи. Найдем решение игры, заданной матрицей .

Проверим наличие седловой точки.

В режиме отображения формул эта запись имеет вид:

Поскольку нижняя цена игры (минимальный выигрыш игрока А) и верхняя цена игры (максимальный проигрыш игрока В) не равны, то модель данной задачи не имеет седловой точки. Поэтому решение следует искать в смешанных стратегиях. Составим задачи линейного программирования для нахождения решений игроков А (согласно формулам (4), (5)) и В(согласно формулам (6), (7)):

для игрока А и для игрока В.

Для решения этих систем используем надстройку «Поиск решения». Сначала оформим задачу для поиска решения игрока А:

В режиме отображения формул:

Затем нужно активировать ячейку В7 и запустить надстройку Поиск решения. Далее заполнить окно Поиска решения:

Затем нажать кнопку Параметры и отметить поля Линейная модель и Неотрицательные значения. Нажать кнопку ОК, затем Выполнить.

Вероятности применения смешанных стратегий и цену игры найдем по формулам: p i = x i / F , v =1/ F .

В режиме отображения формул:

Аналогично найдем решение для игрока В:

В режиме отображения формул:

1. Акулич И.Л. Математическое программирование в примерах и задачах. М. «Высшая школа», 1993г.

2. Агальцов В.П., Волдайская И.В. Математические методы в программировании М. ИД «Форум» — ИНФРА-М, 2006г.

3. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем М. «Финансы и статистика», 2003г.

4. Партыка Т.Л., Попов И.И. Математические методы М. ИД «Форум» — ИНФРА-М, 2007г.

Похожие статьи

Создание и использование программы для статистического.

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

Теория игр: основные понятия, типы игр, примеры

Для второго игрока самой оптимальной смешанной стратегией является стратегия . Запишем цену игры

Алгоритм. Иначе цена игры находится в промежутке и решение игры находится в смешанных стратегиях.

Поиск решения как средство решения задач оптимизации.

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

Нажать кнопку ОК и перейти в диалоговое окно Поиск решения.

Математическое моделирование оптимальных стратегий.

‒ аспект оптимальных решений — теория математических моделей принятия оптимальных решений вусловиях конфликтов.

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

Интеграл Стильтьеса в теории игр | Статья в журнале.

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

Целочисленное решение задач линейного программирования.

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

Решение многокритериальных задач линейного.

Рис. 1. Оптимальное решение задачи.

Основные термины (генерируются автоматически): критерий, задача, учет уступок, полученное решение, поиск решения, матрица коэффициентов, важность критерия, допустимая уступка, линейное программирование.

Применение метода линейного программирования для решения.

Метод линейного программирования при решении текстовых задач графически имеет следующий алгоритм

Литература: 1. Шикин Е. В., Чхартишвили А. Г. Математические методы и модели.

Линейное программирование | Статья в журнале «Молодой. »

Модель линейного программирования имела бы множество переменных решений

Решение задач оптимального раскроя средствами MS Excel. Симплекс-метод, основанный на идеях Л. В. Канторовича, был описан и детально разработан рядом ученых из США в середине 20 века.

Похожие статьи

Создание и использование программы для статистического.

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

Теория игр: основные понятия, типы игр, примеры

Для второго игрока самой оптимальной смешанной стратегией является стратегия . Запишем цену игры

Алгоритм. Иначе цена игры находится в промежутке и решение игры находится в смешанных стратегиях.

Поиск решения как средство решения задач оптимизации.

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

Нажать кнопку ОК и перейти в диалоговое окно Поиск решения.

Математическое моделирование оптимальных стратегий.

‒ аспект оптимальных решений — теория математических моделей принятия оптимальных решений вусловиях конфликтов.

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

Интеграл Стильтьеса в теории игр | Статья в журнале.

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

Целочисленное решение задач линейного программирования.

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

Решение многокритериальных задач линейного.

Рис. 1. Оптимальное решение задачи.

Основные термины (генерируются автоматически): критерий, задача, учет уступок, полученное решение, поиск решения, матрица коэффициентов, важность критерия, допустимая уступка, линейное программирование.

Применение метода линейного программирования для решения.

Метод линейного программирования при решении текстовых задач графически имеет следующий алгоритм

Литература: 1. Шикин Е. В., Чхартишвили А. Г. Математические методы и модели.

Линейное программирование | Статья в журнале «Молодой. »

Модель линейного программирования имела бы множество переменных решений

Решение задач оптимального раскроя средствами MS Excel. Симплекс-метод, основанный на идеях Л. В. Канторовича, был описан и детально разработан рядом ученых из США в середине 20 века.

Решение антагонистической игры в программе MS Excel

Покажем на рассмотренном ниже примере, как можно решить антагонистическую игру в смешанных стратегиях средствами MS Excel 1 . Подробно пройдем все этапы решения.

Проверьте, установлена ли надстройка «Поиск решения» в вашей программе MS Excel. Для этого в меню «Данные > Анализ» найдите надстройку «Поиск решения». Если она не установлена, то ее несложно установить (рис. 2.13).

Рис. 2.13

1 Рассматривается версия MS Excel 2007.

Пусть матрица игры размерности 3×3 имеет следующий вид:

Как отмечалось выше, такая игра сводится к задаче линейного программирования

Сначала вводим в таблицу матрицу игры и выделим ячейки для значений векторов р и q, а также для цены игры V. Заполним эти ячейки (А7 — А9; D4 — F4, В1) произвольными числами (начальные значения) вероятностей и зарезервируем под переменную v ячейку В2. Кроме того, поместим в ячейки А10 и G4 формулы сумм: А10: =СУММ (А7: А9), G4: =СУММ (D4: F4). В ячейку Е1 поместим целевую функцию Е1: =В2 (рис. 2.14).

Далее введем в ячейку D11 формулу =СУММПРОИЗВ ($А$7:$А$9; D7: D9) — $В$ 1 и скопируем ее в соседние ячейки Е11 и F11. Эти ячейки мы готовим для последующего ввода неравенств (1) — (3) в задачу оптимизации (рис. 2.15).

Мы все подготовили для решения задачи. Запускаем надстройку «Поиск решения» в меню «Данные» (рис. 2.16).

Установим в качестве целевой ячейку Е1 и выбираем опцию «Равной максимальному значению». В окне «Изменяя ячейки» выбираем ячейки А 7 — А9, зарезервированные под вероятности раЬурс и ячейку В1 (для цены игры).

Далее вводим несколько ограничений:

  • 1) сумма вероятностей равна 1;
  • 2) ограничения на неотрицательность вероятностей;
  • 3) система неравенств (1) — (3).

Для запуска программы осталось нажать кнопку «Выполнить». Все изменения видны в таблице (рис. 2.17).

Программа вычислила вектор и цену игры v = 0.

Для нахождения вектора вероятностей q добавим в таблицу еще несколько элементов. Ранее было показано, что решение антагонистической игры в смешанных стратегиях приводит к системе неравенств для второго игрока вида (2.5).

Применительно к нашей задаче получим

Добавим в ячейку Н7 формулу для ограничения (4): и скопируем формулу в ячейки Н8 и Н9 (рис. 2.18).

Снова запускаем программу «Поиск решения» и перенастраиваем ее (рис. 2.19).

Обратите внимание, что мы поменяли задачу на максимум на задачу на минимум. Кроме того, изменились переменные в окне «Изменяя ячейки» и ограничения на переменные. После нажатия на клавишу «Выполнить» получим результат (рис. 2.20).

Ответ: цена игры v = 0.

Поиск решения как средство решения задач теории игр Текст научной статьи по специальности «Экономика и бизнес»

Аннотация научной статьи по экономике и бизнесу, автор научной работы — Гришкина Т. Е., Лебедь О. А.

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

Похожие темы научных работ по экономике и бизнесу , автор научной работы — Гришкина Т. Е., Лебедь О. А.

EXCEL SOLVER AS CURE OF TASKS OF THE THEORY OF GAMES

This article demonstrate example of solution task of the theory of games with superstructure use " Excel Solver " Microsoft Excel spreadsheets for the purpose of optimization training process of is reviewed.

Текст научной работы на тему «Поиск решения как средство решения задач теории игр»

Гришкина Т.Е.1, Лебедь О.А.1

'Старший преподаватель, ФГБОУ ВПО «Амурский государственный университет»

ПОИСК РЕШЕНИЯ КАК СРЕДСТВО РЕШЕНИЯ ЗАДАЧ ТЕОРИИ ИГР

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

Ключевые слова: Поиск решения, Microsoft Exсel, теория игр.

Keywords: Excel Solver, Microsoft Exсel, theory of games.

Развитие информатизации образования и внедрение в учебный процесс современных информационных технологий повышает эффективность и качество обучения; обеспечивает мотивацию к самостоятельной познавательной деятельности студентов; способствует углублению межпредметных связей за счет интеграции информационной и предметной подготовки. Надстройка «Поиск решения» представляет собой мощный инструмент для выполнения сложных вычислений, позволяет находить значения переменных, удовлетворяющих указанным критериям оптимальности, при условии выполнения заданных ограничений. Такие результаты оптимизации оформляются в виде отчетов трёх типов: результаты, устойчивость и пределы.

Использование надстройки «Поиск решения» дает преимущество в решении социально-экономических задач, в которых необходимо принимать решения в условиях неопределенности, т. е. возникают ситуации, в которых две (или более) стороны преследуют различные цели, а результаты любого действия каждой из сторон зависят от мероприятий партнера. Такие ситуации относятся к конфликтным: результат каждого хода игрока зависит от ответного хода противника, цель — выигрыш одного из партнеров. Примерами таких ситуаций служат отношения между продавцом и покупателем, адвокатом и прокурором, кредитором и дебитором, истцом и ответчиком и т.д.

Математические методы анализа конфликтных ситуаций объединяются под названием теории игр, сама конфликтная ситуация носит название игры, а стороны, участвующие в конфликте, называются игроками. Исход игры называется выигрышем (или проигрышем) игроков. Если в игре участвуют только два игрока, то игра называется парной. Если выигрыш одного игрока равен проигрышу другого, то игра называется антагонистической.

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

Игру можно представить в виде матрицы, в которой строки — стратегии первого игрока (Ai, i = 1, m), столбцы —

стратегии второго игрока (B ■, j = 1, n ), а элементы матрицы (ai-) платежной.

выигрыши первого игрока. Такую матрицу называют

Величина a = max min a jj — гарантированный выигрыш, который может обеспечить себе первый игрок, — называется нижней i j J

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

любом случае проиграет не больше fi = min max a -, где в — верхняя цена игры (минимакс).

Для матричной игры справедливо неравенство a < fi .

Если а = в, то такая игра называется игрой с седловой точкой, а пара оптимальных стратегий (А1опт, В-опт) — седловой точкой матрицы. В этом случае элемент aij = v называется ценой игры, является одновременно минимальным в i-й строке и j-м столбце. Если игра имеет седловую точку, то говорят, что она решается в чистых стратегиях.

Матричные игры в чистых стратегиях определенной размерности можно автоматизировать в табличном процессоре Microsoft Excel. При этом используются встроенные функции: МАКС, МИН, ЕСЛИ и ПОИСК РЕШЕНИЯ.

Если платежная матрица не имеет седловой точки, т.е. а < в, то поиск решения игры приводит к применению сложной стратегии, состоящей в случайном применении двух и более стратегий с определенными частотами. Такая сложная стратегия называется смешанной.

Решение задач по теории игр включает следующие этапы:

1) составление платёжной матрицы игры в соответствии с выбранными вариантами;

2) определение верхней и нижней цены игры;

3) если а Ф в, то следует составить две взаимно-двойственные задачи;

4) решение задачи линейного программирования. Рекомендуется решать задачу на максимизацию целевой функции с ограничениями «меньше либо равно»;

5) формулирование выводов по задаче.

Рассмотрим решение задачи теории игр в смешанных стратегиях с использованием надстройки «Поиск решения».

Торговая фирма разработала несколько вариантов плана продаж товаров на предстоящей ярмарке с учетом спроса покупателей. Получающиеся от их возможных сочетаний показатели дохода представлены в таблице.

Таблица 1 — Показатели дохода

Bj Ai Bi B2 B3 a Pi

fi 4 4 5 a =2, fi =4

Определить оптимальную стратегию фирмы в продаже товаров на ярмарке, гарантирующую среднюю величину дохода при любом состоянии спроса, считая его неопределенным.

Задача сводится к игровой модели, в которой игра предприятия А против спроса В задана платёжной матрицей (табл. 1). Определим нижнюю и верхнюю цены игры в табл. 1.

Так как а Ф в, то седловая точка отсутствует, и оптимальное решение следует искать в смешанных стратегиях игроков:

sa = (л,Р2.Рз) и sb = (qi,Чз).

Составим две взаимно-двойственные задачи линейного программирования, обозначив Xt

L(x) = x1 + x2 + x3 ^ min 2×1 + x2 + 4×3 > 1 < 4×1 + 3×2 + 2×3 > 1 2×1 + 5×2 + 3×3 > 1 xt > 0

F (y) = У1 + y2 + У3 ^ max

2У1 + 4У2 + 2У3 < 1

Решение двойственной задачи линейного программирования представлено на рис. 1-3. ПО ▼ , £ I =1/F3

Как решать теорию игр в excel

Артём FLASH |информатика ЕГЭ| 100б репетитор

Артём FLASH |информатика ЕГЭ| 100б репетитор

Артём FLASH |информатика ЕГЭ| 100б репетитор запись закреплена

🔥ОБЯЗАТЕЛЬНО смотри этот способ решения в EXCEL

✒В этом видео я расскажу как решать теорию игр с одной кучей через Excel. Да, это задание проще решить руками, но если ты хочешь автоматизировать процесс решения, то данный разбор тебе в помощь.

❗Оставайся в курсе всех новостей! Следи за актуальными материалами, подборками, связанными с ЕГЭ по информатике!
https://vk.cc/c5pA6F

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *