Задача коммивояжера.
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,1)
Тогда F(X0) = 22 + 12 + 44 + 39 = 117
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij
i  j	1	2	3	4	di	
1	M	22	26	56	22	
2	34	M	12	51	12	
3	45	33	M	44	33	
4	39	7	16	M	7	

Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
i  j	1	2	3	4	
1	M	0	4	34	
2	22	M	0	39	
3	12	0	M	11	
4	32	0	9	M	

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij
i  j	1	2	3	4	
1	M	0	4	34	
2	22	M	0	39	
3	12	0	M	11	
4	32	0	9	M	
dj	12	0	0	11	

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
i  j	1	2	3	4	
1	M	0	4	23	
2	10	M	0	28	
3	0	0	M	0	
4	20	0	9	M	

Сумма констант приведения определяет нижнюю границу H:
H = ∑di + ∑dj
H = 22+12+33+7+12+0+0+11 = 97
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij >=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij .
Шаг №1.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i  j	1	2	3	4	di	
1	M	0(4)	4	23	4	
2	10	M	0(14)	28	10	
3	0(10)	0(0)	M	0(23)	0	
4	20	0(9)	9	M	9	
dj	10	0	4	23	0	

d(1,2) = 4 + 0 = 4; d(2,3) = 10 + 4 = 14; d(3,1) = 0 + 10 = 10; d(3,2) = 0 + 0 = 0; d(3,4) = 0 + 23 = 23; d(4,2) = 9 + 0 = 9; 
Наибольшая сумма констант приведения равна (0 + 23) = 23 для ребра (3,4), следовательно, множество разбивается на два подмножества (3,4) и (3*,4*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,4*) = 97 + 23 = 120
Исключение ребра (3,4) проводим путем замены элемента d34 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,4*), в результате получим редуцированную матрицу.
i  j	1	2	3	4	di	
1	M	0	4	23	0	
2	10	M	0	28	0	
3	0	0	M	M	0	
4	20	0	9	M	0	
dj	0	0	0	23	23	

Включение ребра (3,4) проводится путем исключения всех элементов 3-ой строки и 4-го столбца, в которой элемент d43 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 10
После операции приведения сокращенная матрица будет иметь вид:
i  j	1	2	3	di	
1	M	0	4	0	
2	10	M	0	0	
4	20	0	M	0	
dj	10	0	0	10	

Нижняя граница подмножества (3,4) равна:
H(3,4) = 97 + 10 = 107  <  120
Поскольку нижняя граница этого подмножества (3,4) меньше, чем подмножества (3*,4*), то ребро (3,4) включаем в маршрут.
Шаг №2.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i  j	1	2	3	di	
1	M	0(4)	4	4	
2	0(10)	M	0(4)	0	
4	10	0(10)	M	10	
dj	10	0	4	0	

d(1,2) = 4 + 0 = 4; d(2,1) = 0 + 10 = 10; d(2,3) = 0 + 4 = 4; d(4,2) = 10 + 0 = 10; 
Наибольшая сумма констант приведения равна (0 + 10) = 10 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(2*,1*) = 107 + 10 = 117
Исключение ребра (2,1) проводим путем замены элемента d21 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,1*), в результате получим редуцированную матрицу.
i  j	1	2	3	di	
1	M	0	4	0	
2	M	M	0	0	
4	10	0	M	0	
dj	10	0	0	10	

Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d12 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 8
После операции приведения сокращенная матрица будет иметь вид:
i  j	2	3	di	
1	M	4	4	
4	0	M	0	
dj	0	4	8	

Нижняя граница подмножества (2,1) равна:
H(2,1) = 107 + 8 = 115  <  117
Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (1,3) и (4,2).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(3,4), (4,2), (2,1), (1,3), 
Длина маршрута равна F(Mk) = 111

Решение было получено и оформлено с помощью сервиса:
Задача коммивояжера