МЕТОДЫ И АЛГОРИТМЫ ОПТИМИЗАЦИИ ОБНАРУЖЕНИЯ ОТКАЗОВ

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

Диагностическая модель в форме орграфа (8.2) удовлетворяет условиям (8.5), которые при i = 0 являются условиями обнаружения отказов по результатам проверок. Отказы различаются с работоспособным состоянием недопустимыми результатами проверок.

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

Таблица 9.1

Таблица связей

Е

U1

U2

мз

М4

иь

и6

ео

1

1

1

1

1

1

ei

0

1

0

1

0

1

е2

1

0

1

0

0

0

ез

1

1

0

1

1

1

е4

1

1

1

0

0

0

1

1

1

1

0

1

1

1

1

1

1

0

Множества ф0.), составляющие образы отказов, различающихся с работоспособным состоянием, не пустые, т. е.

Например, при j = 1 по таблице 9.1 определяем: Ф0х) = {uj,

из,и°}и|ф0 (et) I = 3.

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

где х. — бинарная переменная, сопоставленная проверке и., принимающая значение 1, если проверка выполняется, и значение 0 — в противном случае;

с. — затраты на выполнение проверки и.;

га — число проверок;

S. — множество номеров проверок, недопустимыми результатами которых проявляется отказ г..

Ограничения (9.3) формируются на основе неравенств (9.1). Число ограничений равно числу отказов п, составляющих множество Е°.

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

Целевая функция и ограничения для объекта, моделируемого таблицей связей 9.1, и значений затрат на выполнение проверок в условных единицах сх = 3, с2 = 4, с3 = 2, с4 = 8, с5 = 6, с = 5 записываются так:

о

При формировании ограничений учитывается, что отказ г. проявляется недопустимыми результатами проверок из множества (р0;) = (ujj и S. = {г}. Например, если Ф0х) = {ttf, uj, ul) то Sx = {1, 3, 5} и приходим к ограничению (9.5).

Задача линейного целочисленного программирования с бинарными переменными решается сокращенным перебором по аддитивному алгоритму Баллаша с фильтром.

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

Для задачи (9.4)-(9.10) допустимым решением являются, например значения переменных х3 = х5 = х6 = хх = 1, х2 = а?4 = 0.

Значение целевой функции при выбранных значениях переменных принимается в качестве дополнительного ограничения (фильтра). Целевая функция (9.4) для допустимого решения принимает значение 16. Следовательно, значение целевой функции в оптимальном решении будет не больше 16. Искомое решение должно удовлетворять ограничению:

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

Сочетания значений переменных и вычисленные значения ограничений целевой функции частично представлены в таблице 9.2.

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

Таблица 9.2

Результаты определения оптимального решения по алгоритму Баллаша

Номер

сочета

ния

Сочетания значений переменных

Значения ограничений и целевой функции

Н

н*

н

н*

н

о

н

ai

05

(6*6)

(01*6)

(9.5)

to

05

  • 00
  • 05

S

05

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

S

о-

оГ

о

ю

S'

S

s

05

05

05

05

05

05

05

05

13

0

0

1

1

0

0

10

1

0

64

1

1

1

1

1

1

28

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

вычисление и проверка которого начинаются с сочетания № 13.

Оптимальным решением задачи, как следует из таблицы 9.2, являются значения переменных х3 = х5 = х6 = 1, лс = = х2 = х4 = 0, при которых целевой функцией принимается значение 13. Следовательно, выполнение проверок и3, и5, и6 позволяет обнаруживать отказы с минимальными затратами в 13 условных единиц.

Число вычислений значений целевой функции (9.2) и ограничений (9.3) при поиске оптимального решения задачи методом полного перебора определяется по формуле 2т (п + 1). Например, для решения задачи (9.4)-(9.10) полным перебором требуется 448 вычислений. Сокращение перебора применением алгоритма Баллаша с фильтром позволяет уменьшить число вычислений до 116, т. е. до 26% от числа вычислений при полном переборе.

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

Уменьшение вычислений по алгоритму Баллаша достигается выбором допустимого решения, принимаемого в качестве фильтра, близкого к оптимальному. Допустимое решение можно определять по эвристическому алгоритму исключения.

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