Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 64
Текст из файла (страница 64)
ПО ОПрЕдЕЛЕНИЮ Таблица б.1. Моменты и производящие фуиииии моментов'! Второй момент тип распределения Математическое огкидан ил Ме(т) Биномиальное (В) ь и гко.. а.:" Р! +Рз+ Экспоненциальное (Е) (1 а! ('- )' Геометрическое(ОЕ) — Ее=— 1 — г' + Рг* Отрицательное ( Оиномиальное(МЗ) (1 — е' -(- рг*) ЫОРМаЛЬНОЕ(МО) е* +П!Ы.Ы* Пуассона (И ,)! — !) Равномерное (О) е* — г'! (а — Ы! лр( Л-Р1 — Л) пр Л! Т! -(- Л*т, + " Р! +Рз+ ' 1 и ь а 1 л г(1 — л) Р Р! ( Рз+ а! йь+ О а! .
с — р р! г(1 — Р](1 -(- г — гр) лн -Р а! л(1 ~- л) а е- «ь + ьз з ' и! л -(- ь л Отметим, что р)+рз+рз — — 1 и ре+рз+ра=1. Кроме того, дуги (4, 2), (1, 4), (1, 2), (1, 3), (4, 3) и (4, 5) соответствуют физическим процессам, которые можно описать плотностями распределения. Например, случайные величины, соответствующие операциям (1, 4) и (4, 5), могут быть нормально распределенными, операциям (1, 2) н (4, 3) — экспоненциально распределеннымн, а операциям (1, 3) и (4, 2) — равномерно распределенными.
Методы системы ГЕРТ позволяют ответить на следующие вопросы: 1. Какова вероятность того, что деталь будет сдана в металлолом? 2. Какова вероятность того, что деталь будет использована на линии сборки? 3. Какова вероятность того, что деталь поступит в розничную продажу? 4. Чему равны математическое ожидание и дисперсия времени, необходимого для изготовления детали, которая поступает на линию сборки? 5. Сколько времени будет потеряно, если деталь сдается в металлолом? В последующих разделах будет разработан аналитический подход, позволяющий ответить на эти вопросы.
Глава 6 операция (й 1) может быть выполнена только в том случае, если выполнен узел й Поэтому для изучения вопросов, связанных с выполнением этой операции, необходимо знать условную вероятность (в дискретном случае) или плотность распределения (в непрерывном случае) случайной величины Уц при условии, что узел 1 выполнен. Это в свою очередь позволит нам провести исследования, связанные с выполнением всей сети. В частности, мы сможем определить моменты распределения времени выполнения сети, с помощью которых будут вычислены математическое ожидание и дисперсия времени выполнения сети.
Пусть Гц — условная вероятность или плотность распределения времени выполнения операции (й 1). Условная производящая функция моментов случайной величины Уц определяется как Мц(з) =Е'1е ~ц1, т. е. эвц в ( 1 мл (для непрерывной случайной величины), Мц (з)= эвц э ( ) (для дискретнои случаиной ~~~ е т уы величины). В частности, Мц(з) =Е[еел)=еел при уц=а=сопз1. Если а=0, то Мц(з)=1. В табл. 5.1 описаны некоторые наиболее важные функции распределения и указаны соответствующие производящие функции моментов и первые (математические ожидания) и вторые моменты относительно начала координат. Пусть рц — вероятность того, что,операция (1, 1) будет выполнена при условии, что узел 1 выполнен.
Для случайной величины Уц определим тР-функцию 134, 351 как Яуц (з) = рцМц (з). (5.12) С помсацью преобразования (5.12) всегда можно определить сеть 6, структура которой идентична структуре сати 6, только вместо двух параметров дуг рц и уц присутствует один- пара- Рис. 6.6. Сети б и б'. а — элемент сети Сц б — элемент сети и'. метр %'ц.
На рис. 5.6 изображены дуга сети 6 и соответствующая ей дуга сети 6'. В описание системы ГЕРТ мы включили в качестве параметра дуги время выполнения соответствующей операции. 391 Новые вопросы В действительности можно рассматривать также любой характерный параметр, который обладает аддитивностью по дугам любого пути. Если времена выполнения операций сети 6 представляются независимыми случайными величинами, то 6' обладает рядом свойств, представляющих интерес с вычислительной точки зрения.
Для изучения этих свойств мы рассмотрим три частных случая: 1) 6' состоит из двух последовательных дуг; 2) 6'— из двух параллельных ветвей; 3) 6' — из одной ветви и одной петли. 5.12.1. ПОСЛ ЕДОВАТЕЛЪНЫЕ ДУГИ Рассмотрим простую сеть, изображенную на рис.
5.7. Она состоит из двух последовательных ветвей. Эти две ветви могут быть заменены одной эквивалентной им ветвью, как показано Рис, 5,7. Последовательные ветви и их эквивалентное представление. ниже. Исходные ветви имеют йУ-пРеобРазовании йуц(з) = =РНМН(з), 151ь(з) =РИМьь(з). 15'-функция для эквивалентной ветви (1, й) имеет вид нгьь(з) =ргьМга(з). Напомним, что производящая функция моментов суммы двух независимых случайных величин равна произведению производящих функций моментов этих величин. Тогда поскольку рм=рцр;ь и Мм(з) = = [Мц(з)) [М;ь(з)1, то 15тм (з) =[РцМи (и)[ (Р1ьМть (з)) = (Рц (з) Фза (з).
(5.13) Основной результат (5.13) может быть обобщен на случай трех и более ветвей; йу-функция для эквивалентной ветви равна произведению 15'-функций для последовательных ветвей. 5.12.2. ПАРАЛЛЕЛЬНЫЕ ВЕТВИ Рассмотрим простую сеть, изображенную на рис. 5.8. Она состоит из двух параллельных ветвей. Будет доказано, что этн ветви могут быть заменены эквивалентной ветвью. Пусть (1, 1) — такая ветвь. По определению вуц(з) =рцМц(з). В этом случае рц= ра+ рь и Мц (з) =''[раМа (и) +рьМь (з) У (Ра+ Рь) .
Поэтому (з) =[р +р [ ~~' '(1 Р' ь(1 ~ =%' (з)+15ь(з). (5.14) Ра+ Рь 392 Глава Б Формула (5.14) также может быть обобщена на случай сетей, состоящих из трех и более параллельных ветвей: й7-функция для эквивалентной ветви равна сумме ну-функций для параллельных дуг. ль "'ь Рис. 5.8. Параллельные ветви и их эквивалентное представление. 5.12.3. ПЕТЛИ Рассмотрим простую сеть, изображенную на рис. 5.9. Она состоит из одной петли и одной дуги и может быть преобразована в эквивалентную сеть, содержащую только одну дугу.
~а. н Рис. 5.9. Сеть с петлей и ее эквивалентное представление. Отметим, что рассматриваемая сеть может быть преобразована в сеть, изображенную на рис. 5.10. Эта новая сеть состоит из бесконечной последовательности параллельных цепей, каждая из которых представляет собой совокупность последова- Рнс. 5.10. Представление петель в виде параллельных и последовательных дуг. Новые волросы тельных ветвей. Поэтому можно вначале каждую ее цепь свести к эквивалентной дуге, а затем эти дуги преобразовать в сеть, состоящую из одной ветви, эквивалентную исходной системе. Пусть (1, 1) — ветвь, эквивалентная сети, изображенной на рис. 5.10.
Из (5.13) и (5.14) следует, что вес ветви (1, 1) равен е (е и = аз+ зуа)(рь+)ььез((рь+ ...= зрь11+ Х 1Г',"') . Данное выражеы 1 ние, в котором мы временно опустили аргументы Я7-функций, можно упростить, зная, что биномнальный ряд (1 — 1(ре) ' раскладывается следующим образом: (1 1(Уе)-ь 1+1Уе +йт з+1Р з+ 1+~~~ йр ы ы 1 Таким образом, окончательно имеем 11711 (з) = йуь (з) (1 — 11гв (з))-' =%'ь (з)/[1 — 117, (з)). (5.15) Следовательно, сеть, изображенная на рис. 5.10, сводится к одной-единственной эквивалентной ей ветви, для которой В'-функция равна Уп(з) = явь(з)/[1 †з(з)1. Отметим, что описанная процедура может быть использована и для контуров, поскольку с помощью формулы (5.13) контур сводится к петле. Таким образом, если ГЕРТ-сеть состоит из параллельных и последовательных цепей и (нли) петель, то она может быть преобразована в эквивалентную сеть, состоящую из одной-единственной ветви.
На самом деле, данный результат обобщается на любую ГЕРТ-сеть, поскольку можно комбинировать базисные преобразования. Перед тем как перейти к рассмотрению новых вопросов, нам хотелось бы познакомить читателя с основными понятиями, касающимися потоковых графов и необходимыми для понимания последующего материала. Данный раздел мы завершим кратким описанием основных шагов системы ГЕРТ: 1. Представить систему в виде стохастической сети с ГЕРТ- узлами. 2.
Для каждой дуги сети определить условную вероятность и производящую функцию моментов. З..Для каждой дуги сети вычислить йГ-функцию. 4. Преобразовать сеть в эквивалентную сеть, состоящую из одной ветви. ЗЛЗ. ОСНОВНЫЕ ПОНЯТИЯ О ПОТОКОВЫХ ГРАФАХ Система может быть определена как совокупность активных взаимодействующих между собой элементов, которые выполняют некоторые функции.
В дальнейшем мы будем рассматривать 26-1664 394 Глава о О з кь =п1к~ + п~х~ 6.14. ОПРЕДЕЛЕНИЯ Петля: связная последовательность ориентированных ветвей, каждый узел которых является общим ровно для двух ветвей. Петлю обычно называют петлей первого порядка, чтобы указать на то, что она не содержит других петель и что каждый узел можно достичь из любого другого узла. Собственную петлю'> можно рассматривать как вырожденную петлю первого порядка. о То есть петлю, состоящую не одной ветви.
— Прим. нерев, только такие системы, в которых элементы и взаимосвязь между элементами описываются линейными уравнениями. Для графического описания таких систем наиболее широко используются потоковые графы. В потоковом графе элементы системы представляются узлами, а взаимосвязь между элементами, или функции перехода, — дугами. Основным элементом потокового графа является ориентированная ветвь, направленная из узла 1 в узел 1, с параметром 1и.
Направление ветви указых~ 2 „, вает связь по входу и выходу между двумя переменными, представленными узлами этой ОЗ ветви. Узел 1 соответствует независимой переменной хь а узел 1 — независимой переменной хр Параметр 1и обычно называют коэффициеитолг проРнс. 5.1!. Основное свойство потаповых графов. пускании дуги. Он равен множителю, используемому для того, чтобы преобразовать величину х; до рассмотрения ее как части величины хь Основное свойство потоковых графов заключается в том, что величина узла равна сумме преобразованных величин узлов, соединенных с рассматриваемым узлом входящими в него дугами.
В качестве примера рассмотрим элементарный потоковый граф, изображенный на рис. 5.11. Основные свойства потоковых графов могут быть использованы для разработки методов, позволяющих обращаться непосредственно с элементами графа, в результате чего он будет преобразован в эквивалентный граф с более простой структурой и, следовательно, упростится решение задачи. Наиболее известным результатом в данной области является топологическое уравнение Мейсона 1341, которое может быть использовано для потоковых графов с произвольной структурой. Для рассмотрения уравнения Мейсона нам понадобятся некоторые определения. Новые вопросы 393 Петли порядка и: множество и не связанных между собой петель первого порядка.
Замкнутагй потоковый граф: граф, в котором каждая ветвь принадлежит по крайней мере одной петле. В качестве примера рассмотрим потоковый граф, изображенный на рис. 5.!2, для которого найдем все петли и определим их порядок. Рис. 3.19. Потоковый граф с петлями. Рис. 3.13. Петли первого порядка в замкнутом потоковом графе. Нетрудно заметить, что данный потоковый граф является замкнутым, поскольку он целиком состоит из петель. На рис. 5.13, и 5.14 и 5.15 изображены петли первого, второго и третьего порядка соответственно для графа, приведенного на рис.5.12. Как было определено выше, петля второго (третьего) порядка — зто множество, состоящее из двух 1трех) не связанных между собой петель первого порядка.
Например, петли Ег и Еа 26в Глава 5 образуют петлю второго порядка, а петли Ьь Еа и Ьз — петлю третьего порядка. Петлю первого порядка можно рассматривать как цепь, состоящую из последовательно соединенных ориентированных ветвей, концевые узлы которой совпадают. Поэтому коэффициент Рис. 5.14.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
