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

Табл. 4

 

Решая задачу, получаем следующий  результат:

 

	X1	X2	X3	Х4	X5
Minimize	1	1	1	1	1
Заготовка 120 см	1	1	0	0	0	>=	80	-0,5
Заготовка 100 см	1	0	2	1	0	>=	120	-0,5
Заготовка 70 см	0	1	0	1	3	>=	102	-0,33
Solution	80	0	20	0	34		134

Табл. 5

 

Ответы: 1. Пять способов.         2.134 единицы материала.

3. Три из пяти рациональных  способов раскроя.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

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

 

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

 

Рис. 1

 

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

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

Рис. 2

 

Для просмотра всех рациональных способов раскроя необходимо нажать на кнопку "Раскрои".

 

Рис. 3

 

Для введения новых данных, необходимо удалить старые с помощью  нажатия кнопки "Обновить".

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

Работу программы опишем на конкретном примере.

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

 

i	1	2	3	4
li	7	11	13	17
ci	9	14	16	22

Табл. 6

 

 Выбираем начальное  значение длины раскроя, равное  минимальной длине детали: l₀ = min l_i = 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

Табл. 7

 

Здесь и  далее i(l) – номер детали, которой соответствует максимальная оценка раскроя (сумма стоимости всех деталей, входящих в раскрой) f(l) на шаге l.

Рассмотрим более подробно последовательное заполнение таблицы  на примере шагов

l = 7…14, 22.

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

Если мы видим, что длина  остатка раскроя больше или равна  начальному значению длины раскроя (l₀ = 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. И т.д., пока не достигнут конец проката.

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

4. l = 40

Из таблицы получаем индекс детали, добавленной в текущий  раскрой: i(40) = 1.

Находим длину детали с  полученным индексом: l₁ = 7.

Вычисляем остаток раскроя: 40 – 7 = 33. Этот остаток используем для следующего шага обратного хода.

2) l = 33

Индекс  детали: i(33) = 2.

Длина детали: l₂ = 11.

Остаток раскроя: 33 – 11 = 22.

3) l = 22

Индекс  детали: i(22) = 2.

Длина детали: l₂ = 11.

Остаток раскроя: 22 – 11 = 11.

4) l = 11

Индекс  детали: i(11) = 2.

Длина детали: l₂ = 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

Результат

 

Рис. 4

 

Рис.5

 

Оптимальное количество деталей  каждого типа:

Деталь №1….: 1 шт.

Деталь №2….: 3 шт.

Деталь №3….: 0 шт.

Деталь №4….: 0 шт.

Оценка раскроя: 51 денежных единиц

Остаток материала: 0

Результаты ручного и  машинного вычислений совпадают, что  говорит о работоспособности  разработанного алгоритма.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

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

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

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

В данной работе поставленная задача была решена с помощью сеточного  метода. Как показала проделанная  работа, этот метод эффективен и  прост для программной реализации на ЭВМ. Результат, полученный с помощью  этого метода, является оптимальным.

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