Задание № 2. Задача о коммивояжере. 
Метод ветвей и границ

Расстояния между пунктами заданы матрицей:

Решение задачи о коммивояжере методом ветвей и границ начинается с приведения матрицы (вычитания из каждой строки (столбца) матрицы C минимального элемента этой строки (столбца).

Произведем приведение матрицы C по строкам:

h_н= min (i) h_нi

Произведем приведение матрицы C по столбцам:

g_i = min (х) g_нi

В итоге получаем полностью приведенную (редуцированную) матрицу:

Величины h_н и g_i называются константами приведения.

Нижняя граница цикла: d₀=1+1+1+1+1+1+0+0+0+0+0+0 = 6.

().

Шаг № 1. Определяем ребро ветвления и разобьем все множество допустимых значений Q⁰ относительно этого ребра на два непересекающихся подмножества () и (), т. е., где.

В приведенной матрице исследуем все нулевые переходы.

Наибольшая сумма констант приведения равна.

х₄₁= б₄ + в₁ =3+2=5,.

следовательно, множество разбивается на два подмножества и .

Оценка длины цикла:

.

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

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

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

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

Шаг № 2. Определяем ребро ветвления и разобьем все множество допустимых значений Q¹ относительно этого ребра на два непересекающихся подмножества .

В приведенной матрице исследуем все нулевые переходы.

Наибольшая сумма констант приведения равна.

х₃₆=1+1=2, следовательно,.

множество разбивается на два подмножества и .

Оценка длины цикла: .

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

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

В приведенной матрице исследуем все нулевые переходы.

Наибольшая сумма констант приведения равна.

х₂₃=5+0=5, следовательно,.

множество разбивается на два подмножества и .

Оценка длины цикла: .

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

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

Шаг № 4. Определяем ребро ветвления и разобьем все множество допустимых значений Q³ относительно этого ребра на два непересекающихся подмножества. программирование беллман уравнение В приведенной матрице исследуем все нулевые переходы.

Наибольшая сумма констант приведения равна.

х₅₄=5+4=9, следовательно,.

множество разбивается на два подмножества и .

Оценка длины цикла: .

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

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

В соответствии с этой матрицей включаем в маршрут и .

Ответ: l* =C₄₁+C₃₆+C₂₃+C₅₄+C₁₂+C₆₅=1+1+1+1+1+1=6.

Дерево решения имеет следующий вид: