Модели и методы оптимизации упаковки N-мерных параллелепипедов

• Автор: Картак, Вадим Михайлович
• Шифр специальности: 05.13.16
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Уфа
• Количество страниц: 98 с. : ил.

Оглавление
Введение
Глава 1. Классификация задач раскроя-упаковки
Глава 2. Задача линейного целочисленного раскроя (N=1)
2.1 Постановка задачи линейного раскроя
2.2 Алгоритм генерации прутков с возвратом (ГПВ)
(переборный алгоритм)
2.3 Эквивалентность планов раскроя
2.4 Доминантность
2.5 Оптимизация смеси
2.6 Коэффициент разветвленности
2.7 Свойства задачи линейного целочисленного раскроя
2.8 Использование на практике свойств Ш11Р
2.9 Группировка
2.10 Эксперимент для одномерной упаковки
Г лава 3. Задача 1Г- мерной прямоугольной упаковки (N>2)
3.1 Математическая модель И-мерной прямоугольной упаковки
3.2 Задача заполнения
3.3 Алгоритм связанных заполнений (СЗ). 59 Глава 4. Задача упаковки прямоугольников в полубесконечную полосу
4.1 Математическая модель
4.2 Схема СЗ алгоритма для N
4.3 Эксперимент для двумерной упаковки
Заключение
Литература
Приложение
Приложение

Введение
Необходимость создания ресурсосберегающих технологий в современных условиях не вызывает сомнения. Проблема ресурсосбережения была и остается чрезвычайно важной. Поэтому представляет большой интерес расчет планов рационального раскроя материалов. Актуальность проблемы оптимального раскроя объясняется не только очевидной эффективностью использования данных планов раскроя на производстве, но и многообразием постановок задач раскроя, трудностью создания совершенных математических моделей и выбора методов их решения. Задачи раскроя-упаковки представляют собой важный раздел методов оптимизации и исследования операций. В рамках решения этих задач развивается и исследуется общие проблемы характерные для указанных областей математики.
Проблема оптимального раскроя объединяет различные по математической постановке задачи. В литературе они встречаются под названиями : задачи раскроя, упаковки, размещения, загрузки,
распределения и т.д. Общим для них является наличие двух групп объектов. К первой группе относятся большие объекты, ко второй- малые. Требуется установить соответствие и порядок назначения между ними так, чтобы некоторая целевая функция достигала минимум при выполнении определенных ограничений.
Диссертационная работа посвящена построениям точных алгоритмов решения задач раскроя-упаковки. Методы, нацеленные на получение оптимального решения этой проблемы, до сих пор остаются мало изученными. Причиной этого является ГТР- полнота рассматриваемой задачи в сильном смысле (задача линейного целочисленного раскроя в частном случае дает задачу 3-РАЗБИЕНИЕ), так что мало надежды на отыскание

даже псевдополиномиального точного алгоритма решения этой задачи. На данный момент теория ЫР задач говорит, что для нахождения оптимального решения рассматриваемых задач существует только один путь - полный перебор всех допустимых вариантов и выбор из них оптимального [37].
Но несмотря на всю трудоёмкость процесса нахождения оптимального результата, на практике часто возникает необходимость его получить: это задачи единичного и мелко серийного раскроя ценных материалов; решение задачи остатка при крупносерийном раскрое. В исследовательском плане знание оптимальных решений дает возможность провести оценку эффективности эвристических алгоритмов и т.д.
Диссертация посвящена разработке точного алгоритма решения задачи линейного целочисленного раскроя (ЛЦР), базирующегося на методе ветвей и границ, и его программной реализации;, созданию оптимизационного алгоритма решения задачи упаковки И- мерных прямоугольных параллелепипедов в полубесконечную область.
Научная новизна диссертационной работы заключается в следующем:
разработан точный алгоритм решения задачи линейного целочисленного раскроя, базирующийся на методе ветвей и границ.
разработан и применён метод группировки для решения задач ЛЦР с большим количеством типов заготовок, подтвердивший свою эффективность в вычислительных экспериментах;
разработана математическая модель задач упаковки Ы-мерных прямоугольных объектов (N>2) в полубесконечную область.
разработан метод решения задач упаковки Ы-мерных прямоугольных объектов.
Предложенные в диссертации методы ориентированы на достаточно широкий класс прикладных задач. Разработанное программное обеспечение позволяет решать задачу линейного целочисленного раскроя и упаковки

Получаемая карта раскроя :
I 1 2 3 4
1 2 2 1
2 2 2 2 1
3 1 1 2

А 7 7 1 0
R 7 14 15 15
Верхнюю границу удалось уменьшить на 1 . Так как верхняя граница равна нижней, то полученный раскрой будет оптимальным.
Принято заполнять матрицу по столбцам от раскроя к раскрою.
2.5 Оптимизация смеси
Рассмотрим случай, когда есть несколько видов прутков и необходимо выбрать рациональную смесь. Для решения задачи в данной постановке требуется минимизировать не количество используемых прутков, а суммарный остаток:
X Lj —> min.
Для решения данной задачи предложен следующий алгоритм:
Находим набор прутков такой, что он покрывает все заготовки, но при этом суммарный остаток минимален. Получается следующая задача :
набор заготовок заданной длины и комплектности (И,bi), всего гп-типов: