Тема: Разработка алгоритма метода ветвей и границ для построения негильотинного размещения набора прямоугольников на листе

Задача размещения прямоугольников на листе долгое время привлекает интерес исследователей, поскольку у неё есть явное практическое применение. Например, данная задача может использоваться при необходимости раскроя материалов на производстве с целью оставить как можно меньшее количество отходов материала, для размещения статей в газетах, для создания планов размещения грузов на кораблях или товаров на складах. А вариант задачи размещения прямоугольников на полуполосе заданной ширины может использоваться для определения минимальной длины полосы материала с фиксированной шириной, на которой удастся разместить все заданные детали.
Практически все варианты задачи прямоугольного размещения являются NP-полными, поэтому в основном исследователи разрабатывают эвристические (не имеющие строгого обоснования, но часто дающие приближенное решение задачи с достаточно хорошей точностью) алгоритмы её решения, наиболее популярные из которых - генетические алгоритмы. Математическая формулировка задачи присутствует в публикациях редко [1]. Существуют модели задачи в виде задачи нелинейного (невыпуклого) программирования [5], задачи линейного программирования с альтернативными ограничениями и задачи частично-булевого программирования (с очень большим количеством переменных и ограничений) [6].
В [1] предложены линейные частично булевы модели задачи негильотинного размещения набора прямоугольников на листе и полуполосе. Для получения точного решения был применён метод ветвей и границ Лэнд и Дойг. Также были предложены эвристические приёмы для уменьшения трудоёмкости задачи.
Цель работы - разработка и экспериментальное исследование эффективности алгоритма метода ветвей и границ для решения задачи негильотинного размещения набора прямоугольников на листе. За основу алгоритма взята линейная частично булева модель размещения прямоугольников на листе из [1]. Для решения задачи применяется метод ветвей и границ, который позволяет обеспечить фиксацию булевых переменных и уменьшить трудоёмкость задачи.
Задачи данной выпускной работы:
- изучить модели и методы решения задачи размещения набора прямоугольников на листе;
- разработать алгоритм метода ветвей и границ для построения негильотинного размещения набора прямоугольников на листе;
- разработать программное обеспечение для реализации разработанного алгоритма;
- разработать генератор для задач негильотинного размещения набора прямоугольников на листе;
- разработать программу для визуального представления полученного размещения;
- провести вычислительный эксперимент и провести анализ его результатов.

Купить

Таким образом, в данной работе была решена задача по разработке и реализации алгоритма решения задачи негильотинного размещения прямоугольников на листе методом ветвей и границ. Также была разработана программа для визуализации полученного размещения прямоугольников на листе.
По сравнению со способом решения данной задачи из [1], где задача линейного программирования решалась по всех узлах дерева, в разработанном алгоритме задача линейного программирования решается только в листовых узлах дерева после того, все булевы переменные стали зафиксированными. Метод ветвей и границ позволил значительно сократить время работы программы по сравнению с полным перебором всех случаев.
Был проведён вычислительный эксперимент, который подтвердил, что данная задача является сложной, она долго решается и потому точное решение получить довольно сложно.
Также вычислительный эксперимент показал, что время работы программы зависит от входных параметров (количества и разнообразия деталей). Так, например, при большом количестве одинаковых деталей задача решается значительно быстрее, чем при большом разнообразии размеров деталей.
Также время работы зависит от того, заполняют ли детали всю ширину листа. Если заполняют, то оптимальная длина части листа, на которой располагаются детали, чаще всего совпадает с предполагаемой (вычисленной как сумма площадей деталей, делённая на ширину листа), а при нахождении рекордного значения, совпадающего с нижней границей целевой функции, решение задачи прекращается. Иначе оптимальный результат получается 21
больше предполагаемого и достаточно много времени работы программы тратится на то, чтобы проверить, что данное решение действительно является оптимальным.

Купить