Нахождение опорного плана транспортной задачи
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 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
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