Задача о раскрое материала

Федеральное государственное  автономное образовательное учреждение высшего профессионального образования

 «Уральский федеральный  университет 

имени первого Президента России Б.Н.Ельцина»

Факультет Безопасности

Кафедра Интерпол

 

 

 

 

 

 

 

 

 

 

 

 

 

Доклад

по дисциплине «Системный анализ»

на тему «Задача о раскрое  материала»

 

 

 

Преподаватель:                  Алферьева Т.И.

 

Cтудентка группы  ВИ-490401                                 Фролова Е.Д.     

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Екатеринбург – 2012

Введение

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

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

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

 

 

 

 

 

 

 

 

 

 

 

1. Методы раскроя материала

Одним из вариантов такой  задачи является задача оптимального линейного раскроя материалов. Это  касается раскроя:

- проволоки;

- ткани;

- труб, швеллера,  уголков и т.п.;

- проводов;

- рулонов материалов на продольные и поперечные полосы и других видов изделий.

Существующие методы  раскроя материалов можно разделить  на 3 группы:

- нормативные;

- технологические;

- оптимизационные.

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

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

Оптимизационные методы основаны на применении математических методов, реализованных на ЭВМ. Эти методы делятся на две группы - чисто оптимизационные и эвристические. Большинство из оптимизационных методов используют линейные модели и метод линейного программирования для их решения. Однако реальные задачи раскроя часто имеют нелинейные элементы, которые приводят к тому, что решение получается все-таки не оптимальным. Эвристические методы иногда приводят к очень неплохим результатам, если это укладывается в норматив отходов. Тем не менее, никогда не ясно, можно ли найти решение еще лучше.

 

2. Постановка задачи о раскрое материала

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

На раскрой (распил, обработку) поступает материал нескольких видов  в определенном количестве. Из этого  материала необходимо изготовить различные  изделия. Материал может быть раскроен разными способами. Каждый способ имеет  свою себестоимость и позволяет  получить разное количество изделий  каждого вида. Необходимо определить способ раскроя, при котором суммарная себестоимость минимальна.

Пусть n - число различных видов материала, поступающего на раскрой;

d_j - количество материала j-го вида, j=1,2…n ,

m - число различных видов изделий, которые надо изготовить;

b_i - число изделий i-го вида, i=1,2…m;

l -число различных способов раскроя;

a_ijk - число изделий i-го вида, которое можно получить из единицы материала j-го вида при k-м способе раскроя, (k=1,2…l);

x_jk - количество единиц материала j-го вида, раскраиваемых k-м способом.

 

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

   (2),

где x_jk ≥ 0 (3) 

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

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

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

 

Модель В раскроя с минимальными отходами:  
  (4)

, (5)

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

Модель С раскроя с учетом комплектации:  
→ max (7) 

 (8) 

 

 ≥ 0, x_jk ≥ 0 (10) 

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

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

 

 

3. Пример задачи о раскрое материала

Имеется некоторый материал в виде стандартных листов, которые надо раскроить для получения не менее 63 штук деталей типа I, не менее 27 штук деталей типа II и не менее 88 штук деталей типа III. Известны лишь пять способов раскроя листа и каждый из них дает результаты, представленные в таблице.

Способы раскроя материала	1	2	3	4	5
Результат (кол-во деталей каждого типа)	1 деталь типа 1,2 детали  типа 2, 10 деталей типа 3.	1 (1) 4 (2) 2 (3)	6 (1) 1 (2) 1 (3)	1 (1) 2 (2) 2 (3)	1 (1) 1 (2) 3 (3)

 

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

Пусть количество листов раскроенных по способу .

Тогда целевая функция  имеет вид:

с учетом способов раскроя  и ограничением на количество деталей  имеем:

,   

,  

, 

, , , , .

Процесс движения по симплексу  представим в виде таблицы.

№						Q (кол-во листов)
1	2	7	9	9	9	36
2	2	8	7	9	9	35
3	3	2	9	9	9	32
4	3	3	7	9	9	31
5	4	0	7	8	9	28
6	5	0	8	2	9	24
7	6	0	8	0	9	23
8	6	0	9	0	7	22
9	7	0	9	0	4	20
10	8	0	9	0	2	19
11	8	0	9	1	0	18

 

Количество деталей

№
1	2	7	9	9	9	81	68	88
2	2	8	7	9	9	70	70	88
3	3	2	9	9	9	77	50	88
4	3	3	7	9	9	66	52	88
5	4	0	7	8	9	63	40	90
6	5	0	8	2	9	64	31	89
7	6	0	8	0	9	63	29	95
8	6	0	9	0	7	67	28	90
9	7	0	9	0	4	65	27	91
10	8	0	9	0	2	64	27	95
11	8	0	9	1	0	63	27	91

 

Ответ: Оптимальный план раскроя:

8 листов – по 1 способу;

9 листов– по 3 способу;

1 листов–  по 4 способу.

При этом получается 63 детали первого типа, 27 второго типа, 91 третьего типа.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

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

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

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