О существовании целочисленного решения релаксированной задачи Вебера для древовидной сети

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