南邮课内实验-运筹学-图与网络建模-第四次1.doc

课内实验报告 课 程 名： 运 筹 学 任课教师： 邢光军 专 业： 学 号： 姓 名： / 学年 第 学期 南京邮电大学 管理学院 《 运筹学 》课程实验第 4 次实验报告 实验内容及基本要求： 实验项目名称：图与网络建模与求解实验 实验类型： 验证 每组人数： 1 实验内容及要求： 内容：图与网络建模与求解 要求：能够写出求解模型、运用软件进行求解并对求解结果进行分析 实验考核办法： 实验结束要求写出实验报告。实验报告的形式可以包括以下3点： 1.问题的分析与建立模型,阐明建立模型的过程。 2.计算过程,包括采用什么算法，使用什么软件以及计算详细过程和结果。 3.结果分析,将结果返回到实际问题进行分析、讨论、评价和推广。 实验结果：（附后） 成绩评定： 该生对待本次实验的态度 □认真 □良好 □一般 □比较差。 本次实验的过程情况 □很好 □较好 □一般 □比较差 对实验结果的分析 □很好 □良好 □一般 □比较差 文档书写符合规范程度 □很好 □良好 □一般 □比较差 综合意见： 成绩 指导教师签名 日期 实验背景：求下图中v1到v6的最短路。 实验结果：一：问题分析和建立模型： 用EXCEL求解最短路的原理是：令最短路径变量为0或1.即如果最短路通过某弧，则该变量为1，否则为0，如最短路径为v1v2-v3v4-v4v6,那么最短路径变量v1v3=1，v3v4=1，v4v6=1，其余的为0.约束条件为起点的进出权数和为1，终点是-1。除了起点和终点，其余每个中间节点的进出权数之和为0。目标函数则为各弧的权数与对应的最短路径变量乘积之和。于是可以转化规划求解最短路径。 二：计算过程： 下面利用Spreadsheet来求解该问题： 在Excel2003版本中，单击“工具”栏中“加载宏”命令，在弹出的的“加载宏”对话框选择“规划求解”，在“工具”下拉菜单中会增加“规划求解”命令，这样就可以使用了。 利用EXCEL求解题中v1到v6的最短路。 第一步，在Excel上建立最短路模型，将所有的弧列出来，如图①中的A和B两列，所有弧的权数如C列所示，并令最短路径变量的初始值为0，如D列所示。节点v1到v6的进出和如G列所示。（G2=D2+D3+D4.G3=D5-D2-D7,G4=D6-D3-D9,G5=D7+D8-D4-D6-D10,G6=D9+D10+D11,G7=-D5-D8-D11）。目标函数为SUMPRODUCT（C2:C11,D2:D11） v2 3 5 2 7 5 3 1 5 1 2 v1 v6 v5 v3 v4