2016年青岛科技大学数理学院运筹学(同等学力加试)复试笔试仿真模拟题
● 摘要
一、计算题
1． 两家工厂x 1和x 2生产一种商品，商品通过如图所示的网络运送到市场y 1，y 2，y 3，试用标号法确定从工厂到市场所能运送的最大总量。
图
【答案】增加v s 和v t 令所有弧上可行流为零，同时给图中的中间点标上名称，如图所示。
图
用网络流的标号算法求该问题的最大流。 步骤一
到标
号。
（2）调整过程。找到一条增广链为得到新的可行流
。
，如图所示，
，进行流量调整，
图
步骤二
（l ）标号过程。对图中的可行流
。V t 得到标号。
（2）调整过程。找到一条新的增广链在
上调整流量，得新的可行流
，如图所示。
，如图中双箭头所示，令
，
进行重新标号:
图
步骤五
（l ）标号过程。将图重新标号:
v t 得到标号。
（2）调整过程。在增广链可行流
，如图所示。
上，令
调整流量，于是得新的
图
步骤六
，再将x 1标号为（v s ，19），将x 2标号为（v s ，4），v 1标号为（x 1，3），首先将v s 标号为（0，+∞）
v 2（x 2，2），v 3（v 1，l ），v 4（x 1，11）。标号再无法继续下去，故算法停止。因此图上的可行流为最大流，其流量为23。
于是，有
其割集如图所示。
2． 已知下列资料，如表所示:
表
求出这项工程的最低成本日程。
【答案】由表中的己知条件和数据，绘制如图所示的网络图。
相关内容
相关标签