Задача раскроя

Задача раскроя (Cutting Stock Problem) — классическая задача комбинаторной оптимизации, которая заключается в оптимальном разрезании стандартных заготовок на детали заданных размеров таким образом, чтобы минимизировать количество использованных заготовок или объём отходов. Это одна из фундаментальных задач производственного планирования, имеющая огромное практическое значение.

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

Практика показывает: даже базовое оптимизационное планирование раскроя заметно снижает отходы. В ряде производств «хорошим уровнем» считают около 3% материальных потерь; на практике применение моделей раскроя нередко даёт снижение на 10–30%. Например, в кейсе из журнала Buildings (2024) по оптимизации раскроя арматуры для железобетонных колонн после внедрения модели удалось снизить расход стали примерно на 18%, отходы — примерно на 9%, совокупные затраты — примерно на 10%

Задача раскроя встречается во множестве отраслей промышленности:

• Металлообработка: раскрой листового металла, труб, профилей, арматуры;
• Деревообработка: распил досок, брусьев, фанеры, ДСП на заготовки для мебели;
• Текстильная промышленность: раскрой рулонов ткани на детали одежды;
• Стекольная промышленность: резка стандартных листов стекла;
• Бумажная промышленность: нарезка рулонов бумаги нужной ширины;
• Строительство: оптимизация распила строительных материалов;
• Кабельное производство: раскрой кабелей на отрезки заданной длины.

В классической одномерной задаче раскроя имеются:

• Стандартные заготовки длины L (например, металлические прутки по 97 см);
• n типов деталей с длинами l₁, l₂, ..., lₙ;
• Требуемое количество деталей каждого типа: b₁, b₂, ..., bₙ.

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

Ключевое понятие — шаблон раскроя (cutting pattern). Шаблон описывает, сколько деталей каждого типа вырезается из одной заготовки. Например, из прутка длиной 97 см можно вырезать либо 4 детали по 23 см (отход 5 см), либо 3 детали по 31 см (отход 4 см), либо 2 детали по 31 см и 2 по 17 см (отход 1 см), и так далее.

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

Постановка задачи

Имеются стандартные заготовки длиной 97 см. Необходимо получить детали следующих типов:

• Тип 1: длина 23 см — 12 шт.
• Тип 2: длина 19 см — 18 шт.
• Тип 3: длина 31 см — 8 шт.
• Тип 4: длина 17 см — 15 шт.
• Тип 5: длина 29 см — 10 шт.
• Тип 6: длина 13 см — 6 шт.

Цель: минимизировать число использованных заготовок при выполнении всех требований.

Решение задачи

1. Выбор модели

Для решения задачи раскроя используется линейная целочисленная модель. Каждая переменная представляет количество использований конкретного шаблона раскроя — это целое неотрицательное число. Линейная формулировка эффективна для решения, так как современные MILP-решатели хорошо справляются с такими задачами.

2. Создание модели

Создается экземпляр линейной целочисленной модели.

// Создаем линейную целочисленную модель
Модель = О2.Модели()
    .ЛинейнаяЦелочисленнаяМодель()
    .СоздатьМодель();

3. Ввод данных

Вводятся исходные данные: длина заготовки, Потребности — требуемое количество деталей определенной длины, и сами длины деталей.

// Вводим данные
ДлинаЗаготовки = 97;
Потребности    = О2.Утилиты().МассивЧиселИзСтроки("12, 18, 8, 15, 10, 6");
ДлиныДеталей   = О2.Утилиты().МассивЧиселИзСтроки("23, 19, 31, 17, 29, 13");

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

• Однотипные шаблоны — максимальное количество деталей одного типа из заготовки;
• Двухтипные шаблоны — комбинации деталей двух типов.

// Генерируем шаблоны раскроя с одним типом деталей
Шаблоны           = Новый Массив();
КоличествоДеталей = ДлиныДеталей.Количество();

Для К = 0 По КоличествоДеталей - 1 Цикл
    Шаблон = Новый Массив();
    Для К1 = 0 По КоличествоДеталей - 1 Цикл
        Шаблон.Добавить(0);
    КонецЦикла;
    МаксимальноеКоличество = Цел(ДлинаЗаготовки / ДлиныДеталей[К]);
    Шаблон[К] = МаксимальноеКоличество;
    Шаблоны.Добавить(Шаблон);
КонецЦикла;

Например, для детали длиной 23 см из заготовки 97 см можно вырезать ⌊97/23⌋ = 4 детали. Это создаёт шаблон [4, 0, 0, 0, 0, 0].

Генерация смешанных шаблонов.

// Генерируем смешанные шаблоны с двумя типами деталей
Для К = 0 По КоличествоДеталей - 1 Цикл
    Для К1 = К + 1 По КоличествоДеталей - 1 Цикл
        МаксимальноеКоличествоК = Цел(ДлинаЗаготовки / ДлиныДеталей[К]);
        Для КоличествоК = 1 По МаксимальноеКоличествоК Цикл
            Остаток = ДлинаЗаготовки - КоличествоК * ДлиныДеталей[К];
            
            Если Остаток <= 0 Тогда
                Продолжить;
            КонецЕсли;
            
            КоличествоК1 = Цел(Остаток / ДлиныДеталей[К1]);
            
            Если КоличествоК1 > 0 Тогда
                Шаблон = Новый Массив();
                Для К2 = 0 По КоличествоДеталей - 1 Цикл
                    Шаблон.Добавить(0);
                КонецЦикла;
                
                Шаблон[К]  = КоличествоК;
                Шаблон[К1] = КоличествоК1;
                
                // Проверка на дубликаты
                ШаблонСуществует = Ложь;
                Для Каждого СуществующийШаблон Из Шаблоны Цикл
                    Совпадает = Истина;
                    Для К2 = 0 По КоличествоДеталей - 1 Цикл
                        Если СуществующийШаблон[К2] <> Шаблон[К2] Тогда
                            Совпадает = Ложь;
                            Прервать;
                        КонецЕсли;
                    КонецЦикла;
                    
                    Если Совпадает Тогда
                        ШаблонСуществует = Истина;
                        Прервать;
                    КонецЕсли;
                КонецЦикла;
                
                Если НЕ ШаблонСуществует Тогда
                    Шаблоны.Добавить(Шаблон);
                КонецЕсли;
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;
КонецЦикла;

Например, перебираются комбинации: 2 детали по 23 см + детали по 19 см. После размещения 2×23=46 см остаётся 51 см, куда помещается ⌊51/19⌋ = 2 детали по 19 см. Получается шаблон [2, 2, 0, 0, 0, 0].

4. Регистрация переменных

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

// Регистрируем переменные для количества использований каждого шаблона
ИспользованияШаблонов = Модель.МассивПеременныхДиапазона(
    Шаблоны.Количество(),
    0,
    1000
);

5. Описание ограничений

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

// Ограничение: удовлетворяем потребности в каждом типе деталей
Для К = 0 По КоличествоДеталей - 1 Цикл
    ДеталиИзШаблонов = Модель.Выражения().СоздатьПостроительВыражений();
    Для К1 = 0 По Шаблоны.ВГраница() Цикл
        КоличествоВШаблоне = Шаблоны[К1][К];
        Если КоличествоВШаблоне > 0 Тогда
            ДеталиИзШаблонов.ДобавитьТерм(ИспользованияШаблонов[К1], КоличествоВШаблоне);
        КонецЕсли;
    КонецЦикла;
    Модель.Ограничения().ЗначениеБольшеИлиРавно(ДеталиИзШаблонов.ПолучитьВыражение(), Потребности[К]);
КонецЦикла;

6. Описание целевой функции

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

// Целевая функция: минимизируем общее количество заготовок
Модель.Минимизировать(Модель.Выражения().Сумма(ИспользованияШаблонов));

7. Решение модели

Вызовем метод Решить, чтобы запустить оптимизационный процесс. Полученный в ходе вычислений объект Решение используем далее для проверки и вывода результата.

// Решение модели
Решение = Модель.Решить();

8. Вывод результатов

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

// Вывод результатов
Если Решение.РешениеНайдено() Тогда
    ФорматВывода = "ЧДЦ=2; ЧН=0; ЧГ=0";
    
    ВсегоЗаготовок = 0;
    ОбщиеОтходы    = 0;
    ВсегоДеталей   = 0;
    
    Сообщение    = "Результаты раскроя материалов" + Символы.ПС + Символы.ПС;
    НомерШаблона = 0;
    
    Для К = 0 По Шаблоны.ВГраница() Цикл
        КоличествоИспользований = Решение.ЗначениеПеременной(ИспользованияШаблонов[К]);
        
        Если КоличествоИспользований > 0 Тогда
            НомерШаблона = НомерШаблона + 1;
            ВсегоЗаготовок = ВсегоЗаготовок + КоличествоИспользований;
            
            СоставШаблона 			  = "";
            СуммаДлин 				  = 0;
            КоличествоДеталейВШаблоне = 0;
            
            Для К1 = 0 По КоличествоДеталей - 1 Цикл
                Если Шаблоны[К][К1] > 0 Тогда
                    Для К2 = 1 По Шаблоны[К][К1] Цикл
                        Если Не ПустаяСтрока(СоставШаблона) Тогда
                            СоставШаблона = СоставШаблона + " + ";
                        КонецЕсли;
                        СоставШаблона 			  = СоставШаблона + Формат(ДлиныДеталей[К1], ФорматВывода) + " см";
                        СуммаДлин 				  = СуммаДлин + ДлиныДеталей[К1];
                        КоличествоДеталейВШаблоне = КоличествоДеталейВШаблоне + 1;
                    КонецЦикла;
                КонецЕсли;
            КонецЦикла;
            
            Отход        = ДлинаЗаготовки - СуммаДлин;
            ОбщиеОтходы  = ОбщиеОтходы + Отход * КоличествоИспользований;
            ВсегоДеталей = ВсегоДеталей + КоличествоДеталейВШаблоне * КоличествоИспользований;
            
            Сообщение = Сообщение + СтрШаблон("Шаблон %1:%2", НомерШаблона, Символы.ПС);
            Сообщение = Сообщение + СтрШаблон("  Количество использований: %1%2", Формат(КоличествоИспользований, ФорматВывода), Символы.ПС);
            Сообщение = Сообщение + СтрШаблон("  Состав: %1%2", СоставШаблона, Символы.ПС);
            Сообщение = Сообщение + СтрШаблон("  Использовано материала: %1 см%2", Формат(СуммаДлин, ФорматВывода), Символы.ПС);
            Сообщение = Сообщение + СтрШаблон("  Отход: %1 см%2", Формат(Отход, ФорматВывода), Символы.ПС);
            Сообщение = Сообщение + Символы.ПС;
        КонецЕсли;
    КонецЦикла;
    
    Эффективность = (1 - ОбщиеОтходы / (ВсегоЗаготовок * ДлинаЗаготовки)) * 100;
    
    Сообщение = Сообщение + "Итоги:" + Символы.ПС;
    Сообщение = Сообщение + СтрШаблон("Всего заготовок: %1%2", Формат(ВсегоЗаготовок, ФорматВывода), Символы.ПС);
    Сообщение = Сообщение + СтрШаблон("Всего деталей: %1%2", Формат(ВсегоДеталей, ФорматВывода), Символы.ПС);
    Сообщение = Сообщение + СтрШаблон("Общие отходы: %1 см%2", Формат(ОбщиеОтходы, ФорматВывода), Символы.ПС);
    Сообщение = Сообщение + СтрШаблон("Эффективность: %1%%%2", Формат(Эффективность, "ЧДЦ=1; ЧН=0; ЧГ=0"), Символы.ПС);
    
    Сообщить(Сообщение);        
Иначе
    Сообщить("Решение не найдено! Статус: " + Решение.Статус());		
КонецЕсли;

Полный код решения задачи

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

// Создаем линейную целочисленную модель
Модель = О2.Модели()
    .ЛинейнаяЦелочисленнаяМодель()
    .СоздатьМодель();

// Вводим данные
ДлинаЗаготовки = 97;
Потребности    = О2.Утилиты().МассивЧиселИзСтроки("12, 18, 8, 15, 10, 6");
ДлиныДеталей   = О2.Утилиты().МассивЧиселИзСтроки("23, 19, 31, 17, 29, 13");

// Генерируем шаблоны раскроя с одним типом деталей
Шаблоны 	      = Новый Массив();
КоличествоДеталей = ДлиныДеталей.Количество();

Для К = 0 По КоличествоДеталей - 1 Цикл
    Шаблон = Новый Массив();
    Для К1 = 0 По КоличествоДеталей - 1 Цикл
        Шаблон.Добавить(0);
    КонецЦикла;
    МаксимальноеКоличество = Цел(ДлинаЗаготовки / ДлиныДеталей[К]);
    Шаблон[К] = МаксимальноеКоличество;
    Шаблоны.Добавить(Шаблон);
КонецЦикла;

// Генерируем смешанные шаблоны с двумя типами деталей
Для К = 0 По КоличествоДеталей - 1 Цикл
    Для К1 = К + 1 По КоличествоДеталей - 1 Цикл
        МаксимальноеКоличествоК = Цел(ДлинаЗаготовки / ДлиныДеталей[К]);
        Для КоличествоК = 1 По МаксимальноеКоличествоК Цикл
            Остаток = ДлинаЗаготовки - КоличествоК * ДлиныДеталей[К];
            
            Если Остаток <= 0 Тогда
                Продолжить;
            КонецЕсли;
            
            КоличествоК1 = Цел(Остаток / ДлиныДеталей[К1]);
            
            Если КоличествоК1 > 0 Тогда
                Шаблон = Новый Массив();
                Для К2 = 0 По КоличествоДеталей - 1 Цикл
                    Шаблон.Добавить(0);
                КонецЦикла;
                
                Шаблон[К]  = КоличествоК;
                Шаблон[К1] = КоличествоК1;
                
                ШаблонСуществует = Ложь;
                Для Каждого СуществующийШаблон Из Шаблоны Цикл
                    Совпадает = Истина;
                    Для К2 = 0 По КоличествоДеталей - 1 Цикл
                        Если СуществующийШаблон[К2] <> Шаблон[К2] Тогда
                            Совпадает = Ложь;
                            Прервать;
                        КонецЕсли;
                    КонецЦикла;
                    
                    Если Совпадает Тогда
                        ШаблонСуществует = Истина;
                        Прервать;
                    КонецЕсли;
                КонецЦикла;
                
                Если НЕ ШаблонСуществует Тогда
                    Шаблоны.Добавить(Шаблон);
                КонецЕсли;
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;
КонецЦикла;

// Регистрируем переменные для количества использований каждого шаблона
ИспользованияШаблонов = Модель.МассивПеременныхДиапазона(
    Шаблоны.Количество(),
    0,
    1000
);

// Целевая функция: минимизируем общее количество заготовок
Модель.Минимизировать(Модель.Выражения().Сумма(ИспользованияШаблонов));

// Ограничение: удовлетворяем потребности в каждом типе деталей
Для К = 0 По КоличествоДеталей - 1 Цикл
    ДеталиИзШаблонов = Модель.Выражения().СоздатьПостроительВыражений();
    Для К1 = 0 По Шаблоны.ВГраница() Цикл
        КоличествоВШаблоне = Шаблоны[К1][К];
        Если КоличествоВШаблоне > 0 Тогда
            ДеталиИзШаблонов.ДобавитьТерм(ИспользованияШаблонов[К1], КоличествоВШаблоне);
        КонецЕсли;
    КонецЦикла;
    Модель.Ограничения().ЗначениеБольшеИлиРавно(ДеталиИзШаблонов.ПолучитьВыражение(), Потребности[К]);
КонецЦикла;

// Решение модели
Решение = Модель.Решить();

// Вывод результатов
Если Решение.РешениеНайдено() Тогда
    ФорматВывода = "ЧДЦ=2; ЧН=0; ЧГ=0";
    
    ВсегоЗаготовок = 0;
    ОбщиеОтходы    = 0;
    ВсегоДеталей   = 0;
    
    Сообщение    = "Результаты раскроя материалов" + Символы.ПС + Символы.ПС;
    НомерШаблона = 0;
    
    Для К = 0 По Шаблоны.ВГраница() Цикл
        КоличествоИспользований = Решение.ЗначениеПеременной(ИспользованияШаблонов[К]);
        
        Если КоличествоИспользований > 0 Тогда
            НомерШаблона = НомерШаблона + 1;
            ВсегоЗаготовок = ВсегоЗаготовок + КоличествоИспользований;
            
            СоставШаблона 			  = "";
            СуммаДлин 				  = 0;
            КоличествоДеталейВШаблоне = 0;
            
            Для К1 = 0 По КоличествоДеталей - 1 Цикл
                Если Шаблоны[К][К1] > 0 Тогда
                    Для К2 = 1 По Шаблоны[К][К1] Цикл
                        Если Не ПустаяСтрока(СоставШаблона) Тогда
                            СоставШаблона = СоставШаблона + " + ";
                        КонецЕсли;
                        СоставШаблона 			  = СоставШаблона + Формат(ДлиныДеталей[К1], ФорматВывода) + " см";
                        СуммаДлин 				  = СуммаДлин + ДлиныДеталей[К1];
                        КоличествоДеталейВШаблоне = КоличествоДеталейВШаблоне + 1;
                    КонецЦикла;
                КонецЕсли;
            КонецЦикла;
            
            Отход        = ДлинаЗаготовки - СуммаДлин;
            ОбщиеОтходы  = ОбщиеОтходы + Отход * КоличествоИспользований;
            ВсегоДеталей = ВсегоДеталей + КоличествоДеталейВШаблоне * КоличествоИспользований;
            
            Сообщение = Сообщение + СтрШаблон("Шаблон %1:%2", НомерШаблона, Символы.ПС);
            Сообщение = Сообщение + СтрШаблон("  Количество использований: %1%2", Формат(КоличествоИспользований, ФорматВывода), Символы.ПС);
            Сообщение = Сообщение + СтрШаблон("  Состав: %1%2", СоставШаблона, Символы.ПС);
            Сообщение = Сообщение + СтрШаблон("  Использовано материала: %1 см%2", Формат(СуммаДлин, ФорматВывода), Символы.ПС);
            Сообщение = Сообщение + СтрШаблон("  Отход: %1 см%2", Формат(Отход, ФорматВывода), Символы.ПС);
            Сообщение = Сообщение + Символы.ПС;
        КонецЕсли;
    КонецЦикла;
    
    Эффективность = (1 - ОбщиеОтходы / (ВсегоЗаготовок * ДлинаЗаготовки)) * 100;
    
    Сообщение = Сообщение + "Итоги:" + Символы.ПС;
    Сообщение = Сообщение + СтрШаблон("Всего заготовок: %1%2", Формат(ВсегоЗаготовок, ФорматВывода), Символы.ПС);
    Сообщение = Сообщение + СтрШаблон("Всего деталей: %1%2", Формат(ВсегоДеталей, ФорматВывода), Символы.ПС);
    Сообщение = Сообщение + СтрШаблон("Общие отходы: %1 см%2", Формат(ОбщиеОтходы, ФорматВывода), Символы.ПС);
    Сообщение = Сообщение + СтрШаблон("Эффективность: %1%%%2", Формат(Эффективность, "ЧДЦ=1; ЧН=0; ЧГ=0"), Символы.ПС);
    
    Сообщить(Сообщение);        
Иначе
    Сообщить("Решение не найдено! Статус: " + Решение.Статус());		
КонецЕсли;

  Скачать пример