Методы математической теории оптимального управления в исследовании экстремальных задач геометрии

• Автор: Красноженов, Григорий Григорьевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Тверь
• Количество страниц: 262 с.

Оглавление.
Введение.
Основные этапы развития и классификация задач раскроя упаковки 8 Классификация задач раскроя упаковки

Особенности задач нерегулярного фигурного раскроя

Последовательность решения задачи размещения.

Актуальность

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