Общая постановка задачи

Имеется n городов. Выехав из одного из них, коммивояжер должен объехать все и вернуться в исходный город. В каждый город можно заезжать только один раз, и, следовательно, маршрут коммивояжера должен образовывать замкнутый цикл без петель (например, если есть 6 городов 1, 2, 3, 4, 5 и 6, то 1 – 4 –2 – 1 и 3 – 5 – 6 – 3 – подциклы (петли). Требуется найти кратчайший замкнутый маршрут коммивояжера, если известна матрица расстояний между городами[2].

Математическая модель

Здесь переменная x_ij принимает значение 1, если коммивояжер переезжает из города i в город j (i, j = 1, 2, …, n, i ≠ j) и 0 в противном случае. Условие (1) представляет собой оптимизируемую функцию, где с_ij – расстояние между городами (i, j = 1, 2, …, n, i ≠ j), причем, в общем случае с_ij ≠ с_ji ; условие (2) означает, что коммивояжер выезжает из каждого города только один раз; (3) – что он въезжает в каждый город только один раз; (4) обеспечивает замкнутость маршрута и отсутствие петель, где u_i и u_j – некоторые вещественные значения i, j = 1, 2, …, n, i ≠ j.

Содержательная постановка задачи

Имеется 6 пунктов. Коммивояжер должен посетить их по одному разу и вернуться в исходный город. Найти кратчайший маршрут. Расстояния между городами заданы в виде матрицы чисел, представленной в Таблице 8:

Таблица 8

Матрица расстояний между городами

Оптимизационное моделирование

Построение модели

1. Разместите на Листе Excel исходные данные. Один из возможных вариантов размещения представлен на Рис.44.

Рис.44. Фрагмент рабочего листа исходных данных и ограничений

2. Диапазон ячеек B2:G7 содержит исходную матрицу расстояний между городами, в которой расстояние от города до самого себя приняты достаточно большими, по сравнению с другими расстояниями (например, 1000). Данный прием замены нулевых расстояний на бесконечные используется в классическом методе «ветвей и границ» решения задач данного типа с целью заранее исключить из решения нулевые по расстоянию переходы, которые хотя и являются наикратчайшими, но не допустимы по смыслу задачи.

3. Диапазон ячеек B9:G14 предназначен для плана возможных переходов между городами, который будет получен в результате решения задачи.

4. В ячейках B15:G15 и H9:H14 находятся формулы расчета количества въездов и выездов из городов (Рис. 45).

5. В ячейке D23 – целевая функция, использующая вспомогательные промежуточные расчеты блока D17:D22 (суммы переходов из городов) (Рис.46).

Рис.45. Фрагмент рабочего листа в режиме формул

Рис.46. Фрагмент рабочего листа в режиме формул

Исследование модели

1. Выполните поиск решения (Рис. 47), задав ограничения согласно Таблице 9.

Таблица 9

Ограничения на въезды и выезды

Рис. 47. .Настройка окна ПОИСК РЕШЕНИЯ

2. Результат выполнения поиска решения – на Рис. 48.

Рис. 48. Результат выполнения поиска решения.