Прикладной системный анализ: сетевой анализ и календарное планирование проектов, метод прогнозного графа (стр. 15 из 18)
Назовем совокупность всех промежуточных целей, выставленных экспертом j для цели i, предпосылкой ij.
Эксперт оценивает время, необходимое для достижения цели Siпри условии, что все цели предпосылки ij уже достигнуты. Эта оценка (обозначим ее через tij), как и в методе Дельфы, предполагает возможность бесконечного значения, т. е. цель никогда не может быть достигнута. Разумеется, в этом случае предпосылка ijпредполагается пустой. Кроме того, эксперт дает качественную оценку своей компетентности (применительно к данной цели) и степени уверенности в своем прогнозе. Эти оценки переводятся в весовые коэффициенты βij и γij, произведение которых βij - γij = δijпредставляет собой вес данного единичного прогноза.
Эксперту предлагается также назвать фамилии нескольких специалистов, которых он считает целесообразным привлечь для прогноза по событию Si (i=1,2,...,m+n). Те эксперты, фамилии которых были указаны их коллегами, получают добавку Δβij к самооценке своей собственной компетентности βij тем большую, чем чаще упоминались их фамилии. Теперь необходимо для каждой цели Si определить предпосылки с набором оценок. В общем это должно выполняться периодически (например, один раз в полтора года).
Заполненные анкеты обрабатываются, строится граф соподчиненности целей. Для любого эксперта j, оценивавшего цель Si, все цели предпосылки ijсоединяются стрелками с целью Siаналогично тому, как было описано.
Построенный граф проверяется на отсутствие циклов. Если в нем оказываются петли, то их устраняют, проведя дополнительную работу с экспертами (хотя в ряде случаев можно работать и с неустранёнными петлями). Так в конце концов получается прогнозный граф.
Систематизируя полученный в результате проведения экспертизы массив исходных данных, выявляют адекватные условия, объединяют некоторые условия в одно, а также искусственно заземляют часть условий в графе, после чего начальные данные и связи в графе кодируются для машинной обработки.
Анализ прогнозного графа включает в себя:
1) поиск циклов и тупиковых событий в прогнозном графе;
2) ранжирование событий в прогнозном графе;
3) вычисление вероятностных и временных характеристик;
4) варьирование вероятностных и временных характеристик.
События в прогнозном графе (т. е. вершины его, соединенные дугами) — это проблемы (исходные и промежуточные цели) и эксперты.
Граф должен удовлетворять следующим условиям:
- в нем не должно быть событий, из которых не выходит ни одной связи, если только эти события не завершающие (имеющие пустые предпосылки ij);
- в нем не должно быть событий, в которые не входит ни одной связи, если только эти события не исходные цели (проблемы);
- в нем не должно быть замкнутых контуров, т. е. не должно быть связей, соединяющих какое-либо событие с ним же самим;
- в нем не должно быть событий, имеющих одинаковые шифры. Поэтому первое, что следует сделать при анализе графа, — выявить все ошибки, допущенные при его составлении.
Рассмотрим порядок поиска тупиковых событий и циклов. Событие, в которое не входит ни одна работа и которое не является исходным событием для данного графа, называется тупиковым событием первого рода. Событие же, из которого не выходит ни одна работа и которое не является конечным для данного графа, является тупиковым событием второго рода.
Исходная информация формируется в виде некоторого массива (событие и связи — работы), затем путем последовательного выбора кодов связи и выделения из них кодов начальных событий создается новый массив, содержащий начальные события с признаками работ, исходящих из этих событий. Наконец, выделяются конечные события, их включают в сформированный массив с признаками работ, входящих в данные события.
После пересмотра всех связей-работ входной информации сформированный массив будет включать все события графа с соответствующими признаками входящих и исходящих связей. При этом признаки тупиковых событий первого и второго рода примут, например, соответственно следующий вид: 01 и 10. Признаком кодов всех нетупиковых условий будет в этом случае сочетание 11. В результате просмотра признаков всех событий, записанных в сформированный массив, выявятся тупиковые события первого и второго рода.
Согласно данному алгоритму начальные и конечные события графа снабжены соответствующими признаками.
Допустим, имеется прогнозный граф с М вершинами и Nдугами. На вершинах m=l,2,... , М данного графа определяется функция
1, если вершина принадлежит контуру или пути, начинающемусяφ(m)= на контуре;
0, в противном случае.
Вычисляют φ(m) рекуррентным образом при пoмощи последовательности
Вспомогательных функций ψk(m) ≤ ψk-1,m=1,2,…,Mсходящейся к φ(m): ψk0(m)≡ψk0(m)≡ φ(m)при некотором конечном k0. Строится функция ψk(m) следующим образом.
Положим ψ0(m) ≡ 1, aψk-1(m) вычислена. Вычисляем ψk(m) следующим образом: последовательно просматриваем список дуг (i, j), i и j— начало и конец дуги. Если ψk-1(i) = 0, то переходим к следующей дуге. В противном случае если ψk-1(i)=1, то ψk(j)=1. Всем ψk(m), не определенным после полного просмотра списка дуг, приписывают значение 0.
Рассмотрим геометрический смысл этого рекуррентного построения. Первоначально значение ψ1(m) = l получает каждая вершина, в которую входит хотя бы одна дуга. Следовательно, ψ1(m) = 0 на тех вершинах, куда не входит ни одна дуга. Эти вершины исключаются из дальнейшего рассмотрения, так как они не могут лежать на контуре или на пути, выходящем из контура.
Граф сокращается за счет исключения дуг, выходящих из начальных вершин (т. е. вершин, не имеющих входящих в них дуг). Но в нем появляются новые начальные вершины, поскольку из графа исключаются все незамкнутые пути, выходящие из начальных вершин (т. е. мы подойдем к контуру, если он имеется в графе).
Если φ(m)=0 (т=1, 2,...,М),то контуров в графе нет. Если же φ(m)≠0, то граф содержит контуры. В этом случае строится функция:
1, если вершина принадлежит контуру или пути, начинающемусяφ*(m) = на контуре;
0, в противном случае.
Чтобы вычислить функции φ*k, нужно построить последовательность по дугам с обратной ориентацией точно так же, как последовательность ψk.
Вершины, в которых ф(т)=ф*(т)=*1, принадлежат одному из контуров.
Рассмотрим порядок ранжирования событий в графе с целью преобразования исходной информации к виду, удобному для вычисления временных и вероятностных характеристик. Используем для этого одну из модификаций стандартных способов ранжирования событий, применяемых в сетевом планировании.
Множество событий в графе разбивается на слои, начиная с уровня событий, не имеющих предпосылок i,j(так называемая «земля» — события класса ko). Событие Siпринадлежит уровню ρ, если все его предпосылки принадлежат меньшим уровням и хотя бы одна — в точности уровню ρ — 1 (ρ = 1, 2, . . . , q, . . . ), начиная с «заземленного уровня» (класс k0), q — число уровней в графе).
Вычисление временных характеристик производят по следующей формуле:
где t(Si)— время свершения события S, графа;tj — время свершения события Si согласно варианту эксперта j (j=l, 2, . . ., Ri);
Vj — вес эксперта j;
Ri — количество экспертов, оценивающих событие Si в графе (i= 1, 2, . . . , т+п).
Временные характеристики для каждого варианта (эксперта j) определяются так:
tj(Si) =max t(Sir)+tij ,
где tj(Si) — время реализации проблемы Si согласно варианту эксперта j;
t (Sir) — время свершения выдвинутых экспертом j условий SirÎj предпосылке;
tij — условное время, заданное экспертом;
Sir — событие, входящее в предпосылку i,jцели Si (r =l, 2,..., nj).
Аналогично (с незначительными изменениями) вычисляются и стоимостные характеристики.
Вероятностные характеристики рассчитывают следующим образом.
1. Вероятность свершения условий, выдвинутых Эj экспертом при наличии значения абсолютных вероятностей событий «заземленного уровня» (пустые ij — предпосылки):