9. Постановка некоторых задач оптимального раскроя

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

Вначале рассмотрим задачи, в которых на материале размещены выкройки одинаковой формы.

Рис. 50

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

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

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

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

где — площадь материала, площадь выкройки.

Величина

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

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

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

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

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

Рассмотрим случай, когда материал покрывает всю плоскость

Задача 3. Плоскость «наилучшим образом» покрыть выкройками, имеющими форму выкроек

Слова «наилучшим образом» могут трактоваться по-разному. Можно, например, поступить следующим образом. Пусть имеется некоторое покрытие плоскости выкройками Пусть (2) есть круг радиуса R с центром в начале координат, а количество выкроек, целиком лежащих внутри круга (2). Отношение

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

может быть принята как характеристика качества покрытия плоскости выкройками Однако, такой выбор функции цели может оказаться неприемлемым. В самом деле, даже в лучшём случае, когда могут быть целые конечные зоны материала, не покрытые выкройками, так как на величину предела (6.90) удаление из множества выкроек любого конечного числа их не может повлиять. От такого явления можно избавиться, исходя из других соображений при выборе функций цели. Можно, например, считать покрытие плоскости оптимальным, если радиус наибольшего кружочка, который можно разместить где-либо на непокрытой чдсти плоскости, минимален.

Задача 4. Пусть материал (2) представляет собой ленту заданной ширины а. Требуется покрыть материал выкройками «наилучшим образом».

Рис. 51.

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

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

Пример 1. Пусть, например, ширина полосы Выкройка имеет форму правильного треугольника с высотой На рис. 51 приведены два различные покрытия полосы.

В случае а) а в случае Следовательно, второе покрытие полосы является лучшим на 5,3%. Периоды в размещении выкроек соответственно равны

Предлагается решить вопрос, существует ли лучшее, чем в случае б), решение задачи.

Из приведенного примера видно, что даже в случае выкроек простой формы не всегда легко принять правильное решение. Естественно, что с усложнением формы выкройки задача существенно усложняется.

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

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

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

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

Рассмотрим, например, задачу о размещении комплектов выкроек.

Задача 6. Задан материал и комплект (набор) выкроек Требуется из материала изготовить максимальное количество комплектов выкроек.

Грубая оценка максимального числа комплектов, которое можно разместить на материале, дается по формуле:

где площади выкроек

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

Задачи 2—5 могут быть перефразированы и для комплектов выкроек.

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

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

Задача 7. На данном материале (2) разместить максимальное количество выкроек так, чтобы на остатке материала разместилось максимальное количество выкроек

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

Задача 8. На данном материале (2) разместить максимальное количество комплектов выкроек так, чтобы

на остатке материала разместилось максимальное количество комплектов

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

Задача 9. На данном материале (2) разместить такое количество выкроек (комплектов) и такое количество выкроек (комплектов) чтобы общая стоимость выкроек была максимальной.

Очевидно, что задача 9 включает в себя, как частный случай, задачи 7 и 8. В свою очередь задача 9 может быть обобщена на случай, когда требуется разместить несколько типов выкроек (комплектов).

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

Задача 10. Материал раскроя есть полубесконечная полоса заданной ширины а (рис. 52). Требуется так разместить комплект выкроек чтобы длина I участка полосы, заключающего этот комплект, была минимальной. В частности, может быть поставлена задача о наилучшем размещении некоторого числа одинаковых выкроек.

Рис. 52.

Задача 11. Комплект выкроек разместить на прямоугольнике (или параллелограмме, круге, эллипсе и т.д.) наименьшей площади.

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

Задачи 10 и И являются частными случаями следующей общей задачи.

Задача 12. Задано параметрическое семейство областей

Среди этих областей найти такую область, на которой может быть размещен данный комплект выкроек и которой соответствует минимальное значение данной функции

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

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

Рассмотрим некоторые примеры.