Тема 7. Игровое моделирование стратегий управления и принятия решений Лекции 18-20. Учебные вопросы: 1. Понятие игрового моделирования. 2. Решение игр. - презентация

1 Тема 7. Игровое моделирование стратегий управления и принятия решений Лекции Учебные вопросы: 1. Понятие игрового моделирования. 2. Решение игр в чистых стратегиях. 3. Решение игры в смешанных стратегиях. 4. Платёжная функция. 5. Существенные и несущественные стратегии. 6. Методы решения игровых задач. 7. Графическое решение игры. 8. Аналитическое решение игры. 9. Сведение игры к задаче линейного программирования. 10. Итерационный алгоритм Брауна. 11. Понятие статистических решений. 12. Оптимизация игры с природой.

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

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

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

5 Математическая модель конечной парной игры с нулевой суммой представляет собой так называемую платежную матрицу размера m × n, где m – число стратегий стороны А; n – число стратегий стороны В. Элемент матрицы а ij представляет собой выигрыш стороны А, если она применяет стратегию А i, а сторона В использует стратегию В j. Платёжная матрица

6 2. Решение игр в чистых стратегиях Если каждая из сторон выбирает однозначно с вероятностью 1 некоторую стратегию, то решение игры будет в чистых стратегиях. Оптимальное решение игры соответствует максимально возможному выигрышу стороны А (минимально возможному проигрышу стороны В). Таким образом, решение игры заключается в нахождении оптимальных чистых стратегий сторон.

7 Чтобы обеспечить себе максимальный выигрыш, сторона А должна выбирать такую стратегию А i, i = 1, 2, …, m, при которой её минимальный выигрыш максимален: = max min ij i j Величина называется нижней ценой игры и представляет собой гарантированный выигрыш стороны А. Стратегия, обеспечивающая стороне А получение выигрыша, называется максиминной. Максиминная стратегия

8 Оптимальной для стороны В будет та стратегия В j, j = 1, 2, …, n, при которой её максимальный проигрыш минимален: = min max ij j i Величина называется верхней ценой игры, а соответствующая проигрышу стратегия стороны В – минимаксной. Минимаксная стратегия

9 Таким образом, выигрыш стороны А (проигрыш стороны В) при выборе ими оптимальных стратегий не может быть больше верхней цены игры (меньше нижней цены игры). Фактический результат игры, называемый ценой игры, лежит в пределах:. Оптимальные стратегии игр с седловой точкой устойчивы, так как отклонение любой стороны от оптимальной стратегии приводит к уменьшению выигрыша стороны А (увеличению проигрыша стороны В).

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

11 Если игра ведётся в смешанных стратегиях, то при многократном повторении игры каждая сторона случайно выбирает одну из своих чистых стратегий. Смешанную стратегию стороны А будем описывать m-мерным вектором Р = (р 1, р 2, …, р m ), где p i - вероятность использования чистой стратегии А i. Смешанную стратегию стороны В будем описывать n-мерным вектором Q = (q 1, q 2, …, q n ), где q j - вероятность использования чистой стратегии В j.

12 Очевидно, что компоненты векторов P и Q должны удовлетворять соотношениям : p i 0; q j 0; m n p i = 1; q j = 1, i=1 j=1 p i = 1; q j = 1, i=1 j=1 i = 1, 2, …, m; j = 1, 2, …, n. Условие нормировки

13 Результат игры будет зависеть от смешанной стратегии Р стороны А и смешанной стратегии Q стороны В, и который получил название платежной функции ( Р, Q ). Физически платежная функция является математическим ожиданием результата игры и вычисляется по формуле: m n ( Р, Q ) = ij p i q j. i=1 j=1 4. Платёжная функция

14 Если сторона А использует оптимальную смешанную стратегию P *, то при любой стратегии стороны В выигрыш стороны А (проигрыш стороны В) будет не меньше цены игры, т.е. m ij p i, j = 1, 2, …, n. i=1 Оптимальное поведение стороны А

15 Если сторона В использует оптимальную смешанную стратегию Q *, то при любой стратегии стороны А проигрыш стороны В (выигрыш стороны А) будет не больше цены игры, т.е. n ij q j, i = 1, 2, …, m. j=1 Оптимальное поведение стороны В

16

17

18 Решение матричной игры в смешанных стратегиях, т.е. нахождение седловой точки платежной функции, связано с операциями над платежной матрицей. Поэтому перед решением игры целесообразно упростить платежную матрицу, оставив в ней только те элементы, которые соответствуют существенным стратегиям. Чистая стратегия называется существенной, если вероятность её использования в смешанной стратегии больше 0. В противном случае, если вероятность использования чистой стратегии в смешанной равна 0, чистая стратегия называется несущественной. 5. Существенные и несущественные стратегии

19 Для выявления существенных стратегий попарно сравнивают строки и столбцы платежной матрицы. Если все элементы i -ой строки больше соответствующего элемента k -ой строки, то стратегия А i доминирует над стратегией А k, и поэтому стратегия А k несущественна и может быть исключена из платежной матрицы. Подобные рассуждения могут быть проведены и в отношении столбцов. Кроме того, в платежной матрице могут существовать одинаковые строки и одинаковые столбцы, т.е. дублирующие стратегии. Из нескольких дублирующих стратегий нужно оставлять одну.

20 Исключение несущественных и дублирующих стратегий

21 В теории игр имеет место следующая теорема. У любой конечной игры m x n имеется решение, в котором число существенных стратегий каждой стороны не превосходит наименьшего из чисел m и n. Решение игровой задачи может быть осуществлено: графически, когда min {m, n} = 2; аналитически, путём решения системы линейных уравнений; сведением игры к задаче линейного программирования; приближённо с помощью алгоритма Брауна. 6. Методы решения игровых задач

22

23 7. Графическое решение игры при m = 2, n = 4 p{4-5} p{6-2} ν A1A1 A2A2

24 Решение игры для существенных стратегий q{4-5} q{6-2} ν B2B2 B3B3

25 Для матрицы 3×4 имеем систему из девяти линейных алгебраических уравнений для восьми неизвестных 8. Аналитическое решение игры

26 Стандартное представление системы линейных алгебраических уравнений

27 Решение игровой задачи средствами EXCEL

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

29 Формализация игры за сторону А

30 Оптимизация игровой задачи за сторону А средством EXCEL «Поиск решения»

31 Преобразование игры за сторону В

32 Формализация игры за сторону В

33 Оптимизация игровой задачи за сторону В средством EXCEL «Поиск решения»

34 Для решения матричных игр американским ученым Г. Брауном предложен приближенный метод. Решение игры методом Брауна начинается со случайного выбора стратегии одной из сторон. Пусть сторона А выбрала стратегию А i. Выпишем элементы этой стратегии под игровой матрицей. Сторона В, минимизируя свой проигрыш, выберет стратегию В j, соответствующую минимальному элементу стратегии А i.Выпишем элементы стратегии В справа от матрицы. Сторона А находит среди элементов стратегии В j максимальный элемент и выбирает стратегию А k, соответствующую максимальному выигрышу. Элементы стратегии А k прибавляются к элементам стратегии А i и записываются под матрицей. 10. Итерационный алгоритм Брауна

35 Аналогичные итерации повторяются столько раз, сколько необходимо для решения игры с требуемой точностью. На каждой итерации максимальный выигрыш стороны А и минимальный проигрыш стороны В отмечаются звездочкой. Подсчитав число отмеченных элементов в каждой стратегии сторон, получим частоту использования каждой стратегии путем деления числа отмеченных элементов стратегии на общее число итераций. При достаточно большом числе итераций частоты стратегий сводятся к вероятностям, которые и являются оптимальными решениями матричной игры. За N проведенных итераций будут получены оптимальные стратегии: Р* = { p 1, p 2, …, p m }; Q* = { q 1, q 2, …, q n }.

36 Пример реализации алгоритма Брауна в EXCEL

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

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

39

40 В теории статистических решений наряду с платежной матрицей пользуются матрицей рисков. Риском r ij называется разность между максимально возможным выигрышем при выборе конкретной стратегии А i и соответствующим элементом игровой матрицы.

41

42 Случай 2. Вероятности состояния среды S j, j = 1, …, n неизвестны. Критерий Вальда (критерий крайнего пессимизма) совпадает с критерием выбора стратегии, позволяющим получить нижнюю цену парной игры: W 1 = max min ij. i j Критерий минимального риска Севиджа рекомендует выбирать стратегию, при которой величина риска принимает наименьшее значение в самой неблагоприятной ситуации: W 2 = max min r ij. i j Критерий Гурвица учитывает как пессиместический, так и оптимистический подход к оценке ситуации: W 3 = max { min ij + (1- ) max ij }, где 0 1. i j j

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

44 Оптимизация игры с природой средством EXCEL «Поиск решения»

45 ЗАКЛЮЧЕНИЕ Оптимальные стратегии игр с седловой точкой устойчивы, так как отклонение любой стороны от оптимальной стратегии приводит к ухудшению получаемого результата (выигрыш, проигрыш). Решение игры в смешанных стратегиях может быть осуществлено на основе сведения игровой ситуации к задаче линейного программирования, к системе линейных алгебраических уравнений, или к итерационному методу Г. Брауна.