|
L Pa+Pb = Wa(s) + Wb(s) (2.3.3) Формула (2.3.3) также может быть обобщена на случай сетей, состоящих из трех и более параллельных ветвей: W-функция для эквивалентной ветви равна сумме W-функций для параллельных дуг. Петли. Рассмотрим простую сеть, состоящую из одной петли и одной дуги. Она может быть преобразована в эквивалентную сеть, содержащую только одну дугу. Отметим, что рассматриваемая сеть может быть преобразована. Эта новая сеть будет состоять из бесконечной последовательности параллельных цепей, каждая из которых представляет собой совокупность последовательных ветвей. Поэтому можно вначале каждую ее цепь свести к эквивалентной дуге, а затем эти дуги преобразовать в сеть, состоящую из одной ветви, эквивалентную исходной системе. Пусть (г, у) — ветвь, эквивалентная сети. Из (2.3.2) и (2.3.3) следует, что вес ветви (г, у) равен Wy = Wb + WaWb + Wa 2Wb + ... = Ж,[1 + ]. m=l Данное выражение, в котором мы временно опустили аргументы W-функций, можно упростить, зная, что биномиальный ряд (1—WJ1 раскладывается следующим образом: (1 Wa)"’ = 1 + Ж, + W2 + W2 +... = 1 + £. т=1 Окончательно имеем Ж7(*) = ад[1-ВДГ' =ИШ/[1-ВД]. (2.3.4) Следовательно, сеть сводится к одной единственной эквивалентной ей ветви, для которой W-функция равна Ж/^) = —Ж/s)]. Отметим, что описанная процедура может быть использована и для контуров, поскольку с помощью формулы (2.3.2) контур сводится к петле. Таким образом, если GERT-сеть состоит из параллельных и последовательных цепей и (или) петель, то она может быть преобразована в 90 |
Последовательные дуги. Рассмотрим простую сеть, состоящую из двух последовательных ветвей. Эти две ветви могут быть заменены одной эквивалентной им ветвью, как показано ниже. Исходные ветви имеют Wпреобразования Wy(s) = pyMy(s), Wik(s) = pyM^s). И'-функция для эквивалентной ветви (г, к) имеет вид Wyfs) = pikMyfs). Напомним, что производящая функция моментов суммы двух независимых случайных величин равна произведению производящих функций моментов этих величин. Тогда ПОСКОЛЬКУ pik ^PyPik и Mik(s) = [Myftj][M;k(s)]f ТО Wik(s) = [pijMjj(s)][pjkMjk(s)] = Wij(s)Wik(s). (3.2.2) Основной результат (3.2.2) может быть обобщен на случай трех и более ветвей: JF-функция для эквивалентной, ветви равна произведению Wфункций для последовательных ветвей. Параллельные ветви. Рассмотрим простую сеть, состоящую из двух параллельных ветвей. Доказано, что эти ветви могут быть заменены эквивалентной ветвью. Пусть (/, у)—такая ветвь. По определению Wy(s) =PyMy(s). В этом случае ру = ра + рь и My(s) = \paMa(s)+pbMb(s)}l{pa+pb). Поэтому W,j (5) = [ра + рь + = W„ (s) + Wb (s) (3.2.3) L Pa + Pb J Формула (3.2.3) также может быть обобщена на случай сетей, состоящих из трех и более параллельных ветвей: ^-функция для эквивалентной ветви равна сумме РК-функций для параллельных дуг. Петли. Рассмотрим простую сеть, состоящую из одной петли и одной дуги. Она может быть преобразована в эквивалентную сеть, содержащую только одну дугу. Отметим, что рассматриваемая сеть может быть преобразована. Эта новая сеть будет состоять из бесконечной последовательности параллельных цепей, каждая из которых представляет собой совокупность последовательных ветвей. Поэтому можно вначале каждую ее цепь свести к из эквивалентной дуге, а затем эти дуги преобразовать в сеть, состоящую из одной ветви, эквивалентную исходной системе. Пусть (/, у) — ветвь, эквивалентная сети. Из (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 |