Page 38 - 2577

 1
 1  
 kl    kl  ; (2.39)

 0
Для виконання обмежень (2.32) і (2.34)  повинно задовольняти таким вимогам:
kl
 kl  0 ;
1
 kl    ; 1    
kl

1
 kl   . kl  ( ; 1  ).
1 
kl
Якщо  1, то маємо  kl   1.
2
Підзадача 2 може бути розділена на n незалежних підзадач по одній на кожну пару
“джерело(i) – адресат(j)”:
N 
 kl  x kl i, ( j)  min , (2.40)

k,  l 1  d kl
 ,1 l  i
N N 
при виконанні обмежень x i, ( j)  x i, ( j)  0 , l  i, .
j

 kl  lk
k 1 k 1  , 1 l  j

Тепер розглянемо процедуру пошуку множників Лагранжа. Оскільки функція (L )
нелінійна, то для розв’язку задачі min: L ( ) можна використати, наприклад, один із
градієнтних методів. Найпростішим із них є метод найшвидшого спуску, у відповідності із
яким

r
V kl r  1  kl  Q r  kl r , r 1 , 0 ,...
 r
kl
де Q r – параметр переміщення;
r
 – градієнт функції (L ) ;
kl
r
 – норма градієнта функції (L ) .
kl
Детальний алгоритм розв’язку задачі (2.22) – (2.25) наведений у монографії В.М.
Вишневського “Теоретические основы проектирования компьютерных сетей”.

К-шляхова маршрутизація. В даному випадку допускається, що К > 1, так як
випадок К = 1 призводить до одношляхової маршрутизації. При К > 1 маємо задачу (2.11) –
(2.15), в якій додатково появляються обмеження на число вихідних ліній, що
використовуються для передачі даних із кожного вузла вузлу – адресату.
Таким чином маємо наступну задачу К-шляхової маршрутизації:
N N
1 f
min T :   kl (2.35)
 d  f
k  l1 1 kl kl
при наявності обмежень
N N
1 , (i ) j
f   x , k, l 1 , N , (2.36)
kl  ij kl

 i 1 j  1
f  d kl , k, l 1 , N , (2.37)
kl

35