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

2016-07-30СтудИзба

Описание файла

Документ из архива "Выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.

Онлайн просмотр документа "49529"

Текст 3 страницы из документа "49529"

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=1112;

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=88;

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=68;

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=66;

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=46;

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=11;

Условие не выполняется.

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.

0,61

0,5734

0,5967

0,56167

0,5934

0,56334

0,56334

0,61

0,61

0,61

0,61

0,61

0,61

0,61

0,5767


Рис.1


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

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

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;

end;

end;

if min1<>0 then min2:=0;

if min2>32000 then min2:=0;

l2[q]:=min2;

end;

for q:=1 to n do

begin

min1:=maxint;min2:=maxint;

for w:=1 to n do

if t^[i(q,w)]-1 then

begin

if min2> t^[i(q,w)] then min2:=t^[i(q,w)];

if min1> min2 then

begin

e:=min1;

min1:=min2;

min2:=e;

end;

end;

if min1<>0 then min2:=0;

if min2>32000 then min2:=0;

l1[q]:=min2;

end;

bz:=-32000;

bestx:=0;besty:=0;

for y:=n downto 1 do

for x:=1 to n do

if (t^[i(x,y)]=0) then

if l1[x]+l2[y]> bz then

begin

bestx:=x;

besty:=y;

bz:=l1[x]+l2[y];

end;

bestziro:=bz;

end;

begin

assign(input,'input.txt');

assign(output,'vetvi.out');

reset(input);

rewrite(output);

nochered:=0;

read(n);

sizeofm:=n*(n+2)*2+2;

start_m:=getid;

sm:=matrix[start_m];

for q:=1 to n do

for w:=1 to n do

read(sm^[i(w,q)]);

addochered(start_m,0);

{ ;

bestziro(start_m);}

{Sobstvenno reshenie}

best:=maxint;

while true do

begin

if nochered=0 then break;

getochered(workm,workc);

{process MATRIX}

inc(workc,simplize(workm));

if workc> best then goto skip;

sm:=matrix[workm];

if sm^[1]=n-1 then

begin

best:=workc;

for q:=1 to n do

begin

bestmatr [q]:=sm^[i(q,n+2)];

bestmatr1[q]:=sm^[i(q,n+1)];

end;

goto skip;

end;

q:=bestziro(workm);

if q=-32000 then goto skip;

{Pravaia vetka}

if(bestx=0) or (besty=0) then goto skip;

rightm:=getid;

move(matrix[workm]^,matrix[rightm]^,sizeofm);

sm:=matrix[rightm];

sm^[i(bestx,besty)]:=-1;

addochered(rightm,workc+q);

{Levaia vetka}

leftm:=getid;

move(matrix[workm]^,matrix[leftm]^,sizeofm);

sm:=matrix[leftm];

{Dobavliaetsia rebro iz bestx v besty}

inc(sm^[1]);

sm^[i(bestx,n+2)]:=besty;

sm^[i(besty,n+1)]:=bestx;

first:=bestx;last:=besty;

if sm^[1]n-1 then

begin

while true do

begin

if sm^[i(last,n+2)]=0 then break;

last:=sm^[i(last,n+2)];

end;

while true do

begin

if sm^[i(first,n+1)]=0 then break;

first:=sm^[i(first,n+1)];

end;

sm^[i(last,first)]:=-1;

sm^[i(first,last)]:=-1;

sm^[i(besty,bestx)]:=-1;

end;

for w:=1 to n do

begin

sm^[i(w,besty)]:=-1;

sm^[i(bestx,w)]:=-1;

end;

addochered(leftm,workc);

skip:

{Free Matrix}

freeid(workm);

end;

{ freeid(start_m);}

if best=maxint then

begin

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Нет! Мы не выполняем работы на заказ, однако Вы можете попросить что-то выложить в наших социальных сетях.
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
4125
Авторов
на СтудИзбе
667
Средний доход
с одного платного файла
Обучение Подробнее