Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 65
Текст из файла (страница 65)
Петли второго порядка в замкнутом потоковом графе. Рис. 5.15. Петли третьего порядка в замкиутом потоковом графе. пропускания эквивалентного ей потокового графа равен произведению коэффициентов пропускания каждой ветви. По определению петля порядка и состоит из и не связанных между собой петель первого порядка. Если каждую из этих петель первого порядка преобразовать в эквивалентный потоковый граф, состоящий из одной ветви, то исходную петлю порядка и можно будет рассматривать как связную последовательность таких ветвей.
Отсюда следует, что коэффициент про- 397 Новыв вонвосм пускания петли порядка и равен произведению коэффициентов пропускания и петель первого порядка. Рассмотрим теперь общий случай. Пусть Ь«, Ьа<, ..., Ь,1— л не связанных между собой петель первого порядка заданной петли порядка и. Выше было установлено, что для каждой петли Ьа< первого порядка эквивалентный .коэффициент пропускання Та равен произведению коэффициентов пропускания ветвей, принадлежащих этой петле, т.
е. 7ь= П 1ы. (5.16) п,па.„, Следовательно, для петли порядка и эквивалентный коэффициент пропускания Т(1.,) равен л а 7'('-.)= П 7'ь = П П;~~~ . (5.17) а-< а-«с, П аьаа Основной результат (5.17) будет использован для определения поведения систем, которые могут быть описаны ГЕРТ-сетями. зпз. ПРАВИЛО МЕЙСОНА ДЛЯ ЗАМКНУТЫХ ПОТОКОВЫХ ГРАФОВ Цель использования системы ГЕРТ в стохастическом сетевом анализе состоит в вычислении математического ожидания и дисперсии времени выполнения сети (которые рассматриваются здесь как общий параметр сети) и вероятности выполнения )Ре О) ВА (а) Рнс.
6.16. Замкнутая стохастяческая сеть. стока (или стоков). Очевидно, что коэффициент пропускания дуги ГЕРТ-сети есть соответствующая аУ-функция. Напомним, что ну-функция дуги определяется как произведение вероятности выполнения этой дуги и производящей функции моментов для времени выполнения операции, представленной этой дугой.
В предыдущем разделе мы показали, как определить все петли замкнутого потокового графа. Для того чтобы применить эти результаты к открытой сети, необходимо ввести дополни- Глава а тельную дугу с %'-функцией аул(з), соединяющую сток 1 с источником з. Затем для модифицированной сети нужно найти все петли (вплоть до максимально возможного порядка). Функция йУл(з) необходима для того, чтобы найти эквивалентную иГ-функцию для исходной сети. На рис. 5.16 исходная сеть изображена в виде «черного ящика» с Я7-функцией Яуе(з). Напомним, что эквивалентный коэффициент пропускания для петли порядка и равен произведению коэффициентов пропускания п не связанных между собой петель первого порядка, т. е. т(1.„)= Пт„.
л-1 (5.18) Топологическое уравнение для замкнутых графов, известное также как правило Мейсона, имеет следующий вид: и=1 — '~ т((.,)+~~~ТУ.,) — ~~ т(Ц+...+ +( — 1) ~т(1.„)+...=6, (5.19) где ХТ(Е;) — сумма эквивалентных коэффициентов пропускания для всех возможных петель (-го порядка. Иными словами, при использовании топологического уравнения необходимо выполнить следующие шаги: 1. Вычислить эквивалентный коэффициент пропускания для всех петель порядка и.
2. Просуммировать полученные величины по всем петлям порядка т и результат умножить на ( — 1) . Отметим, что для петель с четным порядком величина ( — 1)~ положительная, а для петель с нечетным порядком — отрицательная. В топологиком уравнении (5.19) перед каждым слагаемым поставить знак плюс или минус. 3.
К выражению, полученному на шаге 2, прибавить 1 и результат приравнять к нулю. В качестве примера рассмотрим рнс. 5.16. Данный замкнутый потоковый граф содержит одну петлю первого порядка с эквивалентным коэффициентом пропускания, равным Юл(з)Юв(з). По правилу Мейсона получаем, что 1 — (вл(з) (Рв(з) =0 или ((Ул(з) =1/1Рв(з). Отметим, что функция Игл(з) содержится в топологическом уравнении, поскольку оиа является элементом по крайней мере одной петли первого порядка.
Важность результата, полученного при рассмотрении данного примера, состоит в том, что если в топологическом уравнении Юл(з) заменить на 1/(Рв(з) и решить его относительно В'в(з), то будет получена эквивалентная а7-функция для исходной стохастической сети. Новые вояросы В качестве другого примера рассмотрим открытую сеть, изображенную на рис. 5.17. Чтобы определить эквивалентную яу-функцию для этой сети, нужно выполнить следующие шаги: Рис. 8.17. Открытая стохастическая сеть.
1. Замкнуть данную сеть дугой, ведущей из узла 4 в узел 1. 2. Найти все петли порядка и. 3. С помощью топологического уравнения (5.19) получить выражение для %'я(з). я, Рис. 8.18. Замкнутая стохастическая сеть. На рис. 5.18 изображена модифицированная сеть, в которой для удобства записи опущен аргумент з у 117-функций. Если В'2(з) заменить на 1/йре(з), то из (5.17) для петель сети будут получены следующие коэффициенты пропускания. Петли первого порядка: % ь (~3974, иузиузвуз, йуз (т 3 973 (1~1(Уе) . Петля второго порядка: иУ~Кзи74 Используя (5.19), получаем Н 1 — МУ вЂ” Мг,((У вЂ” йУУ,(82,— йУУ%',(1ЛУ )+Яг,йУ (Р,= О. Поэтому р(е(з) 11 21' 31" 37(1 1" 1 11 211' 4 1(' 21" 31" 3+1(71 "731( 4)~ что является эквивалентной ит"-функцией для сети, изображенной на рис.
5.17. В следующем разделе покажем, как с помощью этого равенства можно вычислить математическое ожидание и дисперсию времени выполнения сети (или подсети). Глава 5 5.16. ВЫЧИСЛЕНИЯ МАТЕМАТИЧЕСКОГО ОЖИДАНИЯ И ДИСПЕРСИИ Из топологического уравнения (5.19) было получено выражение для эквивалентной Ф'-функции 575(з) сети. Напомним, что Мв(з) =1 при 5=0.
Поскольку я7з(з) =рвМз(з), то рв= = Юв(0), откуда следует, что Мз(з)='ггз(зУРа= 1(гз(з)11гз(0). (5.20) Отметим, что йув(з) можно выразить через зУ-функции всех или некоторых ветвей исходной сети. Нетрудно вычислить значение (рв(0); для этого в выражении для 1(ув(з), получаемом из (5.19), надо положить 5=0. Вычисляя 1-ю частную производную по з функции Мз(з) и полагая 5=0, находим /-й момент п1в относительно начала координат, т. е. дз рч = —,.
(М (з)1~.-~. (5.21) В частности, первый момент 1мз относительно начала координат есть математическое ожидание времени выполнения сети, а дисперсия времени выполнения сети равна разности между (лев и квадратом величины ры, т. е. рве (рзе) ' (5.22) 5.17. ПРИМЕНЕНИЕ СИСТЕМЫ ГЕРТ 5.17.1. ПРОИЗВОДСТВО ПРЕЦИЗИОННЫХ ДЕТАЛЕЙ Будем считать, что а= 1. Тогда Мп(з) является производящей функцией моментов для продолжительности каждой дуги исходной сети. ГЕРТ-сеть для данной задачи изображена на рис.5.19. Поскольку вероятность изготовления доброкачественной дета.
ли равна 0,20, то 15',= ЕУз=0,80в*, 57з — — 1(74=0,20в*. Из тополо- Фирма, выполняющая государственные подряды, согласилась изготавливать прецизионные детали. Из-за строгого технического контроля вероятность того, что из заготовки будет произведена доброкачественная деталь, равна 0,20. Чему равно ожидаемое число проб, необходимых для изготовления двух доброкачественных деталей? В данной задаче предполагается, что время изготовления одной детали постоянно. Напомним, что если случайная величина Ун равна постоянной величине а, то М (з) Е Уа] ~а 401 Новаае вопросы гического уравнения следует, что Н= 1 — йт — %7 — йу Щ(рд+ЩГа = О, 1 — йу~ — йг — (Р 77~(1/%г~)+В'У = О, аг н (з) = ае а(а а/(1 1(г т 11' а'+ аг т(1' а).
Используя выражения для Угь (аа, йра и нга, получаем, что йув(з) =0,04еае1'(1 — 1,6е'+0,64е"). Поскольку рв=1, то ив(з) = и'1 нй Рнс. 5.19. ГЕРТ-сеть в задаче изготовления прецнаноннык деталей. =Мк(з). Таким образом, ожидаемое число проб, необходимых для изготовления двух доброкачественных деталей, равно 0Мл(е) ~ р„= -~ =10. !е-0 Аналогично дисперсия общего числа проб равна от=40. бн 72. ПРОЦЕСС ПЕРЕРАБОТКИ СЫРЬЯ (ПРИТСКЕР) Рассмотрим процесс производства полупроводника. Как показано на рис. 5.20, сырье вначале поступает в печь для очистки от примесей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
