Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лабораторна 5
Інформація про навчальний заклад
ВУЗ:
Вінницькій національний технічний університет
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
ФІТКІ
Кафедра:
компютерні науки
Інформація про роботу
Рік:
2019
Тип роботи:
Лабораторна робота
Предмет:
ммдо
Група:
КН 217
Варіант:
7 8
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти, науки, молоді та спорту
Вінницький національний технічний університет
Кафедра комп’ютерних наук
Лабораторна робота №5
З дисципліни «Математичні методи дослідження операцій»
Тема: Розробка алгоритму і програми для розв'язування задач цілочисельного лінійного програмування методом Гоморі
Мета: набути практичних навичок розв'язування задач цілочисельного лінійного програмування методом Гоморі та його програмної реалізації.
Хід роботи
Згідно з заданим варіантом практично виконати розв'язування задач цілочисельного лінійного програмування методом Гоморі (7-8)
/
Розробити алгоритм та програму, що реалізує цей метод
/
Рисунок 1
Блок-схема алгоритму розв’язування ЦЛП методом Гоморі.
Практичне рішення приведено тут:
Для тестування програми були введені дані з практичного завдання, результати виконання програми наведені далі:
/
Рисунок 2 – Результати тестування програми
/
Рисунок 3 – Результати тестування програми
/
Рисунок 4 – Результати тестування програми
/
Рисунок 5 – Результати тестування програми
/
Рисунок 6 – Результати тестування програми
/
Рисунок 7 – Результати тестування програми
/
Рисунок 8 – Результати тестування програми
Висновок: У ході виконання даної роботи, були набуті практичні навички розробки ЦЛП програми методом Гоморі. Було практично розв’язано завдання методом Гоморі . При тестуванні програми використовувалась задача з практичного завдання – відповіді зійшлись, отже програма працює правильно.
Додаток 1 – Інструкція користувача
Запустити програму gomory.exe;
Вибрати вверху файл:
/
Вибрати нова задача і ввести необхідну к-ть обмежень і натиснути ОК
/
Ввести дані в відповідні поля
/
- приклад
/
– остача прикладу
/
– функція F = 3x1+3x2->max
– символ рівності
– привести до макс./мін.
Додаток 2 – Лістинг програми
Unit1;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, ComCtrls, Grids, Spin, ExtCtrls, jpeg, XPMan;= class(TForm): TStringGrid;: TSpinEdit;: TLabel;: TStringGrid;: TSpinEdit;: TLabel;: TButton;: TStringGrid;: TButton;: TRadioGroup;: TLabel;: TButton;: TSpinEdit;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TGroupBox;: TLabel;: TLabel;_str: TStringGrid;: TButton;: TXPManifest;: TLabel;SpinEdit1Change(Sender: TObject);SpinEdit2Change(Sender: TObject);FormCreate(Sender: TObject);Button2Click(Sender: TObject);Button1Click(Sender: TObject);Button3Click(Sender: TObject);ChelevayaKeyPress(Sender: TObject; var Key: Char);Button4Click(Sender: TObject);
{ Private declarations }
{ Public declarations };: TForm1;,j,str_um,stolb_um,minmax_zn:Integer;_za:real;Math;
{$R *.dfm}
procedure TForm1.SpinEdit1Change(Sender: TObject);REshenie doi:=0 to colcount-1 doj:=0 to rowcount-1 do[i,j]:='';StringGrid1 doi:=0 to colcount-1 doj:=1 to rowcount-1 do[i,j]:='';Chelevaya doi:=0 to colcount-1 doj:=1 to rowcount-1 do[i,j]:='';.Cells[0,1]:='Ci';.Cells[1,1]:='Áï';.ColCount:=SpinEdit1.Value;.ColCount:=SpinEdit1.Value+SpinEdit2.Value+3;.ColCount:=SpinEdit1.Value+2;.Cells[SpinEdit1.Value-1,0]:='X'+IntToStr(SpinEdit1.Value);.Cells[SpinEdit1.Value-1,0]:='X'+IntToStr(SpinEdit1.Value);.Cells[SpinEdit1.Value,0]:='Çíàê';.Cells[SpinEdit1.Value+1,0]:='#';_um:=REshenie.RowCount;_um:=REshenie.ColCount;;TForm1.SpinEdit2Change(Sender: TObject);REshenie doi:=0 to colcount-1 doj:=0 to rowcount-1 do[i,j]:='';.Cells[0,1]:='Ci';.Cells[1,1]:='Áï';.RowCount:=SpinEdit2.Value+1;.ColCount:=SpinEdit1.Value+SpinEdit2.Value+3;.RowCount:=SpinEdit2.Value+3;_um:=REshenie.RowCount;_um:=REshenie.ColCount;;TForm1.FormCreate(Sender: TObject);_um:=REshenie.RowCount;_um:=REshenie.ColCount;.Cells[0,0]:='X1';.Cells [1,0]:='X2';.Cells[0,0]:='X1';.Cells[1,0]:='X2';.Cells[2,0]:='Çíàê';.Cells [3,0]:='#';.Cells[0,1]:='Ci';.Cells[1,1]:='Áï';;TForm1.Button2Click(Sender: TObject);stolb,strok:Integer;,d:real;.Visible:=true;.RowCount:=str_um;.ColCount:=stolb_um;
with REshenie doi:=0 to colcount-1 doj:=0 to rowcount-1 do[i,j]:='';i:=2 to REshenie.ColCount-1 doj:=0 to REshenie.RowCount-1 do.Cells[i,j]:='0';.Cells[0,1]:='Ci';.Cells[1,1]:='Áï';i:=2 to REshenie.RowCount-2 do.Cells[0,i]:='0';strok:=1 to SpinEdit2.Value+2 dostolb:=2 to SpinEdit1.Value+1 do.Cells[stolb,strok]:=StringGrid1.Cells[stolb-2,strok-1];;stolb:=2 to SpinEdit1.Value+1 do.Cells[stolb,0]:=Chelevaya.Cells[stolb-2,1];;strok:=1 to SpinEdit2.Value do.Cells[REshenie.ColCount-1,strok+1]:=StringGrid1.Cells[StringGrid1.colcount-1,strok];strok:=1 to SpinEdit2.Value do.Cells[1,strok+1]:='X'+inttostr(SpinEdit1.Value+strok);.Cells[strok+SpinEdit1.Value+1,1]:='X'+inttostr(SpinEdit1.Value+strok);;strok:=2 to SpinEdit2.Value+1 doStringGrid1.Cells[SpinEdit1.Value,strok-1]='<=' then.Cells[strok+SpinEdit1.Value,strok]:='+1';StringGrid1.Cells[SpinEdit1.Value,strok-1]='>=' then.Cells[strok+SpinEdit1.Value,strok]:='-1';;
// Расчёт оценок
for stolb:=2 to REshenie.ColCount-1 doj:=2 to REshenie.RowCount-2 do:=StrTofloat( REshenie.cells[stolb,j])*StrTofloat(REshenie.Cells[0,j]);:=s+d;;.Cells[stolb,REshenie.RowCount-1]:=FloatToStr(s-StrTofloat(REshenie.Cells[stolb,0]));;TForm1.Button1Click(Sender: TObject);itera,kluch_stolb,kluch_strok:integer;,min2,d,z,f1,f2,f3,f4,s:real;: integer;_of_min:array[1..10]of real;_of_zna:array[1..10,1..10]of real;
chet:=0;
//Количество итераций
for itera:=1 to SpinEdit3.Value doRadioGroup1.ItemIndex=1 then:=99;
//Нахождение ключ столбца
for i:=1 to REshenie.ColCount-3 doStrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1])<min1 then:=StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1]);_stolb:=i+1;;;i:=1 to REshenie.RowCount-3 doREshenie.Cells[kluch_stolb,i+1]<>'0' then_of_min[i]:=strtofloat(REshenie.Cells[REshenie.Colcount-1,i+1]) /strtofloat(REshenie.Cells[kluch_stolb,i+1])_of_min[i]:=0;;
//Поиск минимальной строки
min2:=9999;
for i:=1 to REshenie.RowCount-3 do(mas_of_min[i]<min2) and (mas_of_min[i]>0) then:=mas_of_min[i];_strok:=i+1;;:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);
//Замена базиса
REshenie.Cells[0,kluch_strok]:=REshenie.Cells[kluch_stolb,0];.Cells[1,kluch_strok]:=REshenie.Cells[kluch_stolb,1];
//Правило прямоугольника
for i:=2 to REshenie.RowCount-2 doj:=2 to REshenie.ColCount-1 doi<>kluch_strok thenj<>kluch_stolb then:=StrToFloat(REshenie.Cells[j,i]);:=StrToFloat(REshenie.Cells[j,kluch_strok]);:=StrToFloat(REshenie.Cells[kluch_stolb,i]);_of_zna[j,i]:=((f1*f4)-(f2*f3))/f4;;;;
//Нули в столбцеi:=2 to REshenie.RowCount-1 do.Cells[kluch_stolb,i]:='0';;.Cells[kluch_stolb,kluch_strok]:=floattostr(f4);
//Строки делятся на ключевой элемент
for i:=2 to REshenie.ColCount-1 do.Cells[i,kluch_strok]:=floattostr(strtofloat(REshenie.Cells[i,kluch_strok])/f4);;:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);i:=2 to REshenie.RowCount-2 doj:=2 to REshenie.ColCount-1 doi<>kluch_strok thenj<>kluch_stolb then.Cells[j,i]:=FloatToStr(mas_of_zna[j,i]);;;;
// Подсчёт оценок
for i:=2 to REshenie.ColCount-1 doj:=2 to REshenie.RowCount-2 do:=StrTofloat( REshenie.cells[i,j])*StrTofloat(REshenie.Cells[0,j]);:=s+d;;.Cells[i,REshenie.RowCount-1]:=FloatToStr(s-StrToInt(REshenie.Cells[i,0]));:=0;;i:=2 to REshenie.ColCount-2 doStrToFloat( REshenie.Cells[i,REshenie.RowCount-1])>= 0 then:=chet+1
else
end;
//Проверка на оптимальность
if chet=REshenie.ColCount-3 then('Решение Найдено’,mtWarning,[mbOK],1);.Visible:=true;.Visible:=false;;elseitera=SpinEdit3.Value then(Решение не найдено, увеличьте количество итераций или отсутствует '+RadioGroup1.items[RadioGroup1.itemindex]+' функции',mtWarning,[mbOK],1);.Visible:=false;.Visible:=false;;:=0;:=-99;
//Накождение ключ столбца
for i:=1 to REshenie.ColCount-3 doStrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1])>min1 then:=StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1]);_stolb:=i+1;;;i:=1 to REshenie.RowCount-3 doREshenie.Cells[kluch_stolb,i+1]<>'0' then_of_min[i]:=strtofloat(REshenie.Cells[REshenie.Colcount-1,i+1]) /strtofloat(REshenie.Cells[kluch_stolb,i+1])_of_min[i]:=0;;
//Поиск Минимальной строки
min2:=9999;
for i:=1 to REshenie.RowCount-3 do(mas_of_min[i]<min2) and (mas_of_min[i]>0) then:=mas_of_min[i];_strok:=i+1;;:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);
//Замена базиса
REshenie.Cells[0,kluch_strok]:=REshenie.Cells[kluch_stolb,0];.Cells[1,kluch_strok]:=REshenie.Cells[kluch_stolb,1];
//Правило прямоугольника
for i:=2 to REshenie.RowCount-2 doj:=2 to REshenie.ColCount-1 doi<>kluch_strok thenj<>kluch_stolb then:=StrToFloat(REshenie.Cells[j,i]);:=StrToFloat(REshenie.Cells[j,kluch_strok]);:=StrToFloat(REshenie.Cells[kluch_stolb,i]);_of_zna[j,i]:=((f1*f4)-(f2*f3))/f4;;;;
//Нули в столбцеi:=2 to REshenie.RowCount-1 do.Cells[kluch_stolb,i]:='0';;.Cells[kluch_stolb,kluch_strok]:=floattostr(f4);
//Строка делится на ключевой элемент
for i:=2 to REshenie.ColCount-1 do.Cells[i,kluch_strok]:=floattostr(strtofloat(REshenie.Cells[i,kluch_strok])/f4);;:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);i:=2 to REshenie.RowCount-2 doj:=2 to REshenie.ColCount-1 doi<>kluch_strok thenj<>kluch_stolb then.Cells[j,i]:=FloatToStr(mas_of_zna[j,i]);;;;
// Подсчёт оценок
for i:=2 to REshenie.ColCount-1 doj:=2 to REshenie.RowCount-2 do:=StrTofloat( REshenie.cells[i,j])*StrTofloat(REshenie.Cells[0,j]);:=s+d;;.Cells[i,REshenie.RowCount-1]:=FloatToStr(s-StrToInt(REshenie.Cells[i,0]));:=0;;i:=2 to REshenie.ColCount-2 doStrToFloat( REshenie.Cells[i,REshenie.RowCount-1])<= 0 then:=chet+1
else
end;
//Проверка на оптимальность
if chet=REshenie.ColCount-3 then('Решение найдено',mtWarning,[mbOK],1);.Visible:=true;.Visible:=false;;elseitera=SpinEdit3.Value then(Решение не найдено, увеличьте количество итераций или отсутствует '+RadioGroup1.items[RadioGroup1.itemindex]+' функции',mtWarning,[mbOK],1);.Visible:=false;.Visible:=false;;:=0;;;.Caption:=IntToStr(kluch_stolb);.Caption:=IntToStr(kluch_strok);;TForm1.Button3Click(Sender: TObject);,finals;,f1,f2,f3,f4,s,d:real;_of_zna:array[1..10,1..10]of real;_of_min:array[1..10]of real;_drob_n,kluch_stolb,kluch_strok:Integer;_of_q:array[1..10]of real;,max,max_drob_z,x,min2,m,min1:real;:=-9999;
//i:=2 to REshenie.rowCount-2 do(frac(StrToFloat(REshenie.Cells[REshenie.colcount-1,i]))<>0) and (frac(StrToFloat( REshenie.Cells[REshenie.ColCount-1,i]))>max) then:=frac(StrToFloat(REshenie.Cells[REshenie.colcount-1,i]));_drob_n:=i;_drob_z:=StrToFloat(REshenie.Cells[REshenie.colcount-1,i]);;
finals:
//Проверка на наличие дроби
if (max_drob_z<>0) or (frac(StrToFloat(REshenie.Cells[REshenie.ColCount-1,REshenie.RowCount-1]))<>0)then.Caption:=FloatToStr(max_drob_z);.Caption:=IntToStr(REshenie.ColCount-1);.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]));_of_q[REshenie.ColCount-1]:=1;i:=2 to REshenie.ColCount-2 do(StrToFloat(REshenie.Cells[i,max_drob_n])<0) and (frac(StrToFloat(REshenie.Cells[i,max_drob_n]))<>0) then_of_q[i]:=StrToFloat(REshenie.Cells[i,max_drob_n])-Trunc(StrToFloat(REshenie.Cells[i,max_drob_n])-1)_of_q[i]:=StrToFloat(REshenie.Cells[i,max_drob_n])-Trunc(StrToFloat(REshenie.Cells[i,max_drob_n]));;
//Вывод ключевых
for i:=2 to REshenie.ColCount do_str.Cells[i-2,0]:=floattostr( mas_of_q[i]);;.Caption:=FloatToStr(mas_of_q[1]);
//Добавление новой строки.RowCount:=REshenie.RowCount+1;
//перенос оценок на последнюю строкуi:=2 to REshenie.ColCount do.Cells[i,REshenie.RowCount-1]:=REshenie.Cells[i,REshenie.RowCount-2];.Cells[i,REshenie.RowCount-2]:='';;.Cells[1,REshenie.RowCount-2]:='X'+IntToStr(strtoint(REshenie.Cells[REshenie.colcount-2,1][2])+1);.Cells[0,REshenie.RowCount-2]:='0';
//добавление нового столбца.ColCount:=REshenie.COlCount+1;
//перенос на последний столбец
for i:=2 to REshenie.rowCount do.Cells[REshenie.COlCount-1,i]:=REshenie.Cells[REshenie.colcount-2,i];.Cells[REshenie.COlCount-2,i]:='';;
//Добавление значений коофицента
REshenie.Cells[REshenie.ColCount-2,1]:=REshenie.Cells[1,REshenie.Rowcount-2];.Cells[REshenie.ColCount-2,0]:='0';
//Заполнение 0
for i:=2 to REshenie.RowCount-1 do.Cells[REshenie.ColCount-2,i]:='0';;
//Заполнение строки q1i:=2 to REshenie.ColCount-1 do(mas_of_q[i]<>0) and (mas_of_q[i]<>1) then.Cells[i,REshenie.RowCount-2]:='-'+FloatToStr(mas_of_q[i]).Cells[i,REshenie.RowCount-2]:=FloatToStr(mas_of_q[i]);;
//Знак - или +i:=2 to REshenie.ColCount-3 do(RadioGroup1.ItemIndex=1) and (REshenie.Cells[i,reshenie.rowcount-1][1]<>'-') and (StrToFloat(REshenie.Cells[i,reshenie.rowcount-1])>0) then.Cells[i,reshenie.rowcount-1]:='-'+REshenie.Cells[i,reshenie.rowcount-1];;
min1:=99;
//Нахождение ключ столбца для гомори
for i:=1 to REshenie.ColCount-3 do(StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-2]) <>0) thenStrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1])<>0 then(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:=StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1])/StrToFloat(REshenie.Cells[i+1,REshenie.rowcount-1]);_stolb:=i+1;;;i:=1 to REshenie.RowCount-3 doREshenie.Cells[kluch_stolb,i+1]<>'0' then_of_min[i]:=strtofloat(REshenie.Cells[REshenie.Colcount-1,i+1]) /strtofloat(REshenie.Cells[kluch_stolb,i+1])_of_min[i]:=0;;
//Поиск мин строки
min2:=9999;
for i:=1 to REshenie.RowCount-3 do(mas_of_min[i]<min2) and (mas_of_min[i]>0) then:=mas_of_min[i];_strok:=i+1;;:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);
//Замена базиса
REshenie.Cells[0,kluch_strok]:=REshenie.Cells[kluch_stolb,0];.Cells[1,kluch_strok]:=REshenie.Cells[kluch_stolb,1];
//Правило прямоугольника
for i:=2 to REshenie.RowCount-2 doj:=2 to REshenie.ColCount-1 doi<>kluch_strok thenj<>kluch_stolb then:=StrToFloat(REshenie.Cells[j,i]);:=StrToFloat(REshenie.Cells[j,kluch_strok]);:=StrToFloat(REshenie.Cells[kluch_stolb,i]);_of_zna[j,i]:=((f1*f4)-(f2*f3))/f4;;;;
//Нули в столбцеi:=2 to REshenie.RowCount-1 do.Cells[kluch_stolb,i]:='0';;.Cells[kluch_stolb,kluch_strok]:=floattostr(f4);
//Строка делится на ключевой элемент
for i:=2 to REshenie.ColCount-1 do.Cells[i,kluch_strok]:=floattostr(strtofloat(REshenie.Cells[i,kluch_strok])/f4);;:=StrToFloat(REshenie.Cells[kluch_stolb,kluch_strok]);i:=2 to REshenie.RowCount-2 doj:=2 to REshenie.ColCount-1 doi<>kluch_strok thenj<>kluch_stolb then.Cells[j,i]:=FloatToStr(mas_of_zna[j,i]);;;;
//Подсчёт оценок
for i:=2 to REshenie.ColCount-1 doj:=2 to REshenie.RowCount-2 do:=StrTofloat( REshenie.cells[i,j])*StrTofloat(REshenie.Cells[0,j]);:=x+m;;i=REshenie.ColCount-1 then.Cells[i,REshenie.RowCount-1]:=FloatToStr(x).Cells[i,REshenie.RowCount-1]:=FloatToStr(x-StrTofloat(REshenie.Cells[i,0]));:=0;;
//Округление
for j:=2 to REshenie.RowCount-1 do((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'))((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'))((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'))((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')).Cells[REshenie.Colcount-1,j]:=inttostr(round(StrToFloat(REshenie.Cells[REshenie.Colcount-1,j])));;.Caption:=FloatToStr(kluch_stolb);.Caption:=FloatToStr(kluch_strok);
else
begin
MessageDlg(Дробей в решении нет, следовательно ответ целочисленный’,mtWarning,[mbOK],1);
Button3.Visible:=false;i:=1 to Q_str.ColCount-1 do_str.Cells[i,0]:='';i:=1 to SpinEdit1.Value do_str.Cells[i-1,0]:='X'+IntToStr(i);;i:=2 to REshenie.RowCount-2 doj:=1 to SpinEdit1.Value doREshenie.Cells[1,i]='X'+IntToStr(j) then_str.Cells[j-1,1]:=REshenie.Cells[REshenie.colcount-1,i];;TForm1.ChelevayaKeyPress(Sender: TObject; var Key: Char);not (key in ['0'..'9',#8,'-','<','=','>','.',#13]) then key:=#0;;TForm1.Button4Click(Sender: TObject);.Cells[0,1]:='2';.Cells[1,1]:='-1';.Cells[0,1]:='-1';.Cells[0,2]:='1';.Cells[0,3]:='1';.Cells[1,1]:='2';.Cells[1,2]:='2';.Cells[1,3]:='-2';.Cells[2,1]:='<=';.Cells[2,2]:='<=';.Cells[2,3]:='<=';.Cells[3,1]:='2';.Cells[3,2]:='6';.Cells[3,3]:='4';
end;.
14.06.2020 12:06-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора