运筹学论文最短路问题

运筹学论文

——旅游路线最短问题

摘要：

随着社会的发展，人民的生活水平的提高，旅游逐渐成为一种时尚，越来越多的人喜欢旅游。而如何才能最经济的旅游也成为人民考虑的一项重要环节，是选择旅游时间最短，旅游花费最少还是旅游路线最短等问题随之出现，如何决策成为一道难题。然而，如果运用运筹学方法来解决这一系列的问题，那么这些问题就能迎刃而解。本文以旅游路线最短问题为列，给出问题的解法，确定最短路线，实现优化问题。

关键词：最短路 0-1规划 约束条件

提出问题:

从重庆乘飞机到北京、杭州、桂林、哈尔滨、昆明五个城市做旅游，每个城市去且仅去一次，再回到重庆，问如何安排旅游线路，使总旅程最短。 各城市之间的航线距离如下表： 重庆 北京 杭州 桂林 哈尔滨 昆明

问题分析：

1．

这是一个求路线最短的问题，题目给出了两两城市之间的距离，而在最短路线中,这些城市有的两个城市是直接相连接的（即紧接着先后到达的关系），有些城市之间就可能没有这种关系，所以给出的两两城市距离中有些在最后的最短路线距离计算中使用到了，有些则没有用。这是一个0-1规划的问题，也是一个线性规划的问题。

2．

由于每个城市去且仅去一次，最终肯定是形成一个圈的结构，这就重庆

0 1640 1500 662 2650 649

北京 杭州 桂林 哈尔滨 昆明

1640 1500 662 2650 649 0 1200 1887 1010 2266 1200 0 1230 2091 2089 1887 1230 0 2822 859 1010 2091 2822 0 3494 2266 2089 859 3494 0

1

导致了这六个城市其中有的两个城市是直接相连的，另外也有两个城市是不连接的。这就可以考虑设0-1变量，如果两个城市紧接着去旅游的则为1，否则为0。就如同下图

城市a100000010101城市b1城市f0城市c城市e1城市d实线代表两个城市相连为1,虚线代表没有相连为0

3． 因为每个城市只去一次，所以其中任何一个城市的必有且仅有一条进入路线和一条出去的路线。

LINGO解法：

为了方便解题，给上面六个城市进行编号，如下表（因为重庆是起点， 将其标为1）

重庆 1 北京 2 杭州 3 桂林 4 哈尔滨 5 昆明 6 假设：设变量x11。如果x11=1,则表示城市i与城市j直接相连（即先后紧接到达关系），否则若x11=0，则表示城市i与城市j不相连。

特别说明：xij和xji是同一变量，都表示表示城市i与城市j是否有相连的关系。这里取其中xij (i

模型建立：由于这是一个最短路线的问题，且变量已经设好。

目标函数

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. 上面目标函数中的变量是表示两个城市是否直接相连接的关系，且最短

路线是可以形成圈的，如下图

2

城市a101城市b10城市f10000000城市c1城市e1城市d实线代表两个城市相连为1,虚线代表没有相连为0

如上图城市a和城市b有直接相连接的关系，所以之间变量为1，而城市a与城市e则没有直接相连接的关系，之间变量为0。其余的也有同样约束,所以有下面的约束。 条件1：

变量xij为0-1变量 @bin(xij)

2．最短旅程路线中，每一个城市都要和其他两个城市相连接，即有一个进入路线和一个出去路线，所以含第i个城市的所有变量xij和xji之和为2。所以又有如下的约束

条件2：

城市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+x45+x46=2

城市5(哈尔滨)有且仅有一个进入路线和一个出去路线,所以和它连接的路线条数为2

x15+x25+x35+x45+x56=2

城市6(昆明)有且仅有一个进入路线和一个出去路线,所以和它连接的路线条数为2

x16+x26+x36+x46+x56=2

3

则可以编制程序如下

!目标函数最小;

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;

4

!城市5(哈尔滨)有且仅有一个进入路线和一个出去路线,所以和它连接的路线条数为2; x15+x25+x35+x45+x56=2;

!城市6(昆明)有且仅有一个进入路线和一个出去路线,所以和它连接的路线条数为2; x16+x26+x36+x46+x56=2;

运行结果如下

Global optimal solution found.

Objective value: 7598.000 Extended solver steps: 0 Total solver iterations: 0

Variable Value Reduced Cost X12 0.000000 1640.000 X13 0.000000 1500.000 X14 0.000000 662.0000 X15 1.000000 2650.000 X16 1.000000 649.0000 X23 1.000000 1200.000 X24 0.000000 1887.000 X25 1.000000 1010.000 X26 0.000000 2266.000 X34 1.000000 1230.000 X35 0.000000 2091.000 X36 0.000000 2089.000 X45 0.000000 2822.000 X46 1.000000 859.0000 X56 0.000000 3494.000

Row Slack or Surplus Dual Price 1 7598.000 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 0.000000 0.000000 7 0.000000 0.000000

上面显示旅程最短的距离是7598

可以看出求出的所有变量的值都是0或1，其中x15=1，x16=1，x23=1，x25=1，

5

x34=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 感想:

运筹学就是教我们如何优化作业，得到最优解或者满意解。现实中有许多的事情都需要优化的，当我们去旅游是，我们会考虑走哪些条路线时费用最少；生产物品时，我们要考虑定货批量和库存持有成本与定货成本之间的关系，从而找到最佳的定货批量；当我们考虑管道的铺设问题时，我们要考虑如何选择铺设的路线才能使铺设管道用料最少，从而找到最少用料的路线等等问题。这些都需要我们去优化找到比较满意的答案。

6

本文来源：https://www.bwwdw.com/article/bgkv.html