Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ДОНСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
ИНСТИТУТ ЭНЕРГЕТИКИ И МАШИНОСТРОЕНИЯ
Кафедра «Экономика и менеджмент в машиностроении»
ПРИМЕНЕНИЕ ТЕОРИИ ИГР К ЭКОНОМИЧЕСКИМ ЗАДАЧАМ
Методические указания к лабораторной работе
Ростов-на-Дону
2011
Составители:
кандидат физико-математических наук, доцент И. М. Пешхоев
кандидат экономических наук, доцент А.А. Алуханян
доцент Т.А. Иваночкина
УДК 336, 658
ПРИМЕНЕНИЕ ТЕОРИИ ИГР В ЭКОНОМИЧЕСКИХ ЗАДАЧАХ: Методические указания к лабораторной работе по дисциплине «Экономико-математическое моделированиет»/ДГТУ, Ростов н/Д, 2011. —16 с.
Методические указания предназначены для студентов 3-го и 4-го курсов специальностей 080507 и 080502 всех форм обучения
Печатается по решению редакционно-издательского совета института энеогетики и машиностроения
Рецензент кандидат технических наук, доцент В. П. Гаценко
Научный редактор доктор экономических наук, профессор
М. В. Альгина
© Издательский центр ДГТУ, 2011.
Составители:
ПЕШХОЕВ Иса Мусаевич
АЛУХАНЯН Артур Александрович
Иваночкина Татьяна Александровна
ПРИМЕНЕНИЕ ТЕОРИИ ИГР В ЭКОНОМИЧЕСКИХ ЗАДАЧАХ
Методические указания к лабораторной работе
Ответственный за выпуск
зав. кафедрой «Экономика и менеджмент в машиностроении»
доктор технических наук, профессор Л.В. Борисова
В печать 25.06.2010.
Объем 1,0 усл.п.л. Офсет. Формат 6084/16.
Бумага тип.№3. Заказ № 372 Тираж 100 экз. Цена свободная
Издательский центр ДГТУ.
Адрес университета и полиграфического предприятия:
, Ростов-на-Дону, пл. Гагарина, 1.
Оглавление
1. Теоретические сведения…………………………….........................4
Литература……………………………………………………………………..27
1. Теоретические сведения
1.1. Основные понятия теории матричных игр
На практике часто приходится сталкиваться с задачами, в которых необходимо принимать решения в условиях неопределенности, т. е. возникают ситуации, в которых две (или более) стороны преследуют различные цели, а результаты любого действия каждой из сторон зависят от мероприятий партнера.
В экономике конфликтные ситуации встречаются очень часто и имеют многообразный характер. К ним относятся, например, взаимоотношения между поставщиком и потребителем, покупателем и продавцом, банком и клиентом. Во всех этих примерах конфликтная ситуация порождается различием интересов партнеров и стремлением каждого из них принимать оптимальные решения, которые реализуют поставленные цели в наибольшей степени. При этом каждому приходится считаться не только со своими целями, но и с целями партнера, и учитывать неизвестные заранее решения, которые эти партнеры будут принимать.
Для решения задач с конфликтными ситуациями методы разработаны математической теорией конфликтных ситуаций, которая носит название теория игр.
Приведем основные понятия теории игр. Математическая модель конфликтной ситуации называется игрой, стороны, участвующие в конфликте − игроками, а исход конфликта − выигрышем. Для каждой формализованной игры вводятся правила, т. е. система условий, определяющая: 1) варианты действий игроков; 2) объем информации каждого игрока о поведении партнеров; 3) выигрыш, к которому приводит каждая совокупность действий. Как правило, выигрыш (или проигрыш) может быть задан количественно.
Игра называется парной, если в ней участвуют два игрока, и множественной, если число игроков больше двух. Рассматривать будем только парные игры. В них участвуют два игрока А и В, интересы которых противоположны, а под игрой будем понимать ряд действий со стороны А и В.
Игра называется игрой с нулевой суммой, или антагонистической, если выигрыш одного из игроков равен проигрышу другого.
Выбор и осуществление предусмотренных правилами действий называется стратегией игрока.
Целью теории игр является определение оптимальной стратегии для каждого игрока. При выборе оптимальной стратегии естественно предполагать, что оба игрока ведут себя разумно с точки зрения своих интересов.
Рассмотрим парную конечную игру. Пусть игрок А располагает стратегиями, которые обозначим А1 , А2 , ... , Аm . У игрока В имеется стратегий, обозначим их В1, В2 ,… , Вn .
В этом случае игра имеет размерность . В результате выбора игроками любой пары стратегий
однозначно определяется исход игры, т. е. выигрыш игрока А (положительный или отрицательный) и проигрыш (-) игрока В. Предположим, что значения известны для любой пары стратегий . Матрица {}, (i=1,2,…, m;j =1,2,…, п) элементами которой являются выигрыши, соответствующие стратегиям Аi и Вj , называется платежной матрицей. Строки этой матрицы соответствуют стратегиям игрока А, а столбцы − стратегиям игрока В.
Рассмотрим игру с матрицей {}, (i=1,2,…, m; j = 1,2,…, п) и определим наилучшую среди стратегий А1 , А2 , ... , Аm . Выбирая стратегию Аi игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий Bj , для которой выигрыш для игрока А минимален (игрок В стремится "навредить" игроку А).
Обозначим через , наименьший выигрыш игрока А при выборе им стратегии Аi для всех возможных стратегий игрока В (наименьшее число в -й строке платежной матрицы), т. е.
(1.1.1)
Среди всех чисел выберем наибольшее: . Назовем нижней ценой игры или максиминным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В. Следовательно,
, (1.1.2)
Стратегия, соответствующая максимину, называется максиминной стратегией. Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А; выбирая стратегию Вj он учитывает максимально возможный при этом выигрыш для А. Обозначим
(1.1.3)
Среди всех чисел выберем наименьшее и назовем верхней ценой игры или минимаксным выигрышем (мииимаксом). Это гарантированный проигрыш игрока В. Следовательно,
(1.1.4)
Простые рассуждения позволяют понять, что всегда . При гарантированный 1-му игроку выигрыш совпадает с тем выигрышем, выше которого второй игрок в состоянии не допустить выигрыша 1-го игрока, т. е. имеет место некоторое равновесие, которым игроки и должны удовлетвориться (при осторожной игре, без риска, так как отступление от этого поведения грозит возможным наказанием, уменьшением выигрыша или увеличением потерь). Эта ситуация отвечает наличию у платежной матрицы «седлового элемента» - максимального в столбце и минимального в строке.
В остальных случаях и возникает вопрос: нельзя ли увеличить гарантированный выигрыш и добиться того, чтобы выигрыш был между нижней и верхней ценой игры ?
1.2 Смешанные стратегии и теорема фон Неймана-Нэша
Ответ на вопрос, поставленный в предыдущем пункте, может быть получен благодаря применению «смешанных» стратегий.
Рассмотрим последовательность игр, в каждой из которых игроки выбирают свои чистые стратегии и, соответственно, получают выигрыши . Средний выигрыш первого игрока при этом равен .
Пусть − число игр, когда первый игрок выбрал свою -тую стратегию, − число игр, когда второй игрок выбрал свою -тую стратегию, причем ,
где − число чистых стратегий первого игрока, a n − второго. Очевидно, что некоторые или могут быть равны нулю (если соответствующие стратегии не выбирались ни разу).
Тогда − относительные частоты выбора стратегий, − векторы частот.
.
Теорема фон Неймана-Нэша
Для любой матричной игры минимакс равен максимину, или − существуют , удовлетворяющие условиям:
.
1.3 Метод решения игры
Рассмотрим игру , т. е. когда у каждого из игроков имеются всего две стратегии ().
Поскольку при равенстве нижних и верхних цен игры в чистых стратегиях решение очевидно (оно определяется седловой точкой матрицы), интерес представляет ситуация их неравенства. Но из теоремы Неймана-Нэша следует, что существует пара смешанных стратегий , обеспечивающая равенство верхней и нижней цены игры (минимакса и максимина). Раз это не реализуется чистыми стратегиями, значит, цена игры достигается при смешивании каждым игроком обеих своих стратегий (обе стратегии «активны») и при каждой чистой стратегии противника (иначе никакое смешивание не может улучшить результат), поэтому если
, то (1.3.1)
Имеем три уравнения с тремя неизвестными. Вычитая из первого уравнения второе, получаем отношение
(1.3.2)
Знак абсолютной величины поставлен потому, что это отношение всегда положительно, так как при разных знаках у и одна из стратегий второго игрока явно хуже другой и не может им применяться.
Решение отношения (1.3.2) сводится к делению единичного отрезка на части, находящиеся в отношении
,
после чего найти не представляет труда.
1.4 Приведение матричной игры к задаче линейного программирования
Решение игры может быть сведено к решению задачи линейного программирования.
Пусть игра задана платежной матрицей . Первый игрок обладает , второй − стратегиями. Необходимо определить оптимальные стратегии первого и второго игрока, где − оптимальные частоты применения своих стратегий соответственно первым и вторым игроком.
.
Оптимальная стратегия обеспечивает первому игроку средний выигрыш, не меньший, чем цена игры V, при любой стратегии второго игрока и выигрыш, равный цене игры V, при оптимальной стратегии второго игрока.
Если первый игрок применяет смешанную стратегию против любой чистой стратегии второго игрока, то он получает средний выигрыш, или математическое ожидание выигрыша (т. е. элементы j-гo столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий первого игрока и результаты складываются).
Для оптимальной стратегии все средние выигрыши не меньше цены игры V, поэтому получаем систему неравенств:
(1.4.1)
Каждое из неравенств можно разделить на число . Введем новые переменные
zi=. (1.4.2)
Тогда система (1.4.1) примет вид:
(1.4.3)
Цель первого игрока —максимизировать свой гарантированный выигрыш, т. е. цену игры V. Разделив на равенство , получаем, что переменные удовлетворяют условию: .
Максимизация цены игры V эквивалентна минимизации величины , поэтому задача может быть сформулирована следующим образом: определить значения переменных так, чтобы они удовлетворяли линейным ограничениям (1.4.3) и при этом линейная функция
(1.4.4)
обращалась в минимум. Это задача линейного программирования. Решая задачу (1.4.3) − (1.4.4), получаем оптимальные стратегии .
Для определения оптимальной стратегии второго игрока следует учесть, что он стремится минимизировать гарантированный выигрыш первого игрока, т. е. найти . Переменные удовлетворяют неравенствам
(1.4.5)
которые следуют из того, что средний проигрыш второго игрока не превосходит цены игры, какую бы чистую стратегию не применял первый игрок.
Если обозначить
(1.4.6)
то получим систему неравенств:
(1.4.7)
Переменные , удовлетворяют условию .
Игра свелась к следующей задаче: определить значения переменных , которые удовлетворяют системе неравенств (1.4.7) и максимизируют линейную функцию
(1.4.8)
Решение задачи линейного программирования (1.4.7) − (1.4.8) определяет оптимальную стратегию . При этом цена игры
. (1.4.9)
Задачи линейного программирования (1.4.3) − (1.4.4) и (1.4.7) − (1.4.8) являются взаимно двойственными. Очевидно, при определении оптимальных стратегий в конкретных задачах следует выбрать ту из взаимно двойственных задач, решение которой менее трудоемко, а решение другой задачи найти с помощью теорем двойственности.
2. Пример выполнения задания
Игра задана платежной матрицей А.
Для определения нижней цены игры выберем в каждой строке платежной матрицы минимальный элемент, затем из полученного столбца выберем максимальный элемент. Получим нижнюю цену игры: .
Для определения верхней цены игры выберем в каждом столбце матрицы максимальный элемент, тогда минимальный элемент из полученной строки и есть верхняя цена игры: .
Из условия следует, что игру необходимо проводить в смешанных стратегиях.
1) Пусть заданы вероятности использования противником своих стратегий: у = (0,2; 0,5; 0,3).
Необходимо определить оптимальное поведение и максимальный выигрыш первого игрока. Для этого рассчитаем его выигрыш в случае применения им всех своих стратегий по формуле:
При заданных условиях первый игрок должен применить свою третью стратегию, в этом случае он получит максимальный выигрыш равный 15,1.
2) Необходимо решить задачу 2x2, вычеркнув из заданной платежной матрицы столбец и строку таким образом, чтобы полученные в новой матрице и не совпадали. Например, вычеркнем из исходной матрицы третью строку и первый столбец, получим новую матрицу:
у которой .
Решение задачи свелось к решению системы:
Используем формулу (1.3.2):
.
Вычислим выигрыш первого игрока:
;
.
Отсюда вывод: первому игроку следует использовать свои стратегии с частотой , при этом его гарантированный выигрыш будет равен 12,19 ед., что существенно выше чем .
Для второго игрока решение сведется к системе:
; .
.
Используя смешанные стратегии с частотой , второй игрок может понизить свой гарантированный протгрыш с 16 ед. до 12,19 ед.
) Игра .
Любая игра сводится к задаче линейного программирования. Для первого игрока ограничения и целевая функция выглядят следующим образом:
где .
Для решения полученной задачи используем симплекс-метод, реализованный в программе LINPROG. При этом получим оптимальное решение:
Перейдем к исходным переменным:
Из полученных результатов следует, что максимальный гарантированный выигрыш первого игрока составит 11,6959 при условии, что он будет применять свою первую стратегию с частотой 0,6035, вторую − с частотой 0,2316 и третью − с частотой 0,1649.
Для второго игрока задача линейного программирования является двойственной к предыдущей и имеет вид:
где
Для решения использовалась программа LINPROG. Полученное оптимальное решение имеет вид:
Перейдем к исходным переменным:
Из полученных результатов следует, что минимальный гарантированный проигрыш второго игрока составит 11,6959 в случае если он будет использовать свою первую стратегию с частотой 0,5123, вторую − с частотой 0,2070, третью − с частотой 0,0240.
3. Задание к лабораторной работе
Игра задана платежной матрицей А. Получить решение задачи в случае, если:
1. Заданы стратегии противника;
2. Из платежной матрицы вычеркнуты строка и столбец таким образом, чтобы нижняя и верхняя цены игры не совпали (игра 2 х 2);
3. Решить задачу полностью (игра 3 х 3) с использованием персонального компьютера (программа LINPROG).
Платежная матрица, вектор известных стратегий второго игрока заданы в таблице.
Согласно заданному варианту в таблице приводятся элементы платежной матрицы и вероятностей использования стратегий 2-ым игроком.
|
№вар |
А11 |
А12 |
А13 |
А21 |
А22 |
А23 |
А31 |
А32 |
А33 |
Y1 |
Y2 |
Y3 |
|
1 |
0.2 |
.5 |
.3 |
|||||||||
|
2 |
0.5 |
.1 |
.4 |
|||||||||
|
3 |
8 |
0.4 |
.3 |
.3 |
||||||||
|
4 |
0.3 |
.4 |
.3 |
|||||||||
|
5 |
14 |
0.25 |
.2 |
.55 |
||||||||
|
6 |
0.6 |
.1 |
.3 |
|||||||||
|
7 |
13 |
0.2 |
.4 |
.4 |
||||||||
|
8 |
0.3 |
.5 |
.2 |
|||||||||
|
9 |
23 |
0.4 |
.3 |
.3 |
||||||||
|
10 |
0.35 |
.3 |
.35 |
|||||||||
|
11 |
0.5 |
.2 |
.3 |
|||||||||
|
12 |
0.65 |
.1 |
.25 |
|||||||||
|
13 |
0.3 |
.4 |
.3 |
|||||||||
|
№вар |
А11 |
А12 |
А13 |
А21 |
А22 |
А23 |
А31 |
А32 |
А33 |
Y1 |
Y2 |
Y3 |
|
14 |
0.2 |
.3 |
.5 |
|||||||||
|
15 |
0.4 |
.2 |
.4 |
|||||||||
|
16 |
0.5 |
.3 |
.2 |
|||||||||
|
17 |
0.3 |
.4 |
.3 |
|||||||||
|
18 |
0.1 |
.25 |
.65 |
|||||||||
|
19 |
0.15 |
.35 |
.5 |
|||||||||
|
20 |
0.5 |
.2 |
.3 |
|||||||||
|
21 |
0.4 |
.3 |
.3 |
|||||||||
|
22 |
0.2 |
.5 |
.3 |
|||||||||
|
23 |
0.3 |
.4 |
.3 |
|||||||||
|
24 |
0.25 |
.25 |
.5 |
|||||||||
|
25 |
0.6 |
.2 |
.2 |
|||||||||
|
26 |
0.2 |
.5 |
.3 |
|||||||||
|
27 |
0.3 |
.3 |
.4 |
|||||||||
|
28 |
0.4 |
.3 |
.3 |
|||||||||
|
29 |
0.5 |
.2 |
.3 |
|||||||||
|
30 |
0.1 |
.6 |
.3 |
|||||||||
|
32 |
5 |
15 |
4 |
18 |
6 |
7 |
6 |
5 |
17 |
0.2 |
.5 |
.3 |
|
33 |
5 |
4 |
0.1 |
.25 |
.65 |
|||||||
|
34 |
17 |
7 |
0.15 |
.35 |
.5 |
|||||||
|
35 |
5 |
5 |
0.3 |
.4 |
.3 |
|||||||
|
36 |
13 |
0.1 |
.25 |
.65 |
||||||||
|
37 |
21 |
0.6 |
.2 |
.2 |
||||||||
|
38 |
6 |
6 |
0.2 |
.5 |
.3 |
|||||||
|
39 |
18 |
6 |
0.5 |
.1 |
.4 |
|||||||
|
40 |
5 |
0.4 |
.3 |
.3 |
||||||||
|
41 |
7 |
0.35 |
.3 |
.35 |
||||||||
|
42 |
16 |
7 |
0.5 |
.2 |
.3 |
|||||||
|
43 |
12 |
6 |
5 |
0.1 |
.4 |
0. 5 |
Литература
4. Вентцель Е.С. Исследование операций. − М: Наука, 1988.
Составители:
ПЕШХОЕВ Иса Мусаевич
АЛУХАНЯН Артур Александрович
Иваночкина Татьяна Александровна
ПРИМЕНЕНИЕ ТЕОРИИ ИГР В ЭКОНОМИЧЕСКИХ ЗАДАЧАХ
Методические указания к лабораторной работе
Ответственный за выпуск
зав. кафедрой «Экономика и менеджмент в машиностроении»
доктор технических наук, профессор Л.В. Борисова
В печать 25.06.2010.
Объем 1,0 усл.п.л. Офсет. Формат 6084/16.
Бумага тип.№3. Заказ № 372 Тираж 100 экз. Цена свободная
Издательский центр ДГТУ.
Адрес университета и полиграфического предприятия:
, Ростов-на-Дону, пл. Гагарина, 1.
21