Задача размещения на сети с ограниченными пропускными способностями коммуникаций

Рассмотрена задача о наилучшем размещении пунктов производства в вершинах сети с ограниченными пропускными способностями коммуникаций. Для решения задачи на древовидной сети предложен алгоритм динамического программирования с временем работы $T=O(n^3b^2)$ и требуемой памятью $\Pi=O(n^2b)$, где $n$ – число вершин сети, $b$ – максимальный объем спроса. Если сеть является цепью, то алгоритм решения задачи имеет оценки $T=O(n^3)$, $\Pi=O(n)$. В общем случае реализован метод ветвей и границ. Приведены результаты численного эксперимента. Ил. 1, библиогр. 9.