Линейный раскрой в Excel

Опубликовано 02 Дек 2015
Рубрика: Справочник Excel | 20 комментариев



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

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

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

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

Метод индексов Л.В. Канторовича и В.А. Залгаллера при определенном навыке позволяет «вручную» без использования вычислительной техники эффектно выполнять линейный раскрой. Любопытным читателям рекомендую с этим методом ознакомиться, прочитав книгу вышеназванных авторов «Рациональный раскрой промышленных материалов».

Симплекс-метод, основанный на идеях Л.В. Канторовича, был описан и детально разработан рядом ученых  из США в середине 20 века. Надстройка MS Excel «Поиск решения» (Solver) использует этот алгоритм. Именно с помощью этого метода и Excel мы будем в этой статье решать задачу линейного раскроя.

Позже появились и получили развитие генетический, жадный и муравьиный алгоритмы. Однако, ограничимся их перечислением и перейдем к делу, не забираясь в дебри теорий (хотя там, «в дебрях», очень интересно).

Включим Excel и на простом примере порезки металлических стержней на детали познакомимся с одним из способов решения практических задач линейного раскроя. Часто математики эту задачу называют «задачей о распиле».

Исходные данные для примера я не стал придумывать, а взял из статьи Покровского М.А. «Минимизация неизбежных потерь материалов в промышленном производстве при их раскрое на штучные заготовки» опубликованной в №5 (май 2015)  электронного научно-технического журнала «Инженерный вестник» издаваемого ФГБОУ ВПО «МГТУ им. Н.Э. Баумана» (ссылка: engbul.bmstu.ru/doc/775784.html).

Цель, которую я преследовал – сравнить полученные результаты решения задачи.

Пример решения задачи линейного раскроя в MS Excel.

Договоримся, что:

1. Заготовки – это исходный материал в виде прутков, полос, стержней и т.д. одинаковой длины.

2. Детали – это элементы, которые необходимо получить, разрезав исходные заготовки на части.

3. Ширина пила, реза, руба принята равной нулю.

Условие задачи:

Для комплектации одного из заказов заготовительный участок должен порубить на комбинированных ножницах из одинаковых прутков-заготовок длиной 1500 мм три типоразмера деталей:

151 штуку длиной 330 мм

206 штук длиной 270 мм

163 штуки длиной 190 мм

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

Исходные данные:

1. Длину исходных заготовок Lз в миллиметрах записываем в объединенную ячейку

D3E3F3: 1500

2. Присваиваем номера i всем типоразмерам деталей, начиная от самой длинной и заканчивая самой короткой в ячейках

D4; E4; F4: 1; 2; 3

3. Длины деталей Lдi в миллиметрах пишем в

D5; E5; F5: 330; 270; 190

4. Количество деталей Nдi в штуках заносим в

D6; E6; F6: 151; 206; 163

5.Приступаем к очень важному этапу – заполнению вариантов раскроев.

Необходимо запомнить и понять 2 принципа выполнения  этой работы.

1. Длины отходов должны быть меньше самой маленькой детали (0<Loj<Lдmin).

2. «Укладку» деталей в заготовку начинаем с самых больших деталей и с самого большого их количества, последовательно двигаясь в сторону уменьшения.

Если какого-нибудь типоразмера деталей в варианте раскроя нет, то ячейку оставляем пустой, ноль писать не будем для облегчения визуального восприятия таблицы.

Вариант раскроя №1:

Попытка выкроить из одной заготовки 5 деталей №1 невозможна, поэтому пишем в ячейку

D7: 4



Добавить в раскрой деталь №2 или деталь №3 также невозможно, поэтому оставляем пустыми ячейки

E7 и F7:

Вариант раскроя №2:

Уменьшаем на 1 от предыдущего варианта количество деталей №1 и записываем в

D8: 3

Пробуем добавить 2 детали №2 – не получается, поэтому дополняем в

E8: 1

Остается возможность дополнить раскрой деталью №3. Заносим в

F8: 1

Придерживаясь озвученных принципов, заполняем по аналогии все возможные в данном случае 18 вариантов раскроев.

Сделав пару-тройку таблиц вариантов раскроев самостоятельно, вы уясните логику действий и будете тратить считанные минуты на эту работу.

Если при раскрое не выполняется первый принцип, то ячейка с длиной отхода автоматически окрашивается в красный цвет. Условное форматирование, примененное к ячейкам G7…G24, наглядно поможет вам в этой работе.

В ячейках H7…H24 ничего не пишем! Они используются для вывода результата решения!

Линейный раскрой в Excel -1-26s

Прошу уважающих труд автора скачать файл с примером после подписки на анонсы статей. Подписные окна расположены в конце статьи и наверху страницы.

Ссылка на скачивание файла с примером: lineynyy-raskroy-v-excel (xls 38,5KB).

Подготовка к решению:

* В ячейках G7…G24 вычисляются длины отходов (обрезков), остающиеся в результате выполнения раскроев, по формуле

Loj=LзΣ(Lдi*Nдij)

6. Количество деталей каждого типоразмера, изготовленных по всем примененным вариантам раскроя, будут подсчитываться в ячейках D26, E26 и F26 по формуле

Nдiрасч=Σ(Nдij*Nзj)

Количество деталей в найденном в конце решения плане раскроя должно полностью соответствовать заданному количеству деталей!

7. Необходимое число заготовок для выполнения оптимального плана раскроя будет определяться в объединенной ячейке D27E27F27 по формуле

Nзрасч=ΣNзj

8. Общая длина всех заготовок, необходимых чтобы выполнить линейный раскрой всех деталей будет подсчитываться в объединенной ячейке D28E28F28 по формуле

LзΣ= Lз*Nзрасч

9. Общая длина всех отходов, получаемых при выполнении найденного плана раскроя, будет считаться в объединенной ячейке D29E29F29 по формуле

LоΣ= Σ(Lоj*Nзj)

10. Доля отходов, полученных при выполнении оптимального плана линейного раскроя от общего количества использованного материала, будет вычисляться в объединенной ячейке D30E30F30 по формуле

Ωo=Σ/Σ

Решение:

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

1. Выбираем в главном меню «Сервис» -  «Поиск решения…».

2. В появившемся одноименном окне  «Поиск решения» производим настройки.

2.1. Назначаем целевой функцией общую длину отходов Σ и вводим ссылку в окно целевой ячейки.

2.2. Устанавливаем переключатель «Равной:» в положение «минимальному значению».

2.3. Указываем ячейки с переменными j в окне «Изменяя ячейки».

2.4. Вводим ограничения в одноименное окно. В качестве условий указываем необходимость равенства заданного i и расчетного iрасч количества деталей, а так же на переменныеj – расчетное количество заготовок по вариантам раскроев – накладываем ограничение: это должны быть целые числа.

poisk-resheniya-26s

3. Нажимаем кнопку «Параметры» и в выпавшем окне  «Параметры поиска решения» выполняем  настройки так, как показано на следующем скриншоте. Закрываем окно кнопкой «ОК».

parametry-poiska-resheniya-26s

4. В окне «Поиск решения» нажимаем кнопку «Выполнить» и ждем, пока Excel найдет решение. Это может длиться несколько минут.

rezultaty-poiska-resheniya-26s

5. После сохранения найденного решения кнопкой «ОК», результаты отобразятся в ячейках  H7...H24 на листе Excel.

На следующей картинке показан найденный оптимальный линейный раскройный план.

raskroynyy-plan-№1-26s

Что в итоге?

Линейный раскрой в Excel заготовок для задач подобных рассмотренной в этой статье выполняется описанным выше методом за 10-15 минут! «Вручную», не зная метод индексов Канторовича, за такое время решения не найдешь.

Запустив «Поиск решения» несколько раз при разных параметрах поиска, удалось найти 5 различных планов рубки заготовок. Все 5 планов требуют одинаковое число заготовок – 93 и дают отходов всего 2,21%!!! Эти планы почти на 6% лучше, чем план, рассчитанный Покровским и более чем на 10% экономичнее «Традиционного» плана (смотри ссылку на первоисточник в первой части статьи). Очень достойный результат достигнут быстро и без применения дорогостоящих программ.

kolichestvo-zagotovok-po-planam-i-raskroyam-26s

Следует заметить, что надстройка Excel Solver («Поиск решения»), использующая симплекс-метод при решении задач линейного программирования, может работать не более чем с 200 переменными. В приложении к рассмотренной нами задаче линейного раскроя это означает, что количество раскроев не может превышать 200 вариантов. Для простых задач этого достаточно. Для более сложных задач следует попробовать применить «смесь» «жадного» алгоритма и симплексного метода Solver, отобрав из полного списка раскроев не более 200 самых экономичных. Далее запасаемся терпением и добиваемся результатов. Можно попытаться разбить сложную задачу на несколько простых, но «уровень оптимальности» найденного решения будет при этом, скорее всего, ниже.

Может быть, рассмотренный вариант решения вопросов линейного раскроя и не «высший пилотаж», но однозначно шаг вперед по сравнению с «традиционным» подходом на многих производствах.

Использование надстройки MS Excel «Поиск решения» (Solver) было на блоге уже однажды рассмотрено в статье «Бак для воды? «Поиск решения» в Excel!». Думаю, что этот замечательный инструмент достоин пристального внимания и еще не раз поможет изящно и быстро решить ряд новых нетривиальных задач.

P.S. Ссылки на лучшие из бесплатных программ линейного раскроя, найденных мной в Сети:

http://stroymaterial-buy.ru/raschet/70-raskroy-lineynih-izdeliy.html

http://forum-okna.ru/index.php?app=core&module=attach&section=attach &attach_id=7508

Программы по первым двум ссылкам решают рассмотренную задачу, используя 94 заготовки. Первая программа на  других тестах показала чуть лучшие результаты, чем вторая.

http://forum.dwg.ru/attachment.php?attachmentid=114501&d=13823277 74

http://www.planetcalc.ru/917/

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

Ниже статьи в блоке «Отзывы» можете написать свои  комментарии, уважаемые читатели.

Другие статьи автора блога

На главную


Введите Ваш e-mail:

Статьи с близкой тематикой

Отзывы

20 комментариев на «Линейный раскрой в Excel»

  1. Артур 03 Дек 2015 00:14

    Интересная тема, Александр.

    В работе часто пригождается. с радостью изучу.

  2. Роман 03 Дек 2015 13:26

    Прекрасная работа, спасибо!

    SVAI-PLUS.COM

  3. Михаил 03 Дек 2015 13:29

    Спасибо! Очень интересно!

  4. Анатолий 03 Дек 2015 16:39

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

  5. MichaelCH 07 Дек 2015 15:39

    Тема линейного раскроя достаточно интересная, для себя решил двумя способами:

    1. Использование линейного программирования. Способ аналогичен тому, что здесь описан и является самым эффективным.

    Разбивается на два этапа: генерация рациональных (оптимальных по Паретто) схем раскроя, и дальнейшее построение модели и ее решение целочисленным симплекс методом.

    Можно использовать заготовки разного размера с ограничением или без ограничения их количества.

    При этом основной упор делается при прочих равных условиях на максимизацию «полезного» остатка.

    2й способ — решение как частный случай «задачи о рюкзаке» («сумма подмножеств»), в случае когда рюкзаков много. В основе решения динамическое программирование.

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

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

  6. Александр Воробьев 07 Дек 2015 16:03

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

    Так как это было достаточно давно, то сегодня было бы интересно разобраться с возможностями и сферой применения «новых» алгоритмов — «генетического» и «муравьиной колонии».

  7. MichaelCH 07 Дек 2015 16:38

    Относительно «генетического» и «муравьиного» алгоритма.

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

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

    «Генетический» алгоритм хорошо себя зарекомендовал для двухмерного раскроя. Думаю, что другого эффективного метода для 2D-раскроя не найти (полный перебор не применим на практике). Раскрой будет зависеть на сколько качественно реализованы мутации.

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

    PS. Александр, а Вы используете на практике линейный раскрой? Хочу предложить сравнить разные алгоритмы на реальных данных.

  8. MichaelCH 08 Дек 2015 12:19

    Относительно раскроя указанных данных.

    Их можно раскроить используя 93 заготовки.

    Вариант 1. Максимизация полезного остатка:

    330*2 + 270 + 190*3 = 1500 (42 повторения), остаток — 0

    330*2 +270*3 = 1470 (32 повторения), остаток — 30

    270*4 + 190*2 = 1460 (17 повторений), остаток — 40

    330*3 + 190*2 = 1370 (1 повторение), остаток — 130

    190 = 190 (1 повторение), остаток — 1310

    Использовано 5 различных вариантов схем раскроя, удалось сохранить полезный остаток размером 1310мм

    отходы (за вычетом полезного остатка) составили 0*42 + 30*32 + 40*17 + 130 = 1770мм, что составляет 1,27% от размера заготовок

    Вариант 2. Минимизация количества переходов:

    330*2 + 270 + 190*3 = 1500 (27 повторений), остаток — 0

    270*2 + 190*5 = 1490 (17 повторений), остаток — 10

    330*2 + 270*3 = 1470 (49 повторений), остаток — 30

    В результате получилось деталей чуть больше, чем требовалось:

    330мм — 152шт (+1)

    270мм — 208шт (+2)

    190мм — 166шт (+3)

    При этом используется всего три различных варианта раскроя.

  9. Александр Воробьев 08 Дек 2015 18:04

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

    PS: MichaelCH, мы используем, хотя и нерегулярно, линейный раскрой. Предложение по сравнению алгоритмов, конечно, принимается.

  10. MichaelCH 08 Дек 2015 19:52

    Решение получил собственной реализацией задачи раскроя линейным программированием. Максимизация «полезного» остатка заложено в алгоритме.

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

    С другой стороны, какая разница получаются ли дополнительные детали или нет.

    Общее кол-во заготовок — 93шт, суммарный размер всех заготовок — 93*1500 = 139500мм

    необходимо получить детали: 330*151 + 270*206 + 190*163 = 136420мм

    общие отходы составят 139500-136420 = 3080мм или 2,21% (3080/139500 = 0,0221)

    В разных производствах по разному относятся к отходам и переналадке.

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

    А, например, при раскрое рулонов пленки, уже не так важно, получаются ли остатки, все обрезки являются отходом. Важным фактором является именно переналадка (перестановка ножей), т.к. эта процедуры достаточно трудоемкая.

    Смогу подробнее ответить на Ваши вопросы по скайпу или почте (m-ch собака mail.ru)

  11. Артем 29 Янв 2016 15:20

    Добрый день

    оптимальный линейный раскройный план как получить визуально картинкой

    Спасибо

  12. Александр Воробьев 30 Янв 2016 11:52

    Картинку раскроя можно нарисовать в любом графическом редакторе или CAD-программе. Можно нарисовать и в Excel. (И не такое люди рисуют!!!).

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

  13. Артем 30 Янв 2016 16:11

    Спасибо за ответ

    теперь ясно

  14. MichaelCH 07 Фев 2016 17:26

    Выложил демо-версию своей программы: excelworld.ru/forum/3-21304-1

  15. AstraRaskroy 04 Июл 2016 18:16

    А вы бы могли привести пример решения в Excel e задачки из книги Синдром стога сена Голдратта?

    (astraraskroy.ru)

  16. Александр Воробьев 04 Июл 2016 19:17

    «Мы, ето, из комендатуры... И, ето, мы бы, конечно, могли бы, но нам по Уставу не положено...» /В августе 44-ого/.

    Кому интересно — почитайте у Сергея Викторовича Багузина:

    baguzin.ru/wp/wp-content/uploads/2013/09/Э.Голдратт. -Синдром-стога-сена.pdf

    Авторам вопроса, я думаю, ответ не нужен.

  17. Алексей Алимпиев 27 Сен 2016 21:48

    «forum.dwg.ru/attachment.php?attachmentid=114501&d=13823277 74»

    этот надо контролировать — тестировал его ранее, выдает при большом количестве деталей глюки: повторные строки и т.п.

  18. Александр Воробьев 28 Сен 2016 07:55

    Спасибо за информацию, Алексей.

  19. MichaelCH 30 Сен 2016 12:26

    В файле RASKROY_GRUPP.xls используется «жадный» алгоритм, который крайне не эффективный на большом количестве деталей

  20. Борис 13 Окт 2016 11:09

    Спасибо. Полезно, понятно. Борис.

Ваш отзыв







  • Посетители: 656 202

  • Подписчики: 3 414