excess求解最短路.docxVIP

例题：V6361442445225V7V5V2V11V4V3基于office2010求解最短路问题用Excel求解最短路问题的原理设决策变量为xij，当xij=1，表示最短路P*通过边vi,vj；当xij=0，表示最短路P*不通过边vi,vj；最短路P*中，除起点和终点之外，每个点的进出度数和为0，起点为1，终点为- 1。目标函数为各边权数与对应决策变量xij的乘积之和的最小值。步骤：第一步：制作表格，第一行依次输入：从、到、是否走、距离、节点、净流量、空、供应/需求；在相应列输入已知数据（是否走列填0；供应/需求列依次填1,0,0,…，0,0，-1）。并在到列数据下空一格，输入总距离。第二步：在净流量列全都输入=SUMIF（从，节点，是否走）-SUMIF（到，节点，是否走），回车，得到净流量列全为0.第三步:在总距离同一行右边单元格Z内输入=SUMPRODUCT（是否走，距离），回车，得到0.第四步：选中Z，单击菜单栏中数据，选择规划求解。设置规划求解参数。目标函数为最小值；可变单元格为是否走列；遵守约束为净流量=供应/需求；√使无约束变量为非负数；选择求解方法为单纯线性规划。第五步：点击求解，并确定。解：i）制作表格，第一行依次输入：从、到、是否走、距离、节点、净流量、空、供应/需求；在从列输入V1，V1,V2,V2,V2,V3,V3,V4,V4,V5,V5,V6;到列输入V2，V3，V3，V4，V5，V4，V6，V5，V6，V6，V7，V7；是否走列输入0,0,0,0,0,0,0,0,0,0,0,0；距离列输入5,2,2,4,5,2,4,4,4,1,3,6；节点列输入V1，V2，V3，V4，V5，V6，V7；空列输入=，=，=，=，=，=，=；供应/需求列输入1,0，0,0,0,0，-1.如下图： ii）在净流量列单元格内全都输入=SUMIF(A2:A13,E2:E8,C2:C13)-SUMIF(B2:B13,E2:E8,C2:C13)，回车（注意：选择复制粘贴时，切勿使用键盘下键，不然改变单元格内公式，直接按enter键即可），得到净流量列全为0.如下图：iii）在总距离同一行右边单元格Z内输入=SUMPRODUCT(C2:C13,D2:D13)，回车，得到0.如下图：iv）选中Z，单击菜单栏中数据，选择规划求解，设置规划求解参数。目标函数为最小值；可变单元格为是否走列，即C2:C13；遵守约束为净流量=供应/需求,即F2:F8=H2:H8；√使无约束变量为非负数；选择求解方法为单纯线性规划。如下图：v) 点击求解按钮，并确定。规划求解找到一解，可以满足所有的约束及最优状况。如下图所示，我们可以得到最短路为11