Выбор параметров контроля c использованием МДП и МВГ при пересекающихся параметрах

Термин пересекающиеся параметры предполагает, что состояние некоторых функциональных элементов ОК может влиять на значения нескольких параметров.

Математическую задачу выбора параметров из заданной совокупности можно сформулировать следующим образом.

Пусть работоспособность объекта контроля характеризуется

ᴲ

совокупностью n взаимосвязанных параметров. Образующих множество S={x₁, x₂,…,x_n}. Проверка всех параметров из S влечет контроль всех N элементов системы и дает однозначный ответ: объект исправен, если все N элементов исправны, или неисправен. Если по крайней мере один из элементов отказал. Для x_i определено подмножество R(x_i) элементов, проверяемых при контроле i -ого параметра. Причем предполагается, что эти подмножества могут пересекаться, т.е. i, j: R(x_i) ∩ R(x_j).

Пусть Ω – некоторый набор параметров из множества S, т.е. . Тогда и , где Ω-набор контролируемых параметров, а - неконтролируемый набор. Значение из S можно представить булевым вектором, причем

Задача выбора параметров в этом случае формулируется двояко:

1) Найти набор, для которого

Р(Ω)=max (1.11)

при

2) Найти набор Ω. Для которого

(1.12)

при

где

- апостериорная вероятность работоспособного состояния объекта контроля при положительном исходе контроля выбранных параметров ;

c{x_i} - затраты на контроль i-ого параметра;

- требуемая достоверность контроля;

С – ограничение на общую стоимость контроля.

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

	(1.13)

где

- априорная вероятность безотказной работы объекта:

- нормированная вероятность отказа системы из-за отказа i -ого элемента:

	(1.14)

- априорная вероятность отказа i-ого элемента.

Тогда вероятность того, что отказ будет обнаружен при проверки i-ого параметра. Можно вычислить по формуле

При возможности наличия в ОК произвольного числа отказов

	(1.15)

Для решения задач (1.11) и (1.12) можно использовать простой перебор вариантов, однако возникающие при этом вычислительные трудности не позволяют сделать этого даже для простых систем (при n>10). В связи с этим комплектование набора трактуется как многошаговый процесс, состоящий из последовательного выбора отдельных параметров. В соответствии с общим принципом оптимальности, разобьем весь имеющийся ресурс стоимости С на С отрезков единичной длины. (В практических случаях заданные положительные величины c(x_i) и С можно считать всегда целыми. Если это не так, то необходимо перейти к более мелким стоимостным единицам в зависимости от разрядности дробной части.) Рассмотрим наряду с интересующей нас исходной задачей множество аналогичных задач

,аналог выражения (1.1),

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

Пусть

(1.16)

тогда при всех соответствующие множества X_Y состоят. Очевидно, из одного нулевого элемента и f(С)=0 для всех таких С. Для ресурса согласно общей схеме динамического программирования справедливы следующие рекуррентные соотношения:

где
R() -множество тех i, для которых , начиная с

номера уравнение (1.16) решается для всех i = 1,n

- сумма вероятностей элементов i-го параметра, которые пересекаются с элементами подмножества , образованного на шаге

Если

Æ, то

И

	(1.17)

Что приводит к условию задачи с пересекающимися параметрами.

Для решения рассматриваемой задачи рассмотрим простой численный метод, не требующий предварительного определения всех допустимых наборов и основанный на рекуррентных соотношениях (1.15). Для всех целых по формуле (1.16) вычисляют величины и при этом фиксируются индексы , на которых достигаются максимумы в (1.16). Искомый вектор формируется последовательно включение в набор параметра и подмножества , зафиксированного на шаге При этом, если , то на данном шаге этот параметр исключается из рассмотрения, так как каждый параметр может включаться в набор не более одного раза. Если на н6екотором v -м шаге окажется, что

То вы качестве принимается я подмножество и фиксируется параметр , причем за принимается значение . Заметим, что если в (1.11) принять более жесткое ограничение, а именно то последнее недопустимо, так как в этом случае может быть меньше из-за того, что он достигает на и другом подмножестве параметров.

Рассмотрим пример решения задачи максимизации целевой функции f(С_K-1) приограничении затрат на контроль С£ 31, для исходных данных, представленных в таблице 1.4., отражающей взаимодействие параметров, элементов, связанных с данными параметрами, вероятность отказа элемента p_i и затрат с_i, необходимых для контроля параметра х_{i .}

Таблица 1.4

Параметры	№	Элементы	Сi	Qi
														0,15
														0,22
														0,06
														0,2
														0,12
														0,19
														0,12
														0,28
	Pi	0,03	0,07	0,05	0,06	0,03	0,09	0,03	0,09	0,07	0,03	02,02	0,03

Ход решения задачи с использованием МДП по алгоритму, реализующему рекуррентное соотношение (1.16), представлено в таблице 1.5, из которой следует результат – оптимальным набором Ω* является состав проверок Ω* = { X₁;X₂;X₃;X₄;X₅;X₇;X₈ }.

Поясним, к примеру, определение значения целевой функции на этапе девять (выделенное количество затрат, при 9 затратных единицах максимальное значение f (C_k) обеспечивает i*_Ck=7, для него и с_i=3, что указывает на переход к шестому этапу (т.е. C_k=9-3), на котором f (C_k) =0,4, параметр 7 добавляет к этому значению 0,03, так как вероятность 0,09 вошла в значение шестого этапа. В результате получим, что на девятом этапе f (C_k) =0.43.
Результат пошаговой работы алгоритма представлен в виде таблицы1.5

Таблица 1.5

Выделяемое количество затратных единиц,   Ck	Значение целевой функции, f(Ck)	Выбор на данном шаге, i*Ck	Выбранный массив, Ω*
		-
	0,12
	0,12	-
	0,12	-
	0,24		5;7
	0,28
	0,4		8;5
	0,4	-	8;5
	0,4	-	8;5
	0,43		8;5;7
	0,43	-	8;5;7
	0,46		8;5;1
	0,46		8;5;1
	0,46		8;5;1
	0,49		8;5;7;1
	0,49		8;5;7;1
	0,49		8;5;1;2
	0,49		8;5;1;2
	0,49		8;5;1;2
	0,52		8;5;7;1;2
	0,52		8;5;7;1;2
	0,52		8;5;7;1;3
	0,52		8;5;7;1;3
	0,52		8;5;1;2;3
	0,54		8;5;7;1;2;4
	0,54		8;5;7;1;2;4
	0,55		8;5;7;1;3;2
	0,55		8;5;7;1;3;2
	0,55	-	8;5;7;1;3;2
	0,55	-	8;5;7;1;3;2
	0,55	-	8;5;7;1;3;2
	0,57		8;5;7;1;2;4;3

Таким образом, решением является набор проверок

Ω* = { X₁;X₂;X₃;X₄;X₅;X₇;X₈ }

Для задач больших размерностей, когда динамическое программирование становится неэффективным, рекомендуется метод ветвей и границ (МВГ). Этот метод более сложен в программировании, но для нахождения оптимального решения требует меньшего, в некоторых случаях, числа итераций. В рассматриваемом случае пересекающихся параметров метод реализуется следующим образом. В его основе лежит разбиение всего множества решений на два непересекающихся подмножества, соответствующих наборам Ω и . При этом для всех решений, получаемых при движении по любому пути от произвольной вершины (Ω^*, ^*) до висячих вершин., соответствующих единственным решениям, справедливо выражение

	(1.18)

P (Ω)≤1- P [ ^*|(S \ ^*)]- P₀,

где

P [ ^*|(S \ ^*)] – условная вероятность обнаружения отказа при контроле ^*, если параметры x _i S\ ^* проверены с положительными результатами.

Тогда выражение для оценки верхней границы целевой функции в случае пересекающихся параметров, т.е. Æ, имеет вид:

	(1.19)

Практически алгоритм поиска оптимального решения заключается в следующем.

1. В качестве исходных данных составляется таблица вида 1.4.

2. Для каждого параметра вычисляется отношение

где

Р_i*- сумма вероятностей отказов элементов, соответствующих единицам строки, параметра, рассчитываемого отношения.

Выбирается параметр, соответствующий максимуму отношения и данный параметр включается в набор, который в последствии называется базовым. Затем отношения пересчитываются для оставшихся параметров, с учетом того, что элементы, вошедшие в Р_i* выбранного параметра не учитываются при расчете очередного параметра. Такой расчет необходимо проделать для всех оставшихся параметров и выбрать из них параметр с максимальным отношением и включить его в базовый набор Ω_Б и т.д.

3.Вычисляется значение целевой функции и затрат базового набора f (С _k *).

Выбранные таким образом параметры образуют вектор базового решения Ω*, для которого вычисляется величина 1-P(Ω^*)=R*,

где P( ^*) соответствует значению целевой функции f (С _k *) из базового набора.

Эта величина и значение ограничения С яляются характеристиками первой вершины дерева вариантов (график на рис 1.2).

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

	(1.20)   (1.21)

Если для одного из параметров (1.20) или (1.21) не выполнено, то этот параметр включается в набор, так как в противном случае либо полученная в в базовом решении достоверность будет в дальнейшем недостижима, либо не будут удовлетворены ограничения по стоимости. В соответствии с этим множество решений решений разбиваем на два подмножества (параметр включен в набор Ω, параметр включен в набор ), образуется новая вершина дерева, для которой вычисляется верхняя граница.

При включении параметра х_i в набор (х_i® Ω) уменьшается запас по стоимости, при исключении параметра из набора (включение,х_i®) в набор Ω уменьшается запас по вероятности необнаружения отказа.

Процедура построения графа отражает процесс исследования возможностей улучшения базового решения.

5.Последовательно выбираются столбцы с двумя, тремя и большим числом единиц. Для которых проверяется условие (1.19).

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

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

Таблица 1.6

Шаг №		Группа проверок			Выбранная группа проверок	Накопленная стоимость
			0,88
		0,293
		0,17
		0,16
		0,1456
		0,144
		0,134
		0,09
		5;7	0,253		5;7
	5;1	0,146
	5;2	0.146
	5;4	0.136
	5;8	0,12
	5;3	0.117
	5;6	0,084
		5;7;1	0,14		5;7;1
	5;7;4	0,136
	5;7;2	0,122
	5;7;8	0,114
	5;7;3	0,1
	5;7;6	0,071
		5;7;1;4	0,118		5;7;1;4
	5;7;1;2	0,11
	5;7;1;8	0,102
	5;7;1;3	0.091
	5;7;1;6	0,064
		5;7;1;4;2	0,106		5;7;1;4;2
	5;7;1;4;8	0,098
	5;7;1;4;3	0,076
	5;7;1;4;6	0,062

Таблица 1.6 - Продолжение

		5; 7; 1; 4; 2; 8	0,092		5; 7; 1; 4; 2; 8
	5; 7; 1; 4; 2; 3	0,071
	5; 7; 1; 4; 2; 6	0,056
		5; 7; 1; 4; 2; 8; 3	0,061		5; 7; 1; 4; 2; 8; 3
	5; 7; 1; 4; 2; 8; 6	0,048
		5; 7; 1; 4; 2; 8; 3; 6	0,044		5; 7; 1; 4; 2; 8; 3; 6

В результате получаем базовый набор

Ω* = { x₅, x₇, x₁,x₄, x₂, x₈, x₃ }

Для которого R* = 0,03.

Далее, следуя описанному алгоритму, строится “дерево ветвления вариантов” (рис 1.2).

Ветвь, соответствующая параметрам Х₁, Х₅, Х₈, Х₃, Х₂, Х₇, , Х₄ соответствует оптимальному решению, так как висячие вершины всех остальных ветвей графа заканчиваются или перерасходом затрат или большей чем в базовом решении вероятностью необнаружения отказа R*.

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

Ω* = {X₁; X₂; X₃: X₄; X₅; X₇; X₈}.

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

Рисунок 1.2 – “ Древо ветвления вариантов” (начало)

Рисунок 1.2 (окончание)