Деревья решений и алгоритмы их построения | DataReview.info

Главная / Публикации / Дерево решений — графическое изображение процесса принятия решений

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

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

Рисуют деревья слева направо. Места, где принимаются решения, обозначают квадратами □, места появления исходов — кругами ○,возможные решения — пунктирными линиями ———, возможные исходы — сплошными линиями ——.

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

Пример 1. Главному инженеру компании надо решить, монтировать или нет новую производственную линию, использующую новейшую технологию. Если новая линия будет работать безотказно, компания получит прибыль 200 млн. рублей. Если же она откажет, компания может потерять 150 млн. рублей. По оценкам главного инженера, существует 60% шансов, что новая производственная линия откажет. Можно создать экспериментальную установку, а затем уже решать, монтировать или нет производственную линию.

Эксперимент обойдется в 10 млн. рублей. Главный инженер считает, что существует 50% шансов, что экспериментальная установка будет работать. Если экспериментальная установка будет работать, то 90% шансов зато, что смонтированная производственная линия также будет работать. Если же экспериментальная установка не будет работать, то только 20% шансов за то, что производственная линия заработает. Следует ли строить экспериментальную установку? Следует ли монтировать производственную линию? Какова ожидаемая стоимостная оценка наилучшего решения?

В узле F возможны исходы «линия работает» с вероятностью 0,4 (что приносит прибыль 200) и «линия не работает» с вероятностью 0,6 (что приносит убыток -150) => оценка узла F. EMV( F) = 0,4 x 200 + 0,6 х ( -150) = -10. Это число мы пишем над узлом F.

EMV(G) = 0.

В узле 4 мы выбираем между решением «монтируем линию» (оценка этого решения EMV( F) = -10) и решением «не монтируем линию» (оценка этого решения EMV(G) = 0): EMV(4) = max {EMV( F), EMV(G)} = max {-10, 0} = 0 = EMV(G). Эту оценку мы пишем над узлом 4, а решение «монтируем линию» отбрасываем и зачеркиваем.

Аналогично:

EMV( B) = 0,9 х 200 + 0,1 х (-150) = 180 — 15 = 165.

EMV(С) = 0.

EMV(2) = max {EMV(В), EMV(С} = max {165, 0} = 165 = EMV(5). Поэтому в узле 2 отбрасываем возможное решение «не монтируем линию».

EM V(D) = 0,2 х 200 + 0,8 х (-150) = 40 — 120 = -80.

EMV( E) = 0.

EMV(3) = max {EMV(D), EMV(E)} = max {-80, 0} = 0 = EMV( E). Поэтому в узле 3 отбрасываем возможное решение «монтируем линию».

ЕМ V( A) = 0,5 х 165 + 0,5 х 0 — 10 = 72,5.

EMV(l) = max {EMV(A), EMV(4)} = max {72,5; 0} = 72,5 = EMV( A). Поэтому в узле 1 отбрасываем возможное решение «не строим установку».

Ожидаемая стоимостная оценка наилучшего решения равна 72,5 млн. рублей. Строим установку. Если установка работает, то монтируем линию. Если установка не работает, то линию монтировать не надо.

Пример 2. Компания рассматривает вопрос о строительстве завода. Возможны три варианта действий.

A. Построить большой завод стоимостью M1 = 700 тысяч долларов. При этом варианте возможны большой спрос (годовой доход в размере R1 = 280 тысяч долларов в течение следующих 5 лет) с вероятностью p1 = 0,8 и низкий спрос (ежегодные убытки R2 = 80 тысяч долларов) с вероятностью р2 = 0,2.

Б. Построить маленький завод стоимостью М2 = 300 тысяч долларов. При этом варианте возможны большой спрос (годовой доход в размере T1= 180 тысяч долларов в течение следующих 5 лет) с вероятностью p1 = 0,8 и низкий спрос (ежегодные убытки Т2 = 55 тысяч долларов) с вероятностью р2 = 0,2.

B. Отложить строительство завода на один год для сбора дополнительной информации, которая может быть позитивной или негативной с вероятностью p3 = 0,7 и p4 = 0,3 соответственно. В случае позитивной информации можно построить заводы по указанным выше расценкам, а вероятности большого и низкого спроса меняются на p 5 = 0,9 и р6 = 0,1 соответственно. Доходы на последующие четыре года остаются прежними. В случае негативной информации компания заводы строить не будет.

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

Ожидаемая стоимостная оценка узла А равна ЕМ V(А) = 0,8 х 1400 + 0,2 х (-400) — 700 = 340.

EMV( B) = 0,8 х 900 + 0,2 х (-275) — 300 = 365.

EMV( D) = 0,9 x 1120 + 0,1 x (-320) — 700 = 276.

EMV(E) = 0,9 x 720 + 0,1 х (-220) — 300 = 326.

EMV(2) = max {EMV( D), EMV( E)} = max {276, 326} = 326 = EMV( E). Поэтому в узле 2 отбрасываем возможное решение «большой завод».

EMV( C) = 0,7 x 326 + 0,3 x 0 = 228,2.

EMV(1) = max {ЕМ V( A), EMV(B), EMV( C)} = max {340; 365; 228,2} = 365 = EMV( B). Поэтому в узле 1 выбираем решение «маленький завод». Исследование проводить не нужно. Строим маленький завод. Ожидаемая стоимостная оценка этого наилучшего решения равна 365 тысяч долларов.

Задание 1. Компания рассматривает вопрос о строительстве завода. Возможны три варианта действий.

A. Построить большой завод стоимостью M1, = 650 тысяч долларов. При этом варианте возможны большой спрос (годовой доход в размере R1 = 300 тысяч долларов в течение следующих 5 лет) с вероятностью р 1 = 0,7 и низкий спрос (ежегодные убытки R2 = 85 тысяч долларов) с вероятностью p2 = 0,3.

Б. Построить маленький завод стоимостью М 2 = 360 тысяч долларов. При этом варианте возможны большой спрос (годовой доход в размере T1, = 120 тысяч долларов в течение следующих 5 лет) с вероятностью р 1 = 0,7 и низкий спрос (ежегодные убытки Т2 = 60 тысяч долларов) с вероятностью р2 = 0,3.

B. Отложить строительство завода на один год для сбора дополнительной информации, которая может быть позитивной или негативной с вероятностью р 3 = 0,9 и р4 = 0,1 соответственно. В случае позитивной информации можно построить заводы по указанным выше расценкам, а вероятности большого и низкого спроса меняются на р5 = 0,8 и р6 = 0,2 соответственно. Доходы на последующие четыре года остаются прежними. В случае негативной информации компания заводы строить не будет.

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

Ответ: Нужно строить большой завод. 272,5 тысяч долларов.

Г.И. Просветов,

Cм. также

Управление бизнесом

Выработка управленческих решений

Реорганизация системы управления финансами

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

Творческие методы разработки управленческих решений

Базовые концепции финансового менеджмента

Подписка на новости

Подпишись и узнай о самых интересных новостях мира бизнеса

Подписаться

Дерево решений

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

Метод построения дерева решений

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

Применение дерева решений

Дерево решений – это популярный метод, применяющийся в самых разнообразных сферах нашей жизни:

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

Как же построить дерево решений?

1. Как правило, дерево решений располагается справа налево и не содержит циклических элементов (новый лист или ветвь могут только расщепляться).

2. Необходимо начать с отображения структуры проблемы в «стволе» будущего дерева решений (справа).

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

Ветви бывают двух видов:

  • пунктирные линии, которые соединяют квадраты — возможные решения;
  • сплошные линии, соединяющие кружки возможных конечных результатов.

4. Узлы — это ключевые события, а линии, соединяющие узлы – это работы по реализации проекта. Квадратные узлы – это места, где решение принимается. Круглые узлы – появление результатов. Поскольку, принимая решения, мы не можем влиять на появление исхода, нам нужно вычислить вероятность их появления.

5. Помимо этого, на дереве решений необходимо отобразить всю информацию о времени работ, их стоимости, а также вероятности принятия каждого решения;

6. после того, как все решения и предполагаемые результаты будут указаны на дереве, проводится анализ и выбор наиболее выгодного пути.

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

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

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

 

Статьи по теме:

Как стать душой компании?

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

Метод «дерево решений»

Источники вдохновения

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

Как избавиться от интернет-зависимости?

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

Как избавиться от комплексов?

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

.

Дерево решений

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

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

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

Принятие решений с помощью дерева возможных вариантов производится поэтапно:

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

Еще интересное: Дерево решений в теории игр,
Найти ветку поудобнее: изучаем дерево решений

Примеры решений задач: Дерево решений

Задача 1. Вы рассматриваете перспективы создания новой консалтинговой службы. Объем необходимых вложений на начальном этапе $200 тыс. Существует 60%-ная вероятность, что спрос будет высоким в 1-й год. Если спрос будет высоким в первый год, то в последующие годы вероятности высокого и низкого спроса составят 80% и 20% соответственно. Если спрос будет низким в 1-й год, то в последующие годы вероятности высокого и низкого спроса составят 40% и 60% соответственно.

Дерево решений

При высоком спросе прогнозируемые доходы составят 500 тыс. дол. в год; при низком спросе прогнозируемые доходы равны 300 тыс. дол. в год. Вы можете прекратить предоставлять услуги в любой момент. Затраты, помимо связанных с использованием компьютера, прогнозируются в размере 140 тыс. дол. в год, вне зависимости от уровня спроса.

Если Вы решите не вкладывать деньги в консалтинговую службу, то сможете вложить их на практически безрисковой основе под 20% в год.
Если будет решено организовать консалтинговую службу, Вам необходимо будет решить вопрос с проведением компьютерных расчетов, составляющих основу деятельности. Один возможный вариант — купить сервер.
Срок морального устаревания его 5 лет. Затраты будут состоять из первоначальных расходов в размере 150 тыс. долларов и ежегодных расходов на эксплуатацию в размере 20 тыс.
Альтернативный вариант — арендовать компьютерные ресурсы по мере необходимости. В этом случае затраты на аренду будут пропорциональны спросу и составят 30% доходной части за вычетом оговоренных постоянных расходов в 140 тыс. Во всех случаях никаких других издержек нет.

a. Постройте «древо решений», иллюстрирующее эти варианты и охватывающее 3 года.
b. Стоит организовать консалтинговую службу или безрисковый доход выгоднее? Рассмотрите итоги деятельности за два и три года.
c. Что лучше — купить компьютер или арендовать?
d. Предположим, что после 3 лет деятельности вы сможете продать службу, как отдельный бизнес в среднем за 350 тыс. долларов. Какому ежегодному проценту прироста соответствует полученный вами доход?
e. Четко сформулируйте любые дополнительные допущения, которые вам потребуется сделать.

Принятие решений о вложении денег

Задача 2. Фермер может выращивать либо кукурузу, либо соевые бобы. Вероятность того, что цены на будущий урожай этих культур повысятся, останутся на том же уровне или понизятся, равна соответственно 0,25, 0,30 и 0,45. Если цены возрастут, урожай кукурузы даст 30 000 долл. чистого дохода, а урожай соевых бобов — 10 000 долл. Если цены останутся неизменными, фермер лишь покроет расходы. Но если цены станут ниже, урожай кукурузы и соевых бобов приведет к потерям в 35 000 и 5 000 долл. соответственно. Постройте дерево решений. Какую культуру следует выращивать фермеру? Каково ожидаемое значение его прибыли?

Дерево решений в задаче фермера (Excel)

Задача 3. Предприятие рассматривает варианты капитальных вложений. Первый вариант предусматривает строительство нового цеха для увеличения объема выпуска продукции стоимостью М1 = 500 млн. руб. При этом варианте возможны большой спрос (годовой доход в размере R1 = 230 млн. руб. в течение 5 последующих лет) с вероятностью p1 = 0,7 и низкий спрос (ежегодные убытки R2 = 90 млн. руб. с вероятностью p2 = 0,3.
Второй вариант предусматривает создание нового предприятия для выпуска новой продукции Стоимостью М1 = 700 млн. руб. При этом варианте возможны большой спрос (годовой доход в размере R1 = 450 млн. руб. в течение 5 последующих лет) с вероятностью p1 = 0,6 и низкий спрос (ежегодные убытки R2 = 150 млн. руб. с вероятностью p2 = 0,4.
При третьем варианте предлагается отложить инвестиции на 1 год для сбора дополнительной информации, которая может быть позитивной или негативной с вероятностью p1 = 0,8 и p2 = 0,2 соответственно. В случае позитивной информации можно осуществить инвестиции по указанным выше расценкам, в вероятности большого и низкого спроса меняются на p1 = 0,9 и p2 = 0,1 соответственно. Доходы на последующие годы остаются на том же уровне. В случае негативной информации инвестиции осуществляться не будут.
Все расчеты выражены в текущих ценах и не должны дисконтироваться. Нарисовать дерево решений. Определить наиболее эффективную последовательность действий, основываясь на ожидаемых доходах. Какова ожидаемая стоимостная оценка наилучшего решения?

Дерево решений в задаче капиталовложений

Задача 4. Рассматривается проект покупки доли (пакета акций) в инвестиционном проекте. Пакет стоит 7 млн., и по завершению проект принесет доход 12 млн. с вероятностью 0,6 или ничего с вероятностью 0,4.
При этом через некоторое время будет опубликован прогноз аналитической фирмы относительно успеха этого проекта. Прогноз верен с вероятностью 0,7, то есть, равны 0,7 условные вероятности.
Однако, в случае положительного прогноза пакет порождает до 10,6 млн., а в случае отрицательного подешевеет до 3,4 млн. Требуется составить стратегию действий: покупать ли долю, или ждать прогноза, и совершать ли покупку при том или ином результате прогноза.

Задача покупки акций

Задача 5. Компания «Большая нефть» хочет знать, стоит ли бурить нефтяную скважину на одном из участков, купленных ранее в перспективном месте.

Бурение, проведенное на множестве соседних участков, показало, что перспективы не так уж хороши. Вероятность найти нефть на глубине не больше 400 м составляет около 50%. При этом стоимость бурения составит 1.5 млн., а стоимость нефти, за вычетом всех расходов, кроме расходов на бурение, составит 6 млн. Если нефть не найдена на малой глубине, не исключена возможность найти ее при более глубоком бурении. Расходы на бурение, вероятность найти нефть и приведенная стоимость нефти для этих случаев даны в таблице.
a. Постройте дерево решений, показывающее последовательные решения о разработке скважины, которые должна принять компания «Большая нефть». На какую среднюю прибыль компания может рассчитывать?
b. Скважину какой глубины нужно быть готовыми пробурить? (Стоит ли остановиться при достижении определенной глубины, или бурить до предельной глубины?)
c. Какова вероятность найти нефть при бурении (при необходимости) до выбранной вами предельной глубины? Какова полная вероятность найти нефть при готовности бурить до 1500 м?

Дерево решений для нефтедобычи

Примеры по ЭМММ бесплатно

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *