книги из ГПНТБ / Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов

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

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

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

Этапы обследования и анализа существующих процессов уп­ равления и движения информации составляют до 30% всего перио­ да разработки системы [51].

Как показывает опыт проведения обследований, исследователь­ ская группа в составе 15—20 человек затрачивает на проведение обследования с учетом подготовительно-заключительных меро­ приятий от 6 до 8,5 месяца [51]. При этом каждый исполнитель должен иметь программу обследования и детальные вопросники, конкретный план своих работ, специальные разработочные табли­ цы или бланки, специальные тетради для записи материалов.

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

В процессе анализа материалов обследования выявляются:

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

30

Информационная модель позволяет символически описать тех­ нологию подготовки и маршруты движения документов, алгорит­

щие потоки информации, необходимые для проектирования систе­

цесс анализа потоков информации. Описание этих моделей приво­ дится в § 2.2.

Прежде чем перейти к детальному изложению информацион­ ных моделей, введем некоторые понятия.

Исходные данные — информация, которая поступает в систему,

При выдаче из системы окончательные результаты могут объе­ диняться в группы определенного функционального назначения — функциональные результаты.

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

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

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

Отношение порядка позволяет различать такты в движении по­ тока. Исходные данные являются компонентами нулевого порядка. На первом такте из исходных данных образуются компоненты пер­

31

§ 2. 2. ИНФОРМАЦИОННЫЕ МОДЕЛИ

Матричная информационная модель, разработанная в ЦЭМИ АН СССР, представляет собой шахматную таблицу, которая по­ зволяет в единой форме отразить связи между подразделениями предприятия и процессы выработки новых сведений [57]. Это мо­ дель выявленных потоков информационной системы, выражающая количественно и качественно все внешние и внутренние характе­ ристики.

Информационная модель состоит из четырех квадратов и двух вспомогательных разделов. Каждый из квадратов и разделов име­ ет свое определенное содержание и назначение. Общий вид инфор­

///

I

итоговая стропа

Рис. 2. Матричная информационная модель

В квадрате I информационной модели отражаются все доку­ менты и показатели*, которые разрабатываются в обследуемом подразделении. Этот квадрат имеет одинаковое наименование показателей по строкам и столбцам. Он характеризует процессы проведения всех планово-экономических расчетов, разработку по­ казателей и использование их для формирования исходящих доку­ ментов.

* Показатель — информационное множество, имеющее определенное закон­ ченное смысловое значение.

32

В каждом столбце квадрата I определяется, какие показатели из документации этого подразделения используются для формиро­

Каждый из блоков, расположенных по основной диагонали квадрата I , отражает формирование показателей данного доку­ мента.

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

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

характеризуют использование поступающих документов и показа­ телей в данном подразделении.

другим подразделениям.

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

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

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

Левый вспомогательный раздел делится на две части — подраз­ дел А и подраздел Б. Подраздел А отражает те признаки, которые имеются в разрабатываемых данным подразделением документах, подраздел Б — признаки поступающих документов.

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

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

Квадраты / и //, вме|сте взятые, показывают процесс создания показателей и документов и передачу их в другие подразделения, внешние организации или хранение в самом подразделении для

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

Подраздел Б и квадрат / / / отражают процесс поступления до­ кументов и показателей и дальнейшее их использование в данном подразделении.

Квадраты III и IV, вместе взятые, отражают использование, контроль или простое переписывание документов и показателей, необходимых в деятельности данного подразделения.

34

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

Чтобы построить информационную модель, необходимо соответ­ ствующим образом обработать собранные анкеты или разработоч­ ные таблицы.

Для обработки исходного материала с помощью вычислитель­ ных средств необходимо разработать единую систему шифров до­ кументов и показателей. В ЦЭМИ АН СССР обработка исходного материала проводилась механизированным путем с помощью вы­ числительно-перфорационных машин. Для построения информа­ ционных моделей были получены следующие табуляграммы:

1. Перечень наименований документов, разрабатываемых дан­ ным подразделением.

2.Перечень наименований документов, поступающих в подраз­ деления.

3.Перечень всех сообщений, поступающих в данное подразде­

ление, с указанием, откуда поступило каждое из них.

4. Перечень наименований всех выходящих из данного подраз­ деления документов с указанием их адреса.

5.Перечень справочных данных, используемых в работе под­ разделений.

6.Наименование показателей, содержащихся в каждом конк­

ретном документе, поступающем в подразделение.

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

С целью упрощения процесса построения информационных мо­ делей в ЦЭМИ АН СССР были разработаны различные варианты, каждый из которых имеет свои особенности классификации пози­ ций, заполнения и т. д. Примерами таких моделей могут служить модели вида «Документ на документ», «Показатель на показа­ тель», «Смешанные информационные модели».

В отличие от математической модели ЦЭМИ АН СССР в мате­ матической модели, разработанной Институтом технической кибер­ нетики, поток информации в управляющей системе изображается в виде графа, как показано на рис. 3 [60].

нальные результаты), для уровня компонент (исходные дан­ ные, промежуточные результаты, внешние данные) и для

связей между ними. Отметим, что в этом графе нет дуг, выходящих

где 2а^— сумма элементов /-го столбца матрицы А1. Действитель­ но, порядок I7j измеряется длиной наибольшего пути, связывающе­

информационного графа установлено только для активных компо­ нент. Отличные от нуля элементы матрицы А, где Oj — оператор, указывают все активные компоненты потока. Ненулевые элементы тех же столбцов матрицы указывают как активные, так и пассив­ ные компоненты, используемые при формировании активных ком­ понент. Остальные компоненты потока формально избыточны.

Анализ информационных потоков позволяет:

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

ниями предприятия; выявить первичные для предприятия данные;

37

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

исследовать целесообразность имеющихся повторений некото­ рых сведений в системе обработки данных;

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

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

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

Получение необходимых материалов для анализа информаци­ онных потоков — весьма трудоемкий процесс; для облегчения и ускорения этих работ необходимо использовать вычислительные средства. В ЦЭМИ АН СССР такие материалы получались с по­

Рассмотренные выше информационные модели анализа потоков информации очень трудоемки.

В информационной модели ЦЭМИ АН СССР первый квадрат имеет большой разброс в заполнении данных, затрудняющий вос­ приятие цепочки формирования и движения документов и показа­ телей. Для устранения этого недостатка необходимо матрицы при­ вести к треугольному виду (триангулировать).

Рассмотрим построение алгоритма триангуляции с использова­ нием теории графов.

Справедлива следующая теорема: матрица А триангулируема тогда и только тогда, когда соответствующий ей граф G не имеет контуров.

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

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

1. Пронумеровать строки матрицы А, начиная с первой, числа­

38

5. Определить порядок каждой вершины, начиная от входов, которые считаются вершинами нулевого порядка.

6.Произвести перенумерацию вершин. Процесс перенумера­ ции начинается с вершины нулевого порядка и продолжается по возрастанию порядков.

7.Построить граф G* в соответствии с новой нумерацией вер­

шин.

8.Построить матрицу смежности А* графа G*.

Матрица А* эквивалентна матрице А и имеет треугольную форму.

С увеличением размерности матрицы А построение соответст­ вующего ей графа и определение порядка вершин при ручной обра­

с помощью ЭВМ, используя так называемую структурную матри­ цу S.

Структурная матрица строится следующим образом. Обозна­

и под каждой дугой укажем номер вершины, из которой она вы­

39