运筹学论文最短路问题

1运筹学论文——旅游路线最短问题摘要：随着社会的发展，人民的生活水平的提高，旅游逐渐成为一种时尚，越来越多的人喜欢旅游。而如何才能最经济的旅游也成为人民考虑的一项重要环节，是选择旅游时间最短，旅游花费最少还是旅游路线最短等问题随之出现，如何决策成为一道难题。然而，如果运用运筹学方法来解决这一系列的问题，那么这些问题就能迎刃而解。本文以旅游路线最短问题为列，给出问题的解法，确定最短路线，实现优化问题。关键词：最短路0-1规划约束条件提出问题:从重庆乘飞机到北京、杭州、桂林、哈尔滨、昆明五个城市做旅游，每个城市去且仅去一次，再回到重庆，问如何安排旅游线路，使总旅程最短。各城市之间的航线距离如下表：重庆北京杭州桂林哈尔滨昆明重庆0164015006622650649北京164001200188710102266杭州150012000123020912089桂林6621887123002822859哈尔滨265010102091282203494昆明6492266208985934940问题分析：1．这是一个求路线最短的问题，题目给出了两两城市之间的距离，而在最短路线中,这些城市有的两个城市是直接相连接的（即紧接着先后到达的关系），有些城市之间就可能没有这种关系，所以给出的两两城市距离中有些在最后的最短路线距离计算中使用到了，有些则没有用。这是一个0-1规划的问题，也是一个线性规划的问题。2．由于每个城市去且仅去一次，最终肯定是形成一个圈的结构，这就2导致了这六个城市其中有的两个城市是直接相连的，另外也有两个城市是不连接的。这就可以考虑设0-1变量，如果两个城市紧接着去旅游的则为1，否则为0。就如同下图1城市a城市b城市c城市d城市e城市f11111000000000实线代表两个城市相连为1,虚线代表没有相连为03．因为每个城市只去一次，所以其中任何一个城市的必有且仅有一条进入路线和一条出去的路线。LINGO解法：为了方便解题，给上面六个城市进行编号，如下表（因为重庆是起点，将其标为1）重庆北京杭州桂林哈尔滨昆明123456假设：设变量x11。如果x11=1,则表示城市i与城市j直接相连（即先后紧接到达关系），否则若x11=0，则表示城市i与城市j不相连。特别说明：xij和xji是同一变量，都表示表示城市i与城市j是否有相连的关系。这里取其中xij(ij)的变量。模型建立：由于这是一个最短路线的问题，且变量已经设好。目标函数min=1640*x12+1500*x13+662*x14+2650*x15+649*x16+1200*x23+1887*x24+1010*x25+2266*x26+1230*x34+2091*x35+2089*x36+2822*x45+859*x46+3494*x56;约束条件：1.上面目标函数中的变量是表示两个城市是否直接相连接的关系，且最短路线是可以形成圈的，如下图31城市a城市b城市c城市d城市e城市f11111000000000实线代表两个城市相连为1,虚线代表没有相连为0如上图城市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(北京)有且仅有一个进入路线和一个出去路线,所以和它连接的路线条数为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=24则可以编制程序如下!目标函数最小;min=1640*x12+1500*x13+662*x14+2650*x15+649*x16+1200*x23+1887*x24+1010*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);!城市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(杭州)与城市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(重庆)有且仅有一个进入路线和一个出去路线,所以和它连接的路线条数为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!城市5(哈尔滨)有且仅有一个进入路线和一个出去路线,所以和它连接的路线条数为2;x15+x25+x35+x45+x56=2;!城市6(昆明)有且仅有一个进入路线和一个出去路线,所以和它连接的路线条数为2;x16+x26+x36+x46+x56=2;运行结果如下Globaloptimalsolutionfound.Objectivevalue:7598.000Extendedsolversteps:0Totalsolveriterations:0VariableValueReducedCostX120.0000001640.000X130.0000001500.000X140.000000662.0000X151.0000002650.000X161.000000649.0000X231.0000001200.000X240.0000001887.000X251.0000001010.000X260.0000002266.000X341.0000001230.000X350.0000002091.000X360.0000002089.000X450.0000002822.000X461.000000859.0000X560.0000003494.000RowSlackorSurplusDualPrice17598.000-1.00000020.0000000.00000030.0000000.00000040.0000000.00000050.0000000.00000060.0000000.00000070.0000000.000000上面显示旅程最短的距离是7598可以看出求出的所有变量的值都是0或1，其中x15=1，x16=1，x23=1，x25=1，6x34=1，x46=1,这说明了城市1（重庆）和城市5（哈尔滨）相连接城市1（重庆）和城市6（昆明）相连接城市2（北京）和城市3（杭州）相连接城市2（北京）和城市5（哈尔滨）相连接城市3（杭州）和城市4（桂林）相连接城市4（桂林）和城市6（昆明）相连接形成的圈是“重庆（1）-哈尔滨（5）-北京（2）-杭州（3）-桂林（4）-昆明（6）-重庆（1）”，如下图最短旅程的旅游线路：重庆→哈尔滨→北京→杭州→桂林→昆明→重庆（上图外环线）或者也可以按这条路线的逆方向旅行，即重庆→昆明→桂林→杭州→北京→哈尔滨→重庆（上图内环线）总旅程：2650+1010+1200+12301+859+649=7598感想:运筹学就是教我们如何优化作业，得到最优解或者满意解。现实中有许多的事情都需要优化的，当我们去旅游是，我们会考虑走哪些条路线时费用最少；生产物品时，我们要考虑定货批量和库存持有成本与定货成本之间的关系，从而找到最佳的定货批量；当我们考虑管道的铺设问题时，我们要考虑如何选择铺设的路线才能使铺设管道用料最少，从而找到最少用料的路线等等问题。这些都需要我们去优化找到比较满意的答案。重庆哈尔滨北京杭州昆明桂林