Рассмотрена важная для развития теории и практики задача проектирования сети минимальной стоимости, которая продолжает функционировать при выходе из строя отдельных ее компонент. Число ограничений в модели с потоковыми переменными 0 или 1 экспоненциально выражается от числа вершин. Показано, что LP-релаксация этой задачи NP-полная. Для ряда случаев доказано, что решения соответствующих LP-релаксаций можно найти с помощью полиномиального алгоритма. Предложены эффективные алгоритмы вычисления нижней и верхней оценок для двухсвязной задачи Штейнера. Для ее решения применяется алгоритм ветвей и границ и приведены результаты численных экспериментов.

Індекс рубрикатора НБУВ: В173.112 + З813.1

Рубрики:

Дискретне програмування

Моделювання систем

Шифр НБУВ: Ж26990 Пошук видання у каталогах НБУВ 

---

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"