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

2.2 Постановка задачи и ее математическая модель.84.

2.2.1 Математическая модель на основе задачи ЛЦП.86.

2.2.2 Плотная упаковка.86.

2.2.3 Матричная модель №-мерной упаковки.89.

2.3 Алгоритм нахождения оптимальной упаковки.96.

2.4 Нижняя граница для задачи упаковки.97.

2.4.1 Связь с задачей линейного программирования.98.

2.4.2 Улучшенная нижняя граница.101.

2.4.3 Численный эксперимент.105.

2.5 Заключение и выводы.106.

ГЛАВА 3. Точные методы решения задачи ортогональной упаковки в полубесконечную полосу 108.

3.1 Введение.108.

3.2 Эквивалентные задачи .109.

3.2.1 Эквивалентные наборы.109.

3.2.2 Эквивалентные задачи.111.

3.3 Симметричность в матричном представлении.111.

3.4 Комбинаторный алгоритм типа ветвей и границ для N — 2.. 115.

3.4.1 Метод построения допустимых матриц упаковки.116.

3.4.2 Построение допустимой вертикальной матрицы упаковки. 116.

3.4.3 Особенности построения горизонтальной матрицы упаковки 119.

3.4.4 Пример работы алгоритма.119.

3.5 Численный эксперимент.121.

3.6 Заключение.124.

ГЛАВА 4. Задача линейного раскроя 126.

4.1 Введение.126.

4.1.1 Линейно целочисленная модель.127.

4.2 Нижняя граница.128.

4.3 Метод значимых элементов для задачи ЛЦП.129.

4.3.1 Адаптация метода значимых элементов для задачи одномерной упаковки .132.

4.3.2 Алгоритм проверки невыполнения свойства целочисленного округления.135.

4.4 Модифицированный метод ветвей и границ.137.

4.4.1 Лексикографическое упорядочивание планов раскроя. 138.

4.4.2 Использование свойства IRUP для решения задач с большой комплектностью.150.

4.5 Метод группировки.151.

4.5.1 Группировочная задача.151.

4.5.2 Новые способы группировки.153.

4.5.3 Процедура разгруппировки .157.

4.5.4 Графическая интерпретация метода группировки.162.

4.5.5 Использование группировки для получения оптимального решения задачи линейного раскроя .162.

4.5.6 Модифицированный метод ветвей и границ с группировкой 164.

4.6 Численный эксперимент.165.

4.7 Результаты и выводы.168.

ГЛАВА 5. Упаковка N-мерных ортогональных многогранников (ОМ) 170.

5.1 Введение.170.

5.1.1 Модели и методы упаковки геометрических объектов произвольной формы.173.

5.1.2 Задачи генерации и планирования .179.

5.2 Постановка задачи размещения ортогональных многогранников 182 5.2.1 Приближенный метод решения задами планирования.

АГ-мерных упаковок ОМ.186.

5.2.2 Размещение ОМ в объекте .188.

5.2.3 Процедура уплотнения.191.

5.3 Программная реализация алгоритмов и численный эксперимент 194.

5.3.1 Описание программного обеспечения .194.

5.3.2 Подготовка численного эксперимента .197.

5.3.3 Численный эксперимент .198.

5.3.4 Развитие методов решения и другие постановки задачи упаковки ОМ .209.

5.4 Заключение и выводы.213.

Основные результаты и выводы.215.

Список использованных источников

218.

ПРИЛОЖЕНИЕ А. Метод Группировки. 232.

ПРИЛОЖЕНИЕ Б. Метод ветвей и границ. 236.

ПРИЛОЖЕНИЕ В. Максимальные зависимые от данных двойственные функции 237.

Актуальность темы

.

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

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

Краткий исторический обзор .

Первые фундаментальные научные результаты в области решения задач ортогональной упаковки принадлежат Л. В. Канторовичу. В 1939 г. им была издана брошюра [1], которая посвящена практическим ситуациям в организации производства, где могут быть полезными предложенные математические модели и возникающие при их анализе показатели.

В ней был описан метод решения задачи раскроя под названием: &bdquo-Мак i новки задачи размещения прямоугольных объектов с условиями связанности, которая является математической моделью многих задач управления и проектирования.

В течение 90-х годов прошлого столетия на тему раскроя-упаковки было выпущено шесть специальных изданий: под редакцией Г. Дикхоффа и Г. Вайшер [18] в 1990 г. С. Мартелло [19], [20] в 1994 г. Ю. Лиров [21] в 1995 г Е. Бисшофф и Г. Вайшер [22] в 1995 г. Э. А. Мухачева [23] в 1997 г., X Юнассе [24] в 1999 г. П. Ванг и Г. Вайшер [25]в 2002 г. Более того, сотни статей опубликованы в международных и российских журналах: European Journal of Operational Research (EJOR), Computers и Operations Research, Computers и Industrial Engineering, Operations Research Letters, Pesquisa OperacionalИнформационные технологии, Автоматика и телемеханика, Дискретный анализ*1 и исследование операций, Вестник высшей школы и другие центральные и ведомственные издания. При этом статьи и книги имеют как теоретический, так и прикладной характер.

Сообщество под названием SICUP (Специальная группа по интересам в области раскроя-упаковки) объединяет многих исследователей, заинтересованных в данной проблеме по всему миру. SICUP организовала несколько сессий по раскрою-упаковке в рамках международных конференций. В 2001 это сообщество было преобразовано в ESICUP (Европейская группа по интересам в области раскроя-упаковки). ESICUP организует ежегодную конференцию и специальные выпуски журнала «European Journal of Operational Research», посвященного данной тематики.

Краткий обзор методов .

Впервые качественная типология в области раскроя-упаковки проведена в 1991 г. немецким ученым Г. Дикхоффа [26]. Она принята в мировой практике и используется при изучении моделей и методов решения задач раскроя-упаковки. Разнообразие моделей определяется прежде всего фактором геометрии.

Система классификации Г. Дикхоффа описывает четыре основные характеристики проблемы раскроя и упаковки.

• Самая важная характеристика — размерность, определяющая минимальным числом измерения, необходимого для описания геометрии объектов. Проблемы более чем с тремя измерениями возникают, когда они расширяются до непространственных измерений, например добавляется время или масса.

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

• Классификация объектов — это характеристика, различающая проблемы, которые имеют объекты идентичной или различной формы.

• Классификация элементов ссылается на форму и номер элементов. Проблемы могут состоять из нескольких элементов, конгруэнтных элементов, множества элементов, состоящих из множества идентичных форм, и множества элементов, состоящих из нескольких разных форм.

В дальнейшем классификация была модифицирована Г. Вейшером. Основной показатель классификации (он еще и является основным показателем сложности рассматриваемой задачи) как и прежде осталась мерность рассматриваемых объектов.

Одномерные задачи раскроя и упаковки.

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

Задача загрузки рюкзака (Knapsack Packing, KP).

Для заданного множества I = {1, ., т} элементов известны вместимость рюкзака Lразмеры €, имеющие смысл веса или длины элементавеличины Q G IR+ (цена, оценка элемента). Требуется найти подмножество V С I такое, что достигает максимума при k < L. Эта задача разрешима методами динамического программирования за псевдополиномиальное время. В настоящие время существует множество различных алгоритмов, решающих данную задачу [27].

Задача одномерного раскроя (1 Dimensional Cutting Stock Problem, 1DCSP).

Дан одномерный материал длины L. Необходимо разделить на заготовки (такая терминология принята в промышленности) меньших длин ?1, ?2,. 1 т в требуемых количествах &i, 62, • • • bm соответственно, тчисло типов заготовок. Целью является минимизация количества использованного материала. В случае, если все 6? = 1, то данную задачу называют бинарной упаковкой (1 Dimensional Bin Packing Problem, 1DBPP). Исторически она является первой из класса задач упаковки, к которой удалось применить методы математического программирования.

Использование методов математического программирования В работах [2] и [3] показано, что проблема линейного раскроя относится к классу линейных целочисленных задач и рассматривали ее непрерывную релаксацию для случая массового производства: м z = ^Г^ Xj —> min Ах = b, х? Ъ1^.

3=1.

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

В 1981 г. С. Баум и Ж. Троттер отметили, что в большинстве случаев разрыв между оптимальными значениями непрерывной релаксации и целочисленной задачей не превышает 1, т. е. округленное решение дает оценку оптимальному целочисленному, решению [28].

В восьмидесятых и девяностых годах прошлого столетия теоретические исследования в этойобласти проводили ОМаркотте [29]- А. Дигел [30] и другие учёные., .;

Базируясь — наэтом факте построены схемы точногорешенияв работах. Р. Шайтхауер и Ш. Тернов [31]. Они использовали различные способыокругления релаксации и построение различных задач остатка. Продолжав ют развиваться точныеалгоритмы на базе,*линейногр целочисленного программирования. Приближение непрерывной релаксации к целочисленному оптимуму реализовали Г. Шайтхауер, И. Терно, А. Муллер и.Г. Н. Белов в: 1999 г. Они. предложили решать задачи-линейного раскроя методом секущих плоскостей Гомори [32]. Этот метод Г. Н: Белов и Г. Шайтхауер пролонгировали и-на случай раскроя материала различной длины [33]. Здесь они встретились с рядом принципиальных: и алгоритмических трудностей: моделирование задачи, генерация столбцов при н ал и чии. отсекающихплост костей и-друг ими. Аналогичный-метод.применяет О. Холтхауз для раскроя стандартного материала-различной длины. Предложенный. им подход разбиения основанша технике1 генерирования столбцов [34].: .

П. Ванце к непрерывной релаксации, добавляет ограничения ветвления-: [35]. Проведено численное сравнение метода: «ветвей и оценок» (П. Ванце) и отсекающих плоскостей (Г. Белов, Г. Шайтхауер). Тесты показывают преимущества: отсекающих плоскостей на задачах с большим разрывом оптимальности. Ф. Вандербек в 1998 г. приводит альтернативную постановку задачи линейного раскроя, где требуется минимизировать число типов используемого материала [36]'. Проблема была сведена к задаче целочислён-ного программированияВалерио де Карвалео в 2002 г. применяет1 модель линейного программирования, для решения задачи упаковки контейнеров.

Точные методы комбинаторной оптимизации.

Методы, основанные на линейном и линейном целочисленном программировании, оказались приемлемыми для решения задач линейного и гильотинного раскроя. Задачи линейного раскроя — классические представители NP-трудных проблем, и для их решения, как правило, применяются методы полного перебора с отсечением неперспективных вариантов. Еще в 1973 г. И. В. Романовский и Н. П. Христова предложили для решения дискретных минимаксных задач метод дихотомии [38], который получил развитие и для решения задач ВРР в работе С. В. Кацева [39].

В 1977 г. И. В. Романовским представлена общая идея переборного метода для решения экспериментальной задачи и предложена его конкретизация в виде метода «ветвей и границ» (Method Branch and Bound, MBB) для решения задач упаковки [40]. Независимо за рубежом выходит серия статей Мартелло С. и Тоз П., посвященная разработке улучшенных версий MBB, называемых методами МТР, для решения линейного раскроя. Размерность задач, разрешимая этими алгоритмами, невелика (<200). Перспективы повышения эффективности алгоритмов МТР состоят в их гибридизации с другими (чаще эвристическими) приемами и алгоритмами.

Впервые серьезная работа по гибридизации точного алгоритма МТР с эвристиками выполнена в 1997 г. Шолл А., Кляин Р., Юргенс Г. предложили гибридный алгоритм BISON [41]. Они используют ранее известные и новые алгоритмы отсечения в рамках МТР, метаэвристику «поиск с запретами «и несколько алгоритмов расчета нижних границ. Проведенный в работе [42] всесторонний вычислительный эксперимент показал, что результаты комбинаторных методов зависят не только от размеров задачи, но также и от относительных размеров заготовок. В этой работе были выделены классы задач, которые являются трудными для решения комбинаторными методами.

Так же задачу линейного раскроя можно представить как частный случай задачи о покрытии множеств. Методами решения этой задачи занимаются в Омской школе оптимизаторов под руководством A.A. Колоколова [43], [44].

Задачи ортогональной упаковки.

Данная категория допускает множество различных постановок задач упаковки. Общим для них является следующее:

• грани рассматриваемых объектов должны быть параллельны осям координат;

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

При этом задачи могут различаться по.

• мерности рассматриваемых объектов (2,3, ., N);

• размерам объекта, в который происходит упаковка;

• типу упаковки: гильотинная или негильотинная;

• функции цели.

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

В качестве основной принято рассматривать следующую задачу упаковки (Packing Problem, РР): имеются малые элементы, их необходимо разместить без взаимного перекрытия внутри больших объектов так, чтобы заданная целевая функция достигла минимума (максимума). В категории «задач раскроя и упаковки» содержится множество прикладных задач, которые изучаются с давних пор. Большая часть таких задач являются NP-трудными комбинаторными проблемами, и для них не существует точных методов решения полиномиальной сложности.

Задача упаковки прямоугольников в полосу (2 Dimensional Stnp Packing Problem, 2DSPP).

Один из размеров полосы, например, ширина W задан, второй длина — является переменным. Требуется найти упаковку в полосу минимальной длины L. Эту задачу, следуя А. Хинксман, часто именуют 1.5DBP [45].

Задача упаковки прямоугольников в контейнеры (2 Dimensional Bin Packing Problem, 2DBPP).

Оба размера, ширина W и длина L заданы. Требуется найти минимальное количество контейнеров, в> которые упакованы все малые прямоугольные элементы.

Задача упаковки прямоугольников в открытую область (квадрант) (2 Dimensional Area Packing Problem, 2DAPP). Оба размера, ширина W и длина L являются для прямоугольного объекта переменными. Требуется найти упаковку элементов в угол, образованный осями координат, совпадающими с шириной и длиной области, для которой площадь огибающего элементы прямоугольника достигает минимума.

Задачи гильотинного раскроя.

Часто встречается задача гильотинного раскроя (2 Dimensional Guillotine Cutting Stock, 2DGCS), когда возможными являются только сквозные резы, параллельные кромкам материала (см. рис. 1). Собственно, задача гильотинного раскроя является обобщением линейного раскроя на двухмерный случай. Для ее решения применяются аналогичные с одномерным случаем методы. Что касается гильотинной упаковки, то это упаковка рядами, например, так размещаются контейнеры и автомашины на палубах судов.

В задаче гильотинного раскроя полубесконечной полосы (2 Dimensional Guillotine Strip Cutting, 2DGSC) требуется найти гильотинный раскрой рулона на заданные прямоугольные предметы, который обеспечит минималь.

Рисунок 1 — Прямоугольные упаковки: а) — допустимая ортогональная упаковкаб) — неортогональная упаковкавнедопустимая ортогональная упаковка.

Р5 F9.

Р10.

Р4 vv> Р8 * rtrttrr,.

Р2 РЗ '/S///SS///////// ////.

Рб Р7 Pll.

Р1 W/V ///S/,.

Р2 РЗ.

S/SSSS///SSS/ •//i"////////// '//////////// V/S/S/S////S* Р4.

PI а) Ь).

Рисунок 2 — Карты раскроя: а — гильотинный раскройбнегильотинный раскрой-упаковка ную длину использованной части полосы (см. рис. 2). В задаче гильотинного раскроя листов (2 Dimensional Guillotine Bin Cutting, 2DGBC) требуется найти набор гильотинных раскроев, обеспечивающий минимальный расход листов.

Методы решения задачи гильотинного раскроя базируются на задаче одномерного раскроя и рассматривались как обобщение последней в первых работах Л. В. Канторовича, В. А. Залгаллера, П. Гилмор и Р. Гомори. Методы, алгоритмы и технологии, разработанные для задач линейного раскроя, адаптированы на случай гильотинного (2-х и 3-хмерного) раскроя. Подробно эта задача в условиях массового и серийного производства описана в работах Э. А. Мухачевой [7],[46] в России и И. Терно, Р. Линдер-ман и Г. Шайтхауер [47] в Германии. Метод склейки И. В. Романовского, разработанный вначале для задач линейного раскроя, также был обобщен на случай гильотинного раскроя [5]. В современных работах авторы часто исходят от тщательной проработки ШСБР. Например, метод отсекающих плоскостей, подробно разработанный и исследованный Г. Н. Беловым и Г. Шайтхауер, обобщен ими на случай гильотинного раскроя [33].

Теоретическое исследование метода решения задачи единичного гильотинного раскроя проведено Э. Ю. Лернером и В. Р. Фазыловым [48]. Ими введена функция гильотиниого размещения, сходная с оценочной функцией при использовании методов локального поиска оптимума. Предлагаемый авторами аппарат позволяет построить все множество прямоугольников, достаточных для размещения заданного набора деталей, из которого практик может выбрать наиболее приемлемый для конкрегной ситуации вариант. В работе приведены оценки трудоемкости вычисления функции гильотинного размещения. Алгоритм полиномиальной сложности для решения задачи гильотинного раскроя без применения линейного программирования разработан в Белоруссии ученым А. Г. Тарновским [49],[50].

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

Геометрические методы.

В 1985 г. А. И. Липовецкий сформулировал задачу упаковки прямоугольников как проблему комбинаторной оптимизации и предложил &bdquo-метод зон" для нахождения оптимального решения. На основе понятия «зоны» доказывается, что для любой упаковки прямоугольников можно указать такой их порядок, при котором каждый следующий прямоугольник не пересекается ни с одной из зон предыдущих (топологическая сортировка)[51]. Метод зон реализован в 1988 г., усовершенствован и исследован в 2001 г. В. В. Бухваловой (С.Петербург) [52].

В 1998 С. Мартелло и Д. Виго предложили контурную концепцию для поиска оптимального решения упаковки прямоугольников [53]. Идея этого подхода схожа с &bdquo-методом зон". Они показали, что любую упаковку можно получить, располагая прямоугольники! на некотором ступенчатообразном контуре. После расположения очередного* прямоугольника этот контур модифицируется. Г. Шайтхауер предложил для сокращения числа вариантов, ряд отсечений, которые позволяют не рассматривать симметричные варианты [54].

Методы на базе линейного целочисленного программирования.

В 1985 г. Я. Бейсли предложил рассматривать задачу упаковки прямоугольников как задачу линейного целочисленного программирования с 0 — 1 переменными [55]. В дальнейшем этот подход был развит в работе Е. Хаджиконстатешно и Н. Кристофильда [56].

Ю. Стоян и М. Новожилова адаптировали в 1988 г. метод непрерывной оптимизации1 к решению задачи упаковки многоугольников [57], где в качестве частного случая рассматривается задача упаковки в полубесконечную полосу. Условия размещения прямоугольников описываются системой 1 неравенств. Разработана стратегия построения множества систем уравнений и строится набор правил отсечения бесперспективных вершин дерева решений. Задача поиска глобального минимума сводится к перебору п!/2 постановок вариантов размещения объектов. Дальнейшее развитие, метод получил в 1999 г. в статьях Ю. Стоян, М. Новожилова [58] и А. Панкратова [59]. Успех использования аппарата линейного программирования во многом зависит от модели, которой описывается задача.

Мателштические модели представления задачи N — мерной упаковки.

Рассмотрим N мерный ортогональный параллелепипед (область) с гранями к = 1, ./V и размеры т предметов и% 6 для каждого г е / = {1, 2,. , И}. Спрашивается, можно ли разместить предметы внутри области ?

Эта задача была рассмотрена в работах [60] и [61]. Простейшая математическая модель описывает в явном виде условия непересечения предметов. Эту модель называют естественной моделью.

Необходимо найти где к — 1, N и г = 1, т, удовлетворяющие следующим условиям: г^ < х) или х^ < ии1- 3 к V г < з.

Эта модель исследовалась в работе Падберга [62]. В его работе была сделана попытка решать данную задачу с помощью линейного целочисленного программирования. Но в силу того, что непрерывная релаксация этой модели очень &bdquo-слаба", удалось точно решать лишь задачи небольшой размерности т < 10. Для больших размерностей этот метод не годится, так как идет квадратичный рост целочисленных переменных.

В работе [63] предлагается следующая модель задачи упаковки. Рассмотрим все возможные координаты положения г предмета по к—мерности. Тогда для каждой размерности к = 1, N и каждого предмета г = 1, т определим множество возможных положений.

А (к, г) = {0,. Зь-ш?}.

Рассмотрим двоичные переменные которые указывают на нахождения начала г предмета в позиции Позиционные переменные впервые были определены для двухмерного случая в работе Балдачи и Бошетти [64]. Более того, для описания условия непересечения предметов введем дополнительные бинарные переменные. Для каждой размерности к = 1, N и упорядоченной пары предметов 1 <�г<�э<�т определим бинарную переменную.

Значение = 0 указывает на то, что проекции { \ э предметов на кю координатную ось не пересекаются. Это возможно только в том случае, когда zfs = 1 и ZjS] = 0 для sj из промежутка: а (к, s, i, j) — {тах {s — w^ + 1,0},. min {s -1- го* — 1, Sk — ги* }}.

Очевидно, что если zfs = 1 и z*t = 1 для некоторого t € a (k, s, i, j), то ¿-Ь = 0. Тогда модель будет иметь следующий вид:

J2 4 = 1. г" = Т/т к = TJV s&A (k, i) zl + 22 4 -1 ^ s € о. V" < j, V*-, tea (k, s, i, j) N.

4 6 {0,1}, seA (k, i), Vi, fc,.

0,1}, Vicj.

Первое условие означает, что каждый предмет начинается в каждой мерности один раз. Второе и третье условие гарантируют, что предметы не будут пересекаться. Заметим, что условие, задающее переменные можно переписать в следующем виде: 4+? 4-!. t.

Также для сокращения пространства решений и генерации только нормализованных решений [64] в модель добавляются следующие неравенства: vfc, г? s?{mmw, г.

Г*.

Sk — min 1U-C}, v/c. i: s—w^> 0.

Это неравенство указывает на то, что предмет может начаться только в начале области или в точке в которой закончился другой предмет. Следующее неравенство сокращает симметричные варианты: т. е. первый предмет должен начинаться только в первой четверти области.

Представленная модель имеет 0(N^2kSk + Nm2) переменных и неравенств.

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

Представленная модель относится к классу задач целочисленного программирования. Эти задачи успешно исследуются учеными из научной школы Колоколова A.A. Ими преложены различные методы нахождения оптимального решения этой задачи, которые основаны на разбиении L классов [65]—[66] .

Псевдополиномиальное число переменных делает затруднительным использование данную модель для прямого расчета упаковок. Даже при Si = ?2 = 20 и т = 15, пакету линейного программирования CPLEX 9.0 требуется много времени для того, чтобы решить задачу.

Методы на базе интервальных графов.

Другой подход для нахождения оптимальной упаковки в 1997 г. предложили С. Фекет С. и Ж. Шеперс [61]. Они предлагают использовать интервальные графы для представления произвольной упаковки.

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

Нижние границы.

В 1990 г. Мартелло С. и Тоз П. предложили несколько элементарных классов нижних границ, вычисление которых основывается на отношении размеров прямоугольников и полосы [67]. Например, простейшей из приведенных границ является отношение суммарной площади прямоугольников к ширине полосы.

Фекет С. и Шеперс Ж. в [68] показали возможность применения двойственно возможных функций как основы для вычисления нижних границ. Идея метода заключается в следующем.

Пусть XI? [0,1], тогда функция ф (х): [0,1] —> [0,1] называется двойственно возможной, если для любого конечного множества б" неотрицательных вещественных чисел справедливо следующее:

Для определения нижней границы можно использовать вместо величин Х{ их значение ф (х{). Они представляют особые классы двойственно допустимых функций, введенных и основанных на специальной технике округлеI ния. Так же доказано, что эти нижние границы доминируют над элементарными.

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

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

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

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

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

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

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

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

Для достижения выбранной цели в диссертационной работе поставлены следующие задачи:

1. Дать декомпозиционное представление задач многомерной ортогональной упаковки и найти метод построения оценки значения оптимального решения.

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

3. Получить критерий максимизации двойственно-допустимой функции и применить его для построения оценки значения оптимального решения задачи ортогональной упаковки.

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

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

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

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

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

Результаты, выносимые на защиту:

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

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

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

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

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

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

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

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

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

3. Установлен критерий максимальности двойственно-допустимой функции, зависимой от данных. Показано, что не все известные ранее функции являются максимальными. Предложены полиномиальные алгоритмы преобразования произвольной двойственно-допустимой зависимой от данных функции к максимальному виду, что позволило выявить новые нижние границы для задачи ортогональной упаковки.

4. Теоретически обоснованы численные процедуры построения оптимального решения задачи одномерной упаковки (метод группировки, модифицированный метод ветвей и границ). Выделены наиболее трудные с точки зрения перебора классы задач. Доказано необходимое условие, при котором задача обладает свойством целочисленного округления.

5. Предоставлено кортежное представление Ы-мерных ортогональных многогранников. Созданы оптимизационные алгоритмы их плотного размещения для решения ряда практических задач промышленности.

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

Апробация работы. Результаты диссертации докладывались на Байкальских школах-семинарах «Методы оптимизации и их приложения» (1995, 2001, 2008 г., Иркутск), семинарах в Институте вычислительной математики Дрезденского технического университета (1996, 2000, 2002, 2006, 2008, 2010 г., Дрезден, Германия), международных конференциях «Дискретный анализ и исследование операций» (1998, 2000, 2010 г., Новосибирск), международной конференции «Математическое программирование и приложения» (1999, 2001, 2007, 2011 г., Екатеринбург), международной конференции «Распределенные системы: оптимизация и приложения в экономике и науках об окружающей среде» (2000 г., Екатеринбург), международной конференции Informs (2000 г., Сан-Антонио, США), семинаре, посвященном 90-летию со дня рождения С. Н. Черникова, «Алгебра и линейная оптимизация» (2002 г., Екатеринбург), международной конференции «Проблемы оптимизации и экономические приложения» (2003, 2006, 2009 г., Омск), международной конференции 1-ESICUP (2004 г., Виттен-берг, Германия), Крымской осенней математической школе (2005 г., Севастополь, Украина), международной конференции 3-ESICUP (2006 г., Порто, Португалия), международной конференции CSIT (2009 г., Крит, Греция), семинарах кафедры вычислительной математики и кибернетики и кафедры математики Уфимского государственного авиационного технического университета, семинарах кафедры вычислительной математики и кафедры математического моделирования Башкирского государственного университета, семинарах отдела вычислительной математики Института математики с вычислительным центром Уфимского научного центра РАН, семинаре «Математические модели принятия решений» Института математики имени СЛ. Соболева Сибирского отделения РАН, семинаре Отдела математического программирования Института математики и механики Уральского отделения РАН.

Публикации. Основные результаты диссертации получены лично автором и опубликованы в 50 научных статьях. В их число входят 1 монография (в соавторстве), 10 статей из перечня ВАК российских рецензируемых научных журналов, 2 статьи, в зарубежных рецензируемых журналах.

Структура диссертацииДиссертация состоит из. введения, пяти глав основного содержания, заключения-, приложений и' списка литературы. Объем. работы — 237 страницы, библиография — 121 наименований;

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ.

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

В первой главе рассмотрена задача многомерной ортогональной упаковки в'" контейнер.. Предложенметод декомпозиции, позволяющий получить линейную релаксацию этой задачи. Получены, условия, ! при которых она не имеет решения-. В заключительном, разделе: рассмотрены двойственно-допустимые функции, зависимые от данных.

В первом' разделеглавы представлены общие методы построенияоценок оптимального значения для задач дискретной оптимизации, которые: представляются в виде линейных целочисленных моделей. Детально рассмотрены методы, основанные и, а непрерывной релаксации. В конце раздела приведено общее описание метода построения: граничной точки:

Во втором разделе рассмотрена классическая задача А/-мерной ортогональной упаковки в замкнутую область (контейнер), которая состоит в следующем: Дано-множество предметов, состоящих из т штук К-мерных ортогональных параллелепипедов Д = {П.-}, ¦} 6 3 — {1, ., т}, заданных своими размерами Ы^ = (г{, 7^) € К+' и контейнер З' =.

5 г, ., Ьу)? являющийся• также АГ-мерным ортогональным параллелепипедом. Требуется1 выяснить, можно ли все предметы из К упаковать в 5 без перекрытия? Поворот предметов запрещен.

Положение параллелепипедов И, в Б задается набором Р = {Рь ., Рто} их «левых нижних» координат, которые являются векторами^з ~ ^ъ— ¦ >27лг)> 3 ^ 3 • Допустимость векторов Р., определяется неравенствами.

Й>0, й+ з е ^ к е/ = {1,. Щ, (1) для любых Зъ 32? «Л 31 32, найдется А- 6 /, для которого.

2) й1 + Г3к} < р{2 или р12 + г12<�р1}.

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

Путем замещения условий типа «или» в неравенствах (2) на дополнительные бинарные переменные эта модель сводится к линейному целочисленному виду. Ее численно исследовал М. Падберг. Он показал, что она обладает слабыми релаксационными свойствами и не может быть использована для решения задач с числом параллелепипедов т > 10.

В диссертационной работе предложена релаксация этой задачи, которая основана на свойствах ортогональных сечений. Введем множество /дг, элементами которого являются всевозможные подмножества I, кроме пустого множества и самого /, т. е. I^ = {{1} ,., {2,., ./V}}. Множество Iдг содержит все возможные наборы координатных направлений, параллельно которым располагаются секущие плоскости.

Выберем подмножество С € /дг и определим подпространство Xе = (е51, е52, ., являющееся линейной оболочкой базисных векторов с номерами из = {<71, и дополнительное к нему подпространство, А. Очевидно, что.

0 = Рассмотрим семейt ство ¿-—мерных плоскостей, параллельных подпространству* Xе. Положение каждой плоскости однозначно определяется выбором точки Н с соответствующим радиус-вектором Ъ. Е Xе. Обозначим плоскость данного семейства как А^ = Ь + Xе.

Предположим, что система (1)-(2) совместная, а Р — допустимое решение. Тогда любой плоскости А^, пересекающей контейнер Б, сопоставим т-мерный бинарный вектор по следующему правилу: ас (Д, Р) = (аь., ато) т, где .

1, если А^ пересекает г-ый параллелепипед,.

3).

О в противном случае. I.

Вектор ас (/г, Р) назовем определяющим вектором.

Пусть Ас = (а^,., матрица, столбцами которой являются всевозможные различные определяющие вектора ас (/г, Р), и Мо — их число. Для каждого набора G Е построим релаксационное множество Мо Л.

УС •={УС: £*?<Ц = € Е^ I, (4) дей) где Ь9 Е Мт с элементами Щ = 3 ^ Множества У° являются декомпозицией исходной задачи по различным наборам координатных направлений.

Теорема 1 Если существует подмножество С Е /дг, для которого Ус = 0, то система (1)-(2) несовместна.

Теорема 1 может служит основой для создания оценок значений целевых функций различных задач ортогональной упаковки. В силу большого числа векторов ас проверка условия Уа = 0 осуществляется с помощью симплекс-метода с генерацией столбцов. Точность получаемого ответа зависит от способа генерации векторов а°. В диссертационной работе рассмотрено несколько различных способов построения определяющих векторов ас, которые зависят от мощности (7. При |С?| = 1 решается задача о загрузке 0−1 рюкзака. Для случая > 1 предложена рекурсивная схема построения аР, а также метод, основанный на непрерывной релаксации модели Бейзли.

Рассмотрим условие неперекрытия параллелепипедов. Очевидно, что если у двух параллелепипедов проекции на все координатные оси с номерами 1, ., N перекрываются, то эти два параллелепипеда будут перекрываться в пространстве.

Возьмем пару параллелепипедов из К с номерами р иди обозначим через гс{р^) := {г: а^р = = 1, € множество номеров определяющих векторов, для которых а^р = а^ = 1.

Для выяснения перекрытия параллелепипедов с номерами р и д по различным координатным направлениям определим вспомогательные множества.

УШ := {у°: У° е Уг = М € д)}. (5).

Связь между множествами У^ф и возможным геометрическим расположением параллелепипедов в 5 устанавливает следующая лемма. Лемма 1 Пусть р, д и (7 таковы, что = Тогда для любого допустимого размещения параллелепипедов И в контейнер в существует точка Ь € Xе, для которой плоскость А^ пересекает р-й и д-й параллелепипед.

Из леммы 1 следует, что проекции р и д параллелепипедов на подпространство Ха пересекаются, то есть пересекаются их проекции на все координатные оси с номерами из.

Теорема 2 Если существуют номера р и д и набор Е = {Оа1, Сто-2, ., Сд-,}, для которых выполняется и<�теЕ = I и У^^ = 0 для всех 6? € Е, то параллелепипеды К нельзя разместить в области.

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

Множества Y^^ также использованы для нахождения устойчивых сочетаний и сокращения числа неравенств в системе (1)-(2). Для этой цели строятся два множества et={(p, q): 3G, г 6 G, Ygtq) = 0}, (6) {(Р, я) •• (Р. я) € Vj G //*}. (7).

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

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

Понятие консервативгюго масштабирования (Conservative Scales (CS)) было сформулировано С. Фекете в 1997 г. Он определил его как модификацию размеров параллелепипедов, для которой из разрешимости исходной задачи следует разрешимость задачи с модифицированными размерами.

Ж.Карлье для построения CS предложил использовать зависимые от данных двойственно-допустимые функции (ЗДДФ) .

Пусть даны константы С, С > 0 и 0 < Ci < С, V г G V. Функция /: {ci,., с&trade-, С} —> [О, С') называется ЗДДФ, если для любого V С V, из условия Y^ieVt ci<=i) < fiC) = c'¦

Он показал, что при существовании набора ЗДДФ fk, k = 1, N с условием IL fki^i) > ELfk{Sk) задача^R, 3^ имеет отрицательный ответ.

В работе введено понятие максимальной ЗДДФ. Функция / называется максимальной ЗДДФ, если не существует другой функции/, для которой.

Сг). /(С*) с т/ /Ы ^ /(<*) «<, и при этом существует г? V с условием < -=-.

1{0)-дсУ /(СО /©.

Обозначим через КР (С, а,(3) классическую задачу загрузки 0−1 рюкзака.

ТО 771.

КР (С, а, /3) = тах < У^ /Згжг: аг • хг < С >, жб{одГ I где, а? К&trade- - веса предметов п /3? — их стоимость, а С — размер рюкзака.

Теорема 3 Пусть, а = (с1,., ст) и (3 = (/(сх),. ,/(ст)). Функция / максимальна тогда и только тогда, когда лС) = КР{С, а,(3), (8) с,) = КР (С, а, /?) -КР (Са, аа, 13 /(*)), Уг? V. (9) Показано, что многие из ранее известных ЗДДФ не обладают свойствами максимальности. В работе представлены алгоритмы различной сложности (квадратичной и кубической) для максимизации произвольной ЗДДФ. Вычислительный эксперимент показал, что эффективность применения ЗДДФ после максимизации повысилась на 50% .

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

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

Полубесконечной полосой в, заданной своими размерами (?1, 52, ., £лг-1)? М^-1, называется множество точек х € X = {х, 372, • ¦ •) Хм) таких, ЧТО 0 < Ж/г < к = 1, ., N — 1 и О < х^.

Пусть для некоторого натурального числа N > 2 и полубесконечной полосы б" с размерами (бх, ?2, • • •, ?>N-1) € К±1 известен набор из т параллелепипедов К = {П^-}, 3 € 3 = {1,., т}. Каждый из них задан своими размерами = (г], ., г^) 6. Считаем, что 0 < г3к< € <7, к = 1, ., N — 1.

Требуется упаковать Ив 5 так, чтобы длина занятой части 5 по Л^-му координатному направлению была минимальной. Поворот запрещен.

Упаковка параллелепипедов И в 5 задается набором координат Р = {Р^}, где = (р], ., р^), ^ € 7, удовлетворяющих условиям.

А> о, Р*к + г{<3к1 jeJ, k = {h., N-l}. (10).

Для любых .71, ?2 € «/, jl^32, найдется к € /, для которого или р?2+г?2.

И).

Определим = {Р} как множество всех Р, отвечающих условиям (10)-(11). Обозначим.

0(Р) = шах (^ + г^).

3=1,т.

Требуется найти такой Р € Эй, для которого.

0(К, 5О = тт0(Р). (12).

Набор Р* Е назовем оптимальным, если 0(Р*) = ©-(И, в). В работе предложена процедура факторизации множества К, которая базируется на идее плотного размещения параллелепипедов. Набор Р? К называется плотным, если выполняются следующее условия.

V1 е^к Е I: (й = о) у (31<�г<�т, р1=рьк + 4) (13).

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

Для поиска оптимального решения в диссертации предложено матричное представление решения системы (10)—(11). Для достижения этой цели используется метод декомпозиции, описанный в главе 1.

Пусть для задачи (К, Б) известно некоторое допустимое решение Р. Для каждого к € I рассмотрим множество координатных направлений, задающих гиперплоскости = /дг Аи дополнение к нему Ск = к. Выберем т + 1 точку на А-—той координатной оси следующим образом: /¿-о = 0, Нк = тт (р]. + г3к: + г^. > у € </), г = 1, т. Проведем гиперплоскости Л^ и сконструируем матрицу Ак &euro-Е {0,1}тХ7П с определяющими векторами а? к{Р, кк) в качестве столбцов.

Построенная матрица Ак кодирует положение каждого параллелепипеда по к-му координатному направлению в виде непрерывной последовательности единиц в строках. Обозначим Zk = (гк,. , г1^), где.

Полученные Ак называются матрицами упаковки, а векторы Еквекторами упаковки.

Пример для N = 2 изображен на рис. 1.

Рисунок 3 — Пример расположения гиперплоскостей для N = 2.

Получаемые при этом матрицы упаковки имеют вид 0 0 1 1 1 1.

Л1^ 1 о о о о о ^.

1 1 0 0 0 0 0 11 110 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 л2 =.

1 1 0 0 0 0 0 0 0 0 1 0 11 110 0 1110 0 0 1 0 0 0 0 0.

Из способа построения матрицы Ак и вектора следует, что они отвечают следующим условиям.

Условие 1 Продолженностъ единиц. Для каждой строки ] € 3 ак¦ = у.

14) матрицы Ак, к = 1, ЛГ найдутся столбцы г3ь и г{, для которых.

1, если г3ь ^ г ^ 0, в противном случае. Условие 2 Завершенность. В каждом столбце матриц Ак, к = 1, ЛГ заканчивается, по крайней мере, одна из последовательностей единиц е 3"о Е </, = 1 и а^ = 0 для г = (¿-о + 1), га. у.

Условие 3 Связь между элементами векторов Ек и матриц Ак, к = 1, N с размерами параллелепипедов И устанавливается соотношением га.

ХХ-*?" 7*' (15) г=1.

Условие 4 Неперекрытие параллелепипедов. Для любой пары параллелепипедов 1 < р < д < т существует координатное направление к* € I такое, что а% + а** <2, г = Т^Ж. (16).

Условия 1−3 задают размещение параллелепипедов по каждому координатному направлению отдельно, а условие 4 устанавливает связь между всеми компонентами матричного представления. Условие 3 указывает на однозначность получения вектора^ из матрицы Ак. В работе установлено взаимооднозначное соответствие между Р 6 К и полученным матричным представлением.

Теорема 4 Пусть для задачи (И, б} известен набор Р 6 Ж. Тогда ему однозначно сопоставляются матрицы Ак и вектора Zk, к = удовлетворяющие условиям 1−4. Обратное, если заданы матрицы Ак и вектора Ек, к = удовлетворяющие условиям 1~4, то им однозначно сопоставляется Р, для которого т г=1.

Из теоремы 4 следует, что задача нахождения оптимального Р эквивалентна нахождению Ак и к = 1, N, с которыми значение достигает минимума.

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

Нижней границей задачи (R, S) называется функция, зависящая от входных параметров задачи Ьь{R, S) > 0, такая, что ?&(R, S) < 0(R, S).

Величина Ьъ{R, S) играет большую роль при доказательстве оптимальности заданного набора координат Р. Так если Ьь (R, S) = 0(Р), то Р — оптимум. В этом случае можно доказать оптимальность решения без полного перебора. В работе предлагаются следующие способы вычисления.

Lb (R, S).

Сопоставим каждому множеству направлений Gk следующую задачу линейного программирования.

MGk.

Ск{R, S) = У2 у? min, AGkyk =, ук е.

Лемма 2 Пусть для (R, S) известна некоторая матрица k € I, отвечающая условиям 1−3. Тогда определяющие вектора из Ак образуют допустимое базисное решение в соответствующей задаче линейного программирования (17).

Из теоремы 4 и леммы 2 следует (c)(R, S) > CN (R, S). Значение bf (R, S) = CiV (R, S) называется lp-нижней границей. Следующая теорема определяет условия, при которых значение нижней границы может быть улучшено.

Теорема 5 Пусть дана некоторая задача (R, S). Для выполнения условия 0(R, S) < 1/5 (R, S) необходимо, чтобы.

• Ck{R, S) < Lb (R, S);

• существовал набор базисных решений задачи (17), удовлетворяющих условию 4.

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

Возможно > дальнейшее уточнение нижней границы. Пусть известно некоторое значение 5). Сформируем контейнер следующим образом.

5 г = г = 1, N — 1 и б’дг = Б). В этом случае получаем задачу ортогональной упаковки в замкнутую область которая была рассмотрена в первой главе. Если удастся доказать, что эта задача не имеет решения, то Ьь{В-, 5) < 0(11, 5) и значение 1/ь (К-> 5) увеличивается.

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

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

Р<(гкЛ) := {а: ?а{гк <Як, а € {0,1}т}, к=Т^, где гк = (г,. , г&trade-). Будем говорить, что задачи ортогональной упаковки^Н, и эквивалентны, если р<(гкЛ) = Р<(гк, вк), к = IГЛГ. 39.

В работе показано, что если задачадИ,. S’y эквивалентна^R, S’y, то из решения одной можно получить решение другой задачи и наоборот.

Теорема 6 Задачи (jl, S^ и^R, S^j эквивалентны тогдаи только тогда ' '.'.¦. •. ' ¦. '.

Теорема 6 дает простое условие проверки эквивалентности двух произвольных задач. В диссертации показано, что множество размеров параллелепипедов задач, эквивалентных заданной, описывается выпуклым многогранником, что позволяет построить эквивалентную задачу, обладающую заданными свойствами. Для этой цели решается задача линейного программирования: со специально заданной целевой функцией! Данная процедура позволяет выбрать наиболее удачную (в вычислительном плане) постановку задачи среди класса эквивалентных.

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

Основным свойством матриц упаковок Акпозволяющим организовать д их эффективный перебор, является свойство симметрии.

Теорема 7 Если для^R, S^ известные матрицы упаковки Ак и Ак отличаются от другой только транспозицией столбцов, то =.

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

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

В заключительном разделе описаны особенности реализации алгоритма для N = 2, дано описание классов тестовых задач и полученных на них результатов. Проведено сравнение полученных результатов с другими известными алгоритмами, которые подтверждают конкурентоспособность матричного подхода. Даны практические рекомендации по использованию разработанного метода. Представленный подход является унифицированным, так как используемое матричное представление позволяет учитывать специфику постановок различных производственных задач, а также может служить основой для разработки приближенных методов.

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

Классическая задача одномерной упаковки состоит в следующем. Дан набор одномерных объектов длины Ь. В них необходимо упаковать предметы ДЛИН I = (?1, • • •) в требуемых количествах Ь= {Ъ, 62) • • • Ьт), где т — число типов предметов. Цель — минимизация количества использованных объектов. Входные данные задачи обозначим. Е = (Ь, т,1,Ь).

В литературе данная задача известна как задача линейного раскроя. Она формулируется в виде задачи линейного целочисленного программирования. Наиболее удачная модель была предложена Л. В. Канторовичем, В. А. Залгаллером и, независимо, Р. Гомори и П. Гилмори: каждый допустимый способ упаковки объектов можно представить в виде га-мерного вектора а3 = (а|, а4) Т" 3 = с целочисленными неотрицательными компонентами, для которого выполнено ограничение lial — Данный вектор a3, j = 1 называется вектором упаковки, а? гколичество г-ых предметов, входящих в j-ый вектор упаковки, Me — число всевозможных векторов упаковки.

Целое xj есть число объектов, которые должны быть упакованы в соответствии с вектором а3. Тогда соответствующая модель линейного целочисленного программирования будет иметь вид.

МЕ.

Z*(?) = VV-min, AEx = b, х €. (18) X j=i.

Столбцами матрица Ае G %тхМЕ являются всевозможные векторы упаковки а3. Нижней границей оптимального значения задачи (18) является решение задачи непрерывной релаксации.

Мв.

ZS (E) = min, Aex = 6, же R+E. (19) j X.

3=1.

Говорят, что задача E обладает свойством целочисленного округления {IRUP, integer round-up property), если Z*(E) — [ZS (E)~] = 0.

А. Маркотте, И. Терно и другие ученые в своих исследованиях показали, что большинство задач одномерной упаковки обладает этим свойствомболее того, пока не найдено ни одного примера, где бы Z*(E) — ZS{E)~ > 2. Поэтому имеет смысл рассматривать ZS (E) как нижнюю границу задачи (19).

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

Внесем в задачу (19) дополнительное ограничение, запрещающее использовать некоторый вектор упаковки а1, и решим новую задачу с ограничением мв.

Zts (E) = У]xj^тт, Ах = 6, ж" = 0, хеШ+Е. (20).

Я/.

Если Zts (E) > ZS (E)~, то исходная задача обладает свойством целочисленного округления только при условии, что данный вектор а1 входит в оптимальное решение. Обозначим редуцированную задачу как Е£ = (Дга, 1, Ь — а£).

Теорема 8 Если для некоторой задачи Е существует? (0 <? < Ме) при котором &а{ЕУ > гз (ЕУ и [гз (Е)] < 1 + [то £*(.Е) -> 1.

На основе на теоремы 8 в работе представлен полиномиальный алгоритм уточнения нижней границы для произвольной задачи одномерной упаковки. Для тестирования алгоритма были взяты примеры из банка трудных задач www.math.tu-dresden.de/capad (Дрезденский-технический университет) и www.apdio.pt/sicup. В более чем половине случаев удалось показать, что данные примеры не обладают свойством целочисленного округления, что позволило получить их оптимальное решение.

Для нахождения оптимального решения задачи одномерной упаковки в диссертационной работе представлен алгоритм, который является модификацией метода ветвей и границ, разработанного И. В. Романовским и Б. А. Кацевым. Представим решение задачи Е в виде матрицы Л = Ца1, а2, ., ап||, состоящей из векторов а-7, которые удовлетворяют условию а-? = Алгоритм базируется на последовательном просмотре всех допустимых вариантов и выборе из них оптимального. Для организации перебора предлагается использовать лексикографическое упорядочивание матриц А.

В работе предложены новые отсечения, основанные на свойстве доминантности. Задача Е доминирует над Е2, если каждому предмету из Е длины 7 можно сопоставить предмет из Е2 с длиной непревосходящей 7. Доказано, что если задача ?4. доминирует над Е2, то Z*(El) < Z*(E2)•.

В работе оценена мощность множества допустимых решений, которая совпадает с максимально возможным числом шагов соответствующего комбинаторного алгоритма. Без потери общности считаем, что для некоторой задачи Е все Ьг = 1. Пусть п — оптимальное решение задачи Е и <9(т, п) -максимально возможное число матриц решений размера тхп. Используя «Гамма-функцию Эйлера» исходя из классического правила Г (п+1) = п!, п = 0,1,2,. получена оценка.

Лемма 3 а (^ т! / Iр/ ^ Г (т+1).

5(&trade-'П) 5 (И)-'.((* + 1)!)'."! — К{т'п) := Г" (? + 1) Г (п + 1)' где к = [т/п] - целая часть дроби, г — остаток от деления т на п (О < г < п).

В работе показано, что оценка из леммы 3 достижима. Для выяснения зависимости т/п (т, фиксированное число) при котором функция Б (т, п) достигает максимума, введем функцию ф, ч т тgm&-xn (F (m, n)), которую можно трактовать как число предметов в векторе упаковки. Теорема 9 Функция Ф (т) при т —> со имеет асимптотику.

Ф (т) ~ (31пт, где /3 некоторая константа. Для т < 1000 график Ф (т) был построен поточечно (рис. 4). Его вид согласуется с теоремой 9. Значение константы /3 = 0,932.

Полученный результат согласуется с данными П. Шверина и Дж. Ваше-ра, которые в 1998 г. экспериментально выделили классы, трудные для комбинаторных алгоритмов для т из диапазона от 40 до 200 (на рис. 4 они выделены прямоугольником). Результаты теоремы 9 можно использовать.

Рисунок 4 — График Ф (т), полученный поточечно для формирования наиболее трудоемких тестовых задач, а также прогнозирования числа шагов переборного алгоритма.

Так как большинство задач одномерной упаковки обладает свойством целочисленного округления, для решения задач большой размерности принято формировать задачу остатка.

Пусть для некоторой задачи Е известно решение хс непрерывной задачи (19). Тогда Ё = (Ь, т,1,Ь — А [яс|) — задача остатка.

Теорема (И. Терно 1995). Если задача остатка Ё обладает свойством целочисленного округления, то и исходная задача Е обладает свойством целочисленного округления.

Таким образом, для нахождения оптимального решения задачи Е достаточно показать, что Ё обладает свойством целочисленного округления. Однако оказывается, что данным фактом не всегда можно воспользоваться: при росте числа т число шагов симплекс-алгоритма сильно возрастает, и при малых значениях 6 задача остатка по вычислительной сложности эквивалентна исходной задаче Ё «Е.

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

Из исходной задачи Е = (Ь, т, Ь, I) генерируем некоторую задачу.

Е9 = (Ьа, тд, 19), которая отвечает следующим условиям:

1. и = Ь.

2. Е доминирует над Е9.

3. т9 < т.

В диссертации представлено несколько линейных алгоритмов построения группировочной задачи. Приведена оценка их поведения в худшем случае. На основе идее группировки предложен метод построения начального решения для задачи непрерывной релаксации. (19). Теорема 10 Пусть для группировочной задачи Е9 известно некоторое допустимое базисное решение х^я? задачи непрерывной релаксации (19). Тогда ему сопоставляется вектор xf €, который является допустимым базисным решением задачи (19) с исходными данными Е. Получаемый таким способом вектор х^ используется в качестве начального решения для задачи Е. Проведенный численный эксперимент показал, что использование процедуры группировки снижает время нахождения непрерывного решения в среднем в два раза. Кроме того, в работе выделены случаи, при которых процедура группировки не дает улучшения.

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

Теорема 11 Если г*(Е9) — га{Е°)] = 0 и гз (Е)] = гз (Е9)}, то г*(Е9) =<�г*(Е).

Теорема 11 используется для построения задачи остатка Ё3, которая имеет меньшую размерность по сравнению с исходной задачей Е без потери оптимального решения. В работе приведен алгоритм построения задачи Е9, а также предложен обобщенный алгоритм нахождения оптимального решения для задачи одномерной упаковки.

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

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

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

Ортогональным многогранником (ОМ) называется фигура, состоящая из конечного числа неперекрывающихся И-мерных прямоугольных параллелепипедов, ребра которых параллельны осям координат и с фиксированным положением относительно друг друга. 1 1.

Рисунок 5 — Примеры ортогональных многогранников на плоскости.

Пусть даны т ортогональных многогранников 0= {О1, О2, ., Оту. Каждый ортогональный многогранник Ог е О задается набором из ./V-мерных ортогональных параллелепипедов. Обозначим его ¦., Щг) • Здесь с1г — число параллелепипедов, входящих в набор. Область, в которую размещаются ОМ, может быть различной, в зависимости от постановки задачи. Это может быть полубесконечная или ограниченная область.

Размещение ортогональных многогранников назовем рациональным, если оно является плотным и никакой ортогональный многогранник нельзя разместить в свободную область, расположенную «левее» его текущего расположения. Для рационального размещения ортогональных многогранников сопоставим каждому Огнабор из N функций, отвечающих мерам сечений по каждому координатному направлению xi, x2, — ¦, xn.

Kij (t) = mes{Otr{xj = t})1 j = 1, iV, i = l, m, t? Ш+.

Функции Kij (t) называются кортежами.

Данная модель позволяет легко реализовать поворот ортогональных многогранников на 90° и 180°. Так, для поворота Oi на 90° с j на ^ направление достаточно только поменять местами функции Кг31 с Кц2, а для поворота на 180° градусов по j оси достаточно только развернуть т. е. Kf]t) = - *), где t° = argmaxieE{i | (Ki3(t) > 0)}.

С помощью функций Kvj (t) также удобно задавать необходимое условие размещения ОМ. Для этого сопоставим произвольной упаковке Р набор из N функций Hj (t) = Kj{t — х}) + «•+ Kmj{t — х&trade-), имеющих смысл суммы мер сечений всех ОМ по j—му направлению. Необходимое условие допустимого размещения ОМ задает следующая.

Теорема 12 Если размещение ортогональных многогранник О в область S допустимо, то.

Hj (t).

На основе теоремы 12 предложено декомпозиционное представление области допустимого размещения ОМ. Каждому координатному направлению сопоставляются кусочно-линейные функции Hj. С их помощью определяются координаты возможного размещения ОМ. Допустимость предполагаемого размещения проверяется с помощью условия взаимного перекрытия параллелепипедов.

Предложенный метод определения свободных областей позволяет учитывать все пространство размещения, что дает возможность получать плотное размещение фигур сложных форм (например, спирали, фигуры с «дырками"и т.д.). В работе рассмотрено несколько подходов для формирования плотного размещения ОМ. Они основаны на методе случайной выборки, методе локального максимума и методе имитации отжига. Также была рассмотрена задача планирования в условиях массового производства упаковки ОМ.

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

В заключении сформулированы основные результаты диссертационной работы.

Основные результаты.

Результаты, полученные в данной работе, носят системный характер, поскольку, с одной стороны, они касаются общей теории дискретной оптимизации, а с другой стороны, они позволяют решать оптимизационные задачи f промышленности, связанные с упаковкой и размещением различных ортогональных объектов. Основные результаты:

1. Разработан метод построения декомпозиции оптимизационной задачи.

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

2. Предложено и обосновано матричное представление ортогональной упаковки. На основе этого представления, разработан метод нахождения оптимального решения задачи Ы-мерной ортогональной упаковки в полубесконечную полосу. Доказаны условия эквивалентности задач ортогональной упаковки.

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

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

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

6. Дано декомпозиционное представление задачи упаковки 1Ч-мерных ортогональных многогранников сложной формы. Предложены оптимизационные алгоритмы, направленные на решение ряда практических задач промышленности, связанных с ортогональной упаковкой.

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

Основные результаты диссертации полностью опубликованы в следующих работах из перечня ВАК [69, 63, 70, 71, 72, 73, 74, 75, 76, 77].

Основные результаты и выводы.

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

1. Предложен унифицированный метод мерной декомпозиции, позволяющий строить линейную релаксацию многомерной задачи ортогональной упаковки в замкнутую область. Его отличительной особенностью является комбинирование свойств сечений различных мерностей. Полученная линейная релаксация исходной задачи представима в виде набора задач линейного программирования с неявной матрицей ограничений, которые разрешимы методом генерации столбцов. Проверено, что она обладает наиболее сильными релаксационными свойствами по сравнению с ранее известными моделями, это позволило построить критерии оценки эффективности решения оптимизационных задач ортогональной упаковки. Доказаны достаточные условия улучшения этих оценок. Разработан псевдополиномиальный алгоритм численного получения оценок для произвольной задачи ортогональной упаковки.

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

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

4. Модифицирован метод консервативного масштабирования для построения за полиномиальное время оценки значения оптимального решения 1Г-мерной задачи ортогональной упаковки. Предложено понятие максимальной произвольной зависимой от данных двойственно-допустимой функции (МЗДДФ). Доказаны необходимые и достаточные условия максимальности произвольной зависимой от данных двойственно-допустимой функции. Показано, что известные ранее функции ЗДДФ не на всех наборах данных являются максимальными. Разработаны полиномиальные алгоритмы максимизации произвольной ЗДДФ. Установлено в ходе вычислительного эксперимента, что применение МЗДДФ вместо ЗДДФ существенно повышает точность получаемой оценки.

5. Проведен анализ структуры линейной релаксации задачи одномерной упаковки. Установлены достаточные условия, при выполнении которых задача не обладает свойством целочисленного округления. Сформулированы новые критерии оптимальности. Получены оптимальные решения для ряда трудных задач одномерной упаковки. Оценена вычислительная задача одномерной упаковки. Выделены наиболее трудные с точки зрения перебора классы задач, что позволяет прогнозировать время работы алгоритмов и генерировать особо трудоемкие тестовые задачи. Предложен критерий выбора метода для решения задачи одномерной упаковки. Разработан метод группировки, который преобразовывает исходную задачу в задачу меньшей размерности. Установлены достаточные условия, при которых сохраняется оптимальное решение, что позволило существенно повысить размерность задач, которые могут быть решены оптимально.

6. Разработано новое декомпозиционное представление задачи упаковки 1Ч-мерных ортогональных многогранников сложной формы. Выделены и доказаны необходимые условия существования их плотного размещения. Предложен оптимизационный эвристический алгоритм для решения этой задачи в различных практических постановках.

7. Разработано специализированное программное обеспечение для оптимизации систем на базе ортогональной упаковки, реализующее предложенные в диссертации алгоритмы. Данное программное обеспечение позволяет решать широкий класс оптимизационных задач, связанных с раскроем-упаковкой в различных постановках (задача одномерного раскроязадача ]М-мерной ортогональной упаковки в полосузадача размещения ]Ч-мерных ортогональных многогранников сложной формы). Проведен вычислительный эксперимент, подтвердивший эффективность разработанных методов на известных из литературы сериях тестовых примеров и примерах из ОК-библиотеки. Для многих из этих примеров удалось получить оптимальные решения.

5.4 Заключение и выводы.

1. Обобщено введенное ранее понятие «гофр» — в поставленной задаче планирования упаковок в качестве заготовок рассмотрены Лг-мерные ортогональные многогранники (ОМ) (ТУ-мерность задачи).

2. Разработана математическая модель задачи упаковки ./У-мерных ОМ внутри А^-мерных прямоугольных объектов: поставленная проблема описана непрерывной моделью линейного программирования.

3. Введено понятие «кортежа» и предложено представление каждого ОМ в виде совокупности кортежей.

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

5. Предложено формирование последовательностей из ОМ для предварительной генерации подмножества допустимых упаковок.

6. Показано сведение задачи упаковки Л^-мерного ОМ в объект к решению задач размещения кортежей ОМ.

7. Разработан алгоритм случайной выборки для генерации допустимого способа упаковки, основанный на представлении ОМ в виде совокупности кортежей.

8. Алгоритм решения задачи планирования упаковок Nмерных ОМ базируется на симплекс-методе с предварительно сгенерированной матрицей ограничений — векторов упаковки, полученных алгоритмом случайной выборки.

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

Примеры упаковки ортогональных многоугольников.