下载本文档
版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
1、TSP 问 题有一个推销员，从城市1出发，要遍访城市2, 3,，n各一次，最后返 回城市1。已知从城市i到j的旅费为Cij，问他应按怎样的次序访问这些城 市，使得总旅费最少？可以用多种方法把TSP表示成整数规划模型。这里介绍的一种建立模型的 方法，是把该问题的每个解（不一定是最优的）看作是一次 “巡回”。在下述意义下，引入一些0-1整数变量：1， 巡回路线是从i到j ,且i jnXj 0， 其它情况cij xij其目标只是使1为最小。这里有两个明显的必须满足的条件：访问城市i后必须要有一个即将访问的确切城市；访问城市 j前必须要有一 个刚刚访问过的确切城市。用下面的两组约束分别实现上面的两个条
2、件。Xij1,j 1i 1,2, ,nnXij 1, j 1,2, ni 1到此我们得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条 件对于TSP来说并不充分，仅仅是必要条件。例如：以上两个条件都满足，但它显然不是 TSP的解，它存在两个子巡回。 这里，我们将叙述一种在原模型上附加充分的约束条件以避免产生子巡回的方法。把额外变量Ui （i 2,3,n）附加到问题中。可把这些变量看作是连续的（最然这些变量在最优解中取普通的整数值）。现在附加下面形式的约束条 件ui Uj n Xjj n 1,2 i j n。为了证明该约束条件有预期的效果，必须证明：（1）任何含子巡回的路线 都不满足该
3、约束条件；（2）全部巡回都满足该约束条件。首先证明（1），用反证法。假设还存在子巡回，也就是说至少有两个子巡 回。那么至少存在一个子巡回中不含城市 1。把该子巡回记为i1i2 iki1，则必有 （对于所有的ik都满足大于2的限制条件）uhUi21Ui2n n 1Ui3n n 1UikUi1n n 1把这k个式子相加，有故假设不正确，结论（1）得证。下面证明（2）,采用构造法。对于任意的总巡回1i1 in 11，可取 Ui访问城市i的顺序数。下面来证明总巡回满足该约束条件。（i）总巡回上的边Ui1Ui2 n n1 n 1Ui2迟 n n1 n 1U-Uimnn 1 n 1（ii）非总巡回上的边Uirun 2n 1,r 1,2,n 2, j 2,3,n ir,iUin1Uj n 2n 1,j 2,3,n ir从而结论（2）得证这样我们把TSP转化成了一个混合整数线性规划问题。nmin z q x”i,j 1i jns.t.Xij 1, j 1,2, ni 1nXij1, i 1,2, , nj 15 Uj n Xjjn 1, 2 i j nXij 0,1, i, j 1,2, ,nui 0, i 2, 3, n显然，当城市个数较大（大于 30）时，该混合整数线性规划问题的规模会 很大，从而给求解带来很大问题。TSP已
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论