Вероятностная оценка надежности структуры сложной системы
Предлагается применение нового метода исключения для оценки надежности структуры сложной системы. Приводятся результаты сравнения работы методов наложения, исключения и метода Монте-Карло при анализе надежности структуры сложной системы. Пропонується застосування нового методу виключення для оцінки...
Збережено в:
| Опубліковано в: : | Математичні машини і системи |
|---|---|
| Дата: | 2012 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2012
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/83770 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Вероятностная оценка надежности структуры сложной системы / Д.В. Ратобыльская // Мат. машини і системи. — 2012. — № 2. — С. 177-187. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859632000574423040 |
|---|---|
| author | Ратобыльская, Д.В. |
| author_facet | Ратобыльская, Д.В. |
| citation_txt | Вероятностная оценка надежности структуры сложной системы / Д.В. Ратобыльская // Мат. машини і системи. — 2012. — № 2. — С. 177-187. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| container_title | Математичні машини і системи |
| description | Предлагается применение нового метода исключения для оценки надежности структуры сложной системы. Приводятся результаты сравнения работы методов наложения, исключения и метода Монте-Карло при анализе надежности структуры сложной системы.
Пропонується застосування нового методу виключення для оцінки надійності структури складної системи. Наводяться результати порівняння роботи методів накладення, виключення і методу Монте-Карло при аналізі надійності структури складної системи.
Use of the new method of exclusion for the estimation of reliability of a complex system is proposed. The results of overlay methods performing comparison, the exclusion method and the Monte Carlo method in the analysis of the reliability of structure of a complex system are shown.
|
| first_indexed | 2025-12-07T13:11:49Z |
| format | Article |
| fulltext |
© Ратобыльская Д.В., 2012 177
ISSN 1028-9763. Математичні машини і системи, 2012, № 2
УДК 519.873+519.876
Д.В. РАТОБЫЛЬСКАЯ
ВЕРОЯТНОСТНАЯ ОЦЕНКА НАДЕЖНОСТИ СТРУКТУРЫ
СЛОЖНОЙ СИСТЕМЫ
Аннотация. Предлагается применение нового метода исключения для оценки надежности
структуры сложной системы. Приводятся результаты сравнения работы методов наложения,
исключения и метода Монте-Карло при анализе надежности структуры сложной системы.
Ключевые слова: сложная система, надежность, надежность сложной системы, метод нало-
жения, метод Монте-Карло, метод исключения.
Анотація. Пропонується застосування нового методу виключення для оцінки надійності струк-
тури складної системи. Наводяться результати порівняння роботи методів накладення, виклю-
чення і методу Монте-Карло при аналізі надійності структури складної системи.
Ключові слова: складна система, надійність, надійність складної системи, метод накладення,
метод Монте-Карло, метод виключення.
Abstract. Use of the new method of exclusion for the estimation of reliability of a complex system is pro-
posed. The results of overlay methods performing comparison, the exclusion method and the Monte Carlo
method in the analysis of the reliability of structure of a complex system are shown.
Keywords: complex system, reliability, reliability of complex system, overlay method, Monte Carlo me-
thod, exclusion method.
1. Введение
Анализ и оценка надежности структуры сложной системы по вероятностным
характеристикам ее компонентов занимают ключевые позиции в современных
исследованиях, посвященных организации и обслуживанию технических
производственных систем. Проведение подобных исследований существенно всякий раз,
когда стоимость отказа системы высока либо система относится к классу опасных объек-
тов с высоким уровнем ущерба [1–3].
В качестве основных параметров оценки структуры системы, с точки зрения теории
надежности и безопасности, выделяют показатели надежности (или безотказности),
отказоустойчивости и эффективности функционирования системы [1, 2]. Надежность сис-
темы определим как вероятность того, что система со всеми ее подсистемами и составны-
ми компонентами успешно завершит задачу, для исполнения которой она предназначена,
при условиях, с которыми встречаются в течение установленного периода времени, опре-
деленного между входом и выходом (источником и приемником).
Оценка надежности – количество эксплуатационной надежности системы. Отказо-
устойчивость – способность системы функционировать, имея отказы различных составных
компонентов. Эффективность – свойство системы, характеризующее степень выполнения
назначенных системе задач в процессе ее эксплуатации. Анализ данных параметров произ-
водится путем исследования отношений зависимости между составными компонентами
системы и их влияния на систему в целом.
Для решения задачи оценки надежности системы используют многочисленные
методы математического и имитационного моделирования [3, 4], позволяющие с заданной
точностью находить требуемые показатели. Однако применимость данных методов
ограничивается параметрами исследуемой системы: наличием сложной топологии, то есть
несводимостью к последовательно-параллельному представлению, либо большой
размерностью, исключающей применение булева разложения и бинарных алгоритмов
полного перебора.
178 ISSN 1028-9763. Математичні машини і системи, 2012, № 2
Рис. 1. 5-узловой 3-путный граф системы
В настоящее время широкое развитие имеют методы исследования систем, предста-
вляемых как чистые параллельно-последовательные структуры, или систем, в которых
сложную топологию можно свести к параллельно-последовательной. Современные вычис-
лительные алгоритмы исследования сложных систем основаны на переборе состояний, ис-
пользовании нейронных сетей и эвристических алгоритмов, параллельном анализе. Иссле-
дования, направленные на получение приблизительных данных параметров оценки струк-
туры системы, используют методы имитационного моделирования, дополняя их граница-
ми для уменьшения сложности вычислений [3, 5].
Рассматриваемый в статье новый метод исключения позволяет оценить надежность
сложной системы, представляемой в графическом виде и характеризующейся наличием
большого числа составных компонентов, сложной топологией и имеющей вероятностную
характеристику надежности составных элементов.
Целью статьи является описание идеи, алгоритма, способа применения метода ис-
ключения для оценки надежности сложной системы. Приведены результаты работы мето-
да исключения при исследовании структуры сложных систем, сравнения полученных дан-
ных с данными аналогичных (решающих эти же задачи) методов – метода наложения, ме-
тода Монте Карло и метода полного перебора.
2. Метод исключения для оценки надежности сложной системы
В качестве объекта исследования будем рассматривать систему, представляемую в форме
графовой структуры – комбинации вершин (узлов) и ребер. Узлы графа описывают все
возможные состояния компонентов системы и их соответствующие вероятностные харак-
теристики, ребра – связи компонентов между
собой, граф неориентированный.
В качестве примера рассмотрим обра-
зец системы, представленной 5-узловым гра-
фом (рис. 1). Начальный узел системы (вход)
– узел под номером 1, целевой узел (выход) –
5 (система «1 – 5»). Пусть для данной систе-
мы каждый узел графа имеет показатель на-
дежности 90R ,= , что можно трактовать в
зависимости от задач исследования: 90 %
времени узел функционирует, 10 % – не выполняет свои функции либо с вероятностью 0,9
в настоящий момент времени узел исправен (работает) и вероятностью 0,1 – находится в
неисправном состоянии. При использовании метода полного перебора список рассматри-
ваемых различных вариантов состояния системы включал бы 25=32 записи, составляющие
полную связь между 1 и 5 узлами графа. В табл. 1 представлены варианты нахождения уз-
лов графа в одном из двух возможных состояний (1 – узел находится в рабочем состоянии,
0 – в противном случае), определяющих рабочее состояние исследуемой системы и соот-
ветствующие им показатели надежности (отличные от нуля).
Применение метода полного перебора и его табличной реализации оправдано для
систем, представляемых графами с малым количеством узлов, поскольку рост числа рас-
сматриваемых вариантов функционирования системы имеет экспоненциальную природу.
Так, система, содержащая 10 узлов, потребует рассмотрения 10 столбцов и 210 (1025) строк
(10 250 полных ячеек), а система с 20 узлами потребует 20 столбцов и 220 (1 048 576) строк
(20 971 520 полных ячеек).
Рассмотрение графа с малым количеством узлов удобно для анализа влияния путей
в графе друг на друга и на показатель надежности системы. Путь в графе – конечная по-
следовательность узлов, в которой каждый узел, кроме целевого, соединен со следующим
в последовательности узлов ребром.
ISSN 1028-9763. Математичні машини і системи, 2012, № 2 179
Исследуем систему, представленную на рис. 1, с точки зрения образуемых путей от
узла 1 к узлу 5. Существуют три таких пути {1→3→5}, {1→3→4→5} и {1→2→4→5}. В
табл. 2 приведены список состояний системы, соответствующих данных путям, и значения
надежности.
Таблица 2. Список состояний 5-узловой 3-путной системы «1–5» с показателями
надежности для существующих путей
Узел
Надежность
Надежность пути
1 2 3 4 5 {1→3→5}, {1→3→4→5} {1→2→4→5}.
1 0 1 0 1 0,00729 0,00729
1 0 1 1 1 0,06561 0,06561 0,06561
1 1 0 1 1 0,06561 0,06561
1 1 1 0 1 0,06561 0,06561 0,06561
1 1 1 1 1 0,59049 0,59049 0,59049 0,59049
Полная надежность 1 0,729 0,72171 0,6561
Путь в графе назовем минимальным или родительским, если любой другой путь,
соединяющий те же начальный и целевой узлы, либо содержит в себе данный путь, либо
содержит замещение одного из узлов данного пути.
Путь в графе назовем дочерним, если существует такой родительский путь, кото-
рый полностью входит в состав данного пути, то есть содержит все узлы из набора роди-
тельского пути.
Как видно из табл. 2, путь {1→3→5} является минимальным и родительским для
пути {1→3→4 →5}. Учитывая в надежности системы надежность родительского пути (в
нашем случае {1→3→5}), будем учитывать надежность и всех его дочерних путей, по-
скольку для их исполнения требуются более строгие условия. Определить надежность пу-
ти можно простым перемножением показателей надежности всех узлов, входящих в дан-
ный путь. Так, для родительского пути {1→3→5} показатель надежности:
729090RRRR 3
531531 ,, ==××=−− .
Исследуемая система имеет второй минимальный путь {1→2→4 →5}, в котором
узел 2 можем считать замещением узла 3 первого родительского пути. Общая надежность
данного пути может быть определена как сумма входящих в ее состав наборов состояний
(данные табл. 2), так и путем перемножения показателей надежности узлов, образующих
путь:
6561090RRRRR 4
54215421 ,, ==×××=−−− .
Таблица 1. Список рабочих состояний 5-узловой 3-путной системы «1 – 5» с ненулевыми
показателями надежности
Узел
Надежность Надежность «1–5»
1 2 3 4 5
1 0 1 0 1 0,00729 0,00729
1 0 1 1 1 0,06561 0,06561
1 1 0 1 1 0,06561 0,06561
1 1 1 0 1 0,06561 0,06561
1 1 1 1 1 0,59049 0,59049
Полная надежность 1 0,79461
180 ISSN 1028-9763. Математичні машини і системи, 2012, № 2
Из данных таблицы видно, что сумма надежностей двух минимальных путей
(=1,385) точно на 0,59049 больше, чем требуемый результат. Это вероятность наложения
(перекрытия) между двумя путями. Для случая графа, узлы которого имеют одинаковые
надежности (например, при представлении компьютерных сетей), подобные пересечения
могут быть найдены с помощью метода наложения, предложенного и реализованного аме-
риканскими учеными-исследователями Сахиноглом и Райсом (Mehmet Sahinoglu, Benjamin
Rice) [5]. Решение задачи нахождения надежности системы в случае различных показате-
лей надежности узлов графа осуществляет предлагаемый новый метод исключения.
Суть метода исключения заключается в корректировке показателя надежности ми-
нимального пути системы коэффициентом исключения ( )L таким образом, чтобы умень-
шить показатель надежности минимальных путей на дублируемые величины (перекрытия).
Для рассматриваемого примера 5-узловой системы (рис. 1) коэффициент исключения рас-
считывается для второго минимального пути как отрицание замещенного в первом мини-
мальном пути узла:
10901R1RL 335421 ,, =−=−==−−− .
Тогда надежность рассматриваемой системы рассчитывается следующим образом:
79461010656107290LRRR 54215421531sys ,,,, =⋅+=×+= −−−−−−−− .
Рассмотрим метод исключения для случая исследования графического представле-
ния абстрактной системы.
Метод исключения можно разбить на два этапа: поиск набора минимальных путей
на графе и расчет на его базе согласно правилам исключения вероятностного показателя
надежности системы.
Этап поиска набора минимальных путей напрямую связан с эффективностью даль-
нейшего применения метода исключения. На данном этапе необходимо исключить воз-
можность дублирования путей, а также организовать сортировку найденных путей в по-
рядке возрастания их длины (длина пути – количество образующих путь узлов), поскольку
это может экспоненциально повлиять на полное время исполнения алгоритма метода.
Для применения метода исключения рационально иметь уникально упорядоченные
узлы графа системы. Упорядочивание может быть выполнено алфавитной сортировкой
или присвоением абстрактного индекса ( )n,1K каждому узлу перед применением метода.
Порядок узлов не важен, поскольку набор минимальных путей не зависит от индексации.
Пусть имеем граф, состоящий из n уникально упорядоченных узлов
{ }njxX j ,1| == (индекс j однозначно определяет узел jx ) и содержащий m минимальных
путей { }miNS i ,1| == , где { }JjxN ji ∈= | , { }nJ ,,2,1 K= – i -ый минимальный путь. Каж-
дый узел графа Jjx j ∈, характеризуется некоторой вероятностной величиной [ ]1,0∈jp , в
приводимом исследовании это надежность, то есть вероятность нахождения узла в рабо-
чем состоянии.
Надежность i -ого пути:
{ }ij
Kj
ji NxJjKpP ∈∈== ∏
∈
|, . (1)
Надежность системы определяется следующей формулой:
∑
=
⋅=
m
i
ii LPP
1
, (2)
ISSN 1028-9763. Математичні машини і системи, 2012, № 2 181
где
=
−
= l
i
l
i TL
1
1
& – коэффициент исключения, { }iqlqql NxNxxT ∉∈= ,| – набор замещенных
узлов l -ого пути. Формула для коэффициентов исключения раскрывается согласно прави-
лам исключения.
Правила исключения:
1. Пусть набор lT содержит r узлов, тогда преобразование замещенных узлов и пе-
реход к числовому выражению соответствующей вероятностной характеристики коэффи-
циента исключения (в приводимом исследовании – надежности) осуществляется по сле-
дующим формулам:
( )
( )
( ) ( ).
,
r
q
1r
q
2
q
1
q
2
q
1
q
1
q
r
q
1r
q
2
q
1
q
2
q
1
q
1
q
r
q
1r
q
2
q
1
q
2
q
1
q
1
q
r
q
2
q
1
ql
r
q
2
q
1
q
r
q
2
q
1
q
r
q
2
q
1
ql
p1pppp1pp1ppppppp
xxxxxxxxxxT
pppxxxxxxT
−⋅⋅++−+−=+++
→+++==
⋅⋅⋅→==
−−
−
LLKL
KLK
KKK
(3)
2. Если один из наборов sT коэффициента исключения iL входит в состав другого
набора замещенных узлов vT (то есть каждый узел набора sT содержится в наборе vT ), то
из состава коэффициента исключения iL более широкий набор vT удаляется.
3. Для различных наборов sT и vT коэффициента исключения, не содержащих об-
щих узлов:
( ) ( ) vsvsvs TTTTTT ⋅== && . (4)
4. Пусть наборы sT и vT содержат общие узлы, тогда их возможно представить в
следующем виде: CATs = , CBTv = , где C – общий и BA, – уникальные поднаборы заме-
щенных узлов наборов. Коэффициент исключения iL в этом случае преобразуется к виду
( ) ( ) ( )BACCCBCATT vs &&& ⋅+== . (5)
3. Алгоритм метода исключения
Метод исключения реализует последовательное исполнение алгоритма генерации набора
минимальных путей и алгоритма исключения. Проведение после алгоритма генерации
предварительной сортировки полученных путей по возрастанию их длин повышает эффек-
тивность работы (сокращает время исполнения) алгоритма исключения.
Задача поиска набора минимальных путей может быть решена обращением к идее
структурированного алгоритма с использованием простого стека [6]. Предполагается на-
личие уникального упорядочения узлов графа, то есть каждому из узлов поставлен в соот-
ветствие абстрактный индекс ( )n,,1K .
Алгоритм поиска минимальных путей: добавляется стартовый (начальный) узел на
первоначально пустой стек, и повторяется следующий алгоритм для внесенного (текуще-
го) узла стека, пока стек снова не станет пустым.
1. Если текущий узел соединяется непосредственно с целевым узлом:
а) целевой узел добавляется в стек;
б) текущий стек сохраняется как новый минимальный путь (первый узел в стеке –
узел запуска, он представляет начало минимального пути, текущий узел – целевой, он
представляет конец пути);
182 ISSN 1028-9763. Математичні машини і системи, 2012, № 2
с) из стека исключаются два последних узла пути: целевой узел и узел, который
соединяется непосредственно с ним.
2. Если текущий узел не соединяется непосредственно с целевым узлом, в стек до-
бавляется следующий соединительный узел. Соединительный узел может быть определен
следующей логикой:
а) никакой узел, который уже находится в стеке, не является кандидатом (это вы-
зовет рекурсию);
б) если предыдущее действие было действием постановки узла в стек, выбирают
самый низкий упорядоченный узел, соединенный с текущим узлом стека и не находящий-
ся в стеке;
с) если предыдущее действие было исключающим действием (то есть один из уз-
лов, соединенных с текущим узлом, был удален), выбирают следующий упорядоченный
узел, соединенный с текущим узлом стека после ранее исключенного узла.
3. Если текущий узел не соединяется непосредственно с целевым узлом, как и все
его соединительные узлы, текущий узел удаляется из стека.
Рассмотрим исполнение алгоритма поиска минимальных путей на примере систе-
мы, представленной 6-узловым графом «1 – 6» (рис. 2).
Шаг 1. Добавление начального узла в стек: {1}.
Шаг 2. Текущий узел стека соединен с узлами 2 и 3 графов, которые не находятся в
стеке. Поскольку предыдущее действие – добавление узла в стек, добавляется следующий
самый низкий по уровню узел 2: {1→2}.
Шаг 3. Текущий узел (2) соединен с узлами 1 и 4, 1 уже находится в стеке, добавля-
ем узел 4: {1→2→4}.
Шаг 4. Текущий узел (4) связан непосредственно с целевым узлом (6). Целевой узел
добавляется в стек: {1→2→4→6} – минимальный путь. Из текущего стека удаляются два
последних узла: {1→2}.
Шаг 5. Узел 4 на предыдущем шаге был выброшен из стека, текущий узел стека (2)
не соединен ни с каким узлом с индексом больше чем 4, согласно алгоритму, узел 2 выбра-
сывается из стека: {1}.
Шаг 6. Узел 2 на предыдущем шаге был выброшен из стека; следующий узел с ин-
дексом, большим 2, связанный с текущим узлом (1) и не находящийся в стеке, – узел 3.
Узел 3 добавляется в стек: {1→3}.
Шаг 7. Текущий узел (3) со-
единен с узлами 1, 4, и 5; 1 уже на-
ходится в стеке, добавляется сле-
дующий самый низкий узел (4):
{1→3→4}.
Шаг 8. Текущий узел (4) со-
единен непосредственно с целевым
узлом. Целевой узел добавляется в
стек: {1→3→4→6} – минимальный
путь. Из текущего стека удаляются два последних узла: {1→3}.
Шаг 9. Узел 4 на предыдущем шаге был выброшен из стека; следующий узел, со-
единенный с текущим узлом, имеющий индекс, больший 4 и не находящийся в стеке, –
узел 5. Узел 5 добавляется в стек: {1→3→5}.
Шаг 10. Текущий узел (5) соединен непосредственно с целевым узлом (6). Целевой
узел добавляется в стек: {1→3→5→6} – минимальный путь. Из текущего стека удаляются
два последних узла {1→3}.
Рис. 2. 6-узловой 4-путный граф системы
ISSN 1028-9763. Математичні машини і системи, 2012, № 2 183
Шаг 11. Узел 5 на предыдущем шаге был выброшен из стека; нет никаких узлов,
имеющих индекс, больший 5, соединенных с текущим узлом. Текущий узел (3) удаляется
из стека: {1}.
Шаг 12. Узел 3 на предыдущем шаге был выброшен из стека; нет никаких узлов,
имеющих индекс, больший 3, и соединенных с текущим узлом. Текущий узел (1) удаляется
из стека.
Шаг 13. Стек пуст; алгоритм генерации минимальных путей исполнен. Набор ми-
нимальных путей ( ) ( ) ( ){ }1356,1346,12460 =S .
Поскольку набор минимальных путей содержит пути равной длины (4 – количество
узлов графа), проводить сортировку с целью оптимизации работы алгоритма исключения
нет необходимости.
Алгоритм исключения может быть реализован с использованием конечного массива
стеков { }kSS = . Каждый стек содержит один или несколько наборов { }ik NS = , каждый
набор состоит из одного или нескольких узлов ( ) { }njxxxN r
jjji LK ,2,1,21 ∈= .
Начальный (корневой) стек 0S образует набор минимальных путей, сгенерирован-
ный для системы – { }miN i ,1| = . Корневой стек создает дополнительные (дочерние) стеки
на уровень ниже. Вероятностный показатель надежности системы )( sysP представляет со-
бой глобальную переменную (глобальная надежность), формируемую текущими показате-
ли надежности пути iii LPR ⋅= согласно формуле (2).
Начальная глобальная надежность и текущие показатели надежности равны нулю,
коэффициенты исключения равны 1. Для каждого набора iN корневого стека:
1. Рассчитывается показатель надежности i -ого пути iP согласно формуле (1). Те-
кущий показатель надежности ii PR = .
2. Рассчитывается коэффициент исключения iL . Для 1-ого набора коэффициент 1.
Создается дочерний стек iS , содержащий наборы замещенных узлов пути:
{ }1,1| −== ilTS i
li , где { }ijljj
i
l NxNxxT ∉∈= ,| .
Производится обработка дочернего стека:
а) устраняются все наборы стека, содержащие полное вхождение других наборов.
Если существуют наборы i
i
q
i
k STT ∈, такие, что i
k
i
q
i
k TTT =∩ , то набор i
qT удаляется из сте-
ка;
б) устраняются все неполные вхождения в наборы стека. Если существуют наборы
i
i
q
i
k STT ∈, такие, что CTT i
q
i
k =∩ , где C – набор, содержащий один или более замещенных
узлов, то есть CBTCAT i
q
i
k == , , наборы i
q
i
k TT , исключаются из стека, коэффициент исклю-
чения преобразуется согласно формуле (5);
с) для оставшихся наборов стека { }KkT i
k ∈| коэффициент исключения
∏
∈
⋅=
Kk
i
kii TLL , где iT вычисляется согласно формуле (3) правил исключения.
3. Рассчитываются текущий и глобальный показатели надежности iR , isyssys RPP ⋅= .
В табл. 3 представлен пример работы алгоритма исключения для задачи нахожде-
ния надежности 6-узловой системы «1 – 6» (рис. 2). Набор минимальных путей
( ) ( ) ( ){ }1356,1346,1246 получен ранее алгоритмом генерации. Надежность узлов примем
равной 0,9, то есть с вероятностью 0,9 узел графа находится в рабочем состоянии.
184 ISSN 1028-9763. Математичні машини і системи, 2012, № 2
Таблица 3. Данные алгоритма исключения для 6-узловой системы «1 – 6» при
одинаковых показателях надежности узлов
i iN iP iT iL iR
1
(1246)
6561090
pppp
4
6421
,, ==
= – 1 0,6561·1=0,6561
2 (1346) 0,6561 (1246)\(1346)=(2) ( ) 1022 ,== 0,06561
3 (1356) 0,6561 (1246)\(1356)=(24)
(1346)\(1356)=(4)
( ) ( ) 1042424 ,& === 0,06561
sysP 0,78732
На первом шаге алгоритма исключения вычисляются значения надежности мини-
мальных путей (столбец iP ). Далее формируются наборы замещенных узлов (столбец iT ),
рассчитываются коэффициент исключения и текущая надежность пути (столбцы iL и iR
соответственно). Показатель надежности системы )( sysP представляет собой сумму теку-
щих надежностей. Результат работы алгоритма исключения, то есть надежность системы,
совпадает с результатами, получаемыми как методом наложения, так и методом полного
перебора.
При изменении показателей надежности узлов системы, но при неизменном составе
набора минимальных путей графа, символьное выражение коэффициентов исключения и
надежности путей останется неизменным.
Пусть новое значение показателей надежности узлов системы, представленной на
рис. 2, определяет вектор надежностей ( )960950940930920910P ,;,;,;,,;,;,= , то есть i -ый
узел системы имеет надежность ip , соответствующую вероятности нахождения узла в ра-
бочем состоянии. Используя полученные ранее символьные выражения коэффициентов
исключения и надежностей путей (табл. 3), получим новый показатель надежности систе-
мы – 8628950Psys ,= (табл. 4), значение которого совпадает с результатами работы метода
полного перебора.
Таблица 4. Данные алгоритма исключения для 6-узловой системы «1 – 6»
при различных показателях надежности узлов
i iN iP iL iR
1 (1246)
7554890
pppp 6421
,=
=
1 0,755489
2 (1346) 0,763701 ( ) 08022 ,== 0,061096
3 (1356) 0,771826 ( ) ( ) 06042424 ,& === 0,0430954
sysP 0,862895
4. Пример исследования сложной системы методом исключения
Рассмотрим пример исследования сложной системы, представленной 19-узловым с 32 реб-
рами графом (рис. 3). Начальный узел – 1, целевой – 19. Пусть для данной системы каж-
дый узел графа имеет показатель надежности 90R ,= .
ISSN 1028-9763. Математичні машини і системи, 2012, № 2 185
Рис. 3. 19-узловой 32-связный граф системы
Согласно методу исключения,
на первом этапе генерируется список
минимальных путей на графе. Для
данной системы он включает восемь
различных путей:
( ) ( ){ ,, 18 15 13 2461116 15 13 11246
( ) ( ) ( ),,, 16 15 13 271116 15 13 278122461718
( ) ( ) ( )}.,, 18 316 15 318 27
С целью оптимизации работы
алгоритма исключения (сокращения
времени исполнения) пути сортируют-
ся в порядке возрастания длин. Затем
производится расчет надежности пу-
тей, составляются наборы замещенных узлов, вычисляются коэффициенты исключения
(процесс расчета коэффициентов в символьном виде представлен в табл. 5). Полученные
значения вероятностей путей и коэффициентов исключения дают показатель надежности
исследуемой системы 7844480Psys ,= .
Таблица 5. Расчет коэффициентов исключения для 19-узловой системы «1 – 9»
i iN iL
1 (3 18) 1
2 (3 15 16) ( ) 1818 =
3 (2 7 18) ( ) ( ) 3316 315&3 ==
4 (2 4 6 17 18) ( ) ( ) 737&37&16 315&3 ⋅==
5 (2 7 11 13 15 16) ( ) ( ) 18318&318 17 6 4&18&3&18 3 ⋅==
6 (2 7 8 12 13 15 16) ( ) ( ) 1118311&18&311&18 17 6 4&18&3&18 3 ⋅⋅==
7 (2 4 6 11 13 15 16)
( ) ( )
( ) 718173717371817173
7&18 17&312 8 7&7&18 17&18 7&3&18 3
⋅⋅⋅+⋅⋅=⋅⋅+⋅=
==
8 (2 4 6 11 13 15 18)
( ) ( )
161773
16 &17&7&316&16 12 8 7&16 7&17&7&16 3&3
⋅⋅⋅=
==
Сравним результаты работы метода исключения с методами наложения и Монте-
Карло (табл. 6). Выбор для сравнения метода наложения, предложенного и реализованного
американскими исследователями Мехметом Сахинголом и Бенджамином Райсом для ис-
следования надежности компьютерных сетей, и метода Монте-Карло обусловлен тем, что
оба метода:
1) позволяют проводить исследования графовых структур;
2) находятся в открытой печати, то есть имеется полное описание метода;
3) имеют простую машинную реализацию;
4) дают точный (метод наложения) или с высокой степенью точности (метод Мон-
те-Карло) результат.
Как видно из табл. 6, метод наложения имеет преимущество в сравнении с методом
исключения, поскольку дает точный результат для исследуемой системы более быстро.
Однако применение метода наложения возможно только для систем с одинаковыми веро-
186 ISSN 1028-9763. Математичні машини і системи, 2012, № 2
ятностными показателями для всех узлов графа, тогда как метод исключения применим
для исследования любой системы, представленной графовой структурой.
Преимущество метода исключения перед методом Монте-Карло заключено не
только во времени исполнения и точности получаемых данных, но и в затратах памяти, не-
обходимой для хранения и обработки данных в процессе работы алгоритма.
Таблица 6. Результаты исследования 19-узловой системы «1–19»
Метод
исключения наложения
Монте-Карло
(100 000 итераций)
Показатель надежности системы, sysP 0,78445 0,78445 0,78439
Время исполнения, t (с) 51,06 50,10 83,08
Пусть новое значение показателей надежности узлов системы, представленной на
рис. 3, определяет вектор надежностей ( )91909180920910P ,;,,,,;, K= , то есть i -ый узел
системы имеет надежность i0090pi ,, += , соответствующую вероятности нахождения узла
в рабочем состоянии. Используя полученные ранее выражения для коэффициентов исклю-
чения (табл. 5), новый показатель надежности системы 823270Psys ,= , время исполнения
метода (работы программы, реализующей метод) 0651t ,= с. Метод Монте-Карло дает ре-
зультат 822140Psys ,= за 4794t ,= с.
Общей проблемой для рассмотренных трех методов исследования является время
обработки больших систем с более чем 30 узлами и 50 связями (ребрами).
5. Заключение
Представленный в статье новый метод исследования – метод исключения, предназначен
для анализа и оценки структуры сложных систем. Широко используемые в настоящий мо-
мент для этих целей методы математического и имитационного моделирования [3] обла-
дают рядом объективных ограничений при исследовании сложных систем, связанных с
возможностями описания структуры объекта, затратами ресурсов памяти компьютера и
временем исполнения соответствующих алгоритмов.
Метод исключения применим для исследования систем, представленных в графиче-
ском виде (неориентированным графом) и характеризующихся наличием большого числа
составных компонентов, сложной топологией (не сводимых к последовательно-
параллельным структурам), имеющих вероятностную характеристику надежности состав-
ных элементов.
Алгоритм метода исключения, включающий разделенные между собой этап поиска
набора минимальных путей на графе и этап применения алгоритма исключения, позволяет
оптимизировать работу метода. Оптимизация возможна путем изменения (усовершенство-
вания) алгоритма поиска минимальных путей внедрением возможности непосредственного
задания списка минимальных путей в процессе работы метода.
Структура алгоритма исключения позволяет настраивать работу метода на решение
задачи анализа и оценки только состояния системы при условии неизменности ее структу-
ры (то есть при постоянном наборе минимальных путей). Для этого достаточно организо-
вать возможность отдельного сохранения и вызова символьного выражения коэффициен-
тов исключения и применять данную процедуру при изменении значений вероятностных
показателей узлов системы.
ISSN 1028-9763. Математичні машини і системи, 2012, № 2 187
Приведенные в статье примеры расчета надежности сложных систем методами ис-
ключения, наложения и Монте-Карло позволяют оценить достоверность и точность работы
предлагаемого метода, эффективность (скорость исполнения) организации алгоритма.
СПИСОК ЛИТЕРАТУРЫ
1. Рябинин И.А. Надежность и безопасность структурно-сложных систем / Рябинин И.А. – СПб.:
Изд-во С.-Петерб. ун-та, 2007. – 276 с.
2. Каштанов В.А. Теория надежности сложных систем / В.А. Каштанов, А.И. Медведев. – М.: Физ-
матлит, 2010. – 608 с.
3. Rykov V.V. Mathematical and Statistical Models and Methods in Reliability / Rykov V.V., Balakrish-
nan N., Nikulin M.S. – New York, Dordrecht, Heidelberg, London: Birkhӓuser, 2010. – P. 485.
4. Советов Б.Я. Моделирование систем: учеб. для вузов / Б.Я. Советов, С.А. Яковлев; 3-е изд.,
перераб. и доп. – М.: Высшая школа, 2001. – 343 с.
5. Sahinoglu M. Network reliability evaluation / M. Sahinoglu, R. Benjamin // Wiley Interdisciplinary
Reviews: Computational Statistics. – 2010. – Vol. 2, Marth/April. – P. 189 – 211.
6. Ратобыльская Д.В. Вероятностная оценка структуры сложной системы по вероятностным харак-
теристикам ее компонентов / Д.В. Ратобыльская // Шоста наук.-практ. конф. за міжнар. участю
«Математичне та імітаційне моделювання систем. МОДС'2011»: тези доп. – Чернигов: ФОП
Васюта В.В., 2011. – С. 386 – 391.
Стаття надійшла до редакції 14.07.2011
|
| id | nasplib_isofts_kiev_ua-123456789-83770 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Russian |
| last_indexed | 2025-12-07T13:11:49Z |
| publishDate | 2012 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Ратобыльская, Д.В. 2015-06-23T08:24:24Z 2015-06-23T08:24:24Z 2012 Вероятностная оценка надежности структуры сложной системы / Д.В. Ратобыльская // Мат. машини і системи. — 2012. — № 2. — С. 177-187. — Бібліогр.: 6 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/83770 519.873+519.876 Предлагается применение нового метода исключения для оценки надежности структуры сложной системы. Приводятся результаты сравнения работы методов наложения, исключения и метода Монте-Карло при анализе надежности структуры сложной системы. Пропонується застосування нового методу виключення для оцінки надійності структури складної системи. Наводяться результати порівняння роботи методів накладення, виключення і методу Монте-Карло при аналізі надійності структури складної системи. Use of the new method of exclusion for the estimation of reliability of a complex system is proposed. The results of overlay methods performing comparison, the exclusion method and the Monte Carlo method in the analysis of the reliability of structure of a complex system are shown. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Якість, надійність і сертифікація обчислювальної техніки і програмного забезпечення Вероятностная оценка надежности структуры сложной системы Імовірнісна оцінка надійності структури складної системи Probabilistic evaluation of reliability of structure of the complex system Article published earlier |
| spellingShingle | Вероятностная оценка надежности структуры сложной системы Ратобыльская, Д.В. Якість, надійність і сертифікація обчислювальної техніки і програмного забезпечення |
| title | Вероятностная оценка надежности структуры сложной системы |
| title_alt | Імовірнісна оцінка надійності структури складної системи Probabilistic evaluation of reliability of structure of the complex system |
| title_full | Вероятностная оценка надежности структуры сложной системы |
| title_fullStr | Вероятностная оценка надежности структуры сложной системы |
| title_full_unstemmed | Вероятностная оценка надежности структуры сложной системы |
| title_short | Вероятностная оценка надежности структуры сложной системы |
| title_sort | вероятностная оценка надежности структуры сложной системы |
| topic | Якість, надійність і сертифікація обчислювальної техніки і програмного забезпечення |
| topic_facet | Якість, надійність і сертифікація обчислювальної техніки і програмного забезпечення |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/83770 |
| work_keys_str_mv | AT ratobylʹskaâdv veroâtnostnaâocenkanadežnostistrukturysložnoisistemy AT ratobylʹskaâdv ímovírnísnaocínkanadíinostístrukturiskladnoísistemi AT ratobylʹskaâdv probabilisticevaluationofreliabilityofstructureofthecomplexsystem |