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

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

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

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

Пусть Υ₀=minc(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=maxc(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ЄΩ так как в этом случае maxf(Y_k) может быть меньше maxf(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(Ω).

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.

Листинг программы

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, ToolWin, ComCtrls, mdCONTROLS, Grids, StdCtrls, ExtCtrls, Unit2,

Buttons;

type

TForm1 = class(TForm)

sgH: TStringGrid;

sgP: TStringGrid;

sgC: TStringGrid;

sgQ: TStringGrid;

lbC: TLabeledEdit;

BitBtn1: TBitBtn;

Label1: TLabel;

sgW: TStringGrid;

Label2: TLabel;

procedure FormCreate(Sender: TObject);

procedure BitBtn1Click(Sender: TObject);

procedure sgExit(Sender: TObject);

private

{ Private declarations }

public

H: TH;

P: TP;

C: TC;

W: TW;

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);

var i,j: integer;

x: Byte;

f: TextFile;

begin

AssignFile(f, 'data.txt');