《运筹学论文最短路问题》由会员分享，可在线阅读，更多相关《运筹学论文最短路问题（9页珍藏版）》请在金锄头文库上搜索。
1、运筹学论文旅游路线最短问题摘要：随着社会的发展，人民的生活水平的提高，旅游逐渐成为一种时尚，越来越 多的人喜欢旅游。而如何才能最经济的旅游也成为人民考虑的一项重要环节，是选 择旅游时间最短，旅游花费最少还是旅游路线最短等问题随之出现，如何决策成为 一道难题。然而，如果运用运筹学方法来解决这一系列的问题，那么这些问题就能 迎刃而解。本文以旅游路线最短问题为列，给出问题的解法，确定最短路线，实现 优化问题。关键词：最短路 0-1规划 约束条件提出问题:从重庆乘飞机到北京、杭州、桂林、哈尔滨、昆明五个城市做旅游，每个城 市去且仅去一次，再回到重庆，问如何安排旅游线路，使总旅程最短。各城市之间的航线距
2、离如下表：重庆北京杭州桂林哈尔滨昆明重庆0164015006622650649北京164001200188710102266杭州150012000123020912089桂林6621887123002822859哈尔滨265010102091282203494昆明6492266208985934940问题分析：1 这是一个求路线最短的问题，题目给出了两两城市之间的距离，而在最 短路线中,这些城市有的两个城市是直接相连接的（即紧接着先后到达的关系）， 有些城市之间就可能没有这种关系，所以给出的两两城市距离中有些在最后的最短 路线距离计算中使用到了，有些则没有用。这是一个 0-1 规划的问题，也是
3、一个线 性规划的问题。2 由于每个城市去且仅去一次，最终肯定是形成一个圈的结构，这就导致 了这六个城市其中有的两个城市是直接相连的，另外也有两个城市是不连接的。这 就可以考虑设 0-1 变量，如果两个城市紧接着去旅游的则为 1，否则为 0。就如同 下图实蜒代农灣个城市祁连先rl* 璨竭我衷谡有和连为u3 因为每个城市只去一次，所以其中任何一个城市的必有且仅有一条进入 路线和一条出去的路线。LINGO 解法：为了方便解题，给上面六个城市进行编号，如下表（因为重庆是起点将其标为 1）重庆北京杭州桂林哈尔滨昆明123456假设：设变量X11。如果xll=l,则表示城市i与城市j直接相连(即先后紧 接
4、到达关系)，否则若xll=o,则表示城市i与城市j不相连。特别说明：xij和xji是同一变量，都表示表示城市i与城市j是否有相连 的关系。这里取其中xij (ij)的变量。模型建立：由于这是一个最短路线的问题，且变量已经设好。目标函数 min=1640*x12+1500*x13+662*x14+2650*x15+649*x16+1200*x23+1887*x24+1010*x2 5+2266*x26+1230*x34+2091*x35+2089*x36+2822*x45+859*x46+3494*x56;约束条件：1.上面目标函数中的变量是表示两个城市是否直接相连接的关系，且最短路线是可以形成
5、圈的，如下图实域狀表两牛城巾柑连为- 虚线代衷邊肓相迄为u如上图城市a和城市b有直接相连接的关系，所以之间变量为1,而城市a 与城市e则没有直接相连接的关系，之间变量为0。其余的也有同样约束，所以有 下面的约束。条件 1：变量 xij 为 0-1 变量bin（xij）2最短旅程路线中，每一个城市都要和其他两个城市相连接，即有一个进入 路线和一个出去路线，所以含第 i 个城市的所有变量 xij 和 xji 之和为 2。所以又 有如下的约束条件 2：城市 1（重庆）有且仅有一个进入路线和一个出去路线,所以和它连接的路线条 数为2x12+x13+x14+x15+x16=2城市 2（北京）有且仅有一个
6、进入路线和一个出去路线,所以和它连接的路线条 数为2x12+x23+x24+x25+x26=2城市 3（杭州）有且仅有一个进入路线和一个出去路线,所以和它连接的路线条 数为2x13+x23+x34+x35+x36=2城市 4（桂林）有且仅有一个进入路线和一个出去路线,所以和它连接的路线条 数为2x14+x24+x34+x45+x46=2城市 5（哈尔滨）有且仅有一个进入路线和一个出去路线,所以和它连接的路线 条数为 2x15+x25+x35+x45+x56=2城市 6（昆明）有且仅有一个进入路线和一个出去路线,所以和它连接的路线条 数为2x16+x26+x36+x46+x56=2则可以编制程序
7、如下!目标函数最小;min=1640*x12+1500*x13+662*x14+2650*x15+649*x16+1200*x23+1887*x24+10 10*x25+2266*x26+1230*x34+2091*x35+2089*x36+2822*x45+859*x46+3494*x56;!变量 0-1 约束;!城市 1（重庆）与城市 2（北京）之间关系变量 x12 的 0-1 约束;bin（x12）;!城市 1（重庆）与城市 3（杭州）之间关系变量 x13 的 0-1 约束;bin（x13）;!城市 1（重庆）与城市 4（桂林）之间关系变量 x14 的 0-1 约束;bin（x14）;!
8、城市 1（重庆）与城市 5（哈尔滨）之间关系变量 x15 的 0-1 约束;bin(x15);!城市 1（重庆）与城市 6（昆明）之间关系变量 x16 的 0-1 约束; bin（x16）;!城市 2（北京）与城市 3（杭州）之间关系变量 x23 的 0-1 约束; bin（x23）;!城市 2（北京）与城市 4（桂林）之间关系变量 x24 的 0-1 约束; bin（x24）;!城市 2（北京）与城市 5（哈尔滨）之间关系变量 x25 的 0-1 约束; bin（x25）;!城市 2（北京）与城市 6（昆明）之间关系变量 x26 的 0-1 约束; bin（x26）;!城市 3（杭州）与城市
9、 4（桂林）之间关系变量 x34 的 0-1 约束; bin（x34）;!城市 3（杭州）与城市 5（哈尔滨）之间关系变量 x35 的 0-1 约束; bin（x35）;!城市 3（杭州）与城市 6（昆明）之间关系变量 x36 的 0-1 约束;bin(x36);!城市 4（桂林）与城市 5（哈尔滨）之间关系变量 x45 的 0-1 约束;bin（x45）;!城市 4（桂林）与城市 6（昆明）之间关系变量 x46 的 0-1 约束;bin（x46）;!城市 5（哈尔滨）与城市6（昆明）之间关系变量 x56 的 0-1 约束;bin（x56）;!条件约束,即每个城市的连接路线约束;!城市 1（重
10、庆）有且仅有一个进入路线和一个出去路线,所以和它连接的路线 条数为 2;x12+x13+x14+x15+x16=2;!城市 2（北京）有且仅有一个进入路线和一个出去路线,所以和它连接的路线 条数为 2;x12+x23+x24+x25+x26=2;!城市 3（杭州）有且仅有一个进入路线和一个出去路线,所以和它连接的路线 条数为 2;x13+x23+x34+x35+x36=2;!城市 4（桂林）有且仅有一个进入路线和一个出去路线,所以和它连接的路线 条数为 2;x14+x24+x34+x35+x46=2;!城市5（哈尔滨）有且仅有一个进入路线和一个出去路线,所以和它连接的路 线条数为2;x15+x
11、25+x35+x45+x56=2;!城市6（昆明）有且仅有一个进入路线和一个出去路线,所以和它连接的路线 条数为2;x16+x26+x36+x46+x56=2;运行结果如下Global optimal solution found.Objective7598.00000value:Extended solversteps:Total solver iterations:VariableValue Reduced CostX120.0000001640.000X130.0000001500.000X140.000000662.0000X151.0000002650.000X23X24X25X26X34X35X36X45X46X561.0000000.0000001.0000000.0000001.0000000.0000000.0000000.0000001.0000000.0000001200.0001887.0001010.0002266.0001230.0002091.0002089.0002822.000859.00003494.000
