Здравствуйте.
Вопрос собственно заключается в алгоритме точного линейного раскроя.
Я реализовал пока эвристику. Т.е все заготовки сортируются по убыванию. Потом берется первый пруток (брусок, профиль и т.д) и на него укладывается макс. возможное кол-во самых длинных заготовок. Потом на отходе пробуем уложить другие детали меньших размеров и так до тех пор пока отход будет меньше самой короткой заготовки. После берем второй пруток. И снова начинаем с самой длинной детали, если конечно еще не удовлетворена ее комплектность и по той же схеме производим раскладку. Пока сделал вариант где размер раскраиваемых полос одинаковый и их кол-во "неограниченно".
Например, нужно получить следующие заготовки из полосы длинной 4000мм:
698 мм 16 шт.
518 мм 16 шт.
Раскрой по алгоритму получается следующий:
698x5 - 3 полосы
698+518х6
518х7
518х3
В результате уходит 6 полос материала. Кстати где то на форуме видел программу Optimize 1.05. Установил ее. Результат такой же. Мне кажется она работает на той же эвристике. Пробовал различные примеры все раскрои совпадают с моими.
Если же этот пример решать с помощью линейного программирования то получится следующий раскрой:
698x2+518x5 - 2 полосы
698х4+518х2 - 3 полосы
Т.е уходит не 6 а 5 полос. Но проблема в том что надо предварительно перечислять все варианты раскроя а если деталей много то уйдет очень много времени. Есть ли алгоритмы которые реализуют такой раскрой не без перечисления всех вариантов? Где то видел что применяется Метод Гомори + задача о рюкзаке+линейное программирование но в интернете что то ничего подходящего не нашел. И может быть еще есть какие то подобные алгоритмы которые решают задачу точно?

Кстати в книге Бабаева Оптимальный раскрой с помощью ЭВМ нашел блок-схему в которой сначала решается задача с помощью двойственного симплекс-метода + задача о ранце. Как написано решение задачи основано на методе Гильмора и Гомори без составления всех исходных вариантов. Эта блок-схема приближенного целочисленного решения. И кстати как там написано вообще задачи раскроя чаще соответствуют нелинейному программированию и для них отстутствует строгий математический метод. Т.е я сделал такой вывод что, например, если материал который будет кроится дорогой и заготовок не так много то можно составить различные варианты раскроя и решить симпекс-методом чтобы сэкономить деньги на покупку материала ...ну а в остальных случаях применять эвристику)
Кстати насколько сильно результаты эвристики могут отличаться от решения симплекс-методом? Ну допустим будем говорить об эвристике которую я в начале привел. Т.е зависит ли она скажем от кол-ва заготовок? (Т.е например если слишком много заготовок то результаты эвристики могуть быть плохими. ) Может кто применял эвристику на большом количестве данных..какие были результаты?

Valer,

Длина раскраиваемой полосы 4000 мм
698x2+518x5 -2 полосы Отход с каждой полосы 14 мм
Получаем 698 - 4 шт и 518 -10 шт
698х4+518х2 - 3 полосы Отход с каждой полосы 172 мм
Получаем 698-12 шт 518-6 шт
в сумме 698: 4+12=16 и 518: 10+6=16 шт
Ушло 5 полос