BCUT. Программа оптимизации раскроя листовых материалов
Экономичный линейный раскрой материалов (раскрой погонажа) актуален для многих отраслей производства и в строительстве. Это — распил бревен и досок в деревообработке, резка прутков, арматурных стержней, уголков, швеллеров, труб, двутавров на заготовки...
В производстве металлоконструкций и машиностроении, поперечный раскрой рулонов с бумагой и тканью в целлюлозной и легкой промышленности.
Не смотря на кажущуюся простоту, решение задач линейного раскроя является весьма не легким, но стоящим делом. Внедрение научного подхода к раскрою погонажных материалов позволяет снизить расходы на них иногда более чем на 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< Lo j < L д min ).
2. «Укладку» деталей в заготовку начинаем с самых больших деталей и с самого большого их количества, последовательно двигаясь в сторону уменьшения.
Если какого-нибудь типоразмера деталей в варианте раскроя нет, то ячейку оставляем пустой, ноль писать не будем для облегчения визуального восприятия таблицы.
Вариант раскроя №1:
Попытка выкроить из одной заготовки 5 деталей №1 невозможна, поэтому пишем в ячейку
Добавить в раскрой деталь №2 или деталь №3 также невозможно, поэтому оставляем пустыми ячейки
Вариант раскроя №2:
Уменьшаем на 1 от предыдущего варианта количество деталей №1 и записываем в
Пробуем добавить 2 детали №2 – не получается, поэтому дополняем в
Остается возможность дополнить раскрой деталью №3. Заносим в
Придерживаясь озвученных принципов, заполняем по аналогии все возможные в данном случае 18 вариантов раскроев.
Сделав пару-тройку таблиц вариантов раскроев самостоятельно, вы уясните логику действий и будете тратить считанные минуты на эту работу.
Если при раскрое не выполняется первый принцип, то ячейка с длиной отхода автоматически окрашивается в красный цвет. Условное форматирование, примененное к ячейкам G7…G24, наглядно поможет вам в этой работе.
В ячейках H7…H24 ничего не пишем! Они используются для вывода результата решения!
Подготовка к решению:
* В ячейках G7…G24 вычисляются длины отходов (обрезков), остающиеся в результате выполнения раскроев, по формуле
Lo j = 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 = Lо Σ /Lз Σ
Решение:
Подготовка завершена, определены 18 вариантов наиболее оптимальных раскроев одной заготовки на детали и вписаны все необходимые формулы. Теперь предстоит решить главную задачу: определить оптимальный план раскроя – сколько заготовок, и по каким вариантам раскроев резать , чтобы в итоге получить все необходимые детали в нужном количестве при минимуме отходов.
1. Выбираем в главном меню «Сервис» - «Поиск решения…».
2. В появившемся одноименном окне «Поиск решения» производим настройки.
2.1. Назначаем целевой функцией общую длину отходов Lо Σ и вводим ссылку в окно целевой ячейки.
2.2. Устанавливаем переключатель «Равной:» в положение «минимальному значению».
2.3. Указываем ячейки с переменными Nз j в окне «Изменяя ячейки».
2.4. Вводим ограничения в одноименное окно. В качестве условий указываем необходимость равенства заданного Nд i и расчетного Nд iрасч количества деталей, а так же на переменные Nз j – расчетное количество заготовок по вариантам раскроев – накладываем ограничение: это должны быть целые числа.
3. Нажимаем кнопку «Параметры» и в выпавшем окне «Параметры поиска решения» выполняем настройки так, как показано на следующем скриншоте. Закрываем окно кнопкой «ОК».
4. В окне «Поиск решения» нажимаем кнопку «Выполнить» и ждем, пока Excel найдет решение. Это может длиться несколько минут.
5. После сохранения найденного решения кнопкой «ОК», результаты отобразятся в ячейках H7...H24 на листе Excel.
На следующей картинке показан найденный оптимальный линейный раскройный план.
Что в итоге?
Линейный раскрой в Excel заготовок для задач подобных рассмотренной в этой статье выполняется описанным выше методом за 10-15 минут! «Вручную», не зная метод индексов Канторовича, за такое время решения не найдешь.
Запустив «Поиск решения» несколько раз при разных параметрах поиска, удалось найти 5 различных планов рубки заготовок. Все 5 планов требуют одинаковое число заготовок – 93 и дают отходов всего 2,21%!!! Эти планы почти на 6% лучше, чем план, рассчитанный Покровским и более чем на 10% экономичнее «Традиционного» плана (смотри ссылку на первоисточник в первой части статьи). Очень достойный результат достигнут быстро и без применения дорогостоящих программ.
Следует заметить, что надстройка Excel Solver («Поиск решения»), использующая симплекс-метод при решении задач линейного программирования, может работать не более чем с 200 переменными. В приложении к рассмотренной нами задаче линейного раскроя это означает, что количество раскроев не может превышать 200 вариантов. Для простых задач этого достаточно. Для более сложных задач следует попробовать применить «смесь» «жадного» алгоритма и симплексного метода Solver, отобрав из полного списка раскроев не более 200 самых экономичных. Далее запасаемся терпением и добиваемся результатов. Можно попытаться разбить сложную задачу на несколько простых, но «уровень оптимальности» найденного решения будет при этом, скорее всего, ниже.
Может быть, рассмотренный вариант решения вопросов линейного раскроя и не «высший пилотаж», но однозначно шаг вперед по сравнению с «традиционным» подходом на многих производствах.
Использование надстройки MS Excel «Поиск решения» (Solver) было на блоге уже однажды рассмотрено в статье . Думаю, что этот замечательный инструмент достоин пристального внимания и еще не раз поможет изящно и быстро решить ряд новых нетривиальных задач.
P.S. Ссылки на лучшие из бесплатных программ линейного раскроя, найденных мной в Сети:
http://stroymaterial-buy.ru/raschet/70-raskroy-lineynih-izdeliy.html
http://forum-okna.ru/index.php?app=core&module=attach§ion=attach &attach_id=7508
http://forum.dwg.ru/attachment.php?attachmentid=114501&d=13823277 74
http://www.planetcalc.ru/917/
Программы по последним двум ссылкам реализуют жадные эвристики и выполняют линейный раскрой в задаче из статьи, используя аж целых 103 заготовки. Применение жадных алгоритмов оправдано в случаях необходимости снижения общего времени операции резки при слишком большом количестве вариантов раскроев в более оптимальных планах.
Ниже статьи в блоке «Отзывы» можете написать свои комментарии, уважаемые читатели.
«bCUT» — программа для автоматизации раскроя листовых материалов предназначенная, преимущественно, для производства корпусной мебели. Она позволяет быстро выполнять раскладку прямоугольных заготовок на листах прямоугольной формы, с учётом технологических параметров оборудования и кромкооблицовки, распечатывать карты раскроя и этикетки для деталей, создавать программы для раскроя и печати этикеток на станках Altendorf ® .
Программа «bCUT» является продолжением развития модуля «Раскрой», входящего в состав САПР «bCAD Мебель ». Она не только вобрала в себя все лучшие достижения предшественника, но и получила ряд новых возможностей.
Если вас заинтересовали возможности пакета «bCUT», вы можете загрузить . С ценами на «bCUT» вы можете ознакомится в разделе цены нашего сайта.
Быстрое создание заказа
«bCUT» позволяет быстро . Функции клавиш оптимизированы для быстрого ввода. Например, размеры деталей, и кромление можно ввести одной рукой, используя только дополнительную цифровую клавиатуру. Тут же можно использовать встроенный калькулятор для пересчета числовых величин.
Знания об используемых материалах и особенностях оборудования хранятся в банке данных. Их заполняют заранее, а не при клиенте. Тем не менее, если у клиента особенный материал, то заполнить сведения о нем можно быстро и просто, не затрагивая банк.
Импорт заготовок
Имеется импорт (чтение данных) заготовок деталей вместе с описанием материалов и . Поддерживается Excel 2003 и Excel 2007. Таким образом можно быстро принимать заказы, набранные заказчиком вручную или сделанные в других программах.
Простота работы с программой
По внешнему виду и способам управления «bCUT» ничем не отличается от любой современной программы. построен на работе с обычными для Windows визуальными элементами, по которым щёлкают мышью или пером, а также вводят текст или числа с клавиатуры. Пиктограммы четкие и ясные. Кнопки снабжены понятными надписями и всплывающими подсказками. Поэтому вы легко сможете освоить «bCUT».
На экране одновременно видно всё, относящееся к заданию на раскрой. Особенно это удобно на современных дисплеях. Достаточно комфортная работа возможна даже на мониторе ноутбука, с разрешением 1024×600. Имеется цветовая подсветка состояния деталей в таблице.
Учёт кромления
Учёт кромочного материала производится по всем раскроенным деталям, с учётом параметров
станка, на котором производится кромкооблицовка.
При замене станка, расход кромки автоматически пересчитывается с учётом параметров
данного станка.
Учёт особенностей оборудования
Все особенности раскройных или кромочных заносят в банк данных. «bCUT» учитывает максимальные длины резов, толщины пил и свесы кромки. Можно учесть и различия в пиле вдоль и поперёк. Заранее задать значения для разных толщин пилы, которые будут учтены при автоматическом расчёте припусков. Толщину пилы и припуски задают с точностью до 0.1 мм.
Количество станков в банке данных не ограничено. Можно совместить в одном задании раскрой на разных станках.
Высокая скорость раскроя
«bCUT» обеспечивает высокую скорость раскроя. Это достигнуто за счёт быстрых алгоритмов и использования многопроцессорности современных компьютеров.
Алгоритм раскладки деталей оптимизирован для работы на многоядерных процессорах, например Intel Core2Duo. При оптимизации используются все ядра процессора.
Это позволяет задавать в заказе на раскрой несколько материалов и кроить их одновременно, нажатием одной кнопки. При очень больших заданиях, можно, введя детали для одного материала, начать раскрой, и во время оптимизации задавать детали для другого материала.
Оптимизации
«bCUT» имеет простой и ясный . Есть возможность и отдельные карты, меняя при этом методы оптимизации и / или добавлять к заданию дополнительные детали.
Автоматический расчёт припусков заготовок
Есть возможность автоматически вычислять припуски и размеры заготовок с учётом режимов реза, припуска на кромление, типа кромки, в том числе учитывая кромку. Расчёт можно . Припуски автоматически пересчитываются при смене настроек, например, при выборе другого режима реза и исходных данных.
Тем не менее, остаётся возможность задать величину припуска вручную. Просто введя его значение, в том числе с использованием встроенного калькулятора.
Более наглядно работа автоматических припусков показана в видеоролике . Размер ~2 МБ .
Сохранить заказ
Выходные документы
Удобные, ясные выходные документы: карты, сводные ведомости, этикетки для деталей и деловых остатков. На картах раскря используется штрих-кодирование. Имеется возможность настройки бирок «под себя». Можно просто запомнить изображение карты в буфере и вставить как картинку, например, в документ Word.
Отчет и задание на раскрой и кромкооблицовку формируются для всех материалов. Указываются количество и площади листов, заготовок, деталей, остатков.
Цель работы : Закрепление знаний в области экономико-математического моделирования, знакомство с методикой решения задачи рационального раскроя материалов, основанной на решении оптимизационной задачи линейного программирования.
Исходные положения . Изготовление многих видов современной промышленной продукции начинается с раскроя материалов, что является одной из важных производственных задач для заготовительного производства и органов материально-технического снабжения.
Задачи оптимального раскроя материалов - одни из первых задач, к решению которых применялись методы линейного программирования. Они заключаются в определении наилучшего способа раскроя поступающего материала, при котором будет изготовлено наибольшее число готовых изделий в заданном ассортименте или будет получено наименьшее количество отходов.
Первая работа, посвященная решению задач, названных впоследствии задачами линейного программирования, появилась в 1939 г. Это была книга Л.В.Канторовича "Математические методы организации и планирования производства". Толчком для ее появления послужила задача, поставленная перед Институтом математики и механики Ленинградского Государственного университета лабораторией фанерного треста. В других отраслях промышленности также успешно применялись экономико-математические методы оптимизации раскроя материалов. Так, еще в 1948 - 1949 гг. математические методы раскроя были успешно применены на вагоностроительном заводе им. Егорова в Ленинграде, что позволило снизить в несколько раз отходы при раскрое различных материалов.
Математическая модель задачи.
Поступающие на предприятие материалы подлежат раскрою на заготовки. От правильности раскроя зависит себестоимость продукции (используется, например на автозаводах и в др.).
В большинстве случаев раскрой материалов на заготовки производится в определенной пропорции, обеспечивающей получение комплекта заготовок (т.е. кратно комплекту).
Задача оптимизации раскроя материалов заключается в разработке таких вариантов раскроя, при которых получают определенное количество заготовок в данном ассортименте (разных видов) с минимальными отходами.
Для составления математической модели задачи оптимального раскроя введем следующие обозначения:
L - длина материала; S - площадь поверхности листового или рулонного материала; N - количество единиц исходного материала.
Необходимо получить m различных видов заготовок либо длиной L i , либо площадью S i , где i - вид заготовки (i=1, 2, ..., m ).
Известно число заготовок i -го вида в изделии, т.е. то число заготовок, которое необходимо для производства одного изделия - b i . Число комплектов изделий, выпускаемых предприятием обозначим через k .
Раскрой материала можно произвести n способами. Известно а ij - число заготовок i -го вида, получаемое j -м способом (j =1, 2, …, n ).
Количество отходов, получаемое при раскрое единицы исходного материала j -м способом - С j .
Требуется составить такой план раскроя, чтобы обеспечить получение полных комплектов заготовок с минимальными отходами.
Обозначим через x j количество единиц исходного материала, раскроенных j -м способом. Найти такие x j ³ 0 , которые удовлетворяют следующим ограничениям:
(ограничение по количеству исходного материала)
(ограничение по плану производства)
Столько получается заготовок i-го вида при всех вариантах раскроя. Исходя из условия комплектности получим следующие ограничения по плану производства:
Суммарная величина отходов должна быть минимальной, тогда функция цели примет вид:
Пример расчетов в задаче оптимального раскроя материалов.
Из металлических прутков длиной по 6 м каждый, имеющихся в количестве 100 шт. необходимо изготовить конструкцию, изображенную на рис.1.
Исключительная простота - это особенная черта программы Astra S-Nesting. Это необычно для профессиональной программы, но мы специально приложили усилия, чтобы решение всех задач от формирования заказа до редактирования карт раскроя и назначения маршрута вырезки было интуитивно понятно. В результате это обеспечивает быстрое внедрение и успешную эксплуатацию.Скачать
Подробно о программе Astra S-Nesting
Импорт из CAD/CAM
Импорт деталей выполняется из DXF-файлов. Для импортируемых деталей указываются свойства: наименование материала, толщина, количество и номер чертежа. Все свойства деталей можно изменить после импорта. Заказ может содержать детали разных толщин и материалов – программа автоматически сортирует детали на группы совместного раскроя.
Оптимизация раскроя
Быстрый автоматический раскрой обеспечивает высокий коэффициент использования материала. Если требуется, карты раскроя можно отредактировать вручную. Для этого программа предлагает удобные инструменты: перемещение деталей с заданным шагом, до упора и свободное перемещение мышью; поворот деталей на заданный и произвольный угол, запараллеливание кромок деталей; команды масштабирования; возможность отмены и повтора команд и др.
Расчет маршрута вырезки
Отличный алгоритм позволяет за считанные секунды рассчитать маршрут вырезки, обеспечивая оптимальную последовательность обработки. В зависимости от заданных параметров устанавливаются способы врезки в наружный и внутренний контура деталей, направление обхода, наличие мостиков или перемычек и пр. При ручном редактировании маршрута вырезки можно изменить все элементы маршрута и последовательность обработки контуров.
Печать отчетов по раскрою
Для заказа формируется комплект отчетов, включающий спецификации и эскизы карт раскроя. Шаблоны отчетов в Astra S-Nesting настраиваемые! Это значит, что вы можете менять их самостоятельно под принятые на вашем предприятии формы. Любой отчет можно экспортировать в Excel.
Интеграция с CAD/CAM
Один из ключевых принципов, который поддерживается в программе Astra S-Nesting – это интеграция с другими системами CAD/CAM. Данные, которые подготавливает и хранит ваша САПР можно сохранить как заказ для программы Astra S-Nesting и получить обратно результаты расчета. Программа обеспечивает запуск с командной строки, автоматический импорт данных, раскрой заказа, и экспорт результатов обратно для обработки во внешней системе.
ОПТИМИЗАЦИЯ РАСКРОЯ ЛИСТОВОГО МАТЕРИАЛА НА ПРЯМОУГОЛЬНИКИ РАЗЛИЧНЫХ РАЗМЕРОВ
Гиниатуллина Регина Айратовна
студент 1 курса магистратуры, кафедра прикладной математики и информатики КНИТУ им. А.Н. Туполева, РФ, г. Казань
E-mail: regina 1402@ yandex . ru
Галиев Шамиль Ибрагимович
научный руководитель, д-р техн. наук, профессорИТКиИ КНИТУ им. А.Н. Туполева, РФ, г. Казань
Гильотинный раскрой стальных и иных листов широко используется в машиностроении и других отраслях промышленности. Этот раскрой фактически является задачей упаковки квадратов различных размеров в заданный лист при использовании гильотинной процедуры. При этом важно уменьшить отходы листа. Интерес к задачам упаковки объясняется их большой практической значимостью. Как правило, такие задачи относятся к материалоемким производствам, где одним из основных факторов снижения себестоимости выпускаемой продукции является рациональное использование ресурсов. Данная задача имеет широкий спектр практических приложений в тех отраслях индустрии, где традиционно возникают задачи упаковки (раскроя) в машиностроении, деревообработке, лёгкой и строительной индустрии.
1. Обзор по задаче
В промышленности при изготовлении различных видов конечной продукций возникает задача оптимального раскроя листов заданных размеров на прямоугольные заготовки. Эта задача состоит в следующем: известны размеры квадратов, размер листа. Требуется разместить в лист заданные квадраты без перекрытия друг с другом так, чтобы можно было кроить лист гильотиной. Под гильотинным понимается раскрой, реализуемый последовательностью сквозных резов, параллельных кромкам материала. Кроме того, эти квадраты должны быть ортогонально упакованными без вращений, то есть у каждого выбранного элемента типа , сторона с высотой должна быть параллельна стороне листа с высотой H . Мы будем рассматривать проблему упаковки квадратов разного размера в прямоугольник. Решим эту проблему с помощью одного точного алгоритма. Он основан на итеративном выполнении рекурсивной процедурой алгоритма ветвей - и - границ (его мы так же рассмотрим) с различными входными параметрами, чтобы определить оптимальное значение решения.
2. Цель проекта
Цель данной работы состоит в исследовании и реализации алгоритма, способного находить решения упаковки квадратов в прямоугольник. Рассматриваемая задача имеет широкое применение в различных отраслях промышленности: машиностроении, деревообработке, лёгкой и строительной индустрии.
Необходимо осуществить возможность вывода на экран полученного результата в виде вписанных в прямоугольник квадратов различного размера и соответствующей дополнительной информации, необходимой пользователю. Например, такой как: времени работы алгоритма, различных сведений об ошибках и т. д.
3. Общие требования
1) Задание вручную размеров прямоугольника-листа (ширины и высоты), в который будут упаковываться квадраты;
2) Ручной ввод размеров квадратов (они могут быть как одинаковыми, так и различными);
3) Визуальный просмотр результатов выполнения алгоритма (с выводом соответствующей информации: время выполнения алгоритма, количества квадратов определенного размера вписавшихся в прямоугольник);
4) Сохранение в файл информацию об уже вписанных квадратах.
4. Актуальность проблемы
Основной целью проектируемой системы является соответствие основному алгоритму упаковки квадратов и удобство эксплуатации конечным пользователем, отказоустойчивость.
Задачи и функции проектируемой системы должны соответствовать поставленным требованиям.
Предложенный в данной работе алгоритм может быть использован для эффективного решения задачи упаковки квадратов в прямоугольную область заданных размеров. Данная задача имеет широкий спектр практических приложений в тех отраслях индустрии, где традиционно возникают задачи раскроя-упаковки. Рассмотренный алгоритм можно использовать в практических расчетах и включать его в автоматизированные системы проектирования и управления. Можно также сказать, что проблема является актуальной на данный момент, так как есть потребность в упаковке квадратов в прямоугольник и эта потребность никогда не закончится, а значит и проблема будет актуальной всегда.
Задачи раскроя-упаковки занимают важное место в современной комбинаторной оптимизации и привлекают внимание многих ученых, как в России, так и за рубежом.
Интерес к задачам раскроя-упаковки объясняется, в частности, их большой практической значимостью. Как правило, приложения задач раскроя-упаковки относятся к материалоемким производствам, где одним из основных факторов снижения себестоимости выпускаемой продукции является рациональное использование ресурсов.
5. Существующие системы раскроя.
Существуют много программных продуктов для раскроя листового материала, такие как ORION, АСТРА РАСКРОЙ, ТЕХТРАН . Рассмотрим один из них на примере ТЕХТРАНА.
Для предприятий, использующих машины термической резки, внедрение современных информационных технологий - задача из числа самых актуальных. Понятно, что сокращение сроков подготовки программ раскроя, оптимальное размещение деталей на листе, меньший расход материала решающим образом повлияют на себестоимость и качество продукции.
Новый программный продукт Техтран/Раскрой дополняет линейку программ семейства Техтран и предназначен для проектирования программ раскроя листового материала. Возможности CAM-системы объединены здесь с функциями организации производственного процесса. Подход к решению, использованный в программе, суммирует опыт работы ряда предприятий, эксплуатирующих машины термической резки. Задача в том, чтобы по заданию на раскрой, которое состоит из номенклатуры отобранных деталей и их количества по каждому наименованию, оперативно, учитывая складские запасы, оптимальным образом разложить детали на листах и получить управляющие программы резки этих деталей. Листы делового отхода, остающиеся после работы, должны быть учтены в базе данных системы для дальнейшего использования.
6. Формализация задачи и разработка математической модели
Приведем математическую модель задачи, следуя работе .
Алгоритм ветвей - и - границ основан на модели целочисленного линейного программирования (ЦЛП). Ради простоты в этой формулировке мы полагаем, что каждый элемент отличен, то есть для каждого типа j прямоугольников , мы определяем идентичных элементов, имеющих ширину , высоту и выгоду . Пусть (1) будет общим количеством элементов. Для каждого элемента k вводим бинарную переменную принимающую значение 1 тогда и только тогда, когда элемент k включен в оптимальное решение. Модель ЦЛП для общей двумерной задачи рюкзака выглядит следующим образом:
|
|
||
|
|
||
|
|
где: - размеры вписанного квадрата,
Размеры самого прямоугольника,
U
- любая верхняя граница величины оптимального решения и C
обозначает множество всех подмножеств элементов, которые не могут быть упакованы в лист гильотинным способом. Для величины порога U
мы используем , то есть, величину оптимального решения для двумерной задачи рюкзака, соответствующей упрощению, согласно которому ограничения гильотинности опущены. Отметим, что ограничения (3) и (4) избыточны, но добавлены к формулировке, чтобы усилить его. Наш алгоритм решает упрощенную задачу, в которой ограничения (5) устранены и проверено будет ли текущее решение допустимо или нет с помощью решения следующей задачи разделения: будут ли все элементы из 
вписываться в лист при гильотинном подходе? В случае, если ответ положителен, то оптимальное решение общей двумерной задачи рюкзака найдено. Иначе, находится новое нарушенное ограничение, и процесс повторяется.
Этот подход подобен методу, предложенному Капрара и Монаси для точного решения двумерной задачи рюкзака и согласно Пизингеру и Сигарду для того, чтобы решить саму общую двумерную задачу рюкзака. Более точно, модель (2)-(6) решена специализированным методом ветвей и границ, в котором элементы упорядочены. Верхние границы получаются из ЛП релаксации задачи (2)-(3) с использованием верхней границы Мартелло и Тота . Обратный проход происходит всякий раз, когда верхняя граница не превышает текущее решение, или когда некоторые ограничения (3)-(5) нарушены.
В задаче 2-6 не учтено, что раскрой гильотинный. С учетом всех условий рассматриваем рекурсивный метод решения.
7. Метод решения
В этом пункте мы рассмотрим рекурсивную процедуру для перечисления гильотинных двумерных упаковок. В процедуре, называемой рекурсивной, мы обозначим каждое допустимое расположение подмножества элементов на листе как допустимую упаковку. Каждая допустимая упаковка может быть представлена как неотрицательный целочисленный вектор , где каждая координата 
представляет число элементов типа в упаковке. Обозначим как 
прибыль упаковки . Мы говорим, что допустимая упаковка максимальна, если никакие дальнейшие элементы не могут быть упакованы в лист, то есть, упаковка 
оказывается, неосуществимой для всех типов элементов, таким образом, что . Для двух допустимых упаковок и 
мы определяем новую упаковку следующим образом: 
, .
Рекурсивная процедура неявно перечисляет все допустимые упаковки, рекурсивно деля лист на две части посредством (горизонтального либо вертикального) гильотинного реза. Процедура получает во входе параметр , который является нижней границей прибыли любой допустимой (гильотинной) упаковки.
Как замечено Кристодесом и Уитлогом , для любой задачи двумерной упаковки существует оптимальное решение, соответствующее нормальному образцу, то есть, решение, в котором для любого упакованного элемента его левая сторона прилегает либо к правой стороне другого элемента или правой стороне листа. Это означает, что мы можем рассмотреть только вертикальные разрезы, по координатам , которые могут быть получены как комбинация ширин элементов, то есть, которые принадлежат множеству:
Похожим способом мы рассматриваем только горизонтальные разрезы, по координатам , принадлежащих следующему множеству:
Мы предполагаем, что элементы обоих множеств и отсортированы по возрастанию значений и полагаем и .
Даны и и пороговая величина решения , пусть будет множеством всех выполнимых (допустимых) упаковок данных элементов в лист размера , который может произвести (вместе с остаточными элементами и листом) прибыль, больше, или равное . Для двух данных выполнимых упаковок 
и 
мы формально обозначаем через попарную сумму упаковок в множества и :
Интуитивно, является множеством упаковок, которые могут быть получены, комбинацией любой упаковки с любой упаковкой , независимо от размеров множеств и . Ясно, что как только множество определено мы можем найти множества с условием, что все (соответственно ), элементы принадлежат упорядоченному множеству (соответственно ). Похожим способом знание множества позволяет нам определять множества . Действительно, достаточно отметить, что каждая упаковка 
, которая может произвести прибыль, по крайней мере равную , в прямоугольнике , может быть получена как сумма двух допустимых упаковок определенных для прямоугольника меньших размеров. Формально: , где либо 
и 
для некоторого , либо 
и 
для некоторого . Таким образом, зная и для каждого и , мы можем легко получить (сгенерировать) рекурсивным способом .
Основной алгоритм может быть улучшен следующим образом. Для каждой упаковки на листе ширины и высоты , верхняя граница, скажем , максимальной прибыли, может быть получена, когда остаточная площадь вычислена. С этой целью рассмотрим примеры рюкзаков с вместимостью , типов элементов, возможных в копий, каждый с прибылью и весом . Оптимальное решение из этого случая или любая верхняя граница этой величины дает верхнюю границу для максимальной прибыли, которая может быть получена, упаковывая остающиеся элементы в остаточную часть листа. Ясно, что все элементы , такие, что 
могут быть удалены из множества , так как они не могут привести к выполнимому решению, имеющему прибыль больше, чем . В нашей реализации мы вычисляем величину верхней границы на оптимальном решении (одномерного) случая задачи рюкзака (см. ). Величины верхних границ и полученные Хайфи и эти же величины, предложенные Янг-Гуном и Кангом для двумерной (ортогональной) задачи рюкзака без ограничений, мы используем минимум этих величин как верхнюю границу.
Кроме того, отметим, что ширина и высота листа могут быть уменьшены до и , соответственно, что приводит к меньшей мощности рюкзака, при решении релаксации задачи рюкзака, следовательно, к более точным верхним границам. Наконец, отметим, что только максимальная допустимая упаковка должна быть сохранена для каждого набора , и что любой не максимальный элемент может быть игнорирован. Это сокращает количество элементы в , следовательно, требования к памяти и времени вычисления алгоритма.
8. Входные и выходные данные системы
Входные данные:
1. Ширина прямоугольника-листа;
2. Высота прямоугольника-листа;
3. Размеры квадратов;
Выходные данные:
5. Прямоугольники, расположенные на экране монитора;
6. Текстовый файл с информацией о вписанных прямоугольниках;
7. Дополнительная информация о вписывании прямоугольников в виде различных сообщений на экране.
8.5. Разработка интерфейса пользователя
Интерфейс пользователя целесообразно делать в графическом виде, так как это максимально удобно для использования.
Форма ввода и вывода данных
Рисунок 1. Интерфейс пользователя
Вводим сначала ширину прямоугольника, нажимаем enter, высоту - enter, и вводим размеры квадратов, например 23 - enter, 45 - enter и т. д., нажимаем 0, для прекращения ввода квадратов и в том месте, где сохранен проект, появляется файл result.png, где можно увидеть упаковку квадратов.
В этом же окне выводится информация о количестве квадратов определенных размеров. Нажимаем 0 и видим информацию о времени заполнения прямоугольной область квадратами.
После всех проделанных действий получаем:
Рисунок 2. Полученный результат программы
и саму упаковку:
Рисунок 3. Упаковка квадратов в прямоугольник
Таблица 1.
Численные результаты программы
|
Размер прямоугольника |
Предполагаемое кол-во квадратов |
Общее кол-во квадратов |
||
Вывод: чем больше введенных квадратов, тем больше время выполнения алгоритма.
9. Заключение
В соответствии с целью исследования были поставлены и выполнены следующие задачи:
1. Формулировка рассматриваемых задач раскроя-упаковки в терминах математического программирования и качественная оценка методов их решения;
2. Разработан и исследован алгоритм решения задачи упаковки квадратов различных размеров в прямоугольник;
3. Проведен анализ эффективности разработанного метода на основе результатов численных экспериментов.
Список литературы:
1.Техтран/Раскрой листового материала [Электронный ресурс] - Режим доступа. - URL: http://9132222.ru/catalog/soft/techtran/textran.html (дата обращения 12.06.2014).
2.Caprara A, Monaci M. On the two-dimensional knapsack problem. Operations Research Letters 2004;32:5–14.
3.Christofides N, Whitlock C. An algorithm for two-dimensional cutting problems. Operations Research 1977;25:30–44.
4.Hifi M. An improvement of Viswanathan and Bagchi’s exact algorithm for constrained two-dimensional cutting stock. Computers and Operations Research 1997;24:727–36.
5.Martello S, Toth P. Knapsack problems: algorithms and computer implementations. Chichester: John Wiley & Sons; 1990.
6.Pisinger D, Sigurd M. Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem. INFORMS Journal on Computing 2007;19:36–51
7.Young-Gun G, Kang MK. A new upper bound for unconstrained two-dimen-sional cutting and packing. Journal of the Operational Research Society 2002;53:587–91.
