Линейный раскрой. Задача одномерного раскроя

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

Эта страница существует благодаря следующим персонам

Timur

Timur

Создан: 2026-11-22 12:05:40, Последнее изменение: 2026-11-22 16:26:18

Линейный раскрой — это распределение деталей по пруткам, арматуре, трубам или другим заготовкам заданной длины. Детали можно переставлять местами: важно не исходное их положение в списке, а то, какие из них стоит вырезать из одной заготовки.

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

PLANETCALC, Линейный раскрой прутков

Линейный раскрой прутков

Заготовки

Тип профиляДлинаКоличество
Записей:

Детали

Тип профиляДлинаКоличество
Записей:

При одинаковом значении основного критерия выбирается план с лучшим вторым критерием.
Дополнительная длина, резервируемая для каждой размещенной детали; в тех же единицах, что и длины в таблицах.
Состояние
 
Использовано заготовок
 
Размещено деталей
 
Всего деталей
 
Длина использованных заготовок
 
Длина размещенных деталей
 
Суммарная ширина реза
 
Суммарный остаток
 
Использование материала, %
 
Нижняя оценка числа заготовок
 
Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.
Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.
Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.
Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

Заготовки, детали и профили

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

  1. Тип профиля — обозначение материала или проката, например «Арматура А500С». Деталь можно разместить только на заготовке с тем же типом профиля. Стальную арматуру и алюминиевую трубу не стоит смешивать в одном плане, даже если их длины удобно совпадают.
  2. Длина — длина заготовки или детали. Все длины должны быть в одних единицах: если выбраны метры, то 80 сантиметров записываются как 0,8.
  3. Количество — число одинаковых позиций. Калькулятор раскрывает его в отдельные детали или заготовки, поэтому строка «длина 3, количество 2» означает две детали по 3.

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

Пример с двумя прутками

Предположим, у нас есть один пруток длиной 12 метров и один длиной 9 метров. Нужны четыре детали: 8, 7, 4 и 2 метра.

Один из полных планов выглядит так:

Заготовка Детали Остаток
12 м 8 + 4 м 0 м
9 м 7 + 2 м 0 м

Суммарная длина деталей — 21 метр, ровно столько же составляет длина использованных заготовок. Использование материала — 100%. Это пример из калькулятора по умолчанию, но для других исходных данных нулевой остаток, разумеется, не обещан.

Зачем учитывать ширину реза

При распиле небольшая часть материала превращается в стружку. Эта величина называется шириной реза (kerf). Если ее не учесть, красивый план на экране может не поместиться на реальном прутке.

Калькулятор использует консервативное правило: для каждой детали резервируется одна ширина реза. Если на заготовке размещены детали длиной L_1,\ldots,L_n, а ширина реза равна k, то занятая длина равна

U=\sum_{i=1}^{n}L_i+nk

где n — количество деталей на заготовке. План допустим только при U\leq L, где L — длина заготовки. Остаток вычисляется как

R=L-U

Почему nk, а не (n-1)k? Правило n-1 подходит для деления прутка полностью на n частей. Но если после последней детали остается кусок, ее еще надо отделить от него. Чтобы не делать скрытое исключение для точного совпадения длин, калькулятор всегда резервирует один рез на деталь.

Например, две детали по 5 метров и ширина реза 1 метр на заготовке длиной 10 метров требуют уже 12 метров. Для такого плана понадобятся две заготовки, если они есть в наличии.

Что именно оптимизируется

Слово «оптимизация» здесь имеет два разных смысла. Можно расходовать поменьше прутков, а можно оставлять поменьше материала на использованных прутках. Эти цели не всегда совпадают.

Допустим, есть одна заготовка длиной 12 метров и две по 5 метров, а нужны две детали по 3 метра:

  1. Минимум числа заготовок. Обе детали помещаются на одну 12-метровую заготовку. Остаток — 6 метров, зато две короткие заготовки остаются нетронутыми.
  2. Минимум суммарного остатка. Каждая деталь размещается на своей 5-метровой заготовке. Использованы две заготовки, но суммарный остаток — только 4 метра.

Поэтому в калькуляторе есть выбор цели. По умолчанию выбран минимум остатка. При равенстве основного критерия используется второй: сначала сравнивается суммарный остаток или число заготовок, затем — наоборот.

Для оценки результата полезен показатель использования материала — доля длины готовых деталей в длине использованных заготовок:

\eta=\frac{\sum_i \ell_i}{\sum_b L_b}\cdot100\%

где \ell_i — длина i-й детали, а L_b — длина b-й использованной заготовки. Ширина реза в числитель не входит. Поэтому использование материала, доля реза и доля остатка в сумме дают 100%.

Почему нельзя просто обещать лучший план

Это задача одномерного раскроя (one-dimensional cutting-stock problem), близкая к задаче упаковки в контейнеры (bin packing problem). В классической постановке нужно разместить заданный набор предметов в минимальное число одинаковых контейнеров. Наша задача дополнительно учитывает разную длину заготовок, их ограниченное количество и совместимость профилей.

Уже классическая задача упаковки NP-трудна.1 Это не значит, что точный ответ получить невозможно. Для небольшого набора можно перебрать варианты, а большие задачи решают целочисленным программированием и генерацией схем раскроя.2 Но такой точный решатель потребовал бы отдельных ограничений и более сложной реализации.

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

Как работает алгоритм

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

  1. детали по убыванию или возрастанию длины;
  2. при открытии новой заготовки — сначала кратчайшая или сначала длиннейшая подходящая.

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

Полученные планы улучшаются локально:3

  1. Удаление заготовки. Детали с нее пытаются перенести на другие использованные заготовки. Если удалось, заготовка освобождается.
  2. Перестановки. Если простой перенос не помогает, алгоритм ограниченно пробует обменять детали местами и повторить удаление.
  3. Замена заготовки. Если та же группа деталей помещается на более короткую свободную заготовку того же профиля, выполняется замена.

Осталось только сравнить варианты по выбранной цели. Никакого метода научного тыка со случайными числами здесь нет: повторный расчет тех же данных дает тот же план.

Нижняя оценка числа заготовок

Для одного профиля суммарную длину деталей можно разделить на длину самой длинной заготовки и округлить вверх:

B_0=\left\lceil\frac{\sum L_i}{L_{\max}}\right\rceil

где B_0 — нижняя оценка числа заготовок, а L_{\max} — максимальная доступная длина для этого профиля. Оценки по профилям складываются.

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

Как читать результат

План раскроя содержит одну строку на использованную заготовку. Запись «8 + 4» означает две детали соответствующей длины; их порядок при резке на расход материала не влияет. Для каждой строки заново выводятся длина деталей, резерв на рез, остаток и использование материала.

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

Что это значит на практике? Возможно, заготовок действительно не хватает или деталь длиннее любой подходящей заготовки. Но возможен и другой случай: эвристика не нашла существующий план. Поэтому сообщение «полный план не найден» не является доказательством невозможности раскроя.

Критерии применимости

  1. Оптимальность не гарантируется. Проверяются допустимость плана и весь баланс длин, но не минимальность результата среди всех возможных планов.
  2. Профили не смешиваются. Их названия сравниваются точно, включая регистр букв. Для замены одного материала другим нужно отдельное инженерное решение, а не правило упаковки.
  3. Детали не делятся. Одна деталь должна целиком поместиться на одну заготовку.
  4. Новые остатки не становятся заготовками автоматически. Если их нужно использовать в следующей работе, добавьте подходящие остатки в таблицу заготовок вручную.
  5. Ограничения ввода. Поддерживается до 100 заготовок и до 100 деталей после раскрытия количества, а также до шести знаков после десятичной точки. Это ограничение браузерного расчета, а не свойство задачи.
  6. Учитывается только длина. Стоимость закупки, торцевые подрезки, зажимы, минимально полезный остаток, порядок работы станка и время резки в модель не входят.

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


  1. Richard E. Korf. A New Algorithm for Optimal Bin Packing. AAAI 2002. Определения задачи, эвристик и сложности. Статья. ↩

  2. P. C. Gilmore, R. E. Gomory. A Linear Programming Approach to the Cutting-Stock Problem. Operations Research, 1961. Схемы раскроя и генерация столбцов. Статья. ↩

  3. A. C. F. Alvim, C. C. Ribeiro, F. Glover, D. J. Aloise. A hybrid improvement heuristic for the one-dimensional bin packing problem. Journal of Heuristics, 2004. Пример сочетания построения и локального улучшения планов. Статья. ↩

Ссылка скопирована в буфер обмена
PLANETCALC, Линейный раскрой. Задача одномерного раскроя

Комментарии