Оптимальный раскрой материала с максимальной прибылью

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Оптимальный раскрой материала с максимальной прибылью

Оптимальный раскрой материала с максимальной прибылью

Содержание

Введение

1. Постановка и анализ задачи

2. Решение задачи

3. Описание алгоритма

4. Описание программы

5. Контрольный пример

Вывод

Текст программы

Литература

1. Введение

Обычно при производстве изделий материал поступает в виде рулонов, полос, прямоугольных листов, стержней и т. д. Поступающий материал раскраивается на части заданных размеров и определенной конфигурации, представляющие собой в одних случаях заготовки, в других -- готовые детали. К задачам раскроя, относятся и задачи плотного размещения совокупности предметов на заданных участках.

Задачи рационального раскроя описываются сходными математическими моделями. Существенное различие этих моделей определяется главным образом двумя факторами:

1) конфигурацией получаемых при раскрое заготовок;

2) объемом выпускаемой продукции.

Задачи раскроя, определяемые первым фактором, подразделяют на два класса. К первому классу относятся задачи фигурного раскроя, ко второму -- задачи нефигурного раскроя. При фигурном раскрое материал раскраивается на заготовки самых различных конфигураций. К классу задач нефигурного раскроя относятся задачи линейного и прямоугольного раскроя. В первом случае материал раскраивают на заготовки различной длины, для которых задается только один линейный размер. Во втором случае получают заготовки прямоугольной формы, для которых задаются два размера.

Задачи раскроя, определяемые вторым фактором, также подразделяют на два класса: задачи раскроя в условиях массового (крупносерийного) выпуска изделий и задачи раскроя в условиях единичного (мелкосерийного) производства. К обоим классам могут принадлежать как задачи фигурного, так и задачи нефигурного раскроя. Задачи раскроя в условиях массового производства описываются непрерывными моделями линейного программирования, а в условиях единичного производства -- целочисленными. В связи с этим задачи раскроя в указанных условиях часто называют соответственно непрерывными и целочисленными.

Задачи рационального раскроя в условиях массового производства относятся к классу задач линейного программировании, с неявно заданными столбцами (способами раскроя). При решении таких задач методами линейного программирования возникает необходимость в генерировании раскроев на каждом шаге процесса. Ниже рассмотрена задача генерирования линейных раскроев.

1. Постановка и анализ задачи

Решить задачу гильотинного раскроя материала (длинномерного проката) с максимальной прибылью: кусок материала длиной L раскраивается на заготовки m наименований, для каждой заготовки с номером i = известны ее длина li и оценка сi. Требуется найти раскрой с максимальной оценкой получаемого набора заготовок.

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

2. Решение задачи

Предположим, что кусок материала длиной L раскраивается на заготовки m наименований. Для каждой заготовки с номером i = известны ее длина li и оценка сi. Требуется найти раскрой с максимальной оценкой получаемого набора заготовок.

Раскрой может содержать любое число каждой из заготовок. Тогда набор заготовок характеризуется m-мерным вектором

X = (x1, x2, … , xm), (1)

Элементы которого представляют собой целые неотрицательные компоненты, указывающие на число заготовок каждого вида. При этом требуется максимизировать суммарную оценку

(2)

набора заготовок (1) при единственном линейном ограничении

.(3)

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

Для решения поставленной задачи рассмотрим функцию

(4)

xXl

где через Xi обозначено множество неотрицательных векторов х, отвечающих раскроям, в которых общая длина заготовок не превосходит длины l. Пусть l0 = min li, где i =1…m.

Тогда при всех l[0,l0] соответствующие множества Xl состоят из одного нулевого элемента и, следовательно, f(l) = 0 для всех таких l. Для l[0,L0], справедливы следующие рекуррентные соотношения:

,(5)

iIl

где через Il обозначено множество тех i, при которых lil.

Опираясь на рекуррентные соотношения (5), можно для решения задачи предложить простой численный метод, представляющий собой перебор всех допустимых раскроев. Реализация всего процесса основывается на двух этапах:

Решаем задачу сеточным методом: сначала выполняем прямой ход. Выбираем начальное значение длины раскроя, равное минимальной длине детали: l0 = min li = 7 и последовательно "шагаем" до конца проката, т.е. 40.

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

Далее в таблице приведены результаты первого этапа (прямого хода) процесса:

Здесь и далее 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;

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 г.