2017年沈阳理工大学经济管理学院818运筹学考研强化模拟题
● 摘要
一、选择题
1． 对于动态规划，下列说法正确的有（ ）
A. 在动态规划模型中，问题的阶段数等于问题中的子问题的数目
B. 动态规划中，定义状态时应保证在各个阶段中所做决策的相互独立性
C. 对一个动态规划问题，应用顺推成逆推解法可能会得出不同的最优解
D. 假如一个线性规划问题含有8个变量和6个约束，则用动态规划方法求解时将划分为6个阶段，每个阶 段的状态将有一个8维的向量组成
【答案】AB
【解析】对于一个动态规划问题，不论是采用顺推法还是逆推法，只能得到一个唯一的解; 假如一个线性规 划问题含有8个变量和6个约束，则用动态规划方法求解时将按照变量的个数划分为8个阶段，每个阶段的状态 将有一个6维的向量组成。
2． 设线性规划
A. 基本可行解
B. 基本可行最优解
C. 最优解
D. 基本解
【答案】A
【解析】可行解包括基可行解与非基可行解。
3． 求一个赋权图中包括指定边集的最小连接方案（最小树），下面（ ）方法是正确的。
A. 最小树的初始边集为图中最小权边，按其余各边的权从小到大，逐一检查选取
B. 最小树的初始边集为某一条指定边，按其余各边边的权从小到大，逐一检查选取
C. 最小树的初始边集为所有指定边的集合，按其余各边边的权从小到大，逐一检查选取
D. 最小树的初始边集为权最小的一条指定边，按其余各边边的权从小到大，逐一检查选取
【答案】C
【解析】该问题不是简单的最短路问题，它要求最小连接方案包括指定边集，所以，最小树的初始边集应为 所有指定边的集合。
4． 运输问题中，m+n-l个变量构成基本可解的充要条件是它不含（ ）。
A. 松弛变量
第 2 页，共 63 页 有可行解，则此线性规划一定有（ ）。
B. 多余变量
C. 闭回路
D. 圈
【答案】C
【解析】位于闭回路上的一组变量，它们对应的运输问题约束条件的系数列向量线性相关，因而在运输问题基可行解的迭代过程中，不允许出现全部顶点由填有数字的格构成的闭回路。也就是说，在确定运输问题的基可行解时，除要求基变量的个数为（m+n-l）外，还要求运输表中填有数字的格不构成闭回路。
二、计算题
5． 某产品有12道加工工序，它们之间的顺序关系如下:工序A 、B 、C 是同时开始的工序; 工序A 、B 的 紧后工序是D ; 工序B 的紧后工序是E 、F 、H ; 工序F 、C 的紧后工序是G ; 工序E 、H 的紧后工序是I 、J ; 工 序C 、D 、F 、J 的紧后工序是K ; 工序K 的紧后工序是L ; 产品在工序I 、G 、L 完成后完工。画出该问题的网络 计划图。
【答案】该问题的网络计划图如图所示。
图
6． 用标号法求点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）调整过程 按点的第一个标号找到一条增广链，按第 3 页，共 63 页 在上调整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）调整过程
按点的第一个标号找到一条增广链，按在上调整. 调整后得如图所示的可行流:
第 4 页，共 63 页
相关内容
相关标签