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