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． 某工地为了研究发放工具应设置几个窗口，对于请领和发放工具分别做了调查记录。 （l ）以10分钟为一段，记录了100段时间内每段到来请领工具的工人数，如表所示。
表
，如表所示 （2）记录了1000次发放工具（服务）所用时间（秒）
表
试完成下列问题:
相关内容
相关标签