Page 33 - 2577

певних значеннях „ваг” ліній зв`язку. Доказано, що оптимальний потік (маршрут) в мережі
може бути поданий як випукла комбінація „екстремальних потоків”.
Властивість 1. Ваги лінії зв'язку (k,l) визначають як часткову похідну

 T
w  .
kl
f 
kl
Нехай  - потік по найкоротших
маршрутах, який визначений відповідно до
ваг w . Утворимо лінійну комбінацію
kl

f     1   ,  f 0  , 1
де f – потік.
Якщо замість f в функцію (2.11)

підставити f , то отримаємо функціонал,
який буде залежати від T ( ) . Також
Рис. 2.7 – Випукла множина
:
1, 2, 3, 4, 5 – крайні точки можна знайти min T ( ). В такому випадку
говорять, що випукла комбінація  і 
мінімізує функцію (T ) .

*
Справедливе таке твердження: Якщо    fTfT  * , то f - оптимальний потік.
Докажемо справедливість такого твердження.

*
Нехай f - оптимальний розв'язок, а f - допустимий розв'язок. Тоді

T    fTf  * (2.18)

*
Із рівняння f      1  f визначимо
*
f  f     f * . (2.19)

*
Звідси знаходимо, що f  f     f * .

*
При значенні   0 різниця  f  f  f також буде прямувати до нуля. Тому
функцію (2.11) можна розкласти в ряд Тейлора, обмежившись лише лінійними членами
 T ( ) f
*
f
T     T f . f 
f  f  f *
Або
 T ( ) f
*
 T  T     T f . f 
f
f  f  f *
Оскільки  fT є функцією багатьох змінних f , то при врахуванні значення f ,
kl
kl
отримаємо
N N

 T   f kl  f kl * T * ..
k  1 l 1 f kl f kl  f kl
Оскільки f     f * , то
N N T
 T      kl  f kl *  *
k  l1 1 f kl f kl  f kl
Із співвідношення (2.18) випливає, що
 T  0 .
Оскільки   0 , то
N N T
   kl  f kl *   0 (2.20)
k  l1 1 f kl

30