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

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

j=1

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

n

∑а_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_1j = c_j/a_1j и допустим, что x_jЄS (j=1, …,k

h_1,k+1≥ h_1,k+2≥ …≥ h_1l, l≤n,

l

∑a_1j>b₁ - ∑ a_1j∙x_j,

j=k+1 x_jЄS

l-1

∑a_1j≤ b₁ - ∑ a_1j∙x_j,

j=k+1 x_jЄS

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

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

H_s =∑c_j∙x_j + L_s^’,

x_jЄS

где

l-1

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

j=k+1

l-1

∆ b₁ = b₁ - ∑ a_1j∙x_j - ∑a_1j.

x_jЄS j=k+1

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

∑c_j∙x_j

x_jЄG_S

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

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

x_jЄG_S x_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

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

Таблица 5

Для формирования таблицы 6 произведем расчеты:

1)

8

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

j=1 x_jЄS

7

∑с_j=1616;

j=1

7

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

x_jЄS j=1

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

8

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

j=2 x_jЄS

7

∑с_j=1516;

j=2

7

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

x_jЄS j=2

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

2)

8

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

j=2 x_jЄS

7

∑с_j=1515;

j=2

7

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

xjЄS j=2

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

8

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

j=3 xjЄS

7

∑с_j=1315;

j=3

7

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

xjЄS j=3

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

3)

8

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

j=3 xjЄS

7

∑с_j=1313;

j=3

7

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

xjЄS j=3

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

8

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

j=4 xjЄS

7

∑с_j=1213;

j=4

7

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

xjЄS j=4

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

4)

8

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

j=4 xjЄS

7

∑с_j=1212;