Page 35 - 2577

 f 
де  max  max  kl  ;   :,lk d kl  . 0
d
 kl 
К7. Перерахувати потоки в лініях зв'язку
  2
f kl : f kl ; k ,l  , 1 . N
  1
К8. Визначити ваги ліній зв'язку
 T d kl
  2 ; k, l  N :,1 d kl  0 i f kl  d kl
w  :  f d  f 
kl kl kl kl

  k,; l  N :,1 d kl  0 або f kl  d kl
та ініцилізувати потоки по найкоротшим шляхам
 : ; 0 k ,l  , 1 . N
kl
К9. Використовуючи нові ваги ліній зв`язку, визначити найкоротші шляхи між всіма
парами вузлів „джерело-адресат”.(ФУ - алгоритм).
К10. Розподілити потоки за найкоротшими шляхами

 i , j , 1 N :
 (k ,l )  ij :

 ) 2 (
 kl :   kl  ij .
  
К11. Знайти величину    1,0 , що мінімізує функцію
N N
1     1  f
T       kl kl .
 2 d      1  f
k  l1 1 kl kl kl
За умови виконання обмежень (2.13).
:
К11. Виконати відхилення (девіацію) потоку на величину 
f    kl  1  f kl ; k ,l  , 1 . N
kl
N N
1 f
К12. Обчислити: T     kl .
new 2
 d  f
k  l1 1 kl kl
К13. Якщо T T   , то stop;
old new
якщо   2   , то не існує допустимих розв'язків;
якщо   2   , то отриманий оптимальний розв'язок із заданою точністю  .
Інакше:
1) Покласти: T : T ;   1 :   2 ;
old new
2) Якщо   1   , то перейти до К6; інакше перейти до К8.

Віртуальна (фіксована) маршрутизація. В порівняні з альтернативною
(дейтограмною) маршрутизацією задача пошуку єдиного шляху є складнішою через вимогу
цілочисельністі змінних x  , ji . Якщо ослабити вимогу цілочисельності, то задачу можна
kl
розв`язати використовуючи метод невизначиних множників Лагранжа. Практика показує, що
для багатьох задач цілочисельнної оптимізації
- функція Лагранжа добре обумовлена, що дозволяє отримати задовільну
швидкість збіжності;
- різниця між цілочисельним оптимумом і оптимумом задачі Лагранжа дуже малі
або зовсім відсутні.

32