Презентация Модели принятия решений в условиях неопределенности Теория игр онлайн

Содержание слайда: Модели принятия решений в условиях неопределенности Теория игр

Содержание слайда: Основные вопросы 1. Основные понятия теории игр. 2. Нижняя и верхняя цена игры. 3. Игра с седловой точкой. 4. Решение игры в смешанных стратегиях. 5. Сведение решения игры к задаче линейного программирования. 6. Игры с природой.

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

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

Содержание слайда: Для того, чтобы найти решение игры, следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности, т.е. один из игроков должен получить максимальный выигрыш, когда второй придерживается своей стратегии. В то же время второй игрок должен иметь минимальный проигрыш, если первый придерживается своей стратегии. Такие стратегии называются оптимальными. Любому из игроков невыгодно отказаться от своей стратегии в игре. Для того, чтобы найти решение игры, следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности, т.е. один из игроков должен получить максимальный выигрыш, когда второй придерживается своей стратегии. В то же время второй игрок должен иметь минимальный проигрыш, если первый придерживается своей стратегии. Такие стратегии называются оптимальными. Любому из игроков невыгодно отказаться от своей стратегии в игре.

Содержание слайда: Математическая модель задачи Пусть игрок А располагает m стратегиями, которые обозначим А1, А2, … , Аm. Пусть у игрока В имеется n стратегий, обозначим их В1, В2, …,Вn. В этом случае игра имеет размерность m х n. В результате выбора игроками любой пары стратегий Аi и Вj (i =1,2, … m; j = 1,2, …, n) однозначно определяется исход игры, т.е. выигрыш aij игрока А (положительный или отрицательный) и проигрыш (-aij ) игрока В.

Содержание слайда: Предположим, что значения aij известны для любой пары стратегий (Аi,Вj). Матрица Р =(aij), i = 1,2, … , m; j = 1,2, …,n, элементами которой являются выигрыши, соответствующие стратегиям Аi, и Вj, называется платежной матрицей или матрицей игры: Предположим, что значения aij известны для любой пары стратегий (Аi,Вj). Матрица Р =(aij), i = 1,2, … , m; j = 1,2, …,n, элементами которой являются выигрыши, соответствующие стратегиям Аi, и Вj, называется платежной матрицей или матрицей игры:

Содержание слайда: Нижняя цена игры Обозначим через i наименьший выигрыш игрока А при выборе им стратегии Аi для всех возможных стратегий игрока В (наименьшее число в i-ой строке платежной матрицы). Среди всех чисел i (i = 1,2, …, m) выберем наибольшее:  = mах {i }. Число  называется нижней ценой игры. Это гарантированный выигрыш игрока А при любой стратегии игрока В.

Содержание слайда: Верхняя цена игры Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А, (а следовательно - свой проигрыш ). Выбирая стратегию Вj, он учитывает максимально возможный при этом выигрыш игрока А. Обозначим j наибольший возможный выигрыш игрока при выборе игроком В его стратегии Вj (наибольшее число в j-ом столбце платежной матрицы). Среди всех чисел j (j = 1,2, …, n) выберем наименьшее: = min{j }. Число  называется верхней ценой игры. Это гарантированный проигрыш игрока В.

Содержание слайда: Игра с седловой точкой Фактический выигрыш игрока А при разумных действиях партнеров ограничен нижней и верхней ценой игры. Если верхняя и нижняя цены игры совпадают, то общее значение верхней и нижней цены игры ==v называется ценой игры. В этом случае игра называется вполне определенной или игрой с седловой точкой.

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

Содержание слайда: Пример Найти решение игры, заданной платежной матрицей: (Игрок А имеет 3 стратегии: А1;А2;А3. Игрок В имеет 4 стратегии: В1;В2;В3;В4.

Содержание слайда: Решение: Определим наименьшие по строкам числа i и наибольшие по столбцам числа j: Определим нижнюю цену игры:  = mах {i } = mах {0,2,-1} =2. Верхняя цена игры: = min{j } = min {3,2,4,5} = 2.

Содержание слайда: Поскольку ==v=2, то платежная матрица содержит седловую точку, а игра имеет решение в чистых стратегиях. Поскольку ==v=2, то платежная матрица содержит седловую точку, а игра имеет решение в чистых стратегиях. Седловая точка находится во второй строке и втором столбце, следовательно оптимальными являются стратегии А2 и В2. При этом цена игры v=2.

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

Содержание слайда: Смешанной стратегией SA игрока А называется применение чистых стратегий А1, А2,… , Аi,…, Аm с вероятностями p1, p2,…, pi,…, pm, причем  pi = 1. Смешанной стратегией SA игрока А называется применение чистых стратегий А1, А2,… , Аi,…, Аm с вероятностями p1, p2,…, pi,…, pm, причем  pi = 1. Смешанные стратегии игрока А записываются в виде матрицы: или в виде строки SA= (p1, p2,…, pi,…, pm).

Содержание слайда: Аналогично смешанные стратегии игрока В обозначаются: Аналогично смешанные стратегии игрока В обозначаются: или SВ=( q1 q2 … qj … qn), где  qj =1. Чистая стратегия, которая входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, называется активной.

Содержание слайда: Если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий. Если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий. Цена игры удовлетворяет неравенству:   v  .

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

Содержание слайда: Предположим, что игра не имеет седловой точки. Предположим, что игра не имеет седловой точки. Найдем ее решение в смешанных стратегиях: SA = (p1, p2,…, pi,…, pm) и SВ =(q1, q2,…,qj, … ,qn). Применение игроком А оптимальной стратегии SA должно обеспечивать ему при любых действиях игрока В выигрыш не меньше цены игры v.

Содержание слайда: Определим математическое ожидание выигрыша игрока А в случае, если его соперник выбрал свою первую стратегию В1. Определим математическое ожидание выигрыша игрока А в случае, если его соперник выбрал свою первую стратегию В1. Аналогично определим М2,М3,….Mn≥v

Содержание слайда: Поэтому выполняются следующие соотношения: Поэтому выполняются следующие соотношения: причем  pi = 1. Аналогично, для игрока В оптимальная стратегия SВ должна обеспечить при любых стратегиях игрока А проигрыш, не превышающий величину v, т.е. справедливо соотношение: Для решения этих задач используют методы линейного программирования.

Содержание слайда: Игры с природой В некоторых случаях успех экономической деятельности зависит не от сознательно противодействующего конкурента, а от объективной действительности, которую принято называть "природой". Пусть игрок А располагает m стратегиями, которые обозначим А1, А2, … , Аm, а относительно "природы" известно, что она может принимать n различных состояний, обозначим их Р1, Р2, … Рn.

Содержание слайда: Известен выигрыш aij игрока А при каждой паре стратегий игрока и "природы", т.е. известна платежная матрица: Известен выигрыш aij игрока А при каждой паре стратегий игрока и "природы", т.е. известна платежная матрица:

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

Содержание слайда: Различают игры с "природой" в условиях определенности и игры с "природой" в условиях неопределенности. Различают игры с "природой" в условиях определенности и игры с "природой" в условиях неопределенности. В первом случае задано распределение вероятностей состояний природы, во втором - оно неизвестно. В этом случае приходится принимать решение в условиях риска.

Содержание слайда: Риском игрока А при использовании стратегии Аi при состоянии "природы" Pj называется разность между выигрышем, который он получил бы, если бы знал Pj и выигрышем, который он получит в обычных условиях, применяя стратегию Аi: Риском игрока А при использовании стратегии Аi при состоянии "природы" Pj называется разность между выигрышем, который он получил бы, если бы знал Pj и выигрышем, который он получит в обычных условиях, применяя стратегию Аi: rij = j - ij, где j = mах {ij }. i Рассмотрим критерии, используемые при решении игр с природой.

Содержание слайда: Критерий Бейеса-Лапласа При известном распределении вероятностей различных состояний природы Р =( p1, p2, …, pn,), где p1+ p2+…+ pn=1, критерием принятия решений является максимум математического ожидания выигрыша, т.е. VB-L = mах  aij pj, где i = 1,2, …, m. i j

Содержание слайда: Критерий Лапласа Если ни одно из состояний "природы" нельзя предпочесть другим, выдвигают гипотезу о том, что все они равновероятны: p1= p2=…=pn= 1/n. Тогда VL = mах  aij ·1/n . i j

Содержание слайда: Максиминный критерий Вальда Он основан на выборе стратегии игрока А, позволяющей гарантировать ему получение нижней цены игры: VW= mах min aij. i j

Содержание слайда: Критерий минимального риска Сэвиджа Рекомендует выбирать стратегию, при которой величина риска принимает наименьшее значение в самой неблагоприятной ситуации, т.е. VS= min mах rij. i j Критерии Вальда и Сэвиджа основаны на пессимистической оценке обстановки. В отличие от них следующий критерий использует как пессимистический, так и оптимистический подход к ситуации.

Содержание слайда: Критерий Гурвица По этому критерию выбирается максимум линейной комбинации максимальных или минимальных выигрышей. VH = mах { min aij +(1-) mах aij }. i j j Если =1, критерий Гурвица превращается в пессимистический критерий Вальда. При =0 - в критерий крайнего оптимизма, рассчитанный на наилучшее стечение обстоятельств. Обычно  принимают в пределах от 0,5 до 0,7.

Содержание слайда: Задача Возможно строительство четырех типов электростанций: тепловых (стратегия А1), приплотинных (А2), бесшлюзовых (А3), шлюзовых (А4). Эффективность каждого из типов зависит от различных факторов: режима рек, стоимости топлива и его перевозки и т.п. Предположим, что выделено четыре различных состояния, каждое из которых означает определенное сочетание факторов, влияющих на эффективность энергетических объектов.

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

Содержание слайда: а) на основе критерия Бейеса - Лапласа при заданном распределении вероятности состояний природы Р = (1/7, 2/7, 3/7, 1/7); а) на основе критерия Бейеса - Лапласа при заданном распределении вероятности состояний природы Р = (1/7, 2/7, 3/7, 1/7); б) на основе критерия Лапласа в предположении, что все состояния природы равновероятны; в) используя максиминный критерий Вальда; г) на базе критерия минимального риска Сэвиджа; д) на основе критерия Гурвица при  = 0,6.

Содержание слайда: Решение: а) Определим математические ожидания выигрыша игрока А при выборе им стратегии Аi: А1М1= 5·1/7 + 2·2/7+8·3/7+4·1/7 = 37/7 5,29; А2М2= 2·1/7 + 3·2/7+4·3/7+12·1/7 = 32/7 4,57; А3М3= 8·1/7 + 5·2/7+3·3/7+10·1/7 = 37/7 5,29; А4 М4= 1·1/7 + 4·2/7+2·3/7+8·1/7 = 23/7 3,29. VB-L = mах {5,29; 4,57; 5,29; 3,29} =5,29. В соответствии с этим по критерию Бейеса-Лапласа наиболее предпочтительными являются стратегии А1 и А3.

Содержание слайда: б) Если предположить, что все состояния природы равновероятны, то p1= p2= p3= =p4=1/4. б) Если предположить, что все состояния природы равновероятны, то p1= p2= p3= =p4=1/4. Определим математические ожидания выигрыша игрока А при выборе им стратегии Аi: А1 a1j /4 =(5+2+8+4)/4=19/4=4,75; А2 a2j /4=(2+3+4+12)/4=21/4=5,25; А3 a3j /4=(8+5+3+10)/4=26/4=6,5; А4 a4j /4=(1+4+2+8)/4=15/4=3,75. Поскольку VL = mах {4,75; 5,25; 6,5; 3,75}= 6,5, то по критерию Лапласа оптимальной является стратегия А3.

Содержание слайда: в) Согласно критерию Вальда в) Согласно критерию Вальда VW= mах min aij. = mах {2,2,3,1}=3 i j Следовательно максиминная стратегия игрока А - А3. г) Построим матрицу рисков.

Содержание слайда: Согласно критерию Сэвиджа определяем: Согласно критерию Сэвиджа определяем: VS=min mах r ij = min{8,6,5,7}= 5. В соответствии с этим критерием также наиболее предпочтительна стратегия А3.

Содержание слайда: д) Воспользуемся критерием Гурвица при при  = 0,6. Определим значение VH =mах {min aij+(1-)mах aij}= =mах {0,6 min aij + 0,4 mах aij}= =mах {0,6·2 + 0,4·8; 0,6·2 + 0,4·12; 0,6·3+ 0,4·10; 0,6· 1 + 0,4· 8}= mах {4,4; 6,0; 5,8; 3,8}= 6,0. Таким образом, согласно критерию Гурвица оптимальной является стратегия А2. д) Воспользуемся критерием Гурвица при при  = 0,6. Определим значение VH =mах {min aij+(1-)mах aij}= =mах {0,6 min aij + 0,4 mах aij}= =mах {0,6·2 + 0,4·8; 0,6·2 + 0,4·12; 0,6·3+ 0,4·10; 0,6· 1 + 0,4· 8}= mах {4,4; 6,0; 5,8; 3,8}= 6,0. Таким образом, согласно критерию Гурвица оптимальной является стратегия А2. Анализ результатов проведенных на основе различных критериев исследований показывает, что доминирующей является стратегия А3.