Файл: Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 21.10.2024
Просмотров: 75
Скачиваний: 0
|
У1 |
Уз |
Уз |
У4 |
Уь |
Ув |
Уч |
У8 |
Уэ |
Ую |
Уп |
У12 |
У13 |
Уи |
У15 |
>'l |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
(• |
0 |
J'2 |
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 |
У4, |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
У5 |
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 |
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 |
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 |
У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 |
У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 |
1 |
0 |
1 |
1 |
0 |
0 |
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
Уз |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
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 |
1 |
1 |
0 |
0 |
Уб |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
У1 |
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 |
53
Л |
У\ |
У-2 Уз |
"1 |
У-о |
Ув |
У-1 |
Уа |
Уа |
Ую |
Уп |
У12 |
Уп |
Уи |
У15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Уи |
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 |
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 |
Таким |
образом, |
порядок |
схемы |
потока |
равен |
двум, так как |
|||||||||
Л 3 = 0. Это значит, |
что максимальное число |
тактов |
движения |
ин |
|||||||||||
формации до получения всех конечных результатов равно двум.
Рассматривая |
суммы |
элементов |
столбцов |
в матрице |
А и А2, |
|||||
определяем порядок каждой |
компоненты |
потока. Так, в |
матрице |
|||||||
А 2а^ = 0 для вершин у\^-уъ, |
следовательно, порядок |
этих |
компо |
|||||||
нент |
будет FIj = l—1=0 |
для |
/ = г/ь |
у2, у3, |
у4 , у5, у6, у7, у8, |
уд. |
||||
В матрице А2 обращается |
* нуль I.ai |
для |
вершин |
ую-т-уп и |
||||||
Ун', |
г/15- Таким образом, |
порядок этих компонент будет |
Л 3 |
= А,—1 = 1 |
||||||
для |
/ = г/ю, Уи, У12, Ун, Уis- |
|
|
|
|
|
|
|
||
Это говорит о том, что данные компоненты |
получаются |
на пер |
||||||||
вом |
такте движения информации, |
непосредственно |
по |
исходным |
||||||
документам. |
|
|
|
|
|
|
|
|
|
|
В матрице А3 |
обращается |
в нуль Еа^ для вершины у\3, |
|
порядок |
||||||
этой |
компоненты |
tfj=13=X—1 |
= 3—1=2. |
Значит, компонента У\3 |
||||||
получается на втором такте движения информации. |
|
|
|
|||||||
Анализируя матрицу А .определяем пути длиной |
в одну дугу, |
|||||||||
т. е. количество непосредственных связей |
компонент. |
Для |
нашего |
|||||||
примера это число равно |
14. Анализ матрицы Л 2 дает |
число путей |
||||||||
длиной А = 2, т. е. длиной в две дуги. Число таких путей в рассмат
риваемом |
примере |
равно |
5. |
|
|
|
|
|
|
|
|
|
||
Рассматривая матрицу Л е , определяем |
общее число |
возможных |
||||||||||||
путей, по которым |
формируются |
конкретные |
компоненты |
потока. |
||||||||||
В данном |
примере |
матрица Л е показывает, |
что документ |
г/ю по |
||||||||||
лучается из исходных документов ух |
и у2. |
При этом |
каждый |
из |
||||||||||
документов |
участвует |
в формировании г/ю только по одному пути. |
||||||||||||
Действительно, |
y1l0=y2l0=l. |
|
|
|
|
|
|
|
|
|
||||
Документ |
у и получается на |
основании |
у3 |
только |
по |
одному |
||||||||
пути: г/з=1. Документ |
у12 |
получается |
на |
основании |
документов |
|||||||||
Уи У2, Уз, г/4, Уъ- Каждый |
документ |
участвует |
в |
формировании |
||||||||||
г/12 только по одному |
пути. Действительно, у{2 |
= у\2 |
=у\2 |
= у\2 |
= |
|||||||||
=У52 = 1. Документ |
yi3 |
формируется |
из документов |
уи |
у2, |
у3, yt, |
||||||||
г/s, г/б, г/7 и |
у12 |
по |
одному |
пути: |
у? |
=yl3 |
=yls |
|
=у\3 |
= г/513 =ув3 |
= |
|||
= г/713 =#123 |
= |
1- Документ уц формируется |
на основании у7 |
только |
||||||||||
54
ло одному пути: у1* = 1 . Документ у15 формируется из у& и уд, каж дый из которых участвует в формировании его только по одному
пути: у\5=Уд5 |
= 1 . Длительность хранения |
компонент потока опре |
||||||||
деляем на основании порядка компонент и матрицы А. Для |
рассмат |
|||||||||
риваемого |
примера |
по |
матрице А установлено, |
что |
компоненты |
|||||
нулевого порядка |
ylt |
у2, Уз, У4, Уъ, Уе, У7 |
непосредственно |
участ |
||||||
вуют в формировании |
компонент у10, |
уп, |
Ум, |
Ун, У is |
первого по |
|||||
рядка. Следовательно, |
они должны |
храниться |
только во время |
|||||||
первого такта, после чего могут быть погашены. |
|
|
|
|||||||
Компоненты |
у6, |
г/7 |
нулевого порядка и у12 |
первого |
порядка не |
|||||
посредственно |
участвуют в формировании |
компоненты |
ухз |
второго |
||||||
порядка. Следовательно, они могут быть погашены только после второго такта.
Число тактов хранения компонент, как указывалось ранее, определяется разностью порядков соответствующих компонент.
Внашем примере число тактов хранения будет:
компонент уи у2, у3, Уь Уь, Уа, Уэ — один такт; компонент у6, yi — два такта;
компоненты ух2 — один такт.
Детальный алгоритм анализа потоков информации по инфор мационной модели будет рассмотрен в главе, посвященной мате матическому обеспечению.
§ 2. 5. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ РАСЧЕТА ОБЪЕМОВ ИНФОРМАЦИИ
В общем случае информацию можно характеризовать содер жанием, способом задания и количеством. Понятие количества информации в некотором сообщении появилось в 30-х годах и окончательно сформировалось в 50-х годах. Оно разрабатывалось главным образом в качестве теоретической базы техники связи. Это послужило причиной того, что возникшая в ходе исследования теория информации игнорировала содержание передаваемой ин формации, так как техническая задача связи заключалась в пра
вильной и своевременной |
передаче |
сообщения |
вне зависимости |
от |
|||||||||
их |
смысла. |
|
|
|
|
|
|
|
|
|
|
|
|
|
Впервые |
понятие |
количества |
информации |
появилось в |
работе |
|||||||
Р. Фишера |
в |
1921 |
г. в связи с вопросами математической |
стати |
|||||||||
стики. Несколько |
позже количество |
информации было |
определено |
||||||||||
в работах Конфюллера, американского инженера Хартли, |
и, |
на |
|||||||||||
конец, в 1948 |
г. К- Э. Шеннон |
дал |
для |
определения |
количества |
||||||||
информации формулу, ставшую |
классической: |
|
|
|
|
||||||||
|
|
|
|
|
|
п |
|
1 |
|
|
|
|
|
|
|
|
|
|
/ = - Е P i - l o g - — ; |
|
|
|
|
||||
|
|
|
|
|
|
i—i |
|
Pi |
|
|
|
|
|
где |
/ — количество |
информации; |
|
|
|
|
|
|
|||||
|
п — число возможных |
сообщений |
(исходов опыта); |
|
|
||||||||
|
Pi — вероятность |
г'-го |
сообщения (исхода). |
|
|
|
|||||||
|
Формула |
|
применяется |
также в |
виде |
|
|
|
|
||||
55
|
|
|
I=—n |
i2= ipi |
|
|
|
|
|
|
|
|
|
|
||
где rn — число |
символов |
(элементов), из которых |
может |
быть со |
||||||||||||
|
ставлено |
сообщение; |
|
|
|
|
|
|
|
|
|
|
||||
|
п — число |
символов |
в |
одном |
сообщении; |
|
|
|
|
|||||||
pi — вероятность |
появления |
г'-го элемента |
в сообщении. |
|
||||||||||||
В |
частном |
случае, |
когда |
все элементы |
равновероятны, |
т. е. |
||||||||||
Pi=p2= |
••• =Рт |
= |
, |
получаем |
формулу |
Хартли: |
7 = n-logm |
• |
||||||||
Эта формула соответствует случаю, когда сообщение из симво |
||||||||||||||||
лов |
несет максимально возможное |
количество информации. |
|
|||||||||||||
|
|
|
|
|
|
|
|
При |
проектировании |
авто |
||||||
|
|
|
|
|
|
|
|
матизированных систем управ |
||||||||
|
|
|
|
|
|
|
|
ления |
|
преобладает |
подсчет |
|||||
|
|
|
|
|
|
|
|
статической |
информации. По |
|||||||
|
|
|
|
|
|
|
|
этому |
объем |
информации из |
||||||
|
|
|
|
|
|
|
|
меряют |
количеством |
докумен |
||||||
|
|
|
|
|
|
|
|
тов, |
количеством |
показателей, |
||||||
|
|
|
|
|
|
|
|
реквизитов, |
символов |
и т. д. |
||||||
|
|
|
|
|
|
|
|
Из |
всех |
характеристик по |
||||||
|
|
|
|
|
|
|
|
тока |
наибольшую |
|
сложность |
|||||
|
|
|
|
|
|
|
|
представляет |
определение |
объ |
||||||
|
|
|
|
|
|
|
|
ема. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Состав |
и |
структуру |
доку |
|||||
|
|
|
|
|
|
|
|
ментов |
в управляющей систе |
|||||||
Рис. |
9. Структурный |
граф |
сводной |
|
ме |
можно |
представить в виде |
|||||||||
специализированной |
ведомости |
по- |
|
графа |
|
аналогично |
тому, |
как |
||||||||
|
требиости |
|
|
|
это показано |
на рис. 9. Граф, |
||||||||||
|
|
|
|
|
|
|
|
отражающий |
структуру |
доку |
||||||
мента, будем называть структурным графом документа. |
|
|
|
|||||||||||||
Если реквизитам документа |
Х\, х2, |
|
хп |
сопоставить |
вершины |
|||||||||||
графа Х\, х2, |
хп |
и каждую пару вершин Xi и Xj соединить дугой, |
||||||||||||||
идущей от Xi к Xj в том и только том |
случае, |
когда |
Xi является |
|||||||||||||
составной частью Xj, то полученный |
граф и будет |
отражать струк |
||||||||||||||
туру документа как взаимосвязь его реквизитов. |
|
|
|
|||||||||||||
Рассмотрим |
структурный |
граф |
G(X, Г) |
документа, |
представ |
|||||||||||
ляющего следующую сводную специализированную ведомость по
требностей отдела оборудования |
ГМПСМ: |
|
|
|
||||
|
|
|
|
Потребность |
|
|
|
|
|
|
|
|
|
в том числе |
|
|
|
Наимено |
Группа |
Наимено |
|
комплектов |
продук |
|
|
Выде |
вание |
ции машиностроения |
|
|
|||||
вание |
оборудо |
оборудо |
всего |
|
|
капиталь |
|
лено |
Главка |
вания |
вания |
ранее |
вновь |
раздел |
|
||
|
|
|
|
ное CTPJH- |
|
|||
|
|
|
выпускае |
выпускае |
тельство |
|
|
|
|
|
|
|
мых |
мых |
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
56
|
При построении графа приняты следующие |
условные |
обозна |
|||||||||||||
чения: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ха |
|
|
Сводная |
специализированная |
ведомость потребности |
|
|
|
; |
|||||||||
|
Наименование |
Главка |
|
|
|
|
|
|
|
|
|
Х\ |
||||
|
Группа |
оборудования |
|
. |
|
|
|
- |
|
|
: |
: |
х2 |
|||
|
Наименование |
оборудования |
|
|
|
>. > |
|
|
|
хъ |
||||||
|
Потребность |
по всем |
видам |
комплектах |
\ |
v |
|
|
|
xt |
||||||
|
Потребность |
в |
ранее |
выпускаемых |
продукции |
машино |
||||||||||
строения |
|
|
|
|
|
• |
|
|
|
i |
|
|
|
х$ |
||
|
Потребность |
во |
вновь |
|
выпускаемых |
комплектах продукции |
машино |
|||||||||
строения |
|
|
|
|
|
|
| |
|
|
|
|
|
|
xs |
||
|
Потребность |
на |
капитальное |
строительство |
|
|
|
|
• |
х7 |
||||||
|
Потребность |
раздела |
|
|
|
|
|
|
|
|
|
xs |
||||
|
Выделенное |
количество |
оборудования |
|
* |
|
|
|
. . |
х9 |
||||||
|
Общая |
потребность |
в |
оборудовании |
|
|
|
|
*к> |
|||||||
|
Потребность |
по |
отдельным |
видам |
|
|
|
: |
|
|
> Хц |
|||||
|
Потребность в комплектах продукции машиностроения |
|
|
|
Хц |
|||||||||||
|
Структурный |
граф |
|
документа |
представляет |
собой |
граф |
типа |
||||||||
дерева, |
висячими вершинами которого являются реквизиты. |
|||||||||||||||
|
Для |
определения |
объема информации |
изменим |
|
ориентацию |
||||||||||
всех дуг в структурном графе на противоположную. |
Каждой |
дуге |
||||||||||||||
графа щ— (XiXj) |
присваивается некоторый |
параметр |
т,-, представ |
|||||||||||||
ляющий собой число |
вхождений |
|
информационной |
совокупности |
||||||||||||
xt |
в информационную |
совокупность |
Xj. Таким |
образом, параметр |
||||||||||||
mi |
указывает, |
сколько |
раз |
данная |
информационная |
совокупность |
||||||||||
входит в соответствующую информационную совокупность более |
|
||||||||||||
старшего |
уровня. |
|
|
|
|
|
|
|
|
|
|
||
Каждой висячей вершине графа-дерева присваивается некото |
|
||||||||||||
рый параметр |
U. Параметр |
U представляет значность данного |
рек |
|
|||||||||
визита по количеству алфавитно-цифровых символов. |
Для |
рас |
|
||||||||||
сматриваемого |
документа |
значения |
параметров trii и U |
приведе |
|
||||||||
ны на рис. 10 над соответствующими дугами и под вершинами. |
|
||||||||||||
Общий |
объем |
инфор- |
|
|
|
|
|
|
|
|
|
||
мации |
определяется как |
|
|
*rt*L |
|
|
|
|
|
||||
сумма |
объемов информа- |
|
N |
/ Т л ^ < ^ / |
|
|
|
|
|||||
ции по каждому пути от |
|
^ / |
/ |
\ g |
— ^ Х д |
|
|
|
|
||||
висячей вершины до кор- |
/ |
|
^ / |
\'^- |
|
|
|
|
|
||||
ня дерева — х0: |
|
г |
§•/ |
\ |
|
|
|
|
|
||||
|
V= |
S |
Vi , |
|
X, |
1-Ю |
,\/*<2^x„ |
|
|
|
|
||
где V — общий объем ин- |
|
|
|
^у' |
|
\$у~~~^~~^Ьг |
|
||||||
|
формации |
по до- |
|
|
* |
Х'1/Съ |
^ |
J ~ ~ |
? |
xs |
|||
Vi |
кументу; |
|
|
|
|
|
\ |
|
|
|
|
||
— объем |
информа- |
|
|
г |
' = ? |
хь |
|
|
|
|
|||
|
ции по пути от 1-Й |
|
|
5 |
|
|
|
|
|
||||
|
вершины, |
висячих |
р и с |
ю |
Граф-дерево |
для расчета |
объе- |
|
|||||
k — число |
|
ма |
информации по |
сводной |
ведомости |
|
|||||||
|
вершин. |
|
|
|
|
потребности |
|
|
|
||||
Объем |
информации по |
конкретному |
пути |
определяется |
как |
|
|||||||
произведение |
соответствующих |
параметров U и |
стоящих |
на |
|
||||||||
57