Page 36 - 2577

Такий підхід до розв`язку задані оптимальної фіксованої маршрутизації дає змогу
знайти її нижню границю, а це дає можливість будувати алгоритми типу „гілок і меж”.
f
Для розв`язку поставленої задачі введемо нову змінну   kl для всіх k, l 1 , N .
kl
d kl
Величину  - називають завантаженням лінії. Із обмеження (2.13) випливає, що   1.
kl kl
Оскільки f   d  , то підставляючи в (2.11) – (2.15) значення f , отримуємо
kl kl kl kl
N N
1 
min T :   kl (2.22)
 1  
k  l1 1 kl
при виконанні обмежень
1 N N
 kl   ij x kl i, ( j) , k, l  N,1 (2.23)

 d
kl  i 1  j 1
0    , 1 k, l  , 1 N (2.24)
kl
 ,1 l  i
N N 
x i, ( j)  x i, ( j)  , 0 l  i, (2.25)
j
 kl  lk 
k 1 k 1 
 , 1 l  j
x i, ( j)    i,,1;0 j, k, l 1 , N (2.26)
kl
Неважко переконатись, що функція (2.22) є строго зростаючою функцією від  .
kl

f(U)

u u=a ua

U=a U a

0 a M
min f(a)

Рисунок 2.10 – До заміни

наближення (2.23) на (2.23а)

Тому рівність (2.23) можна замінити на нерівність (рис. 2.10).
N N
1  x i, ( j)   , k, l  N,1 (2.23а)
 d kl  ij kl kl
 j 1
 i 1
Тепер можемо записати:
1 N 
min T :   kl , (а)
 1  
k,  l 1 kl
N
1 , (i ) j
 kl   ij x kl  , 0 k, l 1 , N (б)

 d
kl i , j 1
0   kl  1.
В функцію Лагранжа включимо функціонал (а) і обмеження (б). Отже,

33