Поиск решения 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). Кратчайший путь (неполный граф, линейная модель) .

© Copyright 2013 - 2020 Excel2.ru. All Rights Reserved