МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ЛАБОРАТОРНОЙ РАБОТЕ 1 «Расчёт количественных характеристик для основных видов структур и основных типов организационных структур систем управления»

СТРУКТУРНЫЕ ХАРАКТЕРИСТИКИ СИСТЕМ И ИХ КОЛИЧЕСТВЕННЫЕ ХАРАКТЕРИСТИКИ

1. Общие положения

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

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

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

Второй этап структурного анализа связывается с изучением направлений связи в структурах. К задачам структурного анализа на данном этапе относят: 1) определение связности структуры с учетом направления связей; 2) выделение сильно связных подсистем; 3) перечисление входных и выходных элементов и на этой основе выделение узлов приема и передачи информации; 4) выделение уровней в структуре и определение их взаимосвязей; 5) определение максимальных и минимальных путей; 6) определение топологической значимости элементов структуры; 7) получение информации о слабых местах в системе и др.

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

2. Некоторые сведения об инструментальном аппарате, используемом при анализе

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

Формальным отображением структуры считается граф, вершинам которого соответствуют элементы, а дуги – связям между ними. Такой граф называется вершинным.

Виды графов.

Различают графы неориентированные, ориентированные и смешанные

Граф, составленный только из неориентированных ребер, называют неориентированным, Ребро Е называют неориентированным, если порядок концевых точек ребра («а» и «b») или вершины безразличен. Цепью в неориентированном графе называют последовательность смежных ребер.

Граф, состоящий из ориентированных ребер, то есть таких, для которых порядок («а» и «b») важен, то есть Е= («а», «b») не равно Е=(«b», «а») называется ориентированным.

Граф, состоящий из одной изолированной вершины, называют нульграфом.

Неориентированный граф называется полным, если каждые две различные вершины его соединены одним и только одним ребром. В полном графе каждая его вершина принадлежит одному и тому же числу ребер. Для задания полного графа достаточно знать число его вершин. Граф, не являющийся полным, можно преобразовать в полный с теми же вершинами, добавив недостающие ребра. Вершины графа G и ребра, которые добавлены, тоже образуют граф. Такой граф называют дополнением графа G.

Полным ориентированным графом называется граф, каждая пара вершин которого соединена в точности одним ориентированным ребром (дугой). Если с каждого ребра полного ориентированного графа снять направление, то образуется полный граф с неориентированными ребрами.

Путём в графе называется такая последовательность дуг, в которой конец предшествующей дуги является началом следующей.

Длина пути равна количеству дуг, его составляющих.

Граф называется сильно связным, если для любой пары его вершин найдётся путь их соединяющий.

Граф называется симметричным, если пара вершин i и j соединены дугами двух направлений.

Если в неориентированном графе для любой пары вершин имеется цепь, связывающая их, то такой граф называется связным.

Общее число линий, инцидентных вершине Х, называется степенью этой вершины (говорят, что i инцидентно X, если линия i графа начинается или заканчивается в вершине X).

Сумма степеней всех вершин графа равна удвоенному количеству линий (рёбер) графа. Для неориентированного графа, имеющего m рёбер и n - вершин, вводится понятие средней степени вершины =2т/n

Если в графе все вершины имеют одну и ту же степень n, то граф называется однородным степени n .

Каждая вершина ориентированного графа имеет кроме степени еще и характеристику, называемую полустепенью исхода и полустепенью захода.

Вершина, степень которой равна единице, называется висячей.

Графическое представление структуры является наиболее наглядной формой, однако этот способ не может быть использован при решении задач структурного анализа с использованием ЭВМ. Вследствие этого широкое распространение получило матричное представление графа, отображающего структуру. Следует также отметить, что большинство количественных оценок структурного анализа формируется на основе матричного представления.

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

Матрица смежности - матрица путей длины I.

Для неориентированного графа матрица смежности имеет вид

А=||а_ij||, (2.1)

г де элементы определяются следующим образом:

I при наличии связей между вершинами i и j

а_ij =

0 при отсутствии связей. (2.2)

При этом предполагается, что нумерация вершин неориентированного графа уже проделана. Матрица смежности для неориентированного графа является симметрической.

Для ориентированного графа элементы а_ij матрицы смежности А определяются по следующему правилу:

I , если из вершины i можно перейти в вершину j

а_ij =

0 при отсутствии связей. (2.3)

Пример:

0 1 0 1 А= 1 0 0 1 0 0 0 1 1 1 1 0

0 1 0 1 А= 0 0 0 0 0 0 0 1 0 1 0 0

На основе матрицы смежности ориентированного графа можно выявить некоторые свойства структуры.

Равенство нулю суммы элементов j-го столбца матрицы служит признаком для формального выделения исходных элементов (входов структуры).

Равенство нулю суммы элементов i-ой строки матрицы смежности служит признаком для выделения конечных элементов (выхода) структуры.

Значение суммы элементов j-го столбца матрицы, отличное от нуля, определяет число элементов, входящих в j-ый элемент.

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

Для неориентированного графа матрица инцидентностей B=||b_ij||, с m - рёбрами и n - вершинами строится по следующему правилу

I, если вершина i инцидента (если есть связь) j-ому ребру

b_ij =

0, если нет связи. (2.4)

д ля ориентированного графа

I , если i-ая вершина есть начало j-го ребра;

b_ij = -I , если i-ая вершина есть конец j-го ребра; (2.5)

0 , если i-ая вершина не инцидентна ребру j.

Для определения некоторых характеристик структуры используется матрица связности

С=||с_ij||.

Элементы матрицы связности вычисляются на основе матрицы числа путей

(2.6)

где - число всевозможных различных путей от вершины i к вершине j; А^k - матрица числа различных путей длины k.

I, если ≥1

с_ij = (2.7)

0, если =0

Рассмотрим пример.

0 1 0 1 А^1= 0 0 0 1 0 0 0 0 0 0 1 0

0 0 1 1 А^2= 0 0 1 0 0 0 0 0 0 0 0 0

0 0 1 0 А^3= 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 А^4= 0 0 0 0 0 0 0 0 0 0 0 0

0 1 2 2 А^∑= 0 0 1 1 0 0 0 0 0 0 1 0

0 1 1 1 С= 0 0 1 1 0 0 0 0 0 0 1 0

Матрицу длин путей, равных k, можно построить также рекурсивным способом

А ^k = А¹·А¹….. A¹ = А^k-1·А

k раз (2.8)