2016年成都理工大学管理科学学院运筹学(同等学力加试)复试笔试最后押题五套卷
● 摘要
目录
2016年成都理工大学管理科学学院运筹学（同等学力加试）复试笔试最后押题五套卷（一） . 2 2016年成都理工大学管理科学学院运筹学（同等学力加试）复试笔试最后押题五套卷（二） 15 2016年成都理工大学管理科学学院运筹学（同等学力加试）复试笔试最后押题五套卷（三） 23 2016年成都理工大学管理科学学院运筹学（同等学力加试）复试笔试最后押题五套卷（四） 34 2016年成都理工大学管理科学学院运筹学（同等学力加试）复试笔试最后押题五套卷（五） 45
一、计算题
1． 求图中所示的网络最大流。
图
【答案】令图中所有弧的可行流为0，同时给图中的中间顶点标上名称，如下图所示（弧旁的数字为
）。
图
用标号算法求最大流 步骤一
，依次给v 2标号（v S ，15），v 6标号（v 2，9），片标号（v 6，（l ）标号过程。先给v s 标号（0，+∞）9）。
（2）调整过程。在网络上寻找增广链
=
，如图双箭头所示。
图
由此得到新的可行流
，如图所示。对新的可行流，重复标号与调整过程。
图
步骤二
，再依次给v 3标号（v s ，10），v s 标号（v 3，9），v 7标号（v 5，（l ）标号过程。先给v s 标号（0，+∞）
9），v 8标号（v 7，9），v t 标号（v 8，9）。v t 己得到标号，因此转入调整过程。 （2）调整过程。在图所示网络上，寻找新的增广
链
，如图中双箭头所示。
，即
图
其他的保持
整过程。
不变。调整后得新的可行流
，如图所示。对此可行流继续标号与调
图
步骤三
，再依次给v 1标号（v s ，8），给v 3标号（v l ，7），（l ）标号过程。在图中，先给v s 标号（0，+∞），给v t 标号（v 4，5）给v 4标 号（v 3，6）。 此时，v t 己经得到标号，转入调整过程。 （2）调整过程。在中寻找增广链
，即 ，如图中双箭头所示。
图
在其他弧上，保持标号与调整过程。
于是，得到调整后的网络图，见图。对此可行流，同样重复
相关内容
相关标签