Математика/5. Математическое моделирование

 

Бакирова Н.Ш., Медетбаева С.А., Айпанов Ш.А.

Алматинский технологический университет, Казахстан

 

РЕШЕНИЕ ЗАДАЧИ ОПТИМАЛЬНОГО РАСКРОЯ

МАТЕРИАЛОВ В ДВУМЕРНОМ СЛУЧАЕ

 

На многих промышленных предприятиях при массовом производстве продукции возникает задача рационального раскроя материалов (ткани, листы металла, рулоны, доски, трубы, арматура, провода и т.д.). При раскрое имеющихся заготовок получаются различные виды деталей, а какая-то часть заготовок образуют отходы. План раскроя называется оптимальным, если он минимизирует отходы при условии получения необходимого количества требуемых деталей. Можно также поставить задачу максимизации количества готовых изделий, собираемых из полученных деталей, при ограниченном количестве раскраиваемых заготовок. Для решения таких задач необходимо построить математические модели и использовать методы оптимизации для решения полученных задач [1, 2].

Рассмотрим постановку задачи для двумерного случая. Пусть имеется ограниченное количество () оди­на­ковых двумерных заготовок. Раскраивая  эти заготовки, можно получить  видов деталей. Пусть имеется  способов раскроя заготовок. Заданы  – количество деталей -го вида, получаемое при -м способе раскроя,  . Из полученных деталей соби­раются готовые изделия. Для изготовления одного изделия используются  видов различных деталей в количестве  соответственно. Необходимо опре­делить число заготовок , раскраиваемых по каждому -му способу .  при кото­ром обеспечивается получение максимального количества готовых изделий .

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

                                                                   (1)

                                             (2)

где  – множество целых чисел.

         Таким образом, получаем полностью целочисленную задачу линейного программирования (1), (2), которая может быть решена с использованием метода отсечения Гомори или метода ветвей и границ [2].   

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

Рассмотрим задачу прямоугольного раскроя, когда заготовки и детали имеют прямоугольную форму. Задачи прямоугольного раскроя имеют большое прак­тическое значение и относятся к классу NP-трудных задач комбинаторной оптимизации. В связи с этим для их решения разрабатываются эвристические подходы, идеи которых заимствованы у живой природы или физических процессов. К таким методам можно отнести генетические алго­ритмы, нейронные сети, а также алгоритм «муравьиной колонии» и др. [3, 4].              

Алгоритм гильотинного раскроя основан на переходе от площадного рас­кроя к линейному раскрою, с элементами эвристик, полученных экспери­менталь­ным путем [5]. Этот алгоритм может решать задачи раскроя только для прямоугольников и только для сквозных резов. Но преимущество его в том, что он прост в реали­зации, не требует большого количества компьютерного времени и реализуем на простейших кроильных станках. Составлена программа,  реализующая алгоритм гильотинного раскроя материалов, а также рассмотрен конкретный пример, решение которого получается с использованием стандартных пакетов для целочисленных задач линейного программирования.     

 

Литература: 

    1. Крушевский А.В. Справочник по экономико-математическим моделям и методам. – Киев: Техніка, 1982. – 208 с.

    2. Таха Х. Введение в исследование операций. – М.: Издательский дом «Вильямс», 2005. – 912 с.

3. Пушкарёва Г.В. Гибридный генетический алгоритм для автоматизирован­ного проектирования оптимальных траекторий // Материалы I‑й Всероссийской научно-практической конференции «Опыт практического примене­ния языков и программных систем имитационного моделирования в промыш­ленности и прикладных разработках». – СПб.: ФГУП ЦНИИ, 2003. – С. 190-195.

4. Валеева А.Ф., Петунин А.А., Файзрахманов Р.И. Применение конструктивной метаэвристики «муравьиная колония» к задаче гильотинного раскроя // Вестник Башкирского университета. – 2007. – № 3. С. 12-14.

5. Бунаков П. Алгоритм оптимального раскроя материалов для автоматизи­рованного производства // САПР и графика. – 2007. – № 1. – С. 74-77.