2017年天津财经大学管理科学与工程809管理科学与工程综合之运筹学考研冲刺密押题
● 摘要
一、选择题
1． 对于动态规划，下列说法正确的有（ ）
A. 在动态规划模型中，问题的阶段数等于问题中的子问题的数目
B. 动态规划中，定义状态时应保证在各个阶段中所做决策的相互独立性
C. 对一个动态规划问题，应用顺推成逆推解法可能会得出不同的最优解
D. 假如一个线性规划问题含有8个变量和6个约束，则用动态规划方法求解时将划分为6个阶段，每个阶 段的状态将有一个8维的向量组成
【答案】AB
【解析】对于一个动态规划问题，不论是采用顺推法还是逆推法，只能得到一个唯一的解; 假如一个线性规 划问题含有8个变量和6个约束，则用动态规划方法求解时将按照变量的个数划分为8个阶段，每个阶段的状态 将有一个6维的向量组成。
2． 运输问题中，m+n-l个变量构成基本可解的充要条件是它不含（ ）。
A. 松弛变量
B. 多余变量
C. 闭回路
D. 圈
【答案】C
【解析】位于闭回路上的一组变量，它们对应的运输问题约束条件的系数列向量线性相关，因而在运输问题基可行解的迭代过程中，不允许出现全部顶点由填有数字的格构成的闭回路。也就是说，在确定运输问题的基可行解时，除要求基变量的个数为（m+n-l）外，还要求运输表中填有数字的格不构成闭回路。
3． 网络计划中的某工序（i ，j ），估计的最乐观时间为a ，最可能时间为m ，最保守时间为b ，则该工序的 期望工时和方差可以按下面（ ）计算。
【答案】A
4． 求解指派问题的匈牙利方法要求系数矩阵中每个元素都是（ ）。
A. 非负的
B. 大于零
C. 无约束
D. 非零常数
【答案】A
【解析】系数矩阵中的系数表示的是费用、成本、时间等。
二、判断题
5． 用动态规划方法求最优解时，都是在行进方向规定后，均要顺着这个规定的行进方向，逐段找出最优途 径。（ ）
【答案】√
【解析】用递推法求解动态规划问题，首先将过程分成几个相互联系的阶段，选取状态变量和决策变量并定 义最优值函数，然后写出基本的递推关系式和基本方程。其行进方向的规定，即选择用逆推法还是顺推法。因 为动态规划的状态具有无后效性，所以必须按规定的行进方向逐段找出最优途径。
6． 在任一图G 中，当点集v 确定后，树图是G 中边数最少的连通图。， （ ）
【答案】×
【解析】连通且不含圈的无向图称为树。
7． 利用破圈法求赋权图的最小支撑树时，每次都是任取一个圈并去掉其中权最小的边，直到该赋权图不再 含圈时，便得到最小支撑树。（ ）
【答案】×
【解析】利用破圈法求最小支撑树时，每次任取一个圈，去掉圈中权最大的边。
8． 如果线性规划问题有最优解，则它对偶问题也一定有最优解。（ ）
【答案】√
【解析】由对偶定理知，原命题为真，且线性规划问题与它的对偶问题的最优值相等。
9． 已知y i *为线性规划问题的对偶问题的最优解，若y i *>0，则说明在最优生产计划中第i 种资源己经完全耗尽。（ ）
【答案】√
【解析】对偶问题互补松弛性质中
中第i 种资源已经完全耗尽。
，表明在最优生产计划
三、证明题
10．证明:设，则为G 的解的充要条件是:存在数
。（本章定理4）
，使得和分别是不等式组（I ）和（II ）的解，且
【答案】（l ）先证充分性。由于x*是不等式组（I ）的解，且
又由于是不等式组的解，且
②
由式①和式②，可知
故由教材第390页的定理3可知，（X ，Y ）为G 的解。 **则
，
**（2）再证必要性，由于（X ，Y ）为G 的解，所以有
，因此X 和Y 分别是不等式组（I ）和 （）**
的解，且v=VG 。
11．设线性规划问题1是
（）是其对偶问题的最优解。