Полная версия

Главная arrow Строительство arrow Диагностирование, ремонт и техническое обслуживание систем управления бытовых машин и приборов

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

МЕТОДЫ И АЛГОРИТМЫ ОПТИМИЗАЦИИ ПОИСКА МЕСТА ОТКАЗА

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

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

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

Таблица 10.1

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

Е

их

U2

W3

W4

иъ

ие

ео

1

1

1

1

1

1

ei

0

1

0

1

0

0

б2

1

0

1

0

0

0

ез

1

1

0

1

1

1

е4

1

1

1

0

0

0

е5

1

1

1

1

0

1

1

1

1

1

1

0

Если отказы различаются результатами проверок, то симметрические разности множеств ср0(в.), 0(е.), содержащие элементы, принадлежащие в точности одному из множеств, не являются пустыми:

где ср0: Е° -> 17°;

А —- символ симметрической разности множеств. Например, при i = 1 и j = 2 по таблице 10.1 определяем:

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

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

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

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

Ограничения (10.3) формируются на основе неравенств (10.1). Число ограничений вычисляется по формуле

где п = |?°|. Например, при п = 6 число ограничений равно

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

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

о

290

Ограничения (10.5)-(10.19) получены на основе неравенств

(10.1).

Например, если

и приходим к ограничению (10.5).

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

Действительно, из ограничения (10.11) следует, что х2 = 1 и множество проверок, позволяющих обнаруживать отказы с минимальными затратами, должно содержать проверку и2. После подстановки х% = 1 в целевую функцию и ограничения получаем:

min (3Xj + 3 + 8о:4

+ 6х5 + 5я6 + 4); (10.20)

х, + + хс > 0;

1 5 о 7

(10.21)

хх + х3 + xt > 0;

(10.22)

х1 + *з + хб>0;

(10.23)

*1 + *з+;г5>0;

(10.24)

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

Допустимым решением задачи (10.20)—(10.30) удовлетворяющим ограничениям (10.21)—(10.30), являются, например,

292

Таблица 10.2

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

Номер

сонета-

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

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

ния

Х3

Х4

*5

Х6

(10.31)

(10.26)

(10.27)

(10.28)

(10.25)

(10.20)

1

0

0

0

0

0

4

0

2

0

0

0

0

1

9

0

3

0

0

0

1

0

10

1

0

4

0

0

0

1

1

15

1

1

1

5

0

0

1

0

0

12

0

6

0

0

1

0

1

17

0

7

0

0

1

1

0

18

8

0

0

1

1

1

23

9

0

1

0

0

0

6

1

1

0

10

0

1

0

0

1

11

1

2

1

11

0

1

0

1

0

12

2

1

0

12

0

1

0

1

1

17

2

2

2

3

17

13

0

1

1

0

0

14

1

1

1

31

1

1

1

1

0

23

32

1

1

1

1

1

28

значения переменных для которых

целевая функция (10.20) принимает значение 17.

Минимальное значение целевой функции будет не более 17, если выполняется дополнительное ограничение

Результаты определения оптимального решения по алгоритму Баллаша частично представлены в таблице 10.2.

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

Число вычислений значений целевой функции (10.2) и ограничений (10.3) при поиске оптимального решения задачи методом полного перебора определяется по формуле

Например, для решения задачи (10.4)-(10.19) полным перебором требуется 1024 вычисления.

Сочетание методического приема сокращения числа ограничений с алгоритмом Баллаша позволяет уменьшить число вычислений до 91, т. е. приблизительно до 9% от числа вычислений при полном переборе.

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

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>