Метод включения-исключения

Метод включения-исключения (Inclusion-Exclusion или IE – метод) основан на использовании минимальных путей и минимальных сечений.

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

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

IE – метод является классическим методом получения точного выражения для надежности в структурах общего вида (теорема Пуанкаре-Сильвестра).

Пусть граф имеет l – минимальных путей, – событие, которое заключается в том, что все элементы пути работают. Вероятность того, что путь работает:

Система из l путей работает, если работает хотя бы один путь. Тогда работоспособность системы будет определяться как

Иными словами, надежность системы равна вероятности объединения всех событий .

Надежность системы, которая равна вероятности объединения l минимальных путей, может быть выражена как

где – сумма вероятностей того, что l минимальных путей работают.

Формула является общим выражением IE – метода.

Анализируя формулу можно увидеть, что добавляется, исключается, добавляется, исключается и т.д. В процессе добавления и исключения определяется верхняя и нижняя границы надежности системы:

(16)

Строгое неравенство имеет место, когда добавлены и исключены все l компонентов:

(17)

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

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