Практическая часть. Решение задачи о коммивояжере методом ветвей и границ
В результате получаем матрицу 
, приводим её и получаем 
.
Связной путь должен содержать последнюю зафиксированную дугу.
Пример
Фирма «Турал Арбуз Корпорейшен» проводит исследование для более удачного расположения нового склада для товара, который они должны поставлять в 4 магазина. Одним из критериев выбора стала своевременная поставка товара в кротчайшие сроки (обговорено в контрактах). Т.е. получается задача о коммивояжере. Водитель должен побывать на каждой точке с утра и вернуться на склад. Продается три склада, нужно выбрать один из них (цены одинаковы). Важнейшим критерием является минимальный срок проезда через все магазины и возвращение опять на склад. Известно время, за которое водитель может доехать с одной торговой точки до другой и время проезда до склада. Сначала находим минимальное время пути, затрачиваемое водителем с первого склада.
Дана матрица затрачиваемого времени при переезде из точки i в j.
Приведение матрицы 
по строкам:
Приведение матрицы по столбцам:
Выбираем 
:
Получаем матрицу 
Связной путь (2,3), следовательно 
Начинаем 2-ую итерацию
Связной путь: 
3-я итерация.
Нам нужно восстановить 
из 
– связной путь 
, 
Приводим по строкам:
4-я итерация:
Связной путь: 
Корректируем 
:
Ответ: оптимальный путь это – 
означает, что водитель будет затрачивать минимум как 62 единицы времени для проезда из первого склада во все нужные магазины один раз и для возвращения обратно на склад. Нужно уточнить, что время отгрузки здесь не считается.
| |||
| |||
=58 
