ВВЕДЕНИЕ 3
ГЛАВА 1. ПОСТАНОВКА ЗАДАЧИ НЕГИЛЬОТИННОГО РАЗМЕЩЕНИЯ
НАБОРА ПРЯМОУГОЛЬНИКОВ НА ПОЛУПОЛОСЕ 7
1.1. Модель размещения набора прямоугольников на листе 7
1.2. Метод ветвей и границ 11
ГЛАВА 2. РАЗРАБОТКА АЛГОРИТМА 14
2.1. Фиксация переменных для очевидных случаев 14
2.2. Метод перебора перестановок. 16
2.3. Алгоритм решения задачи 17
ГЛАВА 3. РЕАЛИЗАЦИЯ АЛГОРИТМА 20
3.1. Программное обеспечение для реализации алгоритма 20
3.2. Вычислительные эксперименты 24
ЗАКЛЮЧЕНИЕ 34
СПИСОК ЛИТЕРАТУРЫ 35
ПРИЛОЖЕНИЕ 1
Купить

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

Купить