型:Р用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)。Р图①Р第二步,单击“规划求解”按钮,设置目标单元格为最小值,设置可变单元格为最短路径变量单元格,添加约束条件,如图②所示。Р图②Р第三步,单击“求解”按钮,选择“保存规划求解结果”。如图③。Р图③Р三:结果分析:Р图③中D列为1的变量表示最短路径经过的弧,得到最短的路径为v1->v3->v4->v6,最短路长为8。Р四:实验心得:Р本次实验我们使用的Excel及其当中的规划求解模块非常快速、准确地解出了笔头上运用Dijkstra算法计算起来比较复杂的最短路问题。Excel是我们解决各种运筹学问题的好帮手。
全文预览
