где ^T(Li) — сумма эквивалентных коэффициентов пропускания для всех возможных петель /-го порядка. Таким образом, мы определили основные шаги процедуры вычисления эквивалентного коэффициента пропускания замкнутой сети. В качестве примера рассмотрим предыдущий рисунок. Данный замкнутый потоковый граф содержит одну петлю первого порядка с эквивалентным коэффициентом пропускания, равным И'Дз) И^(5). По правилу Мейсона получаем, что 1—И'д(5,)=0 или WA(s)=\IWE(s). Отметим, что функция ЖдО) содержится в топологическом уравнении, поскольку она является элементом, по крайней мере, одной петли первого порядка. Важность результата, полученного при рассмотрении данного примера, состоит в том, что если в топологическом уравнении W4(5) заменить на 1/W£(5) и решить его относительно 1УД5), то будет получена эквивалентная W-функция для исходной стохастической сети. Рассмотрим этап вычисления математического ожидания и дисперсии. Из топологического уравнения (2.3.8) было получено выражение для эквивалентной W-функции WE(s) сети. Напомним, что Л/£(5)=1 при 5 = 0. Поскольку W£(s) = рЕ ME(s), то рЕ W£(0), откуда следует, что ME(s) = WE^/pE=W^/WE(0). (2.3.9) Отметим, что WX-s) можно выразить через W-функции всех или некоторых ветвей исходной сети. Нетрудно вычислить значение W£(0); для этого в выражении для W£(5), получаемом из (2.3.8), надо положить 5 = 0. Вычисляя у-ю частную производную по 5 функции М£(5) и полагая 5=0, находим у'-й моментpjE относительно начала координат, т. е. (2.3.10) 94 |
Рис. 3.2.2 Замкнутая стохастическая сеть Топологическое уравнение для замкнутых графов, известное также как правило Мейсона [...], имеет следующий вид: Н = 1 Z T(L{) + 2 T{L2 ) 2 T(L3 ) + ...+ (-1Г 2 T(Lm ) + ... = О, (3.2.8) где 'Y.T(Lj) — сумма эквивалентных коэффициентов пропускания для всех возможных петель г-го порядка. Таким образом, мы определили основные шаги процедуры вычисления эквивалентного коэффициента пропускания замкнутой сети. В качестве примера рассмотрим предыдущий рисунок. Данный замкнутый потоковый граф содержит одну петлю первого порядка с эквивалентным коэффициентом пропускания, равным WA(S) WE(s). По правилу Мейсона получаем, что 1—H/(s)=0 или WA(s)=l/WE(s). Отметим, что функция WA(s) содержится в топологическом уравнении, поскольку она является элементом, по крайней мере, одной петли первого порядка. Важность результата, полученного при рассмотрении данного примера, состоит в том, что если в топологическом уравнении WA(s) заменить на l/WE(s) и решить его относительно We(s), то будет получена эквивалентная ^-функция для исходной стохастической сети. Рассмотрим этап вычисления математического ожидания и дисперсии. Из топологического уравнения (3.2.8) было получено выражение для эквивалентной JF-функции WE(s) сети. Напомним, что ME(s)=l при 5 = 0. Поскольку f7E(s) = рЕ ME(s), то рЕ = ЙРХО), откуда следует, что 117 ME(s) = WE(s)lpE = W^s}! W^O). (3.2.9) Отметим, что ^E(s) можно выразить через 17-функции всех или некоторых ветвей исходной сети. Нетрудно вычислить значение 17Х0); для этого в выражении для fTE(s), получаемом из (3.2.8), надо положить 5 = 0. Вычисляяу-ю частную производную по 5 функции ME(s) и полагая 5=0, находиму'-й момент pjE относительно начала координат, т. е. (3.2.10) В частности, первый момент р\Е относительно начала координат есть математическое ожидание времени выполнения сети, а дисперсия времени выполнения сети равна разности между дгя и квадратом величины р\Е, т. е. (3.2.11) Следует отметить, что для точного нахождения функции распределения (или плотности вероятности) искомой выходной величины (в данном случае, нормативного времени исполнения распределенного алгоритма в автоматизированной ОТС) требуется по известной эквивалентной 17-фуикции GERT-сети определить большое число моментов qJ Pje=—г [МЕ (5)] 5=0 относительно начала координат и использовать dsJ разложение функции в ряд Тейлора [79,85]. Так как в вычислительном отношении данная задача достаточно трудна, дуги сети характеризуются либо экспоненциальным распределением, либо дискретным. [80],. что существенно облегчает решение задачи. В [65] рассматривается численный метод нахождения непрерывной плотности распределения вероятностей выходной величины GERT-сети при условии, что множество распределений, которыми характеризуются отдельные дуги модели, включает в себя: дискретное, биномиальное, пуассоновское, геометрическое, отрицательное биномиальное, равномерное, экспоненциальное, гаммаи нормальное распределения. Как правило, 118 |