Задачу линейного раскроя можно решать разными способами: 1. Полный перебор, как правило, не возможно реализовать в реальных условиях. 2. Самый эффективный способ - целочисленное линейное программирование (метод Гомори, как целочисленный вариант симплекс-метода). В качестве инструмента можно использовать Solver из MS Excel. Но здесь есть ряд ограничений - необходимо найти все варианты сложения исходных деталей, не превышающих размер заготовок (а вариантов может быть несколько тысяч или сотен тысяч). Ограничение Solver'a - 200 изменяемых ячеек. 3. "Жадный" алгоритм. У данного алгоритма есть вариации, основное достоинство - высокая скорость. Применим для быстрой оценки раскроя, либо когда скорость важнее оптимизации. 4. Решать как частный случай задачи о рюкзаке (сумма подмножеств) и выбор наилучшего варианта из имеющихся. 5. Про генетический алгоритм ничего сказать не могу, т.к. не изучал его.
Реализовал собственный алгоритм линейного раскроя в Excel, который основан на решении задачи о рюкзаке (сумма подмножеств) методом целочисленного динамического программирования. Производится генерация различных вариантов раскроя в зависимости от сортировки исходных деталей и заготовок и выбор наилучшего решения. К достоинству можно отнести - достаточно эффективный результат по сравнению с "жадным" алгоритмом, а также при сравнении с результатом других программ линейного раскроя.
Сравнительные тесты различных специализированных программ линейного раскроя применительно к оконному производству проводилось здесь: http://forum-okna.ru/index.php?showtopic=35118 Применяемый мной алгоритм обошел все специализированные программы.
Дополнительно реализовал решение с помощью линейного программирования. Вначале производится генерация рациональных схем раскроя, затем симплекс-методом находим решение системы, данное решение является оптимальным (использование наименьшего количества заготовок). Далее сводим задачу к максимизации полезного остатка.
Domo -версию программы можно скачать здесь или здесь, она полностью функциональна, доступен расчет с помощью динамического программирования (DP). Расчет с помощью линейного программирования (LP) отключен. Также отключена возможность составления и экспорта отчетов.
Можно использовать до 20 различных размеров заготовок и до 90 различных размеров деталей. Есть возможность задать ширину реза, размер торцевой кромки, размер полезного (делового) остатка, возможность раскраивать в два профиля (если это требуется)
Можно убедиться в эффективности алгоритма раскроя в сравнении с другими программами. Если будет заинтересованность в алгоритме или потребуется адаптация отчета под ваши требования, то можете обратиться ко мне в личку.
UPDATE, декабрь 2021 PS: В связи с нехваткой свободного времени на адаптацию программы по линейному раскрою для нужд всех желающих, а также с учетом отсутствия личной мотивации в этом, выкладываю ссылку на рабочую программу с открытым кодом: https://disk.yandex.ru/d/wLjg9aMUpoGtLw Реализованы разные алгоритмы по раскрою Тем, кто знаком с VBA, не трудно будет внести изменение в код, если функционала текущей версии недостаточно. Либо можно воспользоваться веткой фриланс на данном форуме, где специалисты за разумную оплату смогут реализовать все хотелки. Для дальнейшего продолжения темы по раскрою есть моя реализация двумерной упаковки (раскроя) в полуограниченную полосу с использованием линейного программирования: http://www.excelworld.ru/forum/3-48430-1
PPS: Если программа по раскрою окажется полезной и возникнет непреодолимое желания меня отблагодарить, то не откажусь от любого доната ЯД: 410012329135704
UPDATE, апрель 2022 Выкладываю небольшой калькулятор с примерами, который работает в 3х режимах (быстро, медленно и очень медленно) т.к. используется внешняя dll, то будет работать только в Excel 32бит
Задачу линейного раскроя можно решать разными способами: 1. Полный перебор, как правило, не возможно реализовать в реальных условиях. 2. Самый эффективный способ - целочисленное линейное программирование (метод Гомори, как целочисленный вариант симплекс-метода). В качестве инструмента можно использовать Solver из MS Excel. Но здесь есть ряд ограничений - необходимо найти все варианты сложения исходных деталей, не превышающих размер заготовок (а вариантов может быть несколько тысяч или сотен тысяч). Ограничение Solver'a - 200 изменяемых ячеек. 3. "Жадный" алгоритм. У данного алгоритма есть вариации, основное достоинство - высокая скорость. Применим для быстрой оценки раскроя, либо когда скорость важнее оптимизации. 4. Решать как частный случай задачи о рюкзаке (сумма подмножеств) и выбор наилучшего варианта из имеющихся. 5. Про генетический алгоритм ничего сказать не могу, т.к. не изучал его.
Реализовал собственный алгоритм линейного раскроя в Excel, который основан на решении задачи о рюкзаке (сумма подмножеств) методом целочисленного динамического программирования. Производится генерация различных вариантов раскроя в зависимости от сортировки исходных деталей и заготовок и выбор наилучшего решения. К достоинству можно отнести - достаточно эффективный результат по сравнению с "жадным" алгоритмом, а также при сравнении с результатом других программ линейного раскроя.
Сравнительные тесты различных специализированных программ линейного раскроя применительно к оконному производству проводилось здесь: http://forum-okna.ru/index.php?showtopic=35118 Применяемый мной алгоритм обошел все специализированные программы.
Дополнительно реализовал решение с помощью линейного программирования. Вначале производится генерация рациональных схем раскроя, затем симплекс-методом находим решение системы, данное решение является оптимальным (использование наименьшего количества заготовок). Далее сводим задачу к максимизации полезного остатка.
Domo -версию программы можно скачать здесь или здесь, она полностью функциональна, доступен расчет с помощью динамического программирования (DP). Расчет с помощью линейного программирования (LP) отключен. Также отключена возможность составления и экспорта отчетов.
Можно использовать до 20 различных размеров заготовок и до 90 различных размеров деталей. Есть возможность задать ширину реза, размер торцевой кромки, размер полезного (делового) остатка, возможность раскраивать в два профиля (если это требуется)
Можно убедиться в эффективности алгоритма раскроя в сравнении с другими программами. Если будет заинтересованность в алгоритме или потребуется адаптация отчета под ваши требования, то можете обратиться ко мне в личку.
UPDATE, декабрь 2021 PS: В связи с нехваткой свободного времени на адаптацию программы по линейному раскрою для нужд всех желающих, а также с учетом отсутствия личной мотивации в этом, выкладываю ссылку на рабочую программу с открытым кодом: https://disk.yandex.ru/d/wLjg9aMUpoGtLw Реализованы разные алгоритмы по раскрою Тем, кто знаком с VBA, не трудно будет внести изменение в код, если функционала текущей версии недостаточно. Либо можно воспользоваться веткой фриланс на данном форуме, где специалисты за разумную оплату смогут реализовать все хотелки. Для дальнейшего продолжения темы по раскрою есть моя реализация двумерной упаковки (раскроя) в полуограниченную полосу с использованием линейного программирования: http://www.excelworld.ru/forum/3-48430-1
PPS: Если программа по раскрою окажется полезной и возникнет непреодолимое желания меня отблагодарить, то не откажусь от любого доната ЯД: 410012329135704
UPDATE, апрель 2022 Выкладываю небольшой калькулятор с примерами, который работает в 3х режимах (быстро, медленно и очень медленно) т.к. используется внешняя dll, то будет работать только в Excel 32битMCH
MCH, уважаемый! Поделитесь кодом создания отчетов, дорабатываю сейчас плагин Sketchup http://oldbridgesoft.com/steelsketch.html и хотел вставить туда расчет раскроя, веса, метража, стоимости и выводить все в ГОСТовские шаблоны. Ссылку на вашу программу гарантирую. Все перечисленное выше уже реализовал в вашей демке, за что вам огромное спасибо. теперь осталось перенести код VBA в код Ruby и отладить. За ранее благодарен за понимание.
MCH, уважаемый! Поделитесь кодом создания отчетов, дорабатываю сейчас плагин Sketchup http://oldbridgesoft.com/steelsketch.html и хотел вставить туда расчет раскроя, веса, метража, стоимости и выводить все в ГОСТовские шаблоны. Ссылку на вашу программу гарантирую. Все перечисленное выше уже реализовал в вашей демке, за что вам огромное спасибо. теперь осталось перенести код VBA в код Ruby и отладить. За ранее благодарен за понимание.SilverVG
Задача, что бы excel (Ваш скрипт) пронумеровал строки которые влезают в заданную длину кабеля в бухте с наименьшим остатком. Отрезков кабеля может быть больше 1000 штук (В вашем Demo влезло только 90 позиций)
Задача, что бы excel (Ваш скрипт) пронумеровал строки которые влезают в заданную длину кабеля в бухте с наименьшим остатком. Отрезков кабеля может быть больше 1000 штук (В вашем Demo влезло только 90 позиций)Exclus
Сообщение отредактировал Exclus - Суббота, 10.09.2016, 15:15
Доброго дня ночи. Ищу решение реализованное в excel
Задача: Дан рулон стали толщиной 0.5 мм с раскроем 1250 или иным раскроем и толщиной. Необходимо порезать рулон оцинкованной стали в ленту-штрипс различной ширины. Обрезь по краям заготовки в зависимости от станка резки от 2 до 8 мм. Необходимо рассчитать оптимальную порезку в ленту-штрипс с минимальными потерями на обрезь, а также оптимальную ширину заготовки для подобной задачи. Лента: 312мм, 416мм, 112мм (например)
А также рассчитать стоимость за 1 тонну и 1 метра погонного ленты штрипс. (Рассчет стоимости мне понятен как сделать, а вот создать алголритм подбора оптимальных ширин лент для карты раскроя пока не могу) Может кто на мысль натолкнет? или пример такого расчета есть?
Юрий zavod_profil@mail.ru
Доброго дня ночи. Ищу решение реализованное в excel
Задача: Дан рулон стали толщиной 0.5 мм с раскроем 1250 или иным раскроем и толщиной. Необходимо порезать рулон оцинкованной стали в ленту-штрипс различной ширины. Обрезь по краям заготовки в зависимости от станка резки от 2 до 8 мм. Необходимо рассчитать оптимальную порезку в ленту-штрипс с минимальными потерями на обрезь, а также оптимальную ширину заготовки для подобной задачи. Лента: 312мм, 416мм, 112мм (например)
А также рассчитать стоимость за 1 тонну и 1 метра погонного ленты штрипс. (Рассчет стоимости мне понятен как сделать, а вот создать алголритм подбора оптимальных ширин лент для карты раскроя пока не могу) Может кто на мысль натолкнет? или пример такого расчета есть?
скинте мне на почту (m-ch собака mail.ru) более подробно описанную задачу с указанием какие есть потребности и сколько нужно изготовить лент и какого размера
скинте мне на почту (m-ch собака mail.ru) более подробно описанную задачу с указанием какие есть потребности и сколько нужно изготовить лент и какого размераMCH
Целочисленное линейное программирование не может дать результат в 1065, у Вас же кол-во повторов - дробные Кроме того, обратите внимание, что у меня максимизирован остаток от последней заготовки
Целочисленное линейное программирование не может дать результат в 1065, у Вас же кол-во повторов - дробные Кроме того, обратите внимание, что у меня максимизирован остаток от последней заготовкиMCH
Просто вы говорили о линейное программирование, а не о линейном целочисленном программирование. Обычно эти понятия разделяют ))). Вы используете точную модель решения задачи линейного раскроя ?
Просто вы говорили о линейное программирование, а не о линейном целочисленном программирование. Обычно эти понятия разделяют ))). Вы используете точную модель решения задачи линейного раскроя ?kvmail
Вы используете точную модель решения задачи линейного раскроя ?
Я использую собственные наработки для решения задачи линейного раскроя (конечно после изучения работ других авторов, используя их методологию и собственные решения) В линейном программировании в условиях поиска решения ставлю ограничения, что нужно раскроить не менее заданного количества деталей и что решение должно быть целочисленным
Вы используете точную модель решения задачи линейного раскроя ?
Я использую собственные наработки для решения задачи линейного раскроя (конечно после изучения работ других авторов, используя их методологию и собственные решения) В линейном программировании в условиях поиска решения ставлю ограничения, что нужно раскроить не менее заданного количества деталей и что решение должно быть целочисленнымMCH