这里,将叙述一种在原模型上附加充分的约束条件以避免产生子巡 回的方法。把额外变量1(=2,3,…,n) 附加到问题中。可把这些变量看作是连续的(最然这些变量在最优 解中取普通的整数值)。现在附加下面形式的约束条件 l4-l2+ nxisn-,2≤i≠jsn 为证明该约東条件有预期的效果,必须证明: (1)任何含子巡回的路线都不满足该约束条件; (2)全部巡回都满足该约束条件。 首先证明(1),用反证法。假设还存在子巡回,也就是说至少有 两个子巡回。那么至少存在一个子巡回中不含城市1。把该子巡回 记为2…,则必有l12-l12+n≤n-1 2-l2+n≤n-1 u tn<n-1这里，将叙述一种在原模型上附加充分的约束条件以避免产生子巡 回的方法。把额外变量 附加到问题中。可把这些变量看作是连续的（最然这些变量在最优 解中取普通的整数值）。现在附加下面形式的约束条件 − +  −    1 2 i j ij u u nx n i j n ， 为证明该约束条件有预期的效果，必须证明： （1）任何含子巡回的路线都不满足该约束条件； （2）全部巡回都满足该约束条件。 首先证明（1），用反证法。假设还存在子巡回，也就是说至少有 两个子巡回。那么至少存在一个子巡回中不含城市1。把该子巡回 记为 u i n i ( = 2, 3, , ) 1 2 1 k i i i i ，则必有 1 2 2 3 1 1 1 1 − +  − − +  − − +  − k i i i i i i u u n n u u n n u u n n