39
Московский Авиационный Институт
(Технический Университет)
Кафедра 308
Курсовая работа
Выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ
Вариант II(2)
Исходные данные: вероятность отказов элементов и затраты на контроль параметров.
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)
Для решения интересующей нас задачи опишем простой численный метод, не требующий предварительного определения всех допустимых наборов и основанный на рекуррентных соотношениях (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),
обладающую свойством аддитивности и обращающуюся в максимум одновременно с P(?).
1.2 Практическая часть
Ручной счёт
Данные для расчета:
Страницы: 1, 2, 3, 4