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



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

КАРТАК Вадим Михайлович

МЕТОДЫ АНАЛИЗА И ОПТИМИЗАЦИИ К-МЕРНОЙ ОРТОГОНАЛЬНОЙ УПАКОВКИ НА БАЗЕ СЕЧЕНИЙ РАЗЛИЧНЫХ РАЗМЕРНОСТЕЙ

Специальность 05.13.01 «Системный анализ, управление и обработка информации (в промышленности)»

АВТОРЕФЕРАТ диссертации на соискание учёной степени доктора физико-математических наук

Уфа-2011

^ 4 МОП

4851533

Работа выполнена на кафедре вычислительной математики и кибернетики в ФГБОУ ВПО «Уфимский государственный авиационный технический университет».

Научный консультант: доктор технических наук, профессор

Мухалева Элита Александровна

Официальные оппоненты: доктор физико-математических наук, профессор

Колоколов Александр Александрович; Омский филиал института математики им. С.Л. Соболева СО РАН

доктор физико-математических наук, профессор Пашоков Анатолий Васильевич; ГОУ ВПО Южно-Уральский государственный университет

доктор физико-математических наук, профессор Газизов Рафаил Кавыевич. ФГБОУ ВПО Уфимский государственный авиационный технический университет

Ведущая организация: Институт математики и механики

Уральского отделения Российской Академии наук

Защита состоится 16 сентября 2011 г. в ¡0°" час. на заседании диссертационного совета № Д-212.288.06 при ФГБОУ ВПО Уфимском государственном' авиационном техническом университете по адресу: 450000, г. Уфа, К. Маркса, 12.

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

Автореферат разослан «_»_2011 г.

Ученый секретарь диссертационного совета, профессор, доктор физ.-мат. наук

Булгакова Г. Т.

ОБЩАЯ ХАРАКТЕРИСТИКА ДИССЕРТАЦИИ

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

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

Фундаментальные научные результаты в решении данных задач принадлежат Л. В. Канторовичу, В. А. Залгаллеру, П. Гилмори и Р. Гомори. Результаты дальнейших исследований отражены в работах В. А. Булавско-го, М. А. Яковлевой, Ю. Г. Стояна, Э. А. Мухачевой, И. В. Романовского, В. А. Кузнецова, X. Дукхоффа, С. Мартелло, И. Терно, Г. Шайтхауэра и др.

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

В настоящее время разработан ряд эффективных приближенных и эвристических методов решения задач упаковки. Среди них выделяются кон-

структивные методы, методы локального поиска оптимума, генетические алгоритмы и т.д. Эти подходы исследовались в трудах И. П. Норенкова, Ю. А. Кочетова, Э. А. Мухачевой, А. А. Колоколова, А. Ф. Валеевой, А. А. Петунина, М. Дориго, Э. Фолкенауэра и др. Однако наличие этих методов не снимает проблему получения оптимального решения. Даже в тех случаях, когда построенное решение оптимально, доказательство данного факта представляет собой отдельную NP-трудную задачу.

Кроме того, довольно сложно оценить, насколько хорошо тот или другой приближенный алгоритм решает исходную задачу. В настоящее время известно всего несколько точных методов решения задачи ортогональной упаковки. Чаше всего они сводятся к перебору всего множества допустимых решений и нахождению среди них оптимального. Их различия заключаются в способах представления (кодирования) решений и схемах организации перебора. Точный метод решения этой задачи был разработан А. И. Липовецким. Он ввел понятие «зоны»и показал, что поиск оптимального решения сводится к последовательному перебору «зон». В дальнейшем этот подход был развит в работах Г. Шайтхауера, С. Мартелло, Д. Виго и др. С. Фекете и Ж. Ше-перс для нахождения допустимой упаковки в замкнутую область предложили метод, основанный на интервальных графах. Он позволяет избежать повторного просмотра симметричных случаев. С. Клаутио в своих трудах исследует растровую модель задачи ортогональной упаковки, которая представляется в виде задачи линейного целочисленного программирования с псевдополиномиальным числом переменных. Для ее решения он использует метод программирования ограничений (constrain programming). Асимптотически точные методы решения задачи одномерной и двумерной упаковки исследовались в трудах Э. X. Гимади, В. В. Залюбовского и других авторов.

Размерность задач, для которых удается гарантированно получать оптимальные решения, пока невелика (в двухмерном случае не превосходит 20). Одной из причин, по которой точные методы не обладают достаточной эффективностью, является трудоемкость доказательства оптимальности решения. Это связано с тем, что зачастую не удается точно оценить значение оптимального решения. Данную оценку принято называть «нижней границей». Её значение очень важно для сокращения перебора в точных методах, а так-

же для построения качественной оценки приближенных решений. Для задачи одномерной упаковки О. Маркотте показал, что нижняя граница, полученная в результате решения задачи линейной релаксации, достигается на большинстве задач. Это позволило разработать алгоритмы, эффективно находящие оптимальное решения, для задач с большим числом предметов (>500). Однако в случаях, когда эта нижняя граница не достигается, становится актуальной проблема ее уточнения. С. Мартелло и П. Тод в своих работах исследуют нижние границы, основанные на геометрических характеристиках рассматриваемых объектов (длина, площадь, объем и т.д.). С. Фекете и Ж. Шеперс предложили другой подход получения нижних границ. Он основан на свойствах консервативного масштабирования и позволяет получать более точные значения нижней границы. Ж. Карлье для построения консервативного масштабирования применил зависимые от данных двойственно-допустимые функции (ЗДДФ). Вместе с тем используемые им ЗДДФ могут доминиро-ваться другими функциями, таким образом получаемая нижняя граница может быть улучшена путем максимизации ЗДДФ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты диссертации докладывались на Байкальских школах-семинарах «Методы оптимизации и их приложения» (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 наименований.

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

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

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

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

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

нальных параллелепипедов И = {11;}, j € J = {1, ... ,т}, заданных своими размерами И., ~ (г{, ... € и контейнер 5 = (5Ь¿2,• • ■,£ ®ч, являющийся также ЛГ-мерным ортогональным параллелепипедом. Требуется выяснить, можно ли все предметы из Е1 упаковать в 3 без перекрытия? Поворот предметов запрещен.

Положение параллелепипедов II в 5 задается набором Р = {Рх,..., Рт} их «левых нижних» координат, которые являются векторами Р^ = (р[,... $ € 7. Допустимость векторов определяется неравенствами

р1>0, к & I — {1, ... Щ, (1)

для любых £ 7, ]\ ^ j2, найдется к £ I, для которого

или 2)

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

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

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

Выберем подмножество б £ /д и определим подпространство Х° — (еЛ, ед2, ..., еЛ), являющееся линейной оболочкой базисных векторов с номерами из б = {31, ..., и дополнительное к нему подпространство Лс. Очевидно, что Xе ф Ха = К^. Рассмотрим семейство ¿—мерных плоскостей, параллельных подпространству Лс. Положение каждой плоскости однозначно определяется выбором точки Л с соответствующим радиус-вектором

Ь е Х°. Обозначим плоскость данного семейства как А^ = Ь + Ха.

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

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

л (3)

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

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

: = У°6й?в|, (4)

1 ¿=1 дев )

где Ь3 £ Ит с элементами Щ = П5есг|> 3 6 Множества У° являются декомпозицией исходной задачи по различным наборам координатных направлений.

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

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

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

Возьмем пару параллелепипедов из R с номерами р и q и обозначим через ¿G(P><?) : а% — a?q = 1) ci? £ AG} множество номеров определяющих

векторов, для которых afv — afq — 1.

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

: yG € YG, yf = 0, г 6 ¿G(p, ?)}. (5)

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

Лемма 1. Пусть р, q и G таковы, что = 0- Тогда для любого допустимого размещения параллелепипедов R в контейнер S существует точка h 6 \G, для которой плоскость \ft пересекает р-й и q-й параллелепипед.

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

Теорема 2. Если существуют номера р и q и набор Е = {Gav G<j2, ..., Gat}, для которых выполняется Ц.е£С?а = I и У^ = 0 для всех G € Е, то параллелепипеды R нельзя разместить в области S.

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

Множества У^ также использованы для нахождения устойчивых сочетаний и сокращения числа неравенств в системе (1)-(2). Для этой цели строятся два множества

e+ = {(p,g): 3G, г е G, = , (6)

еГ = {(Р.9): (Р.?) 6 V? €//*}. (7)

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

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

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

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

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

Пусть даны константы С, С' > 0 и 0 < Ci < С, V г € V. Функция / {сь... .Сщ, С} [О, С"] называется ЗДДФ, если для любого V"i С V, из условия £ieV, ci ^ с следует ]TieVi f(a) < f(C) = С'.

Он показал, что при существовании набора ЗДДФ Д, к — 1, N с условием Y^ievTikMri) > Hkfk(Sk) задача ^R, S^ имеет отрицательный ответ.

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

f(a) . ha) , с т/ /Ы ^ /Ы

-гг~ < —-, и при этом существует г € к с условием .. ■ < -.

}{С) -/(С)' /(<?) /(С)

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

{mm Л

TpiXi : ,

где а € К™ - веса предметов и /3 £ R™ - их стоимость, а С - размер рюкзака.

Теорема 3. Яустъ а = (ci, ... ,Ст) и j.3 = (/(ci), ... J{cm)). Функция f максимальна тогда и только тогда, когда

f(C) = KP(C,a,P), (8)

/(с*) = К-Р(С, а, /3) — КР (С — ci,a\ci,f3\ f(ci)), Vi € У. (9)

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

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

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

Полубесконечной полосой Б, заданной своими размерами (£1, £2, ..., 5^-1) £ К+-1, называется множество точек х £ К", х = (XI, Х2, ■ ■ ■, хц) таких, что 0 < Хк < Бк, к = 1, 1 и

0 < хц.

Пусть для некоторого натурального числа N > 2 и полубесконечной полосы 5 с размерами («51, ..., 5дт_1) £ известен набор из то параллелепипедов И == {И^}, У € 7 = {1, . - • ,тп}. Каждый из них задан своими размерами а,- = (г), £ Считаем, что 0 < г( < € к = 1, ..., N - 1.

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

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

р1> о, + jeJ, к = {1,...,м~1]. (10)

Для любых £ ./, ф 72, найдется к £ /, для которого

или р? + т?<р£. 11

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

j=l,m

Требуется найти такой РёК, для которого

е(К,5) = шп(?(Р). (12)

Набор Р* £ 9? назовем оптимальным, если #(Р*) = 6(11, 5"). В работе предложена процедура факторизации множества Я, которая базируется на идее плотного размещения параллелепипедов. Набор Р £ 3? называется плотным, если выполняются следующее условия

V; е 7, й € / : (г^ = о) V (э 1 < 4 < т, « ^ *: =р£ + г!) (13)

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

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

Пусть для задачи (К,,!?} известно некоторое допустимое решение Р. Для каждого к Е I рассмотрим множество координатных направлений, задающих гиперплоскости вк = /дг \ к и дополнение к нему Ск — к, Выберем т + 1 точку на /с—той координатной оси следующим образом: /го = 0,

= тщ(р£ + г°к : р^ + > /г,_!, ] £ .7), г = 1, т. Проведем гиперплоскости

и сконструируем матрицу Ак е (0,1}тхт с определяющими векторами а°к(Р,Ь.\) в качестве столбцов.

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

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

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

Рис. 1: Пример расположения гиперплоскостей для N = 2. Получаемые при этом матрицы упаковки имеют вид

Л1

/ 1 0 0 0 0 0 \ 1 1 0 0 0 0 0 11110 0 0 1 0 0 0 0 0 0 1 0 0 \ 0 0 О О 1 1 /

/ 0 О 1 1 1 1 \

1 1 0 0 0 0

0 0 0 0 1 0

11110 0

1110 0 0

\ 1 О О О О О)

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

Условие 1. Продолж.енностъ единиц. Для каждой строки э £ 3 матрицы Л1", к = найдутся столбцы 12ъ и Ре, для которых

4 =

1, если ^ ^ г < г^, 0, в противном случае.

Условие 2. Завершенность. В каждом столбце матриц Ак, к — заканчивается, по крайней мере, одна из последовательностей единиц

V? е 3, Зг0 е 3

= 1 и а,, = 0 для г

(¿0+1),

Условие 3. Связь между элементами векторов Zk и матриц Ак, к = 1, /V с размерами параллелепипедов й. устанавливается соотношением

т

» = (15)

¿=1

Условие 4. Неперекрытие параллелепипедов. Для любой пары, параллелепипедов 1 < р < 5 < т существует координатное направление к* & I такое, что

4,Ч<<2, г = (16)

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

Теорема 4. Пусть для задачи (Л, Б) известен набор Р £ 3?. Тогда ему однозначно сопоставляются матрицы Ак и вектора Zk, к = удовлетворяющие условиям 1-4. Обратное, если заданы матрицы Ак и вектора Zk, к = удовлетворяющие условиям 1~4, то им однозначно сопоставляется Р, для которого

т г= 1

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

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

Нижней границей задачи (И, 5) называется функция, зависящая от входных параметров задачи Ьь(И, 5) > 0, такая, что ¿¿(И, 5) < 9(11,5).

Величина £¿(11, £>) играет большую роль при доказательстве оптимальности заданного набора координат Р. Так если £¿(11, 5) = б(Р), то Р - оп-

тимум. В этом случае можно доказать оптимальность решения без полного перебора. В работе предлагаются следующие способы вычисления ¿¿(R, S).

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

С\R, S) = Y min, Асу = b°\ / е ßf \ (17) м у

где А°к - матрица всех возможных определяющих векторов для множества направлений Gk.

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

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

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

. Ck{R,S) < Sk, k = l,N-l и Cn(R,S) < Lb( R, S);

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

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

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

S{ = Si, i = 1, N — 1 и Sn = Lb(R, S). В этом случае получаем задачу ортогональной упаковки в замкнутую область ^R, S^, которая была рассмотрена в первой главе. Если удастся доказать, что эта задача не имеет решения, то Lb(R, S) < 6(R, S) и значение L{,(R., S) увеличивается.

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

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

P<(r\ Si) := {а : <Sk, а 6 {0,1}т}, к =Tj7,

где тъ = (г\, ... , Будем говорить, что задачи ортогональной упаковки ^R, S^ и ^R, S^ эквивалентны, если

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

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

K{rk, r\ Sk) <Sk и K(rk, r\ Sk) < Sk, k — l^N.

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

выбрать наиболее удачную (в вычислительном плане) постановку задачи среди класса эквивалентных.

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

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

Теорема 7. Если для известные матрицы упаковки Ак и Ак отли-

чаются от другой только транспозицией столбцов, то^™=1 =

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

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

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

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

Классическая задача одномерной упаковки состоит в следующем. Дан набор одномерных объектов длины L. В них необходимо упаковать предметы длин I = (ii, h, ■ ■ ■ lm) в требуемых количествах b = (bi, Ьг» - - - Ьт), где т - число типов предметов. Цель - минимизация количества использованных объектов. Входные данные задачи обозначим Е = (L, т, I, Ь).

В литературе данная задача известна как задача линейного раскроя. Она формулируется в виде задачи линейного целочисленного программирования. Наиболее удачная модель была предложена JI. В. Канторовичем, В. А. Залгаллером и, независимо, Р. Гомори и П. Гилмори: каждый допустимый способ упаковки объектов можно представить в виде m-мерного вектора = (aj, ..., а3т)Т, j = 1,... ,Ме с целочисленными неотрицательными компонентами, для которого выполнено ограничение XX iai — Данный вектор a?, j = 1, •.., Me, называется вектором упаковки, а{- количество г-ых предметов, входящих в j-ьгй вектор упаковки, Me - число всевозможных векторов упаковки.

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

ме

Z*(E) = Xj —> min, АЕх = Ь, xeZ+E. (18)

3=1

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

ме

Zt(E) = y*Xj->mm, AEx = b, z е М+Е. (19)

4—' х

j=i

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

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

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

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

Мв

гЦЕ) = Я,- пип, Ах = Ь, хг = 0, хе 'Е. (20)

3=1

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

Теорема 8. Если для некоторой задачи Е существует t (0 < t < Ме) при котором \%{Е)] > \гг{Е)} и \гв{Е)} < 1 + ГДД-Е1)], то г*{Е) -

Гг,(Щ > 1.

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

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

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

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

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

Лемма 3.

сt \ г- m! ^ T?I \ Г(т +1)

5(т'П) < (ifc!)-. + - КП) " Г"(--М)Г(п + 1)'

где к = [m/n] - целая часть дроби, г остаток от деления т на п (О < г < п).

В работе показано, что оценка из леммы 3 достижима. Для выяснения зависимости гп/п (яг фиксированное число) при котором функция S(m, п) достигает максимума, введем функцию

ащтах„(Р(т, п))' которую можно трактовать как число предметов в векторе упаковки.

Теорема 9. Функция Ф(яг) при тп -ь оо имеет асим,птотику Ф(тп) ~ Р1пт, где /3 некоторая константа.

Рис. 2: График Ф[т), полученный поточечно

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

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

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

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

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

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

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

Из исходной задачи, Е = (Ь, т, Ь, I) генерируем некоторую задачу Е9 = Ъд, Iя), которая отвечает следующим условиям:

1. V = Ь.

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

3. т? < т.

4. ХХЛ = ЕГ=^-

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

основе идее группировки предложен метод построения начального решения для задачи непрерывной релаксации (19).

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

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

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

Теорема 11. Если г*(Ее) - \ге(Е9)] = 0 и \гз(Е) 1 = то

г*{Е9) = г*{Е).

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

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

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

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

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

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

Пусть даны т ортогональных многогранников О— {01; О2, ..., От}. Каждый ортогональный многогранник Oi 6 О задается набором из N-мерных ортогональных параллелепипедов. Обозначим его Ri = [R\, Щ, ..., R^,). ,Здесь d; - число параллелепипедов, входящих в набор. Область, в которую размещаются ОМ, может быть различной, в зависимости от постановки задачи. Это может быть полубесконечная или ограниченная область.

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

Kij(t) = mes (О; П {xj = i}), j = ljf, i = 17m, t € M+.

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

Данная модель позволяет легко реализовать поворот ортогональных многогранников на 90° и 180°. Так, для поворота Oi на 90° с j\ на ¡2 направление достаточно только поменять местами функции К^ с Kij2, а для поворота на 180° градусов по ji оси достаточно только развернуть К^ т.е. Km°{t) = Km°{to _ t)) где to = argmaXt6R{i I (Kij(t) > 0)}.

С помощью функций также удобно задавать необходимое условие

размещения ОМ. Для этого сопоставим произвольной упаковкеР набор из N

функций #;(£) = Кц— я]) Н-----1-- ж™), имеющих смысл суммы мер

сечений всех ОМ по j—мy направлению. Необходимое условие допустимого размещения ОМ задает следующая

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

ЗеЛз

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

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

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

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

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

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

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

1. Разработан метод построения декомпозиции оптимизационной задачи 1Ч-мерной ортогональной упаковки. На его базе построена линейная релаксация множества решений и получена оценка оптимального значения целевой функции снизу. Установлены условия уточнения этой оценки. [2,9,11]

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

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

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

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

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

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

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

Основные результаты диссертации полностью опубликованы в следующих работах

Публикации в рецензируемых журналах из перечня ВАК-

1. Мухачева Э.А., Картак В.М. Модифицированный метод ветвей и границ: алгоритм и численный эксперимент для задачи одномерного раскроя // Информационные технологии. - 2000. - №9. - С. 15-21.

2. Мухачева Э.А., Картак В.М., Мухачева A.C., Валеева А.Ф. Модели и методы решения задач ортогонального раскроя и упаковки: аналитический обзор и новая технология блочных структур // Информационные технологии. - 2004. - №5. - С.2-17.

3. Картак В.М. Достаточные условия невыполнения свойства целочисленного округления длй задачи линейного раскроя // Автоматика и телемеханика. - 2004. - №4. - С. 55-62.

4. Картак В.М. Использование метода группировки для решения задачи линейного раскроя. // Вестник ВашГУ. - 2005. - №3. - С.9-13.

5. Картак В.М. Задача упаковки прямоугольников: точный алгоритм на базе матричного представления // Вестник УГАТУ: научн. журн. Уфимск. гос. авиац. техн. ун-та. Серия «Управление, вычислительная техника и информатика». - 2007. - Т.9, №4(22). - С. 104-110.

6. Картак В.М. Матричный алгоритм поиска оптимального решения для задачи упаковки прямоугольников в полубесконечную полосу // Информационные технологии. - 2008. - №1. - С. 36-44.

7. Картак В.М. Обновленная нижняя граница для задачи упаковки прямоугольников в полубесконечную полосу // Вестник УГАТУ: научн. журн. Уфимск. гос. авиац. техн. уп-та. Серия «Управление, вычислительная техника и информатика». - 2008. - Т. 10, №2(27). - С. 154-158.

8. Картак В.М., Васильева Л.И., Мухачева Э.А., Петунин A.A. Задача размещения прямоугольно-ориентированных многоугольников: модели и алгоритм покоординатной упаковки // Информационные технологии. - 2008. - №3. - С.46-54.

9. Картак В.М., Месягутов М.А., Мухачева Э.А., Филиппова A.C. Локальный поиск ортогональных упаковок с использованием нижних границ // Автоматика и телемеханика. - 2009. - №6. - С. 167-180.

10. Картак В.М. Метод группировки для решения непрерывной задачи линейного раскроя // Дискретный анализ и исследование операций. -2009. - Т.З, №16. - С. 47-62.

В работах, опубликованных в соавторстве, диссертантом были получены следующие результаты: обоснование метода мерной декомпозиции [2]; разработка точного метода [5]; описание точных методов и способов получения оценок [6]; разработка декомпозиционного представления ОМ, процедура их упаковки [10].

Рецензируемые зарубежные журналы

11. Мухачева Э.А., Белов Г.Н., Картак В.М., Мухачева A.C. Одномерная проблема раскроя-упаковки: вычислительный эксперимент мето-

да уточнения оценок и модифицированного метода ветвей и границ // Pesquisa Operacional. - 2000. - V. 2, №20. - Pp. 153-168. (статья на англ.)

12. Г. Белов, В. Картак, X. Роллинг, Г. Шайтхауер. Одномерная релаксация и LP граница для ортогональной упаковки. // International Transactions on Operational Research. - 2009. - №16. - Pp. 745-766. (статья на англ.)

Монография:

13. Мухачева A.C., Картак В.М., Валеева А.Ф. Задачи двумерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума. // МИздательство МАИ. - 2004. - 193 С.

Другие основные публикации:

14. Картак В.М. Комбинаторные методы для получения оптимального целочисленного решения в задачах одномерного раскроя // Принятие решений в условиях неопределенности. - Уфа, 1996. - С. 53-58.

15. Картак В.М. Комбинаторный алгоритм для решения линейной упаковки // Принятие решений в условиях неопределенности. - Уфа, 1997. -С. 30-36.

16. Мухачева Э.А., Картак В.М. Интеграционный подход к решению задачи линейного раскроя // Вычислительная техника и новые информационные технологии. Межвузовский научный сборник. Выпуск третий. -Уфа, 1999. -С. 55-64.

17. Картак В.М., Васильева Л.И. Двумерная упаковка гофров на листах в условиях непрерывного производства // Моделирование, вычисления, проектирование в условиях неопределенности. / Материалы научной конференции. - Уфа, УГАТУ, 2000. -С. 403-407.

18. Мухачева Э.А., Картак В.М., Васильева Л.И. Задача планирования п-мерных упаковок гофров // Распределительные системы: оптимизация и приложения в экономике и науках об окружающей среде. Материалы Международной конференции. - Екатеринбург, ИММ УрО РАН, 2000. - С. 152-156.

19. Картак В.М., Васильева Л.И. Задача двумерной упаковки гофров // Принятие решений в условиях неопределенности. Межвузовский научный сборник. - Уфа, 2000, -С. 108-112.

Картак В.М. Алгоритм проверки свойства IR.UP для задачи линейного раскроя // Алгебра и линейная оптимизация: Труды международного семинара, посвященного 90-летию со дня рождения С.Н.Черникова. -Екатеринбург, ИММ УрО РАН, 2001. - С. 271-276.

Картак В.М. Оптимальная упаковка N-мерных параллелепипедов в полубесконечную область // 12-я Байкальская международная конференция: Методы оптимизации и их приложения. Прикладные задачи оптимизации и динамики. - Иркутск, 2001. - С. 19-22.

22. Картак В.М. Алгоритм проверки невыполнения свойства целочисленного округления для задачи линейного раскроя // Сборник трудов третьей региональной школы-конференции для студентов, аспирантов и молодых ученых по математике и физике. - Уфа, БашГУ, 2003. - С. 88-100.

23. Картак В.М., Картак В.В. Использование метода группировки для точного решения задачи линейного раскроя // Принятие решений в условиях неопределенности. Вып. 2. - Уфа, УГАТУ, 2005. - С. 123-128.

24. Картак В.М. Точный алгоритм для решения задачи одномерного раскроя //Сборник статей 2-й региональной зимней школы-семинара аспирантов и молодых ученых. - Уфа: Издательство «Технология», 2007. - С. 44-50.

25. Картак В.М., Месягутов М.А., Валеев P.C. Нижняя граница для задачи упаковки в полосу: линейная и ld продолженная релаксация// Preprints of the 13th IFAC Symposium on Information Control Problems in Manufacturing - Moscow, Russia: 2009. - June 3-5/ - Pp. 2003-2007. (статья на англ.)

20.

21.

КАРТАК Вадим Михайлович

МЕТОДЫ АНАЛИЗА И ОПТИМИЗАЦИИ ^МЕРНОЙ ОРТОГОНАЛЬНОЙ УПАКОВКИ НА БАЗЕ СЕЧЕНИЙ РАЗЛИЧНЫХ РАЗМЕРНОСТЕЙ

Специальность 05.13.01 «Системный анализ, управление и обработка информации (в промышленности)»

АВТОРЕФЕРАТ диссертации на соискание учёной степени доктора физико-математических наук

Подписан к печати 20.06.2011. Формат 60 х 84 1/16. Печать плоская. Бумага офисная. Усл.печ.л. 1,75. Уч.-изд.л. 1,5 Тираж 100 экз. Заказ № 204

ФГБОУ ВПО Уфимский государственный авиационный технический университет Центр оперативной полиграфии 450000, Уфа - центр, ул. К.Маркса, 12

Введение.

ГЛАВА 1. Метод мерной декомпозиции

1.1 Введение

1.2 Задача существования.

1.2.1 Достаточное условие решения задачи существования

1.2.2 Пространство Мп

1.3 Задача упаковки АГ-мерного ортогонального рюкзака без весов

1.3.1 Постановка задачи.

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

1.4 Метод секущих плоскостей.

1.4.1 Координатные направления и подпространства.

1.4.2 Пересечение плоскости и параллелепипеда.

1.4.3 Меры сечений.

1.4.4 Определяющие вектора.

1.4.5 Связь между определяющими векторами и упаковкой

1.4.6 Построение определяющих векторов.

1.4.7 Условие неперссечения параллелепипедов.

1.4.8 Минимальный вектор

1.4.9 Модифицированный минимальный вектор.

1.4.10 Алгоритм проверки существования решения задачи о загрузки ^-мерного рюкзака.

1.5 Максимизация зависимых от данных двойственно допустимых функций.

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

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], которая посвящена практическим ситуациям в организации производства, где могут быть полезными предложенные математические модели и возникающие при их анализе показатели.

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

В течение 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/ •//í»////////// '//////////// 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г. А.И. Липовецкий сформулировал задачу упаковки прямоугольников как проблему комбинаторной оптимизации и предложил „метод зон" для нахождения оптимального решения. На основе понятия "зоны" доказывается, что для любой упаковки прямоугольников можно указать такой их порядок, при котором каждый следующий прямоугольник не пересекается ни с одной из зон предыдущих (топологическая сортировка)[51]. Метод зон реализован в 1988 г., усовершенствован и исследован в 2001 г. В.В.Бухваловой (С.Петербург) [52].

В 1998 С. Мартелло и Д. Виго предложили контурную концепцию для поиска оптимального решения упаковки прямоугольников [53]. Идея этого подхода схожа с „методом зон". Они показали, что любую упаковку можно получить, располагая прямоугольники! на некотором ступенчатообразном контуре. После расположения очередного* прямоугольника этот контур модифицируется. Г. Шайтхауер предложил для сокращения числа вариантов, ряд отсечений, которые позволяют не рассматривать симметричные варианты [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]. В его работе была сделана попытка решать данную задачу с помощью линейного целочисленного программирования. Но в силу того, что непрерывная релаксация этой модели очень „слаба", удалось точно решать лишь задачи небольшой размерности т < 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<£max(s—1^+1,0) t€.ma,x(s—Wj +1,0) s £ - 1, . ,Sk- min{wf, Wj}}, Vi < j, V/e

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

Г*

Sk — min 1Ü-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,., с™, С} —> [О, С') называется ЗДДФ, если для любого V\ С V, из условия Y^ieVt ci<C следует J2ievi /(<=i) < fiC) = c'■

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

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

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

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

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

ТО 771

КР(С, а, /3) = тах < У^ /Згжг : аг • хг < С > , жб{одГ I где а £ К™ - веса предметов п /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 ,т. Проведем гиперплоскости Л^ и сконструируем матрицу Ак €Е {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 11110 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 11110 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 = , ук е <G*, 1 (17) i=i у где А°к - матрица всех возможных определяющих векторов для множества направлений Gk.

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

Из теоремы 4 и леммы 2 следует ©(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) <Sk,k = 1, JV-1 и CN(R, S) < Lb(R, S);

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

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

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

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

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

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

Р<(гкЛ) := {а : £а{гк <Як, а € {0,1}т}, к=Т^, где гк = (г\, . , г™). Будем говорить, что задачи ортогональной упаковки ^Н,, и эквивалентны, если р<(гкЛ) = Р<(гк, вк), к = 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(™'П) 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) = K\j{t — х}) + "•+ Kmj{t — х™), имеющих смысл суммы мер сечений всех ОМ по j—му направлению. Необходимое условие допустимого размещения ОМ задает следующая

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

Hj(t)<l[Sj, te R, j = TJf. jeJ\j

На основе теоремы 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. Разработанные алгоритмы программно реализованы. Проведены численные эксперименты, подтверждающие перспективность данного подхода. Сформулированы предложения по дальнейшей модификации и развитию этого подхода.

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

1. Канторович, JI. В. Математические методы организации и планирования производства / Л. В. Канторович. — Изд. ЛГУ, 1939. — С. 61.

2. Канторович, JI. В. Расчет рационального раскроя материалов / Л. В. Канторович, В. А. Заллгаллер.— Лениздат, 1951.

3. Gilmore, Р. С. A linear programming approach to the cutting-stock problem / P. C. Gilmore, R. E. Gomory // Operations Research. — 1961.— Vol. 9. Pp. 849-859.

4. Gilmore, P. C. Multistage cutting stock problem of two and more dimensions / P. C. Gilmore, R. E. Gomory // Operations Research. — 1965.— Vol. 13(1).-Pp. 94-120.

5. Романовский, И. В. Решение задачи гильотинного раскроя методом переработки списка состояний / И. В. Романовский // Кибернетика. — 1969. — № 1.-С. 102-104.

6. Вулавский, В. А. О решении задач оптимального раскроя линейных материалов на эвм / В. А. Вулавский, М. А. Яковлева // Математические методы в технико-экономических расчетах: Материалы научного совещания. Т. 4.- М.: АН СССР, 1961.- С. 83-87.

7. Мухачева, Э. А. Рациональный раскрой прямоугольных листов на прямоугольные заготовки / Э. А. Мухачева // Оптимальное планирование: Сб. научных трудов СО АН СССР. 1966. - Т. 6. - С. 43-115.

8. Мухачева, Э. А. Методы условной оптимизации в задаче рационального раскроя листового проката / Э. А. Мухачева // Оптимизация: Сб. науч. трудов СО АН СССР. 1978. - Т. 22. - С. 83-93.

9. Гер и, М. П. Вычислительные машины и трудноразрешимые задачи / М. П. Гери, Д. С. Джонсон. — М. Мир, 1982.

10. George, J. A method for solving container packing for a single size of box / J. George // Journal of the Operational Research Soviety.— 1992.— Vol. 43, no. 4. Pp. 307-312.

11. Мухачева, Э. А. Генетический алгоритм блочной структуры в задачах двухмерной упаковки / Э. А. Мухачева, А. С. Мухачева, А. В. Чиглин-цев // Информационные технологии. — 1999. — Т. 11. — С. 13-18.

12. Мухачева, А. С. Технология блочных структур локального поиска оптимума в задачах прямоугольной упаковки / А. С. Мухачева // Информационные технологии. Приложение.— 2004. — Т. 5. — С. 18-31.

13. Гимади, Э. X. Задача упаковки в контейнеры: асимптотически точный подход / Э. X. Гимади, 3. В. В. // Известия вузов. Математика. — 1997. № 12. - С. 25-33.

14. Гимади, Э. X. Задачи упаковки в полосу: асимптотически точный подход / Э. X. Гимади, В. В. Залюбовский, П. И. Шарыгин // Известия вузов. Математика. — 1997. — № 12. — С. 34-44.

15. Панюков, А. В. Алгоритм локальной оптимизации для задачи размещения прямоугольных объектов с минимальной длиной связывающей их сети / А. В. Панюков // Изв. АН СССР. Техн. кибернетика.— 1981.— № 6. С. 180-184.

16. Панюков, А. В. Алгоритмы размещения прямоугольных объектов / А. В. Панюков // Декомпозиция и координация в сложных системах: Материалы Всесоюз. конф. — Челябинск: ЧПИ, 1987. — С. 80-97.

17. Панюков, А. В. Задача размещения прямоугольных объектов с минимальной стоимостью связывающей сети / А. В. Панюков // Дискретн. анализ и исслед. опер., сер. 2.— 2001. — Т. 8, № 1.— С. 70-87.

18. Bykhoff, Н. Special issue: Cutting and packing / H. Dykhoff, G. Wäscher // European Journal of Operational Researa— 1990.— Vol. 44, no. 2.

19. Martello, S. Special issue: Knapsack, Packing and Cutting, Part I: One Dimensional Knapsack Problem. / S. Martello. — INFOR., 1994. — Vol. 32.

20. Special issue: Knapsack, Packing and Cutting, Part II: Multidimensional Knapsack and Cutting Stock Problems. — INFOR, 1994. — Vol. 32.

21. Lirov, Y. Special issue: Geometric Resource Allocation / Y. Lirov. — 1995. Vol. 16.

22. Bischojf, E. Special issue: Cutting and packing / E. Bischoff,

23. G. Wascher // European Journal of Operational Research — 1995. — Vol. 84, no. 1.

24. Mukhacheva; E. Special issue: Decasion making under conditions of uncertainty (cutting-packing problems) / E. Mukhacheva // The International Scientific Collection. — Ufa. Russia., 1997.

25. Yanasse, H. Special issue: Cutting and packing problems /

26. H. Yanasse // Pesqmsa Operacional.— 1999. — Vol. 19, no. 2.

27. Wang, P. Special issue: Cutting packing problems / P. Wang, G. Wascher // Europen Journal of Operational research.— 2002. — Vol. 141.

28. Dyckhoff, H. A typology of cutting and packing problems / H. Dyckhoff / / European Journal of Operational Research.— 1990. — January. — Vol. 44.— Pp. 145-159. http://ideas.repec.org/a/eee/ejores/v44yl990i2pl45-159.htrnl.

29. Пападемитриу, X. Комбинаторная оптимизация. Алгоритмы и сложность / X. Пападемитриу, К. Стайглец. — М.: Мир., 1985.

30. Байт, S. Integer rounding for polymatroid and branching optimization problems / S. Baum, J. Trotter // SIAM J. Alg. Disc. Meth.— 1981. — Vol. 2, no. 4. Pp. 416-425.

31. Marcotte, O. The cutting stock problem and integer rouding / O. Marcotte // Math.Program. — 1985. — Vol. 33, no. 1. — Pp. 82-92.

32. Diegel, A. Integer lp solution for large trim problems: Tech. rep. / A. Diegel: University of Natal. South Africa, 1988.

33. Scheithauer, G. Improving the formulation of the cutting stock problem. / G. Scheithauer, J. Terno // Presentation given at the International Symposium on Mathematical Programming. Lausanne. — 1997.

34. Solveng one-dimensional cutting stock problems exactly with a cutting plane algorithm / G. Scheithauer, J. Terno, A. Muller, G. Belov /J Journal of the Operational Research Society. — 2001. — Vol. 52. — Pp. 1390-1401.

35. Belov, G. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths / G. Belov, G. Scheithauer // European Journal of Operational Research, — 2002. — Vol. 141. — Pp. 274-294.

36. Holthaus, O. Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard of lengths / O. Holthaus // European Journal of Operational research— 2002.— Vol. 141.-Pp. 295-312.

37. Vance, P. Branch-and-price algorithms for the one-dimensional cutting stock problem / P. Vance // Computational optimization and Applications. — 1998. Vol. 9, no. 3. — Pp. 212-228.

38. Vanderbeck, F. Exact algorithm for minimizing the number of setups in the one-dimensional cutting stock problem: Tech. Rep. 10 / F. Vanderbeck: University of Cambridge, 1998.

39. Valerio de Carvalho, J. Lp models for bin packing and cutting stock problems / J. Valerio de Carvalho // European Journal of Operational research. 2002. - Vol. 141. - Pp. 253-273.

40. Романовский, И. В. Решение дискретных минимаксных задач методом дихотомии / И. В. Романовский, Н. П. Христова // ЖВМ и МФ.— 1973. Т. 13, № 5. - С. 1200-1209.

41. Кацев, С. Об одном классе дискретных минимаксных задач / С. Кацев // Кибернетика.— 1979.- Т. 5. — С. 139-141.

42. Романовский, И. В. Алгоритмы решения экстремальных задач / И. В. Романовский. — М.: Наука, 1977.

43. Scholl, A. Bison: A fast hybrid procedure for exactly solving the one-dimensional bin-packing problem / A. Scholl, R. Klein, J. G. // Computers and Operational Research. — 1997. — Vol. 24, no. 7. — Pp. 627-645.

44. Schwerin, P. The bin-packing problem: a problem generator and some numerical experiments with ffd packing and mtp / P. Schwerin, G. Wascher // International Transactions in Operational Research — 1997. — Vol. 4. — Pp. 337-389.

45. Еремеев, А. В. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования. / А. В. Еремеев, JI. А. Заозерская, А. А. Колоколов // Дискретный анализ и исследование операций. Сер. 2. 2000. - Т. 7, № 2. - С. 22-46.

46. Еремеев, А. В. Генетический алгоритм для задачи о покрытии / А. В. Еремеев // Дискретный анализ и исслед. операций. Сер. 2.— 2000. — Т. 7, № 1. С. 47-60.

47. Hinxman, A. The trim-loss and assortment problems: a survey / A. Hinxman // European Journal of Operational research. — 1980. — no. 11. — Pp. 863-888.

48. Мухачева, Э. А. Рациональный раскрой промышленных материалов. Применение в АСУ / Э. А. Мухачева. — М.: Машиностроение, 1984. — С. 176.

49. Terno, J. Zuschnitprobleme und ihre praktische Losung / J. Terno, R. Lindeman, G. Scheithauer. — Leipzig, 1987.

50. Лернер, Э. Ю. Функция гильотинного размещения для набора прямоугольников / Э. Ю. Лернер, В. Р. Фазылов // Исследования по прикладной математике. — 1999.— Т. 21.— С. 187-196.

51. Tarnowski, Т. A polynomial time algorithm for the guillotine pallet loading problem / T. Tarnowski, J. Terno, G. Scheithauer // INFOR. 1994. — no. 32. - Pp. 275-287.

52. Липовецкий, А. И. К оптимизации свободного размещения прямоугольников / А. И. Липовецкий // Автоматическое проектирование в машиностроении. Минск: НТК АН БССР, 1985. - С. 80-87.

53. Бухвалова, В. В. Задача прямоугольного раскроя: метод зон и другие алгоритмы / В. В. Бухвалова. — СПб.: СПбГУ, 2001.

54. Martello, S. Exact solution of the two-dimensional finite bin packing problem / S. Martello, D. Vigo // Management Science. — 1998. — no. 44. — Pp. 3-34.

55. Scheithauer, G. Equivalence and dominance for problems of optimal packing of rectangles / G. Scheithauer // Ricerca Operativa. — 1998. — no. 83. — Pp. 3-34.

56. Beasley, J. An exact two-dimensional non-guillotine cutting tree search procedure / J. Beasley // Operations Research. — 1985. — no. 33.— P. 49-64.

57. Hadjiconstantinou, E. An exact algorithm for general orthogonal, two dimensional knapsack problems / E. Hadjiconstantinou, N. Christofides // European Journal of Operational research. — 1995. — no. 83. — P. 39-56.

58. Колоколов, А. А. Алгоритмы декомпозиции и перебора 1-классов для решения некоторых задач размещения / А. А. Колоколов, Т. В. Лева-нова // Вестник Омского ун-та. — 1996. —№ 1.— С. 21-23.

59. Martello, S. Lower bounds and reduction procedures for the bin packing problem / S. Martello, P. Toth // Discrete Applied Mathematics.— 1990.— no. 28. Pp. 59-70.

60. Fekete, S. P. New classes of fast lower bounds for bin packing problems.: Angewandte Mathematik und Informatik 97.265a / S. P. Fekete, J. Schepers: Universität zu Köln, 2001.

61. Локальный поиск ортогональных упаковок с использованием нижних границ / В. М. Картак, М. А. Месягутов, Э. А. Мухачева, А. С. Филиппова // Автоматика и телемеханика, — 2009. — № 6. — С. 167-180.

62. Картак, В. М. Метод группировки для решения непрерывной задачи линейного раскроя / В. М. Картак // Дискретный анализ и исследования операций. — 2009. Т. 3, № 16. - С. 47 - 62.

63. Картак, В. М. Обновленная нижняя граница для задачи упаковки прямоугольников в полубесконечную полосу / В. М. Картак // Вестник УГАТУ. Серия „Управление, вычислительная техника и информатика- 2008. Т. 10, № 2(27). - С. 154-158.

64. Картак, В. М. Матричный алгоритм поиска оптимального решения для задачи упаковки прямоугольников в полубесконечную полосу / В. М. Картак // Информационные технологии. — 2008. — № 1. — С. 36-44.

65. Картак, В. М. Задача упаковки прямоугольников: точный алгоритм на базе матричного представления / В. М. Картак // Вестник УГАТУ. Серия „Управление, вычислительная техника и информатика ".— 2007. Т. 9, № 4(22). - С. 104-110.

66. Картак, В. М. Использование метода группировки для решения задачи линейного раскроя / В. М. Картак // Вестник БашГУ.— 2005. — № 3. С. 9-13.

67. Картак, В. М. Достаточные условия невыполнения свойства дело-численного округления для задачи линейного раскроя / В. М. Картак // Автоматика и телемеханика. — 2004. — № 4. — С. 55-62.

68. Мухачева, Э. А. Модифицированный метод ветвей и границ: алгоритм и численный эксперимент для задачи одномерного раскроя / Э. А. Мухачева, В. М. Картак // Информационные технологии. — 2000.— № 9.-С. 15-21.

69. Модели и методы решения задач ортогонального раскроя и упаковки: аналитический обзор и новая технология блочных структур / Э. А. Мухачева, В. М. Картак, А. С. Мухачева, А. Ф. Валеева // Информационные технологии. — 2004. — № 5. — С. 2-17.

70. Мухачева, Э. А. Математическое программирование. / Э. А. Мухачева, Г. Ш. Рубинштейн. — Новосибирск. Наука. Сибирское отделение., 1987.

71. Carlier, J. New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation / J. Carlier, F. Clautiaux, A. Moukrim // Computers Operations Research. — 2007. — Vol. 34, no. 8. Pp. 2223- 2250.

72. Clautiaux, F. A survey of dual-feasible and super additive functions / F. Clautiaux, C. Alves, J. Valerio de Carvalho // Annals of Operations Research. — 2008. — Vol. 179, no. 1.- Pp. 317-342.

73. Beasley, J. E. An exact two-dimensional non-guillotine cutting tree search procedure / J. E. Beasley // Operations Research. — 1985. —Vol. 33.— Pp. 49-64.

74. Стоян, Ю. Г. Математические модели и оптимизационные методыгеометрического проектирования / Ю. Г. Стоян, С. В. Яковлев.--Киев,1. Наук. Думка., 1986.

75. Мухачева, Э. А. Метод последовательного уточнения оценок: алгоритм и численный эксперимент для задачи одномерного ра<зкроя / Э. А. Мухачева, А. С. Мухачева, Г. Н. Белов // Инфорльационт-с^ье технологии. 2000. - № 2. - С. 11-17.

76. Bortfeld, A. A genetic algorithm for the two-dimensional strip» packing problem with rectangular pieces / A. Bortfeld // European Journal of Operational research. — 2006. — Vol. 172, no. 2. Pp. 814-837.

77. Мухачева, Э. А. Задачи двумерной упаковки в контейнерах: новые подходы к разработке методов локального поиска оптимума / Э. Мухачева, В. М. Картак, В. А.Ф. — Издательство МАИ, 2004.

78. Rietz, J. Families of non-irup instances of the one-dimensiona^l cutting stock problem / J. Rietz, G. Scheithauer, J. Terno // Discrete Appl. JSdath.— 2002,- Vol. 121.- Pp. 229-245.

79. Marcotte, О. An instance of the cutting stock problem fox which the rounding property does not hold / O. Marcotte // Operations Research Letters. 1986.- Vol. 4, no. 5. — Pp. 239-243.

80. Wascher, G. Two approaches to the cutting stock piroTolem / G. Wascher, T. Gau // IFORS'93 Conference. Lisboa. 1993.

81. Nitsche, С. New cases of the cutting stock problem having mirup /

82. C. Nitsche, G. Scheithauer, J. Terno // Math. Meth. Oper. Res.— 1998.— Vol. 48. Pp. 105-115.

83. Digital library of mathematical functions (dlmf), gumma function, inequalities. http://dlmf.nist.gov/Contents/GA/6/.

84. Fernandez de la Vega, W. Bin packing can be solved within 1+e in linear time / W. Fernandez de la Vega, G. S. Lueker // Combinatorica. — 1981. no. 1. - Pp. 349-355.

85. The cutting-stock approach to bin packing: Theory and experiments. /

86. D. L. Applegate, L. S. Buriol, B. L. Dillard et al. // Proceedings of the Fifth Workshop on Algorithm Engineering and Experimentation / Ed. by R. E. Ladner. SIAM, 2003. - Pp. 1-15.

87. Shoenfield, J. E. Fast, exact solution of open bin packing problems without linear programming: Tech. rep. / J. E. Shoenfield: Draft, US Army Space k. Missile Defence Command, Huntsville, Alabama, 2002.

88. Aarts, E. Local search in combinatorial optimization. / E. Aarts, J. K. Lenstra. — John Wiley, Sons Ltd, 1997.

89. Корницкая, M. H. Автоматизация проектирования карт фигурного нерегулярного раскроя в условиях единичного производства на основе аппроксимационного подхода.: Ph.D. thesis / Свердловск: политехнический институт. — 1990.

90. Milencovic, V. I. Allocation and compacting of non-convex polygons for easy industry / V. I. Milencovic, K. Daniels, Z. Li // SICUP-Bulletin. — No. 9. — 1993. — January.

91. Chen, C. S. Analitical model for the container load-ing problem / C. S. Chen, S. M. Lee, Q. S. Shen // International Transactions in Operational Research. 1995. - Vol. 80. — Pp. 68-76.

92. Blazewich, J. Search of prohibition for two dimensional cutting stock problem / J. Blazewich, R. Walkowiak, Poland // SICUP-Bulletin. No. 12. — 1993. — November.

93. Fabian, C. A non-guillotine cutting problem for de-fecting sheets / C. Fabian, E. Spinulescu // SICUP-Bulletin. No. 7. — 1993. — June. - P. 13.

94. Valerio de Carvalho, J. M. Interactive computer's approach to a problem of two-stage cutting stock problem. / J. M. Valerio de Carvalho, A. J. Rodrigues // SICUP-Bulletin. No. 9. - 1992. - November. - P. 1.

95. Abdou, G. Approach for the three-dimensional pal-letization problem / G. Abdou, M. Yang // International Journal of Production Research — 1994. — no. 10.- Pp. 381-394.

96. Oliveria, J. F. Application of approach having modeled normalization to bin packing problem / J. F. Oliveria, J. S. Ferreira // SICUP-Bulletin. — No. 9.- 1992.-P. 20.

97. Orlandi, M. A. Half-automatic interac-tive system for two-dimensional non-regular cutting problem / M. A. Orlandi, M. N. Arenales, M. R. N. // SICUP-Bulletin. No. 9. — 1992. — November. - Pp. 13-14.

98. Medetz, W. Package of programs for automatic figure packing / W. Medetz // SICUP-Bulletin. — No. 9,- 1993. January. - P. 20.

99. Scheithauer, G. Modeling of bin packing problems / G. Scheithauer, J. Terno // SICUP-Bulletin. No. 9. - 1993. - January. - P. 7.

100. Мухачева, Э. А. Модели и методы расчета раскроя упаковки геометрических объектов / Э. А. Мухачева, М. А. Верхотуров, В. В. Мартынов. - Уфа: УГАТУ, 1998.

101. Рвачев, В. Л. К задаче об оптимальном размещении круговых выкроек / В. JI. Рвачев, Ю. Г. Стоян // Кибернетика,— 1965.— № 4.— С. 66-78.

102. Математическая модель и оптимизация линейных Ek(R2) задач размещения / АН УССР. Ин-т пробл. Машиностроения: №353. — Харьков, 1991.

103. Гилл, Ф. Практическая оптимизация / Ф. Гилл, У. Мюррей, М. Райт. — М.:Мир, 1985.

104. Milenkovic, V. J. Translational polygon containment and minimal enclosure using mathematical programming / V. J. Milenkovic, K. Daniels // ITOR special issue with papers from IFORS'96. — 1996. — P. 30.

105. Иванов, Г. А. Проектирование размещения плоских геометрических объектов методами нелинейного программирования.: Ph.D. thesis / Йошкар-Ола: МарПИ. — 1993.

106. Amaral, С. Automatic interactive program means for packing / C. Amaral // SICUP-Bulletin. No. 12. - 1992. - Pp. 2-3.

107. Berkey, J. 0. Two-dimensional finite bin-packing algorithms / J. 0. Berkey, P. Y. Wang // Operations Research. — 1987.— Vol. 38, no. 5.— Pp. 423-429.

108. Sha, E. L. — Area efficient and volume efficient algorithms for loading cargo. — Master's thesis, US Navy Post-Graduate School, 1970.

109. Tinarelli, U. Un problema di caricamento di containers / U. Tinarelli, M. Addonizio 11 Proc. AIRO congress. — 1978. — Pp. 79-91.

110. Задача размещения прямоугольно-ориентированных многоугольников: модели и алгоритм покоординатной упаковки / В. М. Картак, Л. И. Васильева, Э. А. Мухачева, А. А. Петунин // Информационные технологии. 2008. — № 3. — С. 46-54.

111. Колоколов, А. А. Регулярные разбиения и отсечения в целочисленном программировании / А. А. Колоколов // Сибирский журнал исследования операций. — 1994. — № 2. — С. 18-39.

112. Колоколов, А. А. Анализ устойчивости 1-разбиения в конечномерном пространстве / А. А. Колоколов, М. В. Девятерикова // Дискретный анализ и исследование операций. Сер.2.— 2000. — Т. 6, № 2. — С. 47-53.