Консалтология Общая теория консалтинга (стр. 27 )

2. Строится полная матрица связей. Последовательным перебо­ром оставшихся вершин определяем, удаление каких именно из них нарушит связность графа.

Как видно, операция нахождения множества сочленения весьма трудоемка. Однако, если рассматривать реальные КП, которые имеют ограниченное число входов и выходов, то размерность зада­чи значительно уменьшится. Поэтому, определяя связность графа и условия ее нарушения, не имеет смысла рассматривать возмож­ность соединения любых двух вершин, а следует ограничиться лишь входами и выходами. Так, в приведенном примере (рис. 8.21) строго к множеству сочленения относятся элементы у2, у3, у4. Если же входом и выходом являются элементы х1 и х5 соответственно, то ко множеству сочленения достаточно отнести элементы у3 и y4.

На рис. 8.22 представлена структура более слож­ной КП. Здесь две подпроблемы А и В связаны системой различных связей. Необходимо определить, удаление ка­ких связей разрушит структуру КП.

Рис. 8.22. Граф структуры сложной КП

Придерживаясь описанного порядка и проделав все необходи­мые операции, определим, что к множеству сочленения во вспомо­гательном графе (рис. 8.23) относятся вершины 6, 7, 13. Следова­тельно, разрушение связей (ребер основного графа) 8, 7, 13 разор­вет и нарушит цепь функциональных связей между подпроблемами А и В.

Рис. 8.23. Вспомогательный граф сложной КП

В заключение следует отметить, что множество сочленения, как структурный параметр, не вводит упорядочение в проблему отноше­ний. Принадлежность к нему отвечает лишь на вопрос о возмож­ности разрушения этой проблемы отношений.

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

Когда проблема отношений отражает взаимные влияния элемен­тов друг на друга, то необходимо стремиться, чтобы к множеству сочленения принадлежало как можно меньшее число элементов. Достаточно изъять их, и вся система взаимных влияний нару­шится.

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

8.16. Декомпозиция структуры консультируемой проблемы

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

Процесс декомпозиции КП можно формализовать сокраще­нием ориентированного графа. Тогда для КП можно рекомендо­вать следующий алгоритм декомпозиции.

1. Составить матрицу смежности А графа G (X,U).

2. Вычислить матрицу R1 = А+ Е, где Е — единичная мат­рица; «+» — знак логического сложения; R1 — матрица первой достижимости, i - я строка которой представляет все ориентирован­ные пути по графу из i-й вершины до всех остальных, если длина пути равна одному ребру.

3. Определить R2 = R*2, где знак «*» означает, что при вычислении R1×R2 применяется логическое умножение и сумми­рование элементов матриц.

Аналогично определяются все матрицы вплоть до R = Rn = R1*п, где R — матрица достижимости графа G(Х,U), i-я строка которой представляет все ориентированные пути по графу длиной от одного до п ребер, из i-й вершины ко всем остальным. Матрицы А и R имеют размерность п × п.

При вычислении R не обязательно R1 возводить в n-ю сте­пень. Если R1* k = R1*(k-1), то R = R1* k, где k < п.

4. Проанализировать матрицу R. Если R = Q, где Q=[qij], такая универсальная матрица, что для всех i и j qij= 1, то граф бисвязен и декомпозиция системы невозможна, т. е. систе­ма состоит из одной сильно связанной подпроблемы. Если R≠Q, то необходимо перейти к следующему шагу. В тех случа­ях, когда известно, что граф связен, следует перейти к шагу 8.

5. Определить матрицу достижимости неориентированного графа G0(X,U), соответствующего ориентированному графу проблемы

G(Х,U). Матрица R0=(А+Ат+D)*n, где знак Т оз­начает транспонирование.

6. Определить связные подграфы ориентированного графа

G(Х,U). Известно, что множество вершин связного подграфа, содержащего вершину i, определено единицами в i - й строке мат­рицы R0. Если R0=Q, то граф G(Х,U) состоит из одного связного подграфа. В этом случае следует переходить к шагу 8. Если же R0≠Q, то надо перейти к следующему шагу.

7. Упорядочить вершины графа G(Х,U) (матрицы А) по связ­ным подграфам.

8. Образовать матрицу связности С=R+RT. Здесь сложе­ние обычное, арифметическое.

9. Выделить из матрицы С бисвязные подграфы. Бисвязный подграф, содержащий вершину i, определен двойками в i - й строке матрицы С.

10. Упорядочить А так, чтобы бисвязные подграфы образовали квадратные подматрицы Eφ A, φ = 1, 2,….,р.

11. Образовать матрицу R+=(A0++АТ+ +Е+)*0,

где А+—матрица смежности подграфа с множеством вершин

V=W/ Bφ и Bφ — подмножество составных частей φ-й сильно связанной подпроблемы, и выполнить п. 6 и 7.

12. По упорядоченной матрице А' определить связи (ребра) между подпроблемами, которые должны быть разорваны в резуль­тате декомпозиции.

Рассмотрим пример реализации описанного алгоритма. Пусть имеется КП, структура которой представлена графом (рис. 8.24).

Рис. 8.24. Граф структурной схемы КП

Составим матрицу смежности А этого графа:

(8.158)

Далее получим матрицу

(8.159)

и матрицу

(8.160)

Следовательно, имеются две сильно связанные подпроблемы

В1=6, 7, 8, 9, 10 и В2=3, 11, 13, 15, 16.

По матрице

(8.162)

получаем еще три слабо связанные подпроблемы S1={1, 4, 5},

S2={12, 14} и S3 ={2}.

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

После декомпозиции матрицу А′ можно разрушить, сохранив лишь подматрицы смежности Ds и матрицу смежности сокращен­ного графа М, которые естественным образом получаются из А′.

Замкнутые контуры в подпроблемах B1 и В2 устраняются с использованием матриц смежности

После декомпозиции и устранения замкнутых контуров можно представить КП сокращенным ориентированным графом Г(∆, Ω), где ∆ — множество вершин (подпроблем); Ω — множество ориентированных ребер (связей между подпроблемами). Сокращенный граф является удобной моделью для решения динамических, информационных и диагностических проблем при решении задач консультирования. Он обладает всеми основными топологическими свойствами исходной КП, поскольку КП преобразовывалась таким образом, что топологическое пространство, представленное ориентированным графом G (X, U), непрерывно отображалось в топологическое пространство, представленное графом Г(∆, Ω).

Так, для рассмотренного примера матрица смежности сокра - щенного графа имеет вид:

(8.162)

а сам граф Г(∆, Ω) представлен на рис. 8.18.

Во всех матрицах рассмотренного примера, за исключением (8.160), в свободных клетках подразумеваются нули; в матрице (8.160) в свободных клетках единицы.

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