|
Статьи автора
|
В данной статье задачи оптимизации трасс, возникающие в САПР линейных сооружений, классифицируются как вариационные и сводятся к минимизации функционалов при
наличии ряда ограничений на вид и параметры искомой экстремали. Искомое проектное
решение независимо от вида сооружения (железные и автомобильные дороги, трубопроводы различного назначения, каналы оросительной сети и др.) представляет собой сплайн,
то есть плоскую кривую, состоящую из элементов заданного вида. В отличие от задач,
рассматриваемых в теории сплайнов, возможные границы элементов и даже их число
не известно. Проектируемый сплайн обладает рядом других особенностей, что не позволяет использовать методы нелинейного программирования. В импортных САПР линейных
сооружений и их российских аналогах проектные решения тем или иным способом назначаются проектировщиками. Предложенный отечественными исследователями альтернативный подход, принятый в данной статье, состоит в переходе к компьютерной выработке
проектных решений на основе математических моделей, алгоритмов оптимизации и проектирующих программ. Излагается новый алгоритм аппроксимации последовательности
точек на плоскости сплайном, состоящим из отрезков прямых, клотоид и окружностей, как
это требуется при проектировании трасс дорог и других линейных сооружений.
Читать дальше...
В данной статье рассматриваются прикладные задачи, для решения которых ранее предлагался метод динамического программирования, разработанный Р. Беллманом в середине прошлого века. Этот метод, основанный на принципе оптимальности и вытекающих из него рекуррентных уравнениях, позволил свести решение многих сложных прикладных задач к решению последовательности более простых однотипных задач. К настоящему времени с помощью динамического программирования решены многие практически важные задачи. Однако при решении задач большой размерности, особенно при разработке систем, в которых алгоритм динамического программирования встроен в многократно повторяющийся цикл расчётов, время счёта оказывается неприемлемо велико даже с учётом мощностей современных компьютеров. Проблема повышения эффективности динамического программирования продолжает оставаться актуальной. В этом состоит цель настоящей работы. Установлено, что возможны различные реализации динамического программирования при решении одних и тех же прикладных задач. В статье анализируются возможности повышения эффективности применения динамического программирования при детальном учёте специфических особенностей прикладных задач, из которых некоторые допускают получение рекуррентных формул для вычисления оптимальной траектории на основе принципа оптимальности Р. Беллмана без перебора вариантов. Показано, что многие прикладные задачи, для решения которых предлагался метод динамического программирования с отбраковкой вариантов путей, приводящих в конкретное состояние, допускают дополнительно и отбраковку бесперспективных состояний в процессе счёта. Это резко повышает эффективность динамического программирования как с точки зрения используемого объёма памяти, так и с точки зрения времени счёта. Это утверждение основано на использовании специально разработанных экспериментальных программ для выполнения расчётов с целью оценки эффективности нового алгоритма применительно к решению практических задач как однокритериальных, так и двухкритериальных. Приводятся примеры таких задач и соответствующий алгоритм их решения. Читать дальше...
Данная статья является продолжением статьи, опубликованной в № 1 журнала «Прикладная информатика» в 2019 году [1]. В ней задачи компьютерного проектирования трасс различных линейных сооружений (новые и реконструируемые железные и автомобильные дороги, трубопроводы различного назначения, каналы и др.) рассматриваются с единых позиций – как задачи аппроксимации последовательности точек на плоскости гладкой кривой, состоящей из элементов заданного вида, т. е. сплайном. Принципиальное отличие от других задач аппроксимации, рассматриваемых в теории сплайнов и ее приложениях, состоит в том, что границы элементов сплайна и даже их число неизвестны. Поэтому предложена двухэтапная схема поиска решения. На первом этапе с помощью динамического программирования определяется число элементов сплайна и их параметры. Для некоторых задач этот этап является единственным. В более сложных случаях результат первого этапа используется как начальное приближение для оптимизации параметров сплайна с помощью нелинейного программирования. Другим осложняющим обстоятельством является наличие многочисленных ограничений на параметры сплайна, которыми учитываются проектные нормативы и условия строительства и последующей эксплуатации сооружения. В статье рассмотрены особенности математических моделей соответствующих проектных задач. Для сплайна, состоящего из дуг окружностей, сопрягаемых отрезками прямых, используемого в проектировании продольного профиля как новых, так и реконструируемых железных и автомобильных дорог и трубопроводов, построена математическая модель и использован нестандартный алгоритм решения задачи нелинейного программирования с учетом структурных особенностей системы ограничений. В отличие от стандартных алгоритмов нелинейного программирования используется построение базиса в нуль-пространстве матрицы активных ограничений и его модификация при изменении набора активных ограничений. При этом для поиска направления спуска на каждой итерации не требуется решение вспомогательных систем уравнений вообще. Рассмотрены два варианта организации итерационного процесса оптимизации: спуск по группам переменных при наличии участков независимого построения направления спуска и традиционное изменение всех переменных в одной итерации. Читать дальше...
|
