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

РАСКРОЯ МАТЕРИАЛОВ

 

                                                         Г.Б. Бронфельд  ( Н.Новгород )

 

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

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

      проволоки;

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

      проводов;

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

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

      нормативные [3];

      технологические [4];

      оптимизационные [2, 5, 6].

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

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

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

       В [6] применен метод оптимизации, основанный на новом методе решения задач нелинейного программирования, описанном в [7].

       Опишем общую задачу линейного (одномерного) раскроя материала.

       Необходимо из кусков материала длиной d _i ( i = 1, 2, …, m ) выкроить заготовки длиной a _j ( j = 1, 2, …, n )  в указанном ассортиментном наборе, заданном вектор-столбцом  [b _jo]. Требуется определить оптимальный план раскроя материала, т.е. получить максимум ассортиментных наборов m  с минимальными отходами т.е. найти матрицу [x _{i j} ] ( количество j – х заготовок в    i – х кусках).

       В [2 ]  сформулирована казалось бы та же постановка задачи, но она существенно отличается. Там упоминаются те же критерии оптимальности минимум отходов и максимум ассортиментных наборов (он задается в виде ограничения).

       В статье же рассматривается в качестве основного критерий максимума ассортиментных наборов при заданном ограничении по минимуму отходов (для всех видов раскроя есть норматив отходов  Z). Эта разница в критериях приводит к разнице в методах решения задачи.

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

       Пусть Δ _i  - отходы, получаемые от i – го куска материала. Тогда сумма отходов равна

                               

                                 m                   m              m     n

                                 S   Δ _I    =   S  d _i  -   S  S   a _j x _{i j}                                              (1)

                                        i  =1                i  =1          i  =1 j = 1           

   Итак, требуется найти матрицу оптимального решения [x _{i j о} ],  максимизирующую линейную форму L при условиях

 

                                                     L = m                                                     (2)

 

                                                    n  

                                                   S  a_j x _{i j}   £    d _i                                                 (3)

                                                   j = 1   

                                                                    _m        

                                                     S   x _{i j}     ³  b _jo  m                                      (4)

                                                     i =1  

                                                   x _{i j}   ³  0                                                        (5)

 

                                                  a  _j  >  0 ,    b _{j o} > 0.                                         (6)

                                                       _{m           m                    m        n}

                                          S   Δ _i =  S d _i  -   S  S a _j x _{i j}  £  Z                       (7)

                                           i =1          i =1          i =1 j =1  

 

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

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

       Таким образом, сумма длин перемычек q _i   в кусках материала равна     

                                                n                                        n                                n

                          q _i = 0 , если S x _{i j} £  1;   q _i = p ( S x _{i j} – 1) , если S x _{i j} > 1    (8)

                                                 j                                         j                           j

       Кстати размер перемычек  достигает несколько процентов и более от размера заготовки и может оказывать весьма существенное влияние на итоги раскроя [4].

       Неравенство (3) будет выглядеть следующим образом

                                              n

                                             S  a _j x _{i j} + q _i  £  d _i                                                   (9)

                                                           _{j = 1}

       а неравенство (7) будет

                          m            m               m   n                            m      

                          S Δ _i = S   d _i  -  S S a _j x _{i j}   -  S q _i  £  Z                                  (10)

                              i = 1         i = 1         i = 1 j = 1              i = 1         

 

      Задача (2), (4) – (6), (8) –(10) является принципиально нелинейной, область изменения переменных невыпукла и представляет собой форму "ежа". С такой постановкой задач автор столкнулся при решении задачи раскроя ткани для швейной фабрики [6 ].

      Оказалось, что математическая постановка задачи близка к математической постановке задачи, решаемой в [7].

      Для задачи [6] тоже был применен метод "надувного шарика" (метод Бронфельда), описанный в [7 ]. Метод основан на итеративном подходе, использует идеи метода максимального элемента и метода ветвей и границ, а также использует специальный прием, направленный на понижение размерности в процессе решения задачи.

       Этот метод напоминает эвристический алгоритм  [2 ], основанный на методе размерной последовательности при раскрое пруткового проката.

       Существенным моментом в рассматриваемом методе решения задачи является следующее.

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

      При вводе информации указывается в какой последовательности количество отдельных видов заготовок может превышать пропорцию, указанную вектором  [b _{j o}]. В этом случае уже решается задача с использованием неравенства  (7) для остатков после нахождения максимума ассортиментных наборов. Если и в этом случае (7) не удовлетворяется, то полученный максимум ассортиментных наборов заготовок уменьшается на 1 и процесс повторяется до нахождения решения.

       Когда внедрили программу [6] на швейной фабрике, столкнулись с интересной ситуацией. Компьютер выдавал оптимальное решение практически сразу после ввода информации, специалисты предприятия выполняли раскрой с помощью калькуляторов в пределах 1-2 часов. Процент отходов, получаемых по расчетам специалистов на основе нормативного метода, укладывался, как правило, в 0,5%, т.е. 99,5% от длины рулонов составляло полезное использование ткани. Мы тоже после ряда улучшений программы вышли на этот результат и программу [6] приняли в эксплуатацию. Но при сравнении раскроя, выданного ПЭВМ, и, полученного сотрудниками предприятия, оказалось, что они отличались в отдельных местах весьма существенно. Анализ привел к выводу, что люди шли иногда на нарушения, в частности нелинейных ограничений (это приводило к ускорению получения карт раскроя). Получаемые численные расчеты с ходу другому специалисту тяжело перепроверить и они регулярно запускались в производство.

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

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

 

 

 

ЛИТЕРАТУРА

 

1.     Амбос Э., Нойбауер А., Освальд Ю. И др. Экономия сырья и материалов. – М.: Металлургия, 1989. – 255 с.

2.     Бабаев Ф.В. Оптимальный раскрой материалов с помощью ЭВМ. – М.: Машиностроение, 1982. -  168 с.

3.     Фурин А.И. Производство мягкой мебели. – М.: Высшая школа, 1988. – 267 с.

4.     Справочник конструктора штампов: Листовая штамповка/ Под общ. Ред. Л.И.Рудмана. – М.: Машиностроение, 1988. – 496 с.

5.     Канторович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов. – Новосибирск: Наука, 1971. – 299 с.

6.     Бронфельд Г.Б., Патокин Д.В. Программа оптимального раскроя ткани на ПЭВМ типа "ИСКРА-1030М". Руководство пользователя. – Н.Новгород: НПЧВП "ВЕХА", 1991. –   5 с.

7.     Бронфельд Г.Б. Алгоритм решения задачи оптимального распределения плана производства // Труды института. Автоматизация и механизация управления производством, Горький, НИИУавтопром, 1977, вып.2, с. 75-83.