Выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ
39 Московский Авиационный Институт (Технический Университет) Кафедра 308 Курсовая работа Выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ Вариант II(2) Выполнила студенткагруппы КТ-515 Принял Москва2008г. СодержаниеЗадание1. Метод динамического программирования1.1 Теоретическая часть 2.2 Практическая часть- ручной счёт- листинг программы2. Метод ветвей и границ2.1 Теоретическая часть 2.2 Практическая часть- ручной счёт- листинг программыВыводЛитература ЗаданиеВариант II(2)Выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ при непересекающихся элементах объекта контроля и ограничениях по затратам на контроль С?16.Исходные данные: вероятность отказов элементов и затраты на контроль параметров.
Выбрать такие параметры, чтобы С?16 при Q=Qmax.|
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={x1, x2, …, xn}. Проверка всех параметров из S влечет контроль всех N элементов системы и дает однозначный ответ: объект исправен, если все N элементов исправны, или неисправен, если по крайней мере один из элементов отказал. Для xi определено подмножество R(xi) элементов, проверяемых при контроле i-го параметра, причем предполагаем, что эти подмножества могут пересекаться, т.е. i, j: R(xi)R(xj). Пусть - некоторый набор параметров из множества S, т.е. S. Тогда и S. Значения xi из S можно представить булевым вектором, причемxi = 1, если xi,0, если xi.Задача выбора параметров в этом случае формулируется двояко:1) найти набор ?, для которогоP(?)=maxпри ?xi·c(xi)?C; iЄ?2) найти набор ?, для которого?xi·c(xi)=min при P(?)?Pз,где P(?) - апостериорная вероятность работоспособного состояния объекта контроля при положительном исходе контроля выбранных параметров S; с(xi) - затраты на контроль i-го параметра; Рз - требуемая достоверность контроля; С - ограничение на общую стоимость контроля.Значение P(?) зависит от принятых допущений и может быть найдено по формуле Байеса. Так, если предполагать в изделии наличие лишь одного отказа, тоP(?)=Р0/1-?Рi, iЄR(?) где Р0=?(1-рi) - априорная вероятность безотказной работы объекта: iЄR(S)Р0=1-?Рi; iЄR(S)Рi - нормированная вероятность отказа системы из-за отказа i-го элемента:Рi=(pi/(1-pi))/(1+? pk/(1-pk); kЄR(S)pi - априорная вероятность отказа i-го элемента. Тогда вероятность того, что отказ будет обнаружен при проверке k-го параметра, можно вычислить по формуле:Qk=?Pk kЄR(xk) При возможности наличия в ОК произвольного числа отказовP(?)=?(1-pi)/?(1-pi) iЄR(S) iЄR(?) Можно использовать простой перебор вариантов, однако возникающие при этом вычислительные трудности не позволяют сделать этого даже для простых систем (при n>10). В связи с этим комплектование набора будем трактовать как многошаговый процесс, состоящий из последовательного выбора отдельных параметров.В соответствии с общим принципом оптимальности разобьем весь имеющийся ресурс стоимости С на С отрезков единичной длины. (В практических случаях заданные положительные величины с(xi) и С можно считать всегда целыми. Если это не так, то необходимо перейти к более мелким стоимостным единицам в зависимости от разрядности дробной части.). Рассмотрим наряду с интересующей нас исходной задачей множество аналогичных задачf(Y)=max ?(x), Y Є [0,C],xЄXYгде через XY обозначено множество неотрицательных целочисленных векторов ?, отвечающих наборам, в которых общая стоимость проверки параметров не превосходит величины ?.Пусть ?0=min c(xi).i=1,…,n Тогда при всех ? Є [0,?0] соответствующие множества ?? состоят, из одного нулевого элемента и f(Y)=0 для всех таких ?. Для ресурса ? Є [?0, С] согласно общей схеме динамического программирования справедливы следующие рекуррентные соотношения:f(Yk)=max [Qi + f[Yk - c(xi)] - Gi (1)iЄIYгде k=Y0, Y0+1, …, C; IY - множество тех i, для которых с(xi)?Yk, начиная с номера k=max c(xi) уравнение (1) решается для всех i= 1,…,n; Gi = ?Pi - сумма вероятностей элементов i-го параметра, которые пересекаются сIЄR(xi)??l*элементами подмножества ?l*, образованного на шаге Yk - c(xi).Если i, j; R(xi)?R(xj)= , то Gi=0 иf(Yk)=max {Qi + f[Yk - c(xi)]} (2)iЄIYДля решения интересующей нас задачи опишем простой численный метод, не требующий предварительного определения всех допустимых наборов и основанный на рекуррентных соотношениях (1). Для всех целых ? = ?0, С по формуле (1) вычисляются величины f(Yk) и при этом фиксируются индексы iYk*, на которых достигаются максимумы в (1). Искомый вектор ? формируется последовательно включением в набор параметра iYk и подмножества ?l*, зафиксированного на шаге Yk - c(xi). При этом, если YkЄ ?l*, то на данном шаге этот параметр исключается из рассмотрения, так как каждый параметр может включаться в набор не более одного раза. Если на некотором ?-м шаге окажется, что f(Y?)< f(Y?-1), то в качестве ??* принимается подмножество ??-1* и фиксируется параметр iY ?-1, причем за f(Y?)< принимается значение f(Y?-1). Заметим, что если в задаче P(?)=max при ?xi·c(xi)?C iЄ? принять более жесткое ограничение, а именно ?c(xi)=C, то последнее не допустимо, iЄ? так как в этом случае max f(Yk) может быть меньше max f(Yk-1) из-за того, что он достигается на другом подмножестве параметров. Общая сложность метода, очевидно, ?(n) ? c(n+1), т.е. экспоненциальная функция при переборе заменена линейной функцией. При этом для запоминания промежуточных значений необходимо k?2c ячеек памяти. Если в качестве максимизируемого критерия использовать P(?)=?(1-pi)/?(1-pi), то необходимо решить задачу динамического iЄR(S) iЄR(?) программирования с мультипликативным критерием. Для этого достаточно прологарифмировать это выражение и обозначить V=lgP(?)=lgР0-?lg(1-pi). (3) iЄR(?) Так как выражение, стоящее под знаком ? в (3), отрицательно, то, V= Vmax тогда, когда максимальна величина суммы, т.е. в этом случае получим новую целевую функцию V=??i, где ?i=lg (1-pi), iЄR(?) обладающую свойством аддитивности и обращающуюся в максимум одновременно с P(?). 1.2 Практическая часть Ручной счёт Данные для расчета: С?16 Таблица 1|
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 следующим образом:Таблица 2|
N | 9 | 10 | 2 | 4 | 7 | 6 | 8 | 3 | 1 | 5 | | Qi | 0.06 | 0.04 | 0.03 | 0.09 | 0.07 | 0.08 | 0.02 | 0.15 | 0.17 | 0.13 | | с(xi) | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 5 | 6 | | |
Вычисления сведем в таблицу 3:Таблица 3|
Yk | f(Yk) | iYk | ?l* | | 1 | 0,06 | 9 | 9 | | 2 | 0,1 | 10 | 9,10 | | 3 | 0,15 | 4 | 4,9 | | 4 | 0,19 | 4 | 4,10,9 | | 5 | 0,22 | 7 | 7,4,9 | | 6 | 0,26 | 7 | 7,4,10,9 | | 7 | 0,3 | 3 | 3,4,9 | | 8 | 0,34 | 3 | 3,4,10,9 | | 9 | 0,37 | 3 | 3,7,4,9 | | 10 | 0,41 | 7 | 7,3,4,10,9 | | 11 | 0,44 | 2 | 2,7,3,4,10,9 | | 12 | 0,47 | 1 | 1,3,4,9 | | 13 | 0,51 | 1 | 1,3,4,10,9 | | 14 | 0,54 | 2 | 2,1,3,4,10,9 | | 15 | 0,58 | 7 | 7,1,3,4,10,9 | | 16 | 0,61 | 1 | 1,2,7,3,4,10,9 | | |
Страницы: 1, 2, 3
|
