Курсовая работа: Выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ
Московский Авиационный Институт
(Технический Университет)
Кафедра 308
Курсовая работа
Выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ
Вариант II(2)
Выполнила
студентка
группы КТ-515
Принял
Москва
2008г.
Содержание
Задание
1. Метод динамического программирования
1.1 Теоретическая часть
2.2 Практическая часть
- ручной счёт
- листинг программы
2. Метод ветвей и границ
2.1 Теоретическая часть
2.2 Практическая часть
- ручной счёт
- листинг программы
Вывод
Литература
Задание
Вариант II(2)
Выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ при непересекающихся элементах объекта контроля и ограничениях по затратам на контроль С≤16.
Исходные данные: вероятность отказов элементов и затраты на контроль параметров.
Выбрать такие параметры, чтобы С≤16 при Q=Qmax.
1. Метод динамического программирования
1.1 Теоретическая часть
Математически задачу выбора набора параметров из заданной их совокупности можно сформулировать следующим образом.
Пусть работоспособность объекта контроля характеризуется совокупностью n взаимосвязанных параметров, образующих множество S={x1, x2, …, xn}. Проверка всех параметров из S влечет контроль всех N элементов системы и дает однозначный ответ: объект исправен, если все N элементов исправны, или неисправен, если по крайней мере один из элементов отказал. Для " xi определено подмножество R(xi) элементов, проверяемых при контроле i-го параметра, причем предполагаем, что эти подмножества могут пересекаться, т.е. $ i, j: R(xi)ÇR(xj). Пусть W - некоторый набор параметров из множества S, т.е. WÍS. Тогда WÇW=Æ и WÈW=S. Значения xi из S можно представить булевым вектором, причем
xi = 1, если xiÎW,
0, если xiÎW.
Задача выбора параметров в этом случае формулируется двояко:
1) найти набор Ω, для которого
P(Ω)=max
при ∑xi·c(xi)≤C; iЄΩ
2) найти набор Ω, для которого
∑xi·c(xi)=min
при P(Ω)≥Pз,
где P(Ω) – апостериорная вероятность работоспособного состояния объекта контроля при положительном исходе контроля выбранных параметров WÍS; с(xi) – затраты на контроль i-го параметра; Рз – требуемая достоверность контроля; С – ограничение на общую стоимость контроля.
Значение P(Ω) зависит от принятых допущений и может быть найдено по формуле Байеса. Так, если предполагать в изделии наличие лишь одного отказа, то
P(Ω)=Р0/1-∑Рi,
iЄR(Ω)
где Р0=∏(1-рi) – априорная вероятность безотказной работы объекта:
iЄR(S)
Р0=1-∑Рi;
iЄR(S)
Рi - нормированная вероятность отказа системы из-за отказа i-го элемента:
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
Вычисления сведем в таблицу 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');
Reset(f);
sgW.Cells[0,0] := 'W';
// Ввод исходной матрицы
readln(f);
for j:=1 to 10 do
begin
sgH.Cells[0,j] := IntToStr(j);
sgW.Cells[0,j] := IntToStr(j);
for i:=1 to 10 do
begin
sgH.Cells[i,0] := IntToStr(i);
read(f, x);
sgH.Cells[i,j] := IntToStr(x);
if x = 1 then
H[i-1,j-1] := true
else
H[i-1,j-1] := false;
end;
readln(f);
end;
// Ввод вероятностей
readln(f);
readln(f);
sgP.Cells[0,0] := 'P';
for i:=1 to 10 do
begin
read(f, P[i-1]);
sgP.Cells[i,0] := FloatToStr(P[i-1]);
end;
readln(f);
// Ввод стоимостей
readln(f);
readln(f);
sgC.Cells[0,0] := 'C';
for j:=1 to 10 do
begin
read(f, C[j-1]);
sgC.Cells[0,j] := IntToStr(C[j-1]);
end;
CloseFile(f);
// Ввод вероятностей обнаружения отказа
sgQ.Cells[0,0] := 'Q';
for j:=1 to 10 do
sgQ.Cells[0,j] := FloatToStr(Q(j-1,H,P));
lbC.Text := '1';
end;
procedure TForm1.BitBtn1Click(Sender: TObject);
var i: integer;
begin
label1.Caption := FloatToStr(maxf(1, StrToInt(lbC.Text), H,P,C, W));
for i:=1 to 10 do
begin
sgW.Cells[2,i] := IntToStr(W[i-1].N);
if W[i-1].E then
sgW.Cells[1,i] := '1'
else
sgW.Cells[1,i] := '0';
end;
end;
procedure TForm1.sgExit(Sender: TObject);
var i,j: integer;
begin
for j:=1 to 10 do
for i:=1 to 10 do
if sgH.Cells[i,j] = '1' then
H[i-1,j-1] := true
else
H[i-1,j-1] := false;
for i:=1 to 10 do
P[i-1] := StrToFloat(sgP.Cells[i,0]);
for j:=1 to 10 do
C[j-1] := StrToInt(sgC.Cells[0,j]);
// Ввод вероятностей обнаружения отказа
for j:=1 to 10 do
sgQ.Cells[0,j] := FloatToStr(Q(j-1,H,P));
end;
end.
unit Unit2;
interface
type
TH = array [0..9, 0..9] of boolean;
TP = array [0..9] of extended;
TC = array [0..9] of integer;
TDateW = record
E: boolean;
N: integer;
end;
TW = array [0..9] of TDateW;
function Q(j: integer; H: TH; P: TP): extended;
function maxf(n, Yk: integer; H: TH; P: TP; C: TC; var W: TW): extended;
implementation
function Q(j: integer; H: TH; P: TP): extended;
var i: integer;
begin
Result := 0;
for i:=0 to 9 do
if H[i,j] then
Result := Result + P[i];
end;
function G(j: integer; H: TH; P: TP; W: TW): extended;
var i,k: integer;
begin
Result := 0;
for i:=0 to 9 do
if H[i,j] then
for k:=0 to 9 do
if W[k].E and H[i,k] then
begin
Result := Result + P[i];
Break;
end;
end;
function f(n, Yk, j: integer; H: TH; P: TP; C: TC; var W: TW): extended;
begin
Result := Q(j,H,P) + maxf(n+1, Yk - C[j], H,P,C, W) - G(j,H,P,W);
end;
function maxf(n, Yk: integer; H: TH; P: TP; C: TC; var W: TW): extended;
var j,i: integer;
ft: extended;
Wt: TW;
begin
Result := 0;
for i:=0 to 9 do
begin
W[i].E := false;
W[i].N := 0;
end;
for j:=0 to 9 do
if C[j] <= Yk then
begin
for i:=0 to 9 do
begin
Wt[i].E := false;
Wt[i].N := 0;
end;
ft := f(n, Yk, j, H,P,C, Wt);
if Result < ft then
begin
Result := ft;
W := Wt;
W[j].E := true;
W[j].N := n;
end;
end;
end;
end.
2. Метод ветвей и границ
2.1 Теоретическая часть
Рассмотрим следующую задачу целочисленного программирования. Требуется максимизировать выражение:
n
L=∑cj∙xj (4)
j=1
при ограничениях
n
∑аij∙xj≤bi, i=1, …,m (5)
j=1
xjЄ{0;1}, j=1, …,n
причем сj≥0, aij≥0.
Метод ветвей и границ использует последовательно-параллельную схему построения дерева возможных вариантов. Первоначально ищут допустимый план и для каждого возможного варианта определяют верхнюю границу целевой функции. Ветви дерева возможных вариантов, для которых верхняя граница ниже приближенного решения, из дальнейшего рассмотрения исключают.
Эффективность вычислительных алгоритмов зависит от точности и простоты способа определения верхней границы возможных решений и точности определения приближенного решения. Чем точнее способ определения верхней границы целевой функции, тем больше бесперспективных ветвей отсекается в процессе оптимизации. Однако увеличение точности расчета верхних границ связано с возрастанием объема вычислений. Например, если для оценки верхней границы использовать симплекс-метод, то результат будет достаточно точным, но потребует большого объема вычислительной работы.
Рассмотрим алгоритм решения задачи методом ветвей и границ с простым и эффективным способом оценки верхней границы целевой функции.
Обозначим: U – множество переменных xj; S – множество фиксированных переменных, вошедших в допустимое решение; Es – множество зависимых переменных, которые не могут быть включены в множество S, так как для них выполняется неравенство
аij> bi - ∑аij∙xj, i=1, …,m
xjЄS
GS – множество свободных переменных, из которых производится выбор для включения в S очередной переменной.
Рассмотрим первоначально одномерную задачу, когда m=1 и задача (4) имеет только одно ограничение вида (5).
Обозначим h1j = cj/a1j и допустим, что xjЄS (j=1, …,k<n) и выполняются условия
h1,k+1≥ h1,k+2≥ …≥ h1l, l≤n,
l
∑a1j>b1 - ∑ a1j∙xj,
j=k+1 xjЄS
l-1
∑a1j≤ b1 - ∑ a1j∙xj,
j=k+1 xjЄS
Условия означают, что во множество S без нарушения неравенства (5) можно дополнительно ввести элементы xk+1, xk+2, …, xl-1. При введении во множество S элементов xk+1, xk+2, …, xl неравенство (5) не выполняется.
Для определения верхней границы решения может быть использовано выражение
Hs =∑cj∙xj + Ls’,
xjЄS
где
l-1
Ls’ = ∑сj + h1l∆ b1 ,
j=k+1
l-1
∆ b1 = b1 - ∑ a1j∙xj - ∑a1j.
xjЄS j=k+1
Из условий следует, что Ls’ не меньше максимального значения величины
∑cj∙xj
xjЄGS
при ограничениях
∑ a1j ∙xj b1 - ∑ a1j∙xj = b1’,
xjЄGS xjЄS
xjЄ {0;1}, xjЄGS ,
Выбор очередной переменной для включения во множество S производится с помощью условия
h1r(xr) = max h1j(xj)
xjЄGS
Для выбранной переменной xr определяются величины Hs(xr) и Hs(xr), т.е. в S включаются xr = 1 или xr = 0.
Если в процессе решения окажется, что во множестве GS нет элементов, которые могут быть введены во множество S без нарушения ограничения (5), то полученное решение Ls =∑cj∙xj принимается в качестве первого приближенного xjЄS решения L0.
Все вершины дерева возможных вариантов, для которых выполняются условия
Hs≤ L0, из дальнейшего рассмотрения исключаются.
Из оставшихся ветвей выбирается ветвь с максимальным значением Hs, и процесс поиска оптимального варианта продолжается. Если в процессе решения будет найдено Ls = ∑cj∙xj > L0, то полученное решение принимается
xjЄS
в качестве нового приближенного результата. Вычислительная процедура заканчивается, если для оставшихся ветвей выполняется условие Hs≤ L0.
2.2 Практическая часть
Ручной счёт
Данные для расчета:
С≤16
Таблица 5
№