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

Оглавление

 

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..3

1.      Определение  рациональных способов раскроя  материала . . . . . . . . . . . . . . 4

2.  Определение  интенсивности  использования рациональных способов раскроя и модели линейного программирования . . . . . . . . . . . . . . . . . . . . . . 5

3.     Практическое приложение теории раскроя к решению задач . . . . . . . . .8

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

5.    Программа вычисления оптимального раскроя. . . . . . . . . . . . . . . . . . . .13

6.     Описание  работы программы на контрольном примере . . . . . . . . . . . . 15

Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20

Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

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

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

Для достижения поставленной цели были решены следующие задачи:

1. Анализ литературы по теме работы
2. Изучение основных понятий
3. Изучение методов оптимизации раскроя стандартных форм
4. Создание программы по оптимизации раскроя
5. Практическое приложение теории к решению текстовых задач

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

 

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

 

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

 Пусть k — индекс вида заготовки, k = 1, ..., q; i — индекс способа раскроя единицы материала, i = 1,..., р; a_ik — количество (целое число) заготовок вида к, полученных при раскрое единицы материала i-м способом.

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

Способ раскроя v называется рациональным (оптимальным по Парето), если для любого другого способа раскроя i из соотношений a_ik>a_vk,k = 1, ..., q, следуют соотношения a_ik = a_vk , k = 1, ..., q.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Определение интенсивности использования рациональных способов раскроя

 

Обозначения:

j —индекс материала, j = 1, …, n;

k — индекс вида заготовки, k = 1, ..., q;

i — индекс способа раскроя единицы материала, i = 1, ..., р;

a_jik  — количество (целое число) заготовок вида k, полученных при раскрое единицы j-го материала i-м способом;

b_k— число заготовок вида k в комплекте, поставляемом заказчику;

d_j — количество материала j-го вида;

x_ji — количество единиц j-го материала, раскраиваемых по i-му способу (интенсивность использования способа раскроя);

c_ji— величина отхода, полученного при раскрое единицы j-го

материала по i-му способу;

у — число комплектов заготовок различного вида, поставляемых заказчику.

Рассмотрим следующие  модели оптимизации раскроя стандартных  форм:

1. Модель А раскроя с минимальным расходом материалов:

 

                                    (1)          

 

    (2)

                  (3)

 

Здесь (1) — целевая функция (минимум количества используемых материалов);

(2) — система ограничений,  определяющих количество заготовок,  необходимое для выполнения заказа;

(3) — условия неотрицательности  переменных.

Специфическими для данной области приложения модели линейного программирования являются ограничения (2).

2. Модель В раскроя с минимальными отходами:

 

                               (4)

    (5)

           (6)

 

Здесь (4) — целевая функция (минимум отходов при раскрое  материалов);

(5) — система ограничений,  определяющих количество заготовок,  необходимое для выполнения заказа;

(6) — условия неотрицательности  переменных.

3. Модель С раскроя с учетом комплектации:

 

                                               (7)

                        (8)

          (9)

    (10)

 

Здесь (7)   — целевая  функция (максимум комплектов, включающих заготовки различных видов);

(8)    —  ограничения  по количеству материалов;

(9)  — система ограничений, определяющих количество заготовок, необходимое для формирования комплектов;

(10)  —  условия неотрицательности  переменных.

 Специфическими для  данной области приложения модели  линейного программирования являются ограничения (9).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Практическое приложение теории раскроя к решению задач

 

Пример 1. Способы раскроя металлического стержня.

Определить все рациональные способы раскроя металлического стержня длиной 100 см на заготовки трех типов: длиной 20, 30 и 50 см. Указать величину отходов для каждого способа.

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

 

Способ раскроя	Количество заготовок  длиной			Величина отходов, см
		50 см	30 см .		20 см
1	2	0	0	0
2	1	1	1	0
3	1	0	2	10
4	0	3	0	10
5	0	2	2	0
6	0	1	3	10
7	0	0	5	0

Табл. 1

 

Пример 2. Способы раскроя куска кожи.

Определите все рациональные способы раскроя прямоугольного куска кожи размером 100 х 60 см на квадратные заготовки со сторонами 50,40 и 20 см и укажите величину отходов для каждого способа.

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

 

 

Способ раскроя	Количество заготовок  со стороной			Величина отходов, см
		50 см	40 см		20 см
1	2	0	0	1000
2	1	1	2	1100
3	1	0	6	1100
4	0	2	7	0
5	0	1	11	0
6	0	0	15	0

Табл. 2

 

Пример 3. Изготовление парников из металлических стержней.

При изготовлении парников используется материал в виде металлических стержней длиной 220 см. Этот материал разрезается на стержни длиной 120, 100 и 70 см. Для выполнения заказа требуется изготовить 80 стержней длиной 120 см, 120 стержней длиной 100 см и 302 стержня длиной 70 см.

Вопросы:

1.  Сколько существует  рациональных способов раскроя?

2.  Какое минимальное  количество материала следует  разрезать, чтобы выполнить заказ?

3.  Сколько способов  раскроя следует использовать  при выполнении заказа?

Решение. Определяем все рациональные способы раскроя материала на заготовки. Таких способов оказывается пять:

 

 

 

 

 

 

Способ раскроя	Количество заготовок  длиной			Величина отходов, см
		120 см	100 см		70 см
1	1	1	0	0
2	1	0	1	30
3	0	2	0	20
4	0	1	1	50
5	0	0	3	10

Табл. 3

 

Используем модель А для одного вида материала. Тогда x_i — количество единиц материала, раскраиваемых по i-му способу.

Для ответа на второй и третий вопросы задачи получаем следующую   модель линейного программирования с критерием «минимум общего количества используемого материала»:

 

	X1	X2	X3	Х4	Х5
Minimize	1	1	1	1	1
Заготовка 120 см	1	1	0	0	0	>=	80
Заготовка 100 см	1	0	2	1	0	>=	120
Заготовка 70 см	0	1	0	1	3	>=	102

Табл. 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, позволяющая реализовать целенаправленный перебор всех способов рационального раскроя за конечное число шагов, в результате чего находится рациональный раскрой с максимумом прибыли.

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

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