<< prev | ^up^ | next >>

3.6. Задача распределения потоков.

        3.6.1.Постановка задачи.

Задана структура сети G=(X,E), пропускные способности всех каналов  и матрица требований . Надо распределить потоки по всем каналам и найти такой вектор многопродуктового потока , совместимый с набором пропускных способностей, для которого   

            (3.24)

при условии

                                               (3.25)

Выше было доказано, что функция   вогнута по переменным . Используем это свойство для построения алгоритма. Для удобства перейдём от целевой функции вида (3.24) к следующей

                     (3.26)

которая тоже вогнута, а потом к эквивалентной задаче минимизации

                (3.27)

Учитывая, что вероятности , получаем, что . Кроме того, очевидно, что функция  будет выпуклой по переменным . Это свойство позволяет применить следующий метод отклонения потоков, или модифицированный метод отклонения потоков.

3.6.2.Алгоритм  решения задачи РП

Алгоритм А2 состоит из начального этапа и  конечного числа однотипных итераций.

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

k-тая итерация:

Пусть есть поток

1. Найдём условные длины всех дуг:

            

2. Находим кратчайшие пути  в метрике  для всех пар узлов (i,j) .

3. Распределяем все потоки по кратчайшим путям и находим общий поток по кратчайшим путям .

4. Рассчитываем  стоимостной показатель для потока V(k):

                            

    и для  потока :

                            

5. Если , то конец. Данный поток  не может быть улучшен, иначе на шаг 6.

6. Построим выпуклую комбинацию потоков

                 

7. Находим значение критерия

                    

 и находим такое , при котором . Для этого используем метод Фибоначчи или "Золотого сечения".

.

8. Находим  и, приравнивая k=k+1, переходим к шагу 1 (k+1)-ой итерации.

Начальный этап.

Допустим, что задан суммарный внешний поток . Вводим масштабный коэффициент  так, чтоб  равнялось интенсивности потока, с которым мы имеем дело при данном значении .

1. Приравниваем  и будем считать, что  решение задачи распределения потоков по кратчайшим путям в сети с условными длинами . На этом шаге направляем весь поток  по сети. Обозначим через  поток в канале (r,s). Приравниваем n=0.

2. Пускай .

 Если , то приравниваем , STOP,  - допустимый начальный поток и перейти к основной части.

 Если , то приравниваем , где - необходимый параметр точности. Иначе на шаг 3.

3. Приравниваем  - это реализуемый многопродуктовый поток, который передаёт трафик с суммарной интенсивностью внешнего потока .

4. Находим условные длины путей:

                 

5. Находим кратчайшие пути  в метрике  и определяем поток по кратчайшим путям .

Дальше находим оптимальное значение  такое, что  минимизирует . Если n=0, то перейти к шагу 7, иначе к шагу 6.

6. Если  и , где  и  соответствующим образом выбранные допуски, то конец. Задача не имеет решения при выбранных допусках   и . Иначе перейти к шагу 7.

7. Приравниваем n=n+1 и переходим к шагу 2.