Математическая энциклопедия - раскроя задача

з а д а ч а р а ц и о н а л ьн о г о р а с к р о я,выбор такого размещения заготовок в кусках материала, к-рое дает заготовки, как правило, в требуемой комплектности при минимальном расходе материала. В соответствии с особенностями в технологии и организации раскроя различаются математич. модели рационального раскроя (р. р.) для массового и индивидуального производства: для прямых (отрезки, прямоугольники, параллелепипеды) и фигурных заготовок, для случая кусков материала постоянных размеров и формы и с разбросом формы или размещения пороков (см. [1]). В зависимости от отрасли производства и используемого оборудования учитываются ограничения на допустимые виды раскроев. С Р. з. совпадает постановка нек-рых задач размещения грузов в сушильных печах, в вагонах, на палубах судов.

В массовом производстве при поступлении одинаковых кусков материала, если можно перечислить все i=1, 2, ... , N доступные способы раскроя одного куска материала на нек-рые из j = 1, ... , тнужных видов заготовок, Р. з. сводится к решению задачи линейного программирования:найти интенсивность применения каждого из раскроев, при к-рых ixi=min и для каждого j соблюдено условие , где а ij- количество j-х заготовок в i-м раскрое, a bj - необходимое на одно изделие количество этих заготовок. На практике обычно нельзя перечислить все допустимые раскрои. Упомянутую задачу линейного программирования решают исходя из нек-рого набора допустимых раскроев методом последовательного улучшения плаца. Одновременно нередко изменяют список допущенных к рассмотрению раскроев. На каждом шаге составляют (генерируют на ЭВМ) один из тех раскроев, к-рые, согласно оценкам двойственной задачи линейного программирования, способны улучшить план раскроя в целом. В случае "линейного" материала (к-рый надо кроить, только по длине) упомянутое генерирование осуществимо в приемлемое время средствами динамического программирования (см. [1], [2]). При раскрое листов на прямоугольники этот путь принципиально тоже осуществим, но в реальных задачах может становиться громоздким. Генерирование улучшающих раскроев тогда ведут эвристич. алгоритмами: ограничиваются целенаправленным составлением раскроев с участием не более трех разнотипных заготовок (см. [2], [3]).

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

В массовом производстве часто используют линейный материал смешанных длин. Здесь Р. з. состоит в выборе раскроя очередного куска конкретной длины. В машиностроении целесообразно применять специально рассчитываемую линейку, предписывающую раскрой остатка, к-рый возникает после отрезания нескольких заготовок [1], В швейном производстве при составлении настилов ткани из рулонов разной длины используют также малые специализированные ЭВМ (см. [4]), решающие только эту Р. з. В металлургии на прокатных станах замеряют на ходу длину прокатного металла и, на основе решения Р. з. на ЭВМ, осуществляют в автоматич. режиме управление раскройным устройством (см. [5]). В зарубежной стекольной промышленности автоматизируют обнаружение пороков стекла и решают на ЭВМ Р. з., подчиняя ее обходу пороков. В лесопилении бревна также имеют разброс размеров и формы, но массовость задачи придает коэффициентам (характеризующим для k-й группы бревен выход досок j-го вида при установке пил i-м способом) устойчивый статистич. характер. Р. з. в лесопилении математически поставлена давно (см. [1]) и эффективно решена в производственных условиях (см. [6]).

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

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

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

Лит.:[1] К а н т о р о в и ч Л. В., 3 а л г а л л с р В. А., Рациональный раскрой промышленных материалов, 2 изд., Новосиб., 1971; [2] М у х а ч е в а Э. А., "Кузн.-штамп. произ-во", 1979, № 6, с. 14-17; [3] Математическое обеспечение расчетов линейного и прямоугольного раскроя, Уфа, 1980 (Тр. Всесоюзного науч. семинара); [4] Г а л ы н к е р И. И., С а ф р о н о в а И. В., Механическая технология производства одежды, М., 1977; [5] Э п ш т е й н В., Л а г у т и н А., "Материально-техн. снабж.", 1976, № 11, с. 77-81; [6] С о б о л е в И. В., Управление производством пиломатериалов, Петрозаводск, 1976; [7] Б е л я к о в а Л. Б., Р я б и н и н а Н. О., "Кузн.штамп. произ-во", 1977, № 11, с. 25-28; [8] С т о я н Ю. Г., П а н а с е н к о А. А., Периодическое размещение геометрических объектов, К., 1978. В. А. Залгаллер, Л. В. Канторович.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985