|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
Научные статьи
Динамическое программирование в задаче маршрутизации: декомпозиционный вариант
А. Г. Ченцовab, П. А. Ченцовba a ФГБУН «Институт математики и механики им. Н. Н. Красовского» Уральского отделения Российской академии наук
b ФГАОУ ВО "Уральский федеральный университет им. первого Президента России Б.Н. Ельцина"
Аннотация:
Исследуются вопросы применения аппарата динамического программирования (ДП) в задаче маршрутизации с ограничениями и функциями стоимости, допускающими зависимость от списка заданий. Предполагается заданным бинарное разбиение множества заданий, т. е. выделены две группы заданий; задания первой группы должны быть выполнены раньше, чем начнется выполнение заданий второй группы. В каждой из групп могут присутствовать условия предшествования. Данная постановка может быть связана, в частности, с вариантом листовой резки зонами на машинах с ЧПУ, где две вышеупомянутые группы заданий образуют зоны, намеченные на этапе раскроя. В общем случае для построения оптимального решения применяется двухэтапный вариант ДП. Стыковка этапов осуществляется посредством отождествления терминальной компоненты критерия предваряющей задачи с функций экстремума финальной задачи. Склеивание оптимальных решений предваряющей и финальной задач доставляет, как показано в статье, оптимальное решение совокупной задачи. На основе теоретических конструкций построен алгоритм, реализованный на ПЭВМ; проведен вычислительный эксперимент.
Ключевые слова:
динамическое программирование, маршрут, условия предшествования.
Поступила в редакцию: 01.12.2021
Образец цитирования:
А. Г. Ченцов, П. А. Ченцов, “Динамическое программирование в задаче маршрутизации: декомпозиционный вариант”, Вестник российских университетов. Математика, 27:137 (2022), 95–124
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vtamu249 https://www.mathnet.ru/rus/vtamu/v27/i137/p95
|
Статистика просмотров: |
Страница аннотации: | 125 | PDF полного текста: | 34 | Список литературы: | 15 |
|