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
   35   36   37   38   39   40   41   42   43   44   45