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

Имеется n городов. Выезжая из исходного города А₁, коммивояжер должен побывать во всех остальных городах по одному разу и вернуться в город А₁.

Задача заключается в определении последовательности объезда городов при которой коммивояжеру требуется минимизировать некоторый критерий эффективности: стоимость проезда, время в пути, суммарное расстояние и т.д. Пусть задана матрица C=||c_ij|| расстояний между городами и требуется минимизировать суммарную длину пути.

Введем переменные

x_ij=1, если коммивояжер переезжает из города А_i в город А_j, i¹ j;

x_ij=0, в противном случае,

i, j= .

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

® min.

ЦФ представляет суммарную длину пути.

Ограничения имеют вид:

, i= , (1)

, j= , (2)

u_i-u_j+(n-1)× x_{ij £} n-2, 2£ i¹ j £ n, (3)

где u_i, i= - неограниченные действительные переменные.

Условия (1) означает, что коммивояжер выезжает из каждого города один раз, а условия (2)- что он въезжает один раз в каждый город.

Условия (3), выглядящие несколько искусственно, предназначены обеспечить связность маршрута коммивояжера. Более точно эти условия запрещают любой цикл, не проходящий через город 1, и тем самым исключают ситуации, подобные приведенной на рисунке.

4 3 7

1 2 5 6

Данная задача является задачей линейного булева программирования.

Дата добавления: 2015-07-14