Домашняя страница Undo Do New Save Карта сайта Обратная связь Поиск по форуму
МИР MS EXCEL - Гость.xls

Вход

Регистрация

Напомнить пароль

 

= Мир MS Excel/Линейный раскрой - Мир MS Excel

Старая форма входа
  • Страница 1 из 6
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • »
Модератор форума: _Boroda_, китин  
Мир MS Excel » Вопросы и решения » Готовые решения » Линейный раскрой (Excel)
Линейный раскрой
MCH Дата: Среда, 03.02.2016, 01:49 | Сообщение № 1
Группа: Админы
Ранг: Старожил
Сообщений: 2001
Репутация: 751 ±
Замечаний: ±

Задачу линейного раскроя можно решать разными способами:
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бит
К сообщению приложен файл: CSP_DLL.zip(411.4 Kb)
 
Ответить
СообщениеЗадачу линейного раскроя можно решать разными способами:
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
Дата добавления - 03.02.2016 в 01:49
SilverVG Дата: Четверг, 11.02.2016, 09:50 | Сообщение № 2
Группа: Заблокированные
Ранг: Прохожий
Сообщений: 3
Репутация: 0 ±
Замечаний: 40% ±

Excel 2010
MCH, уважаемый!
Поделитесь кодом создания отчетов, дорабатываю сейчас плагин Sketchup http://oldbridgesoft.com/steelsketch.html и хотел вставить туда расчет раскроя, веса, метража, стоимости и выводить все в ГОСТовские шаблоны. Ссылку на вашу программу гарантирую. Все перечисленное выше уже реализовал в вашей демке, за что вам огромное спасибо. теперь осталось перенести код VBA в код Ruby и отладить.
За ранее благодарен за понимание.
 
Ответить
СообщениеMCH, уважаемый!
Поделитесь кодом создания отчетов, дорабатываю сейчас плагин Sketchup http://oldbridgesoft.com/steelsketch.html и хотел вставить туда расчет раскроя, веса, метража, стоимости и выводить все в ГОСТовские шаблоны. Ссылку на вашу программу гарантирую. Все перечисленное выше уже реализовал в вашей демке, за что вам огромное спасибо. теперь осталось перенести код VBA в код Ruby и отладить.
За ранее благодарен за понимание.

Автор - SilverVG
Дата добавления - 11.02.2016 в 09:50
Eman Дата: Воскресенье, 28.02.2016, 05:08 | Сообщение № 3
Группа: Пользователи
Ранг: Прохожий
Сообщений: 1
Репутация: 0 ±
Замечаний: 0% ±

Excel 2003
MCH, здравствуйте!
Я по теме
http://www.excelworld.ru/forum/3-21304-1
Я правильно понял, что демо версией можно пользоваться без ограничений?

А как получить и сколько стоит полная версия файла?
прошу написать на 2919051@gmail.com
Спасибо
 
Ответить
СообщениеMCH, здравствуйте!
Я по теме
http://www.excelworld.ru/forum/3-21304-1
Я правильно понял, что демо версией можно пользоваться без ограничений?

А как получить и сколько стоит полная версия файла?
прошу написать на 2919051@gmail.com
Спасибо

Автор - Eman
Дата добавления - 28.02.2016 в 05:08
hbs-group Дата: Среда, 27.04.2016, 19:22 | Сообщение № 4
Группа: Пользователи
Ранг: Прохожий
Сообщений: 7
Репутация: 0 ±
Замечаний: 0% ±

Excel 2010
Мне бы тоже было бы интересно прошу написать на hbs-group@mail.ru
 
Ответить
СообщениеМне бы тоже было бы интересно прошу написать на hbs-group@mail.ru

Автор - hbs-group
Дата добавления - 27.04.2016 в 19:22
Anat Дата: Пятница, 06.05.2016, 13:53 | Сообщение № 5
Группа: Пользователи
Ранг: Прохожий
Сообщений: 1
Репутация: 0 ±
Замечаний: 0% ±

Excel 2007
MCH, меня тоже интересует, как можно получить полную версию и как с Вами связаться. Мой e-mail vikna_a@i.ua
 
Ответить
СообщениеMCH, меня тоже интересует, как можно получить полную версию и как с Вами связаться. Мой e-mail vikna_a@i.ua

Автор - Anat
Дата добавления - 06.05.2016 в 13:53
Asweb Дата: Среда, 03.08.2016, 12:21 | Сообщение № 6
Группа: Пользователи
Ранг: Прохожий
Сообщений: 1
Репутация: 0 ±
Замечаний: 0% ±

Excel 2010
MCH, добрый день. Напишите цену на почту apparit@mail.ru , спасибо.
 
Ответить
СообщениеMCH, добрый день. Напишите цену на почту apparit@mail.ru , спасибо.

Автор - Asweb
Дата добавления - 03.08.2016 в 12:21
Exclus Дата: Суббота, 10.09.2016, 15:14 | Сообщение № 7
Группа: Пользователи
Ранг: Прохожий
Сообщений: 1
Репутация: 0 ±
Замечаний: 0% ±

Excel 2010
MCH, добрый день!

Возможна доработка на кабельную продукцию?

1. Имеем кабельный журнал составленный в exel КЖ для нарезки кабеля

Задача, что бы excel (Ваш скрипт) пронумеровал строки которые влезают в заданную длину кабеля в бухте с наименьшим остатком. Отрезков кабеля может быть больше 1000 штук (В вашем Demo влезло только 90 позиций)


Сообщение отредактировал Exclus - Суббота, 10.09.2016, 15:15
 
Ответить
СообщениеMCH, добрый день!

Возможна доработка на кабельную продукцию?

1. Имеем кабельный журнал составленный в exel КЖ для нарезки кабеля

Задача, что бы excel (Ваш скрипт) пронумеровал строки которые влезают в заданную длину кабеля в бухте с наименьшим остатком. Отрезков кабеля может быть больше 1000 штук (В вашем Demo влезло только 90 позиций)

Автор - Exclus
Дата добавления - 10.09.2016 в 15:14
MCH Дата: Суббота, 10.09.2016, 16:11 | Сообщение № 8
Группа: Админы
Ранг: Старожил
Сообщений: 2001
Репутация: 751 ±
Замечаний: ±

Exclus, пришлите мне на почту (m-ch собака mail.ru) перечень на 1000 и более позиций (из реальной потребности) и укажите размер бухты.
 
Ответить
СообщениеExclus, пришлите мне на почту (m-ch собака mail.ru) перечень на 1000 и более позиций (из реальной потребности) и укажите размер бухты.

Автор - MCH
Дата добавления - 10.09.2016 в 16:11
ZavodProfil Дата: Четверг, 01.12.2016, 18:30 | Сообщение № 9
Группа: Пользователи
Ранг: Прохожий
Сообщений: 1
Репутация: 0 ±
Замечаний: 0% ±

Excel 2013
Доброго дня ночи. Ищу решение реализованное в 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 метра погонного ленты штрипс. (Рассчет стоимости мне понятен как сделать, а вот создать алголритм подбора оптимальных ширин лент для карты раскроя пока не могу) Может кто на мысль натолкнет? или пример такого расчета есть?

Юрий
zavod_profil@mail.ru

Автор - ZavodProfil
Дата добавления - 01.12.2016 в 18:30
MCH Дата: Четверг, 01.12.2016, 20:01 | Сообщение № 10
Группа: Админы
Ранг: Старожил
Сообщений: 2001
Репутация: 751 ±
Замечаний: ±

скинте мне на почту (m-ch собака mail.ru) более подробно описанную задачу с указанием какие есть потребности и сколько нужно изготовить лент и какого размера
 
Ответить
Сообщениескинте мне на почту (m-ch собака mail.ru) более подробно описанную задачу с указанием какие есть потребности и сколько нужно изготовить лент и какого размера

Автор - MCH
Дата добавления - 01.12.2016 в 20:01
kvmail Дата: Вторник, 07.02.2017, 10:15 | Сообщение № 11
Группа: Пользователи
Ранг: Прохожий
Сообщений: 5
Репутация: 0 ±
Замечаний: 0% ±

Excel 2007
А пробовали проверить свои алгоритмы на вот этих примерах:
http://people.brunel.ac.uk/~mastjjb/jeb/orlib/binpackinfo.html
 
Ответить
СообщениеА пробовали проверить свои алгоритмы на вот этих примерах:
http://people.brunel.ac.uk/~mastjjb/jeb/orlib/binpackinfo.html

Автор - kvmail
Дата добавления - 07.02.2017 в 10:15
MCH Дата: Вторник, 07.02.2017, 21:35 | Сообщение № 12
Группа: Админы
Ранг: Старожил
Сообщений: 2001
Репутация: 751 ±
Замечаний: ±

А пробовали проверить свои алгоритмы на вот этих примерах:

Сделал раскрой данных по ссылке: https://www2.wiwi.uni-jena.de/Entscheidung/binpp/index.htm
Понравился набор данных Data set 3

Карты раскроя: https://yadi.sk/i/8FAH4bw23DPUHE
 
Ответить
Сообщение
А пробовали проверить свои алгоритмы на вот этих примерах:

Сделал раскрой данных по ссылке: https://www2.wiwi.uni-jena.de/Entscheidung/binpp/index.htm
Понравился набор данных Data set 3

Карты раскроя: https://yadi.sk/i/8FAH4bw23DPUHE

Автор - MCH
Дата добавления - 07.02.2017 в 21:35
kvmail Дата: Среда, 08.02.2017, 14:20 | Сообщение № 13
Группа: Пользователи
Ранг: Прохожий
Сообщений: 5
Репутация: 0 ±
Замечаний: 0% ±

Excel 2007
Непонятно, почему эти примеры называются сложными ? Оптимальные решения получаются достаточно быстро )))
Попробуйте вот пример gau3.
К сообщению приложен файл: gau3.noext(0.9 Kb)
 
Ответить
СообщениеНепонятно, почему эти примеры называются сложными ? Оптимальные решения получаются достаточно быстро )))
Попробуйте вот пример gau3.

Автор - kvmail
Дата добавления - 08.02.2017 в 14:20
MCH Дата: Среда, 08.02.2017, 16:32 | Сообщение № 14
Группа: Админы
Ранг: Старожил
Сообщений: 2001
Репутация: 751 ±
Замечаний: ±

Попробуйте вот пример gau3

Тест достаточно экстремальный (по количеству деталей - 2500 шт), считалось несколько минут
Результат раскроя - во вложении
К сообщению приложен файл: LinRaskrLP2500.xlsx(74.0 Kb)
 
Ответить
Сообщение
Попробуйте вот пример gau3

Тест достаточно экстремальный (по количеству деталей - 2500 шт), считалось несколько минут
Результат раскроя - во вложении

Автор - MCH
Дата добавления - 08.02.2017 в 16:32
kvmail Дата: Четверг, 09.02.2017, 10:50 | Сообщение № 15
Группа: Пользователи
Ранг: Прохожий
Сообщений: 5
Репутация: 0 ±
Замечаний: 0% ±

Excel 2007
Интересно, а в 1065 нельзя упаковать ?
 
Ответить
СообщениеИнтересно, а в 1065 нельзя упаковать ?

Автор - kvmail
Дата добавления - 09.02.2017 в 10:50
MCH Дата: Четверг, 09.02.2017, 11:02 | Сообщение № 16
Группа: Админы
Ранг: Старожил
Сообщений: 2001
Репутация: 751 ±
Замечаний: ±

Интересно, а в 1065 нельзя упаковать ?

нет, если найдете такое решение - выкладывайте
но линейное программирование показало, что решения в 1065 не может быть
 
Ответить
Сообщение
Интересно, а в 1065 нельзя упаковать ?

нет, если найдете такое решение - выкладывайте
но линейное программирование показало, что решения в 1065 не может быть

Автор - MCH
Дата добавления - 09.02.2017 в 11:02
kvmail Дата: Четверг, 09.02.2017, 11:23 | Сообщение № 17
Группа: Пользователи
Ранг: Прохожий
Сообщений: 5
Репутация: 0 ±
Замечаний: 0% ±

Excel 2007
Линейное программирование как раз показывает, что 1065 возможно. Правда возможно мы о разных моделях говорим ))).
К сообщению приложен файл: gau3.ns(3.8 Kb)
 
Ответить
СообщениеЛинейное программирование как раз показывает, что 1065 возможно. Правда возможно мы о разных моделях говорим ))).

Автор - kvmail
Дата добавления - 09.02.2017 в 11:23
MCH Дата: Четверг, 09.02.2017, 11:37 | Сообщение № 18
Группа: Админы
Ранг: Старожил
Сообщений: 2001
Репутация: 751 ±
Замечаний: ±

Целочисленное линейное программирование не может дать результат в 1065, у Вас же кол-во повторов - дробные
Кроме того, обратите внимание, что у меня максимизирован остаток от последней заготовки
 
Ответить
СообщениеЦелочисленное линейное программирование не может дать результат в 1065, у Вас же кол-во повторов - дробные
Кроме того, обратите внимание, что у меня максимизирован остаток от последней заготовки

Автор - MCH
Дата добавления - 09.02.2017 в 11:37
kvmail Дата: Четверг, 09.02.2017, 12:32 | Сообщение № 19
Группа: Пользователи
Ранг: Прохожий
Сообщений: 5
Репутация: 0 ±
Замечаний: 0% ±

Excel 2007
Просто вы говорили о линейное программирование, а не о линейном целочисленном программирование. Обычно эти понятия разделяют ))). Вы используете точную модель решения задачи линейного раскроя ?
 
Ответить
СообщениеПросто вы говорили о линейное программирование, а не о линейном целочисленном программирование. Обычно эти понятия разделяют ))). Вы используете точную модель решения задачи линейного раскроя ?

Автор - kvmail
Дата добавления - 09.02.2017 в 12:32
MCH Дата: Четверг, 09.02.2017, 12:58 | Сообщение № 20
Группа: Админы
Ранг: Старожил
Сообщений: 2001
Репутация: 751 ±
Замечаний: ±

Вы используете точную модель решения задачи линейного раскроя ?

Я использую собственные наработки для решения задачи линейного раскроя (конечно после изучения работ других авторов, используя их методологию и собственные решения)
В линейном программировании в условиях поиска решения ставлю ограничения, что нужно раскроить не менее заданного количества деталей и что решение должно быть целочисленным
 
Ответить
Сообщение
Вы используете точную модель решения задачи линейного раскроя ?

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

Автор - MCH
Дата добавления - 09.02.2017 в 12:58
Мир MS Excel » Вопросы и решения » Готовые решения » Линейный раскрой (Excel)
  • Страница 1 из 6
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • »
Поиск:

Яндекс.Метрика Яндекс цитирования
© 2010-2022 · Дизайн: MichaelCH · Хостинг от uCoz · При использовании материалов сайта, ссылка на www.excelworld.ru обязательна!