2017年清华大学时专业综合运筹学考研复试核心题库
● 摘要
一、简答题
1． 试简述求解整数规划模型的分枝定界法剪枝的几种情况。
【答案】（l ）某枝已经达到其范围内的最优解;
（2）某枝域内没有可行解时，即是不可行域;
（3）某枝所得数据不优于当前最优解时。
2． 简述目标规划单纯形法求解的基本思想。
【答案】第一步，建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=l;
第二步，检查该行中是否存在负数，且对应的前k 一1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转第三步。若无负数。则转第五步;
第三步，按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别 的变量为换出变量;
第四步，按单纯形法进行基变换运算，建立新的计算表，返回第二步;
第五步，当k=K时，计算结束。表中的解即为满意解。否则置k=k+l，返回到第二步。
二、计算题
3． 一辆货车的有效载重量是20吨，载货有效空间是7×2.5×2m 。现有六件货物可供选择运输，每件货物 的重量、体积及收入如表所示。
表
另外，在货物4和5中优先运货物4，货物2和3不能混装，怎样安排货物运输使收入最大，建立数学模型， 说明是什么模型，可用什么方法求解（注:不要求求解）。
【答案】由题意建立数字模型如下:
该模型为0一1规划模型，可采用隐枚举法求解。
4． 用标号法求点V 1到点v 7的最大流，弧旁数字分别表示流量和容量。
图
【答案】（l ）标号过程:
①首先给v l 标上（0，+∞）
②检查v 1在弧（v 1，v 5）上，v 5的标号为（v l ，7）
③检查v 5，在弧（v 5，v 7）上，v 7的标号为（v 5，6）
因v 7有了标号，故转入调整过程。
（2）调整过程 按点的第一个标号找到一条增广链，按可行流:
在上调整f. 调整后得如图所示的
图
（3）对得到的可行流人进行标号:
①首先给v l 标上（0，+∞）
②检查v 1，在弧（v 1，v 3）上，v 3的标号为（v l ，2）
③检查v 3，在弧（v 3，v 6）上，v 6的标号为（v 3，2）
④检查v 6，在弧（v 6，v 7）上，v :的标号为（v 6，2）
因v 7有了标号，故转入调整过程。
（4）调整过程
按点的第一个标号找到一条增广链，按在上调整. 调整后得如图所示的可行流:
图
（5）对得到的可行流几进行标号:
①首先给v l 标上（0，+∞）
②检查v 1，在弧（v l ，v 2）上，v 2的标号为（v l ，2）
③检查v 2，在弧（v 2，v 5）上，v 5的标号为（v 5，2）
④检查v 5，在弧（v 5，v 6）上，v 6的标号为（v 5，2）
⑤检查v 6，在弧（v 6，v 7）上，v 7的标号为（v 6，2）
因v 7有了标号，故转入调整过程。
（6）调整过程
按点的第一个标号找到一条增广链，按在上调整. 调整后得如图所示的可行流:
图
（7）对得到的可行流进行标号:
①首先给v l 标上（0，+∞）
②检查v 1，在弧（v l ，v 5）上，v 5的标号为（v l ，l ）
③检查v 5，在弧（v 5，v 6）上，v 6的标号为（v 5，l ）
④检查v 6，在弧（v 6，v 7）上，v :的标号为（v 6，l ）
相关内容
相关标签