Решение задач целочисленного программирования методом Гомори
Курсовая работа, 23 Июня 2013, автор: пользователь скрыл имя
Краткое описание
Рассмотрим алгоритм решения задачи линейного целочисленного программирования этим методом.
Решаем задачу симплексным методом без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования. Если обнаруживается неразрешимость задачи, то и неразрешима задача целочисленного программирования.
Если среди компонент оптимального решения есть нецелые, то к ограничениям задачи добавляем новое ограничение, обладающее следующими свойствами:
- оно должно быть линейным;
- должно отсекать найденный оптимальный нецелочисленный план;
- не должно отсекать ни одного целочисленного плана.
Прикрепленные файлы: 1 файл
Курсовая матем методы.doc
— 507.00 Кб (Скачать документ)//добавление нового столбца
REshenie.ColCount:=REshenie.
//перенос на последний столбец
for i:=2 to REshenie.rowCount do
begin
REshenie.Cells[REshenie.
REshenie.Cells[REshenie.
end;
//Добавление значений коофицента
REshenie.Cells[REshenie.
REshenie.Cells[REshenie.
//Заполнение 0
for i:=2 to REshenie.RowCount-1 do
begin
REshenie.Cells[REshenie.
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.
else
REshenie.Cells[i,REshenie.
end;
//Знак - или +
for i:=2 to REshenie.ColCount-3 do
begin
if (RadioGroup1.ItemIndex=1) and (REshenie.Cells[i,reshenie.
REshenie.Cells[i,reshenie.
end;
min1:=99;
//Нахождение ключ столбца для гомори
for i:=1 to REshenie.ColCount-3 do
begin
if (StrToFloat(REshenie.Cells[i+
if StrToFloat(REshenie.Cells[i+1,
if (StrToFloat(REshenie.Cells[i+
begin
min1:=StrToFloat(REshenie.
kluch_stolb:=i+1;
end;
end;
for i:=1 to REshenie.RowCount-3 do
begin
if REshenie.Cells[kluch_stolb,i+
mas_of_min[i]:=strtofloat(
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[
//Замена базиса
REshenie.Cells[0,kluch_strok]:
REshenie.Cells[1,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
f1:=StrToFloat(REshenie.Cells[
f2:=StrToFloat(REshenie.Cells[
f3:=StrToFloat(REshenie.Cells[
mas_of_zna[j,i]:=((f1*f4)-(f2*
end;
end;
end;
//Нули в столбце
for i:=2 to REshenie.RowCount-1 do
begin
REshenie.Cells[kluch_stolb,i]:
end;
REshenie.Cells[kluch_stolb,
//Строка делится на ключевой элемент
for i:=2 to REshenie.ColCount-1 do
begin
REshenie.Cells[i,kluch_strok]:
end;
z:=StrToFloat(REshenie.Cells[
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]:=
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])*
x:=x+m;
end;
if i=REshenie.ColCount-1 then
REshenie.Cells[i,REshenie.RowC
else
REshenie.Cells[i,REshenie.
x:=0;
end;
//Округление
for j:=2 to REshenie.RowCount-1 do
begin
if ((REshenie.Cells[REshenie.
or ((REshenie.Cells[REshenie.
or ((REshenie.Cells[REshenie.
or ((REshenie.Cells[REshenie.
then
REshenie.Cells[REshenie.
end;
Label5.Caption:=FloatToStr(
Label6.Caption:=FloatToStr(
end
else
begin
MessageDlg(Дробей в решении нет, следовательно
ответ целочисленный’,mtWarning,[
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'+
end;
for i:=2 to REshenie.RowCount-2 do
for j:=1 to SpinEdit1.Value do
if REshenie.Cells[1,i]='X'+
Q_str.Cells[j-1,1]:=REshenie.
end;
end
procedure TForm1.ChelevayaKeyPress(
begin
if not (key in ['0'..'9',#8,'-','<','=','>','
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.