Прикладной системный анализ - сетевой анализ и календарное планирование проектов, метод прогнозного графа

- в нем не должно быть замкнутых контуров, т. е. не должно быть связей, соединяющих какое-либо событие с ним же самим;

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

Рассмотрим порядок поиска тупиковых событий и циклов. Событие, в которое не входит ни одна работа и кот

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

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

После пересмотра всех связей-работ входной информации сформированный массив будет включать все события графа с соответствующими признаками входящих и исходящих связей. При этом признаки тупиковых событий первого и второго рода примут, например, соответственно следующий вид: 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 — предпосылки):

Pэj (Sir) =P(Si1 Λ Si2 Λ … Λ Sinj)=pi1 · pi2 ·… ·pinj ,

где pi1 , pi2 ,… ,pinj — абсолютные вероятности свершения отдельных условий, выдвинутых экспертом j;

nij — количество условий, выдвинутых j-м экспертом; Pэj (Sir) — вероятность выполнения ij предпосылки.

2. Pэj (Sir) — вероятность свершения события Si анализируемого экспертом j при предпосылке ij;

pij — условная вероятность, выставленная Эj экспертом:

pэj (Si)= pэj (Sir) pij .

3. Для всех пар экспертов определяются условные вероятности:

где p(Эp/Эl) вычисляется по общим формулам теории вероятностей. Например:

Si=(Э1 (S2 , S3 , S4) , Э2 (S3 , S4, S5) ) ;

p (Э1 Λ Э2) =p ( (S2 Λ S3 Λ S4) Λ (S3 Λ S4 Λ S5) ) = p(S2Λ S3 Λ S4Λ S5) =

= p2 ·p3 ·p4 ·p5;

Если для какой-либо пары экспертов p(Эр / Эl) или р(Эl/Эр) ≥0,5, то производится усреднение вероятностей по формуле:

V рÚ l = min(Vр, Vl)

(p, l = 1, 2, … ,k).

После этого присваивается

p(Эp), если p(Эp/Эl)£ р(Эl/Эр) ;

 Скачать реферат