Метод исключения ветвей при выпуклой функции стоимости

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

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

Оптимизацию топологии сети путем исключения линий можно проводить и в том случае, когда зависимость между стоимостью линии и ее пропускной способностью задается выпуклой функцией. На самом деле существует ограниченный набор возможных пропускных способностей для линий связи, и их стоимости образуют возрастающую ступенчатую функцию. Заменив для удобства анализа эту кривую непрерывной выпуклой функцией, можно применить метод девиации потоков для исключения линий из сильносвязной сети. При этом не следует забывать требований минимальной связности сети и нарушать ее удалением слишком большого числа линий. Такой метод оптимизации топологии сетей известен под названием "метод исключения ветвей при выпуклой функции стоимости". Установлено, что данный метод дает достаточно хорошие результаты, однако порождаемые им топологии сильно зависят от вида функции “стоимость - пропускная способность”.