Оптимальный линейный раскрой

Требуется
1. Решить данную задачу оптимальным алгоритмом.
Если можно на простом примере объяснить оптимальный алгоритм.
Только такие наборы бывают посложнее и побольше
400мм 20шт.
1200мм 12шт.
Все надо разместить данные отрезки на отрезкаъ длинной не более 6000мм.
Расстояние между отрезками = 5мм.
2. Результат нужно будет выводить в следующем виде (приложил файл)
Все данные для данного отчета мы можем получить из базы. Как быть с отрисовкой элементов?
Будем данную обработку использовать в нашей программе (на C# делаем)

Существует ли оптимальный алгоритм решения данной задачи?
Является ли решение данной задачи следующим методом оптимальным

Метод гомора
Симплекс метод

Миниатюры

 

Вложения

Раскрой.pdf (117.2 Кб, 195 просмотров)

0

hulk45, Вам тема с линейным раскроем актуальна?

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

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

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

Вложения

LinRaskr90 v1.01b пример.rar (309.0 Кб, 369 просмотров)

2

m-ch, Пожалуйста помогите разобраться с этой программой . Где взять макрос к ней ?
Которая выше в Вашем посте.

Добавлено через 18 минут

Сообщение от m-ch LinRaskr90 v1.01b пример.rar (309.0 Кб, 13 просмотров)

Я имел ввиду эту таблицу . Нужно оптимизировать раскрой помогите пожалуйста .

0

приложите Ваши данные, которые нужно раскроить

0

m-ch, Это каждый раз разные задачи . Резать металл на разные заготовки исходя из хлыста 60000мм

0

Сообщение от m4shaman Резать металл на разные заготовки исходя из хлыста 60000мм

Вы не ошиблись, у вас заготовки по 60метров, а не по 6м?

Сообщение от m4shaman Пожалуйста помогите разобраться с этой программой . Где взять макрос к ней ? Которая выше в Вашем посте.

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

Если Вас интересуют программы по раскрою, то вот несколько ссылок на них, которые мне удалось найти:
Онлайн калькулятор "Экономичный распил. Раскрой линейных изделий": относительно неплохой калькулятор, достаточно прост в использовании.

Онлайн калькулятор "Задача об упаковке в контейнеры": использует "жадный" алгоритм, качество раскроя соответствующее (как правило не оптимальное)

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

Онлайн калькулятор "Line cutting": работает нестабильно, в сложных реальных раскроях мне не удалось найти решение

"Быстрый линейный раскрой", автор Калашников Александр: доступная для скачивания демоверсия не позволяет оценить качество раскроя из-за существенных ограничений (полную версию не эксплуатировал).

Программа lin_raskr , автор Семенов В.В.: бесплатная программа, реализована на VB6. работает быстро, ввод данных можно делать из текстового файла или файла .xls

Оптимизация раскроя профиля - Optimize от ФС-Буд: высокая скорость работы, невысокая стоимость: доступна демоверсия на 10 запусков. Тестирование показало, что качество раскрое очень плохое, близкое к "жадному" алгоритму.

Cutting Line: достаточно простая программа в использовании, стоимость не большая. Работает относительно быстро, качество раскроя лучше, чем у Optimize, но тоже не всегда хорошее.

RasKon (Расчет Конструкций) от ADGroup: предназначена для организации и контроля производства окон, дверей, перегородок, фасадов и прочих конструкций.
Программа более сложная, а не просто калькулятор линейного раскроя, доступна для скачивания демоверсия.

Программа оптимизации раскроя PaneCut от VSGroup: позволяет оптимизировать линейный и двухмерный раскрой, вести склад обрезков и автоматически изменять параметры раскроя для разных материалов.

Программа линейного раскроя Окнософт cutting: платная программа, с не очень дешевой ценой. Качество работы не проверял, но выложенные на сайте примеры работы программы не самые эффективные, исходные данные можно раскроить с меньшими потерями.

Программа линейного раскроя от компании Простор: Оптимизация раскроя длинномерных материалов: подоконника, профиля, трубы, бруса/доски, рулонных материалов и др.

Указанный перечень не полный и мои комментарии к программам является личным мнением.

Нашел тест по тестированию программ линейного раскроя, используемые в оконном производстве: http://forum-okna.ru/index.php?showtopic=35118
Там указаны еще программы, позволяющие производить линейный раскрой, а также приведены результаты их работы на тестовых данных.

Относительно качества раскроя программ.
Хорошим тестом является набор данных указанных в Википедии по теме «Задача раскроя»:

Данные детали можно раскроить из 73 исходных заготовок, решение указано в статье.
Но не все программы справляются с этой задачей. CuttingLine и Optimize и онлайн калькуляторы не могут найти решение в 73 заготовки.
Следующим показателем качественности алгоритма – какого максимального размера остается остаток от последней заготовки либо минимизация количества различных вариантов раскроя, если критичным является переналадка оборудования.

Во вложении пример, как раскроила эти детали моя программа: использовано 73 заготовки, сохранен остаток в 580 мм.
Применяемый метод линейного программирования в моей программе позволяет найти оптимальное решение при этом максимизируя остаток от последней детали.
Если будет заинтересованность в алгоритме - обращайтесь в личку.

Вложения

LinRaskrLP v1.102b Wiki.xlsx (50.8 Кб, 199 просмотров)

1

да по 6 метров

Добавлено через 6 минут
Получается что Вы этот макрос продаёте ?

0

Ссылка для скачивания Demo-версии есть здесь
Также выкладываю программу на этом форуме

Вложения

LinRaskrLP Demo.zip (407.0 Кб, 249 просмотров)

2

m-ch, Интересен Ваш LinRaskrLP, как приобрести полную версию ?

0

m-ch, Интересен Ваш LinRaskrLP, как приобрести полную версию ?. Прошу сообщить на: del
Заранее спасибо

0

https://softbel.000webhostapp.com/gallery/kroy.zip
вот ещё прога. Пробуйте. Она еще и под углами, отличными от 90, может резать.

Вложения

Kroy.zip (1.84 Мб, 237 просмотров)

0

m-ch, Интересует ваша программа, но в ЛС не могу написать, т.к. не набрал 3х сообщений. Можете мне написать?

0

Сообщение от ZloyEjik Интересует ваша программа

ZloyEjik, что именно интересует?
Демо версия полностью функциональна и без ограничений по времени, по ссылке можно скачать и другие реализации

0

m-ch, я нашел вышу тему на excelworld, попробую поковыряться с вашей программой. Я инженер на алюминиевом производстве витражей и хочу использовать код для автоматизации выгрузки напила на пилу, без использования программы Cutting Optimization Pro.
Как я понял (судя по ветке на другом сайте) вы не возражаете, против использования вашего кода?

0

Уважаемый M-ch, как можно приобрести полную версию вашего файла линейного раскроя? Демоверсией пользуюсь уже почти год. Очень нравится, но хотелось бы иметь полную версию.

0

Artyemy, программа с открытым кодом и в разных вариантах реализации есть на excelworld, легко ищется в поисковике

0

Не могу найти, к сожалению (( Помогите ссылкой , пожалуйста

0

https://www.optimalprograms.com
это чтоле?

0

Сообщение от Artyemy Помогите ссылкой , пожалуйста

http://www.excelworld.ru/forum/3-21304-1

0

Благодарю!

0