Вряд ли можно найти человека, которому удалось в жизни сыграть во все игры, которые есть на свете,- их множество. У каждой свои правила, свои особенности. Хоккей, например, отличается от футбола, домино — от шахмат, шашки — от «крестиков-ноликов», «морской бой» — от игры в слова и т. д. И все-таки совершенно непохожие игры принципиально — в главном совершенно одинаковы. В чем их одинаковость? В столкновении интересов. Вася и Петя играют в шахматы. Каждому во что бы то ни стало, хочется выиграть.
На футбольном поле встречаются две команды. Кто-то из них должен стать победителем. Одна, безусловно, приложит к этому все силы. И вторая полона решимости победить. Столкновение интересов бывает не только в играх. Оно случается часто, намного чаще, чем мы предполагаем. Проследите под этим углом зрения один из своих обычных дней. Сколько раз сталкивались ваши интересы с чьими-либо! В повседневной жизни, в практической деятельности очень часто встречаются ситуации, когда разные люди проявляют разные интересы и располагают разными путями в достижении разных целей. Иными словами, всем нам часто приходится сталкиваться с конфликтными ситуациями.
Такие ситуации, возникающие при игре в шахматы, шашки, домино и т. д. Результат каждого хода игрока зависит от ответного хода противника, цель игры — выигрыш одного из партнёров. В экономике конфликтные ситуации встречаются очень часто и имеют многообразный характер. К ним относятся, например, взаимоотношения между поставщиком и потребителем, покупателем и продавцом, банком и клиентом. Во всех этих примерах конфликтная ситуация порождается различием интересов партнёров и стремлением каждого из них принимать оптимальные решения, которые реализуют поставленные цели в наибольшей степени. При этом каждому приходится считаться не только со своими целями, но и с целями партнёра, и учитывать неизвестные заранее решения, которые эти партнёры будут принимать.
Для грамотного решения задач с конфликтными ситуациями необходимы научно обоснованные методы. Такие методы разработаны математической теорией конфликтных ситуаций, которая носит название теория игр.
Теория игр — математическая дисциплина, устанавливающая количественные закономерности в конфликтных и неопределенных ситуациях. |
Теория игр была разработана Дж. фон Нейманном и О. Моргенштерном в 1944 г., ее дальнейшую разработку продолжил Дж. Нэш.
Ознакомимся с основными понятиями теории игр. Математическая модель конфликтной ситуации называется игрой, стороны, участвующие в конфликте, — игроками, а исход конфликта — выигрышем. Для каждой формализованной игры вводятся правила, т.е. система условий, определяющая: 1) варианты действий игроков; 2) объём информации каждого игрока о поведении партнёров; 3) выигрыш, к которому приводит каждая совокупность действий. Как правило, выигрыш (или проигрыш) может быть задан количественно; например, можно оценить проигрыш нулём, выигрыш — единицей, а ничью — ?..
Игра называется парной, если в ней участвуют два игрока, и множественной, если число игроков больше двух. Мы будем рассматривать только парные игры. В них участвуют два игрока А и В, интересы которых противоположны, а под игрой будем понимать ряд действий со стороны А и В.
В теории игр смысл терминов несколько иной. В теории игр игроком могут быть и несколько человек с определенным интересом, которые борются против одного или, наоборот, против большого количества противников, которые тоже признаны игроком. Значит, игрок — это просто одна группа интересов. Футбольный матч с точки зрения теории игр будет просчитываться как один игрок против одного. В этом смысле он не отличается от шахматной партии. Выдающийся французский математик Луи Борель еще в начале XX века предпринял издание большого, многотомного «Курса теории вероятностей и ее приложений». Предпоследний том был посвящен «Приложениям к азартным играм». Ученый подвел в нем итог своим длительным исследованиям азартных игр, которыми он интересовался как математик. В теорию игр Борель внес смелые и оригинальные идеи. Он попытался найти математическую формулировку игр, когда течение игры зависело от умения игроков. Со временем многие ученые развили теорию. Она стала гораздо шире теории азартных игр. Оказывается, игры бывают антагонистические и неантагонистические, бабочкообразные и вогнуто-выгнутые, бескоалиционные и кооперативные, позиционные и динамические, и даже игры с «линией жизни», и игра с преследованием с ограниченным временем. Есть в теории игр и «общая теория полезности», и еще много других интересных и необходимых для решения важных практических задач.
Игра называется игрой с нулевой суммой, или антагонистической, если выигрыш одного из игроков равен проигрышу другого, т. е. для полного задания игры достаточно указать величину одного из них.
Выбор и осуществление одного из предусмотренных правилами действий называется ходом игрока. Ходы могут быть личными и случайными. Личный ход — это сознательный выбор игроком одного из возможных действий (например, ход в шахматной игре). Случайный ход — это случайно выбранное действие (например, выбор карты из перетасованной колоды).
Стратегией игрока называется совокупность правил, определяющих выбор его действия при каждом личном ходе в зависимости от сложившейся ситуации. Обычно в процессе игры при каждом личном ходе игрок делает выбор в зависимости от конкретной ситуации. Однако в принципе возможно, что все решения приняты игроком заранее (в ответ на любую сложившуюся ситуацию). Это означает, что игрок выбрал определённую стратегию, которая может быть задана в виде списка правил или программы. (Так можно осуществить игру с помощью ЭВМ). Игра называется конечной, если у каждого игрока имеется конечное число стратегий, и бесконечной — в противном случае.
А теперь познакомимся со скандальной историей, случившейся в одном из игорных домов Европы.… Сначала на них никто не обращал внимания. Молодые люди заходили в казино поглядеть на игру в рулетку, останавливались возле игорных столов и записывали в блокноты номера выигрышей, то есть номера чисел на диске рулетки, против которых останавливался шарик. «Просто так, любопытства ради»,- отвечали они тому, кто их спрашивал: «Зачем?». А спустя два месяца в Монте-Карло, в столице игорных домов, разразилась гроза. Снова пришли те молодые люди. Но теперь они ничего не записывали, а стали играть. И выигрывали, как говорят математики, «в достаточно длинных партиях». Журналисты захотели найти объяснение, и считают, что нашли. Оказывается, молодые люди не ради любопытства записывали номера выигрышей. Мало того, они еще их и закодировали. И после этого переслали в Лондон своему компаньону. Тот обработал их с помощью электронной вычислительной машины. В «американском случае» машинное руководство к действию (алгоритм поиска вариантов) было составлено так, чтобы изыскивать повышение вероятностей благоприятного исхода. Именно с этой целью перебирала машина горы чисел, строя свою игру против вымышленного противника по законам теории игр. Право же, не стоило создавать целое направление в математике, чтобы помогать выигрывать в азартные игры! Конечно, теория игр создана не для этого Модели игр служат тем инструментом, с помощью которого теория игр пытается проверить серьезные задачи. С помощью теории игр стремятся выработать целесообразную линию поведения для многих и многих систем, ведущих борьбу против другой системы.
Например, теорию игр можно применить к задачам связи, к вопросам технологии медицины, нефтедобычи, спорта, рыболовства, к противовоздушной обороне, к задачам, которые приходится решать командиру в сражении. Под углом зрения теории игр можно рассматривать и работу экспериментатора, который составляет план экспериментов. Их можно рассматривать как игру, где противниками выступают ученый и нервная система животного, которую он изучает. Есть игры, в которых прорабатываются сложные ситуации, растянутые во времени. Для них готовят специальное математическое обеспечение, им нужна достаточно мощная база вычислительных машин. Ведь для исследования даже самой простой производственно-хозяйственной ситуации бывает необходимым провести большое количество вычислений. В большинстве случаев в играх приходится иметь дело с цифрами: проделывать головокружительное количество вычислений. Не случайно, значит, учат машину играть в разные игры: в домино, в шашки, в шахматы. Шахматы, дающие астрономическое число вариантов партий -2*10116 — открывают большой простор для исследований.
Теория игр имеет большое значение в экономическом анализе. В последние годы значение теории игр существенно возросло во многих областях экономических и социальных наук. С помощью теории игр предприятие получает возможность предусмотреть ходы своих партнеров и конкурентов.
Эта теория рассматривает поведение фирм на рынке как игру, причем имеются определенные правила игры, по результатам которой начисляются «призы» и «штрафы». Участники игры определенно не знают стратегию конкурента, поэтому их поведение основано лишь на прогнозах.
Например, рассмотрим стратегию фирм А и В (табл. 4) с понижением цены. Если обе фирмы не понижают цену, прибыль каждой составит, например, 60 млн усл. ед. Если одна из фирм понижает цену, она получает конкурентное преимущество и увеличивает прибыль до 85 млн усл. ед. В это время конкурент терпит убыток в размере 25 млн усл. ед. Если же обе фирмы в сговоре проводят политику снижения цены, прибыль каждого составит по 12,5 млн усл. ед. Необходимо определить, как поступить фирмам А и В, чтобы не проиграть.
Аналогом данной ситуации на рынке служит другая игра — так называемая «дилемма заключенного». Суть этой игры в следующем: два узника содержатся в отдельных камерах и обвиняются по одному делу (табл. 5).
У обвинения достаточно улик, чтобы осудить узников только на два года. Узникам сообщили (каждому отдельно), что если один сознается, а другой нет, то сознавшийся будет свободен, а не сознавшийся получит 20 лет. Если сознаются оба, то каждый получит по 10 лет. Необходимо определить, каким будет поведение заключенного, когда реакция другого неизвестна.
В этом случае различают две стратегии поведения, называемые maximin и maximax:
1. min — это стратегия пессимиста.
2. max — это стратегия оптимиста.
Пессимист будет искать наилучший вариант из наихудших результатов. Это ситуация, когда, например, узник А ждет, что узник В признается, и тогда А получит 20 лет заключения, при условии, что он не сознается. Чтобы обеспечить себе наименее плохой результат из всех плохих вариантов, узник А решает сознаться, поскольку это позволит ему получить 10 лет заключения, а не 20. Этот результат лучше, чем 20 лет заключения.
Аналогично будет рассуждать и узник В. В результате, не сговариваясь, оба узника придут к решению сознаться и получат по 10 лет тюрьмы.
Оптимист надеется на самый лучший вариант решения вопроса. Узник А думает, что узник В не сознается, поэтому он решает сознаться. Но узник В также оптимист и поступает аналогичным образом. В результате, не сговариваясь, оба заключенных придут к решению сознаться и получат по 10 лет тюрьмы.
Стратегии min и max привели узников к одному результату — это и есть решение Нэша.
Подобного рода решение примут фирмы А и В на конкурентном рынке. В обоих случаях фирмы А и В решают снижать цены, и стратеги min и max приведут их к решению Нэша, т. е. понижать цены, что даст им равные прибыли — по 12,5 млн усл. ед, каждой фирме.
Заключение
«Есть в современной математике одна область, она носит безобидное название теории игр, но ей, несомненно, суждено сыграть очень важную роль в человековедении самого ближайшего будущего, — говорил Джон фон Нейман, один из основоположников кибернетики.- Она занимается вопросами оптимального поведения людей при наличии противодействующего противника. Для ученого противник — это природа со всеми ее явлениями; экспериментатор борется со средой; математик — с загадками математического мира; инженер — с сопротивлением материалов».
www.ronl.ru
Челябинский юридический колледж
Кафедра математических и естественнонаучных дисциплинКУРСОВАЯ РАБОТА
по дисциплине «Математические методы»
Теория игр. Графический метод решения теории игр
Работу выполнила студентка гр. ПО-001-06 | А.В. Егорова |
| Руководитель | Н.Р. Хабибуллина |
Челябинск
2009
Содержание
1. Введение 2. Основные методы решений 2.1.Основные понятия теории игр 2.2.Матричные игры 2.3.Решение матричной игры в чистых стратегиях 2.4.Принцип доминирования 2.5.Решение матричной игры 2×2 в смешанных стратегиях 3. Геометрическое решение игры 3.1.Решение игр с платежной матрицей 2×n 3.2.Решение игр с платежной матрицей m ×24. Практическая часть 5. Заключение 6. Список литературы | 3 4 5 7 11 12 15 18 |
Введение
Непрерывное и последовательное развитие социалистического общества, его производительных сил и производительных отношений, повышение эффективности общественного производства непрерывно связанно с совершенствование системы планирования и управления. Современные достижения науки и техники все шире используются в практике для получения научно обоснованных наиболее эффективных решений в сфере планирования и управления.
При решении ряда практических задач (в разных областях деятельности) приходится анализировать ситуации, где налицо две ( или более) враждующие стороны, преследующие противоположные цели, причем результат каждого мероприятия одной из сторон зависит от того, какой образ действия выберет противник.
Необходимость анализировать подобные ситуации вызвала к жизни специальные математический аппарат. Теория игр по существу представляет собой не что иное, как математическую теорию конфликтных ситуаций.
Целью данной работы является рассмотрение не только теории игр в общем, но и ее графический метод решения.
Для наиболее оптимального изучения и рассмотрения поставлены следующие задачи:
1. Кратко изложить понятие о теории игр в целом;
2. Рассмотреть основные методы решений задач теории игр;
3. Детально изучить графический метод решения задач теории игр.
4. Привести примеры задач, решенных с помощью этого метода..
Основные методы решений 1.Основные понятия теории игрМногие социально-экономические ситуации, в которых рассматриваются вопросы о выборе решения, обладают тем свойством, что в них сталкиваются не мнение двух сторон с различными интересами, каждая из которых для достижения своей цели имеет возможность действовать различными способами,
выбор которых при некоторых условиях может осуществляться в зависимости от
действий противоборствующей стороны. Такие ситуации называют конфликтными .
Математическая модель конфликтной ситуации называется игрой. Теория игр занимается математическими моделями принятия оптимальных решений в условиях конфликта. Любое возможное в игре действие игрока называется его стратегией. Игра называется конечной, если множество стратегий каждого игрока конечно. В противном случае (т.е. когда множество стратегий хотя бы одного игрока бесконечно), игра называется бесконечной. В дальнейшем будем рассматривать только конечные игры двух лиц .
Основной целью теории игр является выявление для каждого из игроков «оптимальных стратегий».
Оптимальной называется стратегия, которая при многократно повторяющейся игре гарантирует игроку максимально возможный средний выигрыш (или, эквивалентно, минимально возможный средний проигрыш).Выбор оптимальной стратегии базируется на принципе, предполагающем, что обаигрока разумны в одинаковой степени и поведение каждого из них направлено напротиводействие противнику в достижении его цели. Таким образом, теория играбстрагируется от ошибок, просчетов, азарта и риска, присущих игрокам, реальных конфликтах.
Будем считать, что выигрыш одного игрока равен в точности проигрышу
второго игрока, такая игра называется игрой с нулевой суммой. Конечная игра двух игроков с ненулевой суммой, в которой выигрыши каждого игрока задаются матрицами отдельно для соответствующего игрока, называется биматричной игрой .
2.Матричные игрыМатричной игрой называется конечная игра двух игроков с нулевой
суммой, в которой задается выигрыш игрока 1 в виде матрицы, строка матрицы
соответствует номеру применяемой стратегии игрока 1, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы
находится выигрыш игрока 1, соответствующий применяемым стратегиям.
Пусть играют 2 игрока P1 и P2. Матрица
элементы aij – выигрыш игрока P1, если P1 – выбирает i строку, а P2 – выбирает j столбец, называется платежной матрицей игры .
Пусть игрок P1 выбирает i строку с вероятностью xi, P2 выбирает j столбец с
вероятностью yj, тогда и будут называться соответственно смешанными стратегиями 1-ого и 2-ого игроков .
Замечание: так как компонентами смешанных стратегий X и Y являются
вероятности, то и . Если среди компонентов смешанной стратегии X только одна 1, остальные 0, то стратегия называется чистой .
— i -ая чистая стратегия. Любую смешанную стратегию можно представить в виде выпуклой комбинации чистых стратегий, т.е.
Пример . Представить смешанную стратегию в виде выпуклой
комбинации чистых стратегий.
Решение.
Платежной функцией (X ,Y ) первого игрока называется математическое
ожидание его выигрыша, т.е.
(X ,Y )=
Решением матричной игры называют пару смешанных стратегий и
число v называемое ценой игры, удовлетворяющих следующим условиям:
1)
Если P1 придерживается своей оптимальной стратегии X *, то какую бы
чистую стратегию не принимал второй игрок P2, P1 получит выигрыш не меньше чем цена игры v .
2)
Если P2 придерживается своей оптимальной стратегии Y *, то какую бы чистую стратегию не применял второй игрок P1, то P2 проиграет не более чем цена игры v .
Теорема 1. Если игрок P1 придерживается своей оптимальной стратегии X *,
а P2 придерживается своей оптимальной стратегии Y *, то.
Теорема 2. Любая матричная игра имеет решение в смешанных стратегиях.
3.Решение матричной игры в чистых стратегияхРассмотрим матричную игру с игроками P1 и P2 и платежной матрицей
1) Перед игроком P1 стоит задача выбора чистой стратегии, в результате применения которой он получит максимально возможный гарантированный
выигрыш. Если игрок P1 выбрал стратегию , то его выигрышем может быть один из выигрышей , расположенный в i-ой строке платежной
матрицы, в зависимости от выбранной стратегии игроком P2. Предполагая поведение игрока P1 крайне осмысленным, необходимо считать, что игрок P2 сыграет наилучшим для себя образом и на выбор игроком P1 стратегии Xi выберет ту стратегию Yj, при которой выигрыш игрока P1 окажется минимальным.
Обозначим минимальный среди выигрышей через αi:
, (αi –показатель эффективности стратегии Xi ).
Продолжая действовать разумно, игрок P1 должен выбрать ту стратегию,
которая максимизирует показатель эффективности, т.е. для которой число αi максимально.
Обозначим:
Число α называется нижней ценой игры в чистых стратегиях, а стратегия
Xi0, которая максимизирует показатель эффективности αi называется максиминной стратегией игрока P1.
Таким образом, если игрок P1 в игре будет следовать максиминной стратегии, то ему при любой игре противника P2 гарантирован выигрыш в чистых стратегиях, не меньший α .
2) Рассмотрим игру с точки зрения игрока P2, который стремиться минимизировать выигрыш игрока P1. Если P2 выберет стратегию , то выигрышем игрока P1 может быть один из выигрышей . Но так как игрок P2 предполагает, что игрок P1 играет наилучшим для себя образом, то выигрышем игрока P1 будет максимальное из этих чисел, обозначим βj:
(βj –показатель неэффективности стратегии Yj ).
Таким образом, для любой стратегии Yj игрока P2 наибольший его проигрыш равен βj. В интересах игрока P2 выбрать стратегию с минимальным показателем неэффективности. Наименьшее из чисел βj обозначим β :
Число β называется верхней ценой игры в чистых стратегиях, а стратегия Yj0, которая максимизирует показатель неэффективности βj называется минимаксной стратегией игрока P2.
Теорема 3. Для элементов платежной матрицы имеют место неравенства:
и, следовательно, нижняя цена игры не больше ее верхней цены в чистых стратегиях:.
Пример . Найти решение игры, заданной платежной матрицей.
Решение:
Решим игру. Пусть – оптимальная стратегия первого игрока, – оптимальная стратегия второго игрока, v – цена игры.
Рассмотрим матрицу
min
max(-1,-2,4)=4=
max 6 7 4 10
min (6,7,5,10)=5=
— нижняя цена игры.
— верхняя цена игры.
— максиминная стратегия, — минимаксная стратегия
Если то элемент называется седловым элементом матрицы
A=
Теорема 4. (о разрешимости матричной игры в чистых стратегиях ) Если платежная матрица A имеет седловой элемент , то матричная игра имеет решение в чистых стратегиях, при этом оптимальной стратегий первого игрока является X i чистая стратегия, а для второго – Yj0 чистая стратегия, а цена игры v = .
Пример . Найти решение игры, заданной платежной матрицей A=
Решение:
Решим игру. Пусть -оптимальная стратегия первого игрока, — оптимальная стратегия второго игрока, v – цена игры.
Рассмотримматрицу
min
max 2 3
v ==2 цена игры v = 2, существует седловой элемент =, тогда решение в чистых стратегиях имеет вид:
оптимальная стратегия первого игрока:
оптимальная стратегия второго игрока:
Ответ: оптимальные стратегии игроков ; , цена игры v =2 .
4.Принцип доминированияРассмотрим игру с платежной матрицей
A=.
Если , то говорят, что j -ая строка доминируется i -ой строкой, при этом i -ая строка называется доминирующей для первого игрока P 1; j -ая строка – доминируемой строкой для P 1.
Если , то говорят, что i -ый столбец доминируется j -ым столбцом, при этом j -ый столбец называется доминирующим для второго игрока P 2; i -ый столбец – доминируемый для P 2. Доминируемую для игрока P 1 строку и доминируемый для P 2 столбец можно вычеркнуть (удалить).
Пример . Упростить платежную матрицу A=, используя принцип доминирования.
Решение.
1 способ: , т.к. — доминирующая строка, -
доминируемая строка (1)
2 способ:, (1)
5.Решение матричной игры 2×2 в смешанных стратегияхРешить игру с платежной матрицей
Платежная функция
Решить игру с платежной матрицей
Положим . Тогда
. Тогда
Если — оптимальная стратегия первого игрока, то по определению
решения матричной игры
Если игра с нулевой суммой, то (-цена игры).
Решая систему, получим .
Аналогично для второго игрока:
Тогда
Тогда
Если — оптимальная стратегия второго игрока.
Если игра с нулевой суммой, то (-цена игры).
Решая систему, получим .
Пример. Найти решение игры заданной платежной матрицей A= .
Решение:
Решим игру. Пусть — оптимальная стратегия первого игрока, — оптимальная стратегия второго игрока,-цена игры. Тогда оптимальные стратегии игроков и цену игры можно найти, решив системы:
Ответ: оптимальные стратегии игроков , цена игры .
Геометрическое решение игры 1.Решение игр с платежной матрицей 2×nРешить игру с платежной матрицей A=
Алгоритм:
1) Через концы горизонтального отрезка [0;1] провести два перпендикуляра к нему: левый и правый. Каждой точке отрезка [0;1] будем ставить некоторую смешанную стратегию (x;1− x).
2) На левом перпендикуляре от точки 0 отложить элементы . На правом перпендикуляре от точки 1 отложить элементы .
Замечание. Масштабы на левом и правом перпендикулярах должны быть
одинаковы, не обязательно совпадающие с масштабом горизонтального отрезка [0;1].
3) Соединить отрезками элементы .
4) Выделить нижнюю огибающую всех построенных отрезков, и найти максимальную точку (точки). Пусть точка является пересечением отрезков и . Тогда оптимальную стратегию можно найти при помощи матрицы .
Решить игру с платежной матрицей A=графически.
Решение:
1. Через концы горизонтального отрезка [0;1] проведем 2 перпендикуляра к нему. Каждой точке отрезка [0;1] будем ставить смешанную стратегию (x; 1− x ).
2. На левом перпендикуляре от точки 0 отложить элементы 2, 3, 11. На правом перпендикуляре от точки 1 отложить элементы 7, 5, 2.
3. Соединить отрезками элементы 2 и 7, 3 и 5, 11 и 2.
4. Выделим нижнюю огибающую всех построенных отрезков, и найдем
максимальную точку. Точка является пересечением отрезков [3;5] и [11;2]. Тогда оптимальную стратегию можно найти при помощи матрицы .
Решим игру с платежной матрицей .
Оптимальные стратегии игроков и цену игры можно найти, решив системы:
Ответ: оптимальные стратегии игроков оптимальные стратегии игроков , цена игры
2.Решение игр с платежной матрицей m ×2Решить игру с платежной матрицей A=.
Алгоритм :
1) Через концы горизонтального отрезка [0;1] провести два перпендикуляра к нему: левый и правый. Каждой точке отрезка [0;1] будем ставить некоторую смешанную стратегию (y;1− y).
2) На левом перпендикуляре от точки 0 отложить элементы . На правом перпендикуляре от точки 1 отложить элементы .
3) Соединить отрезками элементы .
4) Выделить верхнюю огибающую всех построенных отрезков, и найти минимальную точку (точки). Пусть точка является пересечением отрезков Тогда оптимальную стратегию можно найти при помощи матрицы .
Пример . Решить игру с платежной матрицей A=.
Решение:
Решим графическим методом.
1. Через концы горизонтального отрезка [0;1] проведем 2 перпендикуляра к нему. Каждой точке отрезка [0;1] будем ставить смешанную стратегию (y; 1− y).
2. На левом перпендикуляре от точки 0 отложить элементы 6, 4, 2, 1. На правом перпендикуляре от точки 1 отложить элементы 5, 6, 7, 8.
3. Соединить отрезками элементы 6 и 5, 4 и 6, 2 и 7, 1 и 8.
4. Выделим верхнюю огибающую всех построенных отрезков, и найдем минимальную точку. Точка является пересечением отрезков [6;5] и [1;8]. Тогда оптимальную стратегию можно найти при помощи матрицы .
Решим игру с платежной матрицей
Ответ: оптимальные стратегии игроков оптимальные стратегии игроков , цена игры
Практическая Часть
1. Решить Систему
1.1 По формулам Крамера
Решение.
1)Составим определитель из коэффициентов стоящих при неизвестных в системе.
2)Тогда по теореме Крамера:
3)Проверка:
Ответ:
1.2 Методом Гаусса
Решение.
1)Составим расширенную матрицу системы:
2)Преобразим расширенную матрицу к ступенчатому виду:
3)Расширенная приведена к расширенному виду. Получили следующую систему уравнений:
Ответ:
4. Решить транспортную задачу, заданную таблицей. Спланировать перевозки так, чтобы общая их стоимость была минимальной.
| Пункт отправления | В1 | В2 | В3 | B4 | В5 | Запасы, аi (тонн ) |
| А1 | 14 | 8 | 17 | 5 | 3 | 120 |
| А2 | 21 | 10 | 7 | 11 | 6 | 180 |
| А3 | 3 | 5 | 8 | 4 | 9 | 230 |
| Потребности, bj (тонн) | 70 | 120 | 105 | 125 | 110 | 530 |
5. Распределить а=100 единиц средств по четырём предприятиям с целью получения максимальной суммарной прибыли.
| x | g 1 | g 2 | g 3 | g 4 |
| 20 | 18 | 59 | 81 | 72 |
| 40 | 94 | 39 | 66 | 64 |
| 60 | 52 | 115 | 98 | 81 |
| 80 | 143 | 67 | 139 | 140 |
| 100 | 111 | 116 | 126 | 133 |
Решение.
1)Условная оптимизация.
1.1)Пусть k=4, тогда
| 20 | 40 | 60 | 80 | 100 | |||
| 20 | 72 | 72 | 20 | ||||
| 40 | 64 | 64 | 40 | ||||
| 60 | 81 | 81 | 60 | ||||
| 80 | 140 | 140 | 80 | ||||
| 100 | 133 | 133 | 100 |
1.2) Пусть k=3
| 20 | 40 | 60 | 80 | 100 | ||||
| 0+0 | ||||||||
| 20 | 0+72 | 81+0 | 81 | 20 | ||||
| 40 | 0+64 | 81+72 | 66+0 | 153 | 20 | |||
| 60 | 0+81 | 81+64 | 66+72 | 98+0 | 145 | 20 | ||
| 80 | 0+140 | 81+81 | 66+64 | 98+72 | 139+0 | 170 | 60 | |
| 100 | 0+133 | 81+140 | 66+81 | 98+64 | 139+72 | 126+0 | 221 | 20 |
1.3)Пусть k=2
| 20 | 40 | 60 | 80 | 100 | ||||
| 0+0 | ||||||||
| 20 | 0+81 | 59+0 | 81 | |||||
| 40 | 0+153 | 59+81 | 39+0 | 153 | ||||
| 60 | 0+145 | 59+153 | 39+81 | 115+0 | 212 | 20 | ||
| 80 | 0+170 | 59+145 | 39+153 | 115+81 | 67+0 | 204 | 20 | |
| 100 | 0+221 | 59+170 | 39+145 | 115+153 | 67+81 | 116+0 | 268 | 60 |
1.4)Пусть k=1
| 20 | 40 | 60 | 80 | 100 | ||||
| 0+0 | ||||||||
| 20 | 0+81 | 18+0 | 81 | |||||
| 40 | 0+153 | 18+81 | 94+0 | 153 | ||||
| 60 | 0+212 | 18+153 | 94+81 | 52+0 | 212 | |||
| 80 | 0+204 | 18+212 | 94+153 | 52+81 | 143+0 | 247 | 40 | |
| 100 | 0+268 | 18+204 | 94+212 | 52+153 | 143+81 | 111+0 | 306 | 40 |
2) Безусловная оптимизация
2.1)
Прибыль: 306
Так как
2.2)
2.3)
2.4)
Ответ:
Заключение
На основании проведенного исследования можно сделать следующие выводы:
· Теория игр является очень сложной областью знания. При обращении к ней надо соблюдать осторожность и четко знать границы применения.
· Теория игр пытается предсказать результат на основе интерактивных моделей, в которых решения каждой стороны влияют на решения других сторон.
· Смысл «игры» здесь является следующим: действие со стороны одного игрока приводит к действиям со стороны других.
· Теория игр полезна, когда требуется определить наиболее важные и требующие учета факторы в ситуации принятия решений в условиях конкурентной борьбы.
Графический метод является одним из основных методов решения задач теории игр. Главной особенностью этого метода является графической изображение задачи. Именно эта особенность и делает этот метод наиболее простым для восприятия человеком задачи, которую ему нужно решить.
Литература
1.Просветов Г. И. Математические методы в экономике: Учебно-методическое
пособие. – М.: Изд-во РДЛ, 2004.
2. Бережная Е. В., Бережной В. И. Математические методы моделирования
экономических систем: Учеб пособие. – М.: Финансы и статистика, 2003.
3. Экономико-математическое моделирование. / Под ред. И. Н. Дрогобыцкого. –
М.: Изд-во «Экзамен», 2004.
4. Гончарова Г. А., Молчалин А. А. Элементы дискретной математики: Учебное
пособие. – М.: ФОРУМ: ИНФРА-М, 2004.
5. Высшая математика для экономистов: Учебник / Под ред Н. Ш. Кремера –
М.: ЮНИТИ, 2002.
www.ronl.ru
Вряд ли можно найти человека, которому удалось в жизни сыграть во все игры, которые есть на свете,- их множество. У каждой свои правила, свои особенности. Хоккей, например, отличается от футбола, домино — от шахмат, шашки — от «крестиков-ноликов», «морской бой» — от игры в слова и т. д. И все-таки совершенно непохожие игры принципиально — в главном совершенно одинаковы. В чем их одинаковость? В столкновении интересов. Вася и Петя играют в шахматы. Каждому во что бы то ни стало, хочется выиграть.
На футбольном поле встречаются две команды. Кто-то из них должен стать победителем. Одна, безусловно, приложит к этому все силы. И вторая полона решимости победить. Столкновение интересов бывает не только в играх. Оно случается часто, намного чаще, чем мы предполагаем. Проследите под этим углом зрения один из своих обычных дней. Сколько раз сталкивались ваши интересы с чьими-либо! В повседневной жизни, в практической деятельности очень часто встречаются ситуации, когда разные люди проявляют разные интересы и располагают разными путями в достижении разных целей. Иными словами, всем нам часто приходится сталкиваться с конфликтными ситуациями.
Такие ситуации, возникающие при игре в шахматы, шашки, домино и т. д. Результат каждого хода игрока зависит от ответного хода противника, цель игры — выигрыш одного из партнёров. В экономике конфликтные ситуации встречаются очень часто и имеют многообразный характер. К ним относятся, например, взаимоотношения между поставщиком и потребителем, покупателем и продавцом, банком и клиентом. Во всех этих примерах конфликтная ситуация порождается различием интересов партнёров и стремлением каждого из них принимать оптимальные решения, которые реализуют поставленные цели в наибольшей степени. При этом каждому приходится считаться не только со своими целями, но и с целями партнёра, и учитывать неизвестные заранее решения, которые эти партнёры будут принимать.
Для грамотного решения задач с конфликтными ситуациями необходимы научно обоснованные методы. Такие методы разработаны математической теорией конфликтных ситуаций, которая носит название теория игр.
Теория игр — математическая дисциплина, устанавливающая количественные закономерности в конфликтных и неопределенных ситуациях. |
Теория игр была разработана Дж. фон Нейманном и О. Моргенштерном в 1944 г., ее дальнейшую разработку продолжил Дж. Нэш.
Ознакомимся с основными понятиями теории игр. Математическая модель конфликтной ситуации называется игрой, стороны, участвующие в конфликте, — игроками, а исход конфликта — выигрышем. Для каждой формализованной игры вводятся правила, т.е. система условий, определяющая: 1) варианты действий игроков; 2) объём информации каждого игрока о поведении партнёров; 3) выигрыш, к которому приводит каждая совокупность действий. Как правило, выигрыш (или проигрыш) может быть задан количественно; например, можно оценить проигрыш нулём, выигрыш — единицей, а ничью — ?..
Игра называется парной, если в ней участвуют два игрока, и множественной, если число игроков больше двух. Мы будем рассматривать только парные игры. В них участвуют два игрока А и В, интересы которых противоположны, а под игрой будем понимать ряд действий со стороны А и В.
В теории игр смысл терминов несколько иной. В теории игр игроком могут быть и несколько человек с определенным интересом, которые борются против одного или, наоборот, против большого количества противников, которые тоже признаны игроком. Значит, игрок — это просто одна группа интересов. Футбольный матч с точки зрения теории игр будет просчитываться как один игрок против одного. В этом смысле он не отличается от шахматной партии. Выдающийся французский математик Луи Борель еще в начале XX века предпринял издание большого, многотомного «Курса теории вероятностей и ее приложений». Предпоследний том был посвящен «Приложениям к азартным играм». Ученый подвел в нем итог своим длительным исследованиям азартных игр, которыми он интересовался как математик. В теорию игр Борель внес смелые и оригинальные идеи. Он попытался найти математическую формулировку игр, когда течение игры зависело от умения игроков. Со временем многие ученые развили теорию. Она стала гораздо шире теории азартных игр. Оказывается, игры бывают антагонистические и неантагонистические, бабочкообразные и вогнуто-выгнутые, бескоалиционные и кооперативные, позиционные и динамические, и даже игры с «линией жизни», и игра с преследованием с ограниченным временем. Есть в теории игр и «общая теория полезности», и еще много других интересных и необходимых для решения важных практических задач.
Игра называется игрой с нулевой суммой, или антагонистической, если выигрыш одного из игроков равен проигрышу другого, т. е. для полного задания игры достаточно указать величину одного из них.
Выбор и осуществление одного из предусмотренных правилами действий называется ходом игрока. Ходы могут быть личными и случайными. Личный ход — это сознательный выбор игроком одного из возможных действий (например, ход в шахматной игре). Случайный ход — это случайно выбранное действие (например, выбор карты из перетасованной колоды).
Стратегией игрока называется совокупность правил, определяющих выбор его действия при каждом личном ходе в зависимости от сложившейся ситуации. Обычно в процессе игры при каждом личном ходе игрок делает выбор в зависимости от конкретной ситуации. Однако в принципе возможно, что все решения приняты игроком заранее (в ответ на любую сложившуюся ситуацию). Это означает, что игрок выбрал определённую стратегию, которая может быть задана в виде списка правил или программы. (Так можно осуществить игру с помощью ЭВМ). Игра называется конечной, если у каждого игрока имеется конечное число стратегий, и бесконечной — в противном случае.
А теперь познакомимся со скандальной историей, случившейся в одном из игорных домов Европы.… Сначала на них никто не обращал внимания. Молодые люди заходили в казино поглядеть на игру в рулетку, останавливались возле игорных столов и записывали в блокноты номера выигрышей, то есть номера чисел на диске рулетки, против которых останавливался шарик. «Просто так, любопытства ради»,- отвечали они тому, кто их спрашивал: «Зачем?». А спустя два месяца в Монте-Карло, в столице игорных домов, разразилась гроза. Снова пришли те молодые люди. Но теперь они ничего не записывали, а стали играть. И выигрывали, как говорят математики, «в достаточно длинных партиях». Журналисты захотели найти объяснение, и считают, что нашли. Оказывается, молодые люди не ради любопытства записывали номера выигрышей. Мало того, они еще их и закодировали. И после этого переслали в Лондон своему компаньону. Тот обработал их с помощью электронной вычислительной машины. В «американском случае» машинное руководство к действию (алгоритм поиска вариантов) было составлено так, чтобы изыскивать повышение вероятностей благоприятного исхода. Именно с этой целью перебирала машина горы чисел, строя свою игру против вымышленного противника по законам теории игр. Право же, не стоило создавать целое направление в математике, чтобы помогать выигрывать в азартные игры! Конечно, теория игр создана не для этого Модели игр служат тем инструментом, с помощью которого теория игр пытается проверить серьезные задачи. С помощью теории игр стремятся выработать целесообразную линию поведения для многих и многих систем, ведущих борьбу против другой системы.
Например, теорию игр можно применить к задачам связи, к вопросам технологии медицины, нефтедобычи, спорта, рыболовства, к противовоздушной обороне, к задачам, которые приходится решать командиру в сражении. Под углом зрения теории игр можно рассматривать и работу экспериментатора, который составляет план экспериментов. Их можно рассматривать как игру, где противниками выступают ученый и нервная система животного, которую он изучает. Есть игры, в которых прорабатываются сложные ситуации, растянутые во времени. Для них готовят специальное математическое обеспечение, им нужна достаточно мощная база вычислительных машин. Ведь для исследования даже самой простой производственно-хозяйственной ситуации бывает необходимым провести большое количество вычислений. В большинстве случаев в играх приходится иметь дело с цифрами: проделывать головокружительное количество вычислений. Не случайно, значит, учат машину играть в разные игры: в домино, в шашки, в шахматы. Шахматы, дающие астрономическое число вариантов партий -2*10116 — открывают большой простор для исследований.
Теория игр имеет большое значение в экономическом анализе. В последние годы значение теории игр существенно возросло во многих областях экономических и социальных наук. С помощью теории игр предприятие получает возможность предусмотреть ходы своих партнеров и конкурентов.
Эта теория рассматривает поведение фирм на рынке как игру, причем имеются определенные правила игры, по результатам которой начисляются «призы» и «штрафы». Участники игры определенно не знают стратегию конкурента, поэтому их поведение основано лишь на прогнозах.
Например, рассмотрим стратегию фирм А и В (табл. 4) с понижением цены. Если обе фирмы не понижают цену, прибыль каждой составит, например, 60 млн усл. ед. Если одна из фирм понижает цену, она получает конкурентное преимущество и увеличивает прибыль до 85 млн усл. ед. В это время конкурент терпит убыток в размере 25 млн усл. ед. Если же обе фирмы в сговоре проводят политику снижения цены, прибыль каждого составит по 12,5 млн усл. ед. Необходимо определить, как поступить фирмам А и В, чтобы не проиграть.
Аналогом данной ситуации на рынке служит другая игра — так называемая «дилемма заключенного». Суть этой игры в следующем: два узника содержатся в отдельных камерах и обвиняются по одному делу (табл. 5).
У обвинения достаточно улик, чтобы осудить узников только на два года. Узникам сообщили (каждому отдельно), что если один сознается, а другой нет, то сознавшийся будет свободен, а не сознавшийся получит 20 лет. Если сознаются оба, то каждый получит по 10 лет. Необходимо определить, каким будет поведение заключенного, когда реакция другого неизвестна.
В этом случае различают две стратегии поведения, называемые maximin и maximax:
1. min — это стратегия пессимиста.
2. max — это стратегия оптимиста.
Пессимист будет искать наилучший вариант из наихудших результатов. Это ситуация, когда, например, узник А ждет, что узник В признается, и тогда А получит 20 лет заключения, при условии, что он не сознается. Чтобы обеспечить себе наименее плохой результат из всех плохих вариантов, узник А решает сознаться, поскольку это позволит ему получить 10 лет заключения, а не 20. Этот результат лучше, чем 20 лет заключения.
Аналогично будет рассуждать и узник В. В результате, не сговариваясь, оба узника придут к решению сознаться и получат по 10 лет тюрьмы.
Оптимист надеется на самый лучший вариант решения вопроса. Узник А думает, что узник В не сознается, поэтому он решает сознаться. Но узник В также оптимист и поступает аналогичным образом. В результате, не сговариваясь, оба заключенных придут к решению сознаться и получат по 10 лет тюрьмы.
Стратегии min и max привели узников к одному результату — это и есть решение Нэша.
Подобного рода решение примут фирмы А и В на конкурентном рынке. В обоих случаях фирмы А и В решают снижать цены, и стратеги min и max приведут их к решению Нэша, т. е. понижать цены, что даст им равные прибыли — по 12,5 млн усл. ед, каждой фирме.
Заключение
«Есть в современной математике одна область, она носит безобидное название теории игр, но ей, несомненно, суждено сыграть очень важную роль в человековедении самого ближайшего будущего, — говорил Джон фон Нейман, один из основоположников кибернетики.- Она занимается вопросами оптимального поведения людей при наличии противодействующего противника. Для ученого противник — это природа со всеми ее явлениями; экспериментатор борется со средой; математик — с загадками математического мира; инженер — с сопротивлением материалов».
www.ronl.ru
Челябинский юридический колледж
Кафедра математических и естественнонаучных дисциплинКУРСОВАЯ РАБОТА
по дисциплине «Математические методы»
Теория игр. Графический метод решения теории игр
Работу выполнила студентка гр. ПО-001-06 | А.В. Егорова |
| Руководитель | Н.Р. Хабибуллина |
Челябинск
2009
Содержание
1. Введение 2. Основные методы решений 2.1.Основные понятия теории игр 2.2.Матричные игры 2.3.Решение матричной игры в чистых стратегиях 2.4.Принцип доминирования 2.5.Решение матричной игры 2×2 в смешанных стратегиях 3. Геометрическое решение игры 3.1.Решение игр с платежной матрицей 2×n 3.2.Решение игр с платежной матрицей m ×24. Практическая часть 5. Заключение 6. Список литературы | 3 4 5 7 11 12 15 18 |
Введение
Непрерывное и последовательное развитие социалистического общества, его производительных сил и производительных отношений, повышение эффективности общественного производства непрерывно связанно с совершенствование системы планирования и управления. Современные достижения науки и техники все шире используются в практике для получения научно обоснованных наиболее эффективных решений в сфере планирования и управления.
При решении ряда практических задач (в разных областях деятельности) приходится анализировать ситуации, где налицо две ( или более) враждующие стороны, преследующие противоположные цели, причем результат каждого мероприятия одной из сторон зависит от того, какой образ действия выберет противник.
Необходимость анализировать подобные ситуации вызвала к жизни специальные математический аппарат. Теория игр по существу представляет собой не что иное, как математическую теорию конфликтных ситуаций.
Целью данной работы является рассмотрение не только теории игр в общем, но и ее графический метод решения.
Для наиболее оптимального изучения и рассмотрения поставлены следующие задачи:
1. Кратко изложить понятие о теории игр в целом;
2. Рассмотреть основные методы решений задач теории игр;
3. Детально изучить графический метод решения задач теории игр.
4. Привести примеры задач, решенных с помощью этого метода..
Основные методы решений 1.Основные понятия теории игрМногие социально-экономические ситуации, в которых рассматриваются вопросы о выборе решения, обладают тем свойством, что в них сталкиваются не мнение двух сторон с различными интересами, каждая из которых для достижения своей цели имеет возможность действовать различными способами,
выбор которых при некоторых условиях может осуществляться в зависимости от
действий противоборствующей стороны. Такие ситуации называют конфликтными .
Математическая модель конфликтной ситуации называется игрой. Теория игр занимается математическими моделями принятия оптимальных решений в условиях конфликта. Любое возможное в игре действие игрока называется его стратегией. Игра называется конечной, если множество стратегий каждого игрока конечно. В противном случае (т.е. когда множество стратегий хотя бы одного игрока бесконечно), игра называется бесконечной. В дальнейшем будем рассматривать только конечные игры двух лиц .
Основной целью теории игр является выявление для каждого из игроков «оптимальных стратегий».
Оптимальной называется стратегия, которая при многократно повторяющейся игре гарантирует игроку максимально возможный средний выигрыш (или, эквивалентно, минимально возможный средний проигрыш).Выбор оптимальной стратегии базируется на принципе, предполагающем, что обаигрока разумны в одинаковой степени и поведение каждого из них направлено напротиводействие противнику в достижении его цели. Таким образом, теория играбстрагируется от ошибок, просчетов, азарта и риска, присущих игрокам, реальных конфликтах.
Будем считать, что выигрыш одного игрока равен в точности проигрышу
второго игрока, такая игра называется игрой с нулевой суммой. Конечная игра двух игроков с ненулевой суммой, в которой выигрыши каждого игрока задаются матрицами отдельно для соответствующего игрока, называется биматричной игрой .
2.Матричные игрыМатричной игрой называется конечная игра двух игроков с нулевой
суммой, в которой задается выигрыш игрока 1 в виде матрицы, строка матрицы
соответствует номеру применяемой стратегии игрока 1, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы
находится выигрыш игрока 1, соответствующий применяемым стратегиям.
Пусть играют 2 игрока P1 и P2. Матрица
элементы aij – выигрыш игрока P1, если P1 – выбирает i строку, а P2 – выбирает j столбец, называется платежной матрицей игры .
Пусть игрок P1 выбирает i строку с вероятностью xi, P2 выбирает j столбец с
вероятностью yj, тогда и будут называться соответственно смешанными стратегиями 1-ого и 2-ого игроков .
Замечание: так как компонентами смешанных стратегий X и Y являются
вероятности, то и . Если среди компонентов смешанной стратегии X только одна 1, остальные 0, то стратегия называется чистой .
— i -ая чистая стратегия. Любую смешанную стратегию можно представить в виде выпуклой комбинации чистых стратегий, т.е.
Пример . Представить смешанную стратегию в виде выпуклой
комбинации чистых стратегий.
Решение.
Платежной функцией (X ,Y ) первого игрока называется математическое
ожидание его выигрыша, т.е.
(X ,Y )=
Решением матричной игры называют пару смешанных стратегий и
число v называемое ценой игры, удовлетворяющих следующим условиям:
1)
Если P1 придерживается своей оптимальной стратегии X *, то какую бы
чистую стратегию не принимал второй игрок P2, P1 получит выигрыш не меньше чем цена игры v .
2)
Если P2 придерживается своей оптимальной стратегии Y *, то какую бы чистую стратегию не применял второй игрок P1, то P2 проиграет не более чем цена игры v .
Теорема 1. Если игрок P1 придерживается своей оптимальной стратегии X *,
а P2 придерживается своей оптимальной стратегии Y *, то.
Теорема 2. Любая матричная игра имеет решение в смешанных стратегиях.
3.Решение матричной игры в чистых стратегияхРассмотрим матричную игру с игроками P1 и P2 и платежной матрицей
1) Перед игроком P1 стоит задача выбора чистой стратегии, в результате применения которой он получит максимально возможный гарантированный
выигрыш. Если игрок P1 выбрал стратегию , то его выигрышем может быть один из выигрышей , расположенный в i-ой строке платежной
матрицы, в зависимости от выбранной стратегии игроком P2. Предполагая поведение игрока P1 крайне осмысленным, необходимо считать, что игрок P2 сыграет наилучшим для себя образом и на выбор игроком P1 стратегии Xi выберет ту стратегию Yj, при которой выигрыш игрока P1 окажется минимальным.
Обозначим минимальный среди выигрышей через αi:
, (αi –показатель эффективности стратегии Xi ).
Продолжая действовать разумно, игрок P1 должен выбрать ту стратегию,
которая максимизирует показатель эффективности, т.е. для которой число αi максимально.
Обозначим:
Число α называется нижней ценой игры в чистых стратегиях, а стратегия
Xi0, которая максимизирует показатель эффективности αi называется максиминной стратегией игрока P1.
Таким образом, если игрок P1 в игре будет следовать максиминной стратегии, то ему при любой игре противника P2 гарантирован выигрыш в чистых стратегиях, не меньший α .
2) Рассмотрим игру с точки зрения игрока P2, который стремиться минимизировать выигрыш игрока P1. Если P2 выберет стратегию , то выигрышем игрока P1 может быть один из выигрышей . Но так как игрок P2 предполагает, что игрок P1 играет наилучшим для себя образом, то выигрышем игрока P1 будет максимальное из этих чисел, обозначим βj:
(βj –показатель неэффективности стратегии Yj ).
Таким образом, для любой стратегии Yj игрока P2 наибольший его проигрыш равен βj. В интересах игрока P2 выбрать стратегию с минимальным показателем неэффективности. Наименьшее из чисел βj обозначим β :
Число β называется верхней ценой игры в чистых стратегиях, а стратегия Yj0, которая максимизирует показатель неэффективности βj называется минимаксной стратегией игрока P2.
Теорема 3. Для элементов платежной матрицы имеют место неравенства:
и, следовательно, нижняя цена игры не больше ее верхней цены в чистых стратегиях:.
Пример . Найти решение игры, заданной платежной матрицей.
Решение:
Решим игру. Пусть – оптимальная стратегия первого игрока, – оптимальная стратегия второго игрока, v – цена игры.
Рассмотрим матрицу
min
max(-1,-2,4)=4=
max 6 7 4 10
min (6,7,5,10)=5=
— нижняя цена игры.
— верхняя цена игры.
— максиминная стратегия, — минимаксная стратегия
Если то элемент называется седловым элементом матрицы
A=
Теорема 4. (о разрешимости матричной игры в чистых стратегиях ) Если платежная матрица A имеет седловой элемент , то матричная игра имеет решение в чистых стратегиях, при этом оптимальной стратегий первого игрока является X i чистая стратегия, а для второго – Yj0 чистая стратегия, а цена игры v = .
Пример . Найти решение игры, заданной платежной матрицей A=
Решение:
Решим игру. Пусть -оптимальная стратегия первого игрока, — оптимальная стратегия второго игрока, v – цена игры.
Рассмотримматрицу
min
max 2 3
v ==2 цена игры v = 2, существует седловой элемент =, тогда решение в чистых стратегиях имеет вид:
оптимальная стратегия первого игрока:
оптимальная стратегия второго игрока:
Ответ: оптимальные стратегии игроков ; , цена игры v =2 .
4.Принцип доминированияРассмотрим игру с платежной матрицей
A=.
Если , то говорят, что j -ая строка доминируется i -ой строкой, при этом i -ая строка называется доминирующей для первого игрока P 1; j -ая строка – доминируемой строкой для P 1.
Если , то говорят, что i -ый столбец доминируется j -ым столбцом, при этом j -ый столбец называется доминирующим для второго игрока P 2; i -ый столбец – доминируемый для P 2. Доминируемую для игрока P 1 строку и доминируемый для P 2 столбец можно вычеркнуть (удалить).
Пример . Упростить платежную матрицу A=, используя принцип доминирования.
Решение.
1 способ: , т.к. — доминирующая строка, -
доминируемая строка (1)
2 способ:, (1)
5.Решение матричной игры 2×2 в смешанных стратегияхРешить игру с платежной матрицей
Платежная функция
Решить игру с платежной матрицей
Положим . Тогда
. Тогда
Если — оптимальная стратегия первого игрока, то по определению
решения матричной игры
Если игра с нулевой суммой, то (-цена игры).
Решая систему, получим .
Аналогично для второго игрока:
Тогда
Тогда
Если — оптимальная стратегия второго игрока.
Если игра с нулевой суммой, то (-цена игры).
Решая систему, получим .
Пример. Найти решение игры заданной платежной матрицей A= .
Решение:
Решим игру. Пусть — оптимальная стратегия первого игрока, — оптимальная стратегия второго игрока,-цена игры. Тогда оптимальные стратегии игроков и цену игры можно найти, решив системы:
Ответ: оптимальные стратегии игроков , цена игры .
Геометрическое решение игры 1.Решение игр с платежной матрицей 2×nРешить игру с платежной матрицей A=
Алгоритм:
1) Через концы горизонтального отрезка [0;1] провести два перпендикуляра к нему: левый и правый. Каждой точке отрезка [0;1] будем ставить некоторую смешанную стратегию (x;1− x).
2) На левом перпендикуляре от точки 0 отложить элементы . На правом перпендикуляре от точки 1 отложить элементы .
Замечание. Масштабы на левом и правом перпендикулярах должны быть
одинаковы, не обязательно совпадающие с масштабом горизонтального отрезка [0;1].
3) Соединить отрезками элементы .
4) Выделить нижнюю огибающую всех построенных отрезков, и найти максимальную точку (точки). Пусть точка является пересечением отрезков и . Тогда оптимальную стратегию можно найти при помощи матрицы .
Решить игру с платежной матрицей A=графически.
Решение:
1. Через концы горизонтального отрезка [0;1] проведем 2 перпендикуляра к нему. Каждой точке отрезка [0;1] будем ставить смешанную стратегию (x; 1− x ).
2. На левом перпендикуляре от точки 0 отложить элементы 2, 3, 11. На правом перпендикуляре от точки 1 отложить элементы 7, 5, 2.
3. Соединить отрезками элементы 2 и 7, 3 и 5, 11 и 2.
4. Выделим нижнюю огибающую всех построенных отрезков, и найдем
максимальную точку. Точка является пересечением отрезков [3;5] и [11;2]. Тогда оптимальную стратегию можно найти при помощи матрицы .
Решим игру с платежной матрицей .
Оптимальные стратегии игроков и цену игры можно найти, решив системы:
Ответ: оптимальные стратегии игроков оптимальные стратегии игроков , цена игры
2.Решение игр с платежной матрицей m ×2Решить игру с платежной матрицей A=.
Алгоритм :
1) Через концы горизонтального отрезка [0;1] провести два перпендикуляра к нему: левый и правый. Каждой точке отрезка [0;1] будем ставить некоторую смешанную стратегию (y;1− y).
2) На левом перпендикуляре от точки 0 отложить элементы . На правом перпендикуляре от точки 1 отложить элементы .
3) Соединить отрезками элементы .
4) Выделить верхнюю огибающую всех построенных отрезков, и найти минимальную точку (точки). Пусть точка является пересечением отрезков Тогда оптимальную стратегию можно найти при помощи матрицы .
Пример . Решить игру с платежной матрицей A=.
Решение:
Решим графическим методом.
1. Через концы горизонтального отрезка [0;1] проведем 2 перпендикуляра к нему. Каждой точке отрезка [0;1] будем ставить смешанную стратегию (y; 1− y).
2. На левом перпендикуляре от точки 0 отложить элементы 6, 4, 2, 1. На правом перпендикуляре от точки 1 отложить элементы 5, 6, 7, 8.
3. Соединить отрезками элементы 6 и 5, 4 и 6, 2 и 7, 1 и 8.
4. Выделим верхнюю огибающую всех построенных отрезков, и найдем минимальную точку. Точка является пересечением отрезков [6;5] и [1;8]. Тогда оптимальную стратегию можно найти при помощи матрицы .
Решим игру с платежной матрицей
Ответ: оптимальные стратегии игроков оптимальные стратегии игроков , цена игры
Практическая Часть
1. Решить Систему
1.1 По формулам Крамера
Решение.
1)Составим определитель из коэффициентов стоящих при неизвестных в системе.
2)Тогда по теореме Крамера:
3)Проверка:
Ответ:
1.2 Методом Гаусса
Решение.
1)Составим расширенную матрицу системы:
2)Преобразим расширенную матрицу к ступенчатому виду:
3)Расширенная приведена к расширенному виду. Получили следующую систему уравнений:
Ответ:
4. Решить транспортную задачу, заданную таблицей. Спланировать перевозки так, чтобы общая их стоимость была минимальной.
| Пункт отправления | В1 | В2 | В3 | B4 | В5 | Запасы, аi (тонн ) |
| А1 | 14 | 8 | 17 | 5 | 3 | 120 |
| А2 | 21 | 10 | 7 | 11 | 6 | 180 |
| А3 | 3 | 5 | 8 | 4 | 9 | 230 |
| Потребности, bj (тонн) | 70 | 120 | 105 | 125 | 110 | 530 |
5. Распределить а=100 единиц средств по четырём предприятиям с целью получения максимальной суммарной прибыли.
| x | g 1 | g 2 | g 3 | g 4 |
| 20 | 18 | 59 | 81 | 72 |
| 40 | 94 | 39 | 66 | 64 |
| 60 | 52 | 115 | 98 | 81 |
| 80 | 143 | 67 | 139 | 140 |
| 100 | 111 | 116 | 126 | 133 |
Решение.
1)Условная оптимизация.
1.1)Пусть k=4, тогда
| 20 | 40 | 60 | 80 | 100 | |||
| 20 | 72 | 72 | 20 | ||||
| 40 | 64 | 64 | 40 | ||||
| 60 | 81 | 81 | 60 | ||||
| 80 | 140 | 140 | 80 | ||||
| 100 | 133 | 133 | 100 |
1.2) Пусть k=3
| 20 | 40 | 60 | 80 | 100 | ||||
| 0+0 | ||||||||
| 20 | 0+72 | 81+0 | 81 | 20 | ||||
| 40 | 0+64 | 81+72 | 66+0 | 153 | 20 | |||
| 60 | 0+81 | 81+64 | 66+72 | 98+0 | 145 | 20 | ||
| 80 | 0+140 | 81+81 | 66+64 | 98+72 | 139+0 | 170 | 60 | |
| 100 | 0+133 | 81+140 | 66+81 | 98+64 | 139+72 | 126+0 | 221 | 20 |
1.3)Пусть k=2
| 20 | 40 | 60 | 80 | 100 | ||||
| 0+0 | ||||||||
| 20 | 0+81 | 59+0 | 81 | |||||
| 40 | 0+153 | 59+81 | 39+0 | 153 | ||||
| 60 | 0+145 | 59+153 | 39+81 | 115+0 | 212 | 20 | ||
| 80 | 0+170 | 59+145 | 39+153 | 115+81 | 67+0 | 204 | 20 | |
| 100 | 0+221 | 59+170 | 39+145 | 115+153 | 67+81 | 116+0 | 268 | 60 |
1.4)Пусть k=1
| 20 | 40 | 60 | 80 | 100 | ||||
| 0+0 | ||||||||
| 20 | 0+81 | 18+0 | 81 | |||||
| 40 | 0+153 | 18+81 | 94+0 | 153 | ||||
| 60 | 0+212 | 18+153 | 94+81 | 52+0 | 212 | |||
| 80 | 0+204 | 18+212 | 94+153 | 52+81 | 143+0 | 247 | 40 | |
| 100 | 0+268 | 18+204 | 94+212 | 52+153 | 143+81 | 111+0 | 306 | 40 |
2) Безусловная оптимизация
2.1)
Прибыль: 306
Так как
2.2)
2.3)
2.4)
Ответ:
Заключение
На основании проведенного исследования можно сделать следующие выводы:
· Теория игр является очень сложной областью знания. При обращении к ней надо соблюдать осторожность и четко знать границы применения.
· Теория игр пытается предсказать результат на основе интерактивных моделей, в которых решения каждой стороны влияют на решения других сторон.
· Смысл «игры» здесь является следующим: действие со стороны одного игрока приводит к действиям со стороны других.
· Теория игр полезна, когда требуется определить наиболее важные и требующие учета факторы в ситуации принятия решений в условиях конкурентной борьбы.
Графический метод является одним из основных методов решения задач теории игр. Главной особенностью этого метода является графической изображение задачи. Именно эта особенность и делает этот метод наиболее простым для восприятия человеком задачи, которую ему нужно решить.
Литература
1.Просветов Г. И. Математические методы в экономике: Учебно-методическое
пособие. – М.: Изд-во РДЛ, 2004.
2. Бережная Е. В., Бережной В. И. Математические методы моделирования
экономических систем: Учеб пособие. – М.: Финансы и статистика, 2003.
3. Экономико-математическое моделирование. / Под ред. И. Н. Дрогобыцкого. –
М.: Изд-во «Экзамен», 2004.
4. Гончарова Г. А., Молчалин А. А. Элементы дискретной математики: Учебное
пособие. – М.: ФОРУМ: ИНФРА-М, 2004.
5. Высшая математика для экономистов: Учебник / Под ред Н. Ш. Кремера –
М.: ЮНИТИ, 2002.
www.ronl.ru
Вряд ли можно найти человека, которому удалось в жизни сыграть во все игры, которые есть на свете,- их множество. У каждой свои правила, свои особенности. Хоккей, например, отличается от футбола, домино — от шахмат, шашки — от «крестиков-ноликов», «морской бой» — от игры в слова и т. д. И все-таки совершенно непохожие игры принципиально — в главном совершенно одинаковы. В чем их одинаковость? В столкновении интересов. Вася и Петя играют в шахматы. Каждому во что бы то ни стало, хочется выиграть.
На футбольном поле встречаются две команды. Кто-то из них должен стать победителем. Одна, безусловно, приложит к этому все силы. И вторая полона решимости победить. Столкновение интересов бывает не только в играх. Оно случается часто, намного чаще, чем мы предполагаем. Проследите под этим углом зрения один из своих обычных дней. Сколько раз сталкивались ваши интересы с чьими-либо! В повседневной жизни, в практической деятельности очень часто встречаются ситуации, когда разные люди проявляют разные интересы и располагают разными путями в достижении разных целей. Иными словами, всем нам часто приходится сталкиваться с конфликтными ситуациями.
Такие ситуации, возникающие при игре в шахматы, шашки, домино и т. д. Результат каждого хода игрока зависит от ответного хода противника, цель игры — выигрыш одного из партнёров. В экономике конфликтные ситуации встречаются очень часто и имеют многообразный характер. К ним относятся, например, взаимоотношения между поставщиком и потребителем, покупателем и продавцом, банком и клиентом. Во всех этих примерах конфликтная ситуация порождается различием интересов партнёров и стремлением каждого из них принимать оптимальные решения, которые реализуют поставленные цели в наибольшей степени. При этом каждому приходится считаться не только со своими целями, но и с целями партнёра, и учитывать неизвестные заранее решения, которые эти партнёры будут принимать.
Для грамотного решения задач с конфликтными ситуациями необходимы научно обоснованные методы. Такие методы разработаны математической теорией конфликтных ситуаций, которая носит название теория игр.
Теория игр — математическая дисциплина, устанавливающая количественные закономерности в конфликтных и неопределенных ситуациях. |
Теория игр была разработана Дж. фон Нейманном и О. Моргенштерном в 1944 г., ее дальнейшую разработку продолжил Дж. Нэш.
Ознакомимся с основными понятиями теории игр. Математическая модель конфликтной ситуации называется игрой, стороны, участвующие в конфликте, — игроками, а исход конфликта — выигрышем. Для каждой формализованной игры вводятся правила, т.е. система условий, определяющая: 1) варианты действий игроков; 2) объём информации каждого игрока о поведении партнёров; 3) выигрыш, к которому приводит каждая совокупность действий. Как правило, выигрыш (или проигрыш) может быть задан количественно; например, можно оценить проигрыш нулём, выигрыш — единицей, а ничью — ?..
Игра называется парной, если в ней участвуют два игрока, и множественной, если число игроков больше двух. Мы будем рассматривать только парные игры. В них участвуют два игрока А и В, интересы которых противоположны, а под игрой будем понимать ряд действий со стороны А и В.
В теории игр смысл терминов несколько иной. В теории игр игроком могут быть и несколько человек с определенным интересом, которые борются против одного или, наоборот, против большого количества противников, которые тоже признаны игроком. Значит, игрок — это просто одна группа интересов. Футбольный матч с точки зрения теории игр будет просчитываться как один игрок против одного. В этом смысле он не отличается от шахматной партии. Выдающийся французский математик Луи Борель еще в начале XX века предпринял издание большого, многотомного «Курса теории вероятностей и ее приложений». Предпоследний том был посвящен «Приложениям к азартным играм». Ученый подвел в нем итог своим длительным исследованиям азартных игр, которыми он интересовался как математик. В теорию игр Борель внес смелые и оригинальные идеи. Он попытался найти математическую формулировку игр, когда течение игры зависело от умения игроков. Со временем многие ученые развили теорию. Она стала гораздо шире теории азартных игр. Оказывается, игры бывают антагонистические и неантагонистические, бабочкообразные и вогнуто-выгнутые, бескоалиционные и кооперативные, позиционные и динамические, и даже игры с «линией жизни», и игра с преследованием с ограниченным временем. Есть в теории игр и «общая теория полезности», и еще много других интересных и необходимых для решения важных практических задач.
Игра называется игрой с нулевой суммой, или антагонистической, если выигрыш одного из игроков равен проигрышу другого, т. е. для полного задания игры достаточно указать величину одного из них.
Выбор и осуществление одного из предусмотренных правилами действий называется ходом игрока. Ходы могут быть личными и случайными. Личный ход — это сознательный выбор игроком одного из возможных действий (например, ход в шахматной игре). Случайный ход — это случайно выбранное действие (например, выбор карты из перетасованной колоды).
Стратегией игрока называется совокупность правил, определяющих выбор его действия при каждом личном ходе в зависимости от сложившейся ситуации. Обычно в процессе игры при каждом личном ходе игрок делает выбор в зависимости от конкретной ситуации. Однако в принципе возможно, что все решения приняты игроком заранее (в ответ на любую сложившуюся ситуацию). Это означает, что игрок выбрал определённую стратегию, которая может быть задана в виде списка правил или программы. (Так можно осуществить игру с помощью ЭВМ). Игра называется конечной, если у каждого игрока имеется конечное число стратегий, и бесконечной — в противном случае.
А теперь познакомимся со скандальной историей, случившейся в одном из игорных домов Европы.… Сначала на них никто не обращал внимания. Молодые люди заходили в казино поглядеть на игру в рулетку, останавливались возле игорных столов и записывали в блокноты номера выигрышей, то есть номера чисел на диске рулетки, против которых останавливался шарик. «Просто так, любопытства ради»,- отвечали они тому, кто их спрашивал: «Зачем?». А спустя два месяца в Монте-Карло, в столице игорных домов, разразилась гроза. Снова пришли те молодые люди. Но теперь они ничего не записывали, а стали играть. И выигрывали, как говорят математики, «в достаточно длинных партиях». Журналисты захотели найти объяснение, и считают, что нашли. Оказывается, молодые люди не ради любопытства записывали номера выигрышей. Мало того, они еще их и закодировали. И после этого переслали в Лондон своему компаньону. Тот обработал их с помощью электронной вычислительной машины. В «американском случае» машинное руководство к действию (алгоритм поиска вариантов) было составлено так, чтобы изыскивать повышение вероятностей благоприятного исхода. Именно с этой целью перебирала машина горы чисел, строя свою игру против вымышленного противника по законам теории игр. Право же, не стоило создавать целое направление в математике, чтобы помогать выигрывать в азартные игры! Конечно, теория игр создана не для этого Модели игр служат тем инструментом, с помощью которого теория игр пытается проверить серьезные задачи. С помощью теории игр стремятся выработать целесообразную линию поведения для многих и многих систем, ведущих борьбу против другой системы.
Например, теорию игр можно применить к задачам связи, к вопросам технологии медицины, нефтедобычи, спорта, рыболовства, к противовоздушной обороне, к задачам, которые приходится решать командиру в сражении. Под углом зрения теории игр можно рассматривать и работу экспериментатора, который составляет план экспериментов. Их можно рассматривать как игру, где противниками выступают ученый и нервная система животного, которую он изучает. Есть игры, в которых прорабатываются сложные ситуации, растянутые во времени. Для них готовят специальное математическое обеспечение, им нужна достаточно мощная база вычислительных машин. Ведь для исследования даже самой простой производственно-хозяйственной ситуации бывает необходимым провести большое количество вычислений. В большинстве случаев в играх приходится иметь дело с цифрами: проделывать головокружительное количество вычислений. Не случайно, значит, учат машину играть в разные игры: в домино, в шашки, в шахматы. Шахматы, дающие астрономическое число вариантов партий -2*10116 — открывают большой простор для исследований.
Теория игр имеет большое значение в экономическом анализе. В последние годы значение теории игр существенно возросло во многих областях экономических и социальных наук. С помощью теории игр предприятие получает возможность предусмотреть ходы своих партнеров и конкурентов.
Эта теория рассматривает поведение фирм на рынке как игру, причем имеются определенные правила игры, по результатам которой начисляются «призы» и «штрафы». Участники игры определенно не знают стратегию конкурента, поэтому их поведение основано лишь на прогнозах.
Например, рассмотрим стратегию фирм А и В (табл. 4) с понижением цены. Если обе фирмы не понижают цену, прибыль каждой составит, например, 60 млн усл. ед. Если одна из фирм понижает цену, она получает конкурентное преимущество и увеличивает прибыль до 85 млн усл. ед. В это время конкурент терпит убыток в размере 25 млн усл. ед. Если же обе фирмы в сговоре проводят политику снижения цены, прибыль каждого составит по 12,5 млн усл. ед. Необходимо определить, как поступить фирмам А и В, чтобы не проиграть.
Аналогом данной ситуации на рынке служит другая игра — так называемая «дилемма заключенного». Суть этой игры в следующем: два узника содержатся в отдельных камерах и обвиняются по одному делу (табл. 5).
У обвинения достаточно улик, чтобы осудить узников только на два года. Узникам сообщили (каждому отдельно), что если один сознается, а другой нет, то сознавшийся будет свободен, а не сознавшийся получит 20 лет. Если сознаются оба, то каждый получит по 10 лет. Необходимо определить, каким будет поведение заключенного, когда реакция другого неизвестна.
В этом случае различают две стратегии поведения, называемые maximin и maximax:
1. min — это стратегия пессимиста.
2. max — это стратегия оптимиста.
Пессимист будет искать наилучший вариант из наихудших результатов. Это ситуация, когда, например, узник А ждет, что узник В признается, и тогда А получит 20 лет заключения, при условии, что он не сознается. Чтобы обеспечить себе наименее плохой результат из всех плохих вариантов, узник А решает сознаться, поскольку это позволит ему получить 10 лет заключения, а не 20. Этот результат лучше, чем 20 лет заключения.
Аналогично будет рассуждать и узник В. В результате, не сговариваясь, оба узника придут к решению сознаться и получат по 10 лет тюрьмы.
Оптимист надеется на самый лучший вариант решения вопроса. Узник А думает, что узник В не сознается, поэтому он решает сознаться. Но узник В также оптимист и поступает аналогичным образом. В результате, не сговариваясь, оба заключенных придут к решению сознаться и получат по 10 лет тюрьмы.
Стратегии min и max привели узников к одному результату — это и есть решение Нэша.
Подобного рода решение примут фирмы А и В на конкурентном рынке. В обоих случаях фирмы А и В решают снижать цены, и стратеги min и max приведут их к решению Нэша, т. е. понижать цены, что даст им равные прибыли — по 12,5 млн усл. ед, каждой фирме.
Заключение
«Есть в современной математике одна область, она носит безобидное название теории игр, но ей, несомненно, суждено сыграть очень важную роль в человековедении самого ближайшего будущего, — говорил Джон фон Нейман, один из основоположников кибернетики.- Она занимается вопросами оптимального поведения людей при наличии противодействующего противника. Для ученого противник — это природа со всеми ее явлениями; экспериментатор борется со средой; математик — с загадками математического мира; инженер — с сопротивлением материалов».
www.ronl.ru
