Использование матричных игр для решения экономических задач

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования

«Брестский государственный университет имени А. С.Пушкина»

Математический факультет

Кафедра математического моделирования

Курсовая работа

ИСПОЛЬЗОВАНИЕ МАТРИЧНЫХ ИГР ДЛЯ РЕШЕНИЯ

ЭКОНОМИЧЕСКИХ ЗАДАЧ

«Экономическая кибернетика»

Брест 2008

• Содержание
• 1. Матричные игры
• 1.1 Постановка задачи и описание метода решения
• 1.2 Методы решения матричных игр
• 1.2.1 Решение матричной игры сведением к задаче линейного программирования
• 1.2.2 Решение матричной игры графическим методом
• 1.2.3 Решение задачи линейного программирования сведением к эквивалентной матричной игре
• 1.2.4 Приближенный метод решения матричных игр
• Заключение
• Список использованных источников

Введение

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

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

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

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

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

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

Работа состоит из введения, двух разделов, в которых изложены теория игр и методы решения.

Первый раздел посвящён изложению приближённого решения игры разными методами: решение матричной игры сведением к задаче линейного программирования, решение матричной игры графическим способом, решение задачи линейного программирования к эквивалентной матричной игре и приближенный метод решения матричной игры.

Во втором разделе приведены примеры решения матричных игр некоторыми способами: графическим и приведением матричной игры к задаче линейного программирования.

матричная игра задача стратегия

1. Матричные игры

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

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

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

В экономической практике нередко приходится формализовать (моделировать) ситуации, придавая им игровую схему, в которых один из участников безразличен к результату игры. Такие игры называют играми с природой, понимая под термином "природа" всю совокупность внешних обстоятельств, в которых сознательному игроку приходится принимать решение. Например, выбор агрономической службой сельскохозяйственного предприятия участков различного плодородия посева той или иной культуры в надежде получить в предстоящем сезоне наилучший урожай, если нет достоверных данных о погодных условиях, которые могут сложиться в данном регионе; определение объема выпуска сезонной продукции новых образцов в ожидании наиболее выгодного для ее реализации уровня спроса; формирование пакета цент расчете на высокие дивиденды и т. п. Здесь в качестве второго игрока -- "природы" -- выступает: в первом при буквальном смысле природа; во втором -- множество причин, влияющих на величину спроса; в третьем -- совокупность обстоятельств, обусловливающих то или иное состояние рынка ценных бумаг.

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

Пусть игроки и располагают конечным числом возможных действий -- чистых стратегий. Обозначим из соответственно и . Игрок может выбирать любую чистую стратегию , в ответ на которую игрок может выбрать любую свою чистую стратегию . Если игра состоит только из личных хо бор пары стратегий однозначно определяет результат -- выигрыш игрока . При этом проигрыш игрока В составляет -- . Если известны значения -- выигрыша для каждой пары чистых стратегий, можно составить матрицу выигрышей игрока (проигрышей игрока ) (табл.1). Ее называют платежной.

Таблица 1.

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

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

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

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

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

Функцию называют функцией выигрыша или платежной функцией.

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

Величину называют ценой игры.

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

1.2 Методы решения матричных игр

1.2.1. Решение матричной игры сведением к задаче линейного программирования. Пусть игра задана платежной матрицей табл.1. Оптимальные смешанные стратегии и игроков и могут быть найдены в результате решения пары двойственных задач линейного программирования.

Для игрока :

(1)

В результате решения задачи (1) находят оптимальный вектор и , а затем

(2)

Для игрока :

 (3)

Решая задачу (3), находят оптимальный вектор и , а затем

; (4)

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

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

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

1.2.3. Решение задачи линейного программирования сведением к эквивалентной матричной игре. Доказывается, что паре симметричных задач линейного программирования:

(max); ; ; (5)

(min); ; ; (6)

где

; ;

; ; ,

эквивалентна игре с платежной матрицей:

 (7)

Поскольку матрица (7) кососимметрическая, то цена игры равна нулю, а оптимальной для обоих игроков будет одна и та же смешанная стратегия:

где .

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

; ; ; (8)

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

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

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

Таблица 2

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

Таблица 3

Заполнение первой строки табл. 3 завершаем записью значений выигрышей , соответствующих всем возможным стратегиям игрока . В последние три столбца запишем: -- наименьший из накопленных выигрышей игрока за h партий, деленный на число партий h; -- наибольший из накопленных проигрышей игрока за h партий, деленный на число партий h; -- среднее арифметическое и -- приближенное значение цены игры.

Во второй партии игрок предполагает, что игрок и в данной партии воспользуется стратегией , а поэтому игрок отвечает стратегией, которая обеспечивает ему при стратегий наибольший выигрыш. Эта стратегия соответствует наибольшему из элементов . Пусть им будет, например, элемент . Тогда наилучшей для игрока будет чистая стратегия . Во вторую строку табл. 3 запишем суммарные значения выигрыша за первую (при стратегии ) и вторую (при стратегии ) партии -- накопленный выигрыш . В свою очередь игрок , анализируя суммарные выигрыши игрока и предполагая, что игрок и далее будет пользоваться стратегией , аккумулирующей опыт первых партий (в накопленном выигрыше), выбирает стратегию , отвечающую -- наименьшему из элементов . Заканчивая заполнение второй строки табл. 3, записываем накопленный проигрыш игрока за две партии при различных стратегиях игрока : . Заполняем и последние три столбца: .

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

; .

Приближенное значение цены игры .

Заключение

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

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

Матричные игры решаются разными методами:

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

ь решение матричной игры графическим способом

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

ь приближенный метод решения матричной игры.

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

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

По количеству стратегий игры делятся: конечные и бесконечные. Если в игре все игроки имеют конечное число возможных стратегий, то она называется конечной. Если же хотя бы один из игроков имеет бесконечное количество возможных стратегий игра называется бесконечной.

Список использованных источников

1. Алесинская,Т.В. Экономико-математические методы и модели. Линейное программирование: учеб.-метод. пособие / Т.В. Алесинская, В.Д.Сербин, А.В.Катаев. - Таганрог: ТРТУ, 2001. - 79 с.

2. Афанасьев, М.Ю. Исследование операций в экономике: модели, задачи, решения / М.Ю. Афанасьев, Б.П.Суворов - М.: ИНФРА-М, 2003. - 444с.

3. Гилл, Ф. Практическая оптимизация: пер. с англ. / Ф.Гилл, У. Мюррей, М. Райт. - М.: Мир, 1985. - 509 с.

4. Костевич, Л.С. Математическое программирование: информ. технологии оптимальных решений: учеб. пособие / Л.С. Костевич. - Мн.: Новое знание, 2003. - 424 с.

5. Кузнецов, А.В. Руководство к решению задач по математическому программированию: учеб. пособие / А.В.Кузнецов, Н.И.Холод, Л.С.Костевич; под ред. А.В. Кузнецова. - Мн.: Высшая школа, 2001. - 448 с.

6. Кузнецов, Ю.Н. Математическое программирование: учеб. пособие. / Ю.Н. Кузнецов, В.И. Кузубов, А.Б. Волощенко. - М.: Высшая школа, 1980. - 300 с.

7. Струченков, В.И. Методы оптимизации. Основы теории, задачи, обучающие компьютерные программы: учеб. пособие / В.И. Струченков. - М.: Экзамен, 2005. - 256с.

8. Сырцова, Е.Д. Математические методы в планировании и управлении строительным производством: учеб. пособие / Е. Д. Сырцова. - М.: Высшая школа, 1972. - 336 с.

9. Ху, Т. Целочисленное программирование и потоки в сетях / Т. Ху. - М.: Мир, 1974. - 520 с.

10. Шикин, Е.В. Математические методы и модели в управлении / Е.В. Шикин, А.Г. Чхартишвили. - М.: Дело, 2000. - 435 с. Размещено на allbest.ru