Методы вычисления вероятности связности сети

Задача вычисления вероятности связности сети является по своей природе комбинаторной и связана с необходимостью перебора вариантов, число которых быстро возрастает при увеличении

размеров сети. Совокупность методов решения этой задачи может быть разбита на аналитические, методы предельных оценок и методы Монте-Карло. Ниже приводятся наиболее характерные методы из этих групп.

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

При заданных вероятностях исправности линий связи вероятность состояния сети определяется следующим образом:

Введя переменную

можно записать соотношение для вычисления вероятности связности сети:

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

Изложенный метод весьма прост для расчетов на ЭВМ, но для больших сетей нереализуем из-за объема вычислений. Последний может быть уменьшен, если не рассматривать варианты, для которых

Асимптотические оценки вероятности связности. При сравнении вариантов структуры сети могут быть использованы асимптотические оценки нижней и верхней границ вероятности связности. Нижняя граница [17]

Максимум определяется по множеству базисных сечений. Верхняя оценка [16]

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

При использовании граничных методов значительно сокращается объем вычислений.

Метод Монте-Карло. Отмеченные недостатки методов, относящихся к предыдущим группам, делают наиболее предпочтительным использование для оценки вероятности связности метода Монте-Карло. Данный метод при значительной простоте реализующего алгоритма позволяет получить результаты сколь угодно высокой точности практически для любой реализуемой структуры сети.

В качестве исходных данных составляется вектор Далее производится определенное число экспериментов в каждом из которых генерируется случайных чисел с заданным законом распределения и строится матрица смежностей. Если оказывается, что то соответствующий элемент матрицы смежности принимается равным 0, в противном случае — 1. Таким образом, образуется некоторый случайный подграф сети

После проведения всех экспериментов с проверкой связности в каждом из них вычисляется вероятность связности

где определяется (4.68).

Точность получаемого значения определяется числом проведенных экспериментов [24]:

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

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