Решение задач целочисленного программирования методом Гомори

//добавление нового столбца

REshenie.ColCount:=REshenie.COlCount+1;

//перенос на последний столбец

for i:=2 to REshenie.rowCount do

begin

REshenie.Cells[REshenie.COlCount-1,i]:=REshenie.Cells[REshenie.colcount-2,i];

REshenie.Cells[REshenie.COlCount-2,i]:='';

end;

//Добавление значений коофицента

REshenie.Cells[REshenie.ColCount-2,1]:=REshenie.Cells[1,REshenie.Rowcount-2];

REshenie.Cells[REshenie.ColCount-2,0]:='0';

//Заполнение 0

for i:=2 to REshenie.RowCount-1 do

begin

REshenie.Cells[REshenie.ColCount-2,i]:='0';

end;

//Заполнение строки q1

for i:=2 to REshenie.ColCount-1 do

begin

if (mas_of_q[i]<>0) and (mas_of_q[i]<>1) then

REshenie.Cells[i,REshenie.RowCount-2]:='-'+FloatToStr(mas_of_q[i])

else

REshenie.Cells[i,REshenie.RowCount-2]:=FloatToStr(mas_of_q[i]);

end;

//Знак - или +

for i:=2 to REshenie.ColCount-3 do

begin

if (RadioGroup1.ItemIndex=1) and (REshenie.Cells[i,reshenie.rowcount-1][1]<>'-') and (StrToFloat(REshenie.Cells[i,reshenie.rowcount-1])>0) then

REshenie.Cells[i,reshenie.rowcount-1]:='-'+REshenie.Cells[i,reshenie.rowcount-1];

end;

min1:=99;

//Нахождение  ключ столбца для гомори

for i:=1 to REshenie.ColCount-3 do

begin

if (StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-2]) <>0) then

if StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1])<>0 then

if (StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1])/StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-2]) <min1 ) and (StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1]) <>0) then

begin

min1:=StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1])/StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1]);

kluch_stolb:=i+1;

end;

end;

for i:=1 to REshenie.RowCount-3 do

begin

if REshenie.Cells[kluch_stolb,i+1]<>'0' then

mas_of_min[i]:=strtofloat(REshenie.Cells[REshenie.Colcount-1,i+1]) /strtofloat(REshenie.Cells[kluch_stolb,i+1])

else

mas_of_min[i]:=0;

end;

//Поиск мин  строки

min2:=9999;

for i:=1 to REshenie.RowCount-3 do

if (mas_of_min[i]<min2) and (mas_of_min[i]>0) then

begin

min2:=mas_of_min[i];

kluch_strok:=i+1;

end;

f4:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);

//Замена базиса

REshenie.Cells[0,kluch_strok]:=REshenie.Cells[kluch_stolb,0];

REshenie.Cells[1,kluch_strok]:=REshenie.Cells[kluch_stolb,1];

//Правило прямоугольника

for i:=2 to REshenie.RowCount-2 do

begin

for j:=2 to REshenie.ColCount-1 do

begin

if i<>kluch_strok then

if j<>kluch_stolb then

begin

f1:=StrToFloat(REshenie.Cells[j,i]);

f2:=StrToFloat(REshenie.Cells[j,kluch_strok]);

f3:=StrToFloat(REshenie.Cells[kluch_stolb,i]);

mas_of_zna[j,i]:=((f1*f4)-(f2*f3))/f4;

end;

end;

end;

//Нули в столбце

for i:=2 to REshenie.RowCount-1 do

begin

REshenie.Cells[kluch_stolb,i]:='0';

end;

REshenie.Cells[kluch_stolb,kluch_strok]:=floattostr(f4);

//Строка делится на ключевой элемент

for i:=2 to REshenie.ColCount-1 do

begin

REshenie.Cells[i,kluch_strok]:=floattostr(strtofloat(REshenie.Cells[i,kluch_strok])/f4);

end;

z:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);

for i:=2 to REshenie.RowCount-2 do

begin

for j:=2 to REshenie.ColCount-1 do

begin

if i<>kluch_strok then

if j<>kluch_stolb then

begin

REshenie.Cells[j,i]:=FloatToStr(mas_of_zna[j,i]);

end;

end;

end;

//Подсчёт оценок

for i:=2 to REshenie.ColCount-1 do

begin

for j:=2 to REshenie.RowCount-2 do

begin

m:=StrTofloat( REshenie.cells[i,j])*StrTofloat(REshenie.Cells[0,j]);

x:=x+m;

end;

if i=REshenie.ColCount-1 then

REshenie.Cells[i,REshenie.RowCount-1]:=FloatToStr(x)

else

REshenie.Cells[i,REshenie.RowCount-1]:=FloatToStr(x-StrTofloat(REshenie.Cells[i,0]));

x:=0;

end;

//Округление

for j:=2 to REshenie.RowCount-1 do

begin

if ((REshenie.Cells[REshenie.Colcount-1,j][3]='0') and (REshenie.Cells[REshenie.Colcount-1,j][4]='0') and (REshenie.Cells[REshenie.Colcount-1,j][5]='0'))

or ((REshenie.Cells[REshenie.Colcount-1,j][1]='-') and (REshenie.Cells[REshenie.Colcount-1,j][4]='0') and (REshenie.Cells[REshenie.Colcount-1,j][5]='0') and (REshenie.Cells[REshenie.Colcount-1,j][6]='9'))

or ((REshenie.Cells[REshenie.Colcount-1,j][3]='9') and (REshenie.Cells[REshenie.Colcount-1,j][4]='9') and (REshenie.Cells[REshenie.Colcount-1,j][5]='9'))

or ((REshenie.Cells[REshenie.Colcount-1,j][1]='-') and (REshenie.Cells[REshenie.Colcount-1,j][4]='9') and (REshenie.Cells[REshenie.Colcount-1,j][5]='9') and (REshenie.Cells[REshenie.Colcount-1,j][6]='9'))

then

REshenie.Cells[REshenie.Colcount-1,j]:=inttostr(round(StrToFloat(REshenie.Cells[REshenie.Colcount-1,j])));

end;

Label5.Caption:=FloatToStr(kluch_stolb);

Label6.Caption:=FloatToStr(kluch_strok);

end

else

begin

MessageDlg(Дробей в решении нет, следовательно ответ целочисленный’,mtWarning,[mbOK],1);

Button3.Visible:=false;

for i:=1 to Q_str.ColCount-1 do

Q_str.Cells[i,0]:='';

For i:=1 to SpinEdit1.Value do

begin

Q_str.Cells[i-1,0]:='X'+IntToStr(i);

end;

for i:=2 to REshenie.RowCount-2 do

for j:=1 to SpinEdit1.Value do

if REshenie.Cells[1,i]='X'+IntToStr(j) then

Q_str.Cells[j-1,1]:=REshenie.Cells[REshenie.colcount-1,i];

end;

end

procedure TForm1.ChelevayaKeyPress(Sender: TObject; var Key: Char);

begin

if not (key in ['0'..'9',#8,'-','<','=','>','.',#13]) then key:=#0;

end;

procedure TForm1.Button4Click(Sender: TObject);

begin

Chelevaya.Cells[0,1]:='2';

Chelevaya.Cells[1,1]:='-1';

StringGrid1.Cells[0,1]:='-1';

StringGrid1.Cells[0,2]:='1';

StringGrid1.Cells[0,3]:='1';

StringGrid1.Cells[1,1]:='2';

StringGrid1.Cells[1,2]:='2';

StringGrid1.Cells[1,3]:='-2';

StringGrid1.Cells[2,1]:='<=';

StringGrid1.Cells[2,2]:='<=';

StringGrid1.Cells[2,3]:='<=';

StringGrid1.Cells[3,1]:='2';

StringGrid1.Cells[3,2]:='6';

StringGrid1.Cells[3,3]:='4';

end;

end.