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

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

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

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

Скачать полностью (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;

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;

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

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;

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

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;

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;

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

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;

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

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

Button1.Visible:=false;

Button3.Visible:=false;

end;

chet:=0;

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';

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

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

Прикрепленные файлы: 1 файл

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

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

Связанные документы

Метод решения логических задач

Симплексный метод решения задач

Методы решения задачи о рюкзаке

Методика решения задач по физике

Методы и алгоритмы решения задач компоновки

Решение задач динамического программирования

Решение задач линейного программирования в Excel

Решение задач оптимизации симплекс-методом

Численные методы решения инженерных задач на ЭВМ

Численные методы решения инженерных задач на ЭВМ

Решение задач линейного программирования в среде Maple

Решение краевой задачи методом конечных разностей

Похожие темы

Методы решения транспортных задач

Задачи программирование

Методы принятия решений