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

Имеется n городов, пронумерованных числами 1, 2,..., n. Для любой пары городов (i, j) задано расстояние (время, путевые расходы) C(i,j)  0 между ними. Поэтому в общем случае C(i, j)  C(j, i). Коммивояжер, выезжая из какого-либо города, должен посетить все города по одному разу и вернуться в исходный город. Необходимо определить такую последовательность объезда городов, при которой длина маршрута была бы минимальной.

Другая интерпретация этой задачи связана с минимизацией времени переналадок при обработке на одном станке партии из n различных деталей. Здесь C(i, j) – время переналадки при переходе от обработки детали i к обработке детали j. Требуется найти последовательность обработки деталей, минимизирующую общее время переналадок.

Для записи постановки задачи в терминах целочисленного линейного программирования определим переменные следующим образом: = 1, если коммивояжер переезжает и i-го города в j-й; , в противном случае. Тогда задача заключается в отыскании значений переменных , удовлетворяющих следующим соотношениям:

(5.15)

при условиях

(въезд в город j); (5.16)

(выезд из города i); (5.17)

(i  j); (5.18)

x_ij = {0,1}, , целые, i = 1, ..., m, j = 1, ..., n. (5.19)

Ограничения (5.18) требуют, чтобы маршрут образовывал контур.