7.3 Алгоритмы решения задачи выбора оптимальных потоков в сети

7.3.1 Альтернативная маршрутизация

В случае альтернативной маршрутизации задача выбора оптимальных маршрутов относится к классу многопродуктовых задач с выпуклой целевой функцией и выпуклым множеством ограничений. Следовательно, существует единственный локальный минимум данной задачи, являющийся глобальным минимумом, для нахождения которого разработано достаточно большое число вычислительных методов [156,190,209,269].

Наиболее известным методом решения данной задачи является метод отклонения (девиации) потока, предложенный в работе [190]. Данный алгоритм является частным случаем так называемого метода Франка-Вольфе [189] для решения более общих задач нелинейного программирования с выпуклым множеством ограничений.

Доказано [190], что метод отклонения потока в пределе уменьшает значение целевой функции до минимума, хотя по мере приближения к оптимуму скорость сходимости существенно замедляется.

Алгоритм отклонения потока опирается на следующие два свойства оптимального решения задачи [190,209].

Свойство 1. Множество многопродуктовых потоков в линиях связи является выпуклым многогранником, крайними точками которого являются так называемые «экстремальные» потоки, определяемые в соответствии с принципом кратчайших маршрутов. Данный принцип состоит в том, что в качестве оптимальных маршрутов для каждой пары узлов «источник - адресат рассматриваются кратчайшие маршруты, вычисляемые при произвольном назначении «весов» линий связи. Каждое такое назначение соответствует некоторому «экстремальному» потоку и наоборот. В работе [190] показано, что любой многопродуктовый поток в линиях связи может быть представлен, как выпуклая комбинация «экстремальных» потоков.

Свойство 2. Для заданного множества многопродуктовых потоков в линиях связи определим «вес» линии связи как частот производную средней задержки по переменной то есть

Пусть - поток по кратчайшим маршрутам, определенным в соответствии с «весами» Пусть далее, выпуклая комбинация минимизирующая функцию . Если , то оптимальный поток.

Справедливость выбора «весов» и сходимость алгоритма доказываются нижеследующими рассуждениями.

Пусть: - оптимальное решение. Это означает, что любое отклонение от ведет к увеличению целевой функции Т, т. е. для любого отклонения относительно такого, что - допустимый многопродуктовый поток выполняется неравенство:

Если выпуклая комбинация , где - поток по кратчайшим маршрутам, определенным в соответствии с некоторыми «весами» , то

Рассмотрим разность: . Для имеем:

Тогда, из неравенства (7.18) следует: мм

Или:

причем в точке оптимума неравенство (7.21) переходит в равенство. Таким образом, для того чтобы в результате итераций поток приближался к оптимальному решению, необходимо минимизировать величину , где поток по кратчайшим маршрутам, определенным в соответствии с «весами»

Ниже предлагается модифицированная версия алгоритма отклонения потока.

Описание алгоритма

Шаг 1. Определить «веса» линий связи инициализировать потоки в линии связи

Шаг 2. Используя «веса» линий связи определить кратчайшие пути между всеми парами узлов «источник - адресат». Для нахождения кратчайших путей в данном случае наиболее подходящим является алгоритм Флойда [182].

Шаг 3. Распределить потоки по кратчайшим путям:

Шаг 4. Вычислить:

Шаг 5. Положить: .

Шаг 6. Положить: где: .

Шаг 7. Пересчитать потоки в линиях связи:

Шаг 8. Определить «веса» линий связи и инициализировать потоки по кратчайшим путям

Шаг 9. Используя «веса» линий связи определить кратчайшие пути между всеми парами узлов «источник - адресат».

Шаг 10. Распределить потоки по кратчайшим путям:

Шаг 11. Найти величину минимизирующую функцию:

при условии выполнения ограничения (7.13).

Поиск величины можно осуществить любым из известных методов одномерного поиска, например, методом Фибоначчи. Ограничение (7.13) легко добавить в реализацию метода одномерного поиска: если для некоторого значения , то достаточно положить .

Шаг 12. Выполнить отклонение (девиацию) потока на величину

Шаг 13. Вычислить:

если , то допустимых решений нет;

если , то получено оптимальное решение с заданной точностью .

Иначе:

1) положить: Том ;

2) если то перейти к шагу 6; иначе перейти к шагу 8.

По сравнению с исходным описанием [190,209], алгоритм объединяет в себе шаги построения начального допустимого потока (шаги 1 - 14) и собственно задачи минимизации средней задержки (шаги 8 -14).

Для определения множества оптимальных маршрутов и долей потоков от входного потока можно использовать модификацию алгоритма, предложенную в работе [116].

В заключение остановимся на теоретической трудоемкости алгоритма. Данная трудоемкость определяется шагами 2 и 9, на которых производится поиск кратчайших путей между всеми парами узлов. Для алгоритма Флойда теоретическая трудоемкость составляет следовательно, трудоемкость алгоритма отклонения потока .