Содержание к диссертации
Введение
1 Использование математических пакетов в некоторых задач (псевдо)римановой геометрии 9
1.1 Пакеты встроенных процедур "linalg" и " Linear Algebra" 9
1.2 Использование пакета MAPLE в решении некоторых задач (псевдо)римановой геометрии 12
2 Левоинвариантные лоренцевы метрики на трехмерных группах Ли с нулевым квадратом длины тензора Схоутена-Вейля 19
2.1 Постановка основной задачи 19
2.2 Некоторые факты теории групп и алгебр Ли 21
2.3 Классификации трехмерных алгебр и групп Ли 24
2.4 Формулы для вычисления кривизн левоинвариантных (псев-до)римановых метрик 26
2.5 Левоинвариантные лоренцевы метрики с нулевым квадратом длины тензора Схоутена-Вейля на трехмерных унимодуляр-ных группах Ли 29
2.6 Левоинвариантные лоренцевы метрики с нулевым квадратом длины тензора Схоутена-Вейля на трехмерных неунимоду-лярных группах Ли 41
3. Области знакоопределенности кривизн левоинвариантных римановых метрик на трехмерных группах Ли 50
3.1 Оценки кривизн левоинвариантных римановых метрик на трехмерных группах Ли 50
3.2 Области знакоопределенности секционной кривизны левоинвариантных римановых метрик на трехмерных группах Ли 61
3.3 Области знакоопределенности одномерной кривизны левоинвариантных римановых метрик на трехмерных группах Ли . 67
3.4 Области знакоопределенности кривизны Риччи левоинвариантных римановых метрик на трехмерных группах Ли . 75
Приложение 1 78
Приложение 2 92
- Использование пакета MAPLE в решении некоторых задач (псевдо)римановой геометрии
- Формулы для вычисления кривизн левоинвариантных (псев-до)римановых метрик
- Левоинвариантные лоренцевы метрики с нулевым квадратом длины тензора Схоутена-Вейля на трехмерных неунимоду-лярных группах Ли
- Области знакоопределенности секционной кривизны левоинвариантных римановых метрик на трехмерных группах Ли
Введение к работе
Данная диссертация посвящена применению математических пакетов к решению задач (псевдо)римановой геометрии. За пятьдесят лет своего существования вычисления с использованием ЭВМ не только не утратили своей актуальности, но являются приоритетным направлением в развитии современной науки. Область применения компьютерной математики уже не ограничивается предсказанием погоды и вычислением числа 7г. Современная геометрия, также как и другие области математики, привлекает новейшие технологии для решения своих задач. Уже существуют прецен-денты, доказывающие эффективность программного обеспечения не только при решении численных задач, но и при доказательстве теорем. Так, например, О.Г. Вагина и М.И. Кабенюк в [1] дали новое более короткое доказательство о покрытии евклидовой плоскости равносторонними пятиугольниками. Доказательство базировалось на вычислениях, сделанных с помощью пакета MAPLE. Камсеманан (N. Khamsemanan) и Коннелли (R. Connelly) в [21] дали новое доказательство теоремы о функции, сохраняющей расстояние. Также стоит упомянуть доказательство гипотезы Атья (Atiyah) о расположении п точек в трехмерном Евклидовом пространстве при п = 4, данное Иствудом (М. Eastwood) и Норбари (P. Norbury) в [18].
Опыт использования пакетов прикладных программ также широко используется в задачах классификации. Так, Hlavova' М. в [29] удалось классифицировать двупараметрические движения плоскости Лобачевского, P. Bueken, L. Vanhecke в статье [15] внесли вклад в проблему классификации трех- и четырехмерных однородных относительно тензора кривизна Риччи эйнштейново-подобных многообразий. В отечественной науке известны результаты, полученные Е.Д. Родионовым и В.В. Славским при классификации локально конформно однородных многообразий [13],[25], и результаты Ю.Г. Никонорова по классификации однородных эйнштенйно-
5 вых многообразий, полученные в работах [10], [11]. Известны также работы
Никоноровой Ю.В. в области комбинаторной геометрии, использующие для
решения задач (о внутреннем расстоянии на поверхности параллелепипеда,
задачи Фике, Ионина, Поповичи) пакеты символьных вычислений.
Налицо не только рост числа задач, решенных с помощью компьютера, но и разработка новых алгоритмов и программ для решения определенных типов задач. Появляются новые ([16],[30]), совершенствуются старые ([24],[20]) алгоритмы, и сейчас трудно оценить до конца тот вклад, который привносится в математику новыми компьютерными технологиями.
Данная работа посвящена исследованию левоннвариантных (псев-до)римановых метрик на трехмерных группах Ли и является продолжением вышеприведенных исследований в области римановой и псевдори-мановой геометрии с использованием новейших разработок-компьютерной алгебры.
Методы исследования. В работе используются методы компьютерной алгебры, методы теории групп Ли и алгебр Ли, римановой и псевдорима-новой геометрии и тензорного анализа.
Основные результаты.
Получена классификация левоннвариантных лоренцевых метрик на группах Ли с нетривиальным тензором Схоутена-Вейля, квадрат длины которого равен нулю.
Найдены области в пространстве структурных констант, в которых одномерная, секционная кривизна и кривизна Риччи левоинвариантной римановой метрики на трехмерной группе Ли имеет постоянный знак.
Разработаны эффективные алгоритмы для вычисления компонент тензоров секционной, одномерной кривизн и кривизны Риччи, а также компонент тензора Схоутена-Вейля левоннвариантных лоренцевых метрик на группах Ли.
G Апробация работы. Результаты диссертации были представлены на
Международной школе-конференции по анализу и геометрии, посвященной 75-летию академика Ю.Г. Решетияка (Новосибирск, 23 августа - 2 сентября 2004г.), Международной школе-конференции по геометрии и анализу, посвященной памяти А.Д. Александрова) (Новосибирск, 9-20 сентября 2002г.), Седьмой региональной конференции по математике МАК-2004 (Барнаул, 2004), Шестой региональной конференции по математике МАК-2003 (Барнаул, 2003), Межрегиональной конференции по математическому образованию в регионах России (Барнаул, 2004). Кроме того, все результаты диссертации в разное время докладывались на семинарах кафедры математического анализа Алтайского государственного университета, кафедры геометрии Барнаульского государственного педагогического университета.
Публикации. Все основные результаты работы были опубликованы в [31]-[411.
Структура и обьем работы. Диссертация изложена на 118 страницах, состоит из введения, трех глав, разбитых на разделы, пяти приложений и списка литературы.
Содержание диссертации.
Первая глава диссертации посвящена использованию математических пакетов в решении задач (псевдо)римановой геометрии. Первый раздел посвящен описанию некоторых возможностей системы аналитических вычислений MAPLE 8.00: дается краткое описание пакетов встроенных процедур, "linalg" и " LinearAlgebra", используемых автором в процессе решения указанных выше задач, показано их фундаментальное различие. Во втором разделе на примере решения задачи о левоинвариантных лоренцевых метриках с нулевым квадратом длины тензора Схоутена-Вейля показано как можно эффективно использовать пакеты аналитических вычислений в решении задач (псевдо)римановой геометрии.
Вторая глава посвящена решению задач о левоинвариантных
7 лоренцевых метриках на трехмерных группах Ли, для которых квадрат
длины тензора Схоутена-Вейля тривиален, а некоторые его компоненты
отличны от нуля. В первом разделе приводятся необходимые сведения и
сформулирована основная задача.
Во втором разделе указываются некоторые факты из теории групп Ли и алгебр Ли, необходимые при дальнейшем изложении, доказываются некоторые вспомогательные утверждения. В третьем разделе даются определения секционной и одномерной кривизн, кривизны Риччи левоинвариантных (псевдо)римановых метрик и указываются формулы для их вычисления в случае однородных пространств.
В четвертом разделе рассматриваются классификации трехмерных алгебр Ли, данные Н.Джекобсоном и Дж.Милнором, которые используются при дальнейшем изложении. Пятый раздел посвящен левоинвариантным лоренцевым метрикам на трехмерных унимодулярных группах Ли. Доказываются теорема о строении унимодулярных алгебр Ли и теоремы классификации для левоинвариантных лоренцевых метрик с нулевым квадратом длины тензора Схоутена-Вейля.
В заключительном разделе второй главы изучаются левоинвариантные лоренцевы метрики на неунимодулярных группах Ли. Рассматриваются возможные расположения плоскости базисных векторов в алгебре Ли по отношению к изотропному конусу и, в зависимости от этого, определяются метрики с ненулевыми компонентами и нулевым квадратом длины тензора Схоутена-Вейля.
В третьей главе дается решение задачи об областях знакоопределенности кривизн левоинвариантных римановых метриках на трехмерных группах Ли. Первый параграф содержит необходимые сведения об оценках указанных кривизн, второй, третий и четвертый параграфы посвящены отысканию областей в пространстве структурных констант, в которых секционная, одномерная кривизны и кривизна Риччи соответственно имеют постоянный знак.
8 В приложениях описаны программы для вычисления компонент
тензоров римановой, секционной, одномерной кривизн, тензора Риччи и
Схоутена-Вейля и программа для вычисления матрицы формы Киллинга.
Автор глубоко признателен Е.Д. Родионову и В.В. Славскому за
постановку задач, плодотворные дискуссии и поддержку.
Использование пакета MAPLE в решении некоторых задач (псевдо)римановой геометрии
Во втором разделе указываются некоторые факты из теории групп Ли и алгебр Ли, необходимые при дальнейшем изложении, доказываются некоторые вспомогательные утверждения. В третьем разделе даются определения секционной и одномерной кривизн, кривизны Риччи левоинвариантных (псевдо)римановых метрик и указываются формулы для их вычисления в случае однородных пространств.
В четвертом разделе рассматриваются классификации трехмерных алгебр Ли, данные Н.Джекобсоном и Дж.Милнором, которые используются при дальнейшем изложении. Пятый раздел посвящен левоинвариантным лоренцевым метрикам на трехмерных унимодулярных группах Ли. Доказываются теорема о строении унимодулярных алгебр Ли и теоремы классификации для левоинвариантных лоренцевых метрик с нулевым квадратом длины тензора Схоутена-Вейля.
В заключительном разделе второй главы изучаются левоинвариантные лоренцевы метрики на неунимодулярных группах Ли. Рассматриваются возможные расположения плоскости базисных векторов в алгебре Ли по отношению к изотропному конусу и, в зависимости от этого, определяются метрики с ненулевыми компонентами и нулевым квадратом длины тензора Схоутена-Вейля.
В третьей главе дается решение задачи об областях знакоопределенности кривизн левоинвариантных римановых метриках на трехмерных группах Ли. Первый параграф содержит необходимые сведения об оценках указанных кривизн, второй, третий и четвертый параграфы посвящены отысканию областей в пространстве структурных констант, в которых секционная, одномерная кривизны и кривизна Риччи соответственно имеют постоянный знак. В приложениях описаны программы для вычисления компонент тензоров римановой, секционной, одномерной кривизн, тензора Риччи и Схоутена-Вейля и программа для вычисления матрицы формы Киллинга. Автор глубоко признателен Е.Д. Родионову и В.В. Славскому за постановку задач, плодотворные дискуссии и поддержку. Функциональность пакетов "linalg" и " LinearAlgebra" почти одинакова, но все же имеются некоторые отличия. Пакет " Linear Algebra" основан на известном пакете численных расчетов Numerical Algorithms Group (сокращенно - NAG), что позволяет работать с числовыми матрицами больших размеров. Основными объектами, с которыми работают эти пакеты, являются матрицы, но в пакете "linalg" используются матрицы, построенные на основе массива, который создается при помощи программы array(..), а в пакете "LinearAlgebra" при помощи структуры r-таблицы (rtable). Rtable - это низкоуровневая стандартная программа MAPLE, которая позволяет конструировать массивы (Лттау (..)), матрицы (Matrix(..)) и векторы {Vector(..)). Существенное различие в том, что матрицы в пакете "linalg" вычисляются только до уровня своих имен, поэтому, используя простые операции над матрицами, мы должны пользоваться специальным синтаксисом для отображения результата. Например, если мы хотим сложить уже заданные матрицы А п В и вводим в командной строке "А + В", то в качестве результата отобразится не матрица, полученная в результате сложения, а символ "А + В". Если мы хотим все же отобразить нужную матрицу, надо воспользоваться командой eval(..) или print(..). В пакете "LinearAlgebra" матрицы вычисляются до уровня своих элементов, поэтому задание имени матрицы в области ввода рабочего листа приводит к отображению всех ее элементов. Это обстоятельство существенно ускоряет процесс набора команд и позволяет контролировать по шагам ход решения задачи. Матрицы, заданные с помощью массива и матрицы, заданные с помощью г - таблицы, можно конвертировать друг в друга при помощи команды convert ..). В случае, когда надо конвертировать Matrix (заданной в " Linear Algebra") в matrix (заданной в "linalg"), опциями команды будут: convert(Af matrix). Таким образом, можно одновременно пользоваться двумя пакетами, выбирая каждый раз наиболее подходящий для данного этапа вычислений.
Чтобы понять, какой из двух пакетов использовать при решении поставленной задачи, нужно обратить внимание на следующие решающие положения: Пакет "linalg" целесообразно использовать для абстрактных и символьных вычислений; Пакет " Linear Algebra" является, в отличие от "linalg", наиболее мощным и эффективным средством вычисления, особенно если речь идет о численных матрицах большого размера.
Пакет " LinearAlgebra" реализован в виде модуля, новой языковой конструкции MAPLE, реализующей элементы объектно -ориентированного программирования. В состав пакета "LinearAlgebra", помимо процедур и функций пакета "linalg" (отличающихся синтаксисом), входят дополнительные команды для задания специальных типов матриц и некоторые новые функции. При решении задач линейной алгебры этот пакет автоматически выбирает, какую модель вычислений следует использовать: символьную, программную реализацию арифметики чисел с плавающей точкой с произвольным числом значащих цифр или арифметику чисел с плавающей точкой, поддерживаемую процессором компьютера. Символьная модель самая медленная, в то время как процессорная модель самая быстрая. В зависимости от используемой модели для решения одной и той же задачи используются разные встроенные процедуры. Для символьных вычислений применяются процедуры, написанные на языке MAPLE, что приводит к снижению скорости вычислений. Для двух других моделей подключаются откомпилированные программы из пакета численных расчетов NAG, причем для программного моделирования вычислений с произвольным числом плавающих цифр в мантиссе скорость вычислений меньше, чем при использовании арифметики процессора (но в этом случае уменьшается точность вычислений). Для определения используемой модели, MAPLE прежде всего проверяет тип данных матрицы посредством специальной опции конструктора матриц datatype. Если эта опция не была задана пользователем, то MAPLE осуществляет поэлементную проверку типов данных. Очевидно, что при больших порядках матриц этот процесс может быть длительным. После проверки происходит выбор подходящей модели: если элементы матрицы содержат только числовые данные, причем хотя бы один элемент представлен числом с плавающей точкой, и значение переменной окружения UseHardwareFloats равно true, используется арифметика процессора; если элементы матрицы содержат только числовые данные и хотя бы один элемент представлен числом с плавающей точкой, а значение переменной окружения UseHardwareFloats равно false, используется программная реализация арифметики вещественных чисел; если есть хоть одно не числовое значение или нет чисел с плавающей точкой, то используются процедуры символьных вычислений.
Формулы для вычисления кривизн левоинвариантных (псев-до)римановых метрик
Функциональность пакетов "linalg" и " LinearAlgebra" почти одинакова, но все же имеются некоторые отличия. Пакет " Linear Algebra" основан на известном пакете численных расчетов Numerical Algorithms Group (сокращенно - NAG), что позволяет работать с числовыми матрицами больших размеров. Основными объектами, с которыми работают эти пакеты, являются матрицы, но в пакете "linalg" используются матрицы, построенные на основе массива, который создается при помощи программы array(..), а в пакете "LinearAlgebra" при помощи структуры r-таблицы (rtable). Rtable - это низкоуровневая стандартная программа MAPLE, которая позволяет конструировать массивы (Лттау (..)), матрицы (Matrix(..)) и векторы {Vector(..)). Существенное различие в том, что матрицы в пакете "linalg" вычисляются только до уровня своих имен, поэтому, используя простые операции над матрицами, мы должны пользоваться специальным синтаксисом для отображения результата. Например, если мы хотим сложить уже заданные матрицы А п В и вводим в командной строке "А + В", то в качестве результата отобразится не матрица, полученная в результате сложения, а символ "А + В". Если мы хотим все же отобразить нужную матрицу, надо воспользоваться командой eval(..) или print(..). В пакете "LinearAlgebra" матрицы вычисляются до уровня своих элементов, поэтому задание имени матрицы в области ввода рабочего листа приводит к отображению всех ее элементов. Это обстоятельство существенно ускоряет процесс набора команд и позволяет контролировать по шагам ход решения задачи. Матрицы, заданные с помощью массива и матрицы, заданные с помощью г - таблицы, можно конвертировать друг в друга при помощи команды convert ..). В случае, когда надо конвертировать Matrix (заданной в " Linear Algebra") в matrix (заданной в "linalg"), опциями команды будут: convert(Af matrix). Таким образом, можно одновременно пользоваться двумя пакетами, выбирая каждый раз наиболее подходящий для данного этапа вычислений.
Чтобы понять, какой из двух пакетов использовать при решении поставленной задачи, нужно обратить внимание на следующие решающие положения: Пакет "linalg" целесообразно использовать для абстрактных и символьных вычислений; Пакет " Linear Algebra" является, в отличие от "linalg", наиболее мощным и эффективным средством вычисления, особенно если речь идет о численных матрицах большого размера.
Пакет " LinearAlgebra" реализован в виде модуля, новой языковой конструкции MAPLE, реализующей элементы объектно -ориентированного программирования. В состав пакета "LinearAlgebra", помимо процедур и функций пакета "linalg" (отличающихся синтаксисом), входят дополнительные команды для задания специальных типов матриц и некоторые новые функции. При решении задач линейной алгебры этот пакет автоматически выбирает, какую модель вычислений следует использовать: символьную, программную реализацию арифметики чисел с плавающей точкой с произвольным числом значащих цифр или арифметику чисел с плавающей точкой, поддерживаемую процессором компьютера. Символьная модель самая медленная, в то время как процессорная модель самая быстрая. В зависимости от используемой модели для решения одной и той же задачи используются разные встроенные процедуры. Для символьных вычислений применяются процедуры, написанные на языке MAPLE, что приводит к снижению скорости вычислений. Для двух других моделей подключаются откомпилированные программы из пакета численных расчетов NAG, причем для программного моделирования вычислений с произвольным числом плавающих цифр в мантиссе скорость вычислений меньше, чем при использовании арифметики процессора (но в этом случае уменьшается точность вычислений). Для определения используемой модели, MAPLE прежде всего проверяет тип данных матрицы посредством специальной опции конструктора матриц datatype. Если эта опция не была задана пользователем, то MAPLE осуществляет поэлементную проверку типов данных. Очевидно, что при больших порядках матриц этот процесс может быть длительным. После проверки происходит выбор подходящей модели: если элементы матрицы содержат только числовые данные, причем хотя бы один элемент представлен числом с плавающей точкой, и значение переменной окружения UseHardwareFloats равно true, используется арифметика процессора; если элементы матрицы содержат только числовые данные и хотя бы один элемент представлен числом с плавающей точкой, а значение переменной окружения UseHardwareFloats равно false, используется программная реализация арифметики вещественных чисел; если есть хоть одно не числовое значение или нет чисел с плавающей точкой, то используются процедуры символьных вычислений.
Левоинвариантные лоренцевы метрики с нулевым квадратом длины тензора Схоутена-Вейля на трехмерных неунимоду-лярных группах Ли
Сложность решения задачи раскроя-упаковки обусловлена ее принадлежностью к классу NP-трудных задач комбинаторной оптимизации. Исследуемая задача является NP-трудной в сильном смысле, так как содержит в качестве подзадачи также NP-трудную задачу. Во многих случаях применение точных методов для ее решения невозможно из-за больших затрат вычислительного времени. В связи с этим большое значение приобретает разработка и исследование эвристических методов оптимизации, в том числе метаэвристик. В их числе широкое применение получили генетические алгоритмы. Известна асимптотическая сходимость таких методов. Однако практически оптимум достигается не всегда. Кроме того, до сих пор не известны способы построения нижних границ, позволяющие констатировать достижение оптимума. Вместе с тем на практике метаэвристики очень хорошо себя зарекомендовали. Качество полученного решения зависит не только от выбранного метода расчета раскроя-упаковки. Важную роль выполняют и способы кодирования и дешифровки упаковок.
Исходя из вышеизложенного, представляет интерес разработка и применение новых генетических алгоритмов для решения задачи раскроя-упаковки прямоугольных предметов на базе эффективных принципов кодирования упаковок. Важным является создание программной реализации, которая позволила бы решать производственные задачи за приемлемое время. Разработанное алгоритмическое и программное обеспечение становится конкурентоспособным в ряду точных и эвристических подходов. В этом состоит актуальность данной разработки.
Целью работы является разработка и исследование моделей и методов решения задачи прямоугольной упаковки и раскроя на базе блочной и мультиметодной технологий. Для ее достижения были поставлены и решены следующие задачи: 1. Анализ вероятностных методов локального поиска оптимального решения для задач раскроя и упаковки; 2. Постановка задач прямоугольного раскроя и разработка моделей блочной структуры; 3. Разработка и исследование эффективности генетического блочного алгоритма; 4. Создание способа кодирования упаковок, удобного для применения разработанных методов оптимизации к решению исследуемой задачи; 5. Разработка алгоритмов-декодеров, формирующих упаковку на основе заданного кода; 6. Применение мультиметодной технологии дискретной оптимизации И.П. Норенкова для решения задачи прямоугольного гильотинного раскроя и исследование эффективности данного подхода; 7. Разработка программного обеспечения на базе предложенных методов. Анализ эффективности и характеристик разработанных алгоритмов на основе результатов численных экспериментов и сравнение эффективности методов с другими, описанными в литературе. На защиту выносятся: 1. Блочный способ кодирования упаковки; 2. Генетический блочный алгоритм для решения задачи прямоугольной упаковки полубесконечной полосы; 3. Применение генетического блочного алгоритма для решения задач прямоугольной упаковки листов; 4. Алгоритм конструирования упаковки - «блочный декодер»; 5. Генетический алгоритм гильотинного раскроя на базе мультиметодноЙ технологии дискретной оптимизации И.П. Норенкова с дискриминацией эвристик; 6. Компьютерная программа, реализующая разработанные алгоритмы; 7. Исследование эффективности предложенных методов на основе результатов вычислительного эксперимента. Научная новизна работы. Новыми в работе являются: 1. Блочный способ кодирования, основывающийся на блочной модели упаковки, который позволил применить для решения задачи новый тип алгоритмов декодирования. Предложенный способ является эффективным методом моделирования упаковки по ряду параметров: однозначность представления упаковки, простота модификации кода, учет всех пустых областей непосредственно в коде, возможность использования в других методах локального поиска оптимума; 2. «Блочный декодер» - новый алгоритм конструирования упаковки; для него доказано наличие свойства «реставрации»; может применяться в других метаэвристиках; 3. Генетический блочный алгоритм; Модифицирована идентификация элементов генетического метода: генов, аллелей, хромосом и процедур над ними; создан новый генетический алгоритм, показано, что его эффективность лучше по сравнению с известными в литературе реализациями; 4. Применение принципов мулыпиметодной технологии дискретной оптимизации И.П. Нореннова к задаче гильотинного раскроя. Введение дискриминации простых эвристик позволило увеличить эффективность алгоритма. Практическая значимость работы: программная реализация генетического блочного алгоритма показала значительные преимущества перед известными классическими способами применения эвристических методов к задачам упаковки на достаточно широком классе задач. Это позволяет использовать разработанные алгоритмы при практических расчетах. Программное обеспечение зарегистрировано в РОСПАТЕНТ свидетельство №2002610945; результаты работы внедрены в ОАО АСКОН, г. Москва и учебный процесс У Г АТУ.
Апробация работы. Работа выполнялась в рамках заданий РФФИ, проекты 99-01-00937, 01-01-00510. За цикл работ «Новые генетические алгоритмы решения задач двумерного раскроя и упаковки» присуждена Медаль РАН. За лучшую научную студенческую работу автор награжден медалью Министерства Образования РФ. Во время учебы в аспирантуре был удостоен стипендии Президента РФ и стипендии Правительства РФ. Результаты работы и отдельные ее разделы докладывались и обсуждались на следующих конференциях и семинарах:
Области знакоопределенности секционной кривизны левоинвариантных римановых метрик на трехмерных группах Ли
Во введении к диссертации обоснована актуальность решаемой научной проблемы; сформулирована цель и задачи исследования; приведены результаты, выносимые на защиту; отмечена их научная новизна и практическая значимость. Приведены сведения об апробации работы и публикациях.
В первой главе проведен аналитический обзор моделей и методов решения задач прямоугольной упаковки и раскроя.
Во второй главе приводятся математические постановки задач прямоугольной упаковки в полу бесконечную полосу и упаковки на листы. Предложена блочная модель упаковки и изучены две задачи: кодирование упаковки с помощью блочного кода и обратная ей восстановление допустимой упаковки (декодирование). Третья глава посвящена генетическим методам решения задачи упаковки в полосу и адаптация алгоритмов для решения задачи на листы. Четвертая глава посвящена исследованию мультиметодной технологии дискретной оптимизации И.П. Норенкова на примере рулонного гильотинного раскроя. В пятой главе описывается реализация ПО согласно принципов объектно-ориентированного программирования и ряд вычислительных экспериментов.
В течение последних пятидесяти лет проблема «раскроя-упаковки» (Cutting and Packing, С&Р) привлекает внимание научных исследователей и производственников. Начало этому доложила в 1951 г. книга ленинградских ученых Л.В. Канторовича и В.А. Залгаллера [12], [13]. Задачи раскроя рассматривались ими как примеры применения ранее развитого Л.В. Канторовичем линейного программирования (Linear Programming, LP). Для решения задач С&Р применяется модель LP с неявно заданной информацией о раскроях (столбцах матрицы). Для генерации столбцов В.А. Залгаллером был предложен прием, предвосхитивший появившееся позднее динамическое программирование. Аналогичные методы получили развитие в 60-е годы за рубежом в работах P. Gilmore & R. Gomory [59], [60] и позднее J. Terno, R. Lindeman & G. Scheithauer [81]. Для решения задачи генерирования раскроя были разработаны метод склейки И.В.Романовским [35], сеточный метод для линейного раскроя В.А. Булавским и М.А. Яковлевой [3], для гильотинного раскроя Э.А. Мухачевой [26], [27]. На базе линейного программирования Э.А. Мухачевой разработаны также алгоритмы условной оптимизации, учитывающие специфику реального производства [25]. В то время основной целью этих и многих других работ являлось применение линейного программирования в сфере производственных задач. Эта цель в той или иной мере была достигнута в условиях массового и серийного производства. В зарубежной литературе признан приоритет Л.В. Канторовича и В.А. Залгаллера [59]. Однако задачи раскроя и упаковки по своей сути являются проблемами дискретной оптимизации и их решение с помощью линейного программирования не более чем непрерывная релаксация, которая дает близкое к оптимальному решение при дополнительных ограничениях, возникающих в условиях серийного производства. Далее задачи раскроя-упаковки рассматриваются как прикладные проблемы комбинаторных задач исследования операций. Н, Гэри и Д.Джонсон показали, что задача одномерной упаковки в контейнер (ID Bin Packing Problem, IDBP) принадлежит к классу NP-трудных задач и для точного решения необходимо применять схемы полного перебора [7], [57].
Впервые качественная типология в области раскроя-упаковки проведена в 1990 г. немецким ученым Н. Dykhoff [51]. Она принята в мировой практике и используется при изучении моделей и методов решения задач раскроя-упаковки. Разнообразие моделей определяется прежде всего фактором геометрии. Различаются задачи линейного (одномерного), прямоугольного (двухмерного) и параллелепипедного (трехмерного) раскроя-упаковки. Среди этих задач выделяются гильотинный раскрой и упаковка. Особо выделены проблемы нестинга, размещения деталей сложной геометрической формы в заданных областях. Для них на первый план выступают информационные проблемы задания фигур, учета и обеспечения их непересечения. Задачи С&Р являются типичными представителями NP-трудных проблем и для их решения (включая проблемы нестинга) применяются общие подходы: точные методы, простые эвристики и метаэвристики. Ввиду неполиномиальной сложности точных алгоритмов, авторами многих работ уделяется значительное внимание приближенным методам и эвристикам.
В течение 90-х годов прошлого столетия по теме раскроя-упаковки было выпущено шесть специальных изданий: под редакцией H.Dyckhoff & G.Wascher в 1990 г. [52], S.Martello в 1994 г. [69], [70], Y.Lirov в 1995 г. [65], E.Bischoff & G.Wascher в 1995 г. [44], E.Mukhacheva в 1997 г. [75], H.Yanasse в 1999 г. [85], P.Wang & G.Washer в 2002 г. [84]. Более того, сотни статей опубликованы в международных и российских журналах: European Journal of Operational Research (EJOR), Computers & Operational Research, Computers & Industrial Engineering, Operations Research Letters, Pesquisa Operacional; Информационные технологии, Автоматика и телемеханика, Дискретный анализ и исследование операций, Вестник высшей школы, Кузнечно-штамповочное производство и другие центральные и ведомственные издания. При этом статьи и книги имеют как теоретический, так и прикладной характер.
Причина растущего интереса к задачам раскроя-упаковки состоит в их принадлежности к NP-трудным проблемам, в широкой применимости результатов, разнообразии и сложности задач реального мира, которые можно реализовать как NP-трудные. В качестве основной здесь рассматривается задача прямоугольной упаковки в полубесконечную полосу 1.5DBP (L5D Bin Packing, 1.5DBP). Её обобщением является двумерная задача упаковки в листы, а сопутствующими проблемами являются задачи одномерного раскроя (ID Cutting Stock, 1DCSP) и упаковки (ID Bin Packing, 1DBP).
