ВВЕДЕНИЕ 3
Постановка задачи 4
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ 6
Модель размещения прямоугольников на прямоугольном листе 6
Метод ветвей и границ 9
Генерация задач 10
Описание алгоритма генерации задач 11
Генерация задач с единообразными размерами 11
Генерация задач с определённым решением 12
Генерация перестановок 12
СПОСОБЫ ФИКСАЦИИ БУЛЕВЫХ ПЕРЕМЕННЫХ 13
Послойная раскладка 13
Алгоритм послойной раскладки 13
Критерии послойной раскладки 14
Вычисление булевых переменных на основе послойной раскладки 14
Уточнение оставшихся переменных 15
Фиксация булевых переменных на основе перестановок и отношения следования 15
Использование константы 16
Способ частичного решения 16
Модификация метода послойной раскладки 17
Метод ветвей и границ 18
ИМПЛЕМЕНТАЦИЯ АЛГОРИТМА В ПРОГРАММНОМ КОМПЛЕКСЕ 20
Используемые технические средства 20
Архитектура программного продукта 20
Основная форма приложения 22
Форма генерации задач 23
Схема классов 24
ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ 26
Результаты экспериментов 26
ЗАКЛЮЧЕНИЕ 29
ЛИТЕРАТУРА 30
Купить

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