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

Московский Авиационный Институт

(Технический Университет)

Кафедра 308

Курсовая работа

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

Вариант II(2)

Выполнила

студентка

группы КТ-515

Принял

Москва

2008г.

Содержание

Задание

1. Метод динамического программирования

1.1 Теоретическая часть

2.2 Практическая часть

- ручной счёт

- листинг программы

2. Метод ветвей и границ

2.1 Теоретическая часть

2.2 Практическая часть

- ручной счёт

- листинг программы

Вывод

Литература

Задание

Вариант II(2)

Выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ при непересекающихся элементах объекта контроля и ограничениях по затратам на контроль С≤16.

Исходные данные: вероятность отказов элементов и затраты на контроль параметров.

Выбрать такие параметры, чтобы С≤16 при Q=Q_max .

N	1	2	3	4	5	6	7	8	9	10
Qi	0.17	0.03	0.15	0.09	0.13	0.08	0.07	0.02	0.06	0.04
с(xi)	5	1	4	2	6	3	2	3	1	1

1. Метод динамического программирования

1.1 Теоретическая часть

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

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

x_i = 1, если x_i ÎW,

0, если x_i ÎW.

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

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

P(Ω)=max

при ∑x_i ·c(x_i )≤C; iЄΩ

2) найти набор Ω, для которого

∑x_i ·c(x_i )=min

при P(Ω)≥P_з ,

где P(Ω) – апостериорная вероятность работоспособного состояния объекта контроля при положительном исходе контроля выбранных параметров WÍS; с(x_i ) – затраты на контроль i-го параметра; Р_з – требуемая достоверность контроля; С – ограничение на общую стоимость контроля.

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

P(Ω)=Р₀ /1-∑Р_i ,

iЄR(Ω)

где Р₀ =∏(1-р_i ) – априорная вероятность безотказной работы объекта:

iЄR(S)

Р₀ =1-∑Р_i ;

iЄR(S)

Р_i - нормированная вероятность отказа системы из-за отказа i-го элемента: Р_i =(p_i /(1-p_i ))/(1+∑ p_k /(1-p_k ); kЄR(S)

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

Q_k =∑P_k

kЄR(x_k )

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

P(Ω)=∏(1-p_i )/∏(1-p_i )

iЄR(S) iЄR(Ω)

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

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

f(Y)=max λ(x), Y Є [0,C],

xЄX_Y

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

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать