Выбор проверок для обнаружения отказов методом ветвей и границ

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

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

Нижняя граница затрат на обнаружение отказов Е° после выбора к (1 <к<т - 1) проверок Uk с: U, позволяющих обнаруживать отказы обозначается Сн (?7,, Е°) и представляется в виде суммы двух слагаемых

где C(Uk, Е°) — затраты на обнаружение отказов Е'? проверками Ub;

— нижняя граница затрат на обнаружение отказов ?° ?!~ информативными проверками 17 с: Uk.

Множество отказов Ек определяется по формуле

где Uk — недопустимые значения проверок Uk.

Примечание. Если проверок Uk достаточно для обнаружения всех отказов, то е?=?°, ЕоЕ?=0 и Ch{Uu, Е° Е?) =

= СН(17И,0) = 0.

Информативные проверки, позволяющие обнаруживать отказы Е° Е'г, определяются по формуле

Нижняя граница должна быть меньше фактических затрат на обнаружение отказов. Поэтому условно принимается, что среди 17 проверок существует минимальная по затратам проверка, позволяющая обнаружить оставшиеся отказы Е° Eh Тогда нижняя граница затрат на обнаружение отказов Е0 El; определяется по формуле

Результаты выбора проверок методом ветвей и границ для обнаружения с минимальными затратами отказов объекта, моделируемого таблицей связей 9.1, при значениях затрат на выполнение проверок в условных единицах сх = 3, с2 = 4, с3 = 2, с4 = 8, с5 = 6, с6 = 5 представлены деревом на рисунке 9.1 и в таблице 9.3.

Проверки отображаются вершинами ветвей дерева. Ветвь дерева соответствует развиваемому перспективному сочета-

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

Выполнение проверок и3, и , и6, отображаемых затемненными вершинами, позволяет обнаруживать отказы с минимальными затратами в 13 условных единиц.

Анализ диагностической модели (см. таблицу 9.1) показывает, что для обнаружения отказов е3, е5, е6 необходимо и достаточно выполнять проверки и3, иъ, и6 соответственно. Следовательно, для обнаружения всех отказов, задаваемых диагностической моделью, необходимо выполнять не менее трех проверок, причем обязательно и3, и5, и6. Априорные сведения об обязательно выполняемых проверках для обнаружения отказов позволяют сократить перебор методом ветвей и границ.

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

Таблица 9.3

Результаты вычислений по методу ветвей и границ

Номер

шага

ик

4

Е° El;

C(Uk,E°k)

Выбранная

проверка

сн(и-Л,

Е

C„(Uk,E°)

1

иг

2, е3, е4, е5, е6}

2, и3, и4, иъ, и6}

3

мз

2

5

2

и2

{*2>

{е., е3, е4, е5, е,}

{щ,и3, и4ъ, и6}

4

из

2

6

3

М3

К 4

2, е4, е5, е6}

2, м4, и5, гг6}

2

U2

4

6

4

U4

2, ej

К е3, е5, е,}

{Mj.Ug, ttg, Uj

8

из

2

10

5

иь

(е1> 62’ 64’

(ез> eG}

К> UG}

6

из

2

8

6

иь

К бб}

{е,, е3, ej

{Mj.Ug, Mg}

5

и

2

7

7

uv иг

К 4

2, е4, е5, ес}

2, m4, u5, w6}

5

U2

4

9

8

UV U3

(ei> б2, е3}

^4- е5- еК}

K, M5, wfi}

6

иь

5

11

9

ПУ U2

См. шаг 8

10

иу Щ

{ev е2, е3, е4, е6}

7

иь

6

13

11

иУ из

К е2’ ез- е4- еъ)

Ы

K>

8

5

13

12

Uv и3, и2

iei> е2>

4, е5, е6}

{u4, u., U6}

9

ие

5

14

13

uv из

К е2- ез- е4>

{е5- eJ

K> Ub)

10

5

15

14

и2, из, ив

(е1> 62’ ез> 64’

W

4>

11

иь

6

17

15

ив> uv иь

{б1> е2’ ез’ е4> е5’ еб^

0

-

13

-

-

13

16

иу uv и6

См. шаг 15

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

1

иу иУ ив

(е1> 62’ ез> 64’ 65>

0

-

1

13

-

-

верок, позволяющей обнаруживать отказы с минимальными затратами.

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

Выбор проверок для обнаружения отказов с минимальными затратами объекта, моделируемого орграфом (8.6), осуществляется аналогично.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >