2016年南京师范大学计算机科学与技术学院F161运筹学考研复试题库
● 摘要
一、计算题
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． 某省重视智力投资，省政府决定从地方财政收入中拨款给两所大学。甲大学所得经费将有30%用于科研，40%用于购置教学，30%用于校舍建设，乙大学用于科研、教学和校舍建设的相应比例为30%、50%和20%。省政府考虑的目标是:第一优先:两校用于校舍建设的总款额不得超过1刃万元。第二优先:两校科研总经费希望能达到210万元，教学总经费希望能达到2刃万元，如果在第一优先目标限制下无法达到这些数目，则希望差 额越少越好。又因为教学仪器的短缺将影响教学质量，因此，省政府认为教学经费的短缺比科研经费的短缺加倍 的不好。第三优先:甲大学所得经费不要超过240万元，因为甲大学是部属重点大学，教育部还会拨款给它。由 于经费有限，乙大学所得经费也不要超过500万元。求省政府拨款的最优方案，试建立反映本问题的目标规划数 学模型（注:不用求解）。 【答案】由题意可知:
设X 1，X 2分别表示省政府拨给甲、乙两个大学的总经费。 d 1, d 1分别表示两校用于校舍建设超过和不足总经费的部分。 d 2+, d 2分别表示两校用于科研超过和不足总经费的部分。
+
-