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