Resumo

Рассматривается экстремальная задача маршрутизации, ориентированная на инженерные приложения в машиностроении. Имеется в виду известная задача управления инструментом при листовой резке деталей на машинах с ЧПУ. Используется математическая модель, включающая систему мегаполисов (непустых конечных множеств) и функции стоимости, зависящие от списка заданий. Мегаполисы конструируются на основе дискретизации эквидистант, отвечающих контурам деталей, а зависимость от списка заданий возникает из соображений, связанных с учетом ограничений динамического характера, возникающих по мере выполнения заданий. Среди всех ограничений выделяются условия предшествования (предваряющая резка внутренних контуров детали в сравнении с внешним, более ранняя резка крупных деталей и т.д.). Рациональный учет условий предшествования позволяет в определенной степени снизить сложность вычислений при использовании широко понимаемого динамического программирования (ДП) в реализации, развивающей схему Р.Беллмана. Данный подход позволяет принципиально решать задачу оптимизации комплексов, включающих начальное состояние (точку старта), способ нумерации мегаполисов в порядке их посещения и конкретную траекторию процесса. Для задачи, осложненной зависимостью терминальной функции от начального состояния, используется декомпозиционный алгоритм, позволяющий в существенной части процедуры применять единую (для всех начальных состояний) схему ДП. Оптимальный алгоритм на основе ДП реализован в виде программы для ПЭВМ; проведен вычислительный эксперимент.
Título traduzido da contribuiçãoМаршрутная задача с оптимизацией стартовой точки: динамическое программирование
Idioma originalEnglish
Páginas (de-até)102-121
Número de páginas20
RevistaИзвестия Института математики и информатики Удмуртского государственного университета
Volume54
DOIs
Estado da publicaçãoPublished - 2019

ASJC Scopus subject areas

  • Mathematics(all)
  • Computational Theory and Mathematics

WoS ResearchAreas Categories

  • Mathematics

GRNTI

  • 27.00.00 MATHEMATICS

Level of Research Output

  • VAK List

Impressão digital

Mergulhe nos tópicos de investigação de “THE ROUTING PROBLEMS WITH OPTIMIZATION OF THE STARTING POINT: DYNAMIC PROGRAMMING“. Em conjunto formam uma impressão digital única.

Citar isto