Введение
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
