романович. Романович Ж.А. Диагностирование, ремонт и техническое обслуживан. Учебник 3е издание

• Название: Учебник 3е издание
• Анкор: романович
• Дата: 25.03.2022
• Размер: 4.17 Mb.
• Имя файла: Романович Ж.А. Диагностирование, ремонт и техническое обслуживан.pdf
• Тип: Учебник; #415748
• страница: 17 из 18

Глава 10
МЕТОДЫ И АЛГОРИТМЫ ОПТИМИЗАЦИИ ПОИСКА
МЕСТА ОТКАЗА
10.1 Выбор проверок для поиска места отказа методом
линейного целочисленного программирования
Диагностическая модель в форме орграфа (8.2) удовлет- воряет условиям (8.5), которые при i
≠ 0 являются условиями различения отказов по результатам проверок. Отказы разли- чаются результатами хотя бы одной проверки.
Например, в таблице связей 10.1 отказы отличаются меж- ду собой результатами хотя бы одной проверки.
Таблица 10.1
Таблица связей
E
u
1
u
2
u
3
u
4
u
5
u
6
e
0 1
1 1
1 1
1
e
1 0
1 0
1 0
0
e
2 1
0 1
0 0
0
e
3 1
1 0
1 1
1
e
4 1
1 1
0 0
0
e
5 1
1 1
1 0
1
e
6 1
1 1
1 1
0
Если отказы различаются результатами проверок, то сим- метрические разности множеств
ϕ
0
(e
i
),
ϕ
0
(e
j
), содержащие эле- менты, принадлежащие в точности одному из множеств, не яв- ляются пустыми:
|
ϕ
0
(e
i
)
Δϕ
0
(e
j
)| > 0,
(10.1)

290
где
ϕ
0
: E
0
→ U
0
;
Δ — символ симметрической разности множеств.
Например, при i = 1 и j = 2 по таблице 10.1 определяем:
,
, и |
ϕ
0
(e
1
) ·
Δϕ
0
(e
2
)| = 4.
Выбор проверок для поиска места отказа с минимальными затратами приводится к задаче линейного целочисленного про- граммирования:
; (10.2)
, (10.3)
где x
i
— бинарная переменная, сопоставленная проверке u
i
, принимающая значение 1, если проверка выполняется, и значение 0 — в противном случае;
c
i
— затраты на выполнение проверки u
i
;
m
— число проверок;
S
jk
— множество номеров проверок, недопустимыми ре- зультатами которых различаются отказы e
j
, e
k
Ограничения (10.3) формируются на основе неравенств
(10.1). Число ограничений вычисляется по формуле
,
где n = |E
0
|. Например, при n = 6 число ограничений равно
При одинаковых затратах на выполнение проверок задача линейного целочисленного программирования (10.2), (10.3) сво- дится к выбору минимального числа бинарных переменных.
Целевая функция и ограничения для объекта, моделиру- емого таблицей связей 10.1, значений затрат на выполнение проверок в условных единицах c
1
= 3, c
2
= 4, c
3
= 2, c
4
= 8, c
5
= 6,
c
6
= 5 записываются так:
min (3x
1
+ 4x
2
+ 2x
3
+ 8x
4
+ 6x
5
+ 5x
6
); (10.4)
x
1
+ x
3
+ x
4
> 0;
(10.7)
x
1
+ x
2
+ x
3
+ x
4
> 0;
(10.5)
x
1
+ x
3
+ x
6
> 0;
(10.8)
x
1
+ x
5
+ x
6
> 0;
(10.6)
x
1
+ x
3
+ x
5
>0;
(10.9)

291
x
2
+ x
3
+ x
4
+ x
5
+ x
6
> 0;
(10.10)
x
3
+ x
5
> 0;
(10.15)
x
2
> 0;
(10.11)
x
3
+ x
6
> 0;
(10.16)
x
2
+ x
4
+ x
6
> 0;
(10.12)
x
4
+ x
6
> 0;
(10.17)
x
2
+ x
4
+ x
5
> 0;
(10.13)
x
4
+ x
5
> 0;
(10.18)
x
3
+ x
4
+ x
5
+ x
6
> 0;
(10.14)
x
5
+ x
6
> 0.
(10.19)
Ограничения (10.5)
−(10.19) получены на основе неравенств
(10.1).
Например, если
, то S
12
= {1, 2, 3, 4} и приходим к ограничению (10.5).
Задача линейного целочисленного программирования мо- жет содержать ограничения с одной булевой переменной. Та- ким переменным во всех ограничениях и в целевой функции следует присваивать значения 1, а отображаемые ими провер- ки выбирать для поиска места отказа с минимальными затра- тами. Число переменных и ограничений в задаче линейного це- лочисленного программирования уменьшается.
Действительно, из ограничения (10.11) следует, что x
2
= 1 и множество проверок, позволяющих обнаруживать отказы с минимальными затратами, должно содержать проверку u
2
После подстановки x
2
= 1 в целевую функцию и ограничения получаем:
min (3x
1
+ 2x
3
+ 8x
4
+ 6x
5
+ 5x
6
+ 4); (10.20)
x
3
+ x
4
+ x
5
+ x
6
> 0; (10.25)
x
1
+ x
5
+ x
6
> 0;
(10.21)
x
3
+ x
5
> 0;
(10.26)
x
1
+ x
3
+ x
4
> 0;
(10.22)
x
3
+ x
6
> 0;
(10.27)
x
1
+ x
3
+ x
6
> 0;
(10.23)
x
4
+ x
6
> 0;
(10.28)
x
1
+ x
3
+ x
5
> 0;
(10.24)
x
4
+ x
5
> 0;
(10.29)
x
5
+ x
6
> 0.
(10.30)
Задача выбора проверок для поиска места отказа с ми- нимальными затратами, приведенная к задаче линейного це- лочисленного программирования с бинарными переменными, решается по аддитивному алгоритму Баллаша с фильтром (см. подраздел 9.1).
Допустимым решением задачи (10.20)
−(10.30) удовлетво- ряющим ограничениям (10.21)
−(10.30), являются, например,

292
Таблица 10.2
Результаты определения оптимального решения по алгоритму Баллаша
Номер
сочета-
ния
Сочетания значений
переменных
Значения ограничений и целевой функции
x
1
x
3
x
4
x
5
x
6
(10.31)
(10.26)
(10.27)
(10.28)
·
(10.25)
(10.20)
1 0
0000 4
0
·
2 0
0001 9
0
·
3 0
0010 1
0 1
0
·
4 0
0011 1
5 1
1 1
·
5 0
0100 1
2 0
·
6 0
0101 1
7 0
·
7 0
0110 1
8
·
8 0
0111 2
3
·
9 0
1000 6
1 1
0
·
1 0
01001 1
1 1
2 1
·
1 1
01010 1
2 2
1 0
·
12 0
1
0
1
1
17
2
2
2
·
31
7
1 3
01100 1
4 1
1 1
·
·
·
····
·
·
·
·
·
·
·
3 1
11110 2
3
·
3 2
11111 2
8
·

293
значения переменных x
3
= x
5
= x
6
= 1, x
1
= x
4
= 0, для которых целевая функция (10.20) принимает значение 17.
Минимальное значение целевой функции будет не более
17, если выполняется дополнительное ограничение
3x
1
+ 2x
3
+ 8x
4
+ 6x
5
+ 5x
6
+ 4
≤ 17.
(10.31)
Результаты определения оптимального решения по алго- ритму Баллаша частично представлены в таблице 10.2.
Допустимое решение оказалось оптимальным. Выполнение проверок u
2
, u
3
, u
5
, u
6
позволяет обнаруживать отказы и опре- делять место отказа с минимальными затратами в 17 условных единиц.
Число вычислений значений целевой функции (10.2) и огра- ничений (10.3) при поиске оптимального решения задачи мето- дом полного перебора определяется по формуле
Например, для решения задачи (10.4)
−(10.19) полным пере- бором требуется 1024 вычисления.
Сочетание методического приема сокращения числа огра- ничений с алгоритмом Баллаша позволяет уменьшить число вычислений до 91, т. е. приблизительно до 9% от числа вычис- лений при полном переборе.
Уменьшение числа вычислений по алгоритму Баллаша достигается выбором допустимого решения, принимаемого в качестве фильтра, близкого к оптимальному. Допустимое ре- шение можно формировать, например, по эвристическому ал- горитму исключения проверок, на реализацию которого требу- ются относительно небольшие ресурсы.
Выбор проверок для поиска места отказа с минимальными затратами объекта, моделируемого орграфом (8.5) или (8.19), осуществляется аналогично.
10.2 Выбор проверок для поиска места отказа
по эвристическому алгоритму
Выбор проверок для поиска места отказа с минимальными затратами методами комбинаторной оптимизации, например,

294
по алгоритму Баллаша, достигается ценой больших затрат вы- числительных ресурсов, которые недопустимо возрастают с увеличением размерности диагностической модели. Поэтому иногда ограничиваются выбором состава проверок близкого к оптимальному по эвристическому алгоритму без комбинатор- ного перебора вариантов решений.
Критерием оптимизации состава проверок принимается минимум затрат на поиск места отказа, которые вычисляются по формуле
, (10.32)
где U
П
— множество выполняемых проверок.
Ограничения задаются условиями (8.5) при i
≠ 0.
Объект при выборе проверок для поиска места отказа по эвристическому алгоритму исключения моделируется табли- цей связей орграфа (8.2), (8.6) или (8.19). Множество проверок, учитываемых моделью, ранжируется в порядке убывания за- трат на их реализацию.
Например, затраты в условных единицах на реализацию проверок, учитываемых таблицей связей 10.1, в порядке убы- вания составляют: c
4
= 8, c
5
= 6, c
6
= 5, c
2
= 4, c
1
= 3, c
3
= 2.
Таблица связей 10.1 после исключения строки e
0
(i
≠ 0) и ранжирования проверок в порядке убывания затрат на их реа- лизацию представлена таблицей 10.3.
Таблица 10.3
Таблица связей
E
u
4
u
5
u
6
u
2
u
1
u
3
e
1 1
0 0
1 0
0
e
2 0
0 0
0 1
1
e
3 1
1 1
1 1
0
e
4 0
0 0
1 1
1
e
5 1
0 1
1 1
1
e
6 1
1 0
1 1
1

295
Далее осуществляется сравнение строк таблицы связей попарно без учета результатов проверки, затраты на выполне- ние которой наибольшие. Если строки различаются попарно, то проверка (столбец) исключается из таблицы связей.
В случае появления одинаковых строк, а также после ис- ключения проверки действия повторяются для очередных про- верок с меньшими затратами на реализацию. Проверки, остав- шиеся в таблице связей, позволяют определять место отказа.
Например, строки таблицы связей без учета результатов проверки u
4
различаются попарно и проверка (столбец) u
4
ис- ключается. Очередная проверка u
5
должна применяться при поиске места отказа, поскольку ее исключение из таблицы свя- зей приводит к появлению неразличимых строк e
4
, e
6
Аналогично определяется, что проверки u
6
, u
2
, u
3
не исклю- чаются из таблицы связей, а проверка u
1
исключается.
Таблица связей после исключения столбцов u
4
, u
1
пред- ставлена таблицей 10.4.
Таблица 10.4
Таблица связей
E
u
5
u
6
u
2
u
3
e
1 0
0 1
0
e
2 0
0 0
1
e
3 1
1 1
0
e
4 0
0 1
1
e
5 0
1 1
1
e
6 1
0 1
1
Проверки u
5
, u
6
, u
2
, u
3
, оставшиеся в таблице связей, позво- ляют определять место отказа с затратами в 17 условных еди- ниц.
Проверок, выбранных для поиска места отказа по диа- гностической модели, учитывающей только одиночные отказы, обычно недостаточно при поиске места кратного отказа. Ограни- ченное число выполняемых проверок может привести к ошибке в определении места кратного отказа. Действительно, сочетание

296
отказов e
3
, e
4
проявляется сочетанием признаков работоспособ- ности и отказа 0010, как и отказ e
1
в таблице связей 10.4.
Учет кратных отказов приводит к увеличению размернос- ти диагностической модели и затрат вычислительных ресурсов при выборе проверок для поиска места отказа.
10.3 Выбор проверок для поиска места кратного отказа
по эвристическому алгоритму
Обоснование методики выбора проверок для поиска места кратного отказа с минимальными затратами по эвристическо- му алгоритму исключения основывается на моделировании ра- ботоспособного объекта орграфом (8.7), из которого удаляются орциклы, петли, кратные и транзитивные дуги.
Пример орграфа (8.7), представленного на рисунке 8.6, после удаления петель и транзитивных дуг показан на рисун- ке 10.1.
v
1
v
2
v
4
v
3
v
5
v
6
v
7
v
8
Рисунок 10.1 — Орграф без орциклов, петель, кратных и транзитивных дуг
Проверки объекта различаются между собой только конт- ролируемыми сигналами, отображаемыми вершинами орграфа.
Состав проверок задается всеми вершинами орграфа и прове- рок достаточно для поиска места отказа при любом сочетании
(любой кратности) отказов.
Предположим, что контролируются сигналы
ν
4
,
ν
5
. Если каждый из сигналов
ν
4
,
ν
5
имеет недопустимое значение, а соче-

297
тания отказов невозможны, то причиной является недопустимое значение сигнала
ν
1
, которое определяется без его контроля.
Недопустимые значения сигналов
ν
4
,
ν
5
могут быть следс- твием сочетания одиночных отказов. Тогда по результатам кон- троля сигналов
ν
4
,
ν
5
нельзя сделать вывод о значении сигнала
ν
1
без его контроля.
Аналогично можно показать, что при сочетании не более k одиночных отказов необходимое условие для исключения про- верки (определения значения сигнала без его контроля) фор- мулируется следующим образом:
|
γ(ν)| ≥ k + 1,
(10.33)
где
ν — вершина, соответствующая сигналу;
|
γ(ν)| — мощность множества вершин, составляющего образ вершины
ν.
Заметим, что |
γ(ν)| ≥ α
+
(
ν),
где
α
+
(
ν) — полустепень исхода вершины ν (число исходящих дуг).
Выполнения условия (10.33) в общем случае недостаточно для исключения проверки. Исключение проверок, удовлетво- ряющих условию (10.33), не должно приводить к нарушению условий (8.5) при i
≠ 0 модели, учитывающей сочетания не бо- лее k одиночных отказов (отказов кратностью не более k).
Методикой выбора проверок для поиска места кратного от- каза с минимальными затратами по эвристическому алгоритму исключения предусматриваются следующие действия:
1) установление кратности k отказов и формирование таб- лицы связей, учитывающей сочетания не более k одиночных отказов;
2) определение подмножества проверок, удовлетворяю- щих условию (10.33), и упорядочение их по убыванию затрат на выполнение;
3) сравнение строк таблицы связей попарно без учета ре- зультатов проверки, затраты на выполнение которой наиболь- шие и исключение проверки (столбца) из таблицы связей, если строки различаются попарно;

298 4) повторение действий по пункту 3 для очередных прове- рок с меньшими затратами на реализацию.
Проверки, оставшиеся в таблице связей, позволяют опре- делять место кратного отказа.
Например, при k = 1 условию (10.33) удовлетворяют вер- шины v
5
, v
1
, v
3
орграфа на рисунке 10.1, которым соответствуют проверки u
5
, u
1
, u
3
из таблицы связей 8.1, перечисленные в по- рядке убывания затрат на их выполнение.
Исключение проверок u
5
, u
1
, u
3
из таблицы связей не при- водит к нарушению условий (8.5) при i
≠ 0. Вершины, соответс- твующие исключенным проверкам, на рисунке 10.1 затемнены.
Для поиска места отказа с минимальными затратами сле- дует выполнять проверки u
2
, u
4
, u
6
, u
7
, u
8
10.4 Выбор очередности выполнения проверок для поиска
места отказа по эвристическому алгоритму
Очередность выполнения проверок влияет на среднее чис- ло проверок для поиска места отказа по условному алгоритму диагностирования.
Если отказы, учитываемые диагностической моделью, об- разуют полную группу несовместных случайных событий и ал- горитм диагностирования применяется многократно, то сред- нее число проверок для поиска места отказа вычисляется по формуле
, (10.34)
где p
i
— вероятность отказа e
i
∈ E
0
;
m
i
— число проверок, выполняемых для определения мес- та отказа;
n — число отказов.
Таблицу связей двудольного орграфа допустимо рассмат- ривать как форму задания префиксного кода с избыточностью кодирования, определяемой по формуле (10.34), и выбирать очередность выполнения проверок, основываясь на методе ми- нимизации избыточности кодирования Хаффмена.

299
Если для поиска места отказа выбрано минимальное число проверок, то таблица связей содержит n
1
отказов (строк) E
i
, ко- торые отличаются только значениями проверки u
k
, и n
2
отказов
E
j
, отличающихся только значениями проверки u
q
Усечение таблицы связей исключением значений провер- ки u
k
из всех строк, кроме соответствующих отказам E
i
, не на- рушает условия (8.5) и приводит к снижению избыточности ко- дирования l до l
k
. Аналогично, исключение значений проверки
u
q
из всех строк, кроме E
j
, приводит к уменьшению избыточ- ности кодирования до l
q
. Выбор проверки для усечения таблицы связей основывается на следующей теореме:
. (10.35)
Действительно, каждая строка исходной таблицы связей содержит m результатов проверок. После усечения таблицы связей число результатов проверок в строке уменьшается до
m
−1. Тогда исходя из формулы (10.35) получаем
,
что и требовалось доказать.
Проверка условия, сформулированного в теореме, позво- ляет определить по меньшей мере одну проверку, например u
k
, после исключения значений которой из таблицы связей избы- точность кодирования становится наименьшей. Если проверка не единственная, то следует использовать проверку, затраты на выполнение которой наибольшие. Такой прием приводит к уменьшению средних затрат на поиск места отказа.
Каждую пару строк e
s
, e
t
усеченной таблицы связей, име- ющих наибольшую длину и отличающихся только значениями проверки u
k
, можно представить следующим образом:

300
; (10.36)
, (10.37)
где e
st
— общая часть строк.
Строки e
s
, e
t
редуцируются (объединяются), т. е. заменяют- ся строкой e
st
, которой сопоставляется вероятность
p
st
= p(e
s
) + p(e
t
). (10.38)
После редуцирования пар строк с наибольшей длиной таб- лица связей содержит строки одинаковой длины на единицу меньше исходной и удовлетворяет условию (8.5). Усечение и редуцирование продолжаются до получения пар строк, содер- жащих по одному значению проверки.
Пример поэтапного усечения и редуцирования таблицы связей 10.4 представлен на рисунке 10.2, а. Вероятности отка- зов, составляющих полную группу случайных независимых и несовместных событий, указаны в первом столбце.
Отказы, отличающиеся значениями проверки, определя- ются сравнением попарно строк таблицы связей. В исходной таблице связей четыре пары отказов, в которых отказы разли- чаются значениями одной из проверок. Для усечения таблицы связей выбрана проверка u
5
, поскольку суммарная вероятность отказов e
4
, e
6
наименьшая. Редуцируемые строки показаны стрелками. Значения проверки u
5
, которыми отличаются отка- зы e
4
, e
6
указаны в соответствующих строках над стрелками.
На втором этапе выбрана проверка u
2
, значениями кото- рой различаются отказы e
2
, e
4,6
наименьшей суммарной веро- ятностью.
На третьем этапе выбрана проверка u
6
, превосходящая по затратам проверку u
3
Таблица связей, соответствующая префиксному коду с минимальной избыточностью кодирования, формируется из значений проверок, выделенных при поэтапном усечении и указанных над стрелками.
От значения проверки, выбранной на последнем этапе, до значения проверки, выбранной на первом этапе, имеется

301
a
б
в