Оптимальный раскрой материала с максимальной прибылью (стр. 2 из 3)
5. Контрольный пример
Пусть в задаче генерирования линейного раскроя заданы следующие параметры: длина проката L = 40, количество типов деталей m = 4, а значения длин li и стоимости ciкаждой детали приведены в таблице:
| i | 1 | 2 | 3 | 4 |
| li | 7 | 11 | 13 | 17 |
| ci | 9 | 14 | 16 | 22 |
Решаем задачу сеточным методом: сначала выполняем прямой ход. Выбираем начальное значение длины раскроя, равное минимальной длине детали: l0 = minli = 7 и последовательно "шагаем" до конца проката, т.е. 40.
Чтобы найти максимальную стоимость на каждом шаге, мы перебираем все детали, которые могут поместиться в текущий раскрой, начиная с минимальной по длине.Для подсчета стоимости раскроя на текущем шаге мы вычитаем длину очередной выбранной детали из текущего раскроя и по таблице находим раскрой с длиной, равной полученному остатку и суммируем его оценку с оценкой выбранной детали. Из вычисленных оценок выбираем максимальную и заносим её в таблицу, вместе с номером детали, при которой эта оценка была получена.
Далее в таблице приведены результаты первого этапа (прямого хода) процесса:
| l | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| f(l) | 9 | 9 | 9 | 9 | 14 | 14 | 16 | 18 | 18 | 18 | 22 | 23 | 23 | 25 | 27 | 28 | 28 |
| i(l) | 1 | 1 | 1 | 1 | 2 | 2 | 3 | 1 | 1 | 1 | 4 | 1 | 1 | 1 | 1 | 2 | 2 |
| 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 раза.
Таким образом, искомый оптимальный раскрой характеризуется следующим четырёхмерным вектором 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;