Лекции по Методам контроля и диагностики систем и сетей связи   

3. Основные методы построения алгоритмов поиска неисправностей

3.7. Метод ветвей и границ

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

         Средняя стоимость произвольной программы поиска неисправностей

  или  ,                                           (46)

где Ci – стоимость контроля i – параметра;

 - сумма вероятностей состояний, которые рассматриваются при контроле i – параметра.

         Расчет поиска начинается с любого i – параметра, который разбивает всё  множество возможных состояний S на два подмножества: S0 (zi) и S1 (zi), соответствующие отрицательному и положительному результатам контроля параметра zi соответственно.

         Последовательность контроля остальных параметров из приведенных подмножеств неизвестна, и определить значение средней стоимости алгоритма поиска невозможно. Поэтому значения средней стоимости заменяются их нижними границами Сн(S0) и Сн(S1) при контроле соответствующих параметров в подмножествах S0(zi) и S1(zi). Тогда нижняя граница средней стоимости всей программы поиска, которая начинается с контроля первого параметра, определяется как

                                                          (47)

Вычислив нижние границы стоимостей Сн(S0) и Сн(S1) для всех возможных алгоритмов поиска, выбирают первым такой параметр, контроль которого дает минимальную среднюю стоимость нижней границы алгоритма поиска.

Затем для подмножеств S0(zi) и S1(zi) вычисляют нижние границы стоимостей для всех возможных пар контролируемых параметров между первым и оставшимися для каждого подмножества.

Пусть для подмножества S0(zi) контролируется параметр zк , а для подмножества S1(zi) – параметр zj  . Тогда нижняя граница средней стоимости программы поиска, начинающейся с контроля i – параметра, будет:

                                                   (48)

         В общем виде записывается:

                           (49)

где                                   (50)

                                     (51)

где     и   - суммы вероятностей в подмножествах  и  соответственно.

         Значения  рассчитываются по формулам (46-48) для подмножеств

          - подмножество состояний ОД, образующееся при отрицательном результате контроля параметров Ziи  Zк;

           -  подмножество состояний ОД, образующееся при отрицательном результате контроля параметра Ziи положительном результате контроля параметра Zк;

            -   подмножество состояний ОД, образующееся при положительном результате контроля параметра Zк и отрицательном результате контроля параметра Zi;

            -  подмножество состояний ОД, образующееся при положительном результате контроля параметром Zк и Zi;

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

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

Рис. 12 Функциональная модель ОД

Матрица неисправностей и вероятности состояний

                                                                                                              Таб.16

Si

Zi

Pi

Z1

Z2

Z3

Z4

Z5

Z6

S1

0

0

1

0

0

0

0,2

S2

1

0

1

0

0

0

0,05

S3

1

1

0

0

1

0

0,24

S4

1

1

1

0

1

0

0,15

S5

1

1

1

1

0

0

0,06

S6

1

1

1

1

1

0

0,3

Пусть первым контролируется параметр Z1. Тогда множество возможных состояний разбивается на два подмножества S0(Z1) и S1(Z1).Для подмножества S0(Z1) последовательность состояний вероятностей будет состоять из одного состояния Р(S1) =0,2 , а подмножества S1(Z1) составим первую последовательность: Р(S2) = 0,05; Р(S5) =0,06; Р(S4) =0,15; Р(S3) =0,24; Р(S6) =0,3. Затем определим сумму двух наименьших вероятностей: Р*1 = 0,05 + 0,06 = 0,1.

Составим вторую последовательность: Р*1 = 0,1; Р(S4) = 0,15; Р(S3) =0,24; Р(S6) =0,03. Затем определим Р*2 = 0,11 + 0,15 = 0,26.

Составим третью последовательность: Р(S3) = 0,24; Р*2 = 0,26; Р(S6) =0,3. Затем определим Р*3 = 0,24 + 0,26 = 0,5.

И наконец, составим четвертую последовательность: Р(S6) =0,3; Р*3 = 0,5 и определим Р*4 = 0,3 + 0,5 = 0,8.

При этом нижняя граница средней стоимости

           N                         0                    6-1-1

Сн(Z1) = С [ ∑ Р(Si)  + ∑ Рλ  +    ∑ Р*ν] = C (1 +0 +1,67) = 2,67 C

                 i=1                      λ=1                 ν=1

Следует указать, что если подмножество S0(Zi) содержит одно состояние, то нижняя граница стоимости Сн(S1) = 0.

Разделение множества возможных состояний на два подмножества S0(Z1) и S1(Z1) при контроле параметра Z1 как показано в табл. 16.

При контроле параметра Z2 множество возможных состояний разбивается на два подмножества: S0(Z2) и S1(Z2)  (табл. 17).

                                                                                                             Таб.17

Si

Zi

Pi

Z1

Z2

Z3

Z4

Z5

Z6

S1

0

0

1

0

0

0

 S0 (Z2)

S2

1

0

1

0

0

0

S3

1

1

0

0

1

0

  S0 (Z2)

S4

1

1

1

0

1

0

S5

1

1

1

1

0

0

S6

1

1

1

1

1

0

Для подмножества S0(Z2) последовательность двух значений вероятностей будет из двух значений: Р(S2) = 0,05 и Р(S1) = 0,2 , и тогда Р*1 = 0,05 + 0,2 = 0,25.

Для подмножества S1(Z2) первая последовательность будет иметь вид Р(S5) =0,06; Р(S4) =0,15; Р(S3) =0,24; Р(S6) = 0,3 , и тогда Р*1 = 0,21; Р*2 = 0,45; Р*3 = 0,75.

Следовательно, нижняя граница средней стоимости при контроле параметра

           N                0             6-1-1

Сн(Z2) = С [ ∑ Р(Si)  + ∑ Рλ  +    ∑ Р*ν] = C (1 +0,25 +1,41) = 2,66 C.

                    i=1                       λ=1                   ν=1

Поступая аналогичным образом при контроле параметров z3 , z4 и z5 , получим нижние границы стоимости при контроле соответствующих параметров: СН ( z3 ) = 2,59C; СН (z4) = 2,60С; СН (z5) = 2,50С.

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

Посмотрим матрицу (табл. 18) состояний подмножества:

S0 (z5) и S1 (z5).

Анализируя табл. 18 , видим, что в случае отрицательного исхода при контроле параметра z5 следующими можно контролировать параметры z1 , z2 , z5. Параметр z3 контролировать не имеет смысла, так как подмножество   S0(z5) не разбивает при его контроле на более мелкие подмножества. При положительном исходе можно контролировать параметры z3 , z4.

Таким образом, необходимо вычислить значения стоимостей нижних границ алгоритма поиска при контроле таких наборов параметров z5 , z1 , z3 , z5 , z1 , z5 , z2 , z3 , z5 , z2 , z4. Для этого воспользуемся формулой:

   ,              

где                                                              

             ;

                                                                                    Таблица 18

S1

ZI

P(S1)

Z5

Z1

Z2

Z3

Z4

     S1                         0                 0                  0               1                   0               0,2

     S2               0                 1                  0               1                   0               0,05

     S3               0                 1                  1               1                   1               0,06

     S4               1                 1                  1               0                   0               0,24

     S5               1                 1                  1               1                   0               0,15

     S6               1                 1                  1               1                    1                0,3

  ,

где ∑ Р(SK) и ∑ Р(SJ) суммы вероятностей Р(S) диагностируемого объекта, которые различаются контролем параметров zK  и zJ   в подмножествах и   соответственно.

         Вычислим значения стоимостей нижних границ при контроле параметров z5 , z1 , z3 . Контроль параметров z1 позволяет различать состояния S1 , S2 , S5 , следовательно,

∑ P(SK) = Р(S1) +  Р(S2) + Р(S2) = 0,2 + 0,05 + 0,06 = 0,31 

Также при контроле параметра zI  выделяется из подмножества S0(zК) только одно состояние S001 , тогда  CН (S001) = 0 , а значения CН (S101) вычисляется аналогичным способом , как и CН (S01) :

                        К

 CН (S101) = С ∑Р*V  = С [Р (S2) + Р (S5)] = C (0,05 + 0,06) = 0,11C

При контроле параметра z3 различаются состояния S3 , S4 , S6 , следовательно:

∑ P(SJ) = Р(S3) +  Р(S4) + Р(S6) = 0,24 + 0,15 + 0,3 = 0,69

Кроме того, при отрицательном исходе из множеств S1(z5) выделяется только одно состояние, а при положительном – два , следовательно:

CН (S10J) = CН (S103) = 0 

                       К

CН (S11J) = С ∑ Р*V  = С [Р (S4) + Р (S6)] = C (0,15 + 0,3) = 0,45C

                       V

         Тогда значение стоимости нижней границы при контроле параметров z5 , z1 , z3 будет равно  

CН (z5 , z1 , z3,) = С(1 + 0,31 + 0,11 + 0,69 + 0,45) = 2,56С

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

CН (z5 , z1 , z4,) = 2,5С

CН (z5 , z2 , z4,) = 2,64С

CН (z5 , z2 , z3,) = 2,7С

Анализ результатов вычислений стоимостей нижних границ показывает, что минимальной стоимостью будет обладать последовательность параметров z5 , z1 , z4.

                                                                                                 Таблица19

Преобразуем таблицу неисправностей в соответствии с результатами контроля последовательности параметров z5 , z1 , z4 (табл. 19) .

Из таблицы видно, что при отрицательном исходе контроля параметров z5 и z1 выделяется состояние S1 , а при отрицательном исходе контроля z5 и положительном z1 необходимо следующим контролировать параметр z2 (контроль параметра z3 не позволяет  разделить подмножество S01 на более мелкие).

При положительном исходе контроля параметров z5 и z4 выделяется состояние S6 , а при отрицательном исходе контроля параметров z5 и отрицательном z4 необходимо контролировать параметр z3. Поскольку других вариантов нет, на этом заканчивается построение алгоритма поиска неисправностей, обладающего минимальной средней стоимостью (Рис. 13).

Таким образом, последовательность контролируемых параметров z5 , z1,  z4, z2 , z3 дает среднюю стоимость ССР = 2,5С.

 

Рис. 13 Схема алгоритма поиска неисправностей, построенного методом ветвей и границ



*****

© 2009-2017 Банк лекций siblec.ru
Лекции для преподавателей и студентов. Формальные, технические, естественные, общественные, гуманитарные, и другие науки.