l
|
24
|
25
|
26
|
27
|
28
|
29
|
30
|
31
|
32
|
33
|
34
|
35
|
36
|
37
|
38
|
39
|
40
|
f(l)
|
31
|
32
|
32
|
34
|
36
|
37
|
38
|
40
|
41
|
42
|
44
|
45
|
46
|
47
|
49
|
50
|
51
|
i(l)
|
1
|
1
|
1
|
1
|
1
|
1
|
3
|
1
|
1
|
2
|
4
|
1
|
1
|
1
|
1
|
1
|
1
|
Здесь и далее i(l) –
номер детали, которой соответствует максимальная оценка раскроя (сумма
стоимости всех деталей, входящих в раскрой) f(l) на шаге l.
Рассмотрим более подробно
последовательное заполнение таблицы на примере шагов
l = 7…14, 22.
1) l = 7
Выбираем первую деталь: i = 1. Длина детали 7, оценка 9.
Вычисляем остаток от
раскроя: 7 – 7 = 0. Поскольку остаток нулевой, то деталей, которые можно
добавить в раскрой, нет. Следовательно, максимальная оценка текущего раскроя
равна f = 9. Заносим в таблицу значения i(7) = 1, f(7) =
9 и переходим к
следующему шагу раскроя.
2) l = 8
Снова берём первую
деталь: i = 1. Длина детали 7, оценка 9.
Остаток: 8 – 7 = 1. Так
как деталей с такой длиной нет, максимальная оценка раскроя f = 9.
Заносим в таблицу i(8) = 1, f(8) = 9.
3) l = 9
i = 1, остаток 9 – 7 = 2, f = 9.
Заносим в таблицу i(9) = 1, f(9) =
9.
4) l = 10
i = 1, остаток 10 – 7 = 3, f = 9.
Заносим в таблицу i(10) = 1, f(10) = 9.
5) l = 11
i = 1, остаток 11 – 7 = 4, f = 9.
Учитывая, что в текущий
раскрой также уместится деталь i = 2 c длиной 11, получим: i = 2, остаток 11 – 11 = 0, f = 14.
Сравним оценки раскроев.
Выберем максимальную оценку (f = 14) и соответствующую ей деталь (i = 2).
Заносим в таблицу i(11) = 2, f(11) = 14.
6) l = 12
i = 1, остаток 12 – 7 = 5, f = 9.
i = 2, остаток 12 – 11 = 1, f = 14 (максимум)
Заносим в таблицу i(12) = 2, f(12) = 14.
7) l = 13
i = 1, остаток 13 – 7 = 6, f = 9.
i = 2, остаток 13 – 11 = 2, f = 14.
i = 3, остаток 13 – 13 = 0, f = 16 (максимум)
Заносим в таблицу i(13) = 3, f(13) = 16.
8) l = 14
i = 1, остаток 14 – 7 = 7.
Если мы видим, что длина
остатка раскроя больше или равна начальному значению длины раскроя (l0 = 7), т.е. в остаток может поместиться какая-либо
деталь (в данном случае с индексом i = 1), из таблицы считываем значение оценки раскроя f(i) при i,
равном значению остатка:
f
(7) = 9, тогда суммарная оценка раскроя f = f(7) +
9 = 9 + 9 = 18 (максимум)
i = 2, остаток 14 – 11 = 3, f = 14.
i = 3, остаток 14 – 13 = 1, f = 16.
Заносим в таблицу i(14) = 1, f(14) = 18.
…16) l = 22
i = 1, остаток 22 – 7 = 15, f (15) = 18, f = 18 + 9 = 27.
i = 2, остаток 22 – 11 = 11, f(11) = 14, f = 14 + 14 = 28 (максимум)
i = 3, остаток 22 – 13 = 9, f(9) = 9, f = 9 + 16 = 25.
i = 4, остаток 22 – 17 = 5, f = 22.
Заносим в таблицу i(22) = 2, f(22) = 28. и т.д., пока не достигнут конец
проката.
Выполняем обратный ход
(начинаем двигаться с конца таблицы):
1) l = 40
Из таблицы получаем
индекс детали, добавленной в текущий раскрой: i(40) = 1.
Находим длину детали с
полученным индексом: l1 = 7.
Вычисляем остаток
раскроя: 40 - 7 = 33. Этот остаток используем для следующего шага обратного хода.
2) l = 33
Индекс детали: i(33) = 2.
Длина детали: l2 = 11.
Остаток раскроя: 33 - 11
= 22.
3) l = 22
Индекс детали: i(22) = 2.
Длина детали: l2 = 11.
Остаток раскроя: 22 - 11
= 11.
4) l = 11
Индекс детали: i(11) = 2.
Длина детали: l2 = 11.
Остаток раскроя: 11 - 11
= 0. Обратный ход закончен.
Теперь подсчитываем
количество деталей каждого типа, которые мы получили при обратном ходе. Деталь
с индексом i = 1 встретилась 1 раз, деталь с индексом i = 2 встретилась 3 раза.
В вышеприведённой таблице
с результатами прямого хода выделены номера заготовок, которые при обратном
ходе последовательно включались в оптимальный раскрой.
Результат работы
программы (проверка
алгоритма):
Исходные данные
Длина проката: 40
Количество типов деталей:
4
Длина детали №1….: 7 Цена
детали №1….: 9
Длина детали №2….: 11 Цена
детали №2….: 14
Длина детали №3….: 13 Цена
детали №3….: 16
Длина детали №4….: 17 Цена
детали №4….: 22
Результат
Оптимальное количество
деталей каждого типа:
Деталь №1….: 1 шт.
Деталь №2….: 3 шт.
Деталь №3….: 0 шт.
Деталь №4….: 0 шт.
Оценка раскроя: 51
денежных единиц
Остаток материала: 0
Результаты ручного и
машинного вычислений совпадают, что говорит о работоспособности разработанного
алгоритма для ЭВМ.
Вывод
В данной работе
поставленная задача была решена с помощью сеточного метода. Как показала
проделанная работа, этот метод эффективен и прост для программной реализации на
ЭВМ. Результат, полученный с помощью этого метода, является оптимальным. В нём
реализуется целенаправленный перебор за конечное число шагов, в результате чего
находится рациональный раскрой с максимумом прибыли.
В работе были произведены
ручные вычисления и по ним проверена работа запрограммированного алгоритма на
ЭВМ. Разработанная программа и сеточный метод оптимизации раскроя достаточно
универсальны. Они могут применяться в различных отраслях промышленности при
массовом производстве, при этом в алгоритм следует вносить коррективы,
связанные с учетом технологии производства и применяемого оборудования.
Текст программы
unit Unit1;
interface
uses
Windows,
Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls,
Grids, ComCtrls, ExtCtrls;
type
//деталь
TDetail=record
l: integer;//длина
c: integer;//цена
end;
//запись раскроя
TCutRecord=record
l: integer;//длина
c: integer;//цена
i: integer;//индекс
детали
max_i:
integer;//максимальный индекс детали для текущей длины материала
end;
TForm_Main =
class(TForm)
GroupBox1:
TGroupBox;
Edit_MaterialLength:
TEdit;
Label_MaterialLength:
TLabel;
UpDown_MaterialLength:
TUpDown;
Label_DetailAmount:
TLabel;
UpDown_DetailAmount:
TUpDown;
Edit_DetailAmount:
TEdit;
StringGrid_In:
TStringGrid;
GroupBox2:
TGroupBox;
StringGrid_Out1:
TStringGrid;
Button_Calculate:
TButton;
Button_Exit:
TButton;
GroupBox3:
TGroupBox;
Image_Cut:
TImage;
Edit1: TEdit;
Edit2: TEdit;
Label1:
TLabel;
Label2:
TLabel;
Button1:
TButton;
procedure
Button_ExitClick(Sender: TObject);
procedure
Edit_DetailAmountChange(Sender: TObject);
procedure
FormCreate(Sender: TObject);
procedure
Edit_MaterialLengthChange(Sender: TObject);
procedure
Button_CalculateClick(Sender: TObject);
procedure
Button1Click(Sender: TObject);
private
{ Private
declarations }
public
{ Public
declarations }
end;
const
MAX_DETAIL_AMOUNT=10;//максимальное кол-во деталей
MAX_CUTRECORD_AMOUNT=10000;//максимальное кол-во записей
раскроя
MAX_MATERIAL_LENGTH=10000;//максимальная
длина материала
var
Form_Main:
TForm_Main;
materialLength:
integer;//длина материала
detailAmount:
integer;//кол-во деталей
details: array[1..MAX_DETAIL_AMOUNT]
of TDetail;//детали
x:
array[1..MAX_DETAIL_AMOUNT] of integer;//результат
implementation
uses Unit2;
{$R *.DFM}
//процедура вычисления
рационального раскроя
procedure
searchRationalCut(
materialLength:
integer;
detailAmount:
integer;
var details:
array of TDetail;
var x: array
of integer);
var
l0, l, i:
integer;
currCut:
TCutRecord;
maxCut:
TCutRecord;
cutRecords:
array[0..MAX_CUTRECORD_AMOUNT-1] of TCutRecord;
cutRecords1:
array[1..MAX_CUTRECORD_AMOUNT] of TCutRecord;
i1, j1:
integer;
begin
l0:=details[0].l;
for l:=l0 to
materialLength do
begin
currCut.l:=l;
currCut.c:=0;
currCut.i:=0;
currCut.max_i:=-1;
maxCut.l:=0;
maxCut.c:=0;
maxCut.i:=0;
maxCut.max_i:=0;
j1:=0;
while true do
begin
if
currCut.max_i=-1 then
begin
for i1:=0 to
detailAmount-1 do
begin
if
details[i1].l<=currCut.l then
begin
currCut.max_i:=i1;
currCut.i:=0;
end;
end;
end;
if
(currCut.max_i=-1) or (currCut.i>currCut.max_i) then
begin
if j1<>0
then
begin
if
currCut.c>maxCut.c then
begin
maxCut:=currCut;
end;
currCut:=cutRecords1[j1];
j1:=j1-1;
currCut.i:=currCut.i+1;
end
else
begin
break;
end;
end
else
begin
if
(currCut.l>=l0) and (currCut.l<l) then
begin
if
cutRecords[currCut.l].c+currCut.c>maxCut.c then
begin
maxCut:=cutRecords[currCut.l];
maxCut.c:=maxCut.c+currCut.c;
end;
currCut.i:=currCut.i+1;
continue;
end;
j1:=j1+1;
cutRecords1[j1]:=currCut;
currCut.l:=currCut.l-details[currCut.i].l;
currCut.c:=currCut.c+details[currCut.i].c;
currCut.max_i:=-1;
end;
end;
cutRecords[l]:=maxCut;
cutRecords[l].l:=l;
end;
for i:=0 to
detailAmount-1 do
begin
x[i]:=0;
end;
l:=materialLength;
while
l>=details[0].l do
begin
x[cutRecords[l].i]:=x[cutRecords[l].i]+1;
l:=l-details[cutRecords[l].i].l;
end;
end;
//ввод данных
пользователя из таблицы
procedure
updateData;
var
i: integer;
begin
materialLength:=strToInt(Form_Main.Edit_MaterialLength.Text);
detailAmount:=strToInt(Form_Main.Edit_DetailAmount.Text);
for i:=1 to
detailAmount do
begin
details[i].l:=strToInt(Form_Main.StringGrid_In.Cells[1,i]);
details[i].c:=strToInt(Form_Main.StringGrid_In.Cells[2,i]);
end;
end;
//графическое отображение
рационального раскроя
procedure
drawRationalCut(
image: TImage;
materialLength:
integer;
detailAmount:
integer;
details: array
of TDetail;
x: array of
integer);
var
i, j: integer;
sum: integer;
k_x: real;
curr_x:
integer;
curr_x_scr:
real;
begin
sum:=0;
for i:=0 to
detailAmount-1 do
begin
sum:=sum+x[i]*details[i].l;
end;
k_x:=image.width/materialLength;
with
image.Canvas do
begin
brush.Style:=bsSolid;
brush.Color:=clBtnFace;
fillRect(rect(0,
0, image.width, image.height));
brush.Color:=clGray;
pen.Color:=clGray;
rectangle(trunc(k_x*sum),
0, trunc(k_x*materialLength), 50);
brush.Color:=clWhite;
pen.Color:=clGray;
rectangle(0,
0, trunc(k_x*sum), 50);
pen.Color:=clRed;
brush.Style:=bsClear;
textOut(0,51,'0');
curr_x:=0;
curr_x_scr:=0;
for i:=0 to
detailAmount-1 do
begin
for j:=0 to
x[i]-1 do
begin
curr_x:=curr_x+details[i].l;
curr_x_scr:=curr_x_scr+k_x*details[i].l;
if
curr_x<>materialLength then
begin
moveTo(trunc(curr_x_scr),0);
lineTo(trunc(curr_x_scr),50);
textOut(trunc(curr_x_scr),
51, intToStr(curr_x));
// textOut(trunc(curr_x_scr-15),
21, '('+intToStr(i+1)+')');
end;
end;
end;
end;
end;
//выход из программы
procedure
TForm_Main.Button_ExitClick(Sender: TObject);
begin
close;
end;
//изменение кол-ва
детеалей
procedure
TForm_Main.Edit_DetailAmountChange(Sender: TObject);
var
new_d_a:
integer;
i: integer;
begin
new_d_a:=strToInt(Form_Main.Edit_DetailAmount.Text);
if
(new_d_a>=1) then
begin
if
(new_d_a<=MAX_DETAIL_AMOUNT) then
begin
Form_Main.StringGrid_In.RowCount:=new_d_a+1;
for i:=1 to
new_d_a do
begin
Form_Main.StringGrid_In.Cells[0,i]:=intToStr(i);
end;
end
else
begin
Form_Main.Edit_DetailAmount.Text:=intToStr(MAX_DETAIL_AMOUNT);
end;
end
else
begin
Form_Main.Edit_DetailAmount.Text:=intToStr(1);
end;
end;
//инициализация программы
procedure
TForm_Main.FormCreate(Sender: TObject);
begin
Form_Main.UpDown_MaterialLength.Min:=1;
Form_Main.UpDown_MaterialLength.Max:=MAX_MATERIAL_LENGTH;
Form_Main.UpDown_DetailAmount.Min:=1;
Form_Main.UpDown_DetailAmount.Max:=MAX_DETAIL_AMOUNT;
Form_Main.StringGrid_In.Cells[0,0]:='№
детали';
Form_Main.StringGrid_In.Cells[1,0]:='Длина';
Form_Main.StringGrid_In.Cells[2,0]:='Цена';
Form_Main.StringGrid_In.Cells[0,1]:='1';
Form_Main.StringGrid_Out1.Cells[0,0]:='№
детали';
Form_Main.StringGrid_Out1.Cells[1,0]:='Количество';
end;
//изменение длины
материала
procedure
TForm_Main.Edit_MaterialLengthChange(Sender: TObject);
var
new_m_l:
integer;
begin
new_m_l:=strToInt(Form_Main.Edit_MaterialLength.Text);
if
(new_m_l>=1) then
begin
if not
(new_m_l<=MAX_MATERIAL_LENGTH) then
begin
Form_Main.Edit_MaterialLength.Text:=intToStr(MAX_MATERIAL_LENGTH);
end;
end
else
begin
Form_Main.Edit_MaterialLength.Text:=intToStr(1);
end;
end;
//сортировка данных по
возрастанию длины детали
procedure
StrGridSort;
var
i: integer;
do_next:
boolean;
begin
do_next:=true;
while do_next
do
begin
do_next:=false;
for i:=1 to
Form_Main.StringGrid_In.RowCount-2 do
begin
if
strToInt(Form_Main.StringGrid_In.Cells[1,i])>
strToInt(Form_Main.StringGrid_In.Cells[1,i+1])
then
begin
Form_Main.StringGrid_In.cols[1].Exchange(i,i+1);
Form_Main.StringGrid_In.cols[2].Exchange(i,i+1);
do_next:=true;
end;
end;
end;
end;
//вычисление
рационального раскроя и отображение результата
procedure
TForm_Main.Button_CalculateClick(Sender: TObject);
var
i,sum,cost:
integer;
begin
strGridSort;
updateData;
searchRationalCut(materialLength,
detailAmount, details, x);
Form_Main.StringGrid_Out1.RowCount:=detailAmount+1;
sum:=0;
cost:=0;
for i:=1 to
detailAmount do
begin
Form_Main.StringGrid_Out1.Cells[0,i]:=intToStr(i);
Form_Main.StringGrid_Out1.Cells[1,i]:=intToStr(x[i]);
sum:=sum+x[i]*details[i].l;
cost:=cost+x[i]*details[i].c;
end;
Form_Main.Edit1.Text:=intToStr(cost);
Form_Main.Edit2.Text:=intToStr(materialLength-sum);
drawRationalCut(Form_Main.Image_Cut,
materialLength, detailAmount, details, x);
end;
procedure
TForm_Main.Button1Click(Sender: TObject);
begin
Form2.Show;
end.
Литература
1. Э.А. Мухачева "Рациональный раскрой промышленных материалов".
Москва, Машиностроение, 1984 г.
2. Э.А. Мухачева, Г.Ш. Рубинштейн "Математическое
программирование". Новосибирск, Наука, 1977 г.