Содержание к диссертации
Введение
1 Постановка задачи и схема метода 15
1.1 Постановка задачи одномерного раскроя материала различных длин 15
1.2 Классификация методов решения задач раскроя-упаковки . 18
1.3 Схема решения 19
1.4 Выводы 21
2 Непрерывная релаксация 22
2.1 Постановка задачи. Симплекс-метод с обратной матрицей . 22
2.2 Метод секущих плоскостей на базе непрерывной релаксации . 23
2.3 Удаление сечений: меры против циклов 25
2.4 Генерация сечений 25
3 Генерация столбцов 28
3.1 Генерация столбцов без сечений 28
3.1.1 Постановка задачи генерирования столбцов 29
3.1.2 Динамические уравнения для генерирования карты раскроя 29
3.1.3 Прямая стратегия динамического программирования . 30
3.1.4 Принцип Никольсона в динамическом программировании 32
3.1.5 Расчет решения 33
3.2 Генерирование столбцов при наличии сечений 34
3.2.1 Постановка задачи 34
3.2.2 Несколько типов прутка 36
3.2.3 Сортировка заготовок 36
3.2.4 Предварительный останов 37
3.3 Доминантность заготовок 37
3.3.1 Проверка доминантности заготовок при наличии сечений 39
4. Построение целочисленных решений и тест оптимальности 43
4.1 Построение целочисленных решений 43
4.1.1 Округление непрерывного решения 43
4.1.2 Расширение задачи остатка 44
4.2 Метод последовательного уточнения оценок 45
4.3 Тест оптимальности целочисленного решения 47
4.3.1 Описание задачи 47
4.3.2 Генерация растровых точек цен материала 47
Вычислительный эксперимент 49
5.1 Реализация программного обеспечения 49
5.1.1 Концепция ПО 49
5.1.2 Модифицированная трансформация базиса в симплекс-методе 50
5.1.3 Переполнение мантиссы 54
5.1.4 Погрешности вычислений. Рестарт 55
5.2 Несколько типов прутка: сравнение с другими алгоритмами . 57
5.3 Генерирование тестовых задач 58
5.4 Количество задач с сечениями 59
5.5 Сравнение с методом branch-and-price 62
5.6 Несколько типов прутка: характеристики алгоритма 65
5.7 Графический анализ производительности 68
5.8 Эталонные результаты 71
5.9 Управляющие переменные 74
5.10 Фиксированные выходные параметры 74
5.11 Целочисленная трансформация базиса 74
5.12 Оценка серии т — 40, М = 5 78
5.13 Наблюдения относительно свойства MIRUP 78
5.14 Таблицы в приложении 82
5.15 Восстановление карты посредством branch-and-bound 82
5.16 Выводы по тестам и направления дальнейшей работы 83
5.17 Внедрение 85
6 Заключение 87
Список использованной литературы 90
Приложение 95
- Классификация методов решения задач раскроя-упаковки
- Динамические уравнения для генерирования карты раскроя
- Модифицированная трансформация базиса в симплекс-методе
- Графический анализ производительности
Введение к работе
Актуальность проблемы. Задачи раскроя-упаковки вызывают широкий интерес как в производстве, так и в теоретических исследованиях. Классическая задача одномерного раскроя (one-dimensional cutting stock problem, 1DCSP) рассматривается во множестве публикаций [4, 25, 26, 31, 21]. Эта задача состоит в минимизации количества идентичных прутков материала, используемых для раскроя определенного набора заготовок. В диссертации изучается общий случай, когда имеется материал различных длин.
Еще в 1951 году Л.В. Канторович и В.А. Залгаллер предложили под
ход, основанный на непрерывной релаксации с генерацией столбцов (карт
раскроя). Независимо аналогичный метод был обоснован и подробно описан
ф Гил мор и Гомори в [25]. Требование целочисленности интенсивностей рас-
«зг
кроя опускается и можно применить симплекс-метод. Однако из-за большого количества столбцов приходится генерировать только их подмножество, т.е. матрица ограничений задана неявно. При этом (под-)задача генерирования столбцов является задачей рюкзака и решается методом ветвей и границ или с помощью динамического программирования. Решение непрерывной релаксации можно округлить и решить задачу остатка с помощью эвристик. В случае с единственным типом материала в подавляющем большинстве примеров разрыв между значением непрерывной релаксации и значением полученного целочисленного решения не превышает 1 длины материала, то есть округленное решение оптимально. В остальных случаях автору не известно разрыва более чем 2. В условиях массового производства, где значения интенсивностей раскроя велики, этот подход можно назвать рациональным. Но в единичном производстве необходимы более эффективные методы.
Более того, если решать задачу оптимально, то в большинстве случаев оказывается, что разрыв между значением непрерывной релаксации и значением целочисленного оптимума не достигает 1 (т.н. свойство целочисленного округления, integer round-up property IRUP). Известны также примеры, где
этот разрыв превышает 1. Есть гипотеза о том, что этот разрыв не может до-
стигать 2 (модифицированное свойство целочисленного округления, modified integer round-up property MIRUP).
Существует-множество эвристик различной сложности. Самые простые
— это первый подходящий (First Fit, FF), первый подходящий с упорядо
чиванием (First Fit Decreasing, FFD) и их вариации. Большего усердия при
разработке и исследовании требуют такие методы, как жадный алгоритм и
его вариация, метод последовательного уточнения оценок (sequential value
correction method SVC, Мухачева и Залгаллер [31]), эволюционные алгорит
мы, методы частичного перебора. Очень много эвристических схем подключа
ют непрерывную релаксацию с генерацией столбцов для вычисления нижней
границы и получения округленного решения. Существуют различные оценки
Ф качества эвристик, например вероятностные характеристики или доказатель-
ства асимптотической точности на определенном классе задач (см. Гимади и Залюбовский [3]).
Долгое время применение точных методов для 1DCSP не было успешным. Однако в последние годы в связи со значительным развитием вычислительной техники, а также из-за приспособления точных методов к задаче (например, специфические методы ветвления) в практическом применении точных методов достигнуты значительные успехи. В большинстве случаев эти методы — модификации метода ветвей и границ. Наиболее успешен метод ветвей и границ с генерацией столбцов, т.н. branch-and-price. Ветвление производится посредством добавления ограничений (разбиения множества решений) в непрерывной релаксации. Для задачи Bin Packing (требуемые комплектности всех заготовок равны 1) разработаны специальные границы целевой функции и модификации метода ветвей и границ [43, 44].
Другой распространенный в дискретной оптимизации точный метод — это метод секущих плоскостей (cutting plane algorithm, СРА). Секущие плоскости (отсечения) описывают выпуклую оболочку целочисленных решений. Таким образом, добавление отсечений к ограничениям непрерывной релак-
Ф сации уточняет нижнюю границу целевой функции и приближает решение
релаксации к целочисленному оптимуму. Последний часто может быть най
ден с помощью эвристических процедур округления непрерывного решения.
Однако добавление отсечений в модели с генерацией столбцов не так просто.
Дело в том, что при генерации новых столбцов приходится учитывать коэф-
№ фициенты отсечений для этих столбцов. Коэффициенты нелинейно зависят
от предыдущих ограничений. Эту проблему впервые решили Scheithauer et al (2001), в том числе и автор данной работы. К сожалению, генерация столбцов не позволяет применять вариации метода, отличающиеся строгой сходимостью. Ранее был реализован следующий метод: в ходе решения непрерывной релаксации генерировалось множество столбцов и на этом множестве применялся метод секущих плоскостей. Однако оптимум может требовать других
>s. столбцов.
В 1963 Гилмор и Гомори описали реализацию непрерывной релаксации с округлением для задачи с несколькими типами материала [26]. Они не рассматривали границы комплектности материала, т.е. количество прутков каждого типа было неограниченным. Они установили, что возможность комбинации нескольких длин обеспечивает очень хорошую утилизацию материала (мало отхода). Они отметили, что поведение целевой функции очень слож-но, так как она определяется линейными комбинациями цен материала, и поэтому трудно найти оптимум или доказать его оптимальность с помощью нижней границы (настоящая работа подтверждает оба вывода). Для 1DCSP с несколькими длинами материала литература содержит экспериментальные результаты практически только по эвристикам. Исходя из вышеизложенного, проблема является актуальной.
Целью работы является разработка и исследование математической модели и метода отсечений для решения задачи одномерного раскроя материала различных длин.
Для ее достижения были поставлены и решены следующие задачи:
10 Разработать и исследовать математическую модель задачи 1DCSP для материала различных длин.
Разработать эффективный метод моделирования раскроев (столбцов) при наличии прутков различной длины и сечений Гомори.
Смоделировать критерий оптимальности решения и разработать процедуры проверки оптимальности.
Модифицировать и адаптировать известные методы дискретной оптимизации и применить их для повышения эффективности метода отсечений, в т. ч. критерии доминантности, процедуры построения допустимых решений.
Разработать программное обеспечение на базе предложенного метода. Провести анализ эффективности и других характеристик разработанного алгоритма на основе результатов численных экспериментов и сравнения производительности метода с другими, описанными в литературе.
На защиту выносятся:
Математическая модель задачи одномерного раскроя с несколькими типами прутка с неявной матрицей ограничений;
Критерий оптимальности решения задачи одномерного раскроя материала различных длин;
Вычислительная схема метода отсекающих плоскостей для решения задачи одномерного раскроя материала различных длин;
Специализация основных процедур метода отсекающих плоскостей:
Метод генерации столбцов при наличии сечений;
Метод округления непрерывного решения;
Метод генерации растровых точек для критерия оптимальности;
f Критерий доминантности заготовок в задаче рюкзака;
Конкретизация принципа Никольсона в динамическом программировании для генерирования раскроя материала различной длины;
Модификация прямой стратегии в динамическом программировании;
Компьютерная программа, реализующая разработанный алгоритм;
Численный эксперимент на основе созданного алгоритмического и программного обеспечения.
&
Научная новизна работы.
Новыми в работе являются:
Точный метод отсекающих плоскостей для решения задачи одномерного раскроя материала различных длин, разработанный на базе метода Гомори решения целочисленных задач линейного программирования;
Модель целевой функции с верхней границей, которая позволяет эффективно генерировать столбцы при наличии сечений Гомори (ранее примененный критерий часто вел к неприемлемому времени счета);
Динамический принцип изменения размера остаточной задачи при округлении непрерывных решений (ранее рассматривалась статичная остаточная задача);
Метод моделирования множества линейных комбинаций для критерия оптимальности на основе битовых операций (другие известные методы требуют в общем случае огромный размер памяти);
Критерий доминантности заготовок в задаче рюкзака с верхними границами (ранее был известен только для задачи без верхних границ);
^
12
(} Модификация принципа Никольсона в динамическом программирова-
нии для генерирования раскроя материала различной длины (ранее применялся для задачи без верхних границ);
Критерий доминантности состояний в прямой стратегии динамического
^ программирования.
і і
1 Практическая значимость работы: программная реализация гибри-
дизации метода отсекающих плоскостей и эвристик обладает способностью
і і
| быстрого получения оптимального решения и показала значительные пре-
имущества перед известными эвристическими методами на достаточно ши
роком классе задач, сложность которых значительно выше, чем у средних
прикладных задач. Преимущество перед известными точными методами оче-
^ видно и подтверждено расчетами. Это делает программную реализацию ме-
тода отсекающих плоскостей практически применимой в реальных производственных ситуациях.
Апробация работы. Работа выполнялась в рамках заданий РФФИ,
проекты 99-01-00937, 01-01-00510 и долгосрочного совместного научного ис
следования по проблемам раскроя-упаковки между УГАТУ (кафедра вычис-
*^ лительной математики и кибернетики) и Дрезденским техническим универси-
тетом (институт вычислительной математики). Результаты работы и отдельные ее разделы докладывались и обсуждались на следующих конференциях и семинарах:
XXXXVII Теоретическая конференция молодых ученых "Нефть и газ". Ф Уфа, 1997;
Сибирская конференция по исследованию операций. Новосибирск, 1998;
CSIT-2000, The 2nd International Workshop on Computer Science and
Information Technologies. Ufa, Russia (на англ. яз.);
13
0 The 3rd Siemens Workshop on Applied Discrete Optimization. Wuerzburg,
Germany, 2000 (на нем. яз.);
CSIT-2001, The 3rd International Workshop on Computer Science and
Information Technologies. Ufa, Russia (на англ. яз.);
G? The 24th International Workshop on Discrete Optimization. Lutherstadt
Wittenberge, Germany, 2002 (на англ. яз.);
IFORS 2002 "OR in a globalised, networked world economy". (на англ. яз.);
Конференция "Математическое программирование и приложения". Екатеринбург. ИММ УРО РАН. 2003;
Семинарах кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета;
Семинарах института вычислительной математики Дрезденского технического университета;
Семинаре института математики с вычислительным центром Уфимского научного центра РАН.
^ Публикации
По теме диссертации опубликовано 13 работ, в том числе одна работа в Российском рецензируемом журнале, три работы - в международных рецензируемых журналах, остальное - материалы международных и Российских конференций.
Содержание диссертации
В первой главе приведены классификация задач раскроя-упаковки и постановка задачи, обзор существующих методов решения, схема метода секущей плоскости и примеры работы метода.
14 Во второй главе описывается решение непрерывной релаксации с помощью симплекс-метода, а также уточнение формулировки релаксации с помощью отсечений.
В третьей главе описывается генерация столбцов без сечений и с сечениями, а также критерий доминантности заготовок при генерации столбцов.
Четвертая глава посвящена повышению практической эффективности метода, а именно гибридизации метода секущих плоскостей и эвристик для ускоренного нахождения целочисленных решений. Теоретически конечность метода отсечений гарантирует, что при определенном наборе секущих плоскостей решение непрерывной релаксации станет целочисленным и поэтому допустимым решением основной задачи. Однако еще гораздо раньше в течение процесса можно найти оптимальное решение. В данной главе описывается метод построения целочисленных решений на основе решений непрерывной релаксации и критерий оптимальности целочисленных решений.
В пятой главе описывается реализация ПО и вычислительный эксперимент. Описаны сложности, связанные с конечностью мантиссы и реализован вариант целочисленного симплекс-метода. Исследован эффект расширения задачи остатка и различные показатели алгоритма. Произведено сравнение с наилучшим известным точным алгоритмом для задачи одномерного раскроя с одним типом прутка и с несколькими эвристиками. Сделан графический анализ временного поведения алгоритма. Поведение алгоритма задокументировано на представительном наборе задач средней и большой размерности (100-400 типов заготовок), чтобы дать материал для сравнения другим исследователям.
Классификация методов решения задач раскроя-упаковки
Эвристические — Имитирующие опытного упаковщика, природу и т.п. (итера тивные, локального поиска, эволюционные) - На основе непрерывной (ЛП) релаксации Округление решения ЛП-релаксации (Канторович и Залгаллер 1951, Gilmore k Gomory 1961) Метод отсекающей плоскости — отсечение нецелочисленных решений (Terno Sz Scheithauer et al 1999 для M — 1)
На основе непрерывной (ЛП) релаксации Branch-and-price — перебор путем разделения множества решений ЛП-релаксации (Vance 1994, Degraeve & Peeters 1999, Vanderbeck 1996, V.d.Carvalho 1998 для M = 1) 0
Оптимизационная схема решения метода секущей плоскости (СРА) состоит в выполнении следующих процедур. При опускании требования целочислен-ности в (4) может быть применен симплекс-метод (шаг 1). При этом вычисляется нижняя (ЛП) граница целевой функции. При добавлении сечений она становится точнее, непрерывное решение становится все более близким к целочисленному, при этом облегчается построение эвристического допустимого решения (шаг 2). Тест оптимальности последнего использует ЛП-границу (шаг 3).
В следующей главе описываются секущие плоскости и вопросы конечности алгоритма.
Алгоритм метода секущих плоскостей для задачи одномерного раскроя материала различных длин
Шаг 0 Установить Ь := Ь, к := О и z := со. Шаг 1 Непрерывная релаксация: вычислить оптимальное решение хк Є -К++п+м задачи Zk := min{cTxk : Акхк = bk, хк 0}. (8) (переход к равенству с помощью вспомогательных переменных, fx — количество секущих плоскостей). Zk — нижняя граница для (4). 0 Шаг 2 Округлить хк поэлементно до нижних целых и сформировать из неполу ченных заготовок задачу остатка. Путем эвристического решения задачи остатка и с учетом [хк\ сконструировать допустимое целочисленное решение х 2L\. Если (Fx z, тогда z := cFx. «Ф Шаг 3 Если z равно наименьшей линейной целочисленной неотрицательной комбинации zr цен материала, большей или равной Zk, т.е. м Шаг 4 Сконструировать сечения, добавить их к ( 4 6fc) (этим определяется ( +ibfc+1)), удалить излишние (неактивные) сечения, установить к := к + 1 и перейти к шагу 1.
Начальная ЛП-граница: 814366.(6). После целочисленного округления найдено решение со значением 818000. Добавление 2 сечений к ЛП-релаксации вызвало цикл в симплекс-методе. После антициклического рестарта (см. Вычислительный эксперимент) найдено целочисленное ЛП-решение со значением 814700. Когда трансформация базиса выполняется целочисленным методом (см. Вычислительный эксперимент), то после добавления сечений цикл в симплекс-методе не возникает и сразу находится целочисленное ЛП
Если RP создается, от он вставляется в таблицу так, что все растровые точки остаются отсортированными по невозрастающим / и не убывающим у. Это необходимо, чтобы позже за один проход в каждой группе с равной позицией оставить только один RP, если это вообще точка роста.
Таблица содержит в конце оптимальные значения для всех типов материала, если расчет велся до I — Lmax. Т.е. сложность расчета не зависит от количества типов материала. Принцип Никольсона был применен в [35] для одной динамической шкалы. В данном случае имеются т шкал, и принцип может быть обобщен следующим образом. ,0 При прямом применении forward state strategy (последовательное вычис ление от /і до /то) количество растровых точек растет с каждой следующей функцией fq. Пусть RPM обозначает результирующее множество растровых точек для /т. х
Когда /m/2j посчитана (обозначим соответствующую RPS RPM{), тогда О можно сконструировать вторую динамическую таблицу из оставшихся заготовок (соотв. RPM2). Тогда выполняется в общем случае \RPMi\ \RPM\, і = 1,2, т.е. вычислительные затраты для каждой заготовки из второй половины списка уменьшаются. Эта идея была реализована следующим образом: список заготовок не раз деляется с самого начала, а из общего списка каждая следующая заготовка встраивается в ту из двух таблиц, в которой меньше растровых точек. Та Ф ким образом, создаются встречные оптимизационные процессы. Это можно параллельно запрограммировать. Список заготовок, примененный в каждой таблице, остается отсортированным по невозрастающим отношениям СЦ/ІІ, если общий список был так отсортирован. Для того, чтобы определить максимум f(L) для данной длины прутка ф L, необходим дополнительный проход: f(L) = max {fhicfri) + f2Nic(r2) : П Є RPM i = 1,2, n+r2 L}. (ЗО) (fhic определяется аналогично fq, но с заготовками из г -той половины списка). Потом выбирается лучший тип прутка согласно (24). Динамическая таблица программируется как динамическая цепочка
Решение восстанавливается потом методом ветвей и границ по известной целевой функции с некоторым численным допуском
Динамические уравнения для генерирования карты раскроя
В методе ветвей и границ для генерации столбцов при наличии сечений сохраняется тот же принцип, что и без сечений, а именно лексикографический перебор [25]. Однако порядок заготовок (и соответственно элементов столбцов) должен отражать приблизительную степень влияния заготовок данного типа на целевую функцию (34). Чтобы оценить это влияние, целевая функция можеть быть линейно аппроксимирована путем опускания функции округления в формуле коэффициентов сечений (19). Итак, мы определяем приближенные коэффициенты сечений рекурсивно как Теперь имеется линейность: тіг{а) = YlZ=i а іКг(ег) для всех г, где ег — г-й единичный вектор. Аппроксимирующая целевая функция теперь ЗД = Тл=\ diai + Dr=i dn+r7rr(a) - с{а) = YH=\ di 4 - c(q) (39) где di = di + 2r=idn+rTtr(et). Сортировка заготовок согласно d\fl\ ... dm/lm очень эффективна для поиска хороших решений [42]. 0 3.2.4 Предварительный останов
С большим числом сечений граница (36) становится неточной и доказательство оптимальности очень трудоемким. Практически, при подходящей сортировке быстро находятся хорошие решения, что позволяет остановить поиск. Если найдена карта с негативным RC, то после определенного количества шагов с момента последнего улучшения производится останов. Для конкретной задачи количество шагов до останова может быть недостаточным. Тогда симплекс-метод длится очень долго после тестового рестарта. Поэтому порог периодически удваивается.
Другой случай, когда непрерывный оптимум задачи раскроя уже найден, что становится ясным из сравнения zk и zk l. Исходный текст процедуры ф генерирования находится в приложении. 3.3 Доминантность заготовок Рассмотрим задачу рюкзака dFa — max (40) Ф при lTa L, а Є 2Z%. (41) Пример. L = 100, / = (15,17,19,21), d= (17,17,19,21). Допустим, существует оптимальное решение с «2 0. Тогда установи а\ = а\ + й2 и аг = 0. При этом остается (40) постоянным и (41) выполненным. Вообще: если для заготовок г, j k lj и di dj, (42) тогда заготовка j может быть исключена из задачи. Когда каждая заготовка г, 1 г п имеет верхнюю границу bi, т.е. должно выполняться а Ь, (43) то вторая заготовка может еще быть полезной. Пусть в примере Ь = (5,3,1,1). Допустим, существует оптимальное решение с а 2 = Ьг = 3. Тогда выполняется очевидно а\ = 3, 100 -17-3 т.е. 2 экземпляра первой заготовки еще свободны. Установи а\ = ai+2, о = 1-При этом не меняется (40) и (41), (43) выполнены. Лемма 2. Пусть в задаче (40) с условиями (41) и (43) существует такое j, что для всех і Є Ij в некотором Ij выполняется (42). Тогда при установке новой верхней границы для типа оптимальное значение (40) не меняется.
Доказательство. Допустим, что в каком-нибудь решении а Є Ж j-я компонента превышает Ь у. a,j bj. Но тогда a,j — bj экземпляров заготовки j можно заменить на заготовки типов і Є Ij, при этом значение (40) не ухудшится.
Понятие доминантности может быть расширено на группы заготовок. Алгоритм проверки доминантности Input п Є 2Z+, L Є М+, d, b, І Є Мп, її ... Іп (отсортировано по длине). Output: я , d , b , I , j! Значимые для задачи заготовки. Internal: h Є M+, s Є IRn 11 Sf. Недоминируемая длина прутка для заготовки г. For і = 1 to n do b { = bi\ {J Сохранить комплектности For г = 1 to n do Si = L\ Ц Целый пруток недоминирован For і = n downto 1 do {ed — допуск на двойственные переменные). В последнем цикле в новый массив переносятся только такие заготовки (с измененнными комплектностями), которые имеют свободное пространство (si li), могут улучшить целевую функцию (40) (di ed) и имеют положительную комплектность
При генерировании карты в задачах (24) или (34) рассматриваются несколько прутков. При проверке доминантности должна приниматься наи ф большая длина прутка
Модифицированная трансформация базиса в симплекс-методе
Чтобы иметь возможность работать с неточными числами, приходится рассматривать их с определенным допуском. 6-10 цифр мантиссы из 16 в элементах обратного базиса принимаются верными. При округлении вверх 1.00000001... должно считаться единицей (при генерировании сечений, при оценке целочисленности целевой функции задачи (10) и т.д.). Колебания оптимального значения целевой функции, вызванные числен ными погрешностями (например, в следующих друг за другом итерациях СРА), оказались управляемыми. Это связано с тестом оптимальности непре рывной релаксации. Решение оптимально, если не существует столбца с нега тивным ТКЦФ. Из-за численных погрешностей необходимо сравнивать не с нулем, а с достаточно малой константой — ed. Ее величина зависит от двой ственных переменных, которые вычисляются по формуле cF = СдС гНк, где Ф ев = {cj)jeiB Цены базисных столбцов. Мы умножаем численные погреш ности элементов обратного базиса с этими ценами: ed = Ю-8 тах.{р{ : 1 і М}. Во всех тестах колебание затрагивало только последнюю цифру целевой функции (15). Основная проблема трансформации базиса, вычисление 2x2- детерминанты, осталась проблемой из-за переполнения мантиссы. При умножении к к столбца Ь? матрицы Н с матрицей Н, г-тый элемент результирующего век Ф тора равен hkjap — hkjck, г р, т.е. разность. Если уменьшаемое примерно равно вычитаемому, то происходит потеря точности. Численно благоприятнее умножать трансформированную правую сторону на каждом шаге с матрицей H:b = НкЬ. 0 ф В [23] предложена эвристическая комбинация непрерывной релаксации и точного решения задачи остатка, уже известная для задачи с одним типом прут ка [39]. Обозначим наилучшее известное решение z, начальную ЛП-границу и максимальную цену прутка материала ртах- Авторы отмечают, что разрыв оптимальности z — ZQP ПО отношению к ртах составляет в среднем 30%. В нашем методе, как показывает напр. графический анализ производительности (см. далее), этот разрыв уже на начальных итерациях составляет в худшем случае 12%, а через 100 секунд разрыв z — zLP по отношению к ртах не превосходит 2%, где zLP — наилучшая нижняя граница, усиленная сечениями. Аналогичный вывод был сделан по сравнению с генетическим групповым алгоритмом, реализованным по образцу [22] на кафедре вычислительной математики и кибернетики УГАТУ.
Эксперимент проведен для сравнения генетического группового алгоритма (GGA) и метода секущих плоскостей (СРА). Для проведения эксперимента использовался генератор BPPGEN [45]. Вычисления производились на компьютере Pentium 200ММХ, 32Mb. На решение одного примера отводилось до 10 минут времени. Для каждого класса генерировалось по 100 примеров.
Вычисления проводились для следующих параметров: Длины стержней: Lj ={600;800;1000}; количество предметов: т = 200; нижнее ограничение длины предметов: v\ = min /Lmax = 0.001; 0.05; 0.15; 0.25; верхнее ограничение длины предметов: V2 = maxZj/Lmax = 0.1; 0.2; ...; 0.8; 0.9. Количество стержней каждого типа не ограничено. В таблице 1 показаны средние коэффициенты
Как видно из таблицы, GGA достаточно серьезно уступает методу секущих плоскостей на классах с размерами заготовок от 0,25 до 0,5 и 0,25 до 0,6 размера максимального стержня. Известно, что данные классы трудны для Таблица 1: Сравнение с генетическим алгоритмом: коэффициенты раскроя эвристических алгоритмов, каковым является GGA. На остальных классах алгоритмы показывали примерно одинаковое (при небольшом преимуществе СРА), очень близкое к оптимальному (коэффициенты раскроя в большинстве примеров превышали 99%), решение. Надо отметить, что GGA очень быстро находил неплохое решение, в то время как для СРА на классах с мелкими заготовками требовалось более 5 минут, чтобы найти какое-либо допустимое решение. Поэтому преимущество GGA над СРА, как любой метаэвристики над точным алгоритмом, проявляется при дефиците времени. Результаты с генетическим алгоритмом уступают методу отсечений
Графический анализ производительности
Подход, комбинирующий метод отсечений Гомори и генерацию столбцов, применен к одномерной задаче раскроя с несколькими типами прутка. Вычислительные сложности, возникающие в генерации столбцов при наличии сечений из-за нелинейной зависимости коэффициентов сечений от основных ограничений, успешно решены посредством специальной границы ветвления, стратегии поиска и раннего завершения. Эвристическая верхняя граница для задачи раскроя, а именно процедура округления, значительно улучшена схемой изменения задачи остатка. Для решения самой задачи остатка применен метод SVC. Предложен критерий доминантности заготовок для задачи рюкзака с верхними границами. Подробный вычислительный эксперимент включает анализ чувствительности различных параметров, характеристики алгоритма, графический анализ производительности и сравнение с методом branch-and-price.
Ф В противоположность задаче с одним типом прутка, критерий оптималь ности в рассматриваемой задаче более сложен, что уменьшает эффективность сечений при поиске оптимума. Это делает необходимым дальнейшее исследование качества сечений. Однако кажется трудным использовать структуру задачи для создания сильных специализированных сечений. Однако эффек Л тивность реализации алгоритма, как по количеству оптимально решенных задач, так и по утилизации полезного материала говорит о целесообразности применения алгоритма к двух- и трехмерным задачам.90% примеров со 100 типами заготовок были решены оптимально с лимитом времени в несколько минут. Кроме того, среднее значение разрыва между нижней и верхней границей для нерешенных задач составляет всего несколько процентов наибольшей цены прутка, даже для таких классов, где высокая дискретизация цен материала затрудняет оптимальное решение. Были оптимально решены задачи с количеством типов заготовок до 400.
Сравнение с branch-and-price для случая с единственным типом прутка дало почти одинаковые результаты по среднему времени вычислений. Максимальное время меньше в методе отсечений, а количество итераций намного меньше числа обойденных узлов дерева решений в branch-and-price, что говорит о лучшей направленности поиска. Кроме того, производительность нашей реализации может быть улучшена с помощью коммерческих ЛП-программ (CPLEX, Lindo) для решения ЛП-релаксации. Использование концепции ограниченной задачи, двойственных границ для непрерывного решения и субградиентной оптимизации [18] помогло бы генерировать меньше столбцов, что важно для метода отсечений, где задача генерации столбцов очень сложна.
Кроме того, branch-and-price неэффективен для задач с большим разрывом оптимальности. Задачи с большим количеством типов прутка (М = 8, 16) гораздо легче для разработанного подхода, чем с малым количеством (но больше одного, например М = 2, 4). Решение 39 классов задач из серии с 40 типами заготовок и 5 типами прутка показало, что ЛП-граница имеет различную эффективность в разных классах. В классах с высокой комбинаторной сложностью (все длины заготовок не более 1/3 наибольшей длины прутка) граница очень сильна и сечения никогда не становятся активными. Может быть, это также Ф ждает тезис о слабости сечений Гомори. В других классах ЛП-граница слабая и ее значение должно быть улучшено с помощью сечений. Направления дальнейшей работы: более сильные сечения и границы ветвления при генерации столбцов. Большое значение имеет рассмотрение технологических особенностей раскроя, см. далее Программная реализация гибридизации метода отсекающих плоскостей и эвристик показала значительные преимущества перед используемыми на практике эвристическими методами на широком классе задач распределения одномерного ресурса. Выявлены преимущества на некоторых классах задач перед методом ветвей и границ. Это позволяет в перспективе использовать предложенные методы и программы для расчета оптимального раскроя в производстве. Комплекс внедрен в учебный процесс для иллюстрации и изучения некоторых методов математического программирования
Похожие диссертации на Моделирование и решение задачи одномерного раскроя материала различных длин методом отсекающих плоскостей
