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

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

Д.р. применяется тогда, когда количество альтернатив и количество шагов принятия решений ограниченно (конеч­но). Принцип использования этого метода покажем на простом примере.

Предположим, возникла необходимость построить цех для выпуска новой продукции. Можно построить большой цех — мощностью 200 тыс. т продукции в год и стоимостью 1 млрд. руб. Если спрос на продукт будет большой, завод получит прибыль в 1 млрд. руб., строительство цеха окупится за год. Но если спрос будет меньше, допустим, только на 100 тыс. т, то прибыль составит уже лишь 500 млн. руб.: если же товар совсем «не пойдет», завод понесет убытки в 1 млрд. руб.

Возникает второй вариант: строить меньший цех — мощностью 100 тыс. т и стоимостью 500 млн. руб. Тогда при высоком и малом спросе прибыль будет равна 500 млн руб., а при отсутствии спроса убыток составит 500 млн руб. Все это можно показать на схеме (рис.Д.2).

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

Но задача осложнится еще больше, если сформулировать ее иначе: спрос на продукцию будет, как предполагается, расти постепенно. Что при этом лучше: строить сразу большой цех или же малый, но через некоторое время (если спрос действительно окажется большим) реконструировать его? Такие задачи также решаются методом Д.р. Приведенный пример характерен для структуры задач динамического программирования с конечным числом решений. Как видим, здесь сначала осуществлялся выбор последнего по времени решения, а затем, при движении в направлении, обратном течению времени, выбирались все остальные решения вплоть до исходного (см. Беллмана принцип оптимальности).

Рис. Д.2  Дерево решений

Спрос: б — большой, м — малый, о — отсутствие спроса