Книга: Прикладной системный анализ: сетевой анализ и календарное планирование проектов, метод прогнозного графа
Графически эти связи изображаются
в виде ориентированных дуг, направленных от промежуточных целей к эксперту
(выдвинувшему эти цели) и от эксперта к соответствующей исходной проблеме.
Ориентированные дуги
графа интерпретируют работы, а вершины графа — цели экспертов. Таким образом,
предварительный граф соподчиненности промежуточных целей; другими словами,
множество предварительных предпосылок для всех целей Si (i=l,2, ...,m+n) представляет собой
многоуровневую иерархическую структуру с общим числом вершин:
M=m+n+k,
где М — общее
число вершин в графе;
m+n — число исходных проблем
и промежуточных целей;
k — количество экспертов.
На следующем этапе
привлекается широкий коллектив экспертов, который разбивается на относительно
небольшие подгруппы для оценки каждой из целей S1, S2,...,Sm+n. Каждому из экспертов,
оценивающему цель Si посылается анкета с
формулировкой этой цели и списком всех ее предварительных предпосылок. Из этого
списка эксперт должен выбрать те цели, достижение которых он считает
непременным условием для достижения цели Si(i= 1,2, . . . ,m+n), и дополнить его
недостающими на его взгляд целями.
Назовем совокупность всех
промежуточных целей, выставленных экспертом 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 — число уровней в графе).
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23 |
