автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Модели и методы оптимизации упаковки N-мерных параллелепипедов

/ - ' -

& / ' к/К? " / , г _ ^

' /

Уфимский авиационный технический

университет

На правах рукописи

Картак Вадим Михайлович

МОДЕЛИ И МЕТОДЫ ОПТИМИЗАЦИИ УПАКОВКИ ]Ч- МЕРНЫХ ПАРАЛЛЕЛЕПИПЕДОВ

05.13.16- Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата физико-математических наук

Научный руководитель:

доктор технических наук, профессор Э.А. Мухачева

Уфа 1999

Оглавление

Введение 3

Глава 1. Классификация задач раскроя-упаковки. 17

Глава 2. Задача линейного целочисленного раскроя (N=1). 23

2.1 Постановка задачи линейного раскроя. 23

2.2 Алгоритм генерации прутков с возвратом (ГПВ) (переборный алгоритм). 24

2.3 Эквивалентность планов раскроя. 27

2.4 Доминантность. 29

2.5 Оптимизация смеси. 35

2.6 Коэффициент разветвленности. 37

2.7 Свойства задачи линейного целочисленного раскроя. 39

2.8 Использование на практике свойств Ш11Р. 41

2.9 Группировка. 42

2.10 Эксперимент для одномерной упаковки. 45 Глава 3. Задача № мерной прямоугольной упаковки (N>2). 47

3.1 Математическая модель Ы-мерной прямоугольной упаковки. 49

3.2 Задача заполнения. 50

3.3 Алгоритм связанных заполнений (СЗ). 59 Глава 4. Задача упаковки прямоугольников в полубесконечную полосу. 61

4.1 Математическая модель. 61

4.2 Схема СЗ алгоритма для N=2. 63

4.3 Эксперимент для двумерной упаковки. 64 Заключение. 66 Литература. 68 Приложение 1. 75 Приложение 2. 86

Введение

Необходимость создания ресурсосберегающих технологий в современных условиях не вызывает сомнения. Проблема ресурсосбережения была и остается чрезвычайно важной. Поэтому представляет большой интерес расчет планов рационального раскроя материалов. Актуальность проблемы оптимального раскроя объясняется не только очевидной эффективностью использования данных планов раскроя на производстве, но и многообразием постановок задач раскроя, трудностью создания совершенных математических моделей и выбора методов их решения. Задачи раскроя-упаковки представляют собой важный раздел методов оптимизации и исследования операций. В рамках решения этих задач развивается и исследуется общие проблемы характерные для указанных областей математики.

Проблема оптимального раскроя объединяет различные по математической постановке задачи. В литературе они встречаются под названиями : задачи раскроя, упаковки, размещения, загрузки, распределения и т.д. Общим для них является наличие двух групп объектов. К первой группе относятся большие объекты, ко второй- малые. Требуется установить соответствие и порядок назначения между ними так, чтобы некоторая целевая функция достигала минимум при выполнении определенных ограничений.

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

даже псевдополиномиального точного алгоритма решения этой задачи. На данный момент теория ЫР задач говорит, что для нахождения оптимального решения рассматриваемых задач существует только один путь - полный перебор всех допустимых вариантов и выбор из них оптимального [37].

Но несмотря на всю трудоёмкость процесса нахождения оптимального результата, на практике часто возникает необходимость его получить: это задачи единичного и мелко серийного раскроя ценных материалов; решение задачи остатка при крупносерийном раскрое. В исследовательском плане знание оптимальных решений дает возможность провести оценку эффективности эвристических алгоритмов и т.д.

Диссертация посвящена разработке точного алгоритма решения задачи линейного целочисленного раскроя (ЛЦР), базирующегося на методе ветвей и границ, и его программной реализации;, созданию оптимизационного алгоритма решения задачи упаковки И- мерных прямоугольных параллелепипедов в полубесконечную область.

Научная новизна диссертационной работы заключается в следующем:

■ разработан точный алгоритм решения задачи линейного целочисленного раскроя, базирующийся на методе ветвей и границ.

■ разработан и применён метод группировки для решения задач ЛЦР с большим количеством типов заготовок, подтвердивший свою эффективность в вычислительных экспериментах;

■ разработана математическая модель задач упаковки 1М-мерных прямоугольных объектов (N>2) в полубесконечную область.

■ разработан метод решения задач упаковки Ы-мерных прямоугольных объектов.

Предложенные в диссертации методы ориентированы на достаточно широкий класс прикладных задач. Разработанное программное обеспечение позволяет решать задачу линейного целочисленного раскроя и упаковки

прямоугольников в полубесконечную полосу. Это и составляет практическую значимость работы.

Результаты работы и отдельные её разделы докладывались и обсуждались: на 10-й Байкальской школе-семинаре «Методы оптимизации и их приложения» (1995, г. Иркутск), на семинаре в Институте вычислительной математики Дрезденского технического университета (1996г. г. Дрезден ФРГ), на международной конференции по исследованию операций (1998, г. Новосибирск),на семинарах кафедры Вычислительной математики и кибернетики Уфимского авиационного технического университета.

В первой главе диссертации изложена общая классификация задач раскроя-упаковки. Приводится краткий обзор методов решения задачи раскроя- упаковки (11-11).

В основу классификации моделей положены известные работы Л.В. Канторовича и В.А. Залгаллера, Э.А. Мухачевой , И. Терно и Дикхофа .

С учетом. приведенной классификации задачи, рассматриваемые в диссертационной работе, могут быть представлены как 1/У/1/М. [5]

Среди работ, посвященных линейному раскрою, выделяется статья Г. Вешера [33], в котором приводятся результаты вычислительных экспериментов для ряда алгоритмов с указаниям для них наиболее трудных классов задач.

Вторая глава посвящена задаче линейного целочисленного раскроя. Для её решения разработан точный (переборный) алгоритм. Приводится предложенная А. Кацевым схема генерации допустимых планов. На базе этой схемы рассмотрены методы построения дополнительных отсечений неперспективных ветвей. Показан механизм совместного использования точного алгоритма и симплекс метода для решения задач с большой

комплектностью заготовок. Описан прием, позволяющий точно решать задачи большой размерности.

Задача линейного целочисленного раскроя состоит в следующем:

Одномерные материальные предметы одинаковой длины Ь (прутки) должны быть разделены на меньшие части (заготовки) требуемых длин /1,/2,...,/т, так чтобы удовлетворить заказанные потребности Ь1,Ь2,...,Ьт. При этом требуется минимизировать общее количество используемого материала.

План раскроя - матрица, столбцы которой отвечают раскрою прутков (карты раскроя), а строки -заготовкам.

а11 а21 %1 1 ак1

а12 а22 а32 1 ак2

Е1п а2п а3п 1 акш

а,, - количество г-о вида заготовок в]-м раскрое прутка ; К - количество прутков в раскрое;

Как уже было отмечено, данная задача является №>- полной в трудном смысле. Поэтому для её решения приемлем только один подход- полный перебор всех допустимых вариантов и выбор из них оптимального.

Идея базовой схемы , предложенной А.Кацевым [47], состоит в следующем : методом полного перебора ищется такое размещение заготовок в прутках, чтобы суммарный остаток не превосходил допустимого резерва. Если это удаётся, то рассчитывается новое значение допустимого резерва затем перебор продолжается. В случае когда достигнута нижняя граница или перебор не дал результата, работа

алгоритма останавливается и текущее значение верхней границы будет оптимальным результатом.

В диссертационной работе в схему А. Кацева введены некоторые дополнительные ограничения, которые позволяют уменьшить число

просматриваемых вариантов, и при этом не потерять оптимум.

1 2 План раскроя А считается эквивалентным плану А в том случае, если

они состоят из одних и тех же карт раскроя и отличаются только порядком

их расположения.

Для избежания просмотра эквивалентных планов, можно использовать упорядочивание карт раскроя по приоритетам.

Пусть заготовки упорядочены по длинам. Будем считать, что из двух карт приоритетной считается та, которая содержит большее число самых длинных заготовок. Если они содержат одинаковое количество таких заготовок, то сравнение идет по второй по длине заготовке и т.д.

При осуществлении перебора, в момент генерации очередной карты раскроя, необходимо следить, чтобы её приоритет не превосходил приоритета предыдущей карты (на первую карту раскроя это правило не распространяется). В результате будут получаться только те планы раскроя, которые отсортированы по убыванию приоритетов, что позволит избежать просмотра эквивалентных планов.

Очевидно, что данное ограничение не может отсечь оптимальный план и поэтому оно приемлемо для использования в оптимальном алгоритме. Не трудно убедиться, что применения этого ограничения снижает трудоемкость алгоритма по сравнению с начальной схемой в К! - раз. Сложность представленного алгоритма:

где:

к- количество карт раскроя, входящих в план;

т- общее количество заготовок.

т/к - среднее количество заготовок, входящих в одну карту раскроя.

Определим еще одно свойство, которым обладает задача ЛЦР: Назовем Р-задачей такую задачу линейного целочисленного раскроя, где комплектность каждой заготовки равна 1.

Очевидно, что любая классическая задача, где каждой заготовке 4 соответствует некоторая комплектность Ьк > легко преобразуется в Р-задачу путем включения заготовки длины 1к- Ък раз.

Пусть даны две задачи Р 1={Ь,1п,т1) и ¥г=(Щ2рт2), ге 1..ть]е 1..т2 где Ь- длина'прутка;

т/, т2- количество заготовок в задачах Р1, Р2; 1Н,12] - длины заготовок в задачах Р1,Р2.

Задача Р1 доминирует над Р2, если каждой заготовке из Р1 можно сопоставить заготовку из Р2, чтобы для каждой из получившихся пар выполнялось условие 1ц <12] для всех ге 1..т\ и некоторых{1,2, ... , т2} при этом каждой заготовке из Р2 сопоставляется не более чем одна из Р1.

Пусть Х*(Р) - количество прутков в оптимальном целочисленном решении задачи Р. Тогда очевидным является утверждение : Если задача Р1={Ь,1ц,т/) доминирует над У2-(Ь,12],т2), то выполняется неравенство Ъ*{Р1)<Х*(Р2).

Данное свойство означает, что решив некоторую задачу Р1 можно выделить множество задач оптимальные решения которых «не лучше» чем уР1.

Базируясь на этом свойстве задачи ЛЦР, можно построить дополнительное отсечение. Идея его заключается в том , что бы на каждом

шаге работы алгоритма проверять получаемые подзадачи на доминантность и отсекать при. этом неперспективные.

Очевидно, что представленное ограничение не может отсечь оптимального решения, так как отсечение проводится только для тех подзадач, решение которых заведомо не лучше, чем решения ранее просмотренных задач, следовательно оптимум не теряется.

Но, несмотря на применение этих ограничений, сложность алгоритма по прежнему остаётся экспоненциальной, поэтому при решение задач большой размерности данный алгоритм в приемлемое время в большинстве случаев не даёт оптимума.

В диссертации изложены возможный сценарий применения этого алгоритма, которые позволят повысить эффективность его использования и сделают его приемлемым для решения задач большей размерности.

Известно, что задача линейного целочисленного раскроя (ЛЦР) является задачей линейного целочисленного программирования (ЛЦП) с неявно заданной матрицей ограничений.

Обозначим через: Е = (1,т,1,Ь ) задачу ЛЦР, где Ь- длина прутка, т-количество типов заготовок, 1=(11,12--, 11Г) и Ь=(Ь1,Ь2>... Ьгп) - длины и комплектности заготовок соответственно.

Тогда отвечающая ей задача ЛЦП можно сформулировать следующим образом :

Требуется найти совокупность раскроев г\-> г2^, их количество п и вектор интенсивностей их применения х = (х1,х2,...,хп) удовлетворяющих условиям:

1°. > О, целые у = 1 ,...,п;

п

п

3° ,г(х) = . достигает минимума.

7 = 1 7

Где, известны всевозможные способы раскроя прутка (карты раскроя) a(rj) = {aj\->aj2>-~>ajm) J= каждый из которых представляет собой

т — мерный вектор и - количество заготовок вида i, вырезаемых в j -м способе раскроя.

Данную задачу можно представить как частный случай модели стандартной линейной целочисленной минимизации:

z = cTXmitl^ÄX = b,x > 0, целые,

а соответствующая ей задача линейного программирования имеет вид:

z = сТх —> min, Ax>b,x> 0.

Обозначим :

z (Е) - оптимальное значение целочисленной задачи;

zc(E)~ оптимальное значение соответствующей задачи линейного программирования (ЛП).

Говорят, что задача линейного целочисленного раскроя Е обладает свойством округления до целого вверх (IRUP) [23], если

z\E) = [zc(E)1

Для проверки свойств IRUP некоторой задачи ЛЦР эффективно построение так называемой остаточной задачи. Имеем некоторую задачу раскроя E = (m,L,l,b) и пусть Xе- интенсивности планов раскроев, определяемые "из оптимального решения соответствующей задачи ЛП:

z = eTxc —> min,Ах = b,xc > 0.

Тогда задача Е = (l, т, 1,Ь-а[хс J) является остаточной к е.

И. Терно [26] было показано, что для выполнимости свойства IR "U Р некоторой задачи Е, достаточно доказать IR U Р для соответствующего

остаточного случая Е.

Из выше- сказанного следует, что для получения оптимального решения, необязательно решать переборным алгоритмом всю исходную задачу целиком. Достаточно рассмотреть только задачу остатка и если полученное решение будет обладать свойством IRUP, то оптимальный результат найден. В других случаях переборный алгоритм необходимо применить ко всей задаче.

В связи с этим схема применения переборного алгоритма будет выглядеть следующим образом : Пусть дана некоторая задача Е :

1. Симплекс- алгоритмом решается соответствующая ей задача ЛП

z = етх -» min, Ах = b, х > 0.

2. Исходя из решения задачи ЛП формируется задача остатка

E = (m,l,L,b-A[_xc J)

3. Решается задача остатка переборным алгоритмом.

4. Если задача остатка обладает свойством IRUP, то оптимальное решение найдено, иначе для получения оптимального решения необходимо применить переборный алгоритм для всей задачи Е .

Описанная схема во многих случаях позволяет находить оптимальные решения для задач с большой комплектностью заготовок. Однако, когда число типов заготовок велико (>100), а требуемая их комплектность мала (<5), данная схема будет работать неэффективно, т.к. задача остатка практически не будет отличатся от исходной задачи и применение ЛП не

позволит сократить размерность задачи Е которую необходимо решать переборным алгоритмом.

В диссертационной работе для таких задач было предложено использовать прием группировки.

Идея метода группировки заключается в следующем: Из исходной задачи Е генерируется некоторая другая задача Ег, которая содержит меньшее число типов заготовок, при увеличении их комплектности. При этом общее число заготовок Е и Ег одинаково. Генерируемая задача Ег должна отвечать следующим условиям :

1. Е доминирует над Ег.

2. Выполняется условие

3. Задача Ег - обладает свойством Ш1/Р.

Если задача Ег удовлетворяет условиям 1,2,3, то значения оптимального целочисленного решения задач Е и Ег совпадают т.е (2*(Ег)=£*(Е)).

В силу того, что задача Ег содержит меньшее число типов заготовок по сравнению с Е, задача остатка Ег будет иметь меньшую размерность чем

Е , а следовательно, время, затрачиваемое на её решение, уменьшается.

Очевидно, что из решения 2*(Ег) и соответствующего ему плана раскроя получается план раскроя, удовлетворяющий условию задачи Е, с выполнением условия (2*(Ег)=2*(Е)). Это следует из доминантности задачи Е над Ег. (Получение окончательного решения осуществляется путем замены заготовок в плане раскроя для задачи Ег на парные им , но имеющим не большею длину из Е ).

Применяемая в диссертационной работе процедура группировки, позволяет в большинстве случаев находить оптимальные решения для примеров, содержащих 300-400 типов заготовок. Ранее еще не удавалось получать оптимальные результаты для задач такой размерности.

В третей главе рассматривается задача 1\Г-мерной упаковки. Приводится постановка задачи и её математическая модель. Для возможности

построения алгоритма решения вводится дополнительная задача заполнения. Дается определение связанного множества задач заполнения. Приведен ряд теорем, показывающий соответствие между задачей мерной упаковки и связанным множеством задач заполнения.

В общем случае задачу И-мерной прямоугольной упаковки можно описать в следующем виде : Дано :

1. N >1 - мерность евклидова пространства.

2. Полубесконечный КГ- мерный прямоугольный параллелепипед с основанием 0=(01,02,...,0н-1).

3. Набор состоящий из т Ы-мерных прямоугольных параллелепип