Page 40 - 2577
P. 40
f
де max max kl ; (k : ) ,l d kl 0 .
d
kl
К8. Перерахувати потоки в лініях зв’язку
2
f : f kl ; k, l 1 , N .
kl
1
К9. Обчислити затримки z між кожною парою вузлів «джерело - адресат» i j .
ij
N
1
(i
Величину z обчислимо за формулою z ij kl ) , де N - кількість вузлів, які включає в себе
t
ij
1
k ,l 1
маршрут (i, j); t(i,j) – час між вузлами k і l в маршруті (i, j).
К10. Відсортувати множину пар вузлів (i, j) в порядку зменшення величин z .
ij ij
Отриману множину пар позначимо через Ω.
К11. Вибрати чергову пару вузлів (i , j ) . Якщо вже всі пари розглянуті, то Stop.
0 0
К11. Для вибраної пари вузлів (i , j ) ініціалізувати потік по найкоротших шляхах
0 0
:
kl
1) : f ; k, l 1 , N ;
kl kl
2
2) ,lk : : : .
0 i 0 j 0 i 0 j ij kl kl 0 i 0 j
К12. Визначити ваги ліній зв’язку:
T d kl
2 k, l N :,1 d kl ,0 f kl d kl
w : f d f
kl kl kl kl
k, l N :,1 d kl ,0 f kl d kl
К13. Використовуючи ваги ліній зв’язку w kl, визначити найкоротший шлях для
0 i 0 j
пари вузлів (i , j ).
0 0
К14. Перевірити обмеження:
N
(
kl j) K; k, j 1 , N .
l 1
0
1) k ,l :
0 i 0 j
j j
а) kl 0 : kl 0 ;
j j
б) якщо 0 0, 0 1.
kl kl
2) k : lk , 0 визначити:
0 i 0 j
N
j
а) k 0 ;
kl
l 1
б) якщо k > K, то перейти до кроку 11.
К15. Розподілити потоки i j по найкоротшому шляху 0 :
0 0 0 i 0 j
k
0 :
,l
0 i 0 j
2
: 0 i 0 j .
kl
kl
К17. Знайти величину 1,0 , яка мінімізує функцію
37