Гудина И.Ю.

Некоторые модели оптимального использования материалов

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

         Под задачами раскроя понимается широкий класс моделей, объединенных общей логической структурой. К ним можно отнести следующие задачи[2]:

• задача раскроя запаса материала;
• задача плотного размещения геометрических объектов в заданной области;
• задача упаковки контейнеров;
• задача загрузки транспорта;
• задача выбора ассортимента; 
• задача планировки помещения;
• задача распределения памяти вычислительных машин;
• задача составления расписания многопроцессорных систем.

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

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

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

         Проведенный анализ привод нас к постановке следующих основных задач.[5]

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

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

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

         Задача 3.Материал поступает (или имеется на складе) двух (или нескольких) размеров во вполне определенном количестве (например, 1/3 от общего числа листов – листами одного размера и 2/3 листами другого размера), и по-прежнему требуется составить наиболее экономный план раскроя.

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

         В тех случаях, когда требуется  с самого начала выбрать заказ одного мерного материала, выбор, по существу, приходится делать лишь между 2-3 конкретными габаритными материалами из числа предусмотренных ГОСТом. В этом случае для каждого из возможных размеров следует составить, хотя бы приблизительно, свой план раскроя (задача первого типа), а затем выбрать наиболее благоприятный из размеров и для него уточнить план раскроя. При индивидуальном заказе материала, наиболее подходящего для какой-либо резко преобладающей заготовки, выбор габарита материала оказывается очевидным, после чего вновь возникает задача 1.

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

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

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

         Рассмотрим общую задачу линейного (одномерного) раскроя материала[6].

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

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

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

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

L = m

         Еще одним видом раскроя является гильотинный раскрой материала[7].

         Дан лист размера L W и n типов прямоугольников l_jw_j, j= ,p_j0 – доход от прямоугольника j, повороты запрещены, разрезы параллельно осям координат от кромки до кромки. Двухэтапная обработка: сначала режим лист параллельно оси у, затем параллельно  оси х. Где k – число параллельных полос k = [L/l_min], y_j – ширина полосы i, 1k, x_ij – число j-x прямоугольников в полосе I. Найти раскрой листа с максимальным доходом.

Пусть.

=

m_j = [W/w_j] - максимально возможное число прямоугольников в полосе.

Модель:

при ограничениях

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

         Предлагается n возможных способов раскроя, заранее заданного, прутика длиной L. Необходимо распределить определенное количество заготовок различной длины l_i на имеющемся материале(i =).  – отходы, получаемые при j-ом способе раскроя.

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

, , j =

         Данный подход можно использовать и при фигурном раскрое. Необходимо определить сколько прутиков будем раскраивать и какой оптимальный план раскроя. Задача приводится к задачам ЦЛП.

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

Литература:

1. Технология прокатного производства. Учебное пособие. / В.М. Клименко, А.М. Онищенко, А.А. Минаев, В.С. Горелик. –К.: Выща школа. Головное изд-во, 1989. -311с.

2. [сылка более недоступна}

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

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

5. . Канторович Л.В.,Залгаллер В.А. Рациональный раскрой промышленных материалов. Издательство «Наука», Сибирское отделение, Новосибирск, 1971

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

7. Silvano Martello, Paolo Toth, Knapsack problem, Algrithms and computer implementations, University of Bologna. John Wiley and Sons, 1990, 296p