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

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

Completing the CAPTCHA proves you are a human and gives you temporary access to the web property.

What can I do to prevent this in the future?

If you are on a personal connection, like at home, you can run an anti-virus scan on your device to make sure it is not infected with malware.

If you are at an office or shared network, you can ask the network administrator to run a scan across the network looking for misconfigured or infected devices.

Another way to prevent getting this page in the future is to use Privacy Pass. You may need to download version 2.0 now from the Chrome Web Store.

Cloudflare Ray ID: 71adc006faa375b9 • Your IP : 82.102.23.104 • Performance & security by Cloudflare

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

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

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

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

Для рассмотрения метода приведения матричной игры к задаче линейного программирования необходимо познакомиться еще с одним свойством матричных игр, которое называется аффинным правилом. Оптимальные стратегии в матричных играх А и В, элементы платежных матриц которых связаны равенством

где >0, а р — любое вещественное число, имеют одинаковые равновесные ситуации (либо в чистых, либо в смешанных стратегиях), а цены игр удовлетворяют следующему условию: v_A=Xi^ +р.

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

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

Из определения оптимальной смешанной стратегии следует, что игрок 1, придерживающийся своей оптимальной смешанной стратегии, «выиграет» не меньше v при любых стратегиях игрока 2 (в том числе чистых), а игрок 2, придерживающийся своей оптимальной смешанной стратегии, «проиграет» не больше г при любых стратегиях игрока 1 (в том числе чистых). Из этого следует, что смешанные стратегии x=(xi. х_т), у=(у. у„) соответственно игроков 1 и 2 и цена игры v должны удовлетворять соотношениям:

Разделим все уравнения и неравенства в данных системах на v (это можно сделать, так как по предположению v > 0) и введем обозначе- ния:

Тогда получаем: и

Поскольку первый игрок стремится максимизировать цену игры v выбором значений х„ то обратная величина l/v должна минимизироваться выбором р,. Таким образом, решение первой задачи сводится к нахождению таких неотрицательных значений р, (/ = 1,/я), при которых

Поскольку игрок 2 стремится найти такие значения и, следовательно, qj, чтобы цена игры v была наименьшей, то решение второй задачи сводится к нахождению таких неотрицательных значений qj, (j = 1, л), при которых

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

Решив эти задачи, получим значения

Тогда значение цены игры v определяется из условия

Оптимальные смешанные стратегии, т.е. х₍° и у®, получаются по формулам:

Для примера проиллюстрируем использование метода для решения следующей задачи (вариант игры «Борьба за рынки»).

Пример 2.3. Две конкурирующие компании А и Б принимают решение о финансировании трех инновационных технических проектов. Каждая из компаний может инвестировать 100 ден. ед. Компания Б пытается занять рынок, на котором традиционно компания А лидирует. В случае разработки и развития одних и тех же проектов компания А получит прибыль, тогда как компания Б понесет убытки. Если инвестиции направляются в разные проекты, компания А понесет убытки, связанные с перераспределением рынка. Прибыль предприятия А при разных стратегических ситуациях представлена в табл. 2.7. Прибыль предприятия Б соответствует убытку предприятия А. Найти оптимальные стратегии предприятий.

Прибыль компании А при финансировании трех проектов, ден. ед.

Стратегии предприятия Б

Стратегии предприятия А

В таблицу Excel вводятся элементы платежной матрицы игры А, и с помощью функций МИН () и МАКС () определяются минимальные и максимальные значения по строкам и по столбцам соответственно, затем с помощью этих же функций находятся максимин и минимакс (табл. 2.8). Поскольку эти значения не совпадают, седловой точки в игре нет, т.е. в чистых стратегиях она не решается. Значение цены игры должно лежать в диапазоне [—5; 10].

Проверка наличия седловой точки в игре

Для использования алгоритма решения игры путем ее сведения к задаче линейного программирования применим аффинное правило. С помощью функции МИН () находим минимальное значение элементов платежной матрицы (—20). Модуль этого числа определяется как ABS (МИН (. )). С помощью аффинного преобразования с параметрами к= 1 и р = 20 получена новая платежная матрица (табл. 2.9).

Сведение игры к задаче линейного программирования

Справа от платежной матрицы произвольно указываются искомые переменные р, (на этом этапе могут указываться любые значения). В ячейках под платежной матрицей с помощью функции СУММПРО- ИЗВ () определяются значения

которые будут использоваться в ограничениях задачи ЛП. Эти значения для произвольно выбранных р, приведены в табл. 2.9.

В ячейке, обозначенной как «Целевая функция», вводится формула СУММ (. ), соответствующая выражению для целевой функции

В ячейке, обозначенной как «Цена игры», вводится формула для определения цены игры через значение целевой функции

В ячейках, обозначенных как х„ вводятся формулы для обратного преобразования переменных и нахождения искомых элементов смешанной стратегии игрока 1 х, = vp,.

Формулировка первой задачи линейного программирования: найти значения р,, обеспечивающие минимум функции

Решение задачи линейного программирования осуществляется с помощью модуля «Поиск решения» (меню «Сервис» программы Excel) 1 . В диалоговом окне (рис. 2.4) в поле «Установить целевую ячейку» указывается адрес ячейки, содержащей значение целевой функции; выбирается режим «Равной: минимальному значению». В поле «Изменяя ячейки» указывается массив искомых переменных р_г Нажатием кнопки «Добавить» и выбором массива, соответствующего ограничениям задачи, в поле «Ограничения» устанавливается соответствующее условие. Нажатием на кнопку «Параметры» осуществляется переход в диалоговое окно «Параметры поиска решения», в котором выбираются параметры «Линейная модель» и «Неотрицательные значения»; значения остальных параметров остаются без изменений. После закрытия окна «Параметры поиска решения» (кнопкой «ОК») нажатием

Рис. 2.4. Диалоговое окно «Поиск решения»

1 Если этот модуль в меню отсутствует, нужно предварительно выбрать его в опции «Надстройки» меню «Сервис».

на кнопку «Выполнить» в окне «Поиск решения» осуществляется запуск итерационного процесса поиска решения задачи ЛП.

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

Результаты решения задачи ЛП для игрока 1

Результаты решения задачи ЛП для игрока 2

Аналогично решается задача ЛП для игрока 2 (табл. 2.11). Обратите внимание, что в данном случае для технического удобства массив искомых переменных расположен в строчку (поскольку стратегии игрока 2 соответствуют столбцам платежной матрицы), а ячейки с ограничениями — в столбец. Задача решается на максимум и формулируется так: найти значения qj, обеспечивающие максимум функции

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

Решение игры «Финансирование проектов»

Результаты показывают, что оптимальной стратегией компании А является распределение средств, предполагаемых к инвестированию, в следующей пропорции: 29%, 60%, 11%, т.е. 29, 60 и 11 ден. ед. При этом компания А получит прибыль не менее 0,5 ден. ед.Минимальное значение прибыли (0,5 ден. ед.) компания А получит при условии, что компания В будет придерживаться своей оптимальной стратегии инвестирования проектов, а именно: 39%, 25%, 36%, т.е. инвестировать в проекты 39, 25 и 36 ден. ед. соответственно. Если компания В будет отклоняться от этой стратегии (придерживаться другой схемы инвестирования), прибыль компании А будет расти.

Анализ решения показывает, что для компании В данная «игра» невыгодна (ожидаемый убыток составляет приблизительно 0,5 ден. ед.). Однако, если компания В считает этот убыток сравнительно незначительным по сравнению с достижением поставленной цели — вхождение на рынок, традиционно контролируемый компанией А, то придерживаясь своей оптимальной стратегии распределения инвестиций, компания В потеряет не больше 0,5 ден. ед. Если компания А будет вести себя «нерационально», то потери компании В будут уменьшаться.

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

Затем следует во всех случаях проверить наличие седловой точки, т.е. выполнение условия

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

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

Создание пятнашек в Excel

Разбор создания игры в Excel

При создании игры мы преследовали две цели:

1. Продемонстрировать возможности программирования и визуализации в Excel. На примере научить вас некоторым приемам создания пользовательской формы и макросов, которые с ней взаимодействуют.
2. Разнообразить досуг после плодотворной работы в Excel. Игра также встроена в нашу надстройку VBA-Excel чтобы она всегда была под рукой.

Разработка игрового поля

Игровое поле пятнашек состоит по сути из 16 фишек, можно также добавить кнопкой перемешать (начать с начала) и отображением количества шагов. В качестве фишек мы будем использовать обычные кнопки CommandButton — 16 штук.

Расположим их в виде поля 4×4. Уберем стандартное название кнопок (а свойство Caption) сделаем их квадратными в форме фишек. Вообще тут можно дать волю фантазии наложить тени, выбрать цвет и так далее, углубляться не будем. На игровое поле мы добавили также кнопку перемешать. Она будет служить для сброса и начала новой игры.

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

Механика игры

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

Старт игры

Инициализация формы вызываем процедуру создания поля.

Случайным образом заполняем игровое поле и проверяем комбинацию на решаемость. Подробно проверку на решаемость описывать не будем, так как не в этом цель. Изучить этот вопрос можно на сайте http://pyatnashki.wmsite.ru/kombinacyi.

Функция проверки заряженного числа на четность

Создадим процедуры, которые будут перемещать наши фишки. Ниже приведена одна из них, остальные аналогичные, можете найти их в файле.

В конце делаем проверку поля и проверяем правильно ли игрок расставил фишки.

Осталось "отловить" нажатие стрелок на клавиатуре и запускать нужное движение. Для этого воспользуемся событием формы UserForm_KeyDown.