2016年三峡大学水利与环境学院运筹学(同等学力加试)复试笔试最后押题五套卷
● 摘要
目录
2016年三峡大学水利与环境学院运筹学（同等学力加试）复试笔试最后押题五套卷（一） . .... 2
2016年三峡大学水利与环境学院运筹学（同等学力加试）复试笔试最后押题五套卷（二） . .. 14
2016年三峡大学水利与环境学院运筹学（同等学力加试）复试笔试最后押题五套卷（三） . .. 24
2016年三峡大学水利与环境学院运筹学（同等学力加试）复试笔试最后押题五套卷（四） . .. 33
2016年三峡大学水利与环境学院运筹学（同等学力加试）复试笔试最后押题五套卷（五） . .. 42
一、计算题
1． 求如图所示的网络最小费用最大流，每条弧旁的数字为。
图
【答案】给网络中的中间点加上名称，如图所示。
（l ）取为初始可行流。
（2）依照下列方法构造有向赋权图，如图所示。
并求出从v s 到v t 的最短路（v s ，
v 2，v 4，v t ），如图所示（双箭头即为最短路）。
图
（3）在原网络D 中，与这条最短路相应的增广链为
（4），如图所示。 。
图
（5）构造有问赋权图，井求出从v s 到v t 的最短路
最短路）。
，如图所示（其双箭头即为
图
（6）在原网络中，与这条最短路相应的增广链为
（7）在上调整流量，令，得，如图所示。
。
图
（8）构造有向赋权图，并求出从v s 到v t 的最短路，如图所示。因为图己不存在从v s 到v t 的最 短路，故币单位）。 为网络的最小费用最大流。其最大流量为，而最小费用为（货
图
2． 下述论断正确与否:可行流f 的流量为零，即v （f ）=0，当且仅当f 是零流。
【答案】论断错误。 流量，只表明发点的净输出量为零，可能流出等于流入，此时，但f 不是零流。
3． 银行要把总行与支行的计算机直接或间接地连接起来，保持连通，其中任意两银行之间的距离如表所示，而连接线费用为0.2万元/百米，求总费用最小的连接方案及最小总费用。
表
【答案】构建图论模型，如图所示。
图
采用破圈法，如图所示。求得最小支撑树，即为最优连接方案