RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки // Архив

Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 2018, том 28, выпуск 3, страницы 348–363 (Mi vuu643)

Эта публикация цитируется в 6 статьях

МАТЕМАТИКА

Динамическое программирование в обобщенной задаче «на узкие места» и оптимизация точки старта

А. Г. Ченцовab, А. А. Ченцовb, А. Н. Сесекинba

a Уральский федеральный университет, 620002, Россия, г. Екатеринбург, ул. Мира, 19
b Институт математики и механики им. Н. Н. Красовского УрО РАН, 620990, Россия, г. Екатеринбург, ул. С. Ковалевской, 16

Аннотация: Рассматривается одна «неаддитивная» задача маршрутизации перемещений, являющаяся обобщением известной задачи «на узкие места». Предполагается заданным параметр в виде положительного числа, степень которого определяет вес соответствующего этапа системы перемещений. Варьированием параметра можно сделать доминирующими начальные или, напротив, финальные этапы перемещения. Вариант агрегирования стоимостей с упомянутыми весами соответствует идейно постановке задачи «на узкие места», но открывает возможности исследования новых постановок задач маршрутизации с ограничениями. Предполагается, однако, что постановка осложнена зависимостью стоимостей от списка заданий и включает ограничения в виде условий предшествования. Кроме того, в интересах оптимизации допускается произвольный выбор начального состояния из заданного априори множества. Для построения решения используется аппарат широко понимаемого динамического программирования. Исследуется возможность реализации глобального экстремума с любой степенью точности в условиях, когда множество возможных начальных состояний не является конечным.

Ключевые слова: маршрутная оптимизация, динамическое программирование, оптимизация точки старта.

УДК: 517.6

MSC: 49L20, 90C39

Поступила в редакцию: 06.06.2018

DOI: 10.20537/vm180306



Реферативные базы данных:


© МИАН, 2024