Оптимизация на графах с переменным весом ребер

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

Статья представлена к публикации членом редколлегии: В. В. Рыков