Экономическое моделирование методами теории игр

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

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

Пусть в игре участвуют два игрока А и В. Игрок А имеет n чистых стратегий, а игрок В – m стратегий. А выигрывает у В сумму a _ij, если А выбрал вариант i (i=1,2,…, n), а В выбрал вариант j (j=1,2,…, m). Тогда платежная матрица игры имеет вид:

a ₁₁ a ₁₂ … a _1m

A = [ a _ij ] = a ₂₁ a ₂₂ … a _2m

………..

a _n1 a _n2 … a _nm

Для нахождения вероятностей p_i и q_j оптимальных смешанных стратегий необходимо решать прямую и двойственную задачи линейного программирования (ЗЛП) вида:

а) прямая ЗЛП – минимизировать Z = x ₁+ x ₂+…+ x _n

при ограничениях

a ₁₁ x ₁+ a ₂₁ x ₂+…+ a _n1 x _n ≥ 1,

a ₁₂ x ₁+ a ₂₂ x ₂+…+ a _n2 x _n ≥ 1, (5.1)

……………………. ……

a _1m x ₁+ a _2m x ₂+…+ a _nm x _n≥ 1,

x ₁, x ₂,…, x _n ≥ 0.

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

Решая ее, находим оптимальное решение x ₁*, x ₂*,…, x _n*, откуда, разделив на Z*= x ₁*+ x ₂*+…+ x _n*, получаем оптимальную стратегию для игрока А (р ₁*, р ₂*,.., р_n *), которая заключается в применении i-й чистой стратегии с частотой р_i *= х_i */ Z*.

б) двойственная ЗЛП – максимизировать F = y ₁+ y ₂+ … + y _m→max;

при ограничениях

a ₁₁ y ₁+ a ₁₂ y ₂+ …+ a _1m y _m ≤1;

a ₂₁ y ₁+ a ₂₂ y ₂+ …+ a _2m y _m ≤1; (5.2)

…………………………..

a _n1 y ₁+ a _n2 y ₂+ …+ a_{n m} y _m ≤1;

y ₁≥0; y ₂≥0; … y _m ≥0.

Здесь строка ограничения формируется из строки платежной матрицы.

Решая данную ЗЛП, находим оптимальное решение у ₁*, у ₂*,…, у _m*, откуда, разделив на F *= y ₁*+ y ₂*+…+ y _m*, получаем оптимальную стратегию для игрока B (q ₁*, q ₂*,.., q_m *), которая заключается в применении j-й чистой стратегии с частотой q_j *= y_j */ F *.

Затем находим цену игры g =1/ Z* =1 /F*.

ПРИМЕР 5.1. Две конкурирующие коммерческие организации А и В выпускают продукцию одного вида. Каждая организация планирует проведение рекламной акции, причем маркетологи каждой компании предложили четыре сценария ее проведения A ₁, A ₂, A ₃, A ₄– для компании А и B ₁, B ₂, B ₃, B ₄– для компании В. Ожидаемая прибыль для кампании А при каждой ее стратегии A_i и ответе B_j представлена в платежной матрице:

Ai \ Bj	B 1	B 2	B 3	B 4
A 1
A 2
A 3
A 4

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

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

x ₁ + x ₂ + x ₃ + x ₄ →min;

при ограничениях:

70 x ₁ + 60 x ₂ + 20 x ₃ + 50 x ₄≥1;

30 x ₁ + 50 x ₂ + 60 x ₃ + 70 x ₄ ≥1;

20 x ₁ + 40 x ₂ + 80 x ₃ + 30 x ₄ ≥1;

50 x ₁ + 80 x ₂ + 60 x ₃ + 50 x ₄ ≥1;

x ₁ ≥0; x ₂ ≥0; x ₃ ≥0; x ₄ ≥0.

Для решения данной ЗЛП на ЭВМ также используют надстройку EXCEL «Поиск решения».

Подготовим предварительно в электронной таблице данные.

Запускаем программу MS Excel, вводим в ячейку А1 открывшейся электронной таблицы подпись «Переменные», а в следующие ячейки В1-Е1 произвольные значения переменных x ₁, x ₂, x ₃, x ₄. Это вначале могут быть произвольные числа, например единицы. Далее, в ячейку А2 вводим подпись «Целевая», а в соседнюю ячейку В2 значение целевой функции (переключившись в английский режим набора текста): «=B1+С1+D1+Е1» или =SUMM(B1:E1), что означает формулу x ₁ + x ₂ + x ₃ + x ₄. В третьей строке вводятся левые части системы ограничений. Для этого переводим курсор в ячейку А3 и вводим в ней текст «Ограничения», а в ячейку В3 формулу «=70*В1+60*C1+20*D1+50*E1», которая соответствует левой части первого ограничения системы. Три остальных ограничения вводим в ячейки С3-В3, а именно,

в ячейку С3: «=30*В1+50*C1+60*D1+70*E1»,

в D3: «=20*В1+40*C1+80*D1+30*E1»,

в ячейку Е3: «=50*В1+80*C1+60*D1+50*E1».

После этого вызываем надстройку Сервис/Поиск решения, в поле «Установить целевую ячейку» даем ссылку на В2. Ниже, в области «Равной», поставить переключатель на минимальное значение. Ставим курсор в поле «Изменяя ячейки», и даем ссылки на переменные, обводя мышью ячейки В1-Е1.

Далее, переводим курсор в поле «Ограничения», и вводим ограничения. Для этого нажимаем на кнопку «Добавить» и в появившемся окне в поле «Ссылка на ячейку» даем ссылку на ячейки, содержащие левые части всех четырех ограничений, которые хранятся в ячейках В3:Е3 (то есть переводим курсор в поле «Ссылка на ячейку» и обводим мышью ячейки В3:Е3). В центральном поле выбираем знак неравенства – ограничения: «≥», в поле «Ограничение» вводим единицу. Нажимаем «ОК». Для ввода дополнительных ограничений x ₁≥0; x ₂≥0; x ₃≥0; x ₄≥0 нажимаем «Добавить», в поле «Ссылка на ячейку» ставим курсор и обводим ячейки В1-Е1, выводим в центральное поле «≥», ограничение «0», нажимаем «ОК». Результат на рис.5.1.

Рисунок 5.1 Окно «Поиск решения» прямой ЗЛП

Для запуска вычислений нажимаем кнопку «Выполнить». Появляется надпись, что решение найдено. Выбираем «Сохранить найденное решение» и нажимаем «ОК» – видим результат (рис.5.2): x ₁=0, x ₂ =0,015, x ₃ =0,05, x ₄ =0, что видно из ячеек В1-Е1.

Рисунок 5.2 Решение прямой ЗЛП примера 5.1

Вводим в А5 подпись «Цена игры», а в соседнюю В5 формулу (переключаясь на английский язык) «=1/(В1+С1+D1+Е1)» или =1/В2. Результат: 50. Это средняя вероятность выигрыша для игрока А. Находим вероятности чистых стратегий в смешанной стратегии р. Для этого вводим в А6 подпись «Р1=», а в соседнюю В6 формулу «=В5*В1», вводим в А7: «Р2=», а в В7 формулу «=В5*С1», в А8: «Р3=», а в В8: «=В5*D1», в А9: «Р4=», в В9: «=В5*Е1». Данные показатели и есть решение задачи (рис.5.3).

Рисунок 5.3 Решение примера 5.1 для игрока А

Рассмотрим теперь решение относительно игрока В.

ЗЛП для игрока В имеет вид:

y ₁+ y ₂+ y ₃+ y ₄→ max;

70 y ₁+30 y ₂+ 20 y ₃+ 50 y ₄≤1;

60 y ₁+ 50 y ₂+ 40 y ₃+ 80 y ₄≤1;

20 y ₁+ 60 y ₂+ 80 y ₃+ 60 y ₄≤ 1;

50 y ₁+ 70 y ₂+ 30 y ₃+50 y ₄≤1;

y ₁≥0; y ₂≥0; y ₃≥0; y ₄≥0.

Переходим на «Лист2» электронной таблицы, щелкнув на соответствующей закладке внизу таблицы. Вводим в ячейки открывшейся чистой электронной таблицы в ячейку А1 надпись «Переменные», а в следующие ячейки В1-Е1 произвольные значения переменных, например, цифры 1. В ячейку А2 вводим подпись «Целевая». Вводим в ячейку В2 значение целевой функции (переключившись в английский режим набора текста): «=B1+С1+D1+Е1», что означает формулу y ₁+ y ₂+ y ₃+ y ₄. В третьей строке вводятся левые части системы ограничений. Для этого переводим курсор в ячейку А3 и вводим в ней текст «Ограничения». Переключившись в английский режим клавиатуры, вводим в ячейку В3 формулу «=70*В1+30*C1+20*D1+50*E1», которая соответствует левой части первого ограничения системы.

Вводим в ячейку С3: «=60*В1+50*C1+40*D1+80*E1»,

в D3: «=20*В1+60*C1+80*D1+60*E1»,

в ячейку Е3: «=50*В1+70*C1+30*D1+50*E1».

После этого вызываем в меню «Cервис» надстройку «Поиск решений». В поле «Установить целевую ячейку» даем ссылку на В2. Ниже, в области «Равной», поставить переключатель на максимальное значение.

Ставим курсор в поле «Изменяя ячейки», и даем ссылки на переменные, обводя мышью ячейки В1-Е1. Далее, переводим курсор в поле «Ограничения», и вводим ограничения. Для этого, нажимаем на кнопку «Добавить» и далее в поле «Ссылка на ячейку» обводим ячейки В3:Е3, содержащие левые части всех четырех ограничений, в центральном поле выбираем знак неравенства – ограничения: «≤», в поле «Ограничение» вводим единицу. Нажимаем «ОК». Для ввода дополнительных ограничений y ₁≥0; y ₂≥0; y ₃≥0; y ₄≥0 нажимаем «Добавить», в поле «Ссылка на ячейку» ставим курсор и обводим ячейки В1-Е1, выводим в центральное поле «≥», ограничение «0», нажимаем «ОК». Результат на рис.5.4.

Рисунок 5.4 Окно «Поиск решения» обратной ЗЛП

Далее запускаем программу, нажимая «Выполнить». Результат решения обратной ЗЛП в ячейках В1-Е1. Вводим в А5 подпись «Цена игры», а в соседнюю В5 формулу (переключаясь на английский язык) «=1/(В1+С1+D1+Е1)». Находим вероятности чистых стратегий q в смешанной стратегии игрока В. Для этого вводим в А6 подпись «q1=», а в соседнюю В6 формулу «=В5*В1», вводим в А7: «q2=», а в В7 формулу «=В5*С1», в А8: «q3=», а в В8: «=В5*D1», в А9: «q4=», в В9: «=В5*Е1». Данные показатели и есть решение задачи для игрока В (рис.5.5).

Рисунок 5.5 Решение примера 5.1 для игрока В

ПРИМЕР 5.2. Построить прямую и двойственную задачи линейного программирования для решения матричной игры, заданной платежной матрицей:

A=

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

имеют вид:

x ₁ + x ₂ + x ₃ + x ₄ + x ₅ →min;

5 x ₁ + 3 x ₂ + 4 x ₃ + 6 x ₄ + 7 x ₅ ≥1;

6 x ₁ + 8 x ₂ + 2 x ₃ + 3 x ₄ + x ₅ ≥1;

3 x ₁ +5 x ₂ +7 x ₃ +2 x ₄ +8 x ₅ ≥1;

9 x ₁ +2 x ₂ +6 x ₃ + 5 x ₄ +3 x ₅ ≥1;

x _i ≥0; i=1,2,3,4,5.

 

y ₁ + y ₂ + y ₃ + y ₄ →max;

5 y ₁ + 6 y ₂ + 3 y ₃ + 9 y ₄ ≤1;

3 y ₁ + 8 y ₂ + 5 y ₃ + 2 y ₄ ≤1;

4 y ₁ + 2 y ₂ + 7 y ₃ +6 y ₄ ≤1;

6 y ₁ + 3 y ₂ + 2 y ₃ + 5 y ₄ ≤1;

7 y ₁ + y ₂ + 8 y ₃ + 3 y ₄ ≤1;

y_j ≥0; j=1,2,3,4.

Из решения игры можно найти цену игры

g =1/(x ₁ + x ₂ + x ₃ + x ₄ + x ₅) =1/(y ₁ + y ₂ + y ₃ + y ₄)

и вероятности состояний

p_i = x_i g, (i = 1,2,3,4,5); q_j = y_j g, (j =1,2,3,4).

Задание 5.1. Самостоятельно с использованием ЭВМ решить поставленные в примере 5.2 ЗЛП и найти оптимальные смешанные стратегии для игроков А и В.

Отчет должен содержать решения поставленных ЗЛП (значения переменных x_i u y_j, значения целевых функций), смешанные стратегии для обоих игроков и цену игры g.

Задание 5.2. Директор предприятия А заключает договор с конкурирующей фирмой В о реализации своей продукции на конкретной территории областного центра. Конкурирующие стороны выделили пять районов области. Каждая из них может развивать свое производство в этих пяти районах: A ₁, A ₂, A ₃, A ₄, A ₅ – для стороны А и B ₁, B ₂, B ₃, B ₄, B ₅ – для В. Вероятности успеха для стороны А приведены в платежной матрице:

Ai \ Bj	B 1	B 2	B 3	B 4	B 5
A 1
A 2					30+ а
A 3	30+ а
A 4
A 5			30+ а

Определить оптимальные стратегии для каждой стороны.

Значение неизвестного параметра а взять равным номеру варианта.

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

Задание 5.3. Решить игру, описанную платежной матрицей для обоих игроков (матрица приведена для игрока А).

Аi \ Вj	В 1	В 2	В 3	В 4	В 5
А 1		a
А 2			a
А 3
А 4					a

Значение неизвестного параметра а взять равным номеру варианта.

Отчет должен содержать математические модели ЗЛП, составленные для обоих игроков, полученные в результате решения на ЭВМ смешанные стратегии для обоих игроков и цену игры g.

Работа № 6

ИГРЫ С ПРИРОДОЙ

Цель: научиться методам принятия решений в условиях неопределенности и риска (такие математические модели называются Играми с природой) на ЭВМ с использованием критериев Лапласа, Вальда, Байеса, Сэвиджа и Гурвица.

Рассмотрим ситуацию, когда лицо принимающее решение (ЛПР) может выбрать одну из n возможных альтернатив, которые обозначим A ₁, A ₂,..., A _n, то есть выбирает наилучший вариант действий из имеющихся п возможных. Выигрыш для каждой альтернативы зависит от того, какой вариант развития ситуации произойдет. Пусть возможны m вариантов развития ситуации, которые обозначим S ₁, S ₂,..., S _m.

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

ПРИМЕР 6.1. Директор финансовой компании проводит рискованную финансовую операцию. Страховая компания предлагает застраховать сделку и предлагает 4 варианта страховки: A ₁, A ₂, A ₃, A ₄. Компенсация ущерба для каждого варианта зависит от того, какой из возможных страховых случаев произошел. Выделяют 5 видов страховых случаев: S ₁, S ₂, S ₃, S ₄, S ₅.Компенсации (тыс. у.е.) для каждого вида страховки при каждом страховом случае составляют матрицу выигрышей вида:

Ai/Sj	S 1	S 2	S 3	S 4	S 5
A 1
A 2
A 3
A 4

Выбрать наилучшую альтернативу, используя критерии Лапласа, Вальда, Байеса (при вероятностях состояний исходов p ₁ = 0,3; p ₂ = 0,2; p ₃= 0,1; p ₄= 0,3; p ₅ = 0,1), Сэвиджа и Гурвица (при коэффициенте доверия α=0,4).

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

Рисунок 6.1 Решение примера 6.1

Вычисляем функции полезности для критерия Лапласа. Для этого ставим курсор в ячейку G2 и вводим формулу, усредняющую значения показателей привлекательности по первой альтернативе. Для этого вызываем мастер функций, нажимая на кнопку fx и выбираем в категории «Статистические» функцию «СРЗНАЧ», в качестве аргумента функции указываем ячейки B2:F2, обводя их курсором. Нажимаем ОК, видим результат 40,2. Автозаполняем ячейки G2-G5, перетаскивая нижний правый уголок ячейки G2. Видно, что наибольшая функция полезности 40,4 для альтернативы А₃. Вводим в G6: «А₃».

Для критерия Вальда вычисляем наименьшие показатели привлекательности для каждой альтернативы. Для этого вводим в Н2 функцию МИН с аргументами B2:F2: «=МИН(B2:F2)» (кавычки не вводить!). Автозаполняем на Н2-Н5. Выбираем альтернативу, где результат наибольший. Это значение 37 для альтернативы А₂, вводим в Н6: «А₂».

Для критерия Байеса функции полезности равны суммам выигрышей, умноженным на вероятности их исходов. Вводим в I2 формулу:

«=В2*0,3+C2*0,2+D2*0,1+E2*0,3+F2*0,1», автозаполняем на I2-I5. Выбираем альтернативу с наибольшей функцией полезности, то есть А₄, вводим в I6: «А₄».

Для критерия Сэвиджа необходимо построить матрицу рисков.

Для этого ставим курсор в ячейку В8 и вводим формулу «=МАКС(B$2:B$5)-B2», автозаполняем результат на ячейки В8-F11.

Далее находим максимальный риск для каждой альтернативы. Для этого ставим курсор в ячейку J2 и вводим «=МАКС(B8:F8)», автозаполняем результат на J2-J5. Выбираем альтернативу с минимальным риском, это А₃. Вводим в J6: «А₃».

Для критерия Гурвица нужно наибольшее значение каждой альтернативы умножить на α(по условию α= 0,4), наименьшее на (1- α) и результаты сложить. Вводим в К2 формулу:

=МАКС(B2:F2)*0,4+МИН(B2:F2)*0,6 и автозаполняем результат на К2-К5. Выбираем альтернативу с наибольшей функцией полезности. Это А₃, вводим К6: «А₃». Задача решена.

Рассмотрим теперь метод решения задачи в случае минимизации критерия – «чем меньше, тем лучше».

ПРИМЕР 6.2. Фермер, имея в аренде большие площади под посев кукурузы, заметил, что влажности почвы в сезон созревания кукурузы недостаточно, чтобы получить максимальный урожай. Эксперты советовали фермеру провести дренажные каналы в период конца весны – начала лета, что должно значительно повысить урожай. Были предложены 5 проектов дренажных каналов: A ₁, A ₂, A ₃, A ₄, A ₅, затраты на которые зависят от погодных условий в период весна – лето.

Возможны варианты: S ₁ – дождливая весна и дождливое лето; S ₂ – дождливая весна и сухое лето; S ₃ – сухая весна и дождливое лето; S ₄ – сухая весна и сухое лето. Матрица затрат имеет вид:

Ai / Sj	S 1	S 2	S 3	S 4
A 1
A 2
A 3
A 4
A 5

Выбрать наилучшую альтернативу, используя критерии Лапласа, Вальда, Байеса с p ₁ = 0,2; p ₂ = 0,3; p ₃ = 0,3; p ₄ = 0,2, Сэвиджа и Гурвица при коэффициенте доверия α = 0,7.

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

Рисунок 6.2 Решение примера 6.2

Вычисляем функции полезности для критерия Лапласа. Для этого ставим курсор в ячейку F2 и вводим формулу:

«=СРЗНАЧ(В2:Е2)», автозаполняем на F2-F6. Наилучшей в данном случае считается альтернатива с минимальной функцией полезности, это А₂. Вводим в F7: «А₂».

Для критерия Вальда вычисляем наибольшие показатели привлекательности для каждой альтернативы. Для этого вводим в G2 функцию «=МАКС(B2:E2)», автозаполняем на G2-G6. Выбираем альтернативу, где результат наименьший, вводим в G7: «А₂».

Для критерия Байеса функция полезности вычисляется так же как и для предыдущего примера (но для 4-х состояний природы), в ячейку Н2 формулу «=B2*0,2+C2*0,3+D2*0,3+E2*0,2», автозаполняем на Н2-Н6. Выбираем альтернативу с наименьшей функцией полезности, это А₁, вводим в Н7: «А₁».

Для критерия Сэвиджа необходимо построить матрицу рисков. Для этого ставим курсор в ячейку В9 и вводим формулу «=B2-МИН(B$2:B$6)», автозаполняем результат на ячейки В9-Е13.

Далее находим максимальный риск для каждой альтернативы. Для этого ставим курсор в ячейку I2 и вводим «=МАКС(B9:E9)», автозаполняем результат на I2-I6. Выбираем альтернативу с минимальным риском, таких альтернатив две, это А₁ и А₄. Вводим в I7: «А₁, А₄».

Для критерия Гурвица нужно наименьшее значение каждой альтернативы умножить на α(по условию α= 0,7), наибольшее на (1– α) и результаты сложить. Вводим в J2 формулу:

= МИН(B2:E2)*0,7+МАКС(B2:E2)*0,3

и автозаполняем результат на J2-J6. Выбираем альтернативу с наименьшей функцией полезности. Это А₁, вводим J7: «А₁». Задача решена.

Задание 6.1. Директор торговой фирмы, продающей телевизоры, решил открыть представительство в областном центре. У него имеются альтернативы либо создавать собственный магазин в отдельном помещении, либо организовывать сотрудничество с местными торговыми центрами. Всего можно выделить 5 альтернатив решения: A ₁, A ₂, A ₃, A ₄, A ₅. Успех торговой фирмы зависит от того, как сложится ситуация на рынке предоставляемых услуг. Эксперты выделяют 4 возможных варианта развития ситуации S ₁, S ₂, S ₃, S ₄.

Прибыль фирмы для каждой альтернативы при каждой ситуации представлена матрицей выигрышей aij (млн. р./год).

Аi/Bj	S 1	S 2	S 3	S 4
A 1	a
A 2
A 3			a
A 4
A 5

Выбрать наилучшую альтернативу, используя критерии Лапласа, Вальда, Байеса с p 1 = 0,4; p 2 = 0,3; p 3 = 0,1; p 4 = 0,2, Сэвиджа и Гурвица при коэффициенте доверия α = 0,6.

Значение неизвестного параметра а взять равным номеру варианта.

Задание 6.2. Нефтяная компания собирается построить в районе крайнего севера нефтяную вышку. Имеется 4 проекта A, B, C и D.

Затраты на строительство (млн. руб.) зависят от того, какие погодные условия будут в период строительства. Возможны 5 вариантов погоды S ₁, S ₂, S ₃, S ₄, S ₅. Выбрать оптимальный проект для строительства используя критерии Лапласа, Вальда, Байеса с p ₁ = 0,1; p ₂= 0,2; p ₃= 0,3; p ₄= 0,2; p ₅ = 0,2, Сэвиджа и Гурвица при α = 0,6. Матрица затрат имеет вид:

Аi/Sj	S 1	S 2	S 3	S 4	S 5
A 1	а
A 2
A 3				a
A 4

Значение неизвестного параметра а взять равным номеру варианта.

Работа № 7