Решение макси-суммной задачи размещения на сети с ограничением на транспортные затраты

Рассматривается задача оптимального размещения объекта на неориентированной взвешенной сети. Каждому ребру приписан положительный вес, а вершинам  — два положительных параметра. Первый параметр отражает требование размещать объект как можно ближе к вершине, а второй  — как можно дальше. Задано ограничение на суммарное взвешенное расстояние от объекта до вершин с учётом первого параметра. Необходимо найти допустимые места размещения объекта на рёбрах сети с максимальной суммой взвешенных расстояний от них до вершин с учётом второго параметра (локальные экстремумы). Предложен полиномиальный алгоритм поиска всех локальных экстремумов на рёбрах сети.