3.7.Задача ВПС РП

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

Задано: структура сети , матрица требований , набор пропускных способностей каналов связи и соответствующих удельных стоимостей каналов связи . Необходимо найти такое распределение потоков и соответствующие пропускные способности всех каналов связи , при которых

(3.28)

при ограничении

(3.29)

и условии, что многопродуктовый поток, совместимый с матрицей .

3.7.2.Алгоритм решения ВПС РП.

Предложенный алгоритм А3 использует многократное решение комбинации задач ВПС РП. Он состоит из начального этапа и конечного числа однотипных итераций

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

1. В качестве метрики используем длины всех каналов связи

2. Определяем кратчайшие пути в сети с выбранной метрикой и находим начальный поток по кратчайшим путям.

3. Решаем задачу ВПС по критерию при ограничении и находим начальные пропускные способности всех каналов связи .

Переходим к 1-ой итерации.

Пусть уже проведено k итераций и найден некоторый поток в сети и соответствующие ему пропускные способности всех каналов .

(k+1)-а итерация.

1. Решаем задачу РП при заданных пропускных способностях и находим такое распределение потоков , которое обеспечивает .

2. При новом распределении потоков решаем задачу ВПС по критерию при ограничении и находим новые оптимальные значения пропускных способностей всех каналов связи .

3. Вычисляем новое значение критерия . Сравниваем и . Если , то переходим к шагу 1 (k+1)-ой итерации, иначе конец работы алгоритма. Распределение потоков и пропускные способности найдены.

3.7.3.Алгоритм нахождения кратчайших путей и расчёта трафиков.

В процессе работы алгоритмов ВПС РП и нахождения максимального потока в сети при отказах многократно используется алгоритм нахождения кратчайших путей и расчёта информационных потоков (трафиков) в многосвязной сети.

Пусть имеем многосвязную коммуникационную сеть, которая задана в виде графа G(X,E),где -множество вершин графа,E={(i,j)}-множество его ребер. Будем считать, что при нескольких маршрутах передачи информации от x_i к x_j она всегда передаётся по пути минимальной стоимости.

Необходимо рассчитать параметры сети G(X,E): такие маршруты передачи информации и информационные потоки в каждом канале f_rs, ,при которых общая стоимость информации будет минимальной, при этом задана матрица требований .

Исходные данные:

матрица смежности ,где ,

матрица удельных стоимостей передачи информации .

В процессе работы алгоритма используются такие рабочие матрицы:

-матрица удельных стоимостей передачи информации из x_i в x_j по пути минимальной стоимости (если b_ij=1,то a_ij=c_ij), -матрица минимальных маршрутов по сети, где m_ij=r -вершина, смежная с x_j на пути , -искомая матрица информационных потоков (или трафиков) в сети, где f_ij-суммарный трафик, который передаётся по каналу связи (i,j).

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

Алгоритм состоит из конечного числа однотипных итераций, в ходе которых строят и уточняют матрицы A(k),M(k).

1-я итерация.

1.Определяем матрицу

2.Заполняем матрицу маршрутов М(1),в соответствии с соотношением

Таким образом в результате 1-ой итерации рассчитаны характеристики сети для маршрутов длины 1.

2-я итерация.

Определяем минимальные маршруты длиной=2 и рассчитываем А(2),М(2).

1.Просматриваем i-тую строку матрицы А(1),i=1,2... и определяем

(3.30)

2.Если a_ij(1)=a_ij(2),то m_ij(2)=m_ij(1) и приравнивая j=j+1,переходим к рассмотрению следующего элемента i-той строки.

Если ,то меняем элемент m_ij в матрице М:

m_ij(2)=m_sj(1) (3.31)

3.Меняем i от 1 до n и выполняем шаг 2 со всеми строками матрицы А(1).

4.Если А(2)=А(1) и М(2)=М(1) и в матрице нет пустых элементов, то конец работы алгоритма, иначе переходим к следующей итерации.

Пусть проведено (k-1) итераций в ходе которых построены матрицы A(k-1),M(k-1).

В ходе выполнения k-той итерации строим A(k),M(k), где M(k)-маршрутная матрица, которая содержит минимальные пути длиной не более 2(k-1) (по количеству каналов).

1.Просматриваем i-тую строку матрицы A(k-1) и определяем a_ij(k):

(3.32)

2.Если a_ij(k)=a_ij(k-1),то m_ij(k)=m_ij(k-1) приравнивая j=k+1 переходим к рассмотрению следующего элемента i-той строки.

Если ,то меняем элемент m_ij в маршрутной матрице M(k-1) .Меняя i от 1 до n,шаг 2 повторяем со всеми строками матрицы A(k-1).

3.Если A(k)=A(k-1) и M(k)=M(k-1) и в матрице M(k) нет пустых элементов, то конец работы алгоритма, матрица M(k)=M-матрица кратчайших путей, а A(k)=A-соответствующая ей матрица длин этих путей.

Иначе переходим к k+1-й итерации.

Итак, допустим, что построена маршрутная матрица М. Покажем, как при помощи её можно найти кратчайший путь между произвольной парой узлов (i,j).

1.Рассмотрим элемент m_ij. Если m_ij=i, то конец ={i-j}.Допустим, что m_ij=s₁.

2.Находим в матрице М элемент .Пусть он равняется =s₂.

3.Если s₂=i, то конец работы алгоритма, искомый путь ={i-s₁-j}.Иначе переходим к шагу 2, приравнивая s₁=s₂.

Допустим, что через k итераций получен элемент .Тогда кратчайший путь ={i-s_k-s_k-1...-s₂-s₁-j}.

Теперь можно рассчитать матрицу информационных потоков по кратчайшим путям. Алгоритм расчета потоков состоит из k=n(n-1) итераций.

1-я итерация.

1.Выбираем 1-й элемент h₁₂ из матрицы Н.

2.Находим кратчайший путь по матрице М.

3.Тогда

Пусть уже проведено (k-1) итераций и определён вектор F(k-1).

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

1.Из матрицы Н выбираем следующее требование, ещё не распределённое по сети. Пусть это .

2.Определяем кратчайший маршрут .

3.Пересчитываем величину суммарного трафика на каналах маршрута :

4. Проверка условия k=n(n-1). Если да, то конец, иначе k=k+1 и переход на шаг 1 (k+1)-й итерации.

Пример 1.

Рассмотрим задачу нахождения кратчайших путей и потоков по кратчайшим путям для сети, приведенной на рис. 1. На дугах (i,j) сети указаны условные стоимости передачи С_ij, причём C_ij=C_ji. Матрица требований в передаче информации Н приводится ниже.

рис. 1.

i\j 1 2 3 4 5

1 x 13 11 7 9

2 6 x 6 4 8

H= 3 5 4 x 6 3

4 6 14 12 x 15

5 1 6 7 3 x

i\j 1 2 3 4 5

1 x 1 0 1 0

2 1 x 1 0 0

B= 3 0 1 x 1 1

4 1 0 1 x 1

5 0 0 1 1 x

1 итерация.

Вычисляем матрицу длин кратчайших путей А(1):

i\j 1 2 3 4 5

1 x 7 9

2 7 x 7

A(1)= 3 7 x 10 4

4 9 10 x 9

5 4 9 x

Находим матрицу кратчайших маршрутов

i\j 1 2 3 4 5

1 x 1 0 1 0

2 2 x 2 0 0

M(1)=3 0 3 x 3 3

4 4 0 4 x 4

5 0 0 5 5 x

2 итерация

Вычисляем матрицу длин кратчайших путей длин 2 А(2):

i\j 1 2 3 4 5

1 x 7 14 9 18

2 7 x 7 16 11

A(2)= 3 14 7 x 10 4

4 9 16 10 x 9

5 18 11 4 9 x

Находим соответствующую матрицу кратчайших маршрутов.

i\j 1 2 3 4 5

1 x 1 2 1 4

2 2 x 2 3 3

M(2)=3 2 3 x 3 3

4 4 3 4 x 4

5 4 3 5 5 x

3 итерация

Вычисляем матрицу длин кратчайших путей А(3) и соответствующую маршрутную матрицу М(3) и убеждаемся, что А(3)=А(2) и М(3)=М(2). Следовательно, матрица М(2)=М является искомой маршрутной матрицей (кратчайших путей), а А(2)=А соответствующих длин кратчайших путей.

Покажем, как пользуясь матрицей М, найти кратчайший путь .

Рассматриваем элемент m₁₅=4. Далее ищем элемент m₁₄, т.к. m₁₄=1, то конец, , при этом .

Рассчитываем потоки по кратчайшим путям: . Для этого полагаем .

1 итерация

Выбираем элемент h₁₂=13.

Находим и вычисляем поток F(1):

k=k+1 и переход к следующей итерации.

Остальные итерации выполняются аналогично. Спустя k=n(n-1)=20 итераций получим следующее распределение потоков по кратчайшим путям: