J7.3旅行售货员问题(又称货郎担问题, Traveling Salesman Problem) 有一个推销员,从城市1出发,要遍访城市2,3,…,n各一次,最 后返回城市1。已知从城市i到j旅费为C;;问他应按怎样的次序 访问这些城市,使得总旅费最少? 可以用多种方法把TSP表示成整数规划模型。这里介绍的一种建立 模型的方法,是把该问题的每个解(不一定是最优的)看作是一次 在下述意义下,引入一些0-1整数变量: ,巡回路线是从倒,且i≠ 0,其它情况 其目标只是使∑Cnx为最小有一个推销员，从城市1出发，要遍访城市2，3，…，n各一次，最 后返回城市1。已知从城市i到j的旅费为Cij，问他应按怎样的次序 访问这些城市，使得总旅费最少？ 可以用多种方法把TSP表示成整数规划模型。这里介绍的一种建立 模型的方法，是把该问题的每个解（不一定是最优的）看作是一次 “巡回” 。 在下述意义下，引入一些0-1整数变量： 例7.3 旅行售货员问题（又称货郎担问题，Traveling Salesman Problem） 1 0 ij i j i j x   =   ， 巡回路线是从 到 ，且 ， 其它情况 其目标只是使 为最小。 , 1=  ij ij i j C x