|
что функция WA(s) содержится в топологическом уравнении, поскольку она является элементом, по крайней мере, одной петли первого порядка. Важность результата, полученного при рассмотрении данного примера, состоит в том, что если в топологическом уравнении Ж,(5) заменить на \/Wt(s) и решить его относительно W,.(s), то будет получена эквивалентная Ж-функция для исходной стохастической сети. Рассмотрим этап вычисления математического ожидания и дисперсии. Из топологического уравнения (3.6) было получено выражение для эквивалентной Ж-функции W/,(s) сети. Напомним, что M/{s)=l при 5 = 0. Поскольку WL(s) ~P f.M l(s), торЕ~ Ж/.{0), откуда следует, что Отметим, что fV^s) можно выразить через Ж-функции всех или некоторых ветвей исходной сети. Нетрудно вычислить значение Wt(0); для этого в выражении для IV/,(s), получаемом из (3.6), надо положить 5 = 0. Вычисляяj -ю частную производную по s функции ML(s) и полагая 5=0, находим/-Й момент Pje относительно начала координат, т. е. В частности, первый момент ц \е относительно начала координат есть математическое ожидание времени выполнения сети, а дисперсия времени выполнения сети равна разности между квадратом величины т. е. Следует отметить, что для точного нахождения функции распределения (или плотности вероятности) искомой выходной величины (в данном случае, нормативного времени выполнения распределенного алгоритма контроля знаний в АОС) требуется по известной эквивалентной Ж-функции GERT-сети определить большое число моментов M ,(s)=W ,(s)/pE= IV,,(5)/ IV,,(0). (3.7) (3.8) (?=И2Е-(Иид2(3.9) ds относительно начала координат и использовать 109 |
Рис. 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 |