Тема 3. Дерево решений.

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

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

3.1. Некоторые задачи принятия решений и примеры использования деревьев решений.

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

_{рынка (табл. 11).}

_{Таблица 11}

Номер стратегии	Действия компании	Выигрыш, при состоянии рынка
		благоприятном	неблагоприятном
1	крупное производство	200 000	– 180 000
2	малое предприятие	100 000	– 20 000
3	продать патент	10 000	10 000

На основе данной таблицы строим дерево решений (рис 2.).

Крупное производство ¹

благоприятное 200 000

состояние рынка

_{неблагоприятное}

_{–180 000}

	2
алое предприятие		неблагоприятное

_{благоприятное}

³

_М

100 000

Продать патент

_{Рис. 2. Дерево решений примера 5.}

–20 000

10 000

Обозначения: – решение принимает игрок, – решение «принимает»

случай, – ожидаемая денежная оценка (ОДО) исхода.

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

Определим ожидаемую денежную оценку (ОДО) каждой вершины нашего дерева. Так как нам ничего не известно о вероятности благоприятного или неблагоприятного состояния рынка, то, согласно принципу неопределенности Лапласа, примем вероятность этих исходов равной 0.5, тогда

^{• для вершины 1 ОДО}1^{=0.5×200000+0.5× (–180 000)=10000;}

^{• для вершины 2 ОДО}₂^{=0.5×100000+0.5× (–20 000)=40000.}

Таким образом, в вершине 3 целесообразно выбрать стратегию строить малое предприятие, ОДО этого (наилучшего) решения равна

40000.

Усложним пример 5.

Пусть перед принятием решения о строительстве руководство компании может обратиться к специализированной фирме, которая проведет исследование состояния рынка и уточнит вероятности исходов (за 10000 руб.). Возможности фирмы в части достоверности ее прогнозов

_{представлены в табл. 12.}

_{Таблица 12}

Прогноз фирмы	фактически
	благоприятный	неблагоприятный
благоприятный	0.78	0.22
неблагоприятный	0.27	0.73

Например, когда фирма выдает прогноз, что рынок будет благоприятный, то этот прогноз оправдывается с вероятностью 0.78.

Предположим, что фирма выдала следующий прогноз:

• рынок будет благоприятный с вероятностью 0.45;

^{• рынок будет неблагоприятный с вероятностью 0.55.}

На основании дополнительных сведений строим новое дерево решений

(рис 3.).

Крупное производство	1 благоприятное	200 000
10000	состояние рынка

₃ ^{Малое предприятие} ₂

(0,5)

неблагоприятное

(0,5) –180 000

благоприятное

_{Не проводить обследование}

40000 (0,5) 100 000

40000 неблагоприятное –20 000 (0,5)

_{Продать патент 10 000}

₄₉₂₀₀

¹¹

^{Крупное производство} ₄

благоприятное 200 000

116400 состояние рынка

(0,78)

неблагоприятное

(0,22) –180 000

_{Прогноз Малое предприятие благоприятное}

6

_{благоприятный}

73600

⁵ _{(0,78) 100 000}

(0,45) 116400 неблагоприятное –20 000 (0,22)

Продать патент

Проводить 10 000

₅₉₂₀₀

_{обследование} ¹⁰

_{– 10000}

	7
– 77400			состояние рынк
		(0,27) неблагоприятное
(0,73)

Крупное производство благоприятное 200 000

_а

_{Прогноз Малое предприятие благоприятное}

–180 000

неблагоприятный ⁹

_(0,55)

12400

⁸ _{(0,27) 100 000}

12400 неблагоприятное –20 000 (0,73)

Продать патент

_{10 000}

Рис. 3. Дерево решений при дополнительном обследовании рынка

(в скобках показаны вероятности исходов)

Определим теперь ожидаемую денежную оценку (ОДО) каждой вершины нового дерева. Как и прежде

^{• для вершины 1 ОДО}₁^{=0.5×200000+0.5× (–180 000)=10000;}

^{• для вершины 2 ОДО}₂^{=0.5×100000+0.5× (–20 000)=40000;}

^{• для вершины 4 ОДО}₄^{=0.78×200000+0.22× (–180 000)=116400;}

^{• для вершины 5 ОДО}₅^{=0.78×100000+0.22× (–20 000)=73600;}

^{• для вершины 7 ОДО}₇^{=0.27×200000+0.73× (–180 000)= – 77400;}

^{• для вершины 8 ОДО}₈^{=0.27×100000+0.73× (–20 000)=12400.}

Значит, для вершины 3 выбираем ОДО₃=40000,

для вершины 6 выбираем ОДО₆=116400,

для вершины 9 выбираем ОДО₉=12400,

тогда ОДО₁₀=0.45×116400+0.55×12400=59200,

и ОДО₁₁=59200 – 10000=49200.

Анализируя дерево решений, можно сделать следующие выводы:

• целесообразно проводить дополнительное обследование состояния рынка, ОДО этого решения равна 49200 (с учетом стоимости затрат на обследование), тогда как без обследования только 40000;

• если прогнозируется благоприятная ситуация на рынке, то необходимо строить большое предприятие (ОДО=116400), если прогноз

неблагоприятный – малое предприятие (ОДО=12400).

В условиях данного примера рассчитаем ожидаемую ценность достоверной информации (см. 2.4). При отсутствии точной информации ОДО=40000. Если точная информация о состоянии рынка будет благоприятной, то необходимо строить большое предприятие (ОДО=200000), если неблагоприятной, то целесообразно продать патент (ОДО=10000). Предполагая, до обращения к экспертам, что вероятности благоприятной и неблагоприятной ситуаций равны 0.5, вычисляем ОДО точной информации

ОДОт.и = 0.5×200000+0.5×10 000)=105000.

Тогда ожидаемая ценность достоверной информации равна

105000 – 40000=65000.

Это значение показывает, какую максимальную цену может заплатить компания за точную информацию об истинном состоянии рынка.