Добавил:

ivanov666 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Башкирский Государственный Аграрный Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

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

.pdf

Скачиваний:

Добавлен:

20.10.2023

Размер:

8.54 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 45 / 225 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 > Следующая >>>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Общий	принцип построения такого	графа состоит		в	следую
щем. Если	вершинам графа У\,Ц2, —,	Ут	сопоставить	документы
у и у г , —, Ут, используемые при решении			некоторой задачи,		и каж

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


Граф	взаимосвязи		документов		по задаче	можно		дополнить,
введя вершину,		соответствующую			наименованию		(номеру) зада
чи — Нк.	Если	результатом		решения задачи		является		документ
Уг, то ух является входом для вершины #„ . В этом							случае вершина
у» соединяется		дугой	с Нк.	В полученном графе			из вершины Нк
не выходит ни одной			дуги. Такой		граф будем	называть		расширен

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

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

выявить	ряд важных			характеристик			схем потоков		информации.
Пусть	заданы		т		структурных		графов	задач G			(У^Г^),
^2(^2^2),	— ,	Gm(ym,		Гт).	Строим для каждого				из	них	матрицу
смежности АиА2,				Ат.	Выполняя		суммирование			этих	матриц,
получим	матрицу смежности					графа,	отражающего			взаимосвязь
документов по		всем	задачам			управляющей системы				или подси
стемы.
				А=А1+А2+---+Ат			•.
Таким	образом,		в	результате суммирования				матриц			получим

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

Этой матрице	смежности соответствует	граф G,	являющийся
результатом объединения графов Gu G2,		Gm. Назовем этот
граф информационным графом, а соответствующую			матрицу —
информационной	матрицей потока.

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

во, т. е. без контуров. Появление		контуров з		таком	графе	считает
ся ошибкой обследования.						N
Последовательность матриц А,		А2,	,4N				А%
				и матрица ,4s = S
позволяют выявить основные свойства потока информации.						Л =	I

Исходные и результативные данные определяются соответст
венно из условий равенства нулю		суммы	элементов		/-го	столбца
и суммы элементов г-й строки матрицы			смежности		Ах.
2aJ=0	при	Я= 1 ;
2ац = 0	при	К=\,

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

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

захода, а Ъах = Р-ух — полустепень исхода			вершины г/г-.
Порядок компонент потока (вершин информационного графа)
определяется по матрице Ах	из	условия:	если	(Za^) Л j i - i > 0 и
(2а-*)д Л = 0, то fIj=X— 1, где	Я3-	— порядок	/-й	компоненты, опре

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

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

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

AN = 0

равно

FJ =

N—1

при Х= 1,2,

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

матрицы Ах

показывает

число путей

дли

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

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

каждый

элемент

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

дугу,

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

связь

компонент.

Число

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

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

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

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

по

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

Л 2

= 2 Л \

Каждый

элемент

ац матрицы

Аъ

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

собой

число

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

путей от

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

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

Отличные

от

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

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

Нулевые

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

ком

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

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

потока

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

как

разница

между

номером

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

Г* и

номером

такта,

на

котором

она

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

Я,-.

6; = 7',-Я,-

••

где 6j — число

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

Номер

такта

гашения

Ti компоненты

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

как

мак

симальное

значение

порядка

компоненты,

для

которой

элементы

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

Поясним

на

примере

процесс

составления

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

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

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

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

потоков.

На

рис.

показаны

структурные

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

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

(ГМПСМ).

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

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

документов:

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

ведомости

по

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

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

у\

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

уг

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

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

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

Уъ

Сводная

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

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

г/4

Таблица

приоритетов

предприятий

» . . .

(/5

Наряд на

поставку

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

предприятию

. >

ув

Сообщение

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

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

г/7

/Приемный

акт

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

конторы

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

Наряд на

выданное

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

уд

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

ую

Сводная

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

на

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

у и

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

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

по

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

уп

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

строящихся

объектов

t . .

г/13

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

у и

Карточка

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

материалов

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

#15

конторе

. .

•

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

следующие

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

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

продукции

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

Расчет потребности в электрическом оборудовании t			# 2
Составление	плана распределения оборудования на планируемый год .		# 3
Контроль за	реализацией поставок для строящихся	и реконструируе
мых объектов	(. . . . ч.	Hi
Контроль за	реализацией поставок оборудования предприятиям . . .		Я 5
Наблюдение за движением материалов по транспортно-складской конторе			Hs
управления материально-технического снабжения и транспорта
Построим	информационную модель потока	отдела оборудова

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

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

По первой задаче:

ГУ1 = Гу2 = ую; Гую = Нх •

По	второй	задаче:
			Гуъ^Уи	;
			Гуи = Н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	Уз	У4	Уз	У»	У?	У«	У9	Ую	У н	У и	у13	У ч	У и
I	\
У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

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

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

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

По первой задаче:

	0	1
		1
Ую	0	0

По второй задаче:

		J	У а
	1	Уз	У а
	1
Уз		0	1
Уи		0	0

По	третьей задаче:
	У1	Уз
	О	О
У2	О	О
Уз	О	О
У*.	О	О
Уъ	О	О
Ун	О	О
По	четвертой	задаче:
	1
	Ун	О
	Уе	О
	У7	О
	Ун	О

пятой задаче:

У?

Ун

Уз	У1	У5	У и
О	О	О	1
О	О	О	>
			>
О	О	О	>
			>
О	О	О
О	О	О	•
			•
О	О	О	О

Уе	У7	У и
О	О	1
О	О	1
О	О	1
О	О	О

У7 У и

О1

ОО

По шестой	задаче:
	Уа	У»	У15
Уа	0	0	1
Уа
У»	0	0	1
У»
Ун	0	0	0

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

	у1	Уа	Уз	Уш	У н
У1	0	0	0	1	0
У2	0	0	0	1	0
Уз	0	0	0	0	1
Ут	0	0	0	0	0
Уп	0	0	0	0	0

Выполнив	сложение		полученной матрицы			с матрицей		смежно
сти, соответствующей третьей задаче, получим матрицу вида:
>-<	Ух	Уз	Уз	У4	Уз	Ую	У и	У и
	Ух	Уз	Уз	У4	Уз	Ую	У и	У и
У1	0	0	0	0	0	1	0	1
Уъ	0	0	0	0	0	1	0	1
Уз	0	0	0	0	0	0	1	1
У4.	0	0	0	0	0	0	0	1
Уъ	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

4. Заказ 4230.

<<< < Предыдущая 1 2 3 45 / 225 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 > Следующая >>>

Соседние файлы в папке книги из ГПНТБ

#
19.10.20234.23 Mб13Алмазов, В. Б. Методы пассивной радиолокации учебное пособие.pdf
#
19.10.20231.86 Mб11Алтунджи, К. С. Механизация и автоматизация при бестарном хранении и внутризаводской транспортировке сахарного песка в кондитерской промышленности (обзор).pdf
#
30.10.202316.73 Mб36Алтухов В.А. Основы аэродинамики летательных аппаратов.pdf
#
22.10.202311.7 Mб6Алферов, С. А. Динамика зерноуборочного комбайна.pdf
#
23.10.20238.65 Mб30Алферова З.В. Теория алгоритмов учеб. пособие.pdf
#
20.10.20238.54 Mб20Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов.pdf
#
29.10.20232.9 Mб14Алферьевская О.Л. Контактный нагрев.pdf
#
29.10.2023976.17 Кб12Алыбаев Б. Хранение сельскохозяйственных машин.pdf
#
21.10.20239.8 Mб10Альбедо нейтронов..pdf
#
27.10.202322.03 Mб23Альбов М.Н. Рудничная геология.pdf
#
29.10.20232.04 Mб12Альбов С.В. Минеральные источники.pdf