Том 6, серия 2, номер 1, 1999 г., Стр. 3-11

УДК 519.87+519.854.33
И. П. Вознюк
Задача размещения на сети с ограниченными пропускными способностями коммуникаций

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

Вознюк И. П. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 14 апреля 1998 г.
Исправленный вариант — 13 февраля 1999 г.