Аннотация:
Рассматривается экстремальная задача маршрутизации, ориентированная на инженерные приложения в машиностроении. Имеется в виду известная задача управления инструментом при листовой резке деталей на машинах с ЧПУ. Используется математическая модель, включающая систему мегаполисов (непустых конечных множеств) и функции стоимости, зависящие от списка заданий. Мегаполисы конструируются на основе дискретизации эквидистант, отвечающих контурам деталей, а зависимость от списка заданий возникает из соображений, связанных с учетом ограничений динамического характера, возникающих по мере выполнения заданий. Среди всех ограничений выделяются условия предшествования (предваряющая резка внутренних контуров детали в сравнении с внешним, более ранняя резка крупных деталей и т.д.). Рациональный учет условий предшествования позволяет в определенной степени снизить сложность вычислений при использовании широко понимаемого динамического программирования (ДП) в реализации, развивающей схему Р.Беллмана. Данный подход позволяет принципиально решать задачу оптимизации комплексов, включающих начальное состояние (точку старта), способ нумерации мегаполисов в порядке их посещения и конкретную траекторию процесса. Для задачи, осложненной зависимостью терминальной функции от начального состояния, используется декомпозиционный алгоритм, позволяющий в существенной части процедуры применять единую (для всех начальных состояний) схему ДП. Оптимальный алгоритм на основе ДП реализован в виде программы для ПЭВМ; проведен вычислительный эксперимент.
Ключевые слова:
маршрутная задача, динамическое программирование, условия предшествования.
Образец цитирования:
A. G. Chentsov, P. A. Chentsov, “The routing problems with optimization of the starting point: dynamic programming”, Изв. ИМИ УдГУ, 54 (2019), 102–121
\RBibitem{CheChe19}
\by A.~G.~Chentsov, P.~A.~Chentsov
\paper The routing problems with optimization of the starting point: dynamic programming
\jour Изв. ИМИ УдГУ
\yr 2019
\vol 54
\pages 102--121
\mathnet{http://mi.mathnet.ru/iimi385}
\crossref{https://doi.org/10.20537/2226-3594-2019-54-08}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000512131100008}
\elib{https://elibrary.ru/item.asp?id=41435144}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/iimi385
https://www.mathnet.ru/rus/iimi/v54/p102
Эта публикация цитируется в следующих 5 статьяx:
А. Г. Ченцов, П. А. Ченцов, “Динамическое программирование в задаче маршрутизации: декомпозиционный вариант”, Вестник российских университетов. Математика, 27:137 (2022), 95–124
А. Г. Ченцов, П. А. Ченцов, “Экстремальная двухэтапная задача маршрутизации и процедуры на основе динамического программирования”, Тр. ИММ УрО РАН, 28, № 2, 2022, 215–248
А. Г. Ченцов, А. А. Ченцов, “Об одной задаче маршрутизации, ориентированной на проблему демонтажа радиационно опасных объектов”, Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 15:3 (2022), 83–95
A.G. Chentsov, P.A. Chentsov, “To the application of two-stage dynamic programming in the problem of sequential visiting of megalopolises”, Procedia Structural Integrity, 40 (2022), 105
А. Г. Ченцов, А. А. Ченцов, А. Н. Сесекин, “О задаче последовательного обхода мегаполисов с условиями предшествования и функциями стоимости с зависимостью от списка заданий”, Тр. ИММ УрО РАН, 26, № 3, 2020, 219–234; A. G. Chentsov, A. A. Chentsov, A. N. Sesekin, “On the Problem of Sequential Traversal of Megalopolises with Precedence Conditions and Cost Functions Depending on a List of Tasks”, Proc. Steklov Inst. Math. (Suppl.), 315, suppl. 1 (2021), S67–S80
Цитирование в формате AMSBIB
Обратная связь: