Задача 4. Задача коммивояжера

Коммивояжер должен объехать 7 городов. Выехав из одного города, он должен вернуться в него, заехав в каждый из других городов только один раз. Маршрут коммивояжера должен представлять собой замкнутый цикл без петель. Требуется найти кратчайший замкнутый путь коммивояжера. Карта расположения городов показана на рисунке. Расстояния между городами показаны в таблице.

Математическая модель данной транспортной задачи сводится к заданию двух матриц:

— число прохождений пути из города в город . Переменная принимает значение 1, если коммивояжер переезжает из города в город и 0 в противном случае.

— расстояния между городами (в общем случае матрица несимметрична, т.е. .

Кроме того, должны быть заданы два вектора:

— ресурс выезда (число выездов из каждого города);

— ресурс въезда (число въездов в каждый город).

Целевая функция определяет пройденный путь коммивояжера, который должен быть минимальным. Она равна скалярному произведению матриц:

Множество допустимых решений ограничивается ресурсами въезда и ресурсами выезда:

— число прохождений пути из города в город не может превышать заданный ресурс выезда из города ;

— число прохождений пути из города в город не может превышать заданный ресурс въезда в город .

Кроме того, для предупреждения петель вводятся дополнительные условия:

или

Для решения задачи средствами MS Excel нам нужно на листе книги представить дополнительно к матрице расстояний между городами матрицу числа прохождений пути из города в город и сформировать целевую функцию в виде суммы всех маршрутов коммивояжера. Подготовленные таблицы будут выглядеть следующим образом:

В первой матрице диагональные элементы, вообще говоря, равны нулю. Но мы поставили в них большие числа, чтобы предотвратить выезд из города и немедленный въезд в него. Во вторую таблицу вставлены следующие формулы: