Лекции по «Теория принятия решений»

• оценка полезности доступных действий

• определение вероятности каждого неопределенного (имеющего вероятностную природу) события

В качестве основного  формального математического инструмента рассматриваемого метода используется так называемое «дерево решений» (диаграмма решений).

«Дерево решений» - это граф, содержащий вершины двух типов. К первому типу относятся вершины, которые соответствуют моментам принятия некоторых частных решений человеком (эти вершины будем обозначать квадратиками), к другому типу - вершины, соответствующие проявлению случайной природы некоторых событий (эти вершины будем обозначать кружочками).

Можно использовать другое определение, дополняющее первое. «Дерево целей» - это структура задачи в виде хронологически увязанных выборов (моментов принятия решений), которые должен делать человек, решающий задачу на принятие решений, и выборов, определяемых случаем (случайным механизмом).

Продемонстрировать использование рассматриваемого метода и его основного рабочего инструмента - «дерево целей» можно на примере типовой задачи, сформулированной в терминологии урн (терминология, привычная в теории вероятностей).

Имеется N урн, каждая из которых может быть одного из двух типов - Q1 или Q2. Известно, что 80% урн принадлежат к типу Q1, и 20% урн - к типу Q2.

В каждой урне находятся 10 шаров (красные и черные). Распределение красных и черных шаров различно в зависимости от типа урны - в урнах типа Q1   4 красных и 6 черных шаров, в урнах типа Q2  9 красных и 1 черный шар.

Человеку предлагается сыграть в игру. Он случайным образом  выбирает одну из N  урн, и должен решить, к какому типу принадлежит выбранная им урна.

Если человек угадывает тип урны, то он выигрывает некоторую сумму денег, если не угадывает - проигрывает.

У участника игры имеются варианты получить некоторую информацию перед тем, как определить тип урны. За дополнительную плату (8 единиц) можно случайным образом вынуть 1 шар из выбранной урны. За дополнительную плату в 12 единиц можно вынуть 2 шара из выбранной урны. За дополнительную плату в 9 единиц можно вынуть 1 шар и решить вынуть ли ещё один шар за 4.5 единиц. При этом шар, вынутый первым, может быть возвращен в урну или нет (возможны варианты) и т.д.

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

• отказаться от игры

• без дополнительной информации определить тип урны

(решение ЕО)

• вынуть один шар из выбранной урны и после этого  определить тип урны (решение Е1)

• вынуть два шара из выбранной урны и после этого  определить тип урны (решение Е2)

• вынуть один шар из выбранной урны и решить, выбирать ли ещё один шар. После получения  необходимой информации определить тип урны (решение ЕЗ).

Если участник игры определяет тип урны Q1, то он выигрывает 40 единиц в случае «истинности», и проигрывает 20 единиц в случае «ложности» утверждения.

Если участник игры определяет тип урны Q2, то он выигрывает 100 единиц в случае истинности, и проигрывает 5 единиц в случае «ложности» утверждения.

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

P(Q1) - вероятность выбора урны типа Q1, (P(Q1) = 0.8)

P(Q2) - вероятность выбора урны типа Q2, (P(Q2) = 0.2)

P(R/Q1) - вероятность выбрать красный шар при условии выбора урны типа Q1 (P(R/Q1) = 0.4)

P(B/Q1) - вероятность выбрать черный шар при условии выбора урны типа Q1 (P(B/Q1) = 0/6)

P(R/Q2) - вероятность выбрать красный шар при условии выбора урны типа Q2 (P(R/Q2) = 0.9)

P(B/Q2) - вероятность выбрать черный шар при условии выбора урны типа Q2 (P(B/Q2) = 0.1)   

Нам необходимо определить ещё четыре величины:

P(Q1/R), P(Q1/B), P(Q2/R), P(Q2/B), соответственно вероятности выбора урны типа Ql (Q2) при условии, что был вынут красный (черный) шар. Эти вероятности не заданы, их можно найти с помощью известной формулы Байеса.

P(Q1/R) = P(Q1)*P(R/Q1) / (P(Q1)*P(R/Q1)+P(Q2)*P(R/Q2)) =

= 0.8*0.4 / (0.8*0.4 + 0.2*0.9) = 0.64

P(Q1/B) = P(Q1)*P(B/Q1) / (P(Q1)*P(B/Q1)+P(Q2)*P(B/Q2) =

= 0.8*0.6 / (0.8*0.6 + 0.2*0.1) = 0.96

P(Q2/R) = P(Q2)*P(R/Q2) / (P(Q1)*P(R/Q1)+P(Q2)*P(R/Q2)) =

= 0.2*0.9 / 0.5 = 0.36

P(Q2/B) = P(Q2)*P(B/Q2) / (P(Q1)*P(B/Q1)+P(Q2)*P(B/Q2)) =

= 0.2*0.1 / 0.5 = 0.04

По известной формуле  полной вероятности определим значение безусловной вероятности достать красный (черный) шар:

P(R ) = P(Q1)*P(R/Q1) + P(Q2)*P(R/Q2) =

= 0.8*0.4 + 0.2*0.9 = 0.5

P(B) = 0.5.

Следует иметь в виду, что равенство вероятностей P(R ) и Р(В) определяется нашими исходными данными (при других исходных данных равенства, естественно, не будет).

3. Игровые методы обоснования решений

 

Особый, очень большой  и разнообразный класс составляют задачи на принятие решений в условиях неопределенности, когда имеется сознательное противодействие «противника». Эти задачи характеризуются тем, что в них участвуют две или более конкурирующих   стороны,   преследующие   противоположные   цели (конфликтные ситуации).

Методы решения таких  задач достаточно сложны и рассматриваются в специальном разделе математики - Теория игр.

Введем некоторые понятия  и определения:

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

Правила игры регламентируют:

• возможные варианты действия игроков

• объем информации каждой стороны о поведении другой стороны

• результат игры, к  которому приводит любая совокупность ходов (чаще всего результат игры характеризуется числовой величиной)

Игра развивается во времени, т.е. имеется последовательность действий игроков (игроки делают свои ходы).

Ход - выбор одного из предусмотренных правилами игры действий и его осуществление.

Различают личные и случайные ходы.

Личный ход - сознательный выбор одного из возможных действий и его осуществление.

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

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

Если число стратегий  конечное, то считается, что игра - конечная.

Оптимальная стратегия - стратегия, которая при многократном повторении игры обеспечивает данному игроку максимально возможный средний выигрыш (минимально возможный средний проигрыш).

 

2.1. Платежная  матрица

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

Рассмотрим конечную игру, в которой участвуют два  игрока А и В. Игрок А имеет m стратегий (Al, A2, ..., Am), а игрок В - n стратегий (Bl, B2, ..., Вn).

Предположим, что при  выборе игроком А стратегии Ai и игроком В стратегии Bj игрок А получает выигрыш aij. Тогда можно составить платежную матрицу, в которой строки соответствуют стратегиям игрока А, столбцы - стратегиям игрока В, а элементы матрицы - соответствующим выигрышам игрока А.

 

	B1	B2	…	Вn
A1	a11	а12	...	а1n
A2	а21	а22	…	а2n
...	...	...	...	...
Am	am1	аm2		аmn

 

Рассмотрим простой пример (Игра «поиск»).

Игрок А - прячется, игрок  В - ищет игрока А. В распоряжении игрока А есть два убежища. Если игрок В «находит» игрока А (с одной попытки), то игрок А платит ему 1 руб. Если Игрок В не «находит» игрока А, то он платит игроку А 1руб. Платежная матрица для такой игры будет иметь вид:

 

	B1	B2
A1	-1	1
A2	1	-1

 

Анализ этой простой  игры показывает, что, используя платежную матрицу, можно получить далеко нетривиальные выводы:

• если играть только один раз, то вообще нельзя говорить об оптимальной стратегии

• если играть многократно, то игроку А нельзя придерживаться какой-либо одной стратегии или чередовать их в каком-либо определенном порядке. В этом случае игрок В со временем поймет закономерность использования стратегий и начнет постоянно выигрывать.

• игроку А необходимо использовать случайный механизм выбора стратегий (стратегии A1 и A2 должны быть равновероятны).

В нашем примере игрок  А должен использовать «смешанную стратегию», когда отдельные чистые стратегии (Al, A2) чередуются случайным образом.

Пример 2. (Игра «Пальцы»).

Игроки А и В «выбрасывают»  одновременно до 3-х (1, 2 или 3) пальцев. Игрок  А выигрывает (величина выигрыша равна сумме «выброшенных» пальцев), если сумма четная и соответственно проигрывает, если сумма - нечетная.                                                              Для данной игры платежная матрица имеет вид:

 

	В1	В2	В3
A1	2	-3	4
A2	-3	4	-5
A3	4	-5	6

 

Анализ этой платежной  матрицы позволяет заключить:

• для каждой стратегии  игрока А у игрока В есть лучшая стратегия (для A1 - В2, для A2 - ВЗ, для A3 - В2)

• аналогично у игрока А есть лучшая стратегия игры против игрока В

• игрокам А и В  необходимо пользоваться «смешанными  стратегиями»

 

2.2. Нижняя и верхняя цена игры. Принцип минимакса

Рассмотрим некоторую игру, определяемую нижеприведенной платежной матрицей, и рассмотрим случай использования в этой игре «чистых» стратегий.

 

	В1	В2	...	Вn
A1	a11	а12		а1n
A2	а21	а22		а2n
...
Am	am1	аm2		аmn

 

Дополним платежную  матрицу столбцом с элементами a₁, a₂, …, a_m, где    a_i = min a_ij     (минимизация по j) и строкой с элементами     b₁, b₂, …, b_n,

где b_j = max a_ij.минимизация по i ).

a = max a_i  или  a = max min a_ij - нижняя цена игры - так называемый максимин.

Оказывается, что при  любом поведении игрока В игрок  А имеет выигрыш не меньший, чем a. Таким образом a это оценка снизу для результата игры игрока А, если в игре используются «чистые» стратегии.

Аналогичные рассуждения можно провести для игрока В и ввести     

  b = min b_j     или      b = min max a_ij  - называют минимакс или верхняя цена игры. Придерживаясь «чистой» стратегии, соответствующей минимаксу, игрок В может быть уверен, что проиграет не больше  b.

Принцип, определяющий игрокам  выбор максиминной и минимаксной стратегий, называется принципом минимакса.

Рассмотрим игру, характеризующуюся  «платежной матрицей»:

 

	В1	В2	ВЗ
А1	2	-3	4	-3
А2	-3	4	-5	-5
A3	4	-5	6	-5
	4	4	6