20	ГЛАВА 1. ВВЕДЕНИЕ

Обозначим через xj количество единиц материала, раскраиваемого j-ым способом. Переменные xj должны удовлетворять, очевидно, следующим ограничениям:

xj ≥ 0,

x Z,

j

n
jn
å xj	= a,	(17)
=1	j	i
j=1 ij

	å a x = b x (i = 1, . . . , m),

где x — число комплектов изделий.

Задача заключается в максимизации x при ограничениях (17).

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

Коммивояжер должен посетить n городов, не побывав ни в одном дважды и в конце возвратиться в исходный город. Предположим, что известны все расстояния aij между любыми двумя городами i и j (i = 1, . . . , n; j = 1, . . . , n). Каков должен быть маршрут коммивояжера, чтобы суммарное расстояние, пройденное им, было минимальным?

Известно несколько математических постановок этой задачи. Рассмотрим лишь одну из них (Таккер).

Определим переменные xij следующим образом:

xij =	1 если коммивояжер переезжает из города			в город
	0,,	в противном случае.	i		j,

(18) Из каждого города коммивояжер должен выехать ровно один раз,

поэтому

n
å xij = 1 (i = 1, . . . , n).	(19)

j=1

Вкаждый город коммивояжер должен въехать ровно один раз, поэтому

n
åxij = 1 (j = 1, . . . , n).	(20)

i=1

Легко видеть, что этих условий недостаточно, чтобы описать допустимый маршрут коммивояжера (контур, или гамильтонов цикл). Например, две

1.5. ПРИМЕРЫ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 21

Рис. 1.1. Ку–ку!

петли не соответствуют возможному маршруту коммивояжера, однако определяются условиями (18–20). Чтобы отбросить такие случаи, Таккер предложил ограничения (18–20) дополнить n·(n−1) неравенствами вида:

ui − uj + nxij ≤ n − 1 (i = 1, . . . , n; j = 1, . . . , n; i 6= j),

(21)

где ui — новые вещественные переменные.

Покажем, что если мы нашли решение, удовлетворяющее ограничениям (??–??), но не являющееся контуром, то нарушится по крайней мере одно из ограничений (21). В этом случае решение содержит не менее двух петель. Рассмотрим петлю, не проходящую через город с номером 1 и сложим все неравенства, отвечающие xij = 1, вдоль такой петли. Легко видеть, что в результате получим противоречие:

nk ≤ (n − 1)k,

где k — число дуг в петле.

Теперь покажем, что для любого допустимого маршрута найдутся такие ui, удовлетворяюшие неравенствам (21). Положим

ui = t, если город i посещается на шаге t, (t = 1, . . . , n).

При xij = 0 неравенство (21) превращается в верное неравенство ui − uj ≤ n − 1, а при xij = 1 имеем ui − uj + nxij = t − (t + 1) + n = n − 1.

Итак, задача коммивояжера состоит в минимизации функции

n

å xijaij j=1

при ограничениях (18–21).