Построение кольцевых маршрутов
Коммерческая деятельность обычно связана с командировками, поездками по городам для заключения сделок. Расстояния между любой парой множества из п городов известны и составляют а-у (/’ = 1, т j = 1, п, i ^ j). Если прямого маршрута между городами i и j не существует, то допускают, что
а$- °°.
Коммерсант, выезжая из какого-либо города, должен посетить все города, побывав в каждом из них один и только один раз, и вернуться в исходный город. Необходимо определить такую последовательность объезда городов, при которой длина маршрута была бы наименьшей.
Экономико-математическая постановка этой задачи может быть представлена как задача целочисленного линейного программирования. Переменные определим следующим образом: Ху = 1, если коммивояжер переезжает из города i в город j (i = l,m;j = 1, и, i **/); в противном случае Ху = 0.
Задача заключается в определении матрицы целых неотрицательных значений переменных Ху, минимизирующих целевую функцию вида
при ограничениях:
1) для въезда в город j только один раз
2) для выезда из города i только один раз
В такой постановке задача коммивояжера представляет собой задачу целочисленного линейного программирования. Действительно, условия = °о исключают в оптимальном решении значения xV} = 1 как не имеющие смысла, а ограничения требуют:
- 1) чтобы маршрут включал только один въезд в каждый город;
- 2) чтобы маршрут включал лишь один выезд из каждого города, а целевая функция включала длину маршрута коммивояжера;
- 3) чтобы маршрут образовывал контур, проходящий через все города. Таким образом формируется экономный вариант маршрута в виде кольца.
Решение этой задачи строится, например, методом ветвей и границ целочисленного программирования.
