Постановка задачи. Пусть имеется n городов, которые связаны между собой дорогами, и известны числа – расстояние (стоимость проезда или др.) между и

Пусть имеется n городов, которые связаны между собой дорогами, и известны числа – расстояние (стоимость проезда или др.) между и городами. Коммивояжер, начиная с некоторого города, должен пройти все из них. Побывав в каждом из них только один раз и вернуться обратно:

Требуется выбрать такой маршрут обхода городов, чтобы суммарная стоимость была минимальной.

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

Целевая функция (5)

(в j-ый город торговец въезжает один раз) (6)

(из j-ого города торговец выезжает одни раз) (7)