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

2016-07-30СтудИзба

Описание файла

Документ из архива "Выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.

Онлайн просмотр документа "49529"

Текст из документа "49529"

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.

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

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

P(Ω)=max

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

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

∑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.

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Нет! Мы не выполняем работы на заказ, однако Вы можете попросить что-то выложить в наших социальных сетях.
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
4144
Авторов
на СтудИзбе
667
Средний доход
с одного платного файла
Обучение Подробнее