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

// Ввод вероятностей обнаружения отказа

forj:=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=∑c_j∙x_j(4)

j=1

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

∑а_ij∙x_j≤b_i, i=1, …,m(5)

j=1

x_jЄ{0;1}, j=1, …,n

причем с_j≥0, a_ij≥0.

Метод ветвей и границ использует последовательно-параллельную схему построения дерева возможных вариантов. Первоначально ищут допустимый план и для каждого возможного варианта определяют верхнюю границу целевой функции. Ветви дерева возможных вариантов, для которых верхняя граница ниже приближенного решения, из дальнейшего рассмотрения исключают.

Эффективность вычислительных алгоритмов зависит от точности и простоты способа определения верхней границы возможных решений и точности определения приближенного решения. Чем точнее способ определения верхней границы целевой функции, тем больше бесперспективных ветвей отсекается в процессе оптимизации. Однако увеличение точности расчета верхних границ связано с возрастанием объема вычислений. Например, если для оценки верхней границы использовать симплекс-метод, то результат будет достаточно точным, но потребует большого объема вычислительной работы.

Рассмотрим алгоритм решения задачи методом ветвей и границ с простым и эффективным способом оценки верхней границы целевой функции.

Обозначим: U – множество переменных x_j; S – множество фиксированных переменных, вошедших в допустимое решение; E_s – множество зависимых переменных, которые не могут быть включены в множество S, так как для них выполняется неравенство

а_ij> b_i - ∑а_ij∙x_j, i=1, …,m

x_jЄS

G_S – множество свободных переменных, из которых производится выбор для включения в S очередной переменной.

Рассмотрим первоначально одномерную задачу, когда m=1 и задача (4) имеет только одно ограничение вида (5).

Обозначим h₁_j = c_j/a₁_j и допустим, что x_jЄS (j=1, …,k<n) и выполняются условия

h_1,_k₊₁≥ h_1,_k₊₂≥ …≥ h₁_l, l≤n,

∑a₁_j>b₁ - ∑ a₁_j∙x_j,

j=k+1x_jЄS

l-1

∑a₁_j≤b₁ - ∑ a₁_j∙x_j,

j=k+1 x_jЄS

Условия означают, что во множество S без нарушения неравенства (5) можно дополнительно ввести элементы x_k₊₁, x_k₊₂, …, x_l_-1. При введении во множество S элементов x_k₊₁, x_k₊₂, …, x_l неравенство (5) не выполняется.

Для определения верхней границы решения может быть использовано выражение

H_s =∑c_j∙x_j+ L_s^’,

x_jЄS

где

l-1

L_s^’ = ∑с_j + h₁_l∆b₁ ,

j=k+1

l-1

∆b₁ = b₁ - ∑ a₁_j∙x_j- ∑a₁_j.

x_jЄSj=k+1

Из условий следует, что L_s^’не меньше максимального значения величины

∑c_j∙x_j

x_jЄG_S

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

∑ a_1j ∙x_jb₁ - ∑ a_1j∙x_j= b₁^’,

x_jЄG_Sx_jЄS

x_jЄ {0;1}, x_jЄG_S ,

Выбор очередной переменной для включения во множество S производится с помощью условия

h_1r(x_r) = max h_1j(x_j)

x_jЄG_S

Для выбранной переменной x_r определяются величины H_s(x_r) и H_s(x_r), т.е. в S включаются x_r = 1 или x_r = 0.

Если в процессе решения окажется, что во множестве G_S нет элементов, которые могут быть введены во множество S без нарушения ограничения (5), то полученное решение L_s =∑c_j∙x_jпринимается в качестве первого приближенного x_jЄSрешения L₀.

Все вершины дерева возможных вариантов, для которых выполняются условия

H_s≤ L₀, из дальнейшего рассмотрения исключаются.

Из оставшихся ветвей выбирается ветвь с максимальным значением H_s, и процесс поиска оптимального варианта продолжается. Если в процессе решения будет найдено L_s = ∑c_j∙x_j> L₀, то полученное решение принимается

x_jЄS

в качестве нового приближенного результата. Вычислительная процедура заканчивается, если для оставшихся ветвей выполняется условие H_s≤ L₀.

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 в порядке убывания h_j и присвоим новые номера элементам, следующим образом:

Таблица 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 произведем расчеты:

∑с_j=19>b₁ - ∑ c_j∙x_j=16-0=16;

j=1 x_jЄS

∑с_j=16£16;

j=1

∆с = с - ∑ с_j∙x_j- ∑с_j=16-0-16=0

x_jЄSj=1

H_s(x₁) = q1+q2+q3+q4+q5+q6+q7+h₈∆с = 0.61

∑с_j=18>b₁ - ∑ c_j∙x_j=16-0=16;

j=2 x_jЄS

∑с_j=15£16;

j=2

∆с = с - ∑ с_j∙x_j- ∑с_j=16-0-15=1

x_jЄSj=2

H_s(x₁) = q2+q3+q4+q5+q6+q7+h₈∆с = 0.5767

∑с_j=18>b₁ - ∑ c_j∙x_j=16-1=15;

j=2 x_jЄS

∑с_j=15£15;

j=2

∆с = с - ∑ с_j∙x_j- ∑с_j=16-1-15=0

xjЄSj=2

H_s(x₂) = q1+q2+q3+q4+q5+q6+q7+h₈∆с = 0.61

∑с_j=16>b₁ - ∑ c_j∙x_j=16-1=15;

j=3 xjЄS

∑с_j=13£15;

j=3

∆с = с - ∑ с_j∙x_j- ∑с_j=16-1-13=2

xjЄSj=3

H_s(x₂) = q1+q3+q4+q5+q6+q7+h₈∆с = 0.5734

∑с_j=16>b₁ - ∑ c_j∙x_j=16-1-2=13;

j=3xjЄS

∑с_j=13£13;

j=3

∆с = с - ∑ с_j∙x_j- ∑с_j=16-1-2-13=0

xjЄSj=3

H_s(x₃) = q1+q2+q3+q4+q5+q6+q7+h₈∆с = 0.61

∑с_j=15>b₁ - ∑ c_j∙x_j=16-1-2=13;

j=4 xjЄS

∑с_j=12£13;

j=4

∆с = с - ∑ с_j∙x_j- ∑с_j=16-1-2-12=1

xjЄSj=4

H_s(x₃) = q1+q2+q4+q5+q6+q7+h₈∆с = 0.5967

∑с_j=15>b₁ - ∑ c_j∙x_j=16-1-2-1=12;

j=4xjЄS

∑с_j=12£12;

j=4

∆с = с - ∑ с_j∙x_j- ∑с_j=16-1-2-1-12=0

xjЄSj=4

H_s(x₄) = q1+q2+q3+q4+q5+q6+q7+h₈∆с = 0.61

∑с_j=17>b₁ - ∑ c_j∙x_j=16-1-2-1=12;

j=5xjЄS

∑с_j=11£12;

j=5

∆с = с - ∑ с_j∙x_j- ∑с_j=16-1-2-1-11=1

xjЄSj=5

H_s(x₄) = q1+q2+q3+q5+q6+q7+q8+h₉∆с = 0.56167

∑с_j=11>b₁ - ∑ c_j∙x_j=16-1-2-1-4=8;

j=5xjЄS

∑с_j=8£8;

j=5

∆с = с - ∑ с_j∙x_j- ∑с_j=16-1-2-1-4-8=0

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

Для выбранной переменной xr определяются величины Hs(xr) и Hs(xr), т.е. в S включаются xr = 1 или xr = 0.

С≤16

Таблица 4

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

Для выбранной переменной x_r определяются величины H_s(x_r) и H_s(x_r), т.е. в S включаются x_r = 1 или x_r = 0.

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