Xreferat.com » Рефераты по информатике и программированию » Нахождение опорного плана транспортной задачи

Нахождение опорного плана транспортной задачи

set_j:=[];

for j:=0 to n-1 do include(set_j,j);


repeat

// цикл по строкам

for i:= 0 to m-1 do

if i in set_i then

begin

// ищем первоначальный минимальный элемент в строке

for j:= 0 to n-1 do

if j in set_j then

begin

cmin:=c[i,j];

break

end;

// ищем 1-ое наименьшее значение в строке

for j:= 0 to n-1 do

Лист

Кп-км-п-44-2203-99

if j in set_j then

if c[i,j]<=cmin then

begin

cmin:=c[i,j];

SubRow[i,1]:=j

end;


cminprev:=cmin;

// ищем первоначальный минимальный элемент в строке

for j:= 0 to n-1 do

if (j in set_j) and (j<>SubRow[i,1]) then

begin

cminprev:=c[i,j];

break

end;

// ищем 2-ое наименьшее значение в строке

for j:= 0 to n-1 do

if (j in set_j) and (j<>SubRow[i,1]) then

if c[i,j]<=cminprev then

cminprev:=c[i,j];

// Вычисляем разность между двумя наименьшими

SubRow[i,0]:=cminprev-cmin;


end;

// цикл по столбцам

for j:= 0 to n-1 do

if j in set_j then

begin

// ищем первоначальный минимальный элемент в столбце

for i:= 0 to m-1 do

if i in set_i then

begin

cmin:=c[i,j];

break

end;

// ищем 1-ое наименьшее значение в столбце

for i:= 0 to m-1 do

if i in set_i then

if c[i,j]<=cmin then

begin

cmin:=c[i,j];

SubCol[j,1]:=i

end;


cminprev:=cmin;

// ищем первоначальный минимальный элемент в столбце

for i:= 0 to m-1 do

if (i in set_i) and (i<>SubCol[j,1]) then

begin

cminprev:=c[i,j];

break

end;

// ищем 2-ое наименьшее значение в столбце

for i:= 0 to m-1 do

if (i in set_i) and (i<>SubCol[j,1]) then

if c[i,j]<=cminprev then

cminprev:=c[i,j];

// Вычисляем разность между двумя наименьшими

SubCol[j,0]:=cminprev-cmin;

end;


Лист

Кп-км-п-44-2203-99

//отыскиваем максимальное значение в строке

// сперва находим начальный наибольший элемент


for i:= 0 to m-1 do

if i in set_i then

begin

SubRowMax:=Subrow[i,0];

break

end;

// Теперь просматриваем всю строку

for i:= 0 to m-1 do

if i in set_i then

if SubRow[i,0]>=SubRowMax then

begin

SubRowMax:=SubRow[i,0];

imax:=i

end;


//отыскиваем максимальное значение в строке

// сперва находим начальный наибольший элемент

for j:= 0 to n-1 do

if j in set_j then

begin

SubColMax:=SubCol[j,0];

break

end;

// Теперь просматриваем всю строку

for j:= 0 to n-1 do

if j in set_j then

if SubCol[j,0]>=SubColMax then

begin

SubColMax:=SubCol[j,0];

jmax:=j

end;

// сравниваем максимальное значение разности по строкам и столбцам

if SubRowMax>SubColMax then

begin

d[imax,SubRow[imax,1]]:=min(a[imax],b[SubRow[imax,1]]);

a[imax]:=a[imax]-d[imax,SubRow[imax,1]];

b[SubRow[imax,1]]:=b[SubRow[imax,1]]-d[imax,SubRow[imax,1]];


if a[imax]=0 then Exclude(set_i,imax);

if b[SubRow[imax,1]]=0 then

Exclude(set_j,SubRow[imax,1]);

z:=z+d[imax,SubRow[imax,1]]*c[imax,SubRow[imax,1]];

if set_i=[] then set_j:=[];

if set_j=[] then set_i:=[]

end

else

begin

d[SubCol[jmax,1],jmax]:=min(a[SubCol[jmax,1]],b[jmax]);

a[SubCol[jmax,1]]:=a[SubCol[jmax,1]]-d[SubCol[jmax,1],jmax];

b[jmax]:=b[jmax]-d[SubCol[jmax,1],jmax];


if a[SubCol[jmax,1]]=0 then Exclude(set_i,SubCol[jmax,1]);

if b[jmax]=0 then

Exclude(set_j,SubCol[jmax,1]);

z:=z+d[SubCol[jmax,1],jmax]*c[SubCol[jmax,1],jmax];

if set_i=[] then set_j:=[];

if set_j=[] then set_i:=[]

end

Лист

Кп-км-п-44-2203-99

until (set_i=[]) and (set_j = []);

ShowSolve

end;


procedure TwoWall;

var

RowMin,ColMin:integer;

i,j,jj,j0:integer;

imin,jmin:integer;

set_i,set_j:set of 0..255;


begin


set_i:=[];

for i:=0 to m-1 do include(set_i,i);


set_j:=[];

for j:=0 to n-1 do include(set_j,j);


repeat

// начинаем цикл по столбцам

for j:= 0 to n-1 do

if j in set_j then

begin

// находим начальный минимальный элемент строки

for i:= 0 to m-1 do

if i in set_i then

begin

RowMin:=c[i,j];

break

end;

// теперь просматриваем весь столбец

for i:=0 to m-1 do

if i in set_i then

if c[i,j]<=RowMin then

begin

RowMin:=c[i,j];

imin:=i

end;

// минимальный элемент в j-ом столбце найден

// проверяем , минимальный ли он в своей строке

j0:=j;

for jj:= 0 to n-1 do

if jj in set_j then

if c[imin,jj]< RowMin then

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: