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

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

Глава 9
МЕТОДЫ И АЛГОРИТМЫ ОПТИМИЗАЦИИ
ОБНАРУЖЕНИЯ ОТКАЗОВ
9.1 Выбор проверок для обнаружения отказов методом
линейного целочисленного программирования
Диагностическая модель в форме орграфа (8.2) удовлет- воряет условиям (8.5), которые при i = 0 являются условиями обнаружения отказов по результатам проверок. Отказы различаются с работоспособным состоянием недопустимыми результатами проверок.
Например, в таблице связей 9.1 отказы отличаются от ра- ботоспособного состояния недопустимым результатом хотя бы одной проверки.
Таблица 9.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
1
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
j
), составляющие образы отказов, различа- ющихся с работоспособным состоянием, не пустые, т. е.
|
ϕ
0
(e
j
) | > 0,
(9.1)

272
где
ϕ
0
: E
0
→ U
0
Например, при j = 1 по таблице 9.1 определяем: и |
ϕ
0
(e
1
) | = 3.
Выбор проверок для обнаружения отказов с минимальны- ми затратами приводится к задаче линейного целочисленного программирования:
; (9.2)
, (9.3)
где x
i
— бинарная переменная, сопоставленная проверке u
i
, принимающая значение 1, если проверка выполняется, и значение 0 — в противном случае;
c
i
— затраты на выполнение проверки u
i
;
m — число проверок;
S
j
— множество номеров проверок, недопустимыми ре- зультатами которых проявляется отказ e
j
Ограничения (9.3) формируются на основе неравенств
(9.1). Число ограничений равно числу отказов n, составляющих множество E
0
При одинаковых затратах на выполнение проверок задача линейного целочисленного программирования (9.2), (9.3) сво- дится к выбору минимального числа бинарных переменных.
Целевая функция и ограничения для объекта, моделиру- емого таблицей связей 9.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
); (9.4)
x
1
+ x
3
+ x
5
> 0;
(9.5)
x
2
+ x
4
+ x
5
+ x
6
> 0;
(9.6)
x
3
> 0;
(9.7)
x
4
+ x
5
+ x
6
> 0;
(9.8)
x
5
> 0;
(9.9)
x
6
> 0.
(9.10)

273
При формировании ограничений учитывается, что от- каз e
j
проявляется недопустимыми результатами проверок из множества и S
j
= {i}. Например, если
, то S
1
= {1, 3, 5} и приходим к ограничению (9.5).
Задача линейного целочисленного программирования с би- нарными переменными решается сокращенным перебором по аддитивному алгоритму Баллаша с фильтром.
Определяется сочетание значений переменных, удовлет- воряющее всем ограничениям, и прежде всего ограничениям с одной переменной, которое принимается допустимым решени- ем задачи.
Для задачи (9.4)
−(9.10) допустимым решением являются, например значения переменных x
3
= x
5
= x
6
= x
1
= 1, x
2
= x
4
= 0.
Значение целевой функции при выбранных значениях пе- ременных принимается в качестве дополнительного ограниче- ния (фильтра). Целевая функция (9.4) для допустимого реше- ния принимает значение 16. Следовательно, значение целевой функции в оптимальном решении будет не больше 16. Искомое решение должно удовлетворять ограничению:
3x
1
+ 4x
2
+ 2x
3
+ 8x
4
+ 6x
5
+ 5x
6
≤ 16.
(9.11)
Вычисляются значения ограничений, начиная с фильтра, для всех сочетаний значений переменных и проверяется вы- полнение каждого вычисленного ограничения. Если для рас- сматриваемого сочетания значений переменных очередное ограничение не выполняется, то вычисления остальных огра- ничений не проводятся. Значения целевой функции вычисля- ются при условии выполнения всех ограничений.
Сочетания значений переменных и вычисленные значения ограничений целевой функции частично представлены в таб- лице 9.2.
Если при некотором сочетании значений переменных зна- чение целевой функции окажется лучшим, чем в допустимом решении, следует перейти к новому дополнительному ограни- чению и продолжать вычисления ограничений и целевой фун- кции для очередных сочетаний значений переменных.

274
Например, при сочетании значений переменных № 12 зна- чение целевой функции меньше, чем для допустимого решения.
Принимается новое дополнительное ограничение
3x
1
+ 4x
2
+ 2x
3
+ 8x
4
+ 6x
5
+ 5x
6
≤ 13,
(9.12)
вычисление и проверка которого начинаются с сочетания № 13.
Оптимальным решением задачи, как следует из табли- цы 9.2, являются значения переменных x
3
= x
5
= x
6
= 1, x
1
=
= x
2
= x
4
= 0, при которых целевой функцией принимается зна- чение 13. Следовательно, выполнение проверок u
3
, u
5
, u
6
позво-
Таблица 9.2
Результаты определения оптимального решения
по алгоритму Баллаша
Номер
сочета-
ния
Сочетания значений
переменных
Значения ограничений и целевой
функции
x
1
x
2
x
3
x
4
x
5
x
6
(9.11)
(9.7)
(9.9)
(9.10)
(9.5)
(9.6)
(9.8)
(9.4)
1 0
0 0
0 0
0 0
0 2
0 0
0 0
0 1
5 0
3 0
0 0
0 1
0 6
0 4
0 0
0 0
1 1
11 0
5 0
0 0
1 0
0 8
0 6
0 0
0 1
0 1
13 0
7 0
0 0
1 1
0 14 0
8 0
0 0
1 1
1 19 9
0 0
1 0
0 0
2 1
0 10 0
0 1
0 0
1 7
1 0
11 0
0 1
0 1
0 8
1 1
0 12
0
0
1
0
1
1
13
1
1
1
2
2
2
13
(9.12)
(9.7)
(9.9)
(9.10)
(9.5)
(9.6)
(9.8)
(9.4)
13 0
0 1
1 0
0 10 1
0
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
64 1
1 1
1 1
1 28

275
ляет обнаруживать отказы с минимальными затратами в 13 ус- ловных единиц.
Число вычислений значений целевой функции (9.2) и ог- раничений (9.3) при поиске оптимального решения задачи ме- тодом полного перебора определяется по формуле 2
m
(n + 1).
Например, для решения задачи (9.4)
−(9.10) полным перебором требуется 448 вычислений. Сокращение перебора применени- ем алгоритма Баллаша с фильтром позволяет уменьшить чис- ло вычислений до 116, т. е. до 26% от числа вычислений при пол- ном переборе.
Выбор проверок для обнаружения отказов с минимальны- ми затратами объекта, моделируемого орграфом (8.6), осущест- вляется аналогично.
Уменьшение вычислений по алгоритму Баллаша достига- ется выбором допустимого решения, принимаемого в качестве фильтра, близкого к оптимальному. Допустимое решение мож- но определять по эвристическому алгоритму исключения.
9.2 Выбор проверок для обнаружения отказов
методом ветвей и границ
Идея выбора проверок для обнаружения отказов с мини- мальными затратами методом ветвей и границ состоит в мно- гошаговом возвратном (рекуррентном) переборе сочетаний проверок структурированных обычно вершинами ветвей кор- невого дерева и выборе после каждого шага перспективного со- четания с наименьшей нижней границей.
Сокращение перебора достигается развитием на каждом шаге перспективного сочетания проверок добавлением оче- редной проверки, выбираемой по наименьшей нижней границе затрат. Развитие перспективных сочетаний проверок продол- жается до формирования сочетания проверок, позволяющего обнаруживать отказы с наименьшими затратами.
Нижняя граница затрат на обнаружение отказов E
0
после выбора k (1
≤ k ≤ m – 1) проверок U
k
⊆ U, позволяющих обнару-

276
живать отказы
, обозначается C
H
(U
k
, E
0
) и представляет- ся в виде суммы двух слагаемых
, (9.13)
где
— затраты на обнаружение отказов проверка- ми U
k
;
— нижняя граница затрат на обнаружение отказов информативными проверками U
И
⊆ U
k
Множество отказов определяется по формуле
, (9.14)
где
— недопустимые значения проверок U
k
Примечание. Если проверок U
k
достаточно для обнару- жения всех отказов, то
, и
Информативные проверки, позволяющие обнаруживать отказы
, определяются по формуле
. (9.15)
Нижняя граница должна быть меньше фактических за- трат на обнаружение отказов. Поэтому условно принимается, что среди U
И
проверок существует минимальная по затратам проверка, позволяющая обнаружить оставшиеся отказы
Тогда нижняя граница затрат на обнаружение отказов определяется по формуле
. (9.16)
Результаты выбора проверок методом ветвей и границ для обнаружения с минимальными затратами отказов объекта, мо- делируемого таблицей связей 9.1, при значениях затрат на вы- полнение проверок в условных единицах c
1
= 3, c
2
= 4, c
3
= 2, c
4
= 8,
c
5
= 6, c
6
= 5 представлены деревом на рисунке 9.1 и в табли- це 9.3.
Проверки отображаются вершинами ветвей дерева. Ветвь дерева соответствует развиваемому перспективному сочета-

277
нию проверок. Перспективность сочетания проверок опреде- ляется по наименьшему значению нижней границы затрат на обнаружение отказов, указанному в условных единицах рядов с каждой вершиной.
Выполнение проверок u
3
, u
5
, u
6
, отображаемых затемнен- ными вершинами, позволяет обнаруживать отказы с мини- мальными затратами в 13 условных единиц.
Анализ диагностической модели (см. таблицу 9.1) показыва- ет, что для обнаружения отказов e
3
, e
5
, e
6
необходимо и достаточ- но выполнять проверки u
3
, u
5
, u
6
соответственно. Следовательно, для обнаружения всех отказов, задаваемых диагностической моделью, необходимо выполнять не менее трех проверок, при- чем обязательно u
3
, u
5
, u
6
. Априорные сведения об обязательно выполняемых проверках для обнаружения отказов позволяют сократить перебор методом ветвей и границ.
Перебор начинается с комбинации обязательно выпол- няемых проверок. Если выполняемыми проверками не обна- руживаются все отказы, то перебираются их комбинации с одной из невыбиравшихся проверок. Для дальнейшего разви- тия выбирается комбинация проверок с наименьшей нижней границей затрат, которая не выбиралась на предшествующих шагах вычислений, вплоть до формирования комбинации про- u
1
;
5 u
3
;
9 u
2
;
14 u
2
;
6 u
3
;
11 u
6
;
17 u
3
;
6 u
2
;
11 u
6
;
17 u
4
;
10 u
3
;
15 u
5
;
8 u
3
;
13 u
6
;
13 u
6
;
7 u
3
;
13 u
5
;
13
Рисунок 9.1 — Дерево выбора проверок методом ветвей и границ

278
Таблица 9.3
Результаты вычислений по методу ветвей и границ
Номер
шага
U
k
U
И
Выбранная
проверка
1
u
1
{e
1
}{
e
2
,
e
3
,
e
4
,
e
5
,
e
6
}{
u
2
,
u
3
,
u
4
,
u
5
,
u
6
}
3
u
3 25 2
u
2
{e
2
}{
e
1
,
e
3
,
e
4
,
e
5
,
e
6
}{
u
1
,
u
3
,
u
4
,
u
5
,
u
6
}
4
u
3 26 3
u
3
{e
1
,
e
3
}{
e
2
,
e
4
,
e
5
,
e
6
}{
u
2
,
u
4
,
u
5
,
u
6
}
2
u
2 46 4
u
4
{e
2
,
e
4
}{
e
1
,
e
3
,
e
5
,
e
6
}{
u
1
,
u
3
,
u
5
,
u
6
}
8
u
3 21 0
5
u
5
{e
1
,
e
2
,
e
4
,
e
5
}{
e
3
,
e
6
}{
u
3
,
u
6
}
6
u
3 28 6
u
6
{e
2
,
e
4
,
e
6
}{
e
1
,
e
3
,
e
5
}{
u
1
,
u
3
,
u
5
}
5
u
3 27 7
u
1
,
u
3
{e
1
,
e
3
}{
e
2
,
e
4
,
e
5
,
e
6
}{
u
2
,
u
4
,
u
5
,
u
6
}
5
u
2 49 8
u
2
,
u
3
{e
1
,
e
2
,
e
3
}{
e
4
,
e
5
,
e
6
}{
u
4
,
u
5
,
u
6
}
6
u
6 51 1
9
u
3
,
u
2
См. шаг 8 10
u
6
,
u
3
{e
1
,
e
2
,
e
3
,
e
4
,
e
6
}{
e
5
}{
u
5
}
7
u
5 61 3
11
u
5
,
u
3
{e
1
,
e
2
,
e
3
,
e
4
,
e
5
}{
e
6
}{
u
6
}
8
u
6 51 3
12
u
1
,
u
3
,
u
2
{e
1
,
e
2
,
e
3
}{
e
4
,
e
5
,
e
6
}{
u
4
,
u
5
,
u
6
}
9
u
6 51 4
13
u
4
,
u
3
{e
1
,
e
2
,
e
3
,
e
4
}{
e
5
,
e
6
}{
u
5
,
u
6
}
10
u
6 51 5
14
u
2
,
u
3
,
u
6
{e
1
,
e
2
,
e
3
,
e
4
,
e
6
}{
e
5
}{
u
5
}
11
u
5 61 7
15
u
6
,
u
3
,
u
5
{e
1
,
e
2
,
e
3
,
e
4
,
e
5
,
e
6
}
∅
–1 3
–
–
1 3
16
u
5
,
u
3
,
u
6
См. шаг 15
Результаты вычислений при априорных сведениях об обязательно выполняемых проверках
1
u
3
,
u
5
,
u
6
{e
1
,
e
2
,
e
3
,
e
4
,
e
5
,
e
6
}
∅
–1 1
3
–
–

279
верок, позволяющей обнаруживать отказы с минимальными затратами.
Результаты вычислений представлены в таблице 9.3. Про- верки, позволяющие обнаруживать отказы объекта с мини- мальными затратами, выбраны на первом шаге вычислений.
Выбор проверок для обнаружения отказов с минимальны- ми затратами объекта, моделируемого орграфом (8.6), осущест- вляется аналогично.
9.3 Выбор проверок для обнаружения отказов
по эвристическому алгоритму
Критерием оптимизации состава проверок принимается минимум затрат на обнаружение отказов, которые вычисляют- ся по формуле
, (9.17)
где U
K
— множество выполняемых проверок. Ограничения за- даются неравенствами (9.1).
Объект при выборе проверок по эвристическому алгорит- му исключения моделируется таблицей связей орграфа (8.2) или (8.6).
Множество проверок U
K
, позволяющих обнаруживать от- казы с минимальными затратами, формируется поочередным исключением из таблицы связей проверок с наибольшими за- тратами на их выполнение. Если несколько проверок выпол- няются с одинаковыми затратами, исключается любая из этих проверок. Для выполнения неравенств (9.1) достаточно, чтобы каждая строка e
∈ E
0
таблицы связей после исключения про- верки содержала хотя бы один символ 0.
Множество проверок, учитываемых диагностической мо- делью, ранжируется в порядке убывания затрат на их реали- зацию.
Например, затраты в условных единицах на реализацию проверок, учитываемых таблицей связей 9.1, в порядке убыва- ния составляют: c
4
= 8; c
5
= 6; c
6
= 5; c
2
= 4; c
1
= 3; c
3
= 2.

280
Таблица связей 9.1 после ранжирования проверок в порядке убывания затрат на их реализацию представлена таблицей 9.4.
Таблица 9.4
Таблица связей
E
u
4
u
5
u
6
u
2
u
1
u
3
e
0 1
1 1
1 1
1
e
1 1
0 1
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
Далее определяется число символов 0 в каждой строке
e
∈ E
0
таблицы связей без учета результатов проверки, затра- ты на выполнение которой наибольшие. Если каждая строка содержит хотя бы один символ 0, то проверка (столбец) исклю- чается из таблицы связей. В случае невыполнения неравенств
(9.1), а также после исключения проверки действия повторя- ются для очередных проверок с меньшими затратами на реа- лизацию. Проверки, оставшиеся в таблице связей, позволяют обнаруживать отказы.
Например, строки e
∈ E
0
таблицы связей без учета резуль- татов проверки u
4
содержат символы 0 и проверка (столбец) u
4
исключается. Проверка u
5
должна применяться при обнаруже- нии отказов, поскольку после ее исключения из таблицы связей отсутствуют символы 0 в строке e
5
. Аналогично определяется, что проверки u
6
, u
3
не исключаются, а проверки u
2
, u
1
исключа- ются из таблицы связей.
Таблица связей после исключения проверок u
4
, u
2
, u
1
пред- ставлена таблицей 9.5.
Проверки u
5
, u
6
, u
3
, оставшиеся в таблице связей, позволя- ют обнаруживать отказы с затратами в 13 условных единиц.

281
Таблица 9.5
Таблица связей
E
u
5
u
6
u
3
e
0 1
1 1
e
1 0
1 0
e
2 0
0 1
e
3 1
1 0
e
4 0
0 1
e
5 0
1 1
e
6 1
0 1
9.4 Выбор очередности выполнения проверок для обнаружения
отказов методом ветвей и границ
Очередность выполнения проверок, позволяющих обнару- живать отказы с минимальными затратами, влияет на средние затраты при обнаружении отказов по безусловному с условной остановкой алгоритму контроля работоспособности.
Вариант очередности выполнения проверок u
3
, u
5
, u
6
по безусловному с условной остановкой алгоритму контроля ра- ботоспособности объекта, моделируемого таблицей связей 9.5, представлен бинарным деревом на рисунке 9.2.
u
6 0
E
2 0
1 0
1 0
1
u
3
u
5
e
0 0
E
1 0
E
3
Рисунок 9.2 — Граф алгоритма контроля работоспособности

282
Множества отказов, обнаруживаемых после очередных проверок, составляют:
,
,
Если работоспособное состояние и отказы образуют пол- ную группу несовместных случайных событий и алгоритм кон- троля работоспособности применяется многократно, то средние затраты на обнаружение отказов вычисляются по формуле
, (9.18)
где c
i
— затраты на реализацию очередной проверки;
— вероятность отказов, обнаруживаемых при недо- пустимом результате проверки;
m — число выполняемых проверок.
Например, средние затраты алгоритма на рисунке
9.2 при затратах в условных единицах на выполнение проверок c(u
3
) = 2, c(u
5
) = 6, c(u
6
) = 5, вероятностях отказов p(e
1
) = p(e
2
) =
= 0,01, p(e
3
) = p(e
4
) = 0,015, p(e
5
) = p(e
6
) = 0,05 и вероятности работоспособного состояния p(e
0
) = 0,85, учитывая, что
, составляют:
При иной очередности выполнения проверок средние за- траты на обнаружение отказов будут другими.
Комбинации очередности выполнения проверок можно отображать вершинами ветвей ранжированного дерева. Вер- шинам каждой ветви, кроме корня, сопоставляются m прове- рок в очередности их выполнения. Ранг вершины равен числу дуг от корня до рассматриваемой вершины. Полустепень исхо- да корня составляет m. С увеличением на единицу ранга вер- шины полустепень ее исхода уменьшается на единицу.

283
Дерево комбинаций очередности выполнения проверок u
3
,
u
5
, u
6
показано на рисунке 9.3. Ветвь с затемненными вершинами соответствует очередности выполнения проверок, установленной графом алгоритма контроля работоспособности на рисунке 9.2.
Идея поиска оптимального решения задачи методом ветвей и границ состоит в многошаговом возвратном (рекуррентном) сокращенном переборе комбинаций (сочетаний с перестанов- ками) проверок и выборе после каждого шага перспективной комбинации оцениванием нижней границы средних затрат на обнаружение отказов.
Сокращение перебора достигается развитием на каждом шаге только перспективной комбинации проверок с наимень- шей нижней границей средних затрат. Развитие перспектив- ных комбинаций проверок продолжается до формирования комбинации проверок, позволяющей обнаруживать отказы с наименьшими средними затратами.
Нижняя граница средних затрат на обнаружение отказов для очередности выполнения k (1
≤ k ≤ m − 1) проверок u
i
, u
j
, …,
u
q
, составляющих множество U
k
, обозначается C
H
(U
k
) и пред- ставляется в виде суммы двух слагаемых:
C
H
(U
k
) = C (U
k
) + C
H
(U\U
k
). (9.19)
u
6
;
11,95 u
5
;
12,28
u
3
u
3
;
12,25 u
5
;
12,25 u
5
;
12,08 u
3
;
12,33
u
6
u
6
;
12,305
u
3
u
6
u
5
u
3
;
11,975
u
5
;
12,35
u
6
;
12,275
Рисунок 9.3 — Дерево комбинаций очередности выполнения проверок

284
Первое слагаемое составляют средние затраты на обнару- жение отказов после выполнения k проверок. Второе слагаемое является нижней границей средних затрат на обнаружение от- казов для оставшихся U\U
k
проверок.
Из формулы (9.18) получаем
. (9.20)
Нижняя граница должна быть меньше фактических сред- них затрат на обнаружение отказов. Поэтому условно прини- мается, что среди U\U
k
проверок существует минимальная по затратам проверка, позволяющая обнаруживать оставшиеся отказы. Остальные проверки U\U
k+1
используются при опре- делении работоспособного состояния. Тогда нижняя граница средних затрат вычисляется по формуле
. (9.21)
Результаты вычислений нижних границ средних затрат и выбора очередности выполнения проверок методом ветвей и границ представлены на рисунке 9.3.
Первой проверкой при контроле работоспособности может быть любая проверка, отображаемая вершиной первого ранга.
Нижние границы средних затрат на обнаружение отказов пос- ле выполнения первой проверки вычисляются по формулам
(9.19)
−(9.21) при k = 1:
,
где
;
C
H
(u
6
) = c(u
6
) + c(u
3
) [1
− p(e
2
)
−p(e
4
)
− p(e
6
)]
− p(e
0
) c(u
5
) =
= 5 + 2(1
− 0,075) + 0,85 × 6 = 11,95.
,
где
;

285
C
H
(u
5
) = c(u
5
) + c(u
2
) [1
− p(e
1
)
− p(e
2
)
− p(e
4
)
− p(e
5
)]
+ p(e
0
) c(u
6
) =
= 6 + 2(1
− 0,085) + 0,85 × 5 = 12,08.
,
где
;
C
H
(u
3
) = c(u
3
) + c(u
6
) [1
− p(e
1
)
− p(e
3
)]
− p(e
0
) c(u
5
) =
= 2 + 5(1
− 0,025) + 0,85 × 6 = 11,975.
Перспективная комбинация проверок начинается с про- верки u
6
, которой сопоставлена наименьшая нижняя граница.
Вторая проверка выбирается из проверок u
3
, u
5
, отображаемых вершинами второго ранга. Нижние границы средних затрат на обнаружение отказов после выполнения двух проверок вычис- ляются при k = 2.
За проверками u
6
, u
3
может следовать только проверка u
5
, тогда
,
где
;
C
H
(u
6
, u
3
) = c(u
6
) + c(u
3
) [1
− p(e
2
)
− p(e
4
)
−p(e
6
)]
+
+ c(u
5
)[(1
− p(e
1
)
− p(e
2
)
− p(e
3
)
− p(e
4
)
−p(e
6
)] =
= 5 + 2(1
− 0,075) + 6(1 − 0,1) = 12,25.
За проверками u
6
, u
5
может следовать только проверка u
3
, тогда
,
где
;
C
H
(u
6
, u
5
) = c(u
6
) + c(u
5
) [1
− p(e
2
)
− p(e
4
)
− p(e
5
)
− p(e
6
)]
+
+ c(u
3
)[(1
− p(e
1
)
− p(e
2
)
−p(e
4
)
− p(e
5
)
− p(e
6
)] =
= 5 + 6(1
− 0,075) + 2(1 − 0,135) = 12,28.
Перспективная комбинация проверок начинается с про- верки u
3
, которой соответствует наименьшая нижняя граница.

286
Вторая проверка выбирается из проверок u
6
, u
5
, отображаемых вершинами второго ранга. Нижние границы средних затрат на обнаружение отказов после выполнения двух проверок вычис- ляются при k =2.
За проверками u
3
, u
6
может следовать только проверка u
5
, тогда
,
где
;
C
H
(u
3
, u
6
) = c(u
3
) + c(u
6
) [1
− p(e
1
)
− p(e
3
)]
+ c(u
5
)[(1
− p(e
1
)
−
− p(e
2
)
− p(e
3
)
− p(e
4
)
− p(e
6
)] = 2 + 5(1
− 0,025) +
+ 6(1
− 0,1) = 12,275
За проверками u
3
, u
5
может следовать только проверка u
6
, тогда
,
где
;
C
H
(u
3
, u
5
) = c(u
3
) + c(u
5
) [1
− p(e
1
)
− p(e
3
)]
+ c(u
6
)[(1
− p(e
1
)
−
− p(e
2
)
− p(e
3
)
− p(e
4
)
− p(e
5
)] = 2 + 6(1
− 0,025) +
+ 5(1
− 0,1) = 12,35.
Перспективная комбинация проверок начинается с про- верки u
5
, которой соответствует наименьшая нижняя граница.
Вторая проверка выбирается из проверок u
3
, u
6
, отображаемых вершинами второго ранга. Нижние границы средних затрат на обнаружение отказов после выполнения двух проверок вычис- ляются при k = 2.
За проверками u
5
, u
3
может следовать только проверка u
6
, тогда
,
где
;

287
C
H
(u
5
, u
3
) = c(u
5
) + c(u
3
) [1
− p(e
1
)
− p(e
2
)
− p(e
4
)
− p(e
5
)] +
+ c(u
6
) [(1
− p(e
1
)
− p(e
2
)
− p(e
3
)
− p(e
4
)
− p(e
5
)] =
= 6 + 2 (1
− 0,085) + 5 (1 − 0,1) = 12,33.
За проверками u
5
, u
6
может следовать только проверка u
3
, тогда
,
где
;
C
H
(u
5
, u
6
) = c(u
5
) + c(u
6
) [1
− p(e
1
)
− p(e
2
)
− p(e
4
)
− p(e
5
)] +
+ c(u
2
) [(1
− p(e
1
)
− p(e
2
)
− p(e
4
)
− p(e
5
)
− p(e
6
)] =
= 6 + 5(1
− 0,085) + 2(1 − 0,135) = 12,305.
Итак, проверки следует выполнять в последовательности u
6
,
u
3
, u
5
, обеспечивающей минимальное значение 12,25 в условных единицах средних затрат на обнаружение отказов объекта. Граф алгоритма контроля работоспособности с минимальными средни- ми затратами на обнаружение отказов показан на рисунке 9.2.
При поиске оптимального решения методом ветвей и гра- ниц построены все ветви дерева комбинаций очередности вы- полнения проверок и, таким образом, методом ветвей и границ не гарантируется неполный перебор вариантов решений для любых исходных данных.
Контрольные вопросы
1. Как выбор проверок для обнаружения отказов с мини- мальными затратами приводится к задаче линейного целочис- ленного программирования?
2. Поясните переход от условий обнаружения отказов по двудольному орграфу к ограничениям в задаче линейного це- лочисленного программирования.
3. Что такое допустимое решение задачи линейного цело- численного программирования?
4. Как формируется дополнительное ограничение (фильтр) при решении задачи линейного целочисленного программиро- вания методом Баллаша?

288 5. Поясните методику решения задачи линейного целочис- ленного программирования методом Баллаша.
6. Как выбрать проверки для обнаружения отказов с мини- мальными затратами по эвристическому алгоритму исключе- ния?
7. Почему эвристический алгоритм выбора проверок для обнаружения отказов не гарантирует достижения минималь- ного значения целевой функции?
8. Поясните идею выбора проверок для обнаружения от- казов с минимальными затратами методом ветвей и границ с помощью дерева выбора проверок.
9. Как формируется нижняя граница затрат на обнаруже- ние отказов при выборе проверок методом ветвей и границ?
10. Запишите и поясните с помощью графа алгоритма кон- троля работоспособности формулу для вычисления средних затрат на обнаружение отказов.
11. Поясните идею выбора очередности выполнения прове- рок для обнаружения отказов с минимальными средними за- тратами методом ветвей и границ с помощью дерева комбина- ций очередности выполнения проверок.
12. Как формируется нижняя граница затрат на обнару- жение отказов при выборе очередности выполнения проверок методом ветвей и границ?

289