扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 网络与最大流量困难
单选题
2020年5月第35题
收藏
分享
#数学与经济管理
#网络与最大流量
#第二版教材
#凯恩建议必须掌握
某运输网络图（见下图）有A~E五个结点，结点之间标有运输方向箭线，每条箭线旁标有两个数字，前一个是单位流量的运输费用，后一个是该箭线所允许的单位时间内的流量上限。从结点A到E可以有多种分配运输量的方案。如果每次都选择最小费用的路径来分配最大流量，则可以用最小总费用获得最大总流量的最优运输方案。该最优运输方案中，所需总费用和达到的总流量分别为（__）。
问题（1）
正确答案C
凯恩解析
此题考察网络与最大流量相关概念。
本题要求从结点1到结点6的最大流量，其实就是把从结点1到结点6所有的路径找出来，然后把每条路径的流量进行累加。
因为ACBE路径总的最小费用最小，所以根据题意优先计算。
路径ACBE的最大流量为5万吨，计算过后，该路径上各段流量应都减少5万吨。从而BC之间将断开，AC之间的剩余流量是3万吨，BE之间的剩余流量是2万吨（如下图）。
其次ABE上费用最小，所以抽取路径ABE上的最大流量，路径ABE的最大流量为2万吨，计算过后，该路径上各段流量应都减少2万吨。从而BE之间将断开，AB之间的剩余流量是8万吨（如下图）。
然后抽取路径ACDE上的最大流量，路径ACDE的最大流量为3万吨，计算过后，该路径上各段流量应都减少3万吨。从而AC之间将断开，CD之间的剩余流量是7万吨，DE之间的剩余流量是1万吨（如下图）。
然后抽取 ABDE 上的最大流量，计算过后，该路径上各段流量应都减少1万吨，从而DE之间将断开，至此起点到终点已经没有通路，所以算法结束。
所以A到E的最大流量为5+2+3+1=11，总费用为5*4+2*5+3*6+1*12=60。
答案为C选项。