Поиск решения MS EXCEL (6.3). Задача коммивояжера (полный граф, линейная модель)

Решим один из вариантов задачи коммивояжера для небольшого количества городов (5-10) с помощью надстройки Поиск решения. Построим линейную модель.

Рассмотрим задачу коммивояжера (англ. Travelling Salesman Problem, TSP) заключающуюся в отыскании самого короткого маршрута, проходящего через заданные города по одному разу с последующим возвратом в исходный город (также рассмотрим вариант без возврата). Подобная задача решена в статье Поиск решения MS EXCEL (6.2). Задача коммивояжера (полный граф, нелинейная модель) с помощью нелинейной модели.

Задача

Найдем кратчайший путь между 5 городами, координаты которых известны. Сначала рассмотрим замкнутый вариант задачи: коммивояжёру требуется посетить все города, после чего вернуться в исходный город.

Создание модели

Так как даны координаты городов, то сначала найдем расстояния между ними (см. файл примера, лист 5 городов).

Расстояния рассчитаем с помощью формулы:
=КОРЕНЬ((ИНДЕКС($C$7:$D$11;$A16+1;1)-ИНДЕКС($C$7:$D$11;B$15+1;1))^2+(ИНДЕКС($C$7:$D$11;$A16+1;2)-ИНДЕКС($C$7:$D$11;B$15+1;2))^2)

Теперь создадим модель для Поиска решения.

Совет: Вводная статья про Поиск решения в MS EXCEL 2010 находится здесь.

Переменные (выделено зеленым). В качестве переменных модели следует взять номера всех маршрутов соединяющих города. Маршрут из города 0 в город 1 эквивалентен маршруту из 1 в 0, так как направление обхода городов не имеет значения. Необходимо соединить все города (полный граф).

Ограничения (выделено синим). Необходимо, чтобы из каждого города был 1 входящий и 1 исходящий маршрут.

Целевая функция (выделено красным). Длина маршрута должна быть минимальной.

Примечание: для удобства настройки Поиска решения используются именованные диапазоны.

Найденное Решение

Поиск решения гарантировано найдет самый короткий маршрут, т.к. построенная нами модель линейная.

Данную задачу можно решить для максимального количества городов =20, т.к. число маршрутов (ребер) вычисляется по формуле n*(n-1)/2, а количество переменных у Поиска решения ограничено 200.

Также в файле примера приведено решение задачи для прохождения 5 городов по незамкнутому маршруту, а также задачу для 9 городов.

Совет: Решение задачи о поиске кратчайшего пути между 2-мя заданными городами можно найти в статье Поиск решения MS EXCEL (6.4). Кратчайший путь (неполный граф, линейная модель).

Связанные статьи

Похожие задачи
Прочитайте другие статьи, решающие похожие задачи в MS Excel. Это позволит Вам решать широкий класс подобных задач.
Средняя: 5 (2 оценок)