3.2. НЕОБХОДИМЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ МНОГОШАГОВЫХ ПРОЦЕДУР ПРИНЯТИЯ РЕШЕНИЙ

Многошаговыми процедурами принятия решения буде называть такие процедуры, в которых решение об исследуемом процессе (явлении) принимается по результатам нескольких (многих) шагов по заранее выбранному правилу в случайный момент времени [76]. Если число шагов для принятия решения заранее не ограничено, то такие процедуры назовем неусеченными многошаговыми процедурами принятия решений, в противном случае — усеченными. Если многошаговая процедуры позволяют принять только одно решение («да» имеем многошаговые процедуры с единственным решение Если же можно выносить как решение «да», так и решен «нет», то это процедуры с двойным решением.

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

решение «да», если на v смежных шагах впервые появятся ровно k единиц

Чтобы критерий принятия решения был точно определен, кроме задания двух чисел (k и ), необходимо сформулировать три правила: начала процесса принятия решения (1), окончания процесса принятия решения (2) и возврата процесса принятия решения в исходное состояние (3):

1. Процесс принятия решения начинается при появлении в последовательности нулей первой единицы; при этом цепь Маркова из исходного состояния перейдет в первое рабочее состояние

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

3. Процесс принятия решения возвращается в исходное состояние когда впервые после единицы число нулей станет равным

Сформулированные правила позволяют непосредственно перейти к синтезу цепей Маркова. Изобразим геометрически процесс принятия решения с помощью обобщенного графа [76], на котором вершины (состояния) пронумерованы для удобства построения конкретных графов (соответствующих заданным числам k и ). Числа около вершин означают количество путей (траекторий), которыми можно попасть в указанную вершину из состояния (из вершины с номером 1). Нетрудно видеть, что указанное число путей может быть вычислено с помощью известного треугольника Паскаля [46]. На рис. 3.1 стрелкой вверх символически обозначен результат принятия решения «да» на очередном шаге (вероятность этого события равна ); стрелкой вниз — результат принятия решения «нет» на очередном шаге. Вероятность этого события равна

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

Рис. 3.1. Обобщенный граф процесса принятия решения с помощью неусеченных многошаговых процедур с единственным решением

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

Число «2» в последней формуле получается из-за того, что берется дополнительно («вне» высекаемого подграфа) как исходное состояние так и последнее

В качестве примера рассмотрим синтез ориентированного стохастического графа критерия Критерий означает, что для принятия решения «да» достаточно появления (после состояния т. е. после вершины с номером 1) одной единицы. Для возвращения процесса в состояние достаточно появления двух нулей. События, реализующие критерий символически могут быть описаны как [3] (рис. 3.2).

При попадании процесса принятия решения в последнее состояние процесс обнаружения заканчивается принятием решения «да». При этом возникает вопрос: каков исход из этого последнего состояния Ответ зависит от существа рассматриваемых задач. Если нас интересуют вероятностно-временные характеристики первого попадания процесса в состояние то это состояние удобно сделать поглощающим [76, 83]. В дальнейшем так и будем поступать.

На рис. 3.3 показан развернутый в линию граф критерия с последним поглощающим состоянием, из которого следует матрица вероятностей переходов процедуры

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

Из комбинаторных соображений следует, что число событий реализующих критерий определяется формулой Например, для критерия

Рис. 3.2. Синтез ориентированного стохастического графа критерия (2/3)

Рис. 3.3. Стохастический граф критерия (2/3)

В табл. 3.1 и 3.2 приведены значения и для наиболее часто встречающихся критериев.

Таблица 3.1

Таблица 3.2

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

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

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

Трактуя процесс принятия решения как поглощающую цепь Маркова, имеем уже два поглощающих состояния. Решение «нет» будем соотносить с предпоследним поглощающим состоянием; решение же «да» — с последним поглощающим состоянием

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

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

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

Перейдем к синтезу ориентированных стохастических графов и матриц переходных вероятностей процедур

Сначала покажем, как из обобщенного графа процесса

Рис. 3.4. Обобщенный граф процесса принятия решения с помощью усеченных многошаговых процедур с двойным решением

принятия решения получить ориентированный стохастический граф любого критерия

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

Для этого из обобщенного графа выделяем подграф (в направлении вправо-вниз), каждая ветвь которого имеет ровно переходов, соответствующих появлению нуля.

Далее с полученным подграфом поступаем следующим образом: стрелки, идущие вверх, «замкнем» на последнее поглощающее состояние (решение «да»); стрелки, идущие вниз, — на предпоследнее поглощающее состояние (решение «нет»). Разворачивая полученный подграф в линию, получим исходный линейный граф. Из способа получения подграфа вытекает, что результирующий граф имеет минимальное число состояний

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

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

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

Общее число событий, реализующих процедуру равно сумме (3.2.4) и (3.2.5); т.. е.

В табл. 3.3 и 3.4 приведены значения для наиболее часто встречающихся процедур

Таблица 3.3

Таблица 3.4

Приведем пример синтеза графа для На рис. 3.5 показан процесс получения ориентированного стохастического графа критерия На рис. 3.6 развернутый в линию граф критерия для , из которого следует матрица вероятностей переходов критерия

Рис. 3.5. Синтез ориентированного стохастического графа критерия

Рис. 3.6. Стохастический граф критерия