Тема 11. Описание потоков информации с использованием теории графов

Описание потоков информации процессов управления с помощью графов является одним из наиболее разработанных методов. С его помощью достигается наглядность функционирования системы управления и движения потоков информации; применение математического аппарата теории графов позволяет оптимизировать работу управления и каналов связи; имеется возможность также представлять динамику управления и движения информации, которая ускользает при пользовании другими методами. В настоящее время имеется много примеров использования теории графов в описании данных процессов. Они различаются по характеру описываемых объектов, по видам графов. Рассмотрим наиболее типовые примеры.

Исследование информационного потока на основе его сетевой модели. Метод основан на применении сетевого графика и традиционных методов его анализа и оптимизации. Понятия работы и события принимают характер, соответствующий процессу управления, а именно: под работой понимается определенная задача управления, решаемая работниками данного аппарата управления; под событием понимается определенный документ, который был составлен в ходе выполнения работ (конечное событие) либо будет использоваться в ходе выполнения работ (начальное событие).

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

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

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

Матричная модель позволяет определить:

порядок схемы потока информации;

порядок каждой компоненты потока;

число компонент, непосредственно участвующих в формировании каждого результата;

число результатов, в формировании которых непосредственно участвует каждая компонента;

число путей фиксированной длины, связывающих любые две компоненты потока;

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

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

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

число тактов, в течение которых каждая компонента хранится во внешней памяти.

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

Рассмотрим условный пример (рис.).

Составим матрицу смежности и последовательности матрицы по степеням.

Анализ этих матриц позволяет определить данные по всем перечисленным выше пунктам. Например, проанализировав результирующую строку каждой матрицы по числу нулей, можно судить о порядке компонент. Для Х Х Х число входящих путей равно 0 (нули в таблице М), следовательно, эти компоненты являются исходными данными 0-порядка. В таблице М образовались нули для компонент Х Х и в третьей таблице – для Х Х. Четвертая таблица степени М не проводилась, так как она равна нулю по всем элементам.

Итак,

Х

Х

Х

Х

Упорядочим граф по тактам движения потоков информации (рис.).

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

Система потоков информации может быть описана с помощью комплекса графов. Строятся центральный граф – «дерево» взаимосвязи показателей – и графы расчетов, показывающие потоки и преобразования информации при расчете отдельных показателей.

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

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

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

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

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

Информационная модель в виде графа типа «дерево» содержит в себе следующие сведения:

наименование и характеристику блоков преобразования информации;

последовательность преобразования информации в процессе планирования;

наименование и характеристику блоков преобразования информации;

источники входной информации;

адреса выходной информации.

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

Дата добавления: 2015-04-29