Задача розкрою, пояснена просто
Що таке задача розкрою, чому вона NP-складна і як 1D- та 2D-оптимізатори (гільйотина проти вільного вкладання) швидко знаходять добрі рішення.
Що таке задача розкрою?
Дано довжини матеріалу (прутки, дошки, листи) і список потрібних деталей: відріжте всі деталі з якомога меншого матеріалу. Звучить тривіально; математично це NP-складна задача — кількість комбінацій вибухає зі зростанням списку деталей.
1D, 2D і гільйотинні різи
1D — один вимір: труби, профілі, стійки. 2D додає ширину — фанера, скло, листовий метал. Гільйотинні різи йдуть від краю до краю (так працює форматно-розкрійний верстат); вільне вкладання дозволяє будь-який поворот і негільйотинні схеми (так працюють лазери та фрезери).
Чому точні рішення — рідкість
Точно розв'язати можна лише невеликі задачі (динамічне або цілочисельне програмування). Галузь спирається на евристики — First Fit Decreasing, Best Fit Decreasing, полицеві алгоритми, — які зазвичай дають результат у кількох відсотках від оптимуму за мілісекунди.
Пропил та інші пастки реального виробництва
Кожен різ витрачає матеріал: полотно з пропилом 3 mm додає 3 mm на різ, і 50 різів непомітно з'їдають 150 mm матеріалу. Повторне використання обрізків, напрям волокон і втрати на підрізування важать не менше за саме вкладання.
Спробуйте на власному списку різів
Калькулятор лінійного розкрою оптимізує списки прутків і профілів; Калькулятор розкрою листа будує гільйотинні карти розкрою листів із поворотом і пропилом. Вставте свій список і порівняйте загальний матеріал до та після.
Калькулятор лінійного розкрою Відкрити калькулятор лінійного розкрою