2017年东北林业大学运筹学(同等学力加试)复试仿真模拟三套题
● 摘要
一、简答题
1． 试写出标准指派问题的线性规划问题。
【答案】
A ij 表示工作人员i 做工作j 时的工作效益 则得线性规划模型为:
2． 简述求解整数规划分枝定界法的基本思想。
【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界子区域（称为分支）的方法，逐步减小和增大
; 。分支定界法就是将B 的可行域分成
:， 最终求到z*。
二、计算题
3． 两家工厂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，首先将v s 标号为（0，+∞）3），
v 2（x 2，2），v 3（v 1，l ），v 4（x 1，11）。标号再无法继续下去，故算法停止。因此图上的可行流
为最大流，其流量为23。
相关内容
相关标签