Расчет линейного раскроя в Excel

[tomeo]

Вопрос.
Стоит задача (очень насущная и трудоемкая - приходится постоянно выполнять) по раскрою линейного профиля материала (брус, прут, труба). Раскрой требуется выполнять с максимальной экономией материала (деловой отход также учитывается и идет в дело при раскрое). Алгоритм раскроя известен. Вот только очень трудоемко выполнять эту задачу, особенно, если попадается большой набор материала разной длины. Как я понимаю, задача чисто арифметическая - перебор значений для максимального заполнения всей длины заготовки. Возможно ли ее решить силами самого Excel? Или для этой задачи требуются ресурсы языка программирования (наподобие Visual Basic)?

Конечно, хотелось бы создать такую таблицу самому, для последующей шлифовки своими силами. Сам сделал таблицу, но она примитивная и выполняет только расчет и показ остатков материала при постепенном (вручную) его заполнении заготовками. Так что настоящего (можно сказать - самостоятельного) алгоритма раскроя моя таблица не имеет.

Перерыл весь Инет. Имеются готовые программы подобного рода, но все имеют один (или несколько недостатков) или работают ужасно. (Например, одна из них (RealCut) выполнила мою задачу - заготовки с обоими косыми углами разной величины нужно было накроить из материала - неправильно. Вывела результатом работы раскрой, где сочетание возможное равных углов заготовок не было учтено вообще, что привело к неэкономии материала. Переделал все вручную с гораздо большей экономией. Хотя в программе имеется инструмент для задания углов заготовки.) Все это делает их непригодными для моих конкретных условий.

Насколько понял из прочтений материалов на программистких форумах, задача из разряда линейного программирования и давно решена. Вот только решений не нашел готовых. А сам, своими силами программировать я не смогу - не хватает знаний и времени для восполнения этих знаний.

Подскажите, кто что знает по этому вопросу. Помощь очень нужна!

[Алексей Шмуйлович]

Да, задачка непростая. Сталкивался с ней, но уже давно. Подзабыл. У нас было несколько тем по раскрою. Введите в поисковое окошко слово "раскрой".

[tomeo]

Поиск по ключевому слову "раскрой" результатов не дал. Скачал архив форума (до 2008 года) - результат аналогичный. Жалко...

[Алексей Шмуйлович]

Поиск по ключевому слову "раскрой" результатов не дал. Скачал архив форума (до 2008 года) - результат аналогичный. Жалко...

Ну как же, я ведь проверил, прежде чем посоветовать. Конечно, полностью готового решения для excel, кажется, нет, но очень много аналогичных задач и есть ссылка на платную, но недорогую, программку. Вот, что я в течение пяти минут нашел на сайте:
http://www.cutting.com.ua/
https://forum.msexcel.ru/microsoft_excel/karta_raskroya-t1320.0.html
https://forum.msexcel.ru/microsoft_excel/summirovanie_znacheniy_kolonki_na_predmet_poiska_summy_chisel_ravnoy_x-t977.0.html
https://forum.msexcel.ru/microsoft_excel/vybrat_iz_stolbtsa_s_chislami_v_summe_maksimalno_priblizhennoe_k_zadannomu_chislu-t967.0.html
https://forum.msexcel.ru/microsoft_excel/nebolshie_problemmy_s_filtrom-t2463.0.html

[tomeo]

Спасибо за ссылки! (Вечно я тороплюсь...) Изучу их детально. Предмет нужный для меня.

[Алексей Шмуйлович]

tomeo, я из спортивного интереса написал небольшую программку для раскроя. Сразу оговорюсь - я математического алгоритма оптимизации для этой задачи не знаю, поэтому действовал наобум. Но результат меня устроил. Я постарался набор условных данных сделать максимально правдоподобным. В свое время я работал на производстве пластиковых окон. У нас отходы профиля доходили до 10-15 %. Итак я имитировал набор заготовок (около 2,5 тыс. шт) двух типоразмеров 700 +/- 100 мм - порядка 65% и 1400 +/- 100 мм - остальное. Это распределение привязано к среднестатистическому окну 1400 х 1400. Деловыми остатками считал остатки от 500 мм включительно. Процент отходов по моему алгоритму получается 1-3 %. Но нужно еще учитывать, что деловые остатки по длине вряд ли имеют нормальное распределение. По опыту, коротышки накапливаются гораздо быстрее, чем их удается использовать, так что приходится периодически устраивать чистку завалов. Отсюда реальный процент отходов гораздо выше.
И еще я не уверен, что время на поштучный учет деловых остатков не окажется дороже, чем сэкономленный профиль . Мы его так и не внедрили, хотя пытались (нас аудиторы и всякие проверяльщики на это пытались вынудить).

Итак, мой доморощенный алгоритм:
1. Вводим в таблицу номера всех заготовок в порядке убывания длины.
2. Для каждой заготовки, начиная с самой длинной, выбираем в таблице складских остатков самую короткую заготовку, из которой можно вырезать деталь.
3. Записываем сочетание в карту раскроя и уменьшаем длину складской заготовки на длину отрезанной детали.

Собственно все.

Прикладываю файл. Заполняйте два листа - Детали и Остатки и нажимайте кнопку Раскроить на листе Детали. По результатам откроется лист Карта раскроя, а состояние склада после раскроя можно найти на листе Остатки после раскроя.

Вы писали, что алгоритм раскроя известен. Если Вы опишите его, мне будет интересно попробовать его реализовать (если только не много времени потребуется).

[tomeo]

Здравствуйте, Алексей Шмуйлович.

Приложенного вами файлика не увидел. Хотя интересно было бы посмотреть.
Прилаживаю свою таблицу (о которой говорил ранее). Там есть готовые уже раскрои, выполненные мною на работе. Будут интересны как наглядный пример логики раскроя (надеюсь). Таблицы чуть подправил и добавил для объяснения самого процесса и вида карт раскроя.

Да, предложенный Вами алгоритм в целом именно таков. Попытаюсь объяснить его так, как он видится и делается мною.
1. На складе имеются заготовки опеределенной длины (перечень возможных размеров - 12 000мм, 9 000мм, 6 000мм). Кол-во заготовок роли не играет - считается, что их неограниченное колличество.
2. Нужно из одной длины (допустим, 12 000мм) заготовки накроить детали заданной длинны и колличества (к примеру, 7950мм - 33шт., 8590мм - 22шт., 2543мм - 22шт., 2542мм - 22шт.).
3. Берется самая длинная деталь и улаживается на заготовку. При этом стремится надо в к тому, чтобы уложилось целое их число, без остатка. И так далее - по нисходящей.
4. Если все же имеется остаток (тут играет роль и его длина - если это <= 250-300мм - то он не учитывается при дальнейшем расчете), этот остаток вычисляется от длины заготовки, и нужная недостающая длина отпиливается от новой заготовки (так как имеем дело с металлопрофилем, имеют место сварные швы детали, но не более одного шва на одной детали). Получается своеобразная цепочка. Одна из задач - сделать эту цепочку краткой (в приложенной таблице имеются примеры).

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

Основная трудоемкость и рутинность работы видится мною именно в нахождении оптимального разложения длин деталей (и их недостающих остатков) на материале с целью наиболее полного заполнения последнего.


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

Хотелось бы услышать Ваше мнение.

[Алексей Шмуйлович]

Да, виноват. Спешил на поезд и забыл файл приложить.
Бегло посмотрел Ваш файл. Конечно, косые резы все усложняют.
Ведь у меня в алгоритм перебор вариантов вообще не заложен - все построено на сортировке списка деталей по убыванию и использованию самой короткой заготовки из возможных. И в принципе работает. А тут, действительно, нужно перебирать. Единственное, что приходит пока в голову - осуществлять подбор для деталей с одинаковым углом реза отдельными группами. Тогда длину можно искусственно уменьшить на длину одной полки угла.
В общем, обдумайте. Если сможете дать формализованный алгоритм, может быть переделаем и программку.
А Вы на VBA совсем не программируете?

[tomeo]

К сожалению, на VBA не умею програмировать. Хотя есть начальные навыки программирования. Допустим, вложения по тем ссылкам, что Вы привели, открывал и пробовал анализировать. Что-то из исходного текста понимаю. Язык то, в общем, не сложный... Когда-то пытался Python самостоятельно изучать... :-)
Ну, это отступление от темы. Главное - самостоятельно написать подобную программу на VBA, к сожалению, мне не по силам...
Но желание автоматизировать (облегчить, исключить возможные ошибки и повысить скорость соей работы - целых 3 плюса!) у меня большое... :-)
А что значит - формализованный алгоритм? (Хотя, могу догадываться, что это)...

[Алексей Шмуйлович]

Ну, хотите текстом по шагам опишите действия, включая формулы расчета. Хотите, в виде блок-схемы. Плюс структура исходных данных и в каком виде нужнен результат. Как удобнее, только чтобы однозначно было понятно, что должна сделать программа. Тем более, что начальные навыки программирования есть

[Алексей Шмуйлович]

Посмотрите мой вариант. Может быть дополнить исходные данные параметрами углов? только я не понимаю, как их потом использовать.

[tomeo]

Хорошо. Постараюсь сделать это.

[Ruslan R]

Программа Optimize
Ссылка для скачивания: http://fs-bud.at.ua/Programma/Optimize/Optimize_Setup.rar

[MCH]

Задачу линейного раскроя можно решать разными способами:
1. Полный перебор, как правило, не возможно реализовать в реальных условиях.
2. Самый эффективный способ - целочисленное линейное программирование. В качестве инструмента можно использовать Solver.
Но здесь есть ряд ограничений - необходимо найти все варианты сложения исходных деталей, не превышающих размер заготовок (а вариантов может быть несколько тысяч или сотен тысяч). Ограничение Solver'a - 200 изменяемых ячеек.
3. "Жадный" алгоритм. У данного алгоритма есть вариации, основное достоинство - высокая скорость. Применим для быстрой оценки раскроя, либо когда скорость важнее оптимизации.
4. Решать как частный случай задачи о рюкзаке (сумма подмножеств) и выбор наилучшего варианта из имеющихся.
5. Генетический алгоритм и алгоритм муравьиной колонии. Ничего про эти алгоритмы сказать не могу, т.к. их не изучал.

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

Примеры получаемых раскроев можно посмотреть здесь: https://yadi.sk/d/B_fg089lhsMk4
Если будет заинтересованность в алгоритме, то можете обратиться ко мне в личку.

[MCH]

Demo-версию программы можно скачать здесь: http://www.excelworld.ru/forum/3-21304-1