Введение 3
1 Теоретические основы 5
2 Общая схема алгоритма 8
3 Метод ветвей и границ для решения задачи размещения прямоугольников
на листе 10
3.1 Правила для фиксации в список окончательно зафиксированных
переменных 10
3.2 Две детали, не укладывающиеся по длине в значение верхнего
ограничения целевой функции 11
3.3 Поиск циклов в расположении деталей 12
3.4 Проверка длин цепочек деталей 13
4 Программное обеспечение для построения негильотинного размещения
набора прямоугольников на листе 15
5 Результаты вычислительных экспериментов 18
Заключение 21
Список использованной литературы 23
Приложения
Купить

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

Купить