Прямоугольный негильотинный раскрой на основе алгоритма поиска оптимальных элементов

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

Общая характеристика работы
Содержание диссертации
Глава 1. Точные и приближенные методы решения задачи прямоугольного
негильотинного раскроя
Точные методы решения задачи прямоугольного негильотинного
раскроя
Приближенные методы решения задачи прямоугольного негильотинного
раскроя
Глава 2. Основные понятия, используемые в алгоритме поиска оптимальных элементов, необходимые для решения задачи прямоугольного негильотинного
раскроя
ГлаваЗ. Постановка задачи прямоугольного негильотинного раскроя и описание алгоритмов ее решения
3.1. Постановка задачи
3.2. Алгоритм поиска оптимального раскроя
3.2.1. Описание алгоритма поиска оптимального раскроя
3.2.2. Применение алгоритма поиска оптимального раскроя для получения оптимального раскроя на сетке
3.2.3. Правила о порядке размещения сравнимых прямоугольников алгоритмом поиска оптимального раскроя и о порядке размещения прямоугольников
3.2.4. Сокращение перебора при замене функции, определяемой критерием укладки, на оценочную функцию
3.2.5. Применение алгоритма поиска оптимального раскроя для получения оптимальной плотной укладки
3.2.6. Правила сокращения перебора при работе АПОР на множестве плотных укладок

3.2.7. Оценочные функции
3.2.8. Генератор задач прямоугольного раскроя
3.3. Алгоритм поиска плотной укладки
3.3.1. Описание алгоритма поиска плотной укладки
3.3.2. Правило о порядке размещения прямоугольников
3.3.3. Сравнение работы АППУ со способом последовательноодиночного размещения Стояна Ю.Г. на конкретном примере
3.4. Алгоритм поиска оптимального раскроя с верхней границей
Глава 4. Тестирование
Заключение
Приложения
Литература
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Задачи рационального раскроя возникают в различных областях деятельности человека. Наряду с раскроем промышленных материалов, к задачам раскроя относятся и задачи размещения совокупности предметов на заданных участках. Например, это могут быть задачи размещения тяжеловесных грузов на участках палубы универсальных судов, грузов в отсеках самолетов и т.д.
Рациональный раскрой представляет собой частный случай задачи переработки комплексного сырья, а так как с каждым годом добыча полезных ископаемых сокращается, то задача рационального раскроя, как задача экономного использования промышленных материалов, становится все более актуальной. Соответственно возрастает значимость поиска новых эффективных алгоритмов решения этой задачи.
В настоящее время достаточно хорошо изучены задачи нефигурного (линейного и прямоугольного гильотинного) раскроя. Это объясняется простой формой заготовок и тем, что разрешаются только сквозные резы, параллельные кромкам листа.
Задача прямоугольного негильотинного раскроя, которая рассматривается в диссертации, относится к классу ММголных проблем, поэтому поиск оптимального решения этой задачи является весьма трудоемким. Несмотря на это, на практике часто возникает необходимость в его получении (например, при раскрое дорогостоящих материалов).
Для получения оптимального решения задачи прямоугольного негильотинного раскроя на множестве размещений п, п=0,1 т прямоугольников (т - количество прямоугольников) на заданном листе, покрытом сеткой, и на множестве плотных укладок, полученных плотным размещением п, п=0,1 т прямоугольников на листе, в данной работе

2). На одном и том же участке листа число размещений прямоугольника dj не больше, чем число размещений прямоугольника dj+1, следовательно,
/М2' 1<1м22 /.
3). Согласно условию (3), если при работе алгоритма на последовательности 1 после размещения прямоугольника dj значение функции на полученном элементе / будет превышать fopt, то 10 М3, однако, / может принадлежать М2.
Если же при работе алгоритма на последовательности 2 после размещения прямоугольника dj+2 значение функции будет превышать fopt, то / 0 М3, и , согласно условию (3) I 0 М3
Следовательно, /м/ / 4). Рассмотрим множества укладок А1 и А2 - это множества элементов, из которых получены элементы множеств М/ и М/ соответственно размещением одного не размещенного в них ранее прямоугольника. Обозначим их А1 и А2 соответственно. То есть множества А1 и А2 являются начальными множествами для множеств М/ и М/ соответственно.
Очевидно, что эти множества состоят только из тех укладок, принадлежащих множествам М3! и М32, для которых f(l) Рассмотрим эти множества, исходя из двух ситуаций, которые могут иметь место.
Случай 1. Если для элемента /7 е М3 справедливо f(lj) Случай 2. Если для элемента /" е М3 справедливо f(l"i)>fopt (ясно, что для элемента 1'2е М2 , из которого элемент /" был получен, было справедливо f(l'i) Рассмотрим обратную ситуацию. Если для элемента Г'2еМ32 справедливо f(l"Mopt (ясно, что для элемента Г2еМ2, из которого элемент 1"2 был получен, было справедливо /(I'^^fopt), то Г'20А2, и либо