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

Автор работы: Пользователь скрыл имя, 23 Июня 2013 в 23:07, курсовая работа

Краткое описание

Рассмотрим алгоритм решения задачи линейного целочисленного программирования этим методом.
Решаем задачу симплексным методом без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования. Если обнаруживается неразрешимость задачи, то и неразрешима задача целочисленного программирования.
Если среди компонент оптимального решения есть нецелые, то к ограничениям задачи добавляем новое ограничение, обладающее следующими свойствами:
- оно должно быть линейным;
- должно отсекать найденный оптимальный нецелочисленный план;
- не должно отсекать ни одного целочисленного плана.

Скачать полностью (306.58 Кб) Сколько стоит заказать работу?
Прикрепленные файлы: 1 файл

Курсовая матем методы.doc

— 507.00 Кб (Скачать документ)

StringGrid1.Cells[SpinEdit1.Value,0]:='Çíàê';

StringGrid1.Cells[SpinEdit1.Value+1,0]:='#';

str_um:=REshenie.RowCount;

stolb_um:=REshenie.ColCount;

end;

procedure TForm1.SpinEdit2Change(Sender: TObject);

begin

with REshenie do

for i:=0 to colcount-1 do

for j:=0 to rowcount-1 do

Cells[i,j]:='';

REshenie.Cells[0,1]:='Ci';

REshenie.Cells[1,1]:='Áï';

StringGrid1.RowCount:=SpinEdit2.Value+1;

REshenie.ColCount:=SpinEdit1.Value+SpinEdit2.Value+3;

REshenie.RowCount:=SpinEdit2.Value+3;

str_um:=REshenie.RowCount;

stolb_um:=REshenie.ColCount;

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

str_um:=REshenie.RowCount;

stolb_um:=REshenie.ColCount;

StringGrid1.Cells[0,0]:='X1';

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

Chelevaya.Cells[0,0]:='X1';

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

StringGrid1.Cells[2,0]:='Çíàê';

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

REshenie.Cells[0,1]:='Ci';

REshenie.Cells[1,1]:='Áï';

end;

procedure TForm1.Button2Click(Sender: TObject);

var stolb,strok:Integer;

s,d:real;

begin

Button1.Visible:=true;

REshenie.RowCount:=str_um;

REshenie.ColCount:=stolb_um;

with REshenie do

for i:=0 to colcount-1 do

for j:=0 to rowcount-1 do

Cells[i,j]:='';

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

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

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

REshenie.Cells[0,1]:='Ci';

REshenie.Cells[1,1]:='Áï';

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

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

for strok:=1 to SpinEdit2.Value+2 do

for stolb:=2 to SpinEdit1.Value+1 do

begin

REshenie.Cells[stolb,strok]:=StringGrid1.Cells[stolb-2,strok-1];

end;

for stolb:=2 to SpinEdit1.Value+1 do

begin

REshenie.Cells[stolb,0]:=Chelevaya.Cells[stolb-2,1];

end;

for strok:=1 to SpinEdit2.Value do

REshenie.Cells[REshenie.ColCount-1,strok+1]:=StringGrid1.Cells[StringGrid1.colcount-1,strok];

for strok:=1 to SpinEdit2.Value do

begin

REshenie.Cells[1,strok+1]:='X'+inttostr(SpinEdit1.Value+strok);

REshenie.Cells[strok+SpinEdit1.Value+1,1]:='X'+inttostr(SpinEdit1.Value+strok);

end;

for strok:=2 to SpinEdit2.Value+1 do

begin

if StringGrid1.Cells[SpinEdit1.Value,strok-1]='<=' then

REshenie.Cells[strok+SpinEdit1.Value,strok]:='+1';

if StringGrid1.Cells[SpinEdit1.Value,strok-1]='>=' then

REshenie.Cells[strok+SpinEdit1.Value,strok]:='-1';

end;

// Расчёт оценок

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

begin

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

begin

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

s:=s+d;

end;

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

end

end;

procedure TForm1.Button1Click(Sender: TObject);

var itera,kluch_stolb,kluch_strok:integer;

min1,min2,d,z,f1,f2,f3,f4,s:real;

chet: integer;

mas_of_min:array[1..10]of real;

mas_of_zna:array[1..10,1..10]of real;

begin

chet:=0;

//Количество итераций

for itera:=1 to SpinEdit3.Value do

begin

if RadioGroup1.ItemIndex=1 then

begin

min1:=99;

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

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

begin

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

begin

min1:=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

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

s:=s+d;

end;

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

s:=0;

end;

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

begin

if StrToFloat( REshenie.Cells[i,REshenie.RowCount-1])>= 0 then

chet:=chet+1

else

end;

//Проверка на  оптимальность

if chet=REshenie.ColCount-3 then

begin

MessageDlg('Решение Найдено’,mtWarning,[mbOK],1);

Button3.Visible:=true;

Button1.Visible:=false;

break;

end else

if itera=SpinEdit3.Value then

begin

MessageDlg(Решение не найдено, увеличьте количество итераций или отсутствует '+RadioGroup1.items[RadioGroup1.itemindex]+' функции',mtWarning,[mbOK],1);

Button1.Visible:=false;

Button3.Visible:=false;

end;

chet:=0;

end

else

begin

min1:=-99;

//Накождение  ключ столбца

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

begin

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

begin

min1:=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

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

s:=s+d;

end;

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

s:=0;

end;

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

begin

if StrToFloat( REshenie.Cells[i,REshenie.RowCount-1])<= 0 then

chet:=chet+1

else

end;

//Проверка на  оптимальность

if chet=REshenie.ColCount-3 then

begin

MessageDlg('Решение найдено',mtWarning,[mbOK],1);

Button3.Visible:=true;

Button1.Visible:=false;

break;

end else

if itera=SpinEdit3.Value then

begin

MessageDlg(Решение не найдено, увеличьте количество итераций или отсутствует '+RadioGroup1.items[RadioGroup1.itemindex]+' функции',mtWarning,[mbOK],1);

Button1.Visible:=false;

Button3.Visible:=false;

end;

chet:=0;

end;

end;

Label5.Caption:=IntToStr(kluch_stolb);

Label6.Caption:=IntToStr(kluch_strok);

end;

procedure TForm1.Button3Click(Sender: TObject);

label

fin,finals;

var

z,f1,f2,f3,f4,s,d:real;

mas_of_zna:array[1..10,1..10]of real;

mas_of_min:array[1..10]of real;

max_drob_n,kluch_stolb,kluch_strok:Integer;

mas_of_q:array[1..10]of real;

q,max,max_drob_z,x,min2,m,min1:real;

begin

max:=-9999;

//

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

If (frac(StrToFloat(REshenie.Cells[REshenie.colcount-1,i]))<>0) and (frac(StrToFloat( REshenie.Cells[REshenie.ColCount-1,i]))>max) then

begin

max:=frac(StrToFloat(REshenie.Cells[REshenie.colcount-1,i]));

max_drob_n:=i;

max_drob_z:=StrToFloat(REshenie.Cells[REshenie.colcount-1,i]);

end;

finals:

//Проверка на  наличие дроби

if (max_drob_z<>0) or (frac(StrToFloat(REshenie.Cells[REshenie.ColCount-1,REshenie.RowCount-1]))<>0)then

begin

Label9.Caption:=FloatToStr(max_drob_z);

Label5.Caption:=IntToStr(REshenie.ColCount-1);

Label6.Caption:=IntToStr(max_drob_n);

//Нахождение элементов дополнительного ограничения

mas_of_q[REshenie.ColCount]:=StrToFloat(REshenie.Cells[REshenie.ColCount-1,max_drob_n])-trunc(StrToFloat(REshenie.Cells[REshenie.ColCount-1,max_drob_n]));

mas_of_q[REshenie.ColCount-1]:=1;

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

begin

if (StrToFloat(REshenie.Cells[i,max_drob_n])<0) and (frac(StrToFloat(REshenie.Cells[i,max_drob_n]))<>0) then

mas_of_q[i]:=StrToFloat(REshenie.Cells[i,max_drob_n])-Trunc(StrToFloat(REshenie.Cells[i,max_drob_n])-1)

else

mas_of_q[i]:=StrToFloat(REshenie.Cells[i,max_drob_n])-Trunc(StrToFloat(REshenie.Cells[i,max_drob_n]));

end;

//Вывод ключевых

for i:=2 to REshenie.ColCount do

begin

Q_str.Cells[i-2,0]:=floattostr( mas_of_q[i]);

end;

Label10.Caption:=FloatToStr(mas_of_q[1]);

//Добавление новой строки

REshenie.RowCount:=REshenie.RowCount+1;

//перенос оценок на последнюю строку

for i:=2 to REshenie.ColCount do

begin

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

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

end;

REshenie.Cells[1,REshenie.RowCount-2]:='X'+IntToStr(strtoint(REshenie.Cells[REshenie.colcount-2,1][2])+1);

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

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