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

Содержание

 

Введение

 

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)

 

xÎXl

 

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

 

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

 

,(5)

 

iÎIl

 

 

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

 

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

Первый этап

 

На первом этапе осуществляется так называемый прямой ход: по формулам (5) для всех l = последовательно вычисляются  функции f(l) и при этом фиксируются  индексы i(l), при которых достигается  максимум в выражении (5). Получаемая при этом информация l, f(l) и i(l) запоминается и построчно записывается в таблицу:l 

l0 

l0 + 1 

l0 + 2 … L

f(l) 

f(l0) 

f(l0 + 1) 

f(l0 + 2) … f(L)

i(l) 

i(l0) 

i(l0 + 1) 

i(l0 + 2) … i(L)

 

Второй этап

 

На втором этапе осуществляется так называемый обратный ход: для  получения искомого вектора х (1), для которого выполняется равенство m(x) = f(L), в раскрой в первую очередь  включаются заготовка с номером i(l1), где l1 = L, и подсчитывается значение l2= l1-li(l1).

 

Если l2³l0, то в раскрой  включается заготовка с номером i(l2) и подсчитывается значение l3=l2-li(l2) и т.д. Так как при каждом k³1 очевидно, что lk+1£lk-l0, то через конечное число описанных шагов окажется, что lk+1< l0. На этом генерирование искомого раскроя заканчивается и выводится  результат.

 

 

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

 

1. Определяется текущее  значение длины раскроя l от  минимальной длины детали до  длины материала.

 

2. Вычисляется максимальный  индекс (номер) детали, добавление  которой возможно.

 

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

 

Если максимум достигнут, то он запоминается. Последняя добавленная  деталь удаляется из раскроя и  добавляется следующая (п. 4). Если нет  деталей которые можно добавить в раскрой, происходит выход из цикла.

 

4. Запоминается текущий  раскрой. Длина раскроя уменьшается  на длину детали. Цена раскроя  увеличивается на цену детали. Определяются детали, добавление  которых в раскрой возможно (п. 2).

 

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

 

6. Зная количество деталей  для каждого их вида, составляющих  рациональный раскрой, формируется  искомый вектор х.

 

//процедура вычисления  рационального раскроя

 

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;

 

 

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

 

Вид главного окна программы  приведено на рисунке:

 

 

 

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

 

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

 

 

 

 

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

 

Пусть в задаче генерирования  линейного раскроя заданы следующие  параметры: длина проката L = 40, количество типов деталей m = 4, а значения длин li и стоимости ci каждой детали приведены в таблице:i 1 2 3 4

 

li 7 11 13 17

 

ci 9 14 16 22

 

 

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