Выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ
∆ с = с - ∑ сj∙xj - ∑сj=16-1-2-13=0
xjЄS j=3
Hs(x3) = q1+q2+q3+q4+q5+q6+q7+h8∆ с = 0.61
8
∑сj=15>b1 - ∑ cj∙xj=16-1-2=13;
j=4 xjЄS
7
∑сj=12Ј13;
j=4
7
∆ с = с - ∑ сj∙xj - ∑сj=16-1-2-12=1
xjЄS j=4
Hs(x3) = q1+q2+q4+q5+q6+q7+h8∆ с = 0.5967
4)
8
∑сj=15>b1 - ∑ cj∙xj=16-1-2-1=12;
j=4 xjЄS
7
∑сj=12Ј12;
j=4
7
∆ с = с - ∑ сj∙xj - ∑сj=16-1-2-1-12=0
xjЄS j=4
Hs(x4) = q1+q2+q3+q4+q5+q6+q7+h8∆ с = 0.61
9
∑сj=17>b1 - ∑ cj∙xj=16-1-2-1=12;
j=5 xjЄS
8
∑сj=11Ј12;
j=5
8
∆ с = с - ∑ сj∙xj - ∑сj=16-1-2-1-11=1
xjЄS j=5
Hs(x4) = q1+q2+q3+q5+q6+q7+q8+h9∆ с = 0.56167
5)
8
∑сj=11>b1 - ∑ cj∙xj=16-1-2-1-4=8;
j=5 xjЄS
7
∑сj=8Ј8;
j=5
7
∆ с = с - ∑ сj∙xj - ∑сj=16-1-2-1-4-8=0
xjЄS j=5
Hs(x5) = q1+q2+q3+q4+q5+q6+q7+h8∆ с = 0.61
8
∑сj=9>b1 - ∑ cj∙xj=16-1-2-1-4=8;
j=6 xjЄS
7
∑сj=6Ј8;
j=6
7
∆ с = с - ∑ сj∙xj - ∑сj=16-1-2-1-4-6=2
xjЄS j=6
Hs(x5) = q1+q2+q3+q4+q6+q7+h8∆ с = 0.5934
6)
8
∑сj=9>b1 - ∑ cj∙xj=16-1-2-1-4-2=6;
j=6 xjЄS
7
∑сj=6Ј6;
j=6
7
∆ с = с - ∑ сj∙xj - ∑сj=16-1-2-1-4-2-6=0
xjЄS j=6
Hs(x6) = q1+q2+q3+q4+q5+q6+q7+h8∆ с = 0.61
9
∑сj=10>b1 - ∑ cj∙xj=16-1-2-1-4-2=6;
j=7 xjЄS
8
∑сj=4Ј6;
j=7
7
∆ с = с - ∑ сj∙xj - ∑сj=16-1-2-1-4-2-4=2
xjЄS j=6
Hs(x6) = q1+q2+q3+q4+q5+q7+q8+h9∆ с = 0.56334
7) Cs = ∑ cj∙xj, проверяем условие С-Сs. Если с (xj)> С-Сs, то эти
xjЄS
элементы вводятся в множество Es.
Es = {x8,x9,x10}
с7=1>b1 - ∑ cj∙xj=16-1-2-1-4-2-5=1;
xjЄS
с7=1Ј1;
Условие не выполняется.
8) Ls = q1+q2+q3+q4+q5+q6+q7 = 0.61
Ls принимается в качестве приближенного решения L0. Так как все вершины дерева, для которых выполняется условие HsЈ L0, из дальнейшего рассмотрения исключаются, то процесс расчета прекращается.
Таблица 6
|
|
S | Es | Gs | Hs | xr | Hs(xr) | Hs(xr) | L0 |
| 1 | Ж | Ж | 1…10 | 0.61 | x1 | 0.61 | 0.5767 | |
| 2 | x1 | Ж | 2…10 | 0.61 | x2 | 0.61 | 0.5734 | |
| 3 | x1,x2 | Ж | 3…10 | 0.61 | x3 | 0.61 | 0.5967 | |
| 4 | x1,x2,x3 | Ж | 4…10 | 0.61 | x4 | 0.61 | 0.56167 | |
| 5 | x1,x2,x3,x4 | Ж | 5…10 | 0.61 | x5 | 0.61 | 0.5934 | |
| 6 | x1,x2,x3,x4,x5 | Ж | 6…10 | 0.61 | x6 | 0.61 | 0.56334 | |
| 7 | x1,x2,x3,x4,x5,x6 | 8,9,10 | 7 | 0.61 | x7 | 0.61 | 0.56334 | |
| 8 | x1,x2,x3,x4,x5,x6,x7 | 8,9,10 | Ж | - | - | - | - | 0.61 |
Для контроля системы необходимо использовать следующие параметры контроля: x1,x2,x3,x4,x5,x6,x7.
Перейдем на старую нумерацию элементов и построим дерево возможных вариантов решения. Оно представлено на рис.1. Около каждой вершины указана верхняя граница решения. Так как все эти оценки не превышают величины 0,61, то, следовательно, полученное решение L0 = 0,61 является оптимальным. Таким образом необходимо использовать следующие параметры контроля: x9,x4,x10,x3,x7,x1,x2.















![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()
![]()

Листинг программы
program vetvi;
const
maxmatrix=1000;
maxsize=200;
type linear=array[1..10000] of integer;
label skip;
var matrix:array[1..1000] of pointer;
n:integer;
sizeofm:word;
q,w,e,r:integer;
start_m:integer;
sm:^linear;
bestx,besty:integer;
bz:integer;
ochered:array[1..1000] of
record
id:integer;
ocenka:integer;
end;
nochered:integer;
workm,workc:integer;
leftm,rightm:integer;
first,last:integer;
best:integer;
bestmatr:array[1..maxsize] of integer;
bestmatr1:array[1..maxsize] of integer;
curr:integer;
procedure swapo(a,b:integer);
begin
ochered[1000]:=ochered[a];
ochered[a]:=ochered[b];
ochered[b]:=ochered[1000];
end;
procedure addochered(id,ocenka:integer);
var
curr:integer;
begin
inc(nochered);
ochered[nochered].id:=id;
ochered[nochered].ocenka:=ocenka;
{Uravnoveshivanie ocheredi}
curr:=nochered;
while true do
begin
if curr=1 then break;
if ochered[curr].ocenka< ochered[curr div 2].ocenka
then
begin
swapo(curr,curr div 2);
curr:=curr div 2;
end
else break;
end;
end;
procedure getochered(var id,ocenka:integer);
var
curr:integer;
begin
id:=ochered[1].id;
ocenka:=ochered[1].ocenka;
ochered[1]:=ochered[nochered];
dec(nochered);
curr:=1;
while true do
begin
if (curr*2+1> nochered) then break;
if (ochered[curr*2].ocenka< ochered[curr].ocenka) or
(ochered[curr*2+1].ocenka<ochered[curr].ocenka) then
begin
if ochered[curr*2].ocenka> ochered[curr*2+1].ocenka
then
begin
swapo(curr*2+1,curr);
curr:=curr*2+1;
end
else
begin
swapo(curr*2,curr);
curr:=curr*2;
end;
end else break;
end;
end;
function getid:integer;
var q:integer;
qw:^linear;
begin
if memavail<10000 then
begin
q:=ochered[nochered].id;
{ exit;}
end else
begin
for q:=1 to maxmatrix do
if matrix[q]=nil then break;
getmem(matrix[q],sizeofm);
end;
qw:=matrix[q];
fillchar(qw^,sizeofm,0);
getid:=q;
end;
procedure freeid(id:integer);
begin
freemem(matrix[id],sizeofm);
matrix[id]:=nil;
end;
function i(x,y:integer):integer;
begin
i:=(y-1)*n+x+1;
end;
function simplize(id:integer):integer;
var
q,w:integer;
t:^linear;
add:integer;
min:integer;
begin
t:=matrix[id];
add:=0;
for q:=1 to n do
begin
min:=maxint;
for w:=1 to n do
if t^[i(w,q)]< >-1 then
if min> t^[i(w,q)] then min:=t^[i(w,q)];
if min<>0 then
for w:=1 to n do
if t^[i(w,q)]< >-1 then
dec(t^[i(w,q)],min);
if min>32000 then min:=0;
inc(add,min);
end;
for q:=1 to n do
begin
min:=maxint;
for w:=1 to n do
if t^[i(q,w)]< >-1 then
if min> t^[i(q,w)] then min:=t^[i(q,w)];
if min<>0 then
for w:=1 to n do
if t^[i(q,w)]< >-1 then
dec(t^[i(q,w)],min);
if min>32000 then min:=0;
inc(add,min);
end;
simplize:=add;
end;
function bestziro(id:integer):integer;
var
t:^linear;
q,w,e,x,y:integer;
min1,min2:integer;
l1,l2:array[1..maxsize] of integer;
begin
t:=matrix[id];
fillchar(l1,sizeof(l1),0);
fillchar(l2,sizeof(l2),0);
for q:=1 to n do
begin
min1:=maxint;min2:=maxint;
for w:=1 to n do
if t^[i(w,q)]< >-1 then
begin
if min2> t^[i(w,q)] then min2:=t^[i(w,q)];
if min1> min2 then
begin
e:=min1;
min1:=min2;
min2:=e;