Практическая часть. Решение задачи о коммивояжере методом ветвей и границ
Пусть это будет 
и производим разбиение.
Дальнейший процесс будет проходить также.
При этом способе можно достаточно быстро получить подмножество 
, содержащее всего один план задачи 
, то 
- претендент на оптимальный план. Запоминаем 
на графе на ветке, приводящей к ставим конец и корректируется величина 
, т.е. 
.
увеличена, следовательно нужно рассмотреть все нерассмотренные подмножества.
Далее продолжаем процесс решения задачи также.
Второй способ:
Выбирается множество для разбиения из всех висячих вершин, ещё нерассмотренных.
Выбирать способ решения задачи нужно в зависимости от конкретной задачи. При любом способе решения процесс продолжаем до тех пор пока не будет выполнено следующее условие: 
для любого 
(висячие вершины).
Решением задачи будет тот план, который дал последнее значение величине .
Для решения конкретной ЗДП необходимо строить алгоритм метода ветвей и границ, согласно приведенной схеме. При этом нужно решить следующие проблемы:
1) как найти ;
по какому принципу проводить разбиение множества;
как вычислить 
.
Решение задачи о комивояжере.
– верхняя оценка оптимального значения 
– нижняя оценка функции цели на множестве 
- оптимальная
Как найти 
?
Для нахождения 
необходимо провести операцию приведения матрицы 
.
Определение:
Процесс вычитания из каждого элемента i-ой строки матрицы 
минимального элемента этой строки называется приведением матрицы по строке I, а минимальный элемент этой строки называется константой приведения. Аналогично процесс вычитания из каждого элемента j-ого столбца матрицы называется приведением матрицы по столбцам.
Приведенная матрица – это матрица, которая приведена и по всем строкам и столбцам.
– суммарная константа приведения матрицы .
Критерий приведения – в каждой строке и столбце должны быть хотя бы один нуль.
Приведенная матрица – 
t – произвольный гамельктоновый цикл.
На каждой итерации разбиваем множество на два подмножества.
Принцип разбиения:
X – произвольное множество, которое разбивается.
– подмножества, на которые разбивается множество X.
На каждой итерации свои подмножества – 
. Разбиение проходит по дуге
. Во множество 
входят те гамельктоновы циклы из x, каждые из которых содержат дугу . Во множество 
входят те гамельктоновы циклы из x, в которых запрещена дуга , т.е. запрещен переезд в город l.
