Файл: Зингер, И. С. Моделирование информационных процессов в системах управления предприятиями.pdf

ности выдачи данных из любой выходной вершины графа U. Сна­ чала выбирается любой простой контур Кж.и графа U и рассмат­ ривается граф ПН), полученный из графа U заменой простого кон­ тура Кх,у на вершину их, из которой исходят все дуги, исходившие из контура К*,!/ (из вершины иу), и в которую входят все дуги, вхо­ дившие в контур Кж,у-

Вершине их графа НИ) приписывается вероятность достоверного преобразования данных от входа в вершину до выхода из нее,

равная <7(К*,у), т. е. в графе UWqP = q(Kx,y).

С графом НИ) поступаем таким же образом. Продолжаем эту процедуру до тех пор, пока не получим граф, лишенный контуров.

Проделаем эту процедуру на примере. Исходный граф изобра­ жен на рис. 25.

Под вероятностями qt для этого графа понимается qKrp.i — для контролирующих выходных вершин циклических структур и ^ — для остальных вершин графа (величины qKTV.i и qi имеют смысл, описанный выше).

Этот граф имеет две входные вершины: ии и5, две выходные: «8, «э, три циклические структуры: Кг,з, Кг,4, Кв,г, из которых две

(К.2,з и Кед) простые.

Следуя указанной процедуре, устраним сначала простую цик­ лическую структуру Кг,з и получим граф ПН), приведенный на

рис. 26.

В этом графе вероятность ^2{1) достоверного перехода информа­ ции от входа в вершину и2 до ее выхода равна:

68

lj\-f — -—----------------- ---

2 Ркт р .З + <?2 ’ ^ ктр .З

Для остальных вершин Ui этого графа вероятности имеют тот же смысл и значения, что и для графа U*

На втором шаге устраним циклическую структуру Кгд графа UW. Получим граф £Л2), приведенный на рис. 27.

В графе £Л2) вероятность q<p) достоверного перехода информа­ ции от входа в вершину «2 до ее выхода будет

п>

Яг

2 рк тр .4 + <7^ * < 7к т р .4

Яг

/Рктр.З * /? к т р . 4 4 '/? к т р ,4 ‘ <7хтр.З * ^2 + ^2 Я к т р . 4

Для остальных вершин щ этого графа вероятности qj2) такие же,

как и для графа U на рис. 25.

На третьем шаге устраним последнюю циклическую структу­ ру — циклическую структуру Кб,7 графа £Л2>.

Получим граф U£' без контуров, показанный на рис. 28, где вероятности qi достоверного перехода информации через вершины Щравны соответственно:

q f = q i :

______________ Цг________

q f = q f = Рктр.з *Ритул~\~Рктрл ’^ктр.з • Яг~\~ЯктрА' Яг

ff(3)=^9 .

69

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

выходной информации необходима обработка данных во всех этих вершинах.

Вернувшись к рассматриваемому примеру, получим, что веро­ ятность достоверного выхода данных в вершине иа графа U на рис. 25 равна вероятности получения достоверного выхода данных в вершине иа графа £Л3) на рис. 28, которая равна:

q {3) q(3) д (3) д ( з) =

Я1 <7г Яь Яь Я8

(рктр.з -Рктр.4+172 <7ктр.4+ <72’<7ктр.8'рктрл) (Рктр.7+ <7в<7ктр.7)

Вероятность получения достоверного выхода в вершине «9 графа U на рис. 25 равна вероятности получения достоверного выхода данных в вершине и9 графа t/<3) на рис. 28, которая равна:

/ ? к т р .7 + <7б * ^ к т р .7

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

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

врассматриваемый выход. Если вершины, из которых ведут пути

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

мого выхода.

Перейдем к определению указанных параметров для простых контуров.

70

гдерктр.= 1— Рктр. — вероятность искажения информации в гра­ фе

Вычислим среднее значение Q сложности формирования выхо­ да циклической структуры, показанной на рис. 29, из ее входа.

Вероятность того, что данные будут выданы из контура после первого прохода по графу UT, равна вероятности того, что не бу­

дет обнаружено искажения информации после первого прохода данных по графу Нг; 1— (1 — <7г)<7ктр;. При этом сложность фор­ мирования выхода будет равна С?г+<2ктр.. Сложность формирова­

ния выхода в результате двух проходов по контуру равна 2(Qr+ + Qktp:); а вероятность того, что выход будет получен после двух проходов, составит

[1 (1 <7г)<7ктр.] [(1 ^г)7ктр.] .

Сложность формирования выхода в результате трех проходов по контуру равна 3(Qr+QKTp.), а вероятность того, что выход будет получен после трех проходов, будет

[1— (1—<?г) <7ктр.] [ (1 ^г)<7ктр.]2 И Т. Д.

Для среднего значения сложности формирования выхода из циклической структуры получаем выражение

-I— = (Qr + Фктр.) [1— (1 ~ Я г ) <7ктр.] {1 + 2[ (1 — qr) <?ктр.] +

1 (1— *7г)^ктр.

+ 3[ (1 —7г) 9ктр.]2+ " -} = (Qr+QKTP.) [1_ (1_ (7р)?1(ТР1]Г '==

Qi +Q ктр.

Рьтр.+ 9г'<?ктр.

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

71