运筹学-最短路问题[课件参考]

运筹学上机实验报告单

20 14 －20 15 学年第 2 学期

实验名称 最短路问题的计算机求解 日期：2015 年 5 月 26 日

班级 姓名 学号

实验

目的 掌握最短路问题的计算机求解方法。

实验

内容 （1）最短路问题的lingo编程与计算机求解步骤。

（2）最短路问题计算机求解的输出结果分析。

操作

步骤 （1）进入运筹学软件。

（2）利用相应例题（P143例5-1）熟悉网络最短路问题的计算机求解步骤。

（3）对求解中出现问题所进行内容在同学间相互交流，并进行总结。

（4）完成上机作业（P162习题3），并记录步骤与结果。

结果

显示

与

分析 习题3结果：

Variable Value

U( 1) 0.000000

U( 2) -5.000000

U( 3) -2.000000

U( 4) 3.0000

U( 5) 2.000000

U( 6) -11.00000

U( 7) -7.000000

W( 1, 2) 4.000000

W( 1, 3) -2.000000

W( 1, 4) 3.000000

W( 1, 5) 5.000000

W( 2, 6) 1.000000

W( 3, 2) 7.000000

Microsoft Excel 11.0 运算结果报告

工作表 [20103848李园园.xls]Sheet1

报告的建立: 2003-1-19 6:23:54目标单元格 (最小值)单元格名字初值终值

$E$13V7010

可变单元格单元格名字初值终值$D$2V2 路径00$D$3V5 路径01$D$4V7 路径00$D$5V5 路径00

$D$6V2 路径00

$D$7V6 路径00

$D$8V3 路径00

$D$9V8 路径00

$D$10V6 路径01

$D$11V8 路径01

$D$12V5 路径00

$D$13V7 路径00

约束单元格名字单元格值公式状态型数值

$G$2V1 网络流1$G$2>=$H$2到达限制值0

$G$3V2 网络流0$G$3=$H$3未到限制值0

$G$4V3 网络流0$G$4=$H$4未到限制值0

$G$5V4 网络流0$G$5=$H$5未到限制值0

$G$6V5 网络流0$G$6=$H$6未到限制值0

$G$7V6 网络流0$G$7=$H$7未到限制值0

$G$8V7 网络流0$G$8=$H$8未到限制值0

$D$2V2 路径0$D$2=二进制到达限制值0

$D$3V5 路径1$D$3=二进制到达限制值0

$D$4V7 路径0$D$4=二进制到达限制值0

$D$5V5 路径0$D$5=二进制到达限制值0

$D$6V2 路径0$D$6=二进制到达限制值0

$D$7V6 路径0$D$7=二进制到达限制值0

$D$8V3 路径0$D$8=二进制到达限制值0

$D$9V8 路径0$D$9=二进制到达限制值0

$D$10V6 路径1$D$10=二进制到达限制值0

$D$11V8 路径1$D$11=二进制到达限制值0

$D$12V5 路径0$D$12=二进制到达限制值0

$D$13V7 路径0$D$13=二进制到达限制值0

作业：

课堂作业：书本P182第5题第(1)题

最短路径为7521vvvv

课后作业：

1、 求下列赋权无向网络图s到t的最短路径

P:Avvijijjifwz),(min

最短路径为S-3-5-T

2、某公司正在研制一种有极好销售潜力的新产品。当研究工作接近完成时，公司获悉一家竞争者正计划生产这种产品。要突击赶制出这种产品以参与竞争，还有四个互不重叠的阶段。为了加快进度，每个阶段都可采取“优先”或“应急”的措施。不同的措施下每段工作所需要的时间（月）和费用（百万元）如小下表示。现有一千万元资金供这四个阶段使用，则每段应采取什么措施能使这种产品尽早上市。试将此问题化成最短路问题并求解。

阶段

措施 剩余研究 试制 工艺设计 生产与调拨

时间 费用 时间 费用 时间 费用 时间 费用

正常 5 1

优先 4 2 3 2 5 3 2 1

应急 2 3 2 3 3 4 1 2

解得在一千万元资金供应的条件下最短时间为10个月。

要求：在本文档中写出问题的数学模型，在Excel中计算，并将求解结果写入该文档。 3 2

5

6 3

4

4 7 1

2

2 4 3 7

S 1

2

3 4

5

6 t 8

6 1

运筹学最短路问题

----------关于旅游路线最短及程序

摘要：随着社会的发展，人民的生活水平的提高，旅游逐渐成为一种时尚，

越来越多的人喜欢旅游。而如何才能最经济的旅游也成为人民考虑的一项

重要环节，是选择旅游时间最短，旅游花费最少还是旅游路线最短等问题

随之出现，如何决策成为一道难题。然而，如果运用运筹学方法来解决这

一系列的问题，那么这些问题就能迎刃而解。本文以旅游路线最短问题为

列，给出问题的解法，确定最短路线，实现优化问题。

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

提出问题:

从重庆乘飞机到北京、杭州、桂林、哈尔滨、昆明五个城市做旅游，每个城

市去且仅去一次，再回到重庆，问如何安排旅游线路，使总旅程最短。

各城市之间的航线距离如下表： 重庆 北京 杭州 桂林 哈尔滨 昆明 重庆 0 1640 1500 662 2650 649 北京 1640 0 1200 1887 1010 2266 杭州 1500 1200 0 1230 2091 2089 桂林 662 1887 1230 0 2822 859 哈尔滨 2650 1010 2091 2822 0 3494 昆明 649 2266 2089 859 3494 0 问题分析：

1． 这是一个求路线最短的问题，题目给出了两两城市之间的距离，而在最

短路线中,这些城市有的两个城市是直接相连接的（即紧接着先后到

达的关系），有些城市之间就可能没有这种关系，所以给出的两两

城市距离中有些在最后的最短路线距离计算中使用到了，有些则没

有用。这是一个0-1规划的问题，也是一个线性规划的问题。 2． 由于每个城市去且仅去一次，最终肯定是形成一个圈的结构，这就 导致了这六个城市其中有的两个城市是直接相连的，另外也有两个

城市是不连接的。这就可以考虑设0-1变量，如果两个城市紧接着

去旅游的则为1，否则为0。就如同下图

3. 因为每个城市只去一次，所以其中任何一个城市的必有且仅有一条