Принятие решения о надёжности (ненадёжности) сети с ограничением на диаметр по отношению к заданному порогу

Назначение – позволяет устанавливать, является ли сеть достаточно надёжной(ненадёжной) по отношению к заранее заданному порогу надежности для  сети с ограничением на диаметр.

Область применения - анализ надёжности сетей различного назначения.

Рассматриваются сети, в которых отказам подвержены только каналы связи. Под надёжностью понимается вероятность того, что все выделенные узлы связаны между собой с помощью исправных каналов связи путями оганиченной длины. Точный расчет надёжности сети является NP-трудной задачей. Однако при анализе сети иногда достаточно знать, превосходит ли надёжность исследуемой сети величину заданного порога. Используя метод Cancela и Petingi [2], можно организовать итерационный процесс уточнения верхней и нижней границы надёжности сети с ограничением на диаметр и остановить его при достижении одной из границ значения заданного порога. Подобный подход для сетей без ограничения на диаметр был предложен в [1]. Программа позволяет устанавливать, является ли сеть достаточно надёжной по отношению к заданному порогу надежности, а также можно выбрать максимальное время работы, через которое программа остановится, показав верхнюю и нижнюю границы надёжности сети.

[1] Won J.-M., Karray F. Cumulative Update of All-Terminal Reliability for Faster Feasibility Decision // IEEE Trans. On Reliability. September 2010. Vol 59, no 3. P. 551-562.  

[2] Hector Cancela and Louis Petingi. Diameter constrained network reliability: exact evaluation by factorization and bounds. In ICIL’2001 (International Conference on Industrial Logistics), pages 359– 366, 2001.                                                                    

Входные данные программы – структура сети в виде графа, значения надёжности каналов связи (т.е. вероятности их присутствия), значение порога (число от 0 до 1) (можно отключить), ограничение на время расчёта в секундах (можно отключить).

Выходные данные программы – ответ о достаточной надёжности/ненадёжности сети. Если расчёт не был окончен за отведённое время, выводятся полученные к данному моменту значения границ надёжности.

Программа работает с графом, представленным полным файлом предшественников (списки KAO,FO), а также списком терминалов. Вводить списки представления графов и редактировать их можно в соответствующих окнах программы. Информация в файле располагается следующим образом: первая строка и вторая строка – списки KAO и FO соответственно, в третьей строке располагается список терминалов сети (Ki=1, в случае, если i-я вершина сети является терминалом, и 0 иначе). Четвёртая строка – значение надёжности каждого ребра, пятая – значение диаметра сети.

Алгоритм разработан в рамках гранта РФФИ № 14-07-31069.

Функциональные возможности – анализ надёжности сетей с количеством элементов  в несколько сотен.

Инструментальные средства создания – Microsoft Visual Studio 2012.