Задача коммивояжера.
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,5);(5,1)
Тогда F(X0) = 56 + 55 + 99 + 13 + 5 = 228
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij
i  j	1	2	3	4	5	di	
1	M	56	456	77	6	6	
2	35	M	55	88	8	8	
3	48	58	M	99	9	9	
4	12	80	654	M	13	12	
5	5	55	1	100	M	1	

Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
i  j	1	2	3	4	5	
1	M	50	450	71	0	
2	27	M	47	80	0	
3	39	49	M	90	0	
4	0	68	642	M	1	
5	4	54	0	99	M	

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj = min(i) dij
i  j	1	2	3	4	5	
1	M	50	450	71	0	
2	27	M	47	80	0	
3	39	49	M	90	0	
4	0	68	642	M	1	
5	4	54	0	99	M	
dj	0	49	0	71	0	

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

Сумма констант приведения определяет нижнюю границу H:
H = ∑di + ∑dj
H = 6+8+9+12+1+0+49+0+71+0 = 156
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij >=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij .
Шаг №1.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i  j	1	2	3	4	5	di	
1	M	1	450	0(9)	0(0)	0	
2	27	M	47	9	0(9)	9	
3	39	0(1)	M	19	0(0)	0	
4	0(5)	19	642	M	1	1	
5	4	5	0(51)	28	M	4	
dj	4	1	47	9	0	0	

d(1,4) = 0 + 9 = 9; d(1,5) = 0 + 0 = 0; d(2,5) = 9 + 0 = 9; d(3,2) = 0 + 1 = 1; d(3,5) = 0 + 0 = 0; d(4,1) = 1 + 4 = 5; d(5,3) = 4 + 47 = 51; 
Наибольшая сумма констант приведения равна (4 + 47) = 51 для ребра (5,3), следовательно, множество разбивается на два подмножества (5,3) и (5*,3*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(5*,3*) = 156 + 51 = 207
Исключение ребра (5,3) проводим путем замены элемента d53 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,3*), в результате получим редуцированную матрицу.
i  j	1	2	3	4	5	di	
1	M	1	450	0	0	0	
2	27	M	47	9	0	0	
3	39	0	M	19	0	0	
4	0	19	642	M	1	0	
5	4	5	M	28	M	4	
dj	0	0	47	0	0	51	

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

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

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

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

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

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

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

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

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