Экономико-математические методы и модели в отрасли связи

 

    После вычитания минимальных элементов  получаем полностью редуцированную матрицу, где величины d_i и d_j называются константами приведения.

 

    Сумма констант приведения определяет нижнюю границу H:

    H = ∑d_i + ∑d_j

    H = 4+4+5+9+4+5+0+2+0+0+1+0 = 34

    Элементы  матрицы d_ij соответствуют расстоянию от пункта i до пункта j.

    Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d_ij >=0

    Каждый  допустимый маршрут представляет собой  цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.

    Длина маршрута определяется выражением:

    F(M_k) = ∑d_ij

    Причем  каждая строка и столбец входят в  маршрут только один раз с элементом d_ij .

    Шаг №1.

    Определяем  ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

    С этой целью для всех клеток матрицы  с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены  в скобках.

 

    d(1,5) = 0 + 1 = 1; d(1,6) = 0 + 0 = 0; d(2,3) = 1 + 1 = 2; d(3,2) = 0 + 2 = 2; d(3,4) = 0 + 5 = 5; d(4,1) = 0 + 0 = 0; d(4,6) = 0 + 0 = 0; d(5,1) = 2 + 0 = 2; d(6,1) = 1 + 0 = 1;

    Наибольшая  сумма констант приведения равна (0 + 5) = 5 для ребра (3,4), следовательно, множество  разбивается на два подмножества (3,4) и (3*,4*).

    Нижняя  граница гамильтоновых циклов этого  подмножества:

    H(3*,4*) = 34 + 5 = 39

    Исключение  ребра (3,4) проводим путем замены элемента d₃₄ = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,4*), в результате получим редуцированную матрицу.

 

    Включение ребра (3,4) проводится путем исключения всех элементов 3-ой строки и 4-го столбца, в которой элемент d₄₃ заменяем на М, для исключения образования негамильтонова цикла.

    В результате получим другую сокращенную  матрицу (5 x 5), которая подлежит операции приведения.

    Сумма констант приведения сокращенной матрицы:

    ∑d_i + ∑d_j = 2

    После операции приведения сокращенная матрица будет иметь вид:

 

    Нижняя  граница подмножества (3,4) равна:

    H(3,4) = 34 + 2 = 36  <  39

    Поскольку нижняя граница этого подмножества (3,4) меньше, чем подмножества (3*,4*), то ребро (3,4) включаем в маршрут.

    Шаг №2.

    Определяем  ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

    С этой целью для всех клеток матрицы  с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены  в скобках.

 

    d(1,2) = 0 + 0 = 0; d(1,5) = 0 + 1 = 1; d(1,6) = 0 + 0 = 0; d(2,3) = 1 + 2 = 3; d(4,1) = 0 + 0 = 0; d(4,6) = 0 + 0 = 0; d(5,1) = 0 + 0 = 0; d(5,2) = 0 + 0 = 0; d(6,1) = 1 + 0 = 1;

    Наибольшая  сумма констант приведения равна (1 + 2) = 3 для ребра (2,3), следовательно, множество  разбивается на два подмножества (2,3) и (2*,3*).

    Нижняя  граница гамильтоновых циклов этого  подмножества: