Лабораторна 5. Лабораторна робота з ммдо. Робота № 531798

Лабораторна 5

Інформація про навчальний заклад

ВУЗ:

Вінницькій національний технічний університет

Інститут:

Інститут комп’ютерних наук та інформаційних технологій

Факультет:

ФІТКІ

Кафедра:

компютерні науки

Інформація про роботу

Рік:

2020

Тип роботи:

Лабораторна робота

Предмет:

ммдо

Група:

КН 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;.

Лабораторна робота ммдо

Kazbek2013

14.06.2020 12:02

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись