另一种方法求最短路径.doc

练习8 另一种方法求最短路径六个城市的连接情况如图lx8-1，求城市A到城市F的最短路径。图lx8-1 六个城市连接情况 使用Excel的规划求解来处理最短路径问题，求得的结果如图lx8-2所示，即A到F的最短路径为ACEF。图lx8-2 最短路径求解结果8.1输入最短路径问题路径信息（1）工作簿更名为“最算路径解法2”。（2）加载工具。单击【工具】【加载宏】菜单项，打开【加载宏】对话框。选中【规划求解】复选框，然后单击【确定】按钮将规划求解宏加载到Excel中。（2）将工作表Sheet1重命名“最短路径问题”，输入如图3.5-3所示内容，“-”表示不存在路径。图lx8-3 将路径信息输入表格里8.2建立求解最短路径问题模型建立解决问题的模型，如图lx8-4所示，其中C14:H19单元格区域用来记录实际的路径选择情况，0表示路径未选择，1表示选择了从某地出发前往某地的路径。“来源统计”用来统计出发地的情况，“目标统计”用来统计抵达地情况。图lx8-4 最短路径问题模型8.3规划求解最短路径问题（1）加载工具。单击【工具】【加载宏】菜单项，打开【加载宏】对话框。选中【规划求解】复选框，然后单击【确定】按钮将规划求解宏加载到Excel中。（2）在C4:H9单元格区域，将“-”用9999替代，如图lx8-5所示。用一个很大的数表示不存在的路径，避免以后选此路径。图lx8-5 用9999表示不存在路径（2）在I14单元格输入公式：=SUM(C14:H14)填充I15:I19单元格区域。在C20单元格输入公式：=SUM(C14:C19)填充D20:H20单元格区域。在J14单元格输入公式：=SUMPRODUCT(C4:H4,C14:H14)填充J15:J19单元格区域。在J20单元格输入公式：=SUM(J14:J19)设置C14:H19单元格区域的格式，选【格式】【单元格】【数字】【自定义】的“0”类型。（3）选中J20单元格，单击菜单【工具】【规划求解】，打开“规划求解参数”对话框，在“设置目标单元格”文本框中选J20单元格。选中【最小值】单选按钮。在“可变单元格”文本框中选择C14:H19单元格区域。（4）添加约束条件。单击【添加】按钮打开“添加约束”对话框添加如下约束条件：条件1：$C$14:$H$19=二进制条件2：$C$20=1，表示A为起点，必定存在以A为出发点的路径条件3：$I$19=1，表示F为终点，必定存在以F为抵达地的路径条件4：$I$14=0，表示以A为终点的路径不存在条件5：$H$20=0，表示以F为起点的路径不存在条件6：$D$20: $G$20=$I$15: $I$18，表示除A、F外，其余节点有进则有出各个条件添加完成后单击【确定】按钮返回“规划求解参数”对话框，结果如图lx8-6所示。图lx8-6 设置规划求解参数（5）为了提高规划求解的运算效率，单击“规划求解参数”对话框中的【选项】按钮，打开“规划求解选项”对话框，勾选其中的【采用线性模型】复选框，如图lx8-7所示。图lx8-7 采用线性规划模型（6）按【确定】返回“规划求解参数”对话框，单击【求解】按钮开始求解运算，显示找到一个结