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

го результата, определяется по матрице

AN = 0

и

равно

FJ =

N—1

при Х= 1,2,

N.

Каждый элемент ахц

матрицы Ах

показывает

число путей

дли­

ной Я, соединяющих любые две вершины графа.

Следовательно,

каждый

элемент

матрицы А показывает пути длиной в одну

дугу,

т. е. непосредственную

связь

компонент.

Число

всевозможных

путей, связывающих

компоненты потока,

N

определяется

по

элементам матрицы

Л 2

= 2 Л \

Каждый

элемент

ац матрицы

Аъ

представляет

собой

число

всевозможных

путей от

tji к tjj (без указания длины пути).

матрицы А% указы­

Отличные

от

нуля элементы у'-го столбца

вают все компоненты, участвующие в формировании уу

Нулевые

элементы i-й строки матрицы A-z указывают все результатные

ком­

поненты, при формировании которых используется у{.

Срок хранения компонент

потока

определяется

как

разница

между

номером

такта, после которого она гасится,

Г* и

номером

такта,

на

котором

она

сформирована,

Я,-.

_

6; = 7',-Я,-

J

••

где 6j — число

тактов хранения компоненты г/г-

Номер

такта

гашения

Ti компоненты

Уг определяется

как

мак­

симальное

значение

порядка

компоненты,

для

которой

элементы

i-й строки матрицы А отличны от нуля.

Поясним

на

примере

процесс

составления

информационного

графа информационной матрицы и на их

основе — процесс анали­

за информационных

потоков.

На

рис.

6

показаны

структурные

ния строительных материалов г. Москвы

(ГМПСМ).

При построении графов приняты следующие условные обозна­

чения названий

документов:

Комплектовочные

ведомости

по

капитальному

строительству . . . .

у\

Сводная таблица потребности в продукции машиностроения по заводу

уг

Специализированная

ведомость-заявка

на оборудование завода . . .

Уъ

Сводная

таблица-сообщение о количестве отпущенного

оборудования .

г/4

Таблица

приоритетов

предприятий

» . . .

(/5

Наряд на

поставку

оборудования

предприятию

. >

ув

Сообщение

о получении предприятием

оборудования

г/7

/Приемный

акт

транспортно-складской

конторы

оборудование >

ys

Наряд на

выданное

транспортно-складской конторой

уд

Сводная таблица потребности в продукции машиностроения по ГМПСМ

ую

Сводная

ведомость-заявка

на

оборудование

у и

План распределения

оборудования

по

лредприятиям

к

уп

Контрольный лист по комплектации

строящихся

объектов

t . .

г/13

Контрольный лист за поставками оборудования

у и

Карточка

количественного учета

материалов

в

транспортно-складской

#15

конторе

.

. .

•

В отделе решается шесть задач, наименования которых имеют

следующие

обозначения:'

Расчет потребности в оборудовании для капитального строительства и

#1

продукции

машиностроения

Расчет потребности в электрическом оборудовании t

# 2

Составление

плана распределения оборудования на планируемый год .

# 3

Контроль за

реализацией поставок для строящихся

и реконструируе­

мых объектов

(. . . . ч.

Hi

Контроль за

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

Я 5

Наблюдение за движением материалов по транспортно-складской конторе

Hs

управления материально-технического снабжения и транспорта

Построим

информационную модель потока

отдела оборудова­

ния с использованием

операций над графами и над матрицами, так

как информационную

матрицу смежности

информационного гра­

фа можно построить и по графу.

Процесс построения информационного

графа с точки

зрения

теории графов представляет собой операцию объединения

графов.

Для выполнения операции объединения необходимо для

каждого

По

второй

задаче:

Гуъ^Уи

;

Гуи = Н2 •

По

третьей задаче:

Гу\ = Гу2 = Гуг = Л/4 = Гу5 = уi2

;

По

четвертой

задаче:

ГУ\2 = Гу6-=Гг/7

= #1з ;

П/1 3

= Я 4 •

По

пятой

задаче:

Гу7 =

Уи\

Гуи = Н5 •

По

шестой

задаче:

Гуъ — Гуд — ухь ;

/ # 1 5 =

# 6 •

Граф G(Y,

Г),

являющийся

результатом

объединения всех

У={У1,У2,Ую,Н1}\]

{#з,#ц,Я2 }

(J

{yi #2 > #з, #4,

#5, #12, Н3}

U {У12,У6,У7<У\3,Н4} (J

{#т>#14, Я 5 } U

{#8, #9, #15,

Я 6 } = {yV

#2. Уз, #4, #5, #6, #7- #8

#9-

#10, #11-#12,

#13, #14, #15' Н\, # 2 , # 3 , Hi,

Hz,

#6} •

Таким

образом, информационный

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

содержит

пятнадцать

вершин.

Отображения информационного графа определяются как объе­

динение

отображений

структурных графов задач:

ГУ\ = {г/ю, у 12} ;

Гуя=

{уп,

уп};

г УА = {4/12};

Губ

={г/1г};

Гув

=

{г/1з};

Гут

={уп,Уи}\

Гу%=

{у\ъ};

Гуъ =

{г/is};

Г « / 1 0 = { Я 1 } ;

Гг/п =

{ Я 2 } ;

Гу\2={Нй,у1з};

Гуи={Нв};

Гук={Нв};

Щ = Г Я 2 = Г Я 3 = Щ = Щ = Г Я 6 = 0 •

Общий

вид

нерасширенного

информационного графа приведен

на рис.

7,

а

расширенного — на рис.

8.

Рис. 7. Общий вид информационного графа

Матрица

смежности графа G(Y, Г), представленного на рис. 7,

будет иметь

вид:

\

J

У4

У9

у13

I

У1

У2

Уз

Уз

У»

У?

У«

Ую

У н

У и

У ч

У и

\

У1

0

0

0

0

0

0

0

0

0

1

0

•

0

0

0

0

0

0

0

0

0

0

0

0

1

0

>

0

0

0

Уз

0

0

0

0

0

0

0

0

0

0

1

•

0

0

0

У*

0

0

0

0

0

0

0

0

0

0

0

•

0

0

0

Уь

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

= Уе

0

0

0 | 0

0

0

0

0

0

0

0

0

1

0

0

Уч

0

0

0

0

0

0

0

0

0

0

0

0

1

1

0

Уз

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

Уз

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

Ую

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

Уи

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

Уи

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

У13

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

Уи

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

У15

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

1

Ую

0

0

0

J

У а

1

Уз

Уз

0

1

Уи

0

0