实验报告最短路和最大流问题.doc

《实验报告最短路和最大流问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告一、实验名称：图论和排队论二、实验目的：通过学习掌握excel规划求解工具，学会对最短路问题、最大流问题进行求解及利用excel的函数工具对排队论问题进行求解。三、实验设备计算机、Excel四、实验内容1、最短路问题：将原问题建立模型。各个点的净流量=流出该结点的流量-流入该结点的流量，按题目输入各点的净流量函数。在最短路平衡流中，各个中间结点的平衡值为0，起点为1，终点为-1。设置目标单元格B18=SUMPRODUCT(C4:C16,D4:D16)。利用规划求解工具求解，如图进行设置，并在【选项】中选择“采用线性模型”和“假定非负”项，求解可得最短路距离

2、为8.5，最短路线为v1—v2—v6—v9。2、最大流问题：将原问题建立模型。各个点的净流量=流出该结点的流量-流入该结点的流量，按题目输入各点的净流量函数。在最大流平衡流中，各个中间结点的平衡值为0。设置目标单元格B16=SUM(C3:C5)。利用规划求解工具求解，如图进行设置，并在【选项】中选择“采用线性模型”和“假定非负”项，求解可得最大流为14.。3、排队论其中：服务强度=B3/B4；系统中没有顾客的概率=(1-B7)/(1-B7^(B5+1))；有效到达率=B3*(1-B11)；N=4；系统中有n个顾客的概率=B8*B7^B10；平均队长=B7/(1-B

3、7)-(B5+1)*B7^(B5+1)/(1-B7^(B5+1))；平均队列长=B12-(1-B8)；逗留时间Ws=B12/B9；等待时间Wq=B13/B9；即可马上求解得。五、实验体会通过实验，觉得用excel做这类题速度很快，很方便。首先就是要掌握题目梗概，有一个基本的轮廓，才能为建模做好铺垫；将题目的信息输入excel表格中；建模，确定变量，约束条件，目标值的计算方法，求解便可。排队论则是将公式输入单元格的表达式中即可方便求解。