发布时间 : 星期一 文章TSP问题更新完毕开始阅读b0528db6f8b069dc5022aaea998fcc22bcd143d9
有一个推销员，从城市1出发，要遍访城市2，3，…，n各一次，最后返回城市1。已知从城市i到j的旅费为ij，问他应按怎样的次序访问这些城市，使得总旅费最少
可以用多种方法把TSP表示成整数规划模型。这里介绍的一种建立模型的方法，是把该问题的每个解（不一定是最优的）看作是一次“巡回”。
在下述意义下，引入一些0-1整数变量：
?1，巡回路线是从i到j,且i?j??xij?0，其它情况n 其目标只是使i,j?1c?cijxij为最小。
这里有两个明显的必须满足的条件：
访问城市i后必须要有一个即将访问的确切城市；访问城市j前必须要有一个刚刚访问过的确切城市。用下面的两组约束分别实现上面的两个条件。
?xj?1nij?1,?1,i?1,2,?,n
到此我们得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于TSP来说并不充分，仅仅是必要条件。例如：
6 3
4 1
2
5 的解，它存在两个子巡回。 以上两个条件都满足，但它显然不是TSPi?1?xnijj?1,2,?,n这里，我们将叙述一种在原模型上附加充分的约束条件以避免产生子巡回的方法。把额外变量
ui(i?2,3,?,n)附加到问题中。可把这些变量看作是连续的（最然这些变量在最
ui?uj?nxij?n?1,2?i?j?n优解中取普通的整数值）。现在附加下面形式的约束条件
。
为了证明该约束条件有预期的效果，必须证明：（1）任何含子巡回的路线都不满足该约束条件；（2）全部巡回都满足该约束条件。
首先证明（1），用反证法。假设还存在子巡回，也就是说至少有两个子巡回。那么至少存在一个子巡回中不含城市1。把该子巡回记为于2的限制条件)
i1i2?iki1，则必有(对于所有的i都满足大
k
ui1?ui2?n?n?1ui21?ui3?n?n?1?uik?ui1?n?n?1把这k个式子相加，有
n?n?1，矛盾！
故假设不正确，结论（1）得证。
下面证明（2），采用构造法。对于任意的总巡回下面来证明总巡回满足该约束条件。
ui?访问城市i的顺序数。
1i1?in?11，可取
(ⅰ)总巡回上的边
?ui1?ui2?n?n?1?n?1??ui2?ui3?n?n?1?n?1????u?u?n?n?1?n?1in?1?in?2（ⅱ）非总巡回上的边
从而结论（2）得证。
这样我们把TSP转化成了一个混合整数线性规划问题。
??uir?uj?n?2?n?1,r?1,2,?,n?2,j?{2,3,?,n}?{ir,ir?1}???uin?1?uj?n?2?n?1,j?{2,3,?,n}?{ir}
n??minz??cijxiji,j?1?i?j?n?j?1,2,?,n?s.t.?xij?1,i?1?n?xij?1,i?1,2,?,n??j?1??ui?uj?nxij?n?1,2?i?j?n?xij?0,1,i,j?1,2,?,n??ui?0,i?2,3,?,n?
显然，当城市个数较大（大于30）时，该混合整数线性规划问题的规模会很大，从而
给求解带来很大问题。TSP已被证明是NP难问题，目前还没有发现多项式时间的算法。对于小规模问题，我们求解这个混合整数线性规划问题的方式还是有效的。