В наличии имеется рабочая документация на фундамент, где указано сколько деталей из строительной арматуры и какой длины должны использоваться для армирования фундамента.
Ниже приведена сводная таблица для деталей из арматуры диаметром 12 мм.
l - длина детали в мм, L - сумма длин всех деталей данной длины, м.
Поставочная длина прута арматуры диаметром 12 мм - 11,7 м.
5496,63 / 11,7 = 469,8, таким образом, для получения нужного набора деталей (отрезков арматуры) количество прутьев длиной 11,7 м не может быть меньше 470 шт.
Задача - создать набор схем раскроя прутов арматуры 11,7 м, позволяющий получить детали длиной и в количестве, указанным в Табл. 1, при минимизации количества используемых прутов.
Программы, с помощью которых были получены приведённые ниже результаты представлены в [1].
За решением этой задачей я обратился к нейросети DeepSeek.
Нейросеть квалифицировала мою задачу как задачу одномерной упаковки (one-dimensional bin packing problem) и предложила реализацию на Python Улучшенного алгоритма одномерной упаковки (Best-Fit Decreasing). Т.к. речь идёт об алгоритме упаковки, то прут длиной 11,7 м рассматривался как контейнер длиной 11,7 м, в котором нужно разместить отрезки арматуры разной длины. Суть алгоритма:
1. Сортируем отрезки по убыванию длины.
2. Для каждого отрезка выбираем прут с наименьшим остатком, куда он помещается.
3. Если ни в один существующий прут отрезок не влезает, берём новый прут.
Скопировав в Jupyter Notebook (см. [1]) и запустив предложенный код, были полученные следующие результаты:
В строках приведены данные по каждой из предложенных 14 схем раскройки. Цифры в столбце каждого отрезка - количество отрезков данной длины. Например, согласно первой схеме раскройки прут 11,7 м разрезается на 3 отрезка длиной 3145 мм и один отрезок длиной 1990 мм, при этом остаётся остаток (отход) длиной 275 мм. По первой схеме нужно разрезать 90 прутов 11,7 м.
Если следовать предложенному набору схем раскройки, то на производство приведённого в Табл. 1 перечня деталей понадобится 486 прутов 11,7 м. Процент отходов - 3,33% или 3,16% если не учитывать в качестве отхода остаток длиной 9710 мм в 14-ой схеме. Качество оптимизации не впечатляет.
В чём причина такого средненького результата?
Алгоритм Best-Fit Decreasing относится к классу жадных алгоритмов.
Как работают жадные алгоритмы?
1. Разбивают задачу на шаги.
2. На каждом шаге выбирают лучший для текущего шага вариант ("здесь и сейчас") , полагая, что это приведёт к глобально оптимальному решению в конце.
3. Не откатываются назад (не пересматривают предыдущие решения).
В нашем случае алгоритм, например, не рассматривает сочетание длинных и коротких отрезков, т.к. дойдя до коротких отрезков он обнаруживает, что в контейнерах, где размещены длинные отрезки уже помещены средние отрезки и место для коротких остаётся немного. А может быть так, что оптимальными вариантами являются как раз сочетание длинных отрезков с короткими, но данные варианты недоступны.
Можно было бы попробовать изменить порядок следования отрезков и "разбавить" длинные отрезки короткими и средними, но это уже какое-то шаманство, а нам нужна точность и надёжность.
Найти точное решение задачи одномерной упаковки можно с помощью библиотеки PuLP (Python Unstructured Linear Programming Library) — библиотека линейного программирования на Python.
Проблема заключается в том, что решение нашей задачи (1790 отрезков) придётся ждать долго - возможно несколько суток.
После указания на тот факт, что несмотря на большое количество отрезков (1790) каждый из них является представителем одного из всего лишь 11 типов, DeepSeek переквалифицировал мою задачу из задачи одномерной упаковки в задачу раскроя (Cutting Stock Problem, CSP) и разработал алгоритм с использованием библиотеки OR-Tools от Google (устанавливается командой в консоли pip install ortools).
Данный алгоритм сначала создаёт набор шаблонов - все возможные комбинации из отрезков арматуры из табл. 1, суммарная длина которых не превышает 11,7 м (таких шаблонов оказалось 1015 шт.), а затем решает задачу минимизации требуемого количества прутов длиной 11,7 м.
Результаты работы программы:
На производство приведённого в Табл. 1 перечня деталей понадобится 474 прутов 11,7 м. Процент отходов - 0,89%. Если остатки по схемам раскройки 12 и 13 исключить из отходов в виду их значительных длин, то в этом случае процент отходов уменьшится до 0,68%.
Резюме
Даже не являясь специалистом в конкретной области, с помощью нейросети можно получить работающую программу, которая решит поставленную задачу. Главное - правильно классифицировать задачу.
Ссылки
1. Техническая часть данной статьи в формате Jupyter Notebook