Построение простых иерархий доминантного типа

Предположим, что имеется некоторое множество элементов, между которыми существуют определенные отношения.

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

Бинарная матрица может быть представлена матрицей достижимости, которая определяется по матрице зависимости.

Матрица зависимости B заполняется следующим образом. Если множество вершин H определено, то с помощью бинарного отношения «зависит от» можно заполнить матрицу так, что ответ «да» фиксируют «единицей», а ответ «нет» фиксируют «нулем», т. е. элемент b_ij матрицы равен:

Построив таким образом матрицу, переходим к формированию матрицы достижимости.

Для этого формируем бинарную матрицу (I+B), (где I – единичная матрица) и возводим ее в некоторую степень k, при которой выполняется условие: (I+B)^k-1≤(I+B)^k=(I+B)^k+1

Матрица (I+B)^k=(I+B)^k+1 и будет матрицей достижимости.

Матрица достижимости может быть построена и более простым путем, непосредственно по исходному направленному графу. В этом графе дуга выходит из зависимого элемента. Заполнение матрицы бинарными элементами осуществляется по строке(слева направо) по правилу:

Наличие матрицы достижимости позволяет разделить все множество вершин на подмножество уровней.

Для этого вершины делят на достижимые и предшествующие.

Вершину h_j назывют достижимой из вершины h_i, если в ориентированном графе существует путь из h_i к h_j. Обозначим подмножество вершин достижимых из вершины h_i через R(h_i). Вершину h_j называют предшествующей вершине h_i, если возможно достижение h_i из h_j. Обозначим подмножество вершин предшествующих вершине h_i через A(h_i).

Множество тех вершин A(h_i) = R(h_i)∩A(h_i), для которых выполняется условие недостижимости из любой из оставшихся вершин множества H и, следовательно, может быть обозначено как уровень иерархии. Таим образом, для структуризации некоторого множества элементов H, связанных определенными отношениями зависимости, необходимо выполнить следующие поцедуры.

1. Составить напрвленный граф отношений между элементами множества H.

2. Сформировать матрицу достижимости по направленному графу.

3. Сформировать таблицу с элементами h_i, R(h_i), A(h_i) и R(h_i)∩A(h_i).

Для формирования подмножества R(h_i) из i –ой строки матрицы выписываются номера тех элементов, которые содержат единицы. Для формирования подмножества A(h_i) из i –го столбца матрицы достижимости выписываются номера тех элементов, которые содержат единицы.

Подмножество R(h_i)∩A(h_i) формируется как логическое пересечение (совмещение) элементов двух подмножеств.

4. Наити элементы в таблице, для которых выпоняется условие:

A(h_i) = R(h_i)∩A(h_i).

Эти элементы и образуют первый уровень.

5. Вычеркнуть полученные на первой итерации элементы и применить вышеописанные процедуры (п.п. 1 – 4) снова. Итерации повторяются до тех пор, пока остается более одного элемента.

Описанную выше методику структуризации продемонстрируем на таком примере.

Предположим. Что необходимо иерархически структурировать такие компоненты (элементы) как:

· экономическая безопасность (ЭНБ);

· военная безопасность (ВБ);

· экологическая безопасность (ЭЛБ);

· сельскохозяйственный сектор экономики (СХ);

· сектор экономики, производящий электронную и вычислительную технику (ВТ);

· сектор машиностроения (МШ);

· сектор энергетический (ЭН).

Направленный граф отношений между элементами, расположенными произвольным образом, показан на рис 1.2.

Направление стрелки дуги определяется направленностью зависимости: стрелка указывает на элемент, от которого зависит элемент, из которого она выходит.

Матрица зависимости для этой схемы имеет вид:

Матрица достижимости имеет вид:

Используя матрицу достижимости, строим таблицу, которая является первой итерацией анализа.

Из таблицы видно, что критериальное равенство A(h_i) = R(h_i)∩A(h_i). выполняется для элементов 2 и 3. Следовательно они и являются элементами первого уровня.

Вычеркивая из таблицы строки с номерами 2 и 3 и убирая из всех последовательностей цифры 2 и 3, получаем втору итерацию, в которой критериальное равенство выполняется для элемента 1. Он и является элементом второго уроавня.

Повторяя итерации, получаем окончательно пять уровней элементов, которые представлены на рис. 1.2.

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

Рис. 1.2. Иерархическая структура исходного графа.

Порядок выполнения работы.

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

Значение 1 в клетке (i, j) таблицы (где i - строка, j -столбец) означает, что операция i завист от операции j (т.е. операция j предшествует операции i).

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

m – последняя цифра в номере зачетки (если последняя цифра в номере зачетки равна нулю, то m=10);

r – предпоследняя цифра в номере зачетки.

k опредляется по значению r по следующему правилу:

Выпишите матрицу эависимости для своего варианта.

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

4. Используя граф постройте матрицу достижимости.

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

6. Итоговый результат представьте в виде порядкового графа.

Поиск по сайту: