Page 119 - 6197

Враховуючи значення d і  , будемо мати
0 14
 
L G 2   1  48 10 58  .
  1
Для множини G оцінка залишається без змін
1
 
L G 1   1  48.
Оскільки із кожного міста можна виїжджати і в’їжджати
тільки один раз, то перший рядок і четвертий стовпець із
  1
подальшого розгляду слід виключити. У матриці C
2
викреслюємо перший рядок і четвертий стовпець і розставимо
заборони, які можуть привести до виникнення підциклів;
  2
елементу c присвоюємо значення M . В оптимальний
41
 . У
маршрут комівояжера включаємо шлях L   1 4,
результаті виконаної процедури приведення над матрицею
  1
C отримаємо
2
1 2 3 5 6
2 1 M 15 29 24

 
3 15 13 M 5 0
 

C   2  4 M 0 9 2 2  .
 
5 2 41 22 M 0 


6 13 0 0 0 M 


  2
Виконуємо операцію приведення над матрицею C .
  2
Знаходимо в матриці C рядок, який не вміщує нульових
  2
елементів. Таким є другий рядок матриці C . Мінімального
  2
значення цьому рядку набуває елемент c . Тому константа
21
приведення по цьому рядку r  . Копстанти приведення
1
2
  2
матриці C по інших рядках будуть мати нульові значення.
Тому трансформації підлягає тільки рядок під номером два;
119