Задача коммивояжера (решение методом ветвей и границ)
Полное описание заданий с исходными данными представлено в демо-файле "Описание работы".
Если вам нужна работа с другими исходными данными (другой вариант), то напишите мне в личку (Marka37) и обсудим подробности.
Работа выполнена в 2020 году. Объем работы – 14 стр. Оформление в Word. Шрифт – 14, интервал – 1,5.
Работа сделана с подробными пояснениями к решению.
Постановка задания
Имеется необходимость посетить 6 городов в ходе деловой поездки. Спланировать поездку нужно так, чтобы, переезжая из города в город, побывать в каждом не более одного раза и вернуться в исходный город. Определить оптимальный маршрут посещения городов и его минимальное расстояние.
Требуется найти кратчайший из замкнутых маршрутов, проходящих точно по одному разу через каждый из шести городов А1, А2,..., А6. Задана матрица расстояний между любыми парами городов, причём расстояние от города Ai до города Aj может не совпадать с расстоянием от Аj до Ai. Элемент матрицы aij считается равным расстоянию от Ai до Aj.
Матрица расстояний между городами
∞ 9 10 4 10 1
5 ∞ 2 7 1 4
1 4 ∞ 4 6 8
3 10 3 ∞ 1 8
8 8 5 3 ∞ 6
3 9 8 7 5 ∞
Постановка задания
Имеется необходимость посетить 6 городов в ходе деловой поездки. Спланировать поездку нужно так, чтобы, переезжая из города в город, побывать в каждом не более одного раза и вернуться в исходный город. Определить оптимальный маршрут посещения городов и его минимальное расстояние.
Требуется найти кратчайший из замкнутых маршрутов, проходящих точно по одному разу через каждый из шести городов А1, А2,..., А6. Задана матрица расстояний между любыми парами городов, причём расстояние от города Ai до города Aj может не совпадать с расстоянием от Аj до Ai. Элемент матрицы aij считается равным расстоянию от Ai до Aj.
Матрица расстояний между городами
∞ 9 10 4 10 1
5 ∞ 2 7 1 4
1 4 ∞ 4 6 8
3 10 3 ∞ 1 8
8 8 5 3 ∞ 6
3 9 8 7 5 ∞
1. Казанская О.В., Юн С.Г., Альсова О.К. Модели и методы оптимизации. Практикум: уч. пособие - Новосибирск: Изд-во НГТУ, 2012.- 204 с.
2. Пантелеев А.В. Методы оптимизации в примерах и задачах: Учебное пособие / А.В. Пантелеев, Т.А. Летова. - СПб.: Лань, 2015. - 512 c.
