Задачи рационального раскроя в условиях массового производства

 

Выполняем обратный ход (начинаем двигаться с конца таблицы):

 

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 раза.

 

Таким образом, искомый оптимальный  раскрой характеризуется следующим  четырёхмерным вектором x = (1; 3; 0; 0).

 

В вышеприведённой таблице  с результатами прямого хода выделены номера заготовок, которые при обратном ходе последовательно включались в  оптимальный раскрой.

 

Результат работы программы (проверка алгоритма):

 

Исходные данные

 

Длина проката: 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;

 

end.

 

 

Литература

 

1. Э.А. Мухачева "Рациональный раскрой промышленных материалов". Москва, Машиностроение, 1984 г.

 

2. Э.А. Мухачева, Г.Ш. Рубинштейн "Математическое программирование". Новосибирск, Наука, 1977 г.