|
Обозначим через p,j — вероятность того, что операция (/, j) будет выполнена при условии, что узел i выполнен. Для случайной величины Yy определим W-функцию как Wij(s)= puMij(s). (3.3) С помощью преобразования (3.3) всегда можно определить сеть G', структура которой идентична структуре сети G, только вместо двух параметров дуг ру и уу присутствует один параметр Wy. На рис. 2.6 изображены дуга сети G и соответствующая ей дуга сети G'. Рис.3.6. Сети G и G' а элемент сети G; б элемент сети G' В описание системы ГЕРТ мы включили в качестве параметра дуги время выполнения соответствующей операции алгоритма. В действительности можно рассматривать также любой характерный параметр процесса, который обладает аддитивностью по дугам любого пути. Если времена выполнения операций сети G представляются независимыми случайными величинами, то G' обладает рядом свойств, представляющих интерес с вычислительной точки зрения. Для изучения этих свойств рассматриваются зри частных случая 1) G' состоит из двух последовательных дуг; 2) G' — из двух параллельных ветвей, 3) G' — из одной ветви и одной петли [53]. Показано, что если ГЕРТ-сеть состоит из параллельных и последовательных цепей и (или) петель, то она может быть преобразована в эквивалентную сеть, состоящую из одной единственной ветви. На самом деле, данный результат обобщается на любую ГЕРТ-сеть, поскольку можно комбинировать базисные преобразования. 105 |
В частности, A/y(s) = £[esa] = esa при yy = а = const. Если а = 0, то A/y(s) = 1. В приложении 3 представлена таблица, в которой описаны некоторые наиболее важные функции распределения, указаны соответствующие производящие функции моментов и первые (математические ожидания) й вторые моменты относительно начала координат. Обозначим через ру — вероятность того, что операция (/, у) будет выполнена при условии, что узел i выполнен. Для случайной величины Yy определим W-функцию как Wy(s}=PijMy(s). (3.2.1) С помощью преобразования (3.2.1) всегда можно определить сеть G', структура которой идентична структуре сети G, только вместо двух параметров дуг ру и у у присутствует один параметр Wy. На рис. 3.2.1 изображены дуга сети G и соответствующая ей дуга сети G'. а б Рис. 3.2.1 Сети G и G' а элемент сети G; б — элемент сети G' В описание системы GERT мы включили в качестве параметра дуги время выполнения соответствующей операции алгоритма. В действительности можно рассматривать также любой характерный параметр процесса, который обладает аддитивностью по дугам любого пути. Если времена выполнения операций сети G представляются независимыми случайными величинами, то G' обладает рядом свойств, представляющих интерес с вычислительной точки зрения. Для изучения этих свойств далее рассмотрим три частных случая 1) G' состоит из двух последовательных дуг; 2) G' — из двух параллельных ветвей, 3) G' — из одной ветви и одной петли. 112 эквивалентной дуге, а затем эти дуги преобразовать в сеть, состоящую из одной ветви, эквивалентную исходной системе. Пусть (/, у) — ветвь, эквивалентная сети. Из (3.2.2) и (3.2.3) следует; что вес ветви (z,y) равен Wy = Wb + WaWb + Wa 2Wb + ... = 1ГЬ[1+ ]. /77 — 1 Данное выражение, в котором мы временно опустили аргументы FT-функций, можно упростить, зная, что биномиальный ряд (1—WJ'1 раскладывается следующим образом: (1 1¥аУ{ = 1 + Wa + W% + +... = 1 + Таким образом, окончательно имеем ^.(5) = Wb (s)[l Wa (Л)Г' = Wb (s)/[l FF„(s)] . (3.2.4) Следовательно, сеть сводится к одной единственной эквивалентной ей ветви, для которой W-функция равна й^(^) = fPb(s)/[ 1—f^a(s)]. Отметим, что описанная процедура может быть использована и для контуров, поскольку с помощью формулы (3.2.2) контур сводится к петле. Таким образом, если GERT-сеть состоит из параллельных и последовательных цепей и (или) петель, то она может быть преобразована в эквивалентную сеть, состоящую из одной единственной ветви. На самом деле, данный результат обобщается на любую GERT-сеть, поскольку можно комбинировать базисные преобразования. При использовании системы GERT необходимо учитывать основные положения и аппарат теории потоковых графов. Для нас существенно, что процесс может быть определен как совокупность активных взаимодействующих между собой элементов, которые выполняют некоторые функции. Для графического описания таких систем наиболее широко используются потоковые графы. В потоковом графе элементы системы представляются узлами, а взаимосвязь между элементами, или функции перехода, — дугами. Основным элементом потокового графа является ориентированная ветвь, направленная из узла i в узел у, с параметром ty. Направление ветви 114 |