Решение задач с помощью дерева решений

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО

ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Институт управления и информационных технологий

Кафедра «Экономика, организация производства и менеджмент»

Самостоятельная работа

По дисциплине: «Стратегический менеджмент»

На тему: «Решение задач с помощью дерева решений».

МОСКВА 2015

Введение

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

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

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

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

Теоретической основой и практическим инструментарием анализа и прогнозирования решений в экономике и бизнесе яв­ляются экономико-математические модели и проводимые по ним расчеты.

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

Теоретическая часть

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

Традиционно следующим этапом такого развития являются игры с природой. Отличительная особенность игры с природой состоит в том, что в ней сознательно действует только один из участников, в большинстве случаев называемый игроком 1. Игрок 2 (природа) сознательно против игрока 1 не действует, а выступает как не имеющий конкретной цели и случайным образом выбирающий очередные «ходы» партнер по игре. Поэтому термин «природа» характеризует некую объективную действительность, которую не следует понимать буквально, хотя вполне могут встретиться ситуации, в которых «игроком» 2 действительно может быть природа (например, обстоятельства, связанные с погодными ус­ловиями или с природными стихийными силами).

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

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

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

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

·         дерево управленческих решений эффективно в управлении проектами, менеджменте, а также при анализе всевозможных рисков;

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

·         в медицине дерево решений используется для диагностики заболеваний;

·         метод дерева решений применим даже для анализа строения аминокислот (молекулярная биология).

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

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

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

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

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

·         пунктирные линии, которые соединяют квадраты - возможные решения;

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

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

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

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

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

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

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

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

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

Каждый лист представляет собой значение целевой переменной, измененной в ходе движения от корня по листу. Каждый внутренний узел соответствует одной из входных переменных. Дерево может быть также «изучено» разделением исходных наборов переменных на подмножества, основанные на тестировании значений атрибутов. Это процесс, который повторяется на каждом из полученных подмножеств.

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

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

 Типология деревьев решений бывают двух основных типов:

 • Анализ дерева классификации, когда предсказываемый результат является классом, к которому принадлежат данные;

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

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

1. Деревья решений «мешок», наиболее раннее дерево решений, строит несколько деревьев решений, неоднократно интерполируя данные с заменой, и деревья голосований для прогноза консенсуса;

2. Случайный классификатор «лесной» использует ряд деревьев решений, с целью улучшения ставки классификации;

 3. «Повышенные» деревья могут быть использованы для регрессионного типа и классификации типа проблем.

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

Алгоритмы построения дерева

Общая схема построения дерева принятия решений по тестовым примерам выглядит следующим образом:

• Выбираем очередной атрибут , помещаем его в корень.

• Для всех его значений :

• Оставляем из тестовых примеров только те, у которых значение атрибута равно

• Рекурсивно строим дерево в этом потомке

Метод дерева принятия решений имеет несколько достоинств:

• Прост в понимании и интерпретации. Люди способны интерпретировать результаты модели дерева принятия решений после краткого объяснения

• Не требует подготовки данных. Прочие техники требуют нормализации данных, добавления фиктивных переменных, а также удаления пропущенных данных.

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

• Позволяет оценить модель при помощи статистических тестов. Это дает возможность оценить надежность модели.

• Является надежным методом. Метод хорошо работает даже в том случае, если были нарушены первоначальные предположения, включенные в модель.

• Позволяет работать с большим объемом информации без специальных подготовительных процедур. Данный метод не требует специального оборудования для работы с большими базами данных. Недостатки метода

 • Проблема получения оптимального дерева решений является NP- полной с точки зрения некоторых аспектов оптимальности даже для простых задач. Таким образом, практическое применение алгоритма деревьев решений основано на эвристических алгоритмах, таких как алгоритм «жадности», где единственно оптимальное решение выбирается локально в каждом узле. Такие алгоритмы не могут обеспечить оптимальность всего дерева в целом.

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

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

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

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

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

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

Методы регулирования Сокращение дерева может осуществляться сверху вниз или снизу вверх. Сверху вниз — обрезка начинается с корня, снизу вверх — сокращается число листьев дерева.

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

Практическая часть

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

Но перед тем, как принимать решение о строительстве, руководство компании должно определить, заказывать ли допол­нительное исследование состояния рынка или нет, причем пре­доставляемая услуга обойдется компании в 10 000 дол.

 Руковод­ство понимает, что дополнительное исследование по-прежнему не способно дать точной информации, но оно поможет уточнить ожидаемые оценки конъюнктуры рынка, изменив тем самым значения вероятностей.

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

Возможности фирмы в виде условных вероятностей благоприятности и неблагоприят­ности рынка сбыта представлены в табл. 1.

Например, когда фирма утверждает, что рынок благоприятный, то с вероятностью 0,78 этот прогноз оправдывается (с вероятностью 0,22 могут возникнуть неблагоприятные условия), прогноз о неблагоприят­ности рынка оправдывается с вероятностью 0,73.

Таблица 1

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

 1)ситуация будет благоприятной с вероятностью 0,45;

 2)ситуация будет неблагоприятной с вероятностью 0,55;

         3)вероятность благоприятного и неблагоприятного состояний экономичес­кой среды равна 0,5, если не проводить обследование.

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

Таблица 2

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

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

Определим средний ожидаемый выигрыш, если не проводить обследование (ОДО):

• для БП = 0,5*200 000 + 0,5*(-180 000) = 10 000 дол.;

• для МП = 0,5*100 000 + 0,5*(-20 000) =  40 000 дол.(лучший вариант);

• для П = 10 000 дол.

Определим средний ожидаемый выигрыш, если проводить обследование и прогноз благоприятный (ОДО):

• для БП = 0,78*200 000 + 0,22*(-180 000) = 116400 дол.(лучший вариант);

• для МП= 0,78*100 000 + 0,22*(-20 000) =  73600 дол.;

• для П = 10 000 дол.

Определим средний ожидаемый выигрыш, если проводить обследование  и прогноз неблагоприятный (ОДО):

• для БП = 0,27*200 000 + 0,73*(-180 000) = -77400 дол.;

• для МП = 0,27*100 000 + 0,73(-20 000) =  12400 дол.(лучший вариант);

• для П = 10 000 дол.

ОДО, если проводить обследование, то

116400*0,45+12400*0,55=59200 дол.

ОДО, если не проводить обследование, то

       49200 долларов.

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

• необходимо проводить дополнительное исследование конъ­юнктуры рынка, поскольку это позволяет существенно уточнить принимаемое решение;

• если фирма прогнозирует благоприятную ситуацию на рынке, то целесообразно строить большое предприятие (ожида­емая максимальная прибыль 116 400 дол.), если прогноз не­благоприятный - малое (ожидаемая максимальная прибыль 12 400 дол.).

Рис. 1. Дерево решений при дополнительном обследовании рынка (:   - решение (решение принимает игрок): [*] - случай (решение "принимает" случай); // - отвергнутое решение)

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

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

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

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

ОДО = 0,5 × 100 000 - 0,5 × 20 000 = 40 000 дол.

Если точная информация об истинном состоянии рынка будет благоприятной (ОДО = 200 000 дол.), принимается решение строить крупное производство; если неблагоприятной, то наиболее целесообразное решение – продажа патента (ОДО = 10 000 дол.). Учитывая, что вероятности благоприятной и неблагоприятной ситуаций равны 0,5, значение ОДОТ.И. (ОДО точной информации) определяется выражением:

ОДОТ.И. = 0,5 × 200 000 + 0,5 × 10 000 = 105 000 дол.

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

ОЦТ.И. = ОДОТ.И. – ОДО = 105 000 - 40 000 = 65 000 дол.

Значение ОЦТ.И. показывает, какую максимальную цену должна быть готова заплатить компания за точную информацию об истинном состоянии рынка в тот момент, когда ей это необходимо.

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

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

0,45*116 400 + 0,55*12 400 = 59 200,

 а максимальная денежная оценка при отсутствии точной информации равна 40 000.

Таким образом, ожидаемая ценность точной информации равна:

59 200 - 40 000 = 19 200, поэтому исследование, которое стоит 10 000 р., выгодно для фирмы. 

Заключение

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

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

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

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

Список использованной литературы

1. Ансофф И. Стратегическое управление. Пер. с англ. – М.: Экономика, 2008. – 519 с.

2. Балдин К.В. Теоретические основы принятия управленческих решений: Учеб. / К.В. Балдин, С. Н., Воробъев, В.Б. Уткин. – М. Изд – во ЕПО «МОДЭК» Московского психолого – социального института. Воронеж, 2005. – 289 с.

3. Богомолов Б.А. и др. Стратегический менеджмент и внутрифирменное планирование: Учебное пособие. – М.: Из-во МГАП «Мир книги», 2004.

4. Бойделл Т. Как улучшить управление организацией: Пособие для руководителя : Пер. с англ. - М. : ИНФРА-М-Премьер, 1995. - 200 с.

5. Вашко Т.А. Принятие управленческих решений: Учебное пособие / Т. А. Вашко; КГТЭИ. 2- е изд. переаб. И доп.. – Красноярск, 2002. - 317 с.

6. Веснин В.Р. Менеджмент. Учебное пособие. – М.: ТК Велби, изд – во Проспект, 2004. – 176 с.

7. Виханский О. С. Стратегическое управление: Учебник.-2-е изд., перераб. и доп./ О. С. Виханский. – М.: Гардарика, 1998. – 296 с.

8. Гусев Ю.В. Стратегия развития предприятий – СПб.: Издат. УЭФ, 1996. – 385 с

9. Карлоф Б. Деловая стратегия. Пер. с англ.- М.: Экономика, 1991. – 239 с.

10. Коротков Э.М. Концепция российского менеджмента: учеб. пособие / Э.М. Короткова. – М.: Дека, 2004. - 896 с.