Каталог Рефератов - Выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ

	Информационно-образоательный портал
	Рефераты, курсовые, дипломы, научные работы,



МЕНЮ\|

поиск

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

птимальный набор включает параметры ?*= {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);

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);

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;

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;

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.

2. Метод ветвей и границ

2.1 Теоретическая часть

Рассмотрим следующую задачу целочисленного программирования. Требуется максимизировать выражение:

L=?cj•xj (4)

j=1

при ограничениях

?а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,

?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

Таблица 4

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
hj	0.034	0.03	0.0375	0.045	0.0217	0.0267	0.035	0.0067	0.06	0.04

Для удобства расчетов проранжируем таблицу 4 в порядке убывания hj и присвоим новые номера элементам, следующим образом:

Таблица 5

N	1	2	3	4	5	6	7	8	9	10
n	9	4	10	3	7	1	2	6	5	8
Qi	0.06	0.09	0.04	0.15	0.07	0.17	0.03	0.08	0.13	0.02
с(xi)	1	2	1	4	2	5	1	3	6	3
hj	0.06	0.045	0.04	0.0375	0.035	0.034	0.03	0.0267	0.02167	0.0067

Для формирования таблицы 6 произведем расчеты:
1)
8
?сj=19>b1 - ? cj•xj=16-0=16;
j=1 xjЄS
7
?сj=1616;
j=1
7
? с = с - ? сj•xj - ?сj=16-0-16=0
xjЄS j=1
Hs(x1) = q1+q2+q3+q4+q5+q6+q7+h8? с = 0.61
8
?сj=18>b1 - ? cj•xj=16-0=16;
j=2 xjЄS
7
?сj=1516;
j=2
7
? с = с - ? сj•xj - ?сj=16-0-15=1
xjЄS j=2
Hs(x1) = q2+q3+q4+q5+q6+q7+h8? с = 0.5767
2)

?сj=18>b1 - ? cj•xj=16-1=15;

j=2 xjЄS

?сj=1515;

j=2

? с = с - ? сj•xj - ?сj=16-1-15=0

xjЄS j=2

Hs(x2) = q1+q2+q3+q4+q5+q6+q7+h8? с = 0.61

?сj=16>b1 - ? cj•xj=16-1=15;

j=3 xjЄS

?сj=1315;

j=3

? с = с - ? сj•xj - ?сj=16-1-13=2

xjЄS j=3

Hs(x2) = q1+q3+q4+q5+q6+q7+h8? с = 0.5734

Страницы: 1, 2, 3

© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.