Page 112 - 6197

L   i  L 1   i  d . (2.19)
0
Оскільки   0L i  , то   i  d , тобто довжина будь-якого
L
1 0
маршруту обмежена знизу величиною d .
0
Якщо після застосування процедури приведення у
кожному рядку і кожному стовпці є по одному нулеві, то
задача комівояжера розв’язана. Величина цільової функції
дорівнює d , нулі вказують на пункти призначення.
0
У тому випадку, коли нулі утворюють єдиний цикл, то
знайдений маршрут є мінімальним.
Розглянемо деякий маршрут із пункту i в пункт j . Для
довжини цього маршруту має місце співвідношення
L   i  c   2  d .
ij 0
Очевидно, перехід із i в j буде найкоротшим, якщо
c   2  0. Тоді   i  d . Звідси випливає, що найкоротший
L
ij 0
маршрут комівояжера повинен мати один з нульових
переходів.
Застосуємо тепер до розв’язання задачі (2.14) метод меж і
гілок.
Початкову множину маршрутів G   0  I розіб’ємо на дві
  1
  1
  1
множини G і G . Множина G вміщує всі можливі
1 2 1
  1
маршрути із пункту i в пункт j , G - множина, яка не
2
вміщує таких маршрутів.
  1
Як показано раніше нижньою оцінкою для множини G
1
буде d .
0
  1
Знайдемо нижню оцінку для множини G . Розглянемо
2
чотири пункти i , k , j , m (рис. 2.5). Оскільки маршрут із i в
  1
j заборонений (множина G не повинна вміщувати маршрут
2
112