49529 (609145)
Текст из файла
35
Московский Авиационный Институт
(Технический Университет)
Кафедра 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.
Задача выбора параметров в этом случае формулируется двояко:
-
найти набор Ω, для которого
P(Ω)=max
при ∑xi·c(xi)≤C; iЄΩ
-
найти набор Ω, для которого
∑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,7,3,4,10,9} при этом
P(Ω) = 0,61+0,16 = 0,77 и С = 16.
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.