这里,将叙述一种在原模型上附加充分的约束条件以避免产生子巡 回的方法。把额外变量1(=2,3,…,n) 附加到问题中。可把这些变量看作是连续的(最然这些变昰在最优 解中取普通的整数值)。现在附加下面形式的约束条件 l4-l2+ nxisn-,2≤i≠jsn 为证明该约東条件有预期的效果,必须证明: (1)任何含子巡回的路线都不满足该约束条件; (2)全部巡回都满足该约束条件。 首先证明(1),用反证法。假设还存在子巡回,也就是说至少有 两个子巡回。那么至少存在一个子巡回中不含城市1。把该子巡回 记为2…4,则必有1-1+n≤n-1 2-L.+n≤n 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
这k个式子相加,有:n<n-1,矛盾! 故假设不正确,结论(1)得证 下面证明(2),采用构造法。对于任意的总巡回 可取 l4=访问城市的顺序数,取值范围为{=2,3,…,n。因此, l1-/≤n-22≤i≠j≤n。下面来证明总巡回满足该约束条件。 (i)总巡回上的边 L.+n=n-1≤n-1 L.-l.+n=n-1<n +n=n-1
这k个式子相加，有： ，矛盾！ =访问城市i的顺序数，取值范围为 。因此， 。下面来证明总巡回满足该约束条件。 ，可取 n n −1 故假设不正确，结论（1）得证。 下面证明（2），采用构造法。对于任意的总巡回 2 -1 1 1 n i i i u i n = 2, 3, , − − 2 i j u u n 2 i j n (ⅰ)总巡回上的边 1 2 2 3 2 1 1 1 1 1 1 1 − − − + = − − − + = − − − + = − − n n i i i i i i u u n n n u u n n n u u n n n
(i)非总巡回上的边 F≡12…,n-2 4. <n ≤n-1j∈{=2,3,…,n}-{v, 1u1--≤n=2≤n-1∈{=23…n- 从而结论(2)得证。 这样我们把TSP转化成了一个混合整数线性规划问题
（ⅱ）非总巡回上的边 从而结论（2）得证。 这样我们把TSP转化成了一个混合整数线性规划问题。 1 2 -1 2 -1 − − − − − r n i j i j u u n n u u n n j i n i i = − 2, 3, , , r r+1 r n = − 1, 2, , 2 j i n i = − 2, 3, , r
min z ∑Cn 1≠J st ∑ l-l1+nxn≤n-1,2≤i≠j≤n x=0,1 l2≥0, i=2.3
, 1 1 1 min . . 1 1, 2, , 1 1, 2, , 1 2 0,1 , 1, 2, , 0, 2, 3, , = = = = = = = = − + − = = = ij ij i j i j n ij j n ij i i j ij ij i z C x s t x j n x i n u u nx n i j n x i j n u i n
显然,当城市个数较大(大于30)时,该混合整数线性规划问题的 规模会很大,从而给求解带来很大问题。TSP已被证明是№难问题, 目前还没有发现多项式时间的算法。对小规模问题,求解这个混合 整数线性规划问题的方式还是有效的。 TSP是一个重要的组合优化问题,除了有直观的应用外,许多其它 看似无联系的优化问题也可转化为TSP。例如: 问题1现需在一台机器上加工n个零件(如烧瓷器),这些零件可 按任意先后顺序在机器上加工。我们希望加工完成所有零件的总时 间尽可能少。由于加工工艺的要求,加工零件j时机器必须处于相 应状态S;(如炉温)。设起始未加工任何零件时机器处于状态So, ,且当所有零件加工完成后需恢复到S状态。已知从状态S;调整到 状态S1(i≠j需要时间C。零件j本身加工时间为D。为方便起见 ,引入一个虚零件0,其加工时间为0,要求状态为S,,则{0,1 ,2,…,n}的一个圈置换π就表示对所有零件的一个加工顺序, 在此置换下,完成所有加工所需要的总时间为 ∑(c4+p)=∑c+2 =0 ∑ P,是一个常数,故该零件的加工顺序问题变成TSP
显然，当城市个数较大（大于30）时，该混合整数线性规划问题的 规模会很大，从而给求解带来很大问题。TSP已被证明是NP难问题， 目前还没有发现多项式时间的算法。对小规模问题，求解这个混合 整数线性规划问题的方式还是有效的。 TSP是一个重要的组合优化问题，除了有直观的应用外，许多其它 看似无联系的优化问题也可转化为TSP。例如： 问题1 现需在一台机器上加工n个零件（如烧瓷器），这些零件可 按任意先后顺序在机器上加工。我们希望加工完成所有零件的总时 间尽可能少。由于加工工艺的要求，加工零件j时机器必须处于相 应状态Sj（如炉温）。设起始未加工任何零件时机器处于状态S0， ，且当所有零件加工完成后需恢复到S0状态。已知从状态Si调整到 状态Sj(i≠j)需要时间Cij 。零件j本身加工时间为pj。为方便起见 ，引入一个虚零件0，其加工时间为0，要求状态为S0， ，则{0，1 ，2，…，n}的一个圈置换π就表示对所有零件的一个加工顺序， 在此置换下，完成所有加工所需要的总时间为 由于 是一个常数，故该零件的加工顺序问题变成TSP。 ( ( ) ( ) ) ( ) 0 0 0 = = = + = + n n n i i i i i j i i j C p C p =0 n j j p