4.1. Постановка задачи

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

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

На рис. 4.1 дан пример так называемого детерминистского дерева решений.

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

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

Рис. 4.1. Дерево решений в условиях определенности

В приведенном примере граф содержит только так называемые основные, или "решающие"вершины (рис. 4.2).

В каждую такую вершину можно попасть различными способами, что показывается наличием нескольких дуг, входящих в вершину. При этом считается, что система (объект принятия решений) находится в опреде­ленном фазовом состоянии S_h а число состояний конечно. Из вершины S, исходит несколько дуг графа, соответствующих различным решениям, которые могут быть приняты в данном состоянии. Выбор конкретной альтернативы d_{ приводит к переходу системы в новую "решающую" вершину (новое состояние).

Более сложная ситуация возникает, когда выбор конкретного решения d_t определяет не новое состояние системы, а задает некоторую лотерею на множестве возможных новых состояний (плотность распределения веро­ятности) (рис. 4.3).

Рис. 4.2. "Решающие" вершины

Рис. 4.3. Вероятностная связь вершин

Фактически в конечномерном случае (который и рассматривается) это означает, что после выбора d_} мы попадаем в некоторую "случайную" вспомогательную вершину q_tj и далее переходим в одно из возможных для данного этапа состояний S_h ..., S,„, S„ в соответствии с заданными ве­роятностями p_h ...,p_mip„ (рис. 4.3), где

/=/.....m,n

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

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

Перейдем теперь к методологии решения сформулированных много­этапных задач принятия решений.