运筹学上机实验报告单
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
最短路问题的设计
3.1程序开发目标
为使用者提供一个修改方便、操作简单的运行程序。
3.2最短路问题程序设计
3.2.1最短路问题简介
对于图Graph，在所有的路径的情况下，目前效率最高的方法是由Dijkstra于1959年提出的。
3.2.2程序设计
对于任意一个有向或无向交通图，每条弧都具有一个数字属性，该数字属性表示通过通过这段路程所需要的时间，现在某人要从一个起点出发，要通过这个交通图到交通网内另一点。求花费总时间最小的旅行路线。
Dijkstra方法的基本思想是规定一个起点。程序搜索时从起点出发，成环形发散地探索最短路径经过的顶点。Dijkstra 方法把交通图中的点集合分化为两个集合。分别称为集合S和集合V-S。第一个集合S表示目标交通图中据起点的最短路径已经确定的顶点集。交通图中还未涉及的其余的顶点暂时存放在另一个集合V-S中。算法开始后，集合S只包含起点或源点，此时只知道源点或起点到本身的路径为0，为最短路径。设v是V中的某个顶点。一条路径被称为中间路径，当且仅当它满足从起点开始到目标顶点的过程中只经过S中的顶点。Dijkstra算法用矩阵D来记录当前所找到的从源点s到每个顶点的最短中间路径长度。矩阵D的初始状态为：如果从源点s到顶点v有路径，则D[sv]记为弧的权值；否则将D[v]置为无穷大或一个对于此交通图来说近似无穷大的值。Dijkstra 算法在每次运算中都作用。算法从集合V-S中裁出顶点u。其中顶点u满足在D[su]是集合内最短路径。将u增补进集合S，同时修改矩阵中由s到达的最短路径长度。如果增补u作中间顶点后，的最短中间路径比之前减少，则修改的最短中间路径。然后，重复上述操作，一旦S包括了所有V中的路径经过点，矩阵D中的各顶点的最短中间路径值就相当于从起始点s到该顶点的最短路径长度。
堆中的数据一般采用数组的形式存储。存储时可以采用具有三个存储域的一维数组或具有四个存储域的一维数组。其中前者包含节点的值，节点左下方子节点的值，节点右下方子节点的值；后者包含节点的值，节点左下方子节点的值，节点右下方子节点的值，节点父节点的值。数组的数量由堆的具体大小决定。数组中不存在的部分由空值表示。
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
1 硕士研究生入学考试运筹学大纲
考试范围：
第一章 线性规划
§1 数学模型
§2 图解法
§3 标准形式与基本性质
§4 单纯形法
§5 对偶规划
§6 对偶单纯形法
§7 灵敏度分析
§8 运输问题
第二章 整数规划
§1 分支定界法
§2 0-1规划
§3 分配问题
第三章 目标规划
§1 数学模型
§2 图解法
第四章 图与网络
§1图论基本概念
§2 树及其优化问题
§3 最短路问题
§4 最大流问题
§5 最小费用流问题
§6 中国邮递员问题
第五章 网络计划技术
§1网络图绘制
§2 参数计算
第六章 决策论
§1 基本概念
§2 不确定型决策
§3 风险决策
第七章 对策论
§1 基本概念
§2 纯策略对策
§3 混合策略对策
§4 矩阵对策求解方法；
第八章 排队论
§1 基本概念
§2 Poisson排队系统
