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

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

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

Кафедра 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 обозначено множество неотрицательных целочисленных векторов Ω, отвечающих наборам, в которых общая стоимость проверки параметров не превосходит величины Υ.

Пусть Υ₀=min c(x_i).

i=1,…,n

Тогда при всех Υ Є [0,Υ₀] соответствующие множества Χ_Υ состоят, из одного нулевого элемента и f(Y)=0 для всех таких Υ. Для ресурса Υ Є [Υ₀, С] согласно общей схеме динамического программирования справедливы следующие рекуррентные соотношения:

f(Y_k)=max [Q_i + f[Y_k – c(x_i)] – G_i (1)

iЄI_Y

где k=Y₀, Y₀+1, …, C; I_Y – множество тех i, для которых с(x_i)≤Y_k, начиная с номера k=max c(x_i) уравнение (1) решается для всех i= 1,…,n;

G_i = ∑P_i – сумма вероятностей элементов i-го параметра, которые пересекаются с

IЄR(x_i)∩Ω_l^*

элементами подмножества Ω_l^*, образованного на шаге Y_k – c(x_i).

Если " i, j; R(x_i)∩R(x_j)= Æ, то G_i=0 и

f(Y_k)=max {Q_i + f[Y_k – c(x_i)]} (2)

iЄI_Y

Для решения интересующей нас задачи опишем простой численный метод, не требующий предварительного определения всех допустимых наборов и основанный на рекуррентных соотношениях (1). Для всех целых Υ = Υ₀, С по формуле (1) вычисляются величины f(Y_k) и при этом фиксируются индексы i_Yk^*, на которых достигаются максимумы в (1). Искомый вектор Ω формируется последовательно включением в набор параметра i_Ykи подмножества Ω_l^*, зафиксированного на шаге Y_k – c(x_i). При этом, если Y_kЄ Ω_l*, то на данном шаге этот параметр исключается из рассмотрения, так как каждый параметр может включаться в набор не более одного раза. Если на некотором ν-м шаге окажется, что f(Y_ν)< f(Y_ν-1), то в качестве Ω_ν* принимается подмножество Ω_ν-1* и фиксируется параметр i_Yν-1, причем за f(Y_ν)< принимается значение f(Y_ν-1). Заметим, что если в задаче P(Ω)=max при

∑x_i·c(x_i)≤C

iЄΩ

принять более жесткое ограничение, а именно ∑c(x_i)=C, то последнее не допустимо, iЄΩ так как в этом случае max f(Y_k) может быть меньше max f(Y_k-1) из-за того, что он достигается на другом подмножестве параметров.

Общая сложность метода, очевидно, φ(n) ≤ c(n+1), т.е. экспоненциальная функция при переборе заменена линейной функцией. При этом для запоминания промежуточных значений необходимо k≤2c ячеек памяти. Если в качестве максимизируемого критерия использовать P(Ω)=∏(1-p_i)/∏(1-p_i), то необходимо решить задачу динамического iЄR(S) iЄR(Ω) программирования с мультипликативным критерием. Для этого достаточно прологарифмировать это выражение и обозначить

V=lgP(Ω)=lgР₀-∑lg(1-p_i). (3)

iЄR(Ω)

Так как выражение, стоящее под знаком ∑ в (3), отрицательно, то, V= V_max тогда, когда максимальна величина суммы, т.е. в этом случае получим новую целевую функцию

V=∑ν_i, где ν_i=lg (1-p_i),

iЄR(Ω)

обладающую свойством аддитивности и обращающуюся в максимум одновременно с P(Ω).