Файл: Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов.pdf

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

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

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

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

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

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

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

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

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

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

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

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

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

38

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

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

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

шин.

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

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

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

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

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

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

39

максимальному из чисел, содержащихся во второй и третьей стро­ ках, а именно 5;

если некоторое число, меньшее, чем число вершин, отсутствует во второй строке, то соответствующая ему вершина является выхо­ дом;

если в некотором столбце номера во второй и третьей строках равны (например, в столбце, соответствующем дуге и6), то в вер­ шине с этим номером имеется петля.

Триангуляцию матриц можно выполнять, применяя ярусно-па- раллельные формы представления потоков информации, введен­ ные Д. А. Поспеловым для распараллеливания алгоритмов [65].

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

Что касается математической модели Института технической кибернетики, то она обеспечивает анализ потоков информации с применением ЭВМ. Однако, по заключению авторов [54], такая модель на практике себя не оправдывает. Процесс анализа пото­ ков в Институте технической кибернетики осуществляется не на основе информационного графа и соответствующей ему матрицы смежности, а на основе таблиц структурных компонент, заполнен­ ных в процессе обследования. Матрица смежности получается на одном из этапов обработки этой таблицы. С этим мнением можно согласиться, если использовать графы только для анализа пото­ ков информации и не рассматривать комплекс экономических ис­ следований, связанных с синтезом алгоритмов, эквивалентными преобразованиями алгоритмов, оценкой сложности алгоритмов.

Так как целью данной работы является формализация и на ее основе автоматизация комплекса экономических исследований, то выбор математической модели анализа потоков информации дол­

Предлагается математическая модель, основанная на исполь­ зовании теории графов, описывающая следующие этапы:

1. Составление информационной модели по материалам обсле­ дования.

2. Анализ информационной модели с целью определения пото­ ков информации и их объемов.

40

§ 2. 4. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ АНАЛИЗА ПОТОКОВ ИНФОРМАЦИИ

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

дую пару вершин Уг и у^ соединить дугой, идущей от у \ к у^ в том и только том случае, когда yi участвует в образовании г/у, то полу­ ченный граф будет отражать структуру задачи, т. е. взаимосвязь документов по задаче.

41

ным структурным графом задачи..

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

информационную модель потока данной управляющей системы.

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

где ZaJ — сумма элементов /-го столбца матрицы ЛА ; Yai— сумма элементов г-й строки матрицы Ах.

Это вытекает из условия, что 2а-> = .Р+г/г- определяет полустепень

деляемый длиной наибольшего пути, ведущего в г/;-.

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

42