Моделирование и решение задачи одномерного раскроя материала различных длин методом отсекающих плоскостей

• Автор: Белов, Глеб Николаевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Уфа
• Количество страниц: 124 с. : ил

Оглавление

Использованные обозначения

Введение

1 Постановка задачи и схема метода

1.1 Постановка задачи одномерного раскроя материала различных длин

1.2 Классификация методов решения задач раскрояупаковки .

1.3 Схема решения

1.4 Выводы.

5 2 Непрерывная релаксация

2.1 Постановка задачи. Симплексметод с обратной матрицей

2.2 Метод секущих плоскостей на базе непрерывной релаксации . .

2.3 Удаление сечений меры против циклов.
2.4 Генерация сечений
2.5 Выводы.
3 Генерация столбцов
3.1 Генерация столбцов без сечений
3.1.1 Постановка задачи генерирования столбцов
3.1.2 Динамические уравнения для генерирования карты раскроя
3.1.3 Прямая стратегия динамического программирования . .
3.1.4 Принцип Никольсона в динамическом программировании
3.1.5 Расчет решения
3.2 Генерирование столбцов при наличии сечений
3.2.1 Постановка задачи.
3.2.2 Несколько типов прутка
3.2.3 Сортировка заготовок
3.2.4 Предварительный останов.
3.3 Доминантность заготовок.
3.3.1 Проверка доминантности заготовок при наличии сечений
3.4 Выводы
Построение целочисленных решений и тест оптимальности
4.1 Построение целочисленных решений
4.1.1 Округление непрерывного решения
4.1.2 Расширение задачи остатка.
4.2 Метод последовательного уточнения оценок .
4.3 Тест оптимальности целочисленного решения.
4.3.1 Описание задачи.
4.3.2 Генерация растровых точек цен материала.
4.4 Выводы
Вычислительный эксперимент
5.1 Реализация программного обеспечения
5.1.1 Концепция ПО
5.1.2 Модифицированная трансформация базиса в симплексметоде .
5.1.3 Переполнение мантиссы.
5.1.4 Погрешности вычислений. Рестарт.
5.2 Несколько типов прутка сравнение с другими алгоритмами . .
5.3 Генерирование тестовых задач
5.4 Количество задач с сечениями
5.5 Сравнение с методом ЬгапсЬапс1рпсе
5.6 Несколько типов прутка характеристики алгоритма
5 5.7 Графический анализ производительности
5.8 Эталонные результаты
5.9 Управляющие переменные
5. Фиксированные выходные параметры.
р. 5. Целочисленная трансформация базиса
5. Оценка серии т , М 5.
5. Наблюдения относительно свойства МПШР
5. Таблицы в приложении.
5. Восстановление карты посредством ЬгапсЬапбЬоипс.
5. Выводы по тестам и направления дальнейшей работы.
5. Внедрение
6 Заключение
Список использованной литературы


Самые простые — это первый подходящий (First Fit, FF), первый подходящий с упорядочиванием (First Fit Decreasing, FFD) и их вариации. Большего усердия при разработке и исследовании требуют такие методы, как жадный алгоритм и его вариация, метод последовательного уточнения оценок (sequential value correction method SVC, Мухачева и Залгаллер []), эволюционные алгоритмы, методы частичного перебора. Очень много эвристических схем подключают непрерывную релаксацию с генерацией столбцов для вычисления нижней границы и получения округленного решения. Существуют различные оценки качества эвристик, например вероятностные характеристики или доказательства асимптотической точности на определенном классе задач (см. Гимади и Залюбовский [3]). Долгое время применение точных методов для 1DCSP не было успешным. Однако в последние годы в связи со значительным развитием вычислительной техники, а также из-за приспособления точных методов к задаче (например, специфические методы ветвления) в практическом применении точных методов достигнуты значительные успехи. В большинстве случаев эти методы — модификации метода ветвей и границ. Наиболее успешен метод ветвей и границ с генерацией столбцов, т. Ветвление производится посредством добавления ограничений (разбиения множества решений) в непрерывной релаксации. Для задачи Bin Packing (требуемые комплектности всех заготовок равны 1) разработаны специальные границы целевой функции и модификации метода ветвей и границ [, ]. Другой распространенный в дискретной оптимизации точный метод — это метод секущих плоскостей (cutting plane algorithm, CPA). Секущие плоскости (отсечения) описывают выпуклую оболочку целочисленных решений. Последний часто может быть найден с помощью эвристических процедур округления непрерывного решения. Однако добавление отсечений в модели с генерацией столбцов не так просто. Дело в том, что при генерации новых столбцов приходится учитывать коэффициенты отсечений для этих столбцов. Коэффициенты нелинейно зависят от предыдущих ограничений. Эту проблему впервые решили БсЬе^Ьаиег et а1 (), в том числе и автор данной работы. К сожалению, генерация столбцов не позволяет применять вариации метода, отличающиеся строгой сходимостью. Ранее был реализован следующий метод: в ходе решения непрерывной релаксации генерировалось множество столбцов и на этом множестве применялся метод секущих плоскостей. Однако оптимум может требовать других столбцов. В Гилмор и Гомори описали реализацию непрерывной релаксации с округлением для задачи с несколькими типами материала []. Они не рассматривали границы комплектности материала, т. Они установили, что возможность комбинации нескольких длин обеспечивает очень хорошую утилизацию материала (мало отхода). Они отметили, что поведение целевой функции очень сложно, так как она определяется линейными комбинациями цен материала, и поэтому трудно найти оптимум или доказать его оптимальность с помощью нижней границы (настоящая работа подтверждает оба вывода). Для ШСБР с несколькими длинами материала литература содержит экспериментальные результаты практически только по эвристикам. Исходя из вышеизложенного, проблема является актуальной. Целью работы является разработка и исследование математической модели и метода отсечений для решения задачи одномерного раскроя материала различных длин. Разработать и исследовать математическую модель задачи ШСБР для материала различных длин. Разработать эффективный метод моделирования раскроев (столбцов) при наличии прутков различной длины и сечений Гомори. Смоделировать критерий оптимальности решения и разработать процедуры проверки оптимальности. Модифицировать и адаптировать известные методы дискретной оптимизации и применить их для повышения эффективности метода отсечений, в т. Разработать программное обеспечение на базе предложенного метода. Провести анализ эффективности и других характеристик разработанного алгоритма на основе результатов численных экспериментов и сравнения производительности метода с другими, описанными в литературе.