用求解网络最大流问题

子任务5.4　用Excel求解网络最大流问题

5.4.1　任务引入

【任务5-4】　图5-22是连接某产品产地和销地的运输图。弧旁括号内第一个数字表示这条运输线的最大通过能力，括号内第二个数字表示该弧上的实际流。现要求制订一个运输方案，使从v₁运到v₇的产品数量最多。

5.4.2　任务实施

用Excel实施任务：

任务中所表示的网络最大流问题的线性规划模型。

解：设可行流f，则其线性规划模型为

maxz=V（f）

图5-22　连接某产品产地和销地运输图

第一步：输入数据部分，如图5-23所示。

图5-23　网络最大流数据输入

第二步：模型部分输入，如图5-24所示。

图5-24　模型部分输入

其中单元格

C21=SUM（C15：C20）；D21=SUM（D15：D20）；E21=SUM（E15：E20）；F21= SUM（F15：F20）；

G21=SUM（G15：G20）；H21=SUM（H15：H20）；I15=SUM（C15：H15）；I16= SUM（C16：H16）；

I17=SUM（C17：H17）；I18=SUM（C18：H18）；I19=SUM（C19：H19）；I20= SUM（C20：H20）；

C22=I16，D22=I17，E22=I18，F22=I19，G22=I20，H22=I15；C24=I15。

第三步：选择“工具”→“规划求解”，按图5-25所示进行输入。

图5-25　规划求解设置

第四步：单击“选项”，选择“采用线性模型”和“假定非负”，如图5-26所示。

图5-26　规划求解选项设置

第五步：单击“确定”，选择“保存规划求解结果”，结果如图5-27所示。

图5-27　网络最大流规划求解结果