Задача оптимального раскроя линейных материалов (профиля, труб, арматуры) является классической математической проблемой, известной как Cutting Stock Problem. Ее суть заключается в том, чтобы из имеющихся заготовок стандартной длины нарезать детали нужных размеров так, чтобы количество отходов было минимальным. В этой статье мы подробно разберем, как подступиться к решению этой задачи в среде 1С, изучим математическую базу и реализуем конкретный алгоритм подбора.
Прежде чем переходить к написанию кода, нам необходимо понять математическую сложность задачи. Если мы хотим перебрать абсолютно все варианты соединения кусков, мы сталкиваемся с комбинаторным взрывом.
Рассмотрим основные понятия, которые помогут нам в расчетах:
N уникальных элементов, то количество способов выстроить их в ряд равно N! (факториал). Например, для 5 деталей это 120 вариантов, а для 10 — уже более 3,6 миллионов.M элементов из N имеющихся с учетом их порядка, количество вариантов рассчитывается как N! / (N - M)!.N! / (M! * (N - M)!).Понимание этих принципов важно для оценки производительности: простой полный перебор всех вариантов на больших данных (например, 100 и более деталей) заставит программу 1С "задуматься" на очень долгое время. Поэтому мы будем использовать более эффективные методы.
Наиболее подходящим алгоритмом для реализации на встроенном языке 1С является метод ветвей и границ. Это вариация рекурсивного перебора, которая "отсекает" заведомо ложные ветви дерева решений (например, когда сумма длин кусков уже превысила длину хлыста).
Рассмотрим программную реализацию. Предположим, у нас есть обработка с табличной частью Метраж, где указаны имеющиеся куски и их характеристики. Нам нужно заполнить колонку НужноВзять.
Основная процедура запуска расчета:
Процедура КнопкаСформироватьНажатие(Кнопка)
// Подготавливаем рабочую таблицу на основе данных формы
РабочаяТаблица = Метраж.Выгрузить();
// Инициализируем колонку ответа
РабочаяТаблица.ЗаполнитьЗначения(0, "НужноВзять");
// Оптимизация: сортируем куски по убыванию коэффициента (длины)
// Это позволит быстрее находить крупные комбинации
РабочаяТаблица.Сортировать("Коэффициент Убыв");
// Запускаем рекурсивный поиск
ПодборКусков(РабочаяТаблица, РабочаяТаблица.Количество() - 1, Требуется);
КонецПроцедуры
Теперь разберем саму рекурсивную функцию ПодборКусков. Она будет перебирать варианты, пока не найдет комбинацию, максимально близкую к целевому значению Требуется.
Процедура ПодборКусков(РабочаяТаблица, ВГраница, ЗаданнаяСумма, УжеВзяли = 0) Экспорт
// Проверка выхода за границы или достижения цели
Если ЗаданнаяСумма = 0 Тогда
// Если сумма точно совпала, фиксируем решение в основной таблице
Ответ = РабочаяТаблица.Скопировать(, "НомерСтроки, НужноВзять");
Ответ.Сортировать("НомерСтроки");
Метраж.ЗагрузитьКолонку(Ответ.ВыгрузитьКолонку("НужноВзять"), "НужноВзять");
Возврат;
ИначеЕсли ВГраница < 0 Тогда
// Обошли все варианты в данной ветке и не нашли точного совпадения
Возврат;
КонецЕсли;
// Получаем текущий элемент для анализа
Курсор = РабочаяТаблица[ВГраница];
// Перебираем возможное количество использования данного типа куска
Для КолВо = 0 По Курсор.Имеется Цикл
// Проверяем, не превысим ли мы требуемую длину
Если (КолВо * Курсор.Коэффициент) <= ЗаданнаяСумма Тогда
Курсор.НужноВзять = КолВо;
// Рекурсивный вызов для следующего элемента
ПодборКусков(РабочаяТаблица, ВГраница - 1,
ЗаданнаяСумма - (КолВо * Курсор.Коэффициент),
УжеВзяли + КолВо);
// Очищаем значение для возврата по стеку (backtracking)
Курсор.НужноВзять = 0;
Иначе
Прервать; // Дальнейшее увеличение количества не имеет смысла
КонецЕсли;
КонецЦикла;
КонецПроцедуры
Проанализируем практические аспекты, которые часто забывают при теоретическом подходе к раскрою. Без их учета программа будет выдавать результаты, непригодные для реального производства:
ТолщинаПилы к длине каждой детали в расчетах.В зависимости от задач бизнеса, алгоритм может быть настроен на разные приоритеты:
1. Жадный алгоритм (First Fit Decreasing): Самый быстрый. Сортируем нужные детали от больших к меньшим. Берем первый хлыст и кладем туда всё, что влезет. Затем второй и т.д. Дает неплохой результат и работает мгновенно. Подходит для оперативной нарезки "на коленке".
2. Минимизация количества хлыстов: Цель — использовать как можно меньше целых палок профиля. Это важно, когда запасы материала ограничены.
3. Максимизация делового остатка: Иногда выгоднее оставить один кусок длиной 1500 мм (который можно продать или использовать), чем три по 500 мм (которые пойдут в переплавку). В этом случае алгоритм оценивает "полезность" остатка.
Поскольку 1С — это интерпретируемый язык, тяжелые вычисления могут замедлять работу системы. Если объем данных для раскроя велик (сотни и тысячи позиций), рекомендуется:
Рассмотренный метод ветвей и границ является отличным стартом для создания собственного модуля раскроя. Он сочетает в себе относительную простоту реализации на встроенном языке и высокую точность поиска решений для одномерных задач.