Метод сечений или совокупности путей

Рассмотрим еще один метод расчета структурной надежности сетей. Предположим, что необходимо определить вероятность связности сети между заданной парой узлов A и B.

Критерием исправной работы сети в данном случае является наличие хотя бы одного пути передачи информации между рассматриваемыми узлами. Предположим, что имеется список возможных путей в виде перечня элементов (узлов и направлений связи), входящих в каждый путь. В общем случае пути будут зависимы, поскольку любой элемент может входить в несколько путей. Надежность Rs любого пути s можно вычислить по формуле последовательного соединения , где pi s – надежность элемента i пути s.

Искомая надежность  зависит от надежности каждого пути и вариантов их пересечений по общим элементам. Обозначим надежность, которая обеспечивается первыми r путями, через . Добавление очередного (r + 1) пути, с надежностью , очевидно, приведет к увеличению структурной надежности, которая теперь будет определяться объединением двух событий: исправен хотя бы один из первых r путей или исправен (r + 1)-й путь. Вероятность наступления этого объединенного события с учетом возможной зависимости отказов (r + 1)-го и остальных путей

 

,(1.2)

 

где  – вероятность исправности хотя бы одного из первых r путей при условии, что исправен (r + 1)-й путь.

Из определения условной вероятности  следует, что при ее расчете вероятность исправной работы всех элементов, входящих в (r + 1)-й путь, необходимо положить равной единице. Для удобства дальнейших расчетов представим последний член выражения (1.2) в следующем виде:

,(1.3)

где символ (¤) означает, что при перемножении показатели надежности всех элементов, входящих в первые r путей и общих с (r + l)-м путем, заменяются единицей. С учетом (1.3) можно переписать (1.2):

∆ ,(1.4)

 

где ∆ – приращение структурной надежности при введении

(r + 1) ‑ пути;  ‑ вероятность того, что произойдет одновременный отказ первых r путей.

Учитывая, что приращение надежности ∆Hr+1 численно равно уменьшению ненадежности ∆Qr+1 получаем следующее уравнение в конечных разностях:

∆ . (1.5)

 

Легко проверить, что решением уравнения (1.5) является функция:

 

(1.6)

 

В случае независимых путей операция символического умножения совпадает с обычным умножением и выражение (1.6) дает коэффициент простоя системы, состоящей из параллельно включенных элементов. В общем случае необходимость учета общих элементов путей заставляет производить умножение согласно (1.6) в алгебраическом виде. При этом число членов в результирующей формуле с умножением на каждый очередной двучлен удваивается и окончательный результат будет иметь 2r членов, что эквивалентно полному перебору совокупности всех r путей. Например, при r = 10 число членов в окончательной формуле превысит 1000, что уже выходит за рамки ручного счета. С дальнейшим увеличением числа путей довольно быстро исчерпываются и возможности современных ЭВМ.

Однако свойства введенной выше операции символического умножения позволяют существенно сократить трудоемкость расчетов. Рассмотрим эти свойства более подробно. Согласно операции символического умножения для показателя надежности pi любого элемента справедливо следующее правило:

 

pi ¤ pi = pi (1.7)

 

Напомним, что второй сомножитель (1.7) имеет смысл вероятности исправной работы i-го элемента при условии его исправности, которая, очевидно, равна единице.

Для сокращения дальнейших выкладок введем следующее обозначение ненадежности i-го элемента:

 

 (1.8)

 

С учетом (1.7) и (1.8) можно записать следующие простые правила преобразования выражений:

1. ;

2. ;

 

;(1.9)

 

3. ;

4. ;

5. ;

Для примера использования этих правил при расчете надежности рассмотрим простейшую сеть связи, изображенную на рисунке 1.3. Буквы, стоящие у ребер графа, обозначают показатели надежности соответствующих линий связи. Узлы для простоты будем считать идеально надежными. Предположим, что для связи между узлами А и В можно использовать все пути, состоящие из трех и менее последовательно включенных линий, то есть следует учесть подмножество путей{μ} = { ab, cdf, cgb, ahf }. Определим приращение надежности, обеспечиваемое каждым последующим путем, по формуле (1.4) с учетом (1.6):

∆ ,(1.10)

 

где  аналогично (1.8).

 

Рисунок.1.3 - Пример сети расчета на ограниченном подмножестве путей

 

Рисунок 1.4 - Пример сети для расчета надежности по полной совокупности путей

 

Применяя последовательно формулу (1.10) и правила символического умножения (1.9) к рассматриваемой сети, получаем:

 

∆ ;

 

∆ ;

 

∆ ;

 

∆ .

 

При расчете последнего приращения мы использовали правило 4, которое можно назвать правилом поглощения длинных цепей короткими; в данном случае его применение дает b ¤ cgb = b. Если разрешено использование других путей, например пути cdhb, то не представляет труда рассчитать обеспечиваемое им приращение надежности ∆ . Результирующую надежность сети можно теперь вычислить как сумму приращений, обеспечиваемых каждым из рассмотренных путей:

 

HR = ∆Hi (1.11)

 

Так, для рассмотренного примера в предположении, что надежность всех элементов сети одинакова, то есть a = b = c = d = f = h = g = p, получаем:

 

.

 

При машинной реализации в основу расчета можно также положить формулу (1.5) ,с учетом того, что

∆ .(1.12)

 

Таким образом, окончательное выражение, согласно формуле (1.5), можно записать в виде следующего рекуррентного соотношения:

 

. (1.13)

 

При начальном условии , на каждом последующем шаге из полученного ранее выражения для  следует вычесть произведение надежности очередного  пути на это же выражение, в котором показатели надежности всех элементов, входящих в путь , нужно положить равными единице.

В качестве примера рассчитаем надежность сети, изображенной на рисунке 1.4, относительно узлов А и В, между которыми имеется 11 возможных путей передачи информации. Все расчеты сведены в таблицу 1.1: перечень элементов, входящих в каждый путь, результат умножения надежности данного пути на значение Qr, полученное при рассмотрении всех предыдущих путей, и результат упрощения содержимого третьего столбца по правилам (1.9). Окончательная формула для  содержится в последней колонке, если ее читать сверху вниз.

 

Таблица 1.1 Результаты расчета надежности сети, изображенной на рисунке 1.4

Номер Пути
1						-
2						-
3
4
5				-
	6				- - -
	7				- - -
	8				- - - -
	9				- - - - -
	10				- - - - -
	11				- - - -

 

 

Для уменьшения объема вычислений не следует без необходимости раскрывать скобки; если промежуточный результат допускает упрощения (приведение подобных членов, вынесение за скобку общего множителя и так далее), их следует выполнить.

Поясним несколько шагов расчета. Поскольку Q0 = 1 (при отсутствии путей сеть разорвана), то для Q1 из (1.13) . Делаем следующий шаг и, согласно (1.13), получаем:  и так далее.

Рассмотрим подробнее шаг, на котором учитывается вклад пути 9. Произведение показателей надежности составляющих его элементов, записанное во втором столбце таблицы 1.1, переносится в третий. Далее в квадратных скобках записана вероятность разрыва всех предыдущих восьми путей, накопленная в четвертом столбце (начиная с первой строки), с учетом правила (1.7), согласно которому показатели надежности всех элементов, вошедших в путь 9, заменяются единицами. Вклад четвертой, шестой и седьмой строк оказывается равным нулю по правилу 1. Далее выражение, стоящее в квадратных скобках, упрощается по правилам (1.9) следующим образом:

 

.

 

Аналогичным образом производится расчет относительно всех других путей.

Использование рассматриваемого метода позволяет получить общую формулу структурной надежности, содержащую в рассмотренном случае всего 15 членов вместо максимального числа 211=2048, получающегося при непосредственном перемножении вероятностей отказов этих путей. При машинной реализации метода удобно представить все элементы сети в позиционном коде строкой бит и использовать встроенные булевы функции для реализации логических элементов преобразований (1.9).

До сих пор рассматривались показатели структурной надежности сети относительно выделенной пары узлов. Совокупность таких показателей для всех или некоторого подмножества пар может достаточно полно характеризовать структурную надежность сети в целом. Иногда используется другой, интегральный, критерий структурной надежности. По этому критерию сеть считается исправной, если имеется связь между всеми ее узлами и задается требование на вероятность такого события.

Для расчета структурной надежности по этому критерию достаточно ввести обобщение понятия пути в виде дерева, соединяющего все заданные узлы сети. Тогда сеть будет связана, если существует, по крайней мере, одно связывающее дерево, и расчет сводится к перемножению вероятностей отказа всех рассматриваемых деревьев с учетом наличия общих элементов. Вероятность отказа дерева s определяется аналогично вероятности отказа пути, то есть:

,

 

где pis – показатель надежности элемента i, входящего в дерево s; ns – число элементов в этом дереве.

Рассмотрим для примера простейшую сеть в виде треугольника, стороны которого взвешены показателями надежности а, b, с соответствующих ветвей. Для связности такой сети достаточно существования, по крайней мере, одного из деревьев аb, bс, са. Используя рекуррентное соотношение (1.4), определяем вероятность связности этой сети

 

H cb = ab + bca + cab.

 

Если а = b = с = р, получаем следующее значение вероятности связности, которое легко проверить перебором:

 

H cb = 3р2 – 2р3.

 

Для расчета вероятности связности достаточно разветвленных сетей вместо перечня связывающих деревьев, как правило, удобнее пользоваться перечнем сечений {σ} которые приводят к потере связности сети по рассматриваемому критерию. Легко показать, что для сечения справедливы все введенные выше правила символического умножения, только вместо показателей надежности элементов сети в качестве исходных данных следует использовать показатели ненадежности q = 1 – p. Действительно, если все пути или деревья можно считать включенными “ параллельно ” с учетом их взаимозависимости, то все сечения включены в этом смысле “ последовательно ”. Обозначим вероятность того, что в некотором сечении s нет ни одного исправного элемента, через . Тогда можно записать

 

,(1.14)

 

где qis – показатель ненадежности элемента, входящего в пятое сечение.

Вероятность Нcb связности сети можно тогда представить аналогично (1.6) в символическом виде:

 

,(1.15)

 

где r – число рассматриваемых сечений. Другими словами, для того чтобы сеть была связна, необходимо, чтобы одновременно были исправны хотя бы по одному элементу в каждом сечении с учетом взаимной зависимости сечений по общим элементам. Формула (1.15) является в некотором смысле двойственной по отношению к формуле (1.6) и получается из последней заменой путей на сечения и вероятностей исправной работы на вероятности пребывания в состоянии отказа. Аналогично двойственным по отношению к формуле (1.13) является рекуррентное соотношение:

 

Hr+1 = Hr – πr+1 ¤ Hr.(1.16)

Рассчитаем для примера вероятность связности рассмотренной выше треугольной сети с набором сечений ab, bc, ca. Согласно (1.15) при начальном условии  имеем:

 

Hcd = ab – bca – cab,

а при одинаковых показателях ненадежности элементов сети (a = b = c = q) получим: . Этот результат совпадает с ранее полученным по методу перечисления деревьев.

Метод сечений можно, конечно, применять и для расчета вероятности связности сети относительно выделенной пары узлов, особенно в тех случаях, когда число сечений в рассматриваемой сети значительно меньше числа нулей. Однако наибольший эффект в смысле сокращения трудоемкости вычислений дает одновременное использование обоих методов.