Многоэтапное динамическое программирование в задачах маршрутизации с ограничениями

Рассматривается задача о последовательном обходе мегаполисов с условиями предшествования и функциями стоимости, допускающими зависимость от списка заданий. Предполагается, что все множество заданий разбито в сумму непустых подмножеств (групп); требуется последовательно решать частичные задачи о посещении мегаполисов в каждой из групп. Очередность посещения самих групп задана априори. Предполагается, что условия предшествования общей задачи локализуются в упомянутых группах. Постановка ориентирована на инженерную задачу управления инструментом при фигурной листовой резке деталей зонами на машинах с ЧПУ. В качестве основного метода используется динамическое программирование в условиях декомпозиции, когда оптимальные процедуры реализуются для каждой из частичных задач в отдельности, после чего осуществляется специальная склейка полученных решений. Тем самым решается вопрос о декомпозиции исходной «большой» задачи в систему частичных задач умеренной размерности. На основе теоретических конструкций построен работоспособный алгоритм, реализованный на ПЭВМ. Приведено решение модельных примеров.