课内实验-运筹学-图与网络建模.doc

课内实验报告

课 程 名： 运 筹 学
任课教师： 邢 光 军
专 业： 信息管理与信息系统
学 号： B101108XX
姓 名： XXX

2010/2011学年 第 2 学期
南京邮电大学 经济与管理学院
《 运筹学 》课程实验第 4 次实验报告
实验内容及基本要求：
实验项目名称：图与网络建模与求解实验
实验类型： 验证
每组人数： 1
实验内容及要求：
内容：图与网络建模与求解
要求：能够写出求解模型、运用软件进行求解并对求解结果进行分析
实验考核办法：
实验结束要求写出实验报告。实验报告的形式可以包括以下3点：
1.问题的分析与建立模型,阐明建立模型的过程。
2.计算过程,包括采用什么算法，使用什么软件以及计算详细过程和结果。
3.结果分析,将结果返回到实际问题进行分析、讨论、评价和推广。
实验结果：（附后）
实验背景：求下图中v1到v6的最短路
v2
3
5
2
7
5
3
1
5
1
2
v1
v6
v5
v3
v4

分析问题与建立模型：
可见，从V1到V6的路线是很多的，例如可以从V1出发，依次经过V3，V5，然后到V6，也可以从V1出发，经过V2，再到V6。不同的路线，路程的长短是不一样的。
最短路问题可以用Excel线性规划进行求解：
过程如下：
把各个节点之间的指向关系以及权值在Excel表中体现出来，如下图所示，变量的含义为，如果该条路径在最短路径内，则决策变量值为1，若不包含在内，则决策变量值为0；节点的净值为该节点的入度减去出度；目标函数使用SUMPRODUCT函数对距离和决策变量两列进行矩阵相乘，即求最短路所在路径的路径长度。

输入好完整的信息后，对该问题进行规划求解：

求解的结果如下图所示：

由上图可知：最短路径为：1至3至4至6，最短路径的路径长度即为目标函数的值，等于8。

成绩评定：
该生对待本次实验的态度 □认真 □良好 □一般 □比较差。
本次实验的过程情况 □很好 □较好 □一般 □比较差
对实验结果的分析 □很好 □良好 □一般 □比较差
文档书写符合规范程度 □很好 □良好 □一般 □比较差
综合意见：
成绩

指导教师签名
邢光军
日期